CopyOnWriteArrayList


1   /*
2     File: CopyOnWriteArrayList.java
3   
4     Written by Doug Lea. Adapted and released, under explicit
5     permission, from JDK1.2 ArrayList.java
6     which carries the following copyright:
7   
8        * Copyright 1997 by Sun Microsystems, Inc.,
9        * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
10       * All rights reserved.
11       *
12       * This software is the confidential and proprietary information
13       * of Sun Microsystems, Inc. ("Confidential Information").  You
14       * shall not disclose such Confidential Information and shall use
15       * it only in accordance with the terms of the license agreement
16       * you entered into with Sun.
17  
18    History:
19    Date       Who                What
20    21Jun1998  dl               Create public version
21     9Oct1999  dl               faster equals
22    29jun2001  dl               Serialization methods now private
23  */
24  
25  package EDU.oswego.cs.dl.util.concurrent;
26  import java.util.*;
27  
28  /**
29   * This class implements a variant of java.util.ArrayList in which
30   * all mutative operations (add, set, and so on) are implemented
31   * by making a fresh copy of the underlying array.
32   * <p>
33   * This is ordinarily too costly, but it becomes attractive when traversal
34   * operations vastly overwhelm mutations, and, especially, 
35   * when you cannot or don't want to
36   * synchronize traversals, yet need to preclude interference
37   * among concurrent threads.
38   * The iterator method uses a reference to the
39   * state of the array at the point that the
40   * iterator was created. This array never changes during
41   * the lifetime of the iterator, so interference is impossible.
42   * (The iterator will not traverse elements added or changed
43   * since the iterator was created, but usually this is a desirable
44   * feature.) 
45   * <p>
46   * As much code and documentation as possible was shamelessly copied from
47   * java.util.ArrayList (Thanks, Josh!), with the intent of preserving
48   * all semantics of ArrayList except for the copy-on-write 
49   * property.
50   * (The java.util
51   * collection code could not be subclassed here since all of the existing
52   * collection classes assume elementwise mutability.)
53   * <p>
54   * Because of the copy-on-write policy, some one-by-one
55   * mutative operations
56   * in the java.util.Arrays and java.util.Collections classes 
57   * are so time/space intensive as to never
58   * be worth calling (except perhaps as benchmarks for garbage collectors :-).
59   * <p>
60   * Three methods are supported in addition to
61   * those described in List and ArrayList. The addIfAbsent 
62   * and addAllAbsent methods provide Set semantics for add,
63   * and are used in CopyOnWriteArraySet. However, they
64   * can also be used directly from this List version.
65   * The copyIn method (and
66   * a constructor that invokes it) allow
67   * you to copy in an initial array to use. This method can
68   * be useful when you first want to perform many operations
69   * on a plain array, and then make a copy available for
70   * use through the collection API.
71   * <p>
72   * Due to their strict read-only nature, 
73   * element-changing operations on iterators
74   * (remove, set, and add) are not supported. These
75   * are the only methods throwing UnsupportedOperationException.
76   * <p>
77   * <p>[<a HREF="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
78   * @see CopyOnWriteArraySet
79   **/
80  
81  
82  public class CopyOnWriteArrayList implements List, Cloneable  , java.io.Serializable   {
83    /**
84     * The held array. Directly access only within synchronized
85     *  methods
86     */
87  
88    protected transient Object  [] array_;
89  
90    /**
91     * Accessor to the array intended to be called from
92     * within unsynchronized read-only methods
93     **/
94    protected synchronized Object  [] array() { return array_; }
95  
96    /**
97     * Constructs an empty list
98     *
99     */
100   public CopyOnWriteArrayList() {
101     array_ = new Object  [0];
102   }
103 
104   /**
105    * Constructs an list containing the elements of the specified
106    * Collection, in the order they are returned by the Collection's
107    * iterator.  
108    */
109   public CopyOnWriteArrayList(Collection c) {
110     array_ = new Object  [c.size()];
111     Iterator i = c.iterator();
112     int size = 0;
113     while (i.hasNext())
114       array_[size++] = i.next();
115   }
116 
117   /** 
118    * Create a new CopyOnWriteArrayList holding a copy of given array 
119    * @param toCopyIn the array. A copy of this array is used as the
120    * internal array.
121    **/
122   public CopyOnWriteArrayList(Object  [] toCopyIn) {
123     copyIn(toCopyIn, 0, toCopyIn.length);
124   }
125 
126   /**
127    * Replace the held array with a copy of the <code>n</code>
128    * elements of the provided array, starting at position <code>first</code>.
129    * To copy an entire array, call with arguments (array, 0, array.length).
130    * @param toCopyIn the array. A copy of the indicated elements of
131    * this  array is used as the
132    * internal array.
133    * @param first The index of first position of the array to 
134    * start copying from.
135    * @param n the number of elements to copy. This will be the new size of
136    * the list.
137   **/
138   public synchronized void copyIn(Object  [] toCopyIn, int first, int n) {
139     array_  = new Object  [n]; 
140     System.arraycopy(toCopyIn, first, array_, 0, n);
141   }
142 
143   /**
144    * Returns the number of components in this list.
145    *
146    * @return  the number of components in this list.
147    */
148   public int size() {
149     return array().length;
150   }
151 
152   /**
153    * Tests if this list has no components.
154    *
155    * @return  <code>true</code> if this list has no components;
156    *          <code>false</code> otherwise.
157    */
158   public boolean isEmpty() {
159     return size() == 0;
160   }
161   
162   /**
163    * Returns true if this list contains the specified element.
164    *
165    * @param o element whose presence in this List is to be tested.
166    */
167   public boolean contains(Object   elem) {
168     Object  [] elementData = array();
169     int len = elementData.length;
170     return indexOf(elem, elementData, len) >= 0;
171   }
172 
173   /**
174    * Searches for the first occurence of the given argument, testing 
175    * for equality using the <code>equals</code> method. 
176    *
177    * @param   elem   an object.
178    * @return  the index of the first occurrence of the argument in this
179    *          list; returns <code>-1</code> if the object is not found.
180    * @see     Object#equals(Object)
181    */
182   public int indexOf(Object   elem) {
183     Object  [] elementData = array();
184     int len = elementData.length;
185     return indexOf(elem, elementData, len);
186   }
187 
188 
189   /** 
190    * static version allows repeated call without needed
191    * to grab lock for array each time
192    **/
193 
194   protected static int indexOf(Object   elem, 
195                                Object  [] elementData,
196                                int len) {
197     if (elem == null) {
198       for (int i = 0; i < len; i++)
199         if (elementData[i]==null)
200           return i;
201     } else {
202       for (int i = 0; i < len; i++)
203         if (elem.equals(elementData[i]))
204           return i;
205     }
206     return -1;
207   }
208 
209   /**
210    * Searches for the first occurence of the given argument, beginning 
211    * the search at <code>index</code>, and testing for equality using 
212    * the <code>equals</code> method. 
213    *
214    * @param   elem    an object.
215    * @param   index   the index to start searching from.
216    * @return  the index of the first occurrence of the object argument in
217    *          this List at position <code>index</code> or later in the
218    *          List; returns <code>-1</code> if the object is not found.
219    * @see     Object#equals(Object)
220    */
221 
222   // needed in order to compile on 1.2b3
223   public int indexOf(Object   elem, int index) {
224     Object  [] elementData = array();
225     int elementCount = elementData.length;
226 
227     if (elem == null) {
228       for (int i = index ; i < elementCount ; i++)
229         if (elementData[i]==null)
230           return i;
231     } else {
232       for (int i = index ; i < elementCount ; i++)
233         if (elem.equals(elementData[i]))
234           return i;
235     }
236     return -1;
237   }
238 
239   /**
240    * Returns the index of the last occurrence of the specified object in
241    * this list.
242    *
243    * @param   elem   the desired component.
244    * @return  the index of the last occurrence of the specified object in
245    *          this list; returns -1 if the object is not found.
246    */
247   public int lastIndexOf(Object   elem) {
248     Object  [] elementData = array();
249     int len = elementData.length;
250     return lastIndexOf(elem, elementData, len);
251   }
252 
253   protected static int lastIndexOf(Object   elem, 
254                                    Object  [] elementData,
255                                    int len) {
256     if (elem == null) {
257       for (int i = len-1; i >= 0; i--)
258         if (elementData[i]==null)
259           return i;
260     } else {
261       for (int i = len-1; i >= 0; i--)
262         if (elem.equals(elementData[i]))
263           return i;
264     }
265     return -1;
266   }
267 
268   /**
269    * Searches backwards for the specified object, starting from the 
270    * specified index, and returns an index to it. 
271    *
272    * @param  elem    the desired component.
273    * @param  index   the index to start searching from.
274    * @return the index of the last occurrence of the specified object in this
275    *          List at position less than index in the List;
276    *          -1 if the object is not found.
277    */
278 
279   public int lastIndexOf(Object   elem, int index) {
280     // needed in order to compile on 1.2b3
281     Object  [] elementData = array();
282     if (elem == null) {
283       for (int i = index; i >= 0; i--)
284         if (elementData[i]==null)
285           return i;
286     } else {
287       for (int i = index; i >= 0; i--)
288         if (elem.equals(elementData[i]))
289           return i;
290     }
291     return -1;
292   }
293   
294   /**
295    * Returns a shallow copy of this list.  (The elements themselves
296    * are not copied.)
297    *
298    * @return  a clone of this list.
299    */
300   public Object   clone() {
301     try { 
302       Object  [] elementData = array();
303       CopyOnWriteArrayList v = (CopyOnWriteArrayList)super.clone();
304       v.array_ = new Object  [elementData.length];
305       System.arraycopy(elementData, 0, v.array_, 0, elementData.length);
306       return v;
307     } catch (CloneNotSupportedException   e) { 
308       // this shouldn't happen, since we are Cloneable
309       throw new InternalError  ();
310     }
311   }
312 
313   /**
314    * Returns an array containing all of the elements in this list
315    * in the correct order.
316    */
317   public Object  [] toArray() {
318     Object  [] elementData = array();
319     Object  [] result = new Object  [elementData.length];
320     System.arraycopy(elementData, 0, result, 0, elementData.length);
321     return result;
322   }
323 
324   /**
325    * Returns an array containing all of the elements in this list in the
326    * correct order.  The runtime type of the returned array is that of the
327    * specified array.  If the list fits in the specified array, it is
328    * returned therein.  Otherwise, a new array is allocated with the runtime
329    * type of the specified array and the size of this list.
330    * <p>
331    * If the list fits in the specified array with room to spare
332    * (i.e., the array has more elements than the list),
333    * the element in the array immediately following the end of the
334    * collection is set to null.  This is useful in determining the length
335    * of the list <em>only</em> if the caller knows that the list
336    * does not contain any null elements.
337    *
338    * @param a the array into which the elements of the list are to
339    *        be stored, if it is big enough; otherwise, a new array of the
340    *        same runtime type is allocated for this purpose.
341    * @return an array containing the elements of the list.
342    * @exception ArrayStoreException the runtime type of a is not a supertype
343    * of the runtime type of every element in this list.
344    */
345   public Object  [] toArray(Object   a[]) {
346     Object  [] elementData = array();
347     
348     if (a.length < elementData.length)
349       a = (Object  [])
350         java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), 
351                                             elementData.length);
352 
353     System.arraycopy(elementData, 0, a, 0, elementData.length);
354 
355     if (a.length > elementData.length)
356       a[elementData.length] = null;
357 
358     return a;
359   }
360 
361   // Positional Access Operations
362 
363   /**
364    * Returns the element at the specified position in this list.
365    *
366    * @param index index of element to return.
367    * @exception IndexOutOfBoundsException index is out of range (index
368    *          &lt; 0 || index &gt;= size()).
369    */
370   public Object   get(int index) {
371     Object  [] elementData = array();
372     rangeCheck(index, elementData.length);
373     return elementData[index];
374   }
375 
376   /**
377    * Replaces the element at the specified position in this list with
378    * the specified element.
379    *
380    * @param index index of element to replace.
381    * @param element element to be stored at the specified position.
382    * @return the element previously at the specified position.
383    * @exception IndexOutOfBoundsException index out of range
384    *          (index &lt; 0 || index &gt;= size()).
385    */
386   public synchronized Object   set(int index, Object   element) {
387     int len = array_.length;
388     rangeCheck(index, len);
389     Object   oldValue = array_[index];
390 
391     boolean same = (oldValue == element ||
392                     (element != null && element.equals(oldValue)));
393     if (!same) {
394       Object  [] newArray = new Object  [len];
395       System.arraycopy(array_, 0, newArray, 0, len);
396       newArray[index] = element;
397       array_ = newArray;
398     }
399     return oldValue;
400   }
401 
402   /**
403    * Appends the specified element to the end of this list.
404    *
405    * @param element element to be appended to this list.
406    * @return true (as per the general contract of Collection.add).
407    */
408   public synchronized boolean add(Object   element) {
409     int len = array_.length;
410     Object  [] newArray = new Object  [len+1];
411     System.arraycopy(array_, 0, newArray, 0, len);
412     newArray[len] = element;
413     array_ = newArray;
414     return true;
415   }
416 
417   /**
418    * Inserts the specified element at the specified position in this
419    * list. Shifts the element currently at that position (if any) and
420    * any subsequent elements to the right (adds one to their indices).
421    *
422    * @param index index at which the specified element is to be inserted.
423    * @param element element to be inserted.
424    * @exception IndexOutOfBoundsException index is out of range
425    *          (index &lt; 0 || index &gt; size()).
426    */
427   public synchronized void add(int index, Object   element) {
428     int len = array_.length;
429     if (index > len || index < 0)
430       throw new IndexOutOfBoundsException  ("Index: "+index+", Size: "+len);
431 
432     Object  [] newArray = new Object  [len+1];
433     System.arraycopy(array_, 0, newArray, 0, index);
434     newArray[index] = element;
435     System.arraycopy(array_, index, newArray, index+1, len - index);
436     array_ = newArray;
437   }
438 
439   /**
440    * Removes the element at the specified position in this list.
441    * Shifts any subsequent elements to the left (subtracts one from their
442    * indices).  Returns the element that was removed from the list.
443    *
444    * @exception IndexOutOfBoundsException index out of range (index
445    *          &lt; 0 || index &gt;= size()).
446    * @param index the index of the element to removed.
447    */
448   public synchronized Object   remove(int index) {
449     int len = array_.length;
450     rangeCheck(index, len);
451     Object   oldValue = array_[index];
452     Object  [] newArray = new Object  [len-1];
453     System.arraycopy(array_, 0, newArray, 0, index);
454     int numMoved = len - index - 1;
455     if (numMoved > 0)
456       System.arraycopy(array_, index+1, newArray, index, numMoved);
457     array_ = newArray;
458     return oldValue;
459   }
460 
461   /**
462    * Removes a single instance of the specified element from this Collection,
463    * if it is present (optional operation).  More formally, removes an
464    * element <code>e</code> such that <code>(o==null ? e==null :
465    * o.equals(e))</code>, if the Collection contains one or more such
466    * elements.  Returns true if the Collection contained the specified
467    * element (or equivalently, if the Collection changed as a result of the
468    * call).
469    *
470    * @param element element to be removed from this Collection, if present.
471    * @return true if the Collection changed as a result of the call.
472    */
473   public synchronized boolean remove(Object   element) {
474     int len = array_.length;
475     if (len == 0) return false;
476 
477     // Copy while searching for element to remove
478     // This wins in the normal case of element being present
479 
480     int newlen = len-1;
481     Object  [] newArray = new Object  [newlen];
482 
483     for (int i = 0; i < newlen; ++i) { 
484       if (element == array_[i] ||
485           (element != null && element.equals(array_[i]))) {
486         // found one;  copy remaining and exit
487         for (int k = i + 1; k < len; ++k) newArray[k-1] = array_[k];
488         array_ = newArray;
489         return true;
490       }
491       else
492         newArray[i] = array_[i];
493     }
494     // special handling for last cell
495 
496     if (element == array_[newlen] ||
497         (element != null && element.equals(array_[newlen]))) {
498       array_ = newArray;
499       return true;
500     }
501     else 
502       return false; // throw away copy
503 
504   }
505 
506 
507   /**
508    * Removes from this List all of the elements whose index is between
509    * fromIndex, inclusive and toIndex, exclusive.  Shifts any succeeding
510    * elements to the left (reduces their index).
511    * This call shortens the List by (toIndex - fromIndex) elements.  (If
512    * toIndex==fromIndex, this operation has no effect.)
513    *
514    * @param fromIndex index of first element to be removed.
515    * @param fromIndex index after last element to be removed.
516    * @exception IndexOutOfBoundsException fromIndex or toIndex out of
517    *          range (fromIndex &lt; 0 || fromIndex &gt;= size() || toIndex
518    *          &gt; size() || toIndex &lt; fromIndex).
519    */
520   public synchronized void removeRange(int fromIndex, int toIndex) {
521     int len = array_.length;
522 
523     if (fromIndex < 0 || fromIndex >= len ||
524         toIndex > len || toIndex < fromIndex)
525       throw new IndexOutOfBoundsException  ();
526     
527     int numMoved = len - toIndex;
528     int newlen = len - (toIndex-fromIndex);
529     Object  [] newArray = new Object  [newlen];
530     System.arraycopy(array_, 0, newArray, 0, fromIndex);
531     System.arraycopy(array_, toIndex, newArray, fromIndex, numMoved);
532     array_ = newArray;
533   }
534 
535 
536   /** 
537    * Append the element if not present.
538    * This operation can be used to obtain Set semantics
539    * for lists.
540    * @param element element to be added to this Collection, if absent.
541    * @return true if added
542    **/
543   public synchronized boolean addIfAbsent(Object   element) {
544     // Copy while checking if already present.
545     // This wins in the most common case where it is not present
546     int len = array_.length; 
547     Object  [] newArray = new Object  [len + 1];
548     for (int i = 0; i < len; ++i) {
549       if (element == array_[i] ||
550           (element != null && element.equals(array_[i]))) 
551     return false; // exit, throwing away copy
552       else
553         newArray[i] = array_[i];
554     }
555     newArray[len] = element;
556     array_ = newArray;
557     return true;
558   }
559 
560   /**
561    * Returns true if this Collection contains all of the elements in the
562    * specified Collection.
563    * <p>
564    * This implementation iterates over the specified Collection, checking
565    * each element returned by the Iterator in turn to see if it's
566    * contained in this Collection.  If all elements are so contained
567    * true is returned, otherwise false.
568    *
569    */
570   public boolean containsAll(Collection c) {
571     Object  [] elementData = array();
572     int len = elementData.length;
573     Iterator e = c.iterator();
574     while (e.hasNext())
575       if(indexOf(e.next(), elementData, len) < 0)
576         return false;
577     
578     return true;
579   }
580 
581 
582   /**
583    * Removes from this Collection all of its elements that are contained in
584    * the specified Collection. This is a particularly expensive operation
585    * in this class because of the need for an internal temporary array.
586    * <p>
587    *
588    * @return true if this Collection changed as a result of the call.
589    */
590   public synchronized boolean removeAll(Collection c) {
591     Object  [] elementData = array_;
592     int len = elementData.length;
593     if (len == 0) return false;
594 
595     // temp array holds those elements we know we want to keep
596     Object  [] temp = new Object  [len];
597     int newlen = 0;
598     for (int i = 0; i < len; ++i) {
599       Object   element = elementData[i];
600       if (!c.contains(element)) {
601         temp[newlen++] = element;
602       }
603     }
604 
605     if (newlen == len) return false;
606 
607     //  copy temp as new array
608     Object  [] newArray = new Object  [newlen];
609     System.arraycopy(temp, 0, newArray, 0, newlen);
610     array_ = newArray;
611     return true;
612   }
613 
614   /**
615    * Retains only the elements in this Collection that are contained in the
616    * specified Collection (optional operation).  In other words, removes from
617    * this Collection all of its elements that are not contained in the
618    * specified Collection. 
619    * @return true if this Collection changed as a result of the call.
620    */
621   public synchronized boolean retainAll(Collection c) {
622     Object  [] elementData = array_;
623     int len = elementData.length;
624     if (len == 0) return false;
625 
626     Object  [] temp = new Object  [len];
627     int newlen = 0;
628     for (int i = 0; i < len; ++i) {
629       Object   element = elementData[i];
630       if (c.contains(element)) {
631         temp[newlen++] = element;
632       }
633     }
634 
635     if (newlen == len) return false;
636 
637     Object  [] newArray = new Object  [newlen];
638     System.arraycopy(temp, 0, newArray, 0, newlen);
639     array_ = newArray;
640     return true;
641   }
642 
643   /**
644    * Appends all of the elements in the specified Collection that
645    * are not already contained in this list, to the end of
646    * this list, in the order that they are returned by the
647    * specified Collection's Iterator. 
648    *
649    * @param c elements to be added into this list.
650    * @return the number of elements added
651    */
652 
653   public synchronized int addAllAbsent(Collection c) {
654     int numNew = c.size();
655     if (numNew == 0) return 0;
656 
657     Object  [] elementData = array_;
658     int len = elementData.length;
659 
660     Object  [] temp = new Object  [numNew];
661     int added = 0;
662     Iterator e = c.iterator();
663     while (e.hasNext()) {
664       Object   element = e.next();
665       if (indexOf(element, elementData, len) < 0) {
666         if (indexOf(element, temp, added) < 0) {
667           temp[added++] = element;
668         }
669       }
670     }
671 
672     if (added == 0) return 0;
673 
674     Object  [] newArray = new Object  [len+added];
675     System.arraycopy(elementData, 0, newArray, 0, len);
676     System.arraycopy(temp, 0, newArray, len, added);
677     array_ = newArray;
678     return added;
679   }
680 
681   /**
682    * Removes all of the elements from this list. 
683    *
684    */
685   public synchronized void clear() {
686     array_ = new Object  [0];
687   }
688 
689   /**
690    * Appends all of the elements in the specified Collection to the end of
691    * this list, in the order that they are returned by the
692    * specified Collection's Iterator. 
693    *
694    * @param c elements to be inserted into this list.
695    */
696   public synchronized boolean addAll(Collection c) {
697     int numNew = c.size();
698     if (numNew == 0) return false;
699 
700     int len = array_.length;
701     Object  [] newArray = new Object  [len+numNew];
702     System.arraycopy(array_, 0, newArray, 0, len);
703     Iterator e = c.iterator();
704     for (int i=0; i<numNew; i++)
705       newArray[len++] = e.next();
706     array_ = newArray;
707 
708     return true;
709   }
710 
711   /**
712    * Inserts all of the elements in the specified Collection into this
713    * list, starting at the specified position.  Shifts the element
714    * currently at that position (if any) and any subsequent elements to
715    * the right (increases their indices).  The new elements will appear
716    * in the list in the order that they are returned by the
717    * specified Collection's iterator.
718    *
719    * @param index index at which to insert first element
720    *            from the specified collection.
721    * @param c elements to be inserted into this list.
722    * @exception IndexOutOfBoundsException index out of range (index
723    *          &lt; 0 || index &gt; size()).
724    */
725   public synchronized boolean addAll(int index, Collection c) {
726     int len = array_.length;
727     if (index > len || index < 0)
728       throw new IndexOutOfBoundsException  ("Index: "+index+", Size: "+len);
729 
730     int numNew = c.size();
731     if (numNew == 0) return false;
732 
733     Object  [] newArray = new Object  [len+numNew];
734     System.arraycopy(array_, 0, newArray, 0, len);
735     int numMoved = len - index;
736     if (numMoved > 0)
737       System.arraycopy(array_, index, newArray, index + numNew, numMoved);
738     Iterator e = c.iterator();
739     for (int i=0; i<numNew; i++)
740       newArray[index++] = e.next();
741     array_ = newArray;
742 
743     return true;
744   }
745 
746   /**
747    * Check if the given index is in range.  If not, throw an appropriate
748    * runtime exception.
749    */
750   protected void rangeCheck(int index, int length) {
751     if (index >= length || index < 0)
752       throw new IndexOutOfBoundsException  ("Index: "+index+", Size: "+ length);
753   }
754   /**
755    * Save the state of the list to a stream (i.e., serialize it).
756    *
757    * @serialData The length of the array backing the list is emitted
758    *           (int), followed by all of its elements (each an Object)
759    *           in the proper order.
760    */
761   private void writeObject(java.io.ObjectOutputStream   s)
762     throws java.io.IOException  {
763     // Write out element count, and any hidden stuff
764     s.defaultWriteObject();
765 
766     Object  [] elementData = array();
767         // Write out array length
768     s.writeInt(elementData.length);
769 
770     // Write out all elements in the proper order.
771     for (int i=0; i<elementData.length; i++)
772       s.writeObject(elementData[i]);
773   }
774 
775   /**
776    * Reconstitute the list from a stream (i.e., deserialize it).
777    */
778   private synchronized void readObject(java.io.ObjectInputStream   s)
779     throws java.io.IOException  , ClassNotFoundException   {
780     // Read in size, and any hidden stuff
781     s.defaultReadObject();
782 
783         // Read in array length and allocate array
784     int arrayLength = s.readInt();
785     Object  [] elementData = new Object  [arrayLength];
786 
787     // Read in all elements in the proper order.
788     for (int i=0; i<elementData.length; i++)
789       elementData[i] = s.readObject();
790     array_ = elementData;
791   }
792 
793   /**
794    * Returns a string representation of this Collection, containing
795    * the String representation of each element.
796    */
797   public String   toString() {
798     StringBuffer   buf = new StringBuffer  ();
799     Iterator e = iterator();
800     buf.append("[");
801     int maxIndex = size() - 1;
802     for (int i = 0; i <= maxIndex; i++) {
803       buf.append(String.valueOf(e.next()));
804       if (i < maxIndex)
805         buf.append(", ");
806     }
807     buf.append("]");
808     return buf.toString();
809   }
810 
811 
812   /**
813    * Compares the specified Object with this List for equality.  Returns true
814    * if and only if the specified Object is also a List, both Lists have the
815    * same size, and all corresponding pairs of elements in the two Lists are
816    * <em>equal</em>.  (Two elements <code>e1</code> and <code>e2</code> are
817    * <em>equal</em> if <code>(e1==null ? e2==null : e1.equals(e2))</code>.)
818    * In other words, two Lists are defined to be equal if they contain the
819    * same elements in the same order.
820    * <p>
821    * This implementation first checks if the specified object is this
822    * List. If so, it returns true; if not, it checks if the specified
823    * object is a List. If not, it returns false; if so, it iterates over
824    * both lists, comparing corresponding pairs of elements.  If any
825    * comparison returns false, this method returns false.  If either
826    * Iterator runs out of elements before before the other it returns false
827    * (as the Lists are of unequal length); otherwise it returns true when
828    * the iterations complete.
829    *
830    * @param o the Object to be compared for equality with this List.
831    * @return true if the specified Object is equal to this List.
832    */
833   public boolean equals(Object   o) {
834     if (o == this)
835       return true;
836     if (!(o instanceof List))
837       return false;
838     
839     List l2 = (List)(o);
840     if (size() != l2.size()) 
841       return false;
842 
843     ListIterator e1 = listIterator();
844     ListIterator e2 = l2.listIterator();
845     while(e1.hasNext()) {
846       Object   o1 = e1.next();
847       Object   o2 = e2.next();
848       if (!(o1==null ? o2==null : o1.equals(o2)))
849         return false;
850     }
851     return true;
852   }
853   
854   /**
855    * Returns the hash code value for this List.
856    * <p>
857    * This implementation uses exactly the code that is used to define
858    * the List hash function in the documentation for List.hashCode.
859    */
860   public int hashCode() {
861     int hashCode = 1;
862     Iterator i = iterator();
863     while (i.hasNext()) {
864       Object   obj = i.next();
865       hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
866     }
867     return hashCode;
868   }
869   
870   /**
871    * Returns an Iterator over the elements contained in this collection.
872    * The iterator provides a snapshot of the state of the list
873    * when the iterator was constructed. No synchronization is
874    * needed while traversing the iterator. The iterator does
875    * <em>NOT</em> support the <code>remove</code> method.
876    */
877   public Iterator iterator() {
878     return new COWIterator(array(), 0);
879   }
880 
881   /**
882    * Returns an Iterator of the elements in this List (in proper sequence).
883    * The iterator provides a snapshot of the state of the list
884    * when the iterator was constructed. No synchronization is
885    * needed while traversing the iterator. The iterator does
886    * <em>NOT</em> support the <code>remove</code>, <code>set</code>,
887    * or <code>add</code> methods.
888    *
889    */
890 
891   public ListIterator listIterator() {
892     return new COWIterator(array(), 0);
893   }
894 
895   /**
896    * Returns a ListIterator of the elements in this List (in proper
897    * sequence), starting at the specified position in the List.  The
898    * specified index indicates the first element that would be returned by
899    * an initial call to nextElement.  An initial call to previousElement
900    * would return the element with the specified index minus one.
901    * The ListIterator returned by this implementation will throw
902    * an UnsupportedOperationException in its remove, set and
903    * add methods.
904    *
905    * @param index index of first element to be returned from the
906    *            ListIterator (by a call to getNext).
907    * @exception IndexOutOfBoundsException index is out of range
908    *          (index &lt; 0 || index &gt; size()).
909    */
910   public ListIterator listIterator(final int index) {
911     Object  [] elementData = array();
912     int len = elementData.length;
913     if (index<0 || index>len)
914       throw new IndexOutOfBoundsException  ("Index: "+index);
915     
916     return new COWIterator(array(), index);
917   }
918 
919   protected static class COWIterator implements ListIterator {
920 
921     /** Snapshot of the array **/
922     protected final Object  [] array;
923 
924     /**
925      * Index of element to be returned by subsequent call to next.
926      */
927     protected int cursor;
928 
929     protected COWIterator(Object  [] elementArray, int initialCursor) { 
930       array = elementArray; 
931       cursor = initialCursor;
932     }
933 
934     public boolean hasNext() {
935       return cursor < array.length;
936     }
937 
938     public boolean hasPrevious() {
939       return cursor > 0;
940     }
941 
942     public Object   next() {
943       try {
944         return array[cursor++];
945       }
946       catch (IndexOutOfBoundsException   ex) {
947         throw new NoSuchElementException();
948       }
949     }
950 
951     public Object   previous() {
952       try {
953         return array[--cursor];
954       } catch(IndexOutOfBoundsException   e) {
955         throw new NoSuchElementException();
956       }
957     }
958 
959     public int nextIndex() {
960       return cursor;
961     }
962 
963     public int previousIndex() {
964       return cursor-1;
965     }
966 
967     /**
968      * Not supported. Always throws UnsupportedOperationException.
969      * @exception UnsupportedOperationException remove is not supported
970      *