Code - Class EDU.oswego.cs.dl.util.concurrent.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      * by this Iterator.
971      */
972
973     public void remove() {
974       throw new UnsupportedOperationException();
975     }
976
977     /**
978      * Not supported. Always throws UnsupportedOperationException.
979      * @exception UnsupportedOperationException set is not supported
980      * by this Iterator.
981      */
982     public void set(Object o) {
983       throw new UnsupportedOperationException();
984     }
985
986     /**
987      * Not supported. Always throws UnsupportedOperationException.
988      * @exception UnsupportedOperationException add is not supported
989      * by this Iterator.
990      */
991     public void add(Object o) {
992       throw new UnsupportedOperationException();
993     }
994   }
995
996
997   /**
998    * Returns a view of the portion of this List between fromIndex,
999    * inclusive, and toIndex, exclusive. The returned List is backed by this
1000   * List, so changes in the returned List are reflected in this List, and
1001   * vice-versa. While mutative operations are supported, they are
1002   * probably not very useful for CopyOnWriteArrays.
1003   * </p>
1004   * The semantics of the List returned by this method become undefined if
1005   * the backing list (i.e., this List) is <i>structurally modified</i> in
1006   * any way other than via the returned List. (Structural modifications are
1007   * those that change the size of the List, or otherwise perturb it in such
1008   * a fashion that iterations in progress may yield incorrect results.)
1009   *
1010   * @param fromIndex low endpoint (inclusive) of the subList.
1011   * @param toKey high endpoint (exclusive) of the subList.
1012   * @return a view of the specified range within this List.
1013   * @exception IndexOutOfBoundsException Illegal endpoint index value
1014   * (fromIndex &lt; 0 || toIndex &gt; size || fromIndex &gt; toIndex).
1015   */
1016  public synchronized List subList(int fromIndex, int toIndex) {
1017    // synchronized since sublist ctor depends on it.
1018 int len = array_.length;
1019    if (fromIndex<0 || toIndex>len || fromIndex>toIndex)
1020      throw new IndexOutOfBoundsException();
1021    return new COWSubList(this, fromIndex, toIndex);
1022  }
1023  
1024  protected static class COWSubList extends AbstractList {
1025
1026    /*
1027      This is currently a bit sleazy. The class
1028      extends AbstractList merely for convenience,
1029      to avoid having to define addAll, etc. This
1030      doesn't hurt, but is stupid and wasteful.
1031      This class does not need or use modCount mechanics
1032      in AbstractList, but does need to check for
1033      concurrent modification using similar mechanics.
1034      On each operation, the array that we expect
1035      the backing list to use is checked and updated.
1036      Since we do this for all of the base operations
1037      invoked by those defined in AbstractList, all is well.
1038
1039      It's not clear whether this is worth cleaning up.
1040      The kinds of list operations inherited from
1041      AbstractList are are already so slow on COW sublists
1042      that adding a bit more space/time doesn't seem
1043      even noticeable.
1044    */
1045
1046    protected final CopyOnWriteArrayList l;
1047    protected final int offset;
1048    protected int size;
1049    protected Object[] expectedArray;
1050
1051    protected COWSubList(CopyOnWriteArrayList list,
1052                         int fromIndex, int toIndex) {
1053      l = list;
1054      expectedArray = l.array();
1055      offset = fromIndex;
1056      size = toIndex - fromIndex;
1057    }
1058
1059    // only call this holding l's lock
1060 protected void checkForComodification() {
1061      if (l.array_ != expectedArray)
1062        throw new ConcurrentModificationException();
1063    }
1064
1065    // only call this holding l's lock
1066 protected void rangeCheck(int index) {
1067      if (index<0 || index>=size)
1068        throw new IndexOutOfBoundsException("Index: "+index+
1069                                            ",Size: "+size);
1070    }
1071
1072
1073    public Object set(int index, Object element) {
1074      synchronized(l) {
1075        rangeCheck(index);
1076        checkForComodification();
1077        Object x = l.set(index+offset, element);
1078        expectedArray = l.array_;
1079        return x;
1080      }
1081    }
1082
1083    public Object get(int index) {
1084      synchronized(l) {
1085        rangeCheck(index);
1086        checkForComodification();
1087        return l.get(index+offset);
1088      }
1089    }
1090
1091    public int size() {
1092      synchronized(l) {
1093        checkForComodification();
1094        return size;
1095      }
1096    }
1097
1098    public void add(int index, Object element) {
1099      synchronized(l) {
1100        checkForComodification();
1101        if (index<0 || index>size)
1102          throw new IndexOutOfBoundsException();
1103        l.add(index+offset, element);
1104        expectedArray = l.array_;
1105        size++;
1106      }
1107    }
1108
1109    public Object remove(int index) {
1110      synchronized(l) {
1111        rangeCheck(index);
1112        checkForComodification();
1113        Object result = l.remove(index+offset);
1114        expectedArray = l.array_;
1115        size--;
1116        return result;
1117      }
1118    }
1119
1120    public Iterator iterator() {
1121      synchronized(l) {
1122        checkForComodification();
1123        return new COWSubListIterator(0);
1124      }
1125    }
1126
1127    public ListIterator listIterator(final int index) {
1128      synchronized(l) {
1129        checkForComodification();
1130        if (index<0 || index>size)
1131          throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
1132        return new COWSubListIterator(index);
1133      }
1134    }
1135
1136    protected class COWSubListIterator implements ListIterator {
1137      protected final ListIterator i;
1138      protected final int index;
1139      protected COWSubListIterator(int index) {
1140        this.index = index;
1141        i = l.listIterator(index+offset);
1142      }
1143
1144      public boolean hasNext() {
1145        return nextIndex() < size;
1146      }
1147      
1148      public Object next() {
1149        if (hasNext())
1150          return i.next();
1151        else
1152          throw new NoSuchElementException();
1153      }
1154      
1155      public boolean hasPrevious() {
1156        return previousIndex() >= 0;
1157      }
1158      
1159      public Object previous() {
1160        if (hasPrevious())
1161          return i.previous();
1162        else
1163          throw new NoSuchElementException();
1164      }
1165      
1166      public int nextIndex() {
1167        return i.nextIndex() - offset;
1168      }
1169      
1170      public int previousIndex() {
1171        return i.previousIndex() - offset;
1172      }
1173
1174      public void remove() {
1175        throw new UnsupportedOperationException();
1176      }
1177
1178      public void set(Object o) {
1179        throw new UnsupportedOperationException();
1180      }
1181      
1182      public void add(Object o) {
1183        throw new UnsupportedOperationException();
1184      }
1185    }
1186
1187
1188    public List subList(int fromIndex, int toIndex) {
1189      synchronized(l) {
1190        checkForComodification();
1191        if (fromIndex<0 || toIndex>size)
1192          throw new IndexOutOfBoundsException();
1193        return new COWSubList(l, fromIndex+offset, toIndex+offset);
1194      }
1195    }
1196
1197    
1198  }
1199
1200}
1201
Java API By Example, From Geeks To Geeks. | Conditions of Use | About Us © 2002 - 2005, KickJava.com, or its affiliates