Mercurial > hg > blitz_stable

comparison src/EDU/oswego/cs/dl/util/concurrent/CopyOnWriteArrayList.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial checkin of blitz 2.0 fcs - no installer yet.
author Dan Creswell <dan.creswell@gmail.com>
date Sat, 21 Mar 2009 11:00:06 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:3dc0c5604566
1 /*
2 File: CopyOnWriteArrayList.java
3
4 Written by Doug Lea. Adapted from JDK1.2 ArrayList.java
5 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 History:
18 Date Who What
19 21Jun1998 dl Create public version
20 9Oct1999 dl faster equals
21 29jun2001 dl Serialization methods now private
22 */
23
24 package EDU.oswego.cs.dl.util.concurrent;
25 import java.util.*;
26
27 /**
28 * This class implements a variant of java.util.ArrayList in which
29 * all mutative operations (add, set, and so on) are implemented
30 * by making a fresh copy of the underlying array.
31 * <p>
32 * This is ordinarily too costly, but it becomes attractive when traversal
33 * operations vastly overwhelm mutations, and, especially,
34 * when you cannot or don't want to
35 * synchronize traversals, yet need to preclude interference
36 * among concurrent threads.
37 * The iterator method uses a reference to the
38 * state of the array at the point that the
39 * iterator was created. This array never changes during
40 * the lifetime of the iterator, so interference is impossible.
41 * (The iterator will not traverse elements added or changed
42 * since the iterator was created, but usually this is a desirable
43 * feature.)
44 * <p>
45 * As much code and documentation as possible was shamelessly copied from
46 * java.util.ArrayList (Thanks, Josh!), with the intent of preserving
47 * all semantics of ArrayList except for the copy-on-write
48 * property.
49 * (The java.util
50 * collection code could not be subclassed here since all of the existing
51 * collection classes assume elementwise mutability.)
52 * <p>
53 * Because of the copy-on-write policy, some one-by-one
54 * mutative operations
55 * in the java.util.Arrays and java.util.Collections classes
56 * are so time/space intensive as to never
57 * be worth calling (except perhaps as benchmarks for garbage collectors :-).
58 * <p>
59 * Three methods are supported in addition to
60 * those described in List and ArrayList. The addIfAbsent
61 * and addAllAbsent methods provide Set semantics for add,
62 * and are used in CopyOnWriteArraySet. However, they
63 * can also be used directly from this List version.
64 * The copyIn method (and
65 * a constructor that invokes it) allow
66 * you to copy in an initial array to use. This method can
67 * be useful when you first want to perform many operations
68 * on a plain array, and then make a copy available for
69 * use through the collection API.
70 * <p>
71 * Due to their strict read-only nature,
72 * element-changing operations on iterators
73 * (remove, set, and add) are not supported. These
74 * are the only methods throwing UnsupportedOperationException.
75 * <p>
76 * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
77 * @see CopyOnWriteArraySet
78 **/
79
80
81 public class CopyOnWriteArrayList implements List, Cloneable, java.io.Serializable {
82 /**
83 * The held array. Directly access only within synchronized
84 * methods
85 */
86
87 protected transient Object[] array_;
88
89 /**
90 * Accessor to the array intended to be called from
91 * within unsynchronized read-only methods
92 **/
93 protected synchronized Object[] array() { return array_; }
94
95 /**
96 * Constructs an empty list
97 *
98 */
99 public CopyOnWriteArrayList() {
100 array_ = new Object[0];
101 }
102
103 /**
104 * Constructs an list containing the elements of the specified
105 * Collection, in the order they are returned by the Collection's
106 * iterator.
107 */
108 public CopyOnWriteArrayList(Collection c) {
109 array_ = new Object[c.size()];
110 Iterator i = c.iterator();
111 int size = 0;
112 while (i.hasNext())
113 array_[size++] = i.next();
114 }
115
116 /**
117 * Create a new CopyOnWriteArrayList holding a copy of given array
118 * @param toCopyIn the array. A copy of this array is used as the
119 * internal array.
120 **/
121 public CopyOnWriteArrayList(Object[] toCopyIn) {
122 copyIn(toCopyIn, 0, toCopyIn.length);
123 }
124
125 /**
126 * Replace the held array with a copy of the <code>n</code>
127 * elements of the provided array, starting at position <code>first</code>.
128 * To copy an entire array, call with arguments (array, 0, array.length).
129 * @param toCopyIn the array. A copy of the indicated elements of
130 * this array is used as the
131 * internal array.
132 * @param first The index of first position of the array to
133 * start copying from.
134 * @param n the number of elements to copy. This will be the new size of
135 * the list.
136 **/
137 public synchronized void copyIn(Object[] toCopyIn, int first, int n) {
138 array_ = new Object[n];
139 System.arraycopy(toCopyIn, first, array_, 0, n);
140 }
141
142 /**
143 * Returns the number of components in this list.
144 *
145 * @return the number of components in this list.
146 */
147 public int size() {
148 return array().length;
149 }
150
151 /**
152 * Tests if this list has no components.
153 *
154 * @return <code>true</code> if this list has no components;
155 * <code>false</code> otherwise.
156 */
157 public boolean isEmpty() {
158 return size() == 0;
159 }
160
161 /**
162 * Returns true if this list contains the specified element.
163 *
164 * @param o element whose presence in this List is to be tested.
165 */
166 public boolean contains(Object elem) {
167 Object[] elementData = array();
168 int len = elementData.length;
169 return indexOf(elem, elementData, len) >= 0;
170 }
171
172 /**
173 * Searches for the first occurence of the given argument, testing
174 * for equality using the <code>equals</code> method.
175 *
176 * @param elem an object.
177 * @return the index of the first occurrence of the argument in this
178 * list; returns <code>-1</code> if the object is not found.
179 * @see Object#equals(Object)
180 */
181 public int indexOf(Object elem) {
182 Object[] elementData = array();
183 int len = elementData.length;
184 return indexOf(elem, elementData, len);
185 }
186
187
188 /**
189 * static version allows repeated call without needed
190 * to grab lock for array each time
191 **/
192
193 protected static int indexOf(Object elem,
194 Object[] elementData,
195 int len) {
196 if (elem == null) {
197 for (int i = 0; i < len; i++)
198 if (elementData[i]==null)
199 return i;
200 } else {
201 for (int i = 0; i < len; i++)
202 if (elem.equals(elementData[i]))
203 return i;
204 }
205 return -1;
206 }
207
208 /**
209 * Searches for the first occurence of the given argument, beginning
210 * the search at <code>index</code>, and testing for equality using
211 * the <code>equals</code> method.
212 *
213 * @param elem an object.
214 * @param index the index to start searching from.
215 * @return the index of the first occurrence of the object argument in
216 * this List at position <code>index</code> or later in the
217 * List; returns <code>-1</code> if the object is not found.
218 * @see Object#equals(Object)
219 */
220
221 // needed in order to compile on 1.2b3
222 public int indexOf(Object elem, int index) {
223 Object[] elementData = array();
224 int elementCount = elementData.length;
225
226 if (elem == null) {
227 for (int i = index ; i < elementCount ; i++)
228 if (elementData[i]==null)
229 return i;
230 } else {
231 for (int i = index ; i < elementCount ; i++)
232 if (elem.equals(elementData[i]))
233 return i;
234 }
235 return -1;
236 }
237
238 /**
239 * Returns the index of the last occurrence of the specified object in
240 * this list.
241 *
242 * @param elem the desired component.
243 * @return the index of the last occurrence of the specified object in
244 * this list; returns -1 if the object is not found.
245 */
246 public int lastIndexOf(Object elem) {
247 Object[] elementData = array();
248 int len = elementData.length;
249 return lastIndexOf(elem, elementData, len);
250 }
251
252 protected static int lastIndexOf(Object elem,
253 Object[] elementData,
254 int len) {
255 if (elem == null) {
256 for (int i = len-1; i >= 0; i--)
257 if (elementData[i]==null)
258 return i;
259 } else {
260 for (int i = len-1; i >= 0; i--)
261 if (elem.equals(elementData[i]))
262 return i;
263 }
264 return -1;
265 }
266
267 /**
268 * Searches backwards for the specified object, starting from the
269 * specified index, and returns an index to it.
270 *
271 * @param elem the desired component.
272 * @param index the index to start searching from.
273 * @return the index of the last occurrence of the specified object in this
274 * List at position less than index in the List;
275 * -1 if the object is not found.
276 */
277
278 public int lastIndexOf(Object elem, int index) {
279 // needed in order to compile on 1.2b3
280 Object[] elementData = array();
281 if (elem == null) {
282 for (int i = index; i >= 0; i--)
283 if (elementData[i]==null)
284 return i;
285 } else {
286 for (int i = index; i >= 0; i--)
287 if (elem.equals(elementData[i]))
288 return i;
289 }
290 return -1;
291 }
292
293 /**
294 * Returns a shallow copy of this list. (The elements themselves
295 * are not copied.)
296 *
297 * @return a clone of this list.
298 */
299 public Object clone() {
300 try {
301 Object[] elementData = array();
302 CopyOnWriteArrayList v = (CopyOnWriteArrayList)super.clone();
303 v.array_ = new Object[elementData.length];
304 System.arraycopy(elementData, 0, v.array_, 0, elementData.length);
305 return v;
306 } catch (CloneNotSupportedException e) {
307 // this shouldn't happen, since we are Cloneable
308 throw new InternalError();
309 }
310 }
311
312 /**
313 * Returns an array containing all of the elements in this list
314 * in the correct order.
315 */
316 public Object[] toArray() {
317 Object[] elementData = array();
318 Object[] result = new Object[elementData.length];
319 System.arraycopy(elementData, 0, result, 0, elementData.length);
320 return result;
321 }
322
323 /**
324 * Returns an array containing all of the elements in this list in the
325 * correct order. The runtime type of the returned array is that of the
326 * specified array. If the list fits in the specified array, it is
327 * returned therein. Otherwise, a new array is allocated with the runtime
328 * type of the specified array and the size of this list.
329 * <p>
330 * If the list fits in the specified array with room to spare
331 * (i.e., the array has more elements than the list),
332 * the element in the array immediately following the end of the
333 * collection is set to null. This is useful in determining the length
334 * of the list <em>only</em> if the caller knows that the list
335 * does not contain any null elements.
336 *
337 * @param a the array into which the elements of the list are to
338 * be stored, if it is big enough; otherwise, a new array of the
339 * same runtime type is allocated for this purpose.
340 * @return an array containing the elements of the list.
341 * @exception ArrayStoreException the runtime type of a is not a supertype
342 * of the runtime type of every element in this list.
343 */
344 public Object[] toArray(Object a[]) {
345 Object[] elementData = array();
346
347 if (a.length < elementData.length)
348 a = (Object[])
349 java.lang.reflect.Array.newInstance(a.getClass().getComponentType(),
350 elementData.length);
351
352 System.arraycopy(elementData, 0, a, 0, elementData.length);
353
354 if (a.length > elementData.length)
355 a[elementData.length] = null;
356
357 return a;
358 }
359
360 // Positional Access Operations
361
362 /**
363 * Returns the element at the specified position in this list.
364 *
365 * @param index index of element to return.
366 * @exception IndexOutOfBoundsException index is out of range (index
367 * &lt; 0 || index &gt;= size()).
368 */
369 public Object get(int index) {
370 Object[] elementData = array();
371 rangeCheck(index, elementData.length);
372 return elementData[index];
373 }
374
375 /**
376 * Replaces the element at the specified position in this list with
377 * the specified element.
378 *
379 * @param index index of element to replace.
380 * @param element element to be stored at the specified position.
381 * @return the element previously at the specified position.
382 * @exception IndexOutOfBoundsException index out of range
383 * (index &lt; 0 || index &gt;= size()).
384 */
385 public synchronized Object set(int index, Object element) {
386 int len = array_.length;
387 rangeCheck(index, len);
388 Object oldValue = array_[index];
389
390 boolean same = (oldValue == element ||
391 (element != null && element.equals(oldValue)));
392 if (!same) {
393 Object[] newArray = new Object[len];
394 System.arraycopy(array_, 0, newArray, 0, len);
395 newArray[index] = element;
396 array_ = newArray;
397 }
398 return oldValue;
399 }
400
401 /**
402 * Appends the specified element to the end of this list.
403 *
404 * @param element element to be appended to this list.
405 * @return true (as per the general contract of Collection.add).
406 */
407 public synchronized boolean add(Object element) {
408 int len = array_.length;
409 Object[] newArray = new Object[len+1];
410 System.arraycopy(array_, 0, newArray, 0, len);
411 newArray[len] = element;
412 array_ = newArray;
413 return true;
414 }
415
416 /**
417 * Inserts the specified element at the specified position in this
418 * list. Shifts the element currently at that position (if any) and
419 * any subsequent elements to the right (adds one to their indices).
420 *
421 * @param index index at which the specified element is to be inserted.
422 * @param element element to be inserted.
423 * @exception IndexOutOfBoundsException index is out of range
424 * (index &lt; 0 || index &gt; size()).
425 */
426 public synchronized void add(int index, Object element) {
427 int len = array_.length;
428 if (index > len || index < 0)
429 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
430
431 Object[] newArray = new Object[len+1];
432 System.arraycopy(array_, 0, newArray, 0, index);
433 newArray[index] = element;
434 System.arraycopy(array_, index, newArray, index+1, len - index);
435 array_ = newArray;
436 }
437
438 /**
439 * Removes the element at the specified position in this list.
440 * Shifts any subsequent elements to the left (subtracts one from their
441 * indices). Returns the element that was removed from the list.
442 *
443 * @exception IndexOutOfBoundsException index out of range (index
444 * &lt; 0 || index &gt;= size()).
445 * @param index the index of the element to removed.
446 */
447 public synchronized Object remove(int index) {
448 int len = array_.length;
449 rangeCheck(index, len);
450 Object oldValue = array_[index];
451 Object[] newArray = new Object[len-1];
452 System.arraycopy(array_, 0, newArray, 0, index);
453 int numMoved = len - index - 1;
454 if (numMoved > 0)
455 System.arraycopy(array_, index+1, newArray, index, numMoved);
456 array_ = newArray;
457 return oldValue;
458 }
459
460 /**
461 * Removes a single instance of the specified element from this Collection,
462 * if it is present (optional operation). More formally, removes an
463 * element <code>e</code> such that <code>(o==null ? e==null :
464 * o.equals(e))</code>, if the Collection contains one or more such
465 * elements. Returns true if the Collection contained the specified
466 * element (or equivalently, if the Collection changed as a result of the
467 * call).
468 *
469 * @param element element to be removed from this Collection, if present.
470 * @return true if the Collection changed as a result of the call.
471 */
472 public synchronized boolean remove(Object element) {
473 int len = array_.length;
474 if (len == 0) return false;
475
476 // Copy while searching for element to remove
477 // This wins in the normal case of element being present
478
479 int newlen = len-1;
480 Object[] newArray = new Object[newlen];
481
482 for (int i = 0; i < newlen; ++i) {
483 if (element == array_[i] ||
484 (element != null && element.equals(array_[i]))) {
485 // found one; copy remaining and exit
486 for (int k = i + 1; k < len; ++k) newArray[k-1] = array_[k];
487 array_ = newArray;
488 return true;
489 }
490 else
491 newArray[i] = array_[i];
492 }
493 // special handling for last cell
494
495 if (element == array_[newlen] ||
496 (element != null && element.equals(array_[newlen]))) {
497 array_ = newArray;
498 return true;
499 }
500 else
501 return false; // throw away copy
502
503 }
504
505
506 /**
507 * Removes from this List all of the elements whose index is between
508 * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding
509 * elements to the left (reduces their index).
510 * This call shortens the List by (toIndex - fromIndex) elements. (If
511 * toIndex==fromIndex, this operation has no effect.)
512 *
513 * @param fromIndex index of first element to be removed.
514 * @param fromIndex index after last element to be removed.
515 * @exception IndexOutOfBoundsException fromIndex or toIndex out of
516 * range (fromIndex &lt; 0 || fromIndex &gt;= size() || toIndex
517 * &gt; size() || toIndex &lt; fromIndex).
518 */
519 public synchronized void removeRange(int fromIndex, int toIndex) {
520 int len = array_.length;
521
522 if (fromIndex < 0 || fromIndex >= len ||
523 toIndex > len || toIndex < fromIndex)
524 throw new IndexOutOfBoundsException();
525
526 int numMoved = len - toIndex;
527 int newlen = len - (toIndex-fromIndex);
528 Object[] newArray = new Object[newlen];
529 System.arraycopy(array_, 0, newArray, 0, fromIndex);
530 System.arraycopy(array_, toIndex, newArray, fromIndex, numMoved);
531 array_ = newArray;
532 }
533
534
535 /**
536 * Append the element if not present.
537 * This operation can be used to obtain Set semantics
538 * for lists.
539 * @param element element to be added to this Collection, if absent.
540 * @return true if added
541 **/
542 public synchronized boolean addIfAbsent(Object element) {
543 // Copy while checking if already present.
544 // This wins in the most common case where it is not present
545 int len = array_.length;
546 Object[] newArray = new Object[len + 1];
547 for (int i = 0; i < len; ++i) {
548 if (element == array_[i] ||
549 (element != null && element.equals(array_[i])))
550 return false; // exit, throwing away copy
551 else
552 newArray[i] = array_[i];
553 }
554 newArray[len] = element;
555 array_ = newArray;
556 return true;
557 }
558
559 /**
560 * Returns true if this Collection contains all of the elements in the
561 * specified Collection.
562 * <p>
563 * This implementation iterates over the specified Collection, checking
564 * each element returned by the Iterator in turn to see if it's
565 * contained in this Collection. If all elements are so contained
566 * true is returned, otherwise false.
567 *
568 */
569 public boolean containsAll(Collection c) {
570 Object[] elementData = array();
571 int len = elementData.length;
572 Iterator e = c.iterator();
573 while (e.hasNext())
574 if(indexOf(e.next(), elementData, len) < 0)
575 return false;
576
577 return true;
578 }
579
580
581 /**
582 * Removes from this Collection all of its elements that are contained in
583 * the specified Collection. This is a particularly expensive operation
584 * in this class because of the need for an internal temporary array.
585 * <p>
586 *
587 * @return true if this Collection changed as a result of the call.
588 */
589 public synchronized boolean removeAll(Collection c) {
590 Object[] elementData = array_;
591 int len = elementData.length;
592 if (len == 0) return false;
593
594 // temp array holds those elements we know we want to keep
595 Object[] temp = new Object[len];
596 int newlen = 0;
597 for (int i = 0; i < len; ++i) {
598 Object element = elementData[i];
599 if (!c.contains(element)) {
600 temp[newlen++] = element;
601 }
602 }
603
604 if (newlen == len) return false;
605
606 // copy temp as new array
607 Object[] newArray = new Object[newlen];
608 System.arraycopy(temp, 0, newArray, 0, newlen);
609 array_ = newArray;
610 return true;
611 }
612
613 /**
614 * Retains only the elements in this Collection that are contained in the
615 * specified Collection (optional operation). In other words, removes from
616 * this Collection all of its elements that are not contained in the
617 * specified Collection.
618 * @return true if this Collection changed as a result of the call.
619 */
620 public synchronized boolean retainAll(Collection c) {
621 Object[] elementData = array_;
622 int len = elementData.length;
623 if (len == 0) return false;
624
625 Object[] temp = new Object[len];
626 int newlen = 0;
627 for (int i = 0; i < len; ++i) {
628 Object element = elementData[i];
629 if (c.contains(element)) {
630 temp[newlen++] = element;
631 }
632 }
633
634 if (newlen == len) return false;
635
636 Object[] newArray = new Object[newlen];
637 System.arraycopy(temp, 0, newArray, 0, newlen);
638 array_ = newArray;
639 return true;
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 elements to be added into this list.
649 * @return the number of elements added
650 */
651
652 public synchronized int addAllAbsent(Collection c) {
653 int numNew = c.size();
654 if (numNew == 0) return 0;
655
656 Object[] elementData = array_;
657 int len = elementData.length;
658
659 Object[] temp = new Object[numNew];
660 int added = 0;
661 Iterator e = c.iterator();
662 while (e.hasNext()) {
663 Object element = e.next();
664 if (indexOf(element, elementData, len) < 0) {
665 if (indexOf(element, temp, added) < 0) {
666 temp[added++] = element;
667 }
668 }
669 }
670
671 if (added == 0) return 0;
672
673 Object[] newArray = new Object[len+added];
674 System.arraycopy(elementData, 0, newArray, 0, len);
675 System.arraycopy(temp, 0, newArray, len, added);
676 array_ = newArray;
677 return added;
678 }
679
680 /**
681 * Removes all of the elements from this list.
682 *
683 */
684 public synchronized void clear() {
685 array_ = new Object[0];
686 }
687
688 /**
689 * Appends all of the elements in the specified Collection to the end of
690 * this list, in the order that they are returned by the
691 * specified Collection's Iterator.
692 *
693 * @param c elements to be inserted into this list.
694 */
695 public synchronized boolean addAll(Collection c) {
696 int numNew = c.size();
697 if (numNew == 0) return false;
698
699 int len = array_.length;
700 Object[] newArray = new Object[len+numNew];
701 System.arraycopy(array_, 0, newArray, 0, len);
702 Iterator e = c.iterator();
703 for (int i=0; i<numNew; i++)
704 newArray[len++] = e.next();
705 array_ = newArray;
706
707 return true;
708 }
709
710 /**
711 * Inserts all of the elements in the specified Collection into this
712 * list, starting at the specified position. Shifts the element
713 * currently at that position (if any) and any subsequent elements to
714 * the right (increases their indices). The new elements will appear
715 * in the list in the order that they are returned by the
716 * specified Collection's iterator.
717 *
718 * @param index index at which to insert first element
719 * from the specified collection.
720 * @param c elements to be inserted into this list.
721 * @exception IndexOutOfBoundsException index out of range (index
722 * &lt; 0 || index &gt; size()).
723 */
724 public synchronized boolean addAll(int index, Collection c) {
725 int len = array_.length;
726 if (index > len || index < 0)
727 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
728
729 int numNew = c.size();
730 if (numNew == 0) return false;
731
732 Object[] newArray = new Object[len+numNew];
733 System.arraycopy(array_, 0, newArray, 0, len);
734 int numMoved = len - index;
735 if (numMoved > 0)
736 System.arraycopy(array_, index, newArray, index + numNew, numMoved);
737 Iterator e = c.iterator();
738 for (int i=0; i<numNew; i++)
739 newArray[index++] = e.next();
740 array_ = newArray;
741
742 return true;
743 }
744
745 /**
746 * Check if the given index is in range. If not, throw an appropriate
747 * runtime exception.
748 */
749 protected void rangeCheck(int index, int length) {
750 if (index >= length || index < 0)
751 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+ length);
752 }
753 /**
754 * Save the state of the list to a stream (i.e., serialize it).
755 *
756 * @serialData The length of the array backing the list is emitted
757 * (int), followed by all of its elements (each an Object)
758 * in the proper order.
759 */
760 private void writeObject(java.io.ObjectOutputStream s)
761 throws java.io.IOException{
762 // Write out element count, and any hidden stuff
763 s.defaultWriteObject();
764
765 Object[] elementData = array();
766 // Write out array length
767 s.writeInt(elementData.length);
768
769 // Write out all elements in the proper order.
770 for (int i=0; i<elementData.length; i++)
771 s.writeObject(elementData[i]);
772 }
773
774 /**
775 * Reconstitute the list from a stream (i.e., deserialize it).
776 */
777 private synchronized void readObject(java.io.ObjectInputStream s)
778 throws java.io.IOException, ClassNotFoundException {
779 // Read in size, and any hidden stuff
780 s.defaultReadObject();
781
782 // Read in array length and allocate array
783 int arrayLength = s.readInt();
784 Object[] elementData = new Object[arrayLength];
785
786 // Read in all elements in the proper order.
787 for (int i=0; i<elementData.length; i++)
788 elementData[i] = s.readObject();
789 array_ = elementData;
790 }
791
792 /**
793 * Returns a string representation of this Collection, containing
794 * the String representation of each element.
795 */
796 public String toString() {
797 StringBuffer buf = new StringBuffer();
798 Iterator e = iterator();
799 buf.append("[");
800 int maxIndex = size() - 1;
801 for (int i = 0; i <= maxIndex; i++) {
802 buf.append(String.valueOf(e.next()));
803 if (i < maxIndex)
804 buf.append(", ");
805 }
806 buf.append("]");
807 return buf.toString();
808 }
809
810
811 /**
812 * Compares the specified Object with this List for equality. Returns true
813 * if and only if the specified Object is also a List, both Lists have the
814 * same size, and all corresponding pairs of elements in the two Lists are
815 * <em>equal</em>. (Two elements <code>e1</code> and <code>e2</code> are
816 * <em>equal</em> if <code>(e1==null ? e2==null : e1.equals(e2))</code>.)
817 * In other words, two Lists are defined to be equal if they contain the
818 * same elements in the same order.
819 * <p>
820 * This implementation first checks if the specified object is this
821 * List. If so, it returns true; if not, it checks if the specified
822 * object is a List. If not, it returns false; if so, it iterates over
823 * both lists, comparing corresponding pairs of elements. If any
824 * comparison returns false, this method returns false. If either
825 * Iterator runs out of elements before before the other it returns false
826 * (as the Lists are of unequal length); otherwise it returns true when
827 * the iterations complete.
828 *
829 * @param o the Object to be compared for equality with this List.
830 * @return true if the specified Object is equal to this List.
831 */
832 public boolean equals(Object o) {
833 if (o == this)
834 return true;
835 if (!(o instanceof List))
836 return false;
837
838 List l2 = (List)(o);
839 if (size() != l2.size())
840 return false;
841
842 ListIterator e1 = listIterator();
843 ListIterator e2 = l2.listIterator();
844 while(e1.hasNext()) {
845 Object o1 = e1.next();
846 Object o2 = e2.next();
847 if (!(o1==null ? o2==null : o1.equals(o2)))
848 return false;
849 }
850 return true;
851 }
852
853 /**
854 * Returns the hash code value for this List.
855 * <p>
856 * This implementation uses exactly the code that is used to define
857 * the List hash function in the documentation for List.hashCode.
858 */
859 public int hashCode() {
860 int hashCode = 1;
861 Iterator i = iterator();
862 while (i.hasNext()) {
863 Object obj = i.next();
864 hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
865 }
866 return hashCode;
867 }
868
869 /**
870 * Returns an Iterator over the elements contained in this collection.
871 * The iterator provides a snapshot of the state of the list
872 * when the iterator was constructed. No synchronization is
873 * needed while traversing the iterator. The iterator does
874 * <em>NOT</em> support the <code>remove</code> method.
875 */
876 public Iterator iterator() {
877 return new COWIterator(array(), 0);
878 }
879
880 /**
881 * Returns an Iterator of the elements in this List (in proper sequence).
882 * The iterator provides a snapshot of the state of the list
883 * when the iterator was constructed. No synchronization is
884 * needed while traversing the iterator. The iterator does
885 * <em>NOT</em> support the <code>remove</code>, <code>set</code>,
886 * or <code>add</code> methods.
887 *
888 */
889
890 public ListIterator listIterator() {
891 return new COWIterator(array(), 0);
892 }
893
894 /**
895 * Returns a ListIterator of the elements in this List (in proper
896 * sequence), starting at the specified position in the List. The
897 * specified index indicates the first element that would be returned by
898 * an initial call to nextElement. An initial call to previousElement
899 * would return the element with the specified index minus one.
900 * The ListIterator returned by this implementation will throw
901 * an UnsupportedOperationException in its remove, set and
902 * add methods.
903 *
904 * @param index index of first element to be returned from the
905 * ListIterator (by a call to getNext).
906 * @exception IndexOutOfBoundsException index is out of range
907 * (index &lt; 0 || index &gt; size()).
908 */
909 public ListIterator listIterator(final int index) {
910 Object[] elementData = array();
911 int len = elementData.length;
912 if (index<0 || index>len)
913 throw new IndexOutOfBoundsException("Index: "+index);
914
915 return new COWIterator(array(), index);
916 }
917
918 protected static class COWIterator implements ListIterator {
919
920 /** Snapshot of the array **/
921 protected final Object[] array;
922
923 /**
924 * Index of element to be returned by subsequent call to next.
925 */
926 protected int cursor;
927
928 protected COWIterator(Object[] elementArray, int initialCursor) {
929 array = elementArray;
930 cursor = initialCursor;
931 }
932
933 public boolean hasNext() {
934 return cursor < array.length;
935 }
936
937 public boolean hasPrevious() {
938 return cursor > 0;
939 }
940
941 public Object next() {
942 try {
943 return array[cursor++];
944 }
945 catch (IndexOutOfBoundsException ex) {
946 throw new NoSuchElementException();
947 }
948 }
949
950 public Object previous() {
951 try {
952 return array[--cursor];
953 } catch(IndexOutOfBoundsException e) {
954 throw new NoSuchElementException();
955 }
956 }
957
958 public int nextIndex() {
959 return cursor;
960 }
961
962 public int previousIndex() {
963 return cursor-1;
964 }
965
966 /**
967 * Not supported. Always throws UnsupportedOperationException.
968 * @exception UnsupportedOperationException remove is not supported
969 * by this Iterator.
970 */
971
972 public void remove() {
973 throw new UnsupportedOperationException();
974 }
975
976 /**
977 * Not supported. Always throws UnsupportedOperationException.
978 * @exception UnsupportedOperationException set is not supported
979 * by this Iterator.
980 */
981 public void set(Object o) {
982 throw new UnsupportedOperationException();
983 }
984
985 /**
986 * Not supported. Always throws UnsupportedOperationException.
987 * @exception UnsupportedOperationException add is not supported
988 * by this Iterator.
989 */
990 public void add(Object o) {
991 throw new UnsupportedOperationException();
992 }
993 }
994
995
996 /**
997 * Returns a view of the portion of this List between fromIndex,
998 * inclusive, and toIndex, exclusive. The returned List is backed by this
999 * List, so changes in the returned List are reflected in this List, and
1000 * vice-versa. While mutative operations are supported, they are
1001 * probably not very useful for CopyOnWriteArrays.
1002 * </p>
1003 * The semantics of the List returned by this method become undefined if
1004 * the backing list (i.e., this List) is <i>structurally modified</i> in
1005 * any way other than via the returned List. (Structural modifications are
1006 * those that change the size of the List, or otherwise perturb it in such
1007 * a fashion that iterations in progress may yield incorrect results.)
1008 *
1009 * @param fromIndex low endpoint (inclusive) of the subList.
1010 * @param toKey high endpoint (exclusive) of the subList.
1011 * @return a view of the specified range within this List.
1012 * @exception IndexOutOfBoundsException Illegal endpoint index value
1013 * (fromIndex &lt; 0 || toIndex &gt; size || fromIndex &gt; toIndex).
1014 */
1015 public synchronized List subList(int fromIndex, int toIndex) {
1016 // synchronized since sublist ctor depends on it.
1017 int len = array_.length;
1018 if (fromIndex<0 || toIndex>len || fromIndex>toIndex)
1019 throw new IndexOutOfBoundsException();
1020 return new COWSubList(this, fromIndex, toIndex);
1021 }
1022
1023 protected static class COWSubList extends AbstractList {
1024
1025 /*
1026 This is currently a bit sleazy. The class
1027 extends AbstractList merely for convenience,
1028 to avoid having to define addAll, etc. This
1029 doesn't hurt, but is stupid and wasteful.
1030 This class does not need or use modCount mechanics
1031 in AbstractList, but does need to check for
1032 concurrent modification using similar mechanics.
1033 On each operation, the array that we expect
1034 the backing list to use is checked and updated.
1035 Since we do this for all of the base operations
1036 invoked by those defined in AbstractList, all is well.
1037
1038 It's not clear whether this is worth cleaning up.
1039 The kinds of list operations inherited from
1040 AbstractList are are already so slow on COW sublists
1041 that adding a bit more space/time doesn't seem
1042 even noticeable.
1043 */
1044
1045 protected final CopyOnWriteArrayList l;
1046 protected final int offset;
1047 protected int size;
1048 protected Object[] expectedArray;
1049
1050 protected COWSubList(CopyOnWriteArrayList list,
1051 int fromIndex, int toIndex) {
1052 l = list;
1053 expectedArray = l.array();
1054 offset = fromIndex;
1055 size = toIndex - fromIndex;
1056 }
1057
1058 // only call this holding l's lock
1059 protected void checkForComodification() {
1060 if (l.array_ != expectedArray)
1061 throw new ConcurrentModificationException();
1062 }
1063
1064 // only call this holding l's lock
1065 protected void rangeCheck(int index) {
1066 if (index<0 || index>=size)
1067 throw new IndexOutOfBoundsException("Index: "+index+
1068 ",Size: "+size);
1069 }
1070
1071
1072 public Object set(int index, Object element) {
1073 synchronized(l) {
1074 rangeCheck(index);
1075 checkForComodification();
1076 Object x = l.set(index+offset, element);
1077 expectedArray = l.array_;
1078 return x;
1079 }
1080 }
1081
1082 public Object get(int index) {
1083 synchronized(l) {
1084 rangeCheck(index);
1085 checkForComodification();
1086 return l.get(index+offset);
1087 }
1088 }
1089
1090 public int size() {
1091 synchronized(l) {
1092 checkForComodification();
1093 return size;
1094 }
1095 }
1096
1097 public void add(int index, Object element) {
1098 synchronized(l) {
1099 checkForComodification();
1100 if (index<0 || index>size)
1101 throw new IndexOutOfBoundsException();
1102 l.add(index+offset, element);
1103 expectedArray = l.array_;
1104 size++;
1105 }
1106 }
1107
1108 public Object remove(int index) {
1109 synchronized(l) {
1110 rangeCheck(index);
1111 checkForComodification();
1112 Object result = l.remove(index+offset);
1113 expectedArray = l.array_;
1114 size--;
1115 return result;
1116 }
1117 }
1118
1119 public Iterator iterator() {
1120 synchronized(l) {
1121 checkForComodification();
1122 return new COWSubListIterator(0);
1123 }
1124 }
1125
1126 public ListIterator listIterator(final int index) {
1127 synchronized(l) {
1128 checkForComodification();
1129 if (index<0 || index>size)
1130 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
1131 return new COWSubListIterator(index);
1132 }
1133 }
1134
1135 protected class COWSubListIterator implements ListIterator {
1136 protected final ListIterator i;
1137 protected final int index;
1138 protected COWSubListIterator(int index) {
1139 this.index = index;
1140 i = l.listIterator(index+offset);
1141 }
1142
1143 public boolean hasNext() {
1144 return nextIndex() < size;
1145 }
1146
1147 public Object next() {
1148 if (hasNext())
1149 return i.next();
1150 else
1151 throw new NoSuchElementException();
1152 }
1153
1154 public boolean hasPrevious() {
1155 return previousIndex() >= 0;
1156 }
1157
1158 public Object previous() {
1159 if (hasPrevious())
1160 return i.previous();
1161 else
1162 throw new NoSuchElementException();
1163 }
1164
1165 public int nextIndex() {
1166 return i.nextIndex() - offset;
1167 }
1168
1169 public int previousIndex() {
1170 return i.previousIndex() - offset;
1171 }
1172
1173 public void remove() {
1174 throw new UnsupportedOperationException();
1175 }
1176
1177 public void set(Object o) {
1178 throw new UnsupportedOperationException();
1179 }
1180
1181 public void add(Object o) {
1182 throw new UnsupportedOperationException();
1183 }
1184 }
1185
1186
1187 public List subList(int fromIndex, int toIndex) {
1188 synchronized(l) {
1189 checkForComodification();
1190 if (fromIndex<0 || toIndex>size)
1191 throw new IndexOutOfBoundsException();
1192 return new COWSubList(l, fromIndex+offset, toIndex+offset);
1193 }
1194 }
1195
1196
1197 }
1198
1199 }