List


1   // $Id: List.java,v 1.10 2005/04/12 12:59:21 belaban Exp $
2   
3   package org.jgroups.util;
4   
5   import java.io.*;
6   import java.util.Enumeration  ;
7   import java.util.NoSuchElementException  ;
8   import java.util.Vector  ;
9   
10  
11  /**
12   * Doubly-linked list. Elements can be added at head or tail and removed from head/tail.
13   * This class is tuned for element access at either head or tail, random access to elements
14   * is not very fast; in this case use Vector. Concurrent access is supported: a thread is blocked
15   * while another thread adds/removes an object. When no objects are available, removal returns null.
16   * @author Bela Ban
17   */
18  public class List implements Externalizable, Cloneable   {
19      protected Element head=null, tail=null;
20      protected int     size=0;
21      protected transient final Object    mutex=new Object  ();
22  
23  
24  
25      class Element {
26          Object   obj=null;
27          Element next=null;
28          Element prev=null;
29  
30          Element(Object   o) {
31              obj=o;
32          }
33      }
34  
35  
36      public List() {
37      }
38  
39  
40      /**
41       Adds an object at the tail of the list.
42       */
43      public void add(Object   obj) {
44          Element el=new Element(obj);
45  
46          synchronized(mutex) {
47              if(head == null) {
48                  head=el;
49                  tail=head;
50                  size=1;
51              }
52              else {
53                  el.prev=tail;
54                  tail.next=el;
55                  tail=el;
56                  size++;
57              }
58          }
59      }
60  
61      /**
62       Adds an object at the head of the list.
63       */
64      public void addAtHead(Object   obj) {
65          Element el=new Element(obj);
66  
67          synchronized(mutex) {
68              if(head == null) {
69                  head=el;
70                  tail=head;
71                  size=1;
72              }
73              else {
74                  el.next=head;
75                  head.prev=el;
76                  head=el;
77                  size++;
78              }
79          }
80      }
81  
82  
83      /**
84       Removes an object from the tail of the list. Returns null if no elements available
85       */
86      public Object   remove() {
87          Element retval=null;
88  
89          synchronized(mutex) {
90              if(tail == null)
91                  return null;
92              retval=tail;
93              if(head == tail) { // last element
94                  head=null;
95                  tail=null;
96              }
97              else {
98                  tail.prev.next=null;
99                  tail=tail.prev;
100                 retval.prev=null;
101             }
102 
103             size--;
104         }
105         return retval.obj;
106     }
107 
108 
109     /** Removes an object from the head of the list. Returns null if no elements available */
110     public Object   removeFromHead() {
111         Element retval=null;
112 
113         synchronized(mutex) {
114             if(head == null)
115                 return null;
116             retval=head;
117             if(head == tail) { // last element
118                 head=null;
119                 tail=null;
120             }
121             else {
122                 head=head.next;
123                 head.prev=null;
124                 retval.next=null;
125             }
126             size--;
127         }
128         return retval.obj;
129     }
130 
131 
132     /**
133      Returns element at the tail (if present), but does not remove it from list.
134      */
135     public Object   peek() {
136         synchronized(mutex) {
137             return tail != null ? tail.obj : null;
138         }
139     }
140 
141 
142     /**
143      Returns element at the head (if present), but does not remove it from list.
144      */
145     public Object   peekAtHead() {
146         synchronized(mutex) {
147             return head != null ? head.obj : null;
148         }
149     }
150 
151 
152     /**
153      Removes element <code>obj</code> from the list, checking for equality using the <code>equals</code>
154      operator. Only the first duplicate object is removed. Returns the removed object.
155      */
156     public Object   removeElement(Object   obj) {
157         Element el=null;
158         Object   retval=null;
159 
160         synchronized(mutex) {
161             el=head;
162             while(el != null) {
163                 if(el.obj.equals(obj)) {
164                     retval=el.obj;
165                     if(head == tail) {           // only 1 element left in the list
166                         head=null;
167                         tail=null;
168                     }
169                     else
170                         if(el.prev == null) {  // we're at the head
171                             head=el.next;
172                             head.prev=null;
173                             el.next=null;
174                         }
175                         else
176                             if(el.next == null) {  // we're at the tail
177                                 tail=el.prev;
178                                 tail.next=null;
179                                 el.prev=null;
180                             }
181                             else {                      // we're somewhere in the middle of the list
182                                 el.prev.next=el.next;
183                                 el.next.prev=el.prev;
184                                 el.next=null;
185                                 el.prev=null;
186                             }
187                     size--;
188                     break;
189                 }
190 
191                 el=el.next;
192             }
193         }
194         return retval;
195     }
196 
197 
198     public void removeAll() {
199         synchronized(mutex) {
200             size=0;
201             head=null;
202             tail=null;
203         }
204     }
205 
206 
207     public int size() {
208         return size;
209     }
210 
211     public String   toString() {
212         StringBuffer   ret=new StringBuffer  ("[");
213         Element el=head;
214 
215         while(el != null) {
216             if(el.obj != null)
217                 ret.append(el.obj + " ");
218             el=el.next;
219         }
220         ret.append(']');
221         return ret.toString();
222     }
223 
224 
225     public String   dump() {
226         StringBuffer   ret=new StringBuffer  ("[");
227         for(Element el=head; el != null; el=el.next)
228             ret.append(el.obj + " ");
229 
230         return ret.toString() + ']';
231     }
232 
233 
234     public Vector   getContents() {
235         Vector   retval=new Vector  (size);
236         Element el;
237 
238         synchronized(mutex) {
239             el=head;
240             while(el != null) {
241                 retval.addElement(el.obj);
242                 el=el.next;
243             }
244         }
245         return retval;
246     }
247 
248 
249     public Enumeration   elements() {
250         return new ListEnumerator(head);
251     }
252 
253 
254     public boolean contains(Object   obj) {
255         Element el=head;
256 
257         while(el != null) {
258             if(el.obj != null && el.obj.equals(obj))
259                 return true;
260             el=el.next;
261         }
262         return false;
263     }
264 
265 
266     public List copy() {
267         List retval=new List();
268 
269         synchronized(mutex) {
270             for(Element el=head; el != null; el=el.next)
271                 retval.add(el.obj);
272         }
273         return retval;
274     }
275 
276 
277     protected Object   clone() throws CloneNotSupportedException   {
278         // calling clone() is superfluous because we don't want a shallow copy
279         return copy();
280     }
281 
282 
283 
284     public void writeExternal(ObjectOutput out) throws IOException {
285         Element el;
286 
287         synchronized(mutex) {
288             el=head;
289             out.writeInt(size);
290             for(int i=0; i < size; i++) {
291                 out.writeObject(el.obj);
292                 el=el.next;
293             }
294         }
295     }
296 
297 
298     public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException   {
299         Object   obj;
300         int new_size=in.readInt();
301 
302         if(new_size == 0)
303             return;
304         for(int i=0; i < new_size; i++) {
305             obj=in.readObject();
306             add(obj);
307         }
308     }
309 
310 
311 //    public void writeTo(DataOutputStream out) throws IOException {
312 //        Element el;
313 //        Object obj;
314 //        if(size == 0) {
315 //            out.writeInt(0);
316 //            return;
317 //        }
318 //        out.writeInt(size);
319 //        el=head;
320 //        while(el != null) {
321 //            obj=el.obj;
322 //            if(obj instanceof Streamable) {
323 //                out.writeByte(1);
324 //                ((Streamable)obj).writeTo(out);
325 //            }
326 //            else {
327 //                out.writeByte(0);
328 //                ObjectOutputStream oos=new ObjectOutputStream(out); // very inefficient
329 //                oos.writeObject(obj);
330 //                oos.close();
331 //            }
332 //            el=el.next;
333 //        }
334 //    }
335 //
336 //    public void readFrom(DataInputStream in) throws IOException, IllegalAccessException, InstantiationException {
337 //        Object obj;
338 //        int    size=in.readInt();
339 //        byte   b;
340 //
341 //        for(int i=0; i < size; i++) {
342 //            b=in.readByte();
343 //            if(b == 1) {
344 //
345 //            }
346 //            else if(b == 0) {
347 //
348 //            }
349 //            else
350 //                throw new InstantiationException("byte '" + b + "' not recognized (needs to be 1 or 0)");
351 //        }
352 //
353 //    }
354 
355 
356 
357 
358     class ListEnumerator implements Enumeration   {
359         Element curr=null;
360 
361         ListEnumerator(Element start) {
362             curr=start;
363         }
364 
365         public boolean hasMoreElements() {
366             return curr != null;
367         }
368 
369         public Object   nextElement() {
370             Object   retval;
371 
372             if(curr == null)
373                 throw new NoSuchElementException  ();
374             retval=curr.obj;
375             curr=curr.next;
376             return retval;
377         }
378 
379     }
380 
381 
382 
383 
384 //      public static void main(String args[]) {
385 //      List l=new List();
386 
387 //      l.add("Bela");
388 //      l.add("Janet");
389 //      l.add("Marco");
390 //      l.add("Ralph");
391 
392 //      for(Enumeration e=l.elements(); e.hasMoreElements();) {
393 //          System.out.println(e.nextElement());
394 //      }
395 
396 //      System.out.println(l + ".contains(\"Bela\"): " + l.contains("Bela"));
397 
398 
399 //      l.add(new Integer(1));
400 //      l.add(new Integer(2));
401 //      l.add(new Integer(5));
402 //      l.add(new Integer(6));
403 
404 
405 //      System.out.println(l + ".contains(2): " + l.contains(new Integer(2)));
406 //      }
407 
408 
409 
410 
411 
412 
413     public static void main(String  [] args) {
414         List l=new List();
415         Long   n;
416 
417 
418         l.addAtHead(new Integer  (1));
419         l.addAtHead(new Integer  (2));
420         l.addAtHead(new Integer  (3));
421         l.addAtHead(new Integer  (4));
422         l.addAtHead(new Integer  (5));
423 
424         System.out.println("Removed from head: " + l.removeFromHead());
425         System.out.println("Removed from head: " + l.removeFromHead());
426         System.out.println("Removed from head: " + l.removeFromHead());
427         System.out.println("Removed from head: " + l.removeFromHead());
428         System.out.println("Removed from head: " + l.removeFromHead());
429         System.out.println("Removed from head: " + l.removeFromHead());
430         System.out.println("Removed from head: " + l.removeFromHead());
431 
432 
433         System.out.print("Adding 50000 numbers:");
434         for(long i=0; i < 50000; i++) {
435             n=new Long  (i);
436             if(i % 2 == 0) {
437                 l.addAtHead(n);
438             }
439             else {
440                 l.add(n);
441             }
442         }
443         System.out.println(" OK");
444 
445         long num=0;
446         System.out.print("Removing all elements: ");
447         while((l.remove()) != null)
448             num++;
449         System.out.println("OK, removed " + num + " objects");
450     }
451 
452 
453 
454 
455 
456 }
457
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags