001: // $Id: List.java,v 1.12 2006/10/10 15:46:24 belaban Exp $
002:
003: package org.jgroups.util;
004:
005: import java.io.*;
006: import java.util.*;
007:
008: /**
009: * Doubly-linked list. Elements can be added at head or tail and removed from head/tail.
010: * This class is tuned for element access at either head or tail, random access to elements
011: * is not very fast; in this case use Vector. Concurrent access is supported: a thread is blocked
012: * while another thread adds/removes an object. When no objects are available, removal returns null.
013: * @author Bela Ban
014: */
015: public class List implements Externalizable, Cloneable {
016: protected Element head = null, tail = null;
017: protected int size = 0;
018: protected transient final Object mutex = new Object();
019:
020: class Element {
021: Object obj = null;
022: Element next = null;
023: Element prev = null;
024:
025: Element(Object o) {
026: obj = o;
027: }
028: }
029:
030: public List() {
031: }
032:
033: /**
034: Adds an object at the tail of the list.
035: */
036: public void add(Object obj) {
037: Element el = new Element(obj);
038:
039: synchronized (mutex) {
040: if (head == null) {
041: head = el;
042: tail = head;
043: size = 1;
044: } else {
045: el.prev = tail;
046: tail.next = el;
047: tail = el;
048: size++;
049: }
050: }
051: }
052:
053: /**
054: Adds an object at the head of the list.
055: */
056: public void addAtHead(Object obj) {
057: Element el = new Element(obj);
058:
059: synchronized (mutex) {
060: if (head == null) {
061: head = el;
062: tail = head;
063: size = 1;
064: } else {
065: el.next = head;
066: head.prev = el;
067: head = el;
068: size++;
069: }
070: }
071: }
072:
073: public void addAll(Collection c) {
074: if (c == null)
075: return;
076: for (Iterator it = c.iterator(); it.hasNext();) {
077: add(it.next());
078: }
079: }
080:
081: /**
082: Removes an object from the tail of the list. Returns null if no elements available
083: */
084: public Object remove() {
085: Element retval = null;
086:
087: synchronized (mutex) {
088: if (tail == null)
089: return null;
090: retval = tail;
091: if (head == tail) { // last element
092: head = null;
093: tail = null;
094: } else {
095: tail.prev.next = null;
096: tail = tail.prev;
097: retval.prev = null;
098: }
099:
100: size--;
101: }
102: return retval.obj;
103: }
104:
105: /** Removes an object from the head of the list. Returns null if no elements available */
106: public Object removeFromHead() {
107: Element retval = null;
108:
109: synchronized (mutex) {
110: if (head == null)
111: return null;
112: retval = head;
113: if (head == tail) { // last element
114: head = null;
115: tail = null;
116: } else {
117: head = head.next;
118: head.prev = null;
119: retval.next = null;
120: }
121: size--;
122: }
123: return retval.obj;
124: }
125:
126: /**
127: Returns element at the tail (if present), but does not remove it from list.
128: */
129: public Object peek() {
130: synchronized (mutex) {
131: return tail != null ? tail.obj : null;
132: }
133: }
134:
135: /**
136: Returns element at the head (if present), but does not remove it from list.
137: */
138: public Object peekAtHead() {
139: synchronized (mutex) {
140: return head != null ? head.obj : null;
141: }
142: }
143:
144: /**
145: Removes element <code>obj</code> from the list, checking for equality using the <code>equals</code>
146: operator. Only the first duplicate object is removed. Returns the removed object.
147: */
148: public Object removeElement(Object obj) {
149: Element el = null;
150: Object retval = null;
151:
152: synchronized (mutex) {
153: el = head;
154: while (el != null) {
155: if (el.obj.equals(obj)) {
156: retval = el.obj;
157: if (head == tail) { // only 1 element left in the list
158: head = null;
159: tail = null;
160: } else if (el.prev == null) { // we're at the head
161: head = el.next;
162: head.prev = null;
163: el.next = null;
164: } else if (el.next == null) { // we're at the tail
165: tail = el.prev;
166: tail.next = null;
167: el.prev = null;
168: } else { // we're somewhere in the middle of the list
169: el.prev.next = el.next;
170: el.next.prev = el.prev;
171: el.next = null;
172: el.prev = null;
173: }
174: size--;
175: break;
176: }
177:
178: el = el.next;
179: }
180: }
181: return retval;
182: }
183:
184: public void removeAll() {
185: synchronized (mutex) {
186: size = 0;
187: head = null;
188: tail = null;
189: }
190: }
191:
192: public int size() {
193: return size;
194: }
195:
196: public String toString() {
197: StringBuffer ret = new StringBuffer("[");
198: Element el = head;
199:
200: while (el != null) {
201: if (el.obj != null)
202: ret.append(el.obj).append(" ");
203: el = el.next;
204: }
205: ret.append(']');
206: return ret.toString();
207: }
208:
209: public String dump() {
210: StringBuffer ret = new StringBuffer("[");
211: for (Element el = head; el != null; el = el.next)
212: ret.append(el.obj).append(" ");
213:
214: return ret.toString() + ']';
215: }
216:
217: public Vector getContents() {
218: Vector retval = new Vector(size);
219: Element el;
220:
221: synchronized (mutex) {
222: el = head;
223: while (el != null) {
224: retval.addElement(el.obj);
225: el = el.next;
226: }
227: }
228: return retval;
229: }
230:
231: public Enumeration elements() {
232: return new ListEnumerator(head);
233: }
234:
235: public boolean contains(Object obj) {
236: Element el = head;
237:
238: while (el != null) {
239: if (el.obj != null && el.obj.equals(obj))
240: return true;
241: el = el.next;
242: }
243: return false;
244: }
245:
246: public List copy() {
247: List retval = new List();
248:
249: synchronized (mutex) {
250: for (Element el = head; el != null; el = el.next)
251: retval.add(el.obj);
252: }
253: return retval;
254: }
255:
256: protected Object clone() throws CloneNotSupportedException {
257: // calling clone() is superfluous because we don't want a shallow copy
258: return copy();
259: }
260:
261: public void writeExternal(ObjectOutput out) throws IOException {
262: Element el;
263:
264: synchronized (mutex) {
265: el = head;
266: out.writeInt(size);
267: for (int i = 0; i < size; i++) {
268: out.writeObject(el.obj);
269: el = el.next;
270: }
271: }
272: }
273:
274: public void readExternal(ObjectInput in) throws IOException,
275: ClassNotFoundException {
276: Object obj;
277: int new_size = in.readInt();
278:
279: if (new_size == 0)
280: return;
281: for (int i = 0; i < new_size; i++) {
282: obj = in.readObject();
283: add(obj);
284: }
285: }
286:
287: // public void writeTo(DataOutputStream out) throws IOException {
288: // Element el;
289: // Object obj;
290: // if(size == 0) {
291: // out.writeInt(0);
292: // return;
293: // }
294: // out.writeInt(size);
295: // el=head;
296: // while(el != null) {
297: // obj=el.obj;
298: // if(obj instanceof Streamable) {
299: // out.writeByte(1);
300: // ((Streamable)obj).writeTo(out);
301: // }
302: // else {
303: // out.writeByte(0);
304: // ObjectOutputStream oos=new ObjectOutputStream(out); // very inefficient
305: // oos.writeObject(obj);
306: // oos.close();
307: // }
308: // el=el.next;
309: // }
310: // }
311: //
312: // public void readFrom(DataInputStream in) throws IOException, IllegalAccessException, InstantiationException {
313: // Object obj;
314: // int size=in.readInt();
315: // byte b;
316: //
317: // for(int i=0; i < size; i++) {
318: // b=in.readByte();
319: // if(b == 1) {
320: //
321: // }
322: // else if(b == 0) {
323: //
324: // }
325: // else
326: // throw new InstantiationException("byte '" + b + "' not recognized (needs to be 1 or 0)");
327: // }
328: //
329: // }
330:
331: class ListEnumerator implements Enumeration {
332: Element curr = null;
333:
334: ListEnumerator(Element start) {
335: curr = start;
336: }
337:
338: public boolean hasMoreElements() {
339: return curr != null;
340: }
341:
342: public Object nextElement() {
343: Object retval;
344:
345: if (curr == null)
346: throw new NoSuchElementException();
347: retval = curr.obj;
348: curr = curr.next;
349: return retval;
350: }
351:
352: }
353:
354: // public static void main(String args[]) {
355: // List l=new List();
356:
357: // l.add("Bela");
358: // l.add("Janet");
359: // l.add("Marco");
360: // l.add("Ralph");
361:
362: // for(Enumeration e=l.elements(); e.hasMoreElements();) {
363: // System.out.println(e.nextElement());
364: // }
365:
366: // System.out.println(l + ".contains(\"Bela\"): " + l.contains("Bela"));
367:
368: // l.add(new Integer(1));
369: // l.add(new Integer(2));
370: // l.add(new Integer(5));
371: // l.add(new Integer(6));
372:
373: // System.out.println(l + ".contains(2): " + l.contains(new Integer(2)));
374: // }
375:
376: public static void main(String[] args) {
377: List l = new List();
378: Long n;
379:
380: l.addAtHead(new Integer(1));
381: l.addAtHead(new Integer(2));
382: l.addAtHead(new Integer(3));
383: l.addAtHead(new Integer(4));
384: l.addAtHead(new Integer(5));
385:
386: System.out.println("Removed from head: " + l.removeFromHead());
387: System.out.println("Removed from head: " + l.removeFromHead());
388: System.out.println("Removed from head: " + l.removeFromHead());
389: System.out.println("Removed from head: " + l.removeFromHead());
390: System.out.println("Removed from head: " + l.removeFromHead());
391: System.out.println("Removed from head: " + l.removeFromHead());
392: System.out.println("Removed from head: " + l.removeFromHead());
393:
394: System.out.print("Adding 50000 numbers:");
395: for (long i = 0; i < 50000; i++) {
396: n = new Long(i);
397: if (i % 2 == 0) {
398: l.addAtHead(n);
399: } else {
400: l.add(n);
401: }
402: }
403: System.out.println(" OK");
404:
405: long num = 0;
406: System.out.print("Removing all elements: ");
407: while ((l.remove()) != null)
408: num++;
409: System.out.println("OK, removed " + num + " objects");
410: }
411:
412: }
|