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         }
925 
926         public int previousIndex() {
927             return cursor-1;
928         }
929 
930         /**
931          * Not supported. Always throws UnsupportedOperationException.
932          * @throws UnsupportedOperationException remove is not supported
933          *            by this Iterator.
934          */
935 
936         public void remove() {
937             throw new UnsupportedOperationException  ();
938         }
939 
940         /**
941          * Not supported. Always throws UnsupportedOperationException.
942          * @throws UnsupportedOperationException set is not supported
943          *            by this Iterator.
944          */
945         public void set(E o) {
946             throw new UnsupportedOperationException  ();
947         }
948 
949         /**
950          * Not supported. Always throws UnsupportedOperationException.
951          * @throws UnsupportedOperationException add is not supported
952          *            by this Iterator.
953          */
954         public void add(E o) {
955             throw new UnsupportedOperationException  ();
956         }
957     }
958 
959 
960     /**
961      * Returns a view of the portion of this List between fromIndex,
962      * inclusive, and toIndex, exclusive.  The returned List is backed by this
963      * List, so changes in the returned List are reflected in this List, and
964      * vice-versa.  While mutative operations are supported, they are
965      * probably not very useful for CopyOnWriteArrayLists.
966      * <p>
967      * The semantics of the List returned by this method become undefined if
968      * the backing list (i.e., this List) is <i>structurally modified</i> in
969      * any way other than via the returned List.  (Structural modifications are
970      * those that change the size of the List, or otherwise perturb it in such
971      * a fashion that iterations in progress may yield incorrect results.)
972      *
973      * @param fromIndex low endpoint (inclusive) of the subList.
974      * @param toIndex high endpoint (exclusive) of the subList.
975      * @return a view of the specified range within this List.
976      * @throws IndexOutOfBoundsException Illegal endpoint index value
977      *     (fromIndex &lt; 0 || toIndex &gt; size || fromIndex &gt; toIndex).
978      */
979     public synchronized List<E> subList(int fromIndex, int toIndex) {
980         // synchronized since sublist constructor depends on it.
981         int len = array.length;
982         if (fromIndex<0 || toIndex>len  || fromIndex>toIndex)
983             throw new IndexOutOfBoundsException  ();
984         return new COWSubList<E>(this, fromIndex, toIndex);
985     }
986 
987     private static class COWSubList<E> extends AbstractList<E> {
988 
989         /*
990           This class extends AbstractList merely for convenience, to
991           avoid having to define addAll, etc. This doesn't hurt, but
992           is wasteful.  This class does not need or use modCount
993           mechanics in AbstractList, but does need to check for
994           concurrent modification using similar mechanics.  On each
995           operation, the array that we expect the backing list to use
996           is checked and updated.  Since we do this for all of the
997           base operations invoked by those defined in AbstractList,
998           all is well.  While inefficient, this is not worth
999           improving.  The kinds of list operations inherited from
1000          AbstractList are already so slow on COW sublists that
1001          adding a bit more space/time doesn't seem even noticeable.
1002         */
1003
1004        private final CopyOnWriteArrayList  <E> l;
1005        private final int offset;
1006        private int size;
1007        private E[] expectedArray;
1008
1009        private COWSubList(CopyOnWriteArrayList  <E> list,
1010        int fromIndex, int toIndex) {
1011            l = list;
1012            expectedArray = l.array();
1013            offset = fromIndex;
1014            size = toIndex - fromIndex;
1015        }
1016
1017        // only call this holding l's lock
1018        private void checkForComodification() {
1019            if (l.array != expectedArray)
1020                throw new ConcurrentModificationException();
1021        }
1022
1023        // only call this holding l's lock
1024        private void rangeCheck(int index) {
1025            if (index<0 || index>=size)
1026                throw new IndexOutOfBoundsException  ("Index: "+index+ ",Size: "+size);
1027        }
1028
1029
1030        public E set(int index, E element) {
1031            synchronized(l) {
1032                rangeCheck(index);
1033                checkForComodification();
1034                E x = l.set(index+offset, element);
1035                expectedArray = l.array;
1036                return x;
1037            }
1038        }
1039
1040        public E get(int index) {
1041            synchronized(l) {
1042                rangeCheck(index);
1043                checkForComodification();
1044                return l.get(index+offset);
1045            }
1046        }
1047
1048        public int size() {
1049            synchronized(l) {
1050                checkForComodification();
1051                return size;
1052            }
1053        }
1054
1055        public void add(int index, E element) {
1056            synchronized(l) {
1057                checkForComodification();
1058                if (index<0 || index>size)
1059                    throw new IndexOutOfBoundsException  ();
1060                l.add(index+offset, element);
1061                expectedArray = l.array;
1062                size++;
1063            }
1064        }
1065
1066        public void clear() {
1067            synchronized(l) {
1068                checkForComodification();
1069                l.removeRange(offset, offset+size);
1070                expectedArray = l.array;
1071                size = 0;
1072            }
1073        }
1074
1075        public E remove(int index) {
1076            synchronized(l) {
1077                rangeCheck(index);
1078                checkForComodification();
1079                E result = l.remove(index+offset);
1080                expectedArray = l.array;
1081                size--;
1082                return result;
1083            }
1084        }
1085
1086        public Iterator<E> iterator() {
1087            synchronized(l) {
1088                checkForComodification();
1089                return new COWSubListIterator<E>(l, 0, offset, size);
1090            }
1091        }
1092
1093        public ListIterator<E> listIterator(final int index) {
1094            synchronized(l) {
1095                checkForComodification();
1096                if (index<0 || index>size)
1097                    throw new IndexOutOfBoundsException  ("Index: "+index+", Size: "+size);
1098                return new COWSubListIterator<E>(l, index, offset, size);
1099            }
1100        }
1101
1102        public List<E> subList(int fromIndex, int toIndex) {
1103            synchronized(l) {
1104                checkForComodification();
1105                if (fromIndex<0 || toIndex>size)
1106                    throw new IndexOutOfBoundsException  ();
1107                return new COWSubList<E>(l, fromIndex+offset, toIndex+offset);
1108            }
1109        }
1110
1111    }
1112
1113
1114    private static class COWSubListIterator<E> implements ListIterator<E> {
1115        private final ListIterator<E> i;
1116        private final int index;
1117        private final int offset;
1118        private final int size;
1119        private COWSubListIterator(List<E> l, int index, int offset, int size) {
1120            this.index = index;
1121            this.offset = offset;
1122            this.size = size;
1123            i = l.listIterator(index+offset);
1124        }
1125
1126        public boolean hasNext() {
1127            return nextIndex() < size;
1128        }
1129
1130        public E next() {
1131            if (hasNext())
1132                return i.next();
1133            else
1134                throw new NoSuchElementException();
1135        }
1136
1137        public boolean hasPrevious() {
1138            return previousIndex() >= 0;
1139        }
1140
1141        public E previous() {
1142            if (hasPrevious())
1143                return i.previous();
1144            else
1145                throw new NoSuchElementException();
1146        }
1147
1148        public int nextIndex() {
1149            return i.nextIndex() - offset;
1150        }
1151
1152        public int previousIndex() {
1153            return i.previousIndex() - offset;
1154        }
1155
1156        public void remove() {
1157            throw new UnsupportedOperationException  ();
1158        }
1159
1160        public void set(E o) {
1161            throw new UnsupportedOperationException  ();
1162        }
1163
1164        public void add(E o) {
1165            throw new UnsupportedOperationException  ();
1166        }
1167    }
1168
1169}
1170
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags