Java > Open Source Codes > prefuse > util > collections > CopyOnWriteArrayList


1 package prefuse.util.collections;
2 /*
3  * Written by Doug Lea with assistance from members of JCP JSR-166
4  * Expert Group. Adapted and released, under explicit permission,
5  * from JDK ArrayList.java which carries the following copyright:
6  *
7  * Copyright 1997 by Sun Microsystems, Inc.,
8  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
9  * All rights reserved.
10  *
11  * This software is the confidential and proprietary information
12  * of Sun Microsystems, Inc. ("Confidential Information"). You
13  * shall not disclose such Confidential Information and shall use
14  * it only in accordance with the terms of the license agreement
15  * you entered into with Sun.
16  */
17
18 import java.util.AbstractList ;
19 import java.util.Collection ;
20 import java.util.ConcurrentModificationException ;
21 import java.util.Iterator ;
22 import java.util.List ;
23 import java.util.ListIterator ;
24 import java.util.NoSuchElementException ;
25 import java.util.RandomAccess ;
26
27
28 /**
29  * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
30  * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
31  * making a fresh copy of the underlying array.
32  *
33  * <p> This is ordinarily too costly, but may be <em>more</em> efficient
34  * than alternatives when traversal operations vastly outnumber
35  * mutations, and is useful when you cannot or don't want to
36  * synchronize traversals, yet need to preclude interference among
37  * concurrent threads. The "snapshot" style iterator method uses a
38  * reference to the state of the array at the point that the iterator
39  * was created. This array never changes during the lifetime of the
40  * iterator, so interference is impossible and the iterator is
41  * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
42  * The iterator will not reflect additions, removals, or changes to
43  * the list since the iterator was created. Element-changing
44  * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and
45  * <tt>add</tt>) are not supported. These methods throw
46  * <tt>UnsupportedOperationException</tt>.
47  *
48  * <p>All elements are permitted, including <tt>null</tt>.
49  *
50  * <p>This class is a member of the
51  * <a HREF="{@docRoot}/../guide/collections/index.html">
52  * Java Collections Framework</a>.
53  *
54  * @since 1.5
55  * @author Doug Lea
56  */
57 public class CopyOnWriteArrayList
58     implements List , RandomAccess , Cloneable , java.io.Serializable {
59     private static final long serialVersionUID = 8673264195747942595L;
60
61     /** The array, accessed only via getArray/setArray. */
62     private volatile transient Object [] array;
63
64     /**
65      * This has been made public to support more efficient iteration.
66      * <strong>DO NOT MODIFY this array upon getting it</strong>.
67      * Otherwise you risk wreaking havoc on your list. In fact, if you are
68      * not the author of this comment, you probably shouldn't use it at all.
69      * @return this lists internal array
70      */
71     public Object [] getArray() { return array; }
72     
73     void setArray(Object [] a) { array = a; }
74
75     /**
76      * Creates an empty list.
77      */
78     public CopyOnWriteArrayList() {
79         setArray(new Object [0]);
80     }
81
82     /**
83      * Creates a list containing the elements of the specified
84      * collection, in the order they are returned by the collection's
85      * iterator.
86      *
87      * @param c the collection of initially held elements
88      * @throws NullPointerException if the specified collection is null
89      */
90     public CopyOnWriteArrayList(Collection c) {
91         Object [] elements = new Object [c.size()];
92         int size = 0;
93         for (Iterator itr = c.iterator(); itr.hasNext(); ) {
94             Object e = itr.next();
95             elements[size++] = e;
96         }
97         setArray(elements);
98     }
99
100     /**
101      * Creates a list holding a copy of the given array.
102      *
103      * @param toCopyIn the array (a copy of this array is used as the
104      * internal array)
105      * @throws NullPointerException if the specified array is null
106      */
107     public CopyOnWriteArrayList(Object [] toCopyIn) {
108         copyIn(toCopyIn, 0, toCopyIn.length);
109     }
110
111     /**
112      * Replaces the held array with a copy of the <tt>n</tt> elements
113      * of the provided array, starting at position <tt>first</tt>. To
114      * copy an entire array, call with arguments (array, 0,
115      * array.length).
116      * @param toCopyIn the array. A copy of the indicated elements of
117      * this array is used as the internal array.
118      * @param first The index of first position of the array to
119      * start copying from.
120      * @param n the number of elements to copy. This will be the new size of
121      * the list.
122      */
123     private void copyIn(Object [] toCopyIn, int first, int n) {
124         int limit = first + n;
125         if (limit > toCopyIn.length)
126             throw new IndexOutOfBoundsException ();
127         Object [] newElements = copyOfRange(toCopyIn, first, limit,
128                                           Object [].class);
129         synchronized (this) { setArray(newElements); }
130     }
131
132     /**
133      * Returns the number of elements in this list.
134      *
135      * @return the number of elements in this list
136      */
137     public int size() {
138         return getArray().length;
139     }
140
141     /**
142      * Returns <tt>true</tt> if this list contains no elements.
143      *
144      * @return <tt>true</tt> if this list contains no elements
145      */
146     public boolean isEmpty() {
147         return size() == 0;
148     }
149
150     /**
151      * Test for equality, coping with nulls.
152      */
153     private static boolean eq(Object o1, Object o2) {
154         return (o1 == null ? o2 == null : o1.equals(o2));
155     }
156
157     /**
158      * static version of indexOf, to allow repeated calls without
159      * needing to re-acquire array each time.
160      * @param o element to search for
161      * @param elements the array
162      * @param index first index to search
163      * @param fence one past last index to search
164      * @return index of element, or -1 if absent
165      */
166     private static int indexOf(Object o, Object [] elements,
167                                int index, int fence) {
168         if (o == null) {
169             for (int i = index; i < fence; i++)
170                 if (elements[i] == null)
171                     return i;
172         } else {
173             for (int i = index; i < fence; i++)
174                 if (o.equals(elements[i]))
175                     return i;
176         }
177         return -1;
178     }
179
180     /**
181      * static version of lastIndexOf.
182      * @param o element to search for
183      * @param elements the array
184      * @param index first index to search
185      * @return index of element, or -1 if absent
186      */
187     private static int lastIndexOf(Object o, Object [] elements, int index) {
188         if (o == null) {
189             for (int i = index; i >= 0; i--)
190                 if (elements[i] == null)
191                     return i;
192         } else {
193             for (int i = index; i >= 0; i--)
194                 if (o.equals(elements[i]))
195                     return i;
196         }
197         return -1;
198     }
199
200     /**
201      * Returns <tt>true</tt> if this list contains the specified element.
202      * More formally, returns <tt>true</tt> if and only if this list contains
203      * at least one element <tt>e</tt> such that
204      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
205      *
206      * @param o element whose presence in this list is to be tested
207      * @return <tt>true</tt> if this list contains the specified element
208      */
209     public boolean contains(Object o) {
210         Object [] elements = getArray();
211         return indexOf(o, elements, 0, elements.length) >= 0;
212     }
213
214     /**
215      * {@inheritDoc}
216      */
217     public int indexOf(Object o) {
218         Object [] elements = getArray();
219         return indexOf(o, elements, 0, elements.length);
220     }
221
222
223     /**
224      * Returns the index of the first occurrence of the specified element in
225      * this list, searching forwards from <tt>index</tt>, or returns -1 if
226      * the element is not found.
227      * More formally, returns the lowest index <tt>i</tt> such that
228      * <tt>(i&nbsp;&gt;=&nbsp;index&nbsp;&amp;&amp;&nbsp;(e==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;e.equals(get(i))))</tt>,
229      * or -1 if there is no such index.
230      *
231      * @param e element to search for
232      * @param index index to start searching from
233      * @return the index of the first occurrence of the element in
234      * this list at position <tt>index</tt> or later in the list;
235      * <tt>-1</tt> if the element is not found.
236      * @throws IndexOutOfBoundsException if the specified index is negative
237      */
238     public int indexOf(Object e, int index) {
239         Object [] elements = getArray();
240         return indexOf(e, elements, index, elements.length);
241     }
242
243     /**
244      * {@inheritDoc}
245      */
246     public int lastIndexOf(Object o) {
247         Object [] elements = getArray();
248         return lastIndexOf(o, elements, elements.length - 1);
249     }
250
251     /**
252      * Returns the index of the last occurrence of the specified element in
253      * this list, searching backwards from <tt>index</tt>, or returns -1 if
254      * the element is not found.
255      * More formally, returns the highest index <tt>i</tt> such that
256      * <tt>(i&nbsp;&lt;=&nbsp;index&nbsp;&amp;&amp;&nbsp;(e==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;e.equals(get(i))))</tt>,
257      * or -1 if there is no such index.
258      *
259      * @param e element to search for
260      * @param index index to start searching backwards from
261      * @return the index of the last occurrence of the element at position
262      * less than or equal to <tt>index</tt> in this list;
263      * -1 if the element is not found.
264      * @throws IndexOutOfBoundsException if the specified index is greater
265      * than or equal to the current size of this list
266      */
267     public int lastIndexOf(Object e, int index) {
268         Object [] elements = getArray();
269         return lastIndexOf(e, elements, index);
270     }
271
272     /**
273      * Returns a shallow copy of this list. (The elements themselves
274      * are not copied.)
275      *
276      * @return a clone of this list
277      */
278     public Object clone() {
279         try {
280             return super.clone();
281         } catch (CloneNotSupportedException e) {
282             // this shouldn't happen, since we are Cloneable
283 throw new InternalError ();
284         }
285     }
286
287     /**
288      * Returns an array containing all of the elements in this list
289      * in proper sequence (from first to last element).
290      *
291      * <p>The returned array will be "safe" in that no references to it are
292      * maintained by this list. (In other words, this method must allocate
293      * a new array). The caller is thus free to modify the returned array.
294      *
295      * <p>This method acts as bridge between array-based and collection-based
296      * APIs.
297      *
298      * @return an array containing all the elements in this list
299      */
300     public Object [] toArray() {
301         Object [] elements = getArray();
302         return copyOf(elements, elements.length);
303     }
304
305     /**
306      * Returns an array containing all of the elements in this list in
307      * proper sequence (from first to last element); the runtime type of
308      * the returned array is that of the specified array. If the list fits
309      * in the specified array, it is returned therein. Otherwise, a new
310      * array is allocated with the runtime type of the specified array and
311      * the size of this list.
312      *
313      * <p>If this list fits in the specified array with room to spare
314      * (i.e., the array has more elements than this list), the element in
315      * the array immediately following the end of the list is set to
316      * <tt>null</tt>. (This is useful in determining the length of this
317      * list <i>only</i> if the caller knows that this list does not contain
318      * any null elements.)
319      *
320      * <p>Like the {@link #toArray()} method, this method acts as bridge between
321      * array-based and collection-based APIs. Further, this method allows
322      * precise control over the runtime type of the output array, and may,
323      * under certain circumstances, be used to save allocation costs.
324      *
325      * <p>Suppose <tt>x</tt> is a list known to contain only strings.
326      * The following code can be used to dump the list into a newly
327      * allocated array of <tt>String</tt>:
328      *
329      * <pre>
330      * String[] y = x.toArray(new String[0]);</pre>
331      *
332      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
333      * <tt>toArray()</tt>.
334      *
335      * @param a the array into which the elements of the list are to
336      * be stored, if it is big enough; otherwise, a new array of the
337      * same runtime type is allocated for this purpose.
338      * @return an array containing all the elements in this list
339      * @throws ArrayStoreException if the runtime type of the specified array
340      * is not a supertype of the runtime type of every element in
341      * this list
342      * @throws NullPointerException if the specified array is null
343      */
344     public Object [] toArray(Object a[]) {
345         Object [] elements = getArray();
346         int len = elements.length;
347         if (a.length < len)
348             return copyOf(elements, len, a.getClass());
349         else {
350             System.arraycopy(elements, 0, a, 0, len);
351             if (a.length > len)
352                 a[len] = null;
353             return a;
354         }
355     }
356
357     // Positional Access Operations
358
359     /**
360      * {@inheritDoc}
361      *
362      * @throws IndexOutOfBoundsException {@inheritDoc}
363      */
364     public Object get(int index) {
365         return (getArray()[index]);
366     }
367
368     /**
369      * Replaces the element at the specified position in this list with the
370      * specified element.
371      *
372      * @throws IndexOutOfBoundsException {@inheritDoc}
373      */
374     public synchronized Object set(int index, Object element) {
375         Object [] elements = getArray();
376         int len = elements.length;
377         Object oldValue = elements[index];
378
379         if (oldValue != element) {
380             Object [] newElements = copyOf(elements, len);
381             newElements[index] = element;
382             setArray(newElements);
383         }
384         return oldValue;
385     }
386
387     /**
388      * Appends the specified element to the end of this list.
389      *
390      * @param e element to be appended to this list
391      * @return <tt>true</tt> (as per the spec for {@link Collection#add})
392      */
393     public boolean add(Object e) {
394         synchronized (this) {
395             Object [] elements = getArray();
396             int len = elements.length;
397             Object [] newElements = copyOf(elements, len + 1);
398             newElements[len] = e;
399             setArray(newElements);
400         }
401         return true;
402     }
403
404     /**
405      * Inserts the specified element at the specified position in this
406      * list. Shifts the element currently at that position (if any) and
407      * any subsequent elements to the right (adds one to their indices).
408      *
409      * @throws IndexOutOfBoundsException {@inheritDoc}
410      */
411     public synchronized void add(int index, Object element) {
412         Object [] elements = getArray();
413         int len = elements.length;
414         if (index > len || index < 0)
415             throw new IndexOutOfBoundsException ("Index: " + index+
416                                                 ", Size: " + len);
417         Object [] newElements;
418         int numMoved = len - index;
419         if (numMoved == 0)
420             newElements = copyOf(elements, len + 1);
421         else {
422             newElements = new Object [len + 1];
423             System.arraycopy(elements, 0, newElements, 0, index);
424             System.arraycopy(elements, index, newElements, index + 1,
425                              numMoved);
426         }
427         newElements[index] = element;
428         setArray(newElements);
429     }
430
431     /**
432      * Removes the element at the specified position in this list.
433      * Shifts any subsequent elements to the left (subtracts one from their
434      * indices). Returns the element that was removed from the list.
435      *
436      * @throws IndexOutOfBoundsException {@inheritDoc}
437      */
438     public synchronized Object remove(int index) {
439         Object [] elements = getArray();
440         int len = elements.length;
441         Object oldValue = elements[index];
442         int numMoved = len - index - 1;
443         if (numMoved == 0)
444             setArray(copyOf(elements, len - 1));
445         else {
446             Object [] newElements = new Object [len - 1];
447             System.arraycopy(elements, 0, newElements, 0, index);
448             System.arraycopy(elements, index + 1, newElements, index,
449                              numMoved);
450             setArray(newElements);
451         }
452         return oldValue;
453     }
454
455     /**
456      * Removes the first occurrence of the specified element from this list,
457      * if it is present. If this list does not contain the element, it is
458      * unchanged. More formally, removes the element with the lowest index
459      * <tt>i</tt> such that
460      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
461      * (if such an element exists). Returns <tt>true</tt> if this list
462      * contained the specified element (or equivalently, if this list
463      * changed as a result of the call).
464      *
465      * @param o element to be removed from this list, if present
466      * @return <tt>true</tt> if this list contained the specified element
467      */
468     public synchronized boolean remove(Object o) {
469         Object [] elements = getArray();
470         int len = elements.length;
471         if (len != 0) {
472             // Copy while searching for element to remove
473 // This wins in the normal case of element being present
474 int newlen = len - 1;
475             Object [] newElements = new Object [newlen];
476
477             for (int i = 0; i < newlen; ++i) {
478                 if (eq(o, elements[i])) {
479                     // found one; copy remaining and exit
480 for (int k = i + 1; k < len; ++k)
481                         newElements[k-1] = elements[k];
482                     setArray(newElements);
483                     return true;
484                 } else
485                     newElements[i] = elements[i];
486             }
487
488             // special handling for last cell
489 if (eq(o, elements[newlen])) {
490                 setArray(newElements);
491                 return true;
492             }
493         }
494         return false;
495     }
496
497     /**
498      * Removes from this list all of the elements whose index is between
499      * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
500      * Shifts any succeeding elements to the left (reduces their index).
501      * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
502      * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
503      *
504      * @param fromIndex index of first element to be removed
505      * @param toIndex index after last element to be removed
506      * @throws IndexOutOfBoundsException if fromIndex or toIndex out of
507      * range (fromIndex &lt; 0 || fromIndex &gt;= size() || toIndex
508      * &gt; size() || toIndex &lt; fromIndex)
509      */
510     private synchronized void removeRange(int fromIndex, int toIndex) {
511         Object [] elements = getArray();
512         int len = elements.length;
513
514         if (fromIndex < 0 || fromIndex >= len ||
515             toIndex > len || toIndex < fromIndex)
516             throw new IndexOutOfBoundsException ();
517         int newlen = len - (toIndex - fromIndex);
518         int numMoved = len - toIndex;
519         if (numMoved == 0)
520             setArray(copyOf(elements, newlen));
521         else {
522             Object [] newElements = new Object [newlen];
523             System.arraycopy(elements, 0, newElements, 0, fromIndex);
524             System.arraycopy(elements, toIndex, newElements,
525                              fromIndex, numMoved);
526             setArray(newElements);
527         }
528     }
529
530     /**
531      * Append the element if not present.
532      *
533      * @param e element to be added to this list, if absent
534      * @return <tt>true</tt> if the element was added
535      */
536     public synchronized boolean addIfAbsent(Object e) {
537         // Copy while checking if already present.
538 // This wins in the most common case where it is not present
539 Object [] elements = getArray();
540         int len = elements.length;
541         Object [] newElements = new Object [len + 1];
542         for (int i = 0; i < len; ++i) {
543             if (eq(e, elements[i]))
544                 return false; // exit, throwing away copy
545 else
546                 newElements[i] = elements[i];
547         }
548         newElements[len] = e;
549         setArray(newElements);
550         return true;
551     }
552
553     /**
554      * Returns <tt>true</tt> if this list contains all of the elements of the
555      * specified collection.
556      *
557      * @param c collection to be checked for containment in this list
558      * @return <tt>true</tt> if this list contains all of the elements of the
559      * specified collection
560      * @throws NullPointerException if the specified collection is null
561      * @see #contains(Object)
562      */
563     public boolean containsAll(Collection c) {
564         Object [] elements = getArray();
565         int len = elements.length;
566         for (Iterator itr = c.iterator(); itr.hasNext(); ) {
567             Object e = itr.next();
568             if (indexOf(e, elements, 0, len) < 0)
569                 return false;
570         }
571         return true;
572     }
573
574     /**
575      * Removes from this list all of its elements that are contained in
576      * the specified collection. This is a particularly expensive operation
577      * in this class because of the need for an internal temporary array.
578      *
579      * @param c collection containing elements to be removed from this list
580      * @return <tt>true</tt> if this list changed as a result of the call
581      * @throws ClassCastException if the class of an element of this list
582      * is incompatible with the specified collection (optional)
583      * @throws NullPointerException if this list contains a null element and the
584      * specified collection does not permit null elements (optional),
585      * or if the specified collection is null
586      * @see #remove(Object)
587      */
588     public synchronized boolean removeAll(Collection c) {
589         Object [] elements = getArray();
590         int len = elements.length;
591         if (len != 0) {
592             // temp array holds those elements we know we want to keep
593 int newlen = 0;
594             Object [] temp = new Object [len];
595             for (int i = 0; i < len; ++i) {
596                 Object element = elements[i];
597                 if (!c.contains(element))
598                     temp[newlen++] = element;
599             }
600             if (newlen != len) {
601                 setArray(copyOfRange(temp, 0, newlen, Object [].class));
602                 return true;
603             }
604         }
605         return false;
606     }
607
608     /**
609      * Retains only the elements in this list that are contained in the
610      * specified collection. In other words, removes from this list all of
611      * its elements that are not contained in the specified collection.
612      *
613      * @param c collection containing elements to be retained in this list
614      * @return <tt>true</tt> if this list changed as a result of the call
615      * @throws ClassCastException if the class of an element of this list
616      * is incompatible with the specified collection (optional)
617      * @throws NullPointerException if this list contains a null element and the
618      * specified collection does not permit null elements (optional),
619      * or if the specified collection is null
620      * @see #remove(Object)
621      */
622     public synchronized boolean retainAll(Collection c) {
623         Object [] elements = getArray();
624         int len = elements.length;
625         if (len != 0) {
626             // temp array holds those elements we know we want to keep
627 int newlen = 0;
628             Object [] temp = new Object [len];
629             for (int i = 0; i < len; ++i) {
630                 Object element = elements[i];
631                 if (c.contains(element))
632                     temp[newlen++] = element;
633             }
634             if (newlen != len) {
635                 setArray(copyOfRange(temp, 0, newlen, Object [].class));
636                 return true;
637             }
638         }
639         return false;
640     }
641
642     /**
643      * Appends all of the elements in the specified collection that
644      * are not already contained in this list, 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 collection containing elements to be added to this list
649      * @return the number of elements added
650      * @throws NullPointerException if the specified collection is null
651      * @see #addIfAbsent(Object)
652      */
653     public int addAllAbsent(Collection c) {
654         int numNew = c.size();
655         if (numNew == 0)
656             return 0;
657         synchronized (this) {
658             Object [] elements = getArray();
659             int len = elements.length;
660
661             Object [] temp = new Object [numNew];
662             int added = 0;
663             for (Iterator itr = c.iterator(); itr.hasNext(); ) {
664                 Object e = itr.next();
665                 if (indexOf(e, elements, 0, len) < 0 &&
666                     indexOf(e, temp, 0, added) < 0)
667                     temp[added++] = e;
668             }
669             if (added != 0) {
670                 Object [] newElements = new Object [len + added];
671                 System.arraycopy(elements, 0, newElements, 0, len);
672                 System.arraycopy(temp, 0, newElements, len, added);
673                 setArray(newElements);
674             }
675             return added;
676         }
677     }
678
679     /**
680      * Removes all of the elements from this list.
681      * The list will be empty after this call returns.
682      */
683     public synchronized void clear() {
684         setArray(new Object [0]);
685     }
686
687     /**
688      * Appends all of the elements in the specified collection to the end
689      * of this list, in the order that they are returned by the specified
690      * collection's iterator.
691      *
692      * @param c collection containing elements to be added to this list
693      * @return <tt>true</tt> if this list changed as a result of the call
694      * @throws NullPointerException if the specified collection is null
695      * @see #add(Object)
696      */
697     public boolean addAll(Collection c) {
698         int numNew = c.size();
699         if (numNew == 0)
700             return false;
701         synchronized (this) {
702             Object [] elements = getArray();
703             int len = elements.length;
704             Object [] newElements = new Object [len + numNew];
705             System.arraycopy(elements, 0, newElements, 0, len);
706             for (Iterator itr = c.iterator(); itr.hasNext(); ) {
707                 Object e = itr.next();
708                 newElements[len++] = e;
709             }
710             setArray(newElements);
711             return true;
712         }
713     }
714
715     /**
716      * Inserts all of the elements in the specified collection into this
717      * list, starting at the specified position. Shifts the element
718      * currently at that position (if any) and any subsequent elements to
719      * the right (increases their indices). The new elements will appear
720      * in this list in the order that they are returned by the
721      * specified collection's iterator.
722      *
723      * @param index index at which to insert the first element
724      * from the specified collection
725      * @param c collection containing elements to be added to this list
726      * @return <tt>true</tt> if this list changed as a result of the call
727      * @throws IndexOutOfBoundsException {@inheritDoc}
728      * @throws NullPointerException if the specified collection is null
729      * @see #add(int,Object)
730      */
731     public boolean addAll(int index, Collection c) {
732         int numNew = c.size();
733         synchronized (this) {
734             Object [] elements = getArray();
735             int len = elements.length;
736             if (index > len || index < 0)
737                 throw new IndexOutOfBoundsException ("Index: " + index +
738                                                     ", Size: "+ len);
739             if (numNew == 0)
740                 return false;
741             int numMoved = len - index;
742             Object [] newElements;
743             if (numMoved == 0)
744                 newElements = copyOf(elements, len + numNew);
745             else {
746                 newElements = new Object [len + numNew];
747                 System.arraycopy(elements, 0, newElements, 0, index);
748                 System.arraycopy(elements, index,
749                                  newElements, index + numNew,
750                                  numMoved);
751             }
752             for (Iterator itr = c.iterator(); itr.hasNext(); ) {
753                 Object e = itr.next();
754                 newElements[index++] = e;
755             }
756             setArray(newElements);
757             return true;
758         }
759     }
760
761     /**
762      * Save the state of the list to a stream (i.e., serialize it).
763      *
764      * @serialData The length of the array backing the list is emitted
765      * (int), followed by all of its elements (each an Object)
766      * in the proper order.
767      * @param s the stream
768      */
769     private void writeObject(java.io.ObjectOutputStream s)
770         throws java.io.IOException {
771
772         // Write out element count, and any hidden stuff
773 s.defaultWriteObject();
774
775         Object [] elements = getArray();
776         int len = elements.length;
777         // Write out array length
778 s.writeInt(len);
779
780         // Write out all elements in the proper order.
781 for (int i = 0; i < len; i++)
782             s.writeObject(elements[i]);
783     }
784
785     /**
786      * Reconstitute the list from a stream (i.e., deserialize it).
787      * @param s the stream
788      */
789     private void readObject(java.io.ObjectInputStream s)
790         throws java.io.IOException , ClassNotFoundException {
791
792         // Read in size, and any hidden stuff
793 s.defaultReadObject();
794
795         // Read in array length and allocate array
796 int len = s.readInt();
797         Object [] elements = new Object [len];
798
799         // Read in all elements in the proper order.
800 for (int i = 0; i < len; i++)
801             elements[i] = s.readObject();
802         setArray(elements);
803
804     }
805
806     /**
807      * Returns a string representation of this list, containing
808      * the String representation of each element.
809      */
810     public String toString() {
811         Object [] elements = getArray();
812         int maxIndex = elements.length - 1;
813         StringBuffer buf = new StringBuffer ();
814         buf.append("[");
815         for (int i = 0; i <= maxIndex; i++) {
816             buf.append(String.valueOf(elements[i]));
817             if (i < maxIndex)
818                 buf.append(", ");
819         }
820         buf.append("]");
821         return buf.toString();
822     }
823
824     /**
825      * Compares the specified object with this list for equality.
826      * Returns true if and only if the specified object is also a {@link
827      * List}, both lists have the same size, and all corresponding pairs
828      * of elements in the two lists are <em>equal</em>. (Two elements
829      * <tt>e1</tt> and <tt>e2</tt> are <em>equal</em> if <tt>(e1==null ?
830      * e2==null : e1.equals(e2))</tt>.) In other words, two lists are
831      * defined to be equal if they contain the same elements in the same
832      * order.
833      *
834      * @param o the object to be compared for equality with this list
835      * @return <tt>true</tt> if the specified object is equal to this list
836      */
837     public boolean equals(Object o) {
838         if (o == this)
839             return true;
840         if (!(o instanceof List ))
841             return false;
842
843         List l2 = (List )(o);
844         if (size() != l2.size())
845             return false;
846
847         ListIterator e1 = listIterator();
848         ListIterator e2 = l2.listIterator();
849         while (e1.hasNext()) {
850             if (!eq(e1.next(), e2.next()))
851                 return false;
852         }
853         return true;
854     }
855
856     /**
857      * Returns the hash code value for this list.
858      *
859      * <p>This implementation uses the definition in {@link List#hashCode}.
860      *
861      * @return the hash code value for this list
862      */
863     public int hashCode() {
864         int hashCode = 1;
865         Object [] elements = getArray();
866         int len = elements.length;
867         for (int i = 0; i < len; ++i) {
868             Object obj = elements[i];
869             hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
870         }
871         return hashCode;
872     }
873
874     /**
875      * Returns an iterator over the elements in this list in proper sequence.
876      *
877      * <p>The returned iterator provides a snapshot of the state of the list
878      * when the iterator was constructed. No synchronization is needed while
879      * traversing the iterator. The iterator does <em>NOT</em> support the
880      * <tt>remove</tt> method.
881      *
882      * @return an iterator over the elements in this list in proper sequence
883      */
884     public Iterator iterator() {
885         return new COWIterator(getArray(), 0);
886     }
887
888     /**
889      * {@inheritDoc}
890      *
891      * <p>The returned iterator provides a snapshot of the state of the list
892      * when the iterator was constructed. No synchronization is needed while
893      * traversing the iterator. The iterator does <em>NOT</em> support the
894      * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
895      */
896     public ListIterator listIterator() {
897         return new COWIterator(getArray(), 0);
898     }
899
900     /**
901      * {@inheritDoc}
902      *
903      * <p>The list iterator returned by this implementation will throw an
904      * <tt>UnsupportedOperationException</tt> in its <tt>remove</tt>,
905      * <tt>set</tt> and <tt>add</tt> methods.
906      *
907      * @throws IndexOutOfBoundsException {@inheritDoc}
908      */
909     public ListIterator listIterator(final int index) {
910         Object [] elements = getArray();
911         int len = elements.length;
912         if (index < 0 || index > len)
913             throw new IndexOutOfBoundsException ("Index: " + index);
914
915         return new COWIterator(getArray(), index);
916     }
917
918     private static class COWIterator implements ListIterator {
919         /** Snapshot of the array **/
920         private final Object [] snapshot;
921         /** Index of element to be returned by subsequent call to next. */
922         private int cursor;
923
924         private COWIterator(Object [] elements, int initialCursor) {
925             cursor = initialCursor;
926             snapshot = elements;
927         }
928
929         public boolean hasNext() {
930             return cursor < snapshot.length;
931         }
932
933         public boolean hasPrevious() {
934             return cursor > 0;
935         }
936
937         public Object next() {
938             try {
939                 return (snapshot[cursor++]);
940             } catch (IndexOutOfBoundsException ex) {
941                 throw new NoSuchElementException ();
942             }
943         }
944
945         public Object previous() {
946             try {
947                 return (snapshot[--cursor]);
948             } catch (IndexOutOfBoundsException e) {
949                 throw new NoSuchElementException ();
950             }
951         }
952
953         public int nextIndex() {
954             return cursor;
955         }
956
957         public int previousIndex() {
958             return cursor - 1;
959         }
960
961         /**
962          * Not supported. Always throws UnsupportedOperationException.
963          * @throws UnsupportedOperationException always; <tt>remove</tt>
964          * is not supported by this iterator.
965          */
966         public void remove() {
967             throw new UnsupportedOperationException ();
968         }
969
970         /**
971          * Not supported. Always throws UnsupportedOperationException.
972          * @throws UnsupportedOperationException always; <tt>set</tt>
973          * is not supported by this iterator.
974          */
975         public void set(Object e) {
976             throw new UnsupportedOperationException ();
977         }
978
979         /**
980          * Not supported. Always throws UnsupportedOperationException.
981          * @throws UnsupportedOperationException always; <tt>add</tt>
982          * is not supported by this iterator.
983          */
984         public void add(Object e) {
985             throw new UnsupportedOperationException ();
986         }
987     }
988
989     /**
990      * Returns a view of the portion of this list between
991      * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
992      * The returned list is backed by this list, so changes in the
993      * returned list are reflected in this list, and vice-versa.
994      * While mutative operations are supported, they are probably not
995      * very useful for CopyOnWriteArrayLists.
996      *
997      * <p>The semantics of the list returned by this method become
998      * undefined if the backing list (i.e., this list) is
999      * <i>structurally modified</i> in any way other than via the
1000     * returned list. (Structural modifications are those that change
1001     * the size of the list, or otherwise perturb it in such a fashion
1002     * that iterations in progress may yield incorrect results.)
1003     *
1004     * @param fromIndex low endpoint (inclusive) of the subList
1005     * @param toIndex high endpoint (exclusive) of the subList
1006     * @return a view of the specified range within this list
1007     * @throws IndexOutOfBoundsException {@inheritDoc}
1008     */
1009    public synchronized List subList(int fromIndex, int toIndex) {
1010        Object [] elements = getArray();
1011        int len = elements.length;
1012        if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
1013            throw new IndexOutOfBoundsException ();
1014        return new COWSubList(this, fromIndex, toIndex);
1015    }
1016
1017
1018    /**
1019     * Sublist for CopyOnWriteArrayList.
1020     * This class extends AbstractList merely for convenience, to
1021     * avoid having to define addAll, etc. This doesn't hurt, but
1022     * is wasteful. This class does not need or use modCount
1023     * mechanics in AbstractList, but does need to check for
1024     * concurrent modification using similar mechanics. On each
1025     * operation, the array that we expect the backing list to use
1026     * is checked and updated. Since we do this for all of the
1027     * base operations invoked by those defined in AbstractList,
1028     * all is well. While inefficient, this is not worth
1029     * improving. The kinds of list operations inherited from
1030     * AbstractList are already so slow on COW sublists that
1031     * adding a bit more space/time doesn't seem even noticeable.
1032     */
1033    private static class COWSubList extends AbstractList {
1034        private final CopyOnWriteArrayList l;
1035        private final int offset;
1036        private int size;
1037        private Object [] expectedArray;
1038
1039        // only call this holding l's lock
1040 private COWSubList(CopyOnWriteArrayList list,
1041                           int fromIndex, int toIndex) {
1042            l = list;
1043            expectedArray = l.getArray();
1044            offset = fromIndex;
1045            size = toIndex - fromIndex;
1046        }
1047
1048        // only call this holding l's lock
1049 private void checkForComodification() {
1050            if (l.getArray() != expectedArray)
1051                throw new ConcurrentModificationException ();
1052        }
1053
1054        // only call this holding l's lock
1055 private void rangeCheck(int index) {
1056            if (index < 0 || index >= size)
1057                throw new IndexOutOfBoundsException ("Index: " + index +
1058                                                    ",Size: " + size);
1059        }
1060
1061        public Object set(int index, Object element) {
1062            synchronized (l) {
1063                rangeCheck(index);
1064                checkForComodification();
1065                Object x = l.set(index + offset, element);
1066                expectedArray = l.getArray();
1067                return x;
1068            }
1069        }
1070
1071        public Object get(int index) {
1072            synchronized (l) {
1073                rangeCheck(index);
1074                checkForComodification();
1075                return l.get(index + offset);
1076            }
1077        }
1078
1079        public int size() {
1080            synchronized (l) {
1081                checkForComodification();
1082                return size;
1083            }
1084        }
1085
1086        public void add(int index, Object element) {
1087            synchronized (l) {
1088                checkForComodification();
1089                if (index<0 || index>size)
1090                    throw new IndexOutOfBoundsException ();
1091                l.add(index + offset, element);
1092                expectedArray = l.getArray();
1093                size++;
1094            }
1095        }
1096
1097        public void clear() {
1098            synchronized (l) {
1099                checkForComodification();
1100                l.removeRange(offset, offset+size);
1101                expectedArray = l.getArray();
1102                size = 0;
1103            }
1104        }
1105
1106        public Object remove(int index) {
1107            synchronized (l) {
1108                rangeCheck(index);
1109                checkForComodification();
1110                Object result = l.remove(index + offset);
1111                expectedArray = l.getArray();
1112                size--;
1113                return result;
1114            }
1115        }
1116
1117        public Iterator iterator() {
1118            synchronized (l) {
1119                checkForComodification();
1120                return new COWSubListIterator(l, 0, offset, size);
1121            }
1122        }
1123
1124        public ListIterator listIterator(final int index) {
1125            synchronized (l) {
1126                checkForComodification();
1127                if (index<0 || index>size)
1128                    throw new IndexOutOfBoundsException ("Index: "+index+
1129                                                        ", Size: "+size);
1130                return new COWSubListIterator(l, index, offset, size);
1131            }
1132        }
1133
1134        public List subList(int fromIndex, int toIndex) {
1135            synchronized (l) {
1136                checkForComodification();
1137                if (fromIndex<0 || toIndex>size)
1138                    throw new IndexOutOfBoundsException ();
1139                return new COWSubList(l, fromIndex + offset,
1140                                         toIndex + offset);
1141            }
1142        }
1143
1144    }
1145
1146
1147    private static class COWSubListIterator implements ListIterator {
1148        private final ListIterator i;
1149        private final int offset;
1150        private final int size;
1151        private COWSubListIterator(List l, int index, int offset,
1152                                   int size) {
1153            this.offset = offset;
1154            this.size = size;
1155            i = l.listIterator(index + offset);
1156        }
1157
1158        public boolean hasNext() {
1159            return nextIndex() < size;
1160        }
1161
1162        public Object next() {
1163            if (hasNext())
1164                return i.next();
1165            else
1166                throw new NoSuchElementException ();
1167        }
1168
1169        public boolean hasPrevious() {
1170            return previousIndex() >= 0;
1171        }
1172
1173        public Object previous() {
1174            if (hasPrevious())
1175                return i.previous();
1176            else
1177                throw new NoSuchElementException ();
1178        }
1179
1180        public int nextIndex() {
1181            return i.nextIndex() - offset;
1182        }
1183
1184        public int previousIndex() {
1185            return i.previousIndex() - offset;
1186        }
1187
1188        public void remove() {
1189            throw new UnsupportedOperationException ();
1190        }
1191
1192        public void set(Object e) {
1193            throw new UnsupportedOperationException ();
1194        }
1195
1196        public void add(Object e) {
1197            throw new UnsupportedOperationException ();
1198        }
1199    }
1200
1201// // Support for resetting lock while deserializing
1202// private static final Unsafe unsafe = Unsafe.getUnsafe();
1203// private static final long lockOffset;
1204// static {
1205// try {
1206// lockOffset = unsafe.objectFieldOffset
1207// (CopyOnWriteArrayList.class.getDeclaredField("lock"));
1208// } catch (Exception ex) { throw new Error(ex); }
1209// }
1210// private void resetLock() {
1211// unsafe.putObjectVolatile(this, lockOffset, new ReentrantLock());
1212// }
1213//
1214
1215    // Temporary emulations of anticipated new j.u.Arrays functions
1216
1217    private static Object [] copyOfRange(Object [] original, int from, int to,
1218                                        Class newType) {
1219        int newLength = to - from;
1220        if (newLength < 0)
1221            throw new IllegalArgumentException (from + " > " + to);
1222        Object [] copy = (Object []) java.lang.reflect.Array.newInstance
1223            (newType.getComponentType(), newLength);
1224        System.arraycopy(original, from, copy, 0,
1225                         Math.min(original.length - from, newLength));
1226        return copy;
1227    }
1228
1229    private static Object [] copyOf(Object [] original, int newLength,
1230                                   Class newType) {
1231        Object [] copy = (Object []) java.lang.reflect.Array.newInstance
1232            (newType.getComponentType(), newLength);
1233        System.arraycopy(original, 0, copy, 0,
1234                         Math.min(original.length, newLength));
1235        return copy;
1236    }
1237
1238    private static Object [] copyOf(Object [] original, int newLength) {
1239        return copyOf(original, newLength, original.getClass());
1240    }
1241}
1242

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags