Java > Open Source Codes > java > util > concurrent > CopyOnWriteArrayList


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