0001: package prefuse.util.collections;
0002:
0003: /*
0004: * Written by Doug Lea with assistance from members of JCP JSR-166
0005: * Expert Group. Adapted and released, under explicit permission,
0006: * from JDK ArrayList.java which carries the following copyright:
0007: *
0008: * Copyright 1997 by Sun Microsystems, Inc.,
0009: * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
0010: * All rights reserved.
0011: *
0012: * This software is the confidential and proprietary information
0013: * of Sun Microsystems, Inc. ("Confidential Information"). You
0014: * shall not disclose such Confidential Information and shall use
0015: * it only in accordance with the terms of the license agreement
0016: * you entered into with Sun.
0017: */
0018:
0019: import java.util.AbstractList;
0020: import java.util.Collection;
0021: import java.util.ConcurrentModificationException;
0022: import java.util.Iterator;
0023: import java.util.List;
0024: import java.util.ListIterator;
0025: import java.util.NoSuchElementException;
0026: import java.util.RandomAccess;
0027:
0028: /**
0029: * A thread-safe variant of {@link java.util.ArrayList} in which all mutative
0030: * operations (<tt>add</tt>, <tt>set</tt>, and so on) are implemented by
0031: * making a fresh copy of the underlying array.
0032: *
0033: * <p> This is ordinarily too costly, but may be <em>more</em> efficient
0034: * than alternatives when traversal operations vastly outnumber
0035: * mutations, and is useful when you cannot or don't want to
0036: * synchronize traversals, yet need to preclude interference among
0037: * concurrent threads. The "snapshot" style iterator method uses a
0038: * reference to the state of the array at the point that the iterator
0039: * was created. This array never changes during the lifetime of the
0040: * iterator, so interference is impossible and the iterator is
0041: * guaranteed not to throw <tt>ConcurrentModificationException</tt>.
0042: * The iterator will not reflect additions, removals, or changes to
0043: * the list since the iterator was created. Element-changing
0044: * operations on iterators themselves (<tt>remove</tt>, <tt>set</tt>, and
0045: * <tt>add</tt>) are not supported. These methods throw
0046: * <tt>UnsupportedOperationException</tt>.
0047: *
0048: * <p>All elements are permitted, including <tt>null</tt>.
0049: *
0050: * <p>This class is a member of the
0051: * <a href="{@docRoot}/../guide/collections/index.html">
0052: * Java Collections Framework</a>.
0053: *
0054: * @since 1.5
0055: * @author Doug Lea
0056: */
0057: public class CopyOnWriteArrayList implements List, RandomAccess,
0058: Cloneable, java.io.Serializable {
0059: private static final long serialVersionUID = 8673264195747942595L;
0060:
0061: /** The array, accessed only via getArray/setArray. */
0062: private volatile transient Object[] array;
0063:
0064: /**
0065: * This has been made public to support more efficient iteration.
0066: * <strong>DO NOT MODIFY this array upon getting it</strong>.
0067: * Otherwise you risk wreaking havoc on your list. In fact, if you are
0068: * not the author of this comment, you probably shouldn't use it at all.
0069: * @return this lists internal array
0070: */
0071: public Object[] getArray() {
0072: return array;
0073: }
0074:
0075: void setArray(Object[] a) {
0076: array = a;
0077: }
0078:
0079: /**
0080: * Creates an empty list.
0081: */
0082: public CopyOnWriteArrayList() {
0083: setArray(new Object[0]);
0084: }
0085:
0086: /**
0087: * Creates a list containing the elements of the specified
0088: * collection, in the order they are returned by the collection's
0089: * iterator.
0090: *
0091: * @param c the collection of initially held elements
0092: * @throws NullPointerException if the specified collection is null
0093: */
0094: public CopyOnWriteArrayList(Collection c) {
0095: Object[] elements = new Object[c.size()];
0096: int size = 0;
0097: for (Iterator itr = c.iterator(); itr.hasNext();) {
0098: Object e = itr.next();
0099: elements[size++] = e;
0100: }
0101: setArray(elements);
0102: }
0103:
0104: /**
0105: * Creates a list holding a copy of the given array.
0106: *
0107: * @param toCopyIn the array (a copy of this array is used as the
0108: * internal array)
0109: * @throws NullPointerException if the specified array is null
0110: */
0111: public CopyOnWriteArrayList(Object[] toCopyIn) {
0112: copyIn(toCopyIn, 0, toCopyIn.length);
0113: }
0114:
0115: /**
0116: * Replaces the held array with a copy of the <tt>n</tt> elements
0117: * of the provided array, starting at position <tt>first</tt>. To
0118: * copy an entire array, call with arguments (array, 0,
0119: * array.length).
0120: * @param toCopyIn the array. A copy of the indicated elements of
0121: * this array is used as the internal array.
0122: * @param first The index of first position of the array to
0123: * start copying from.
0124: * @param n the number of elements to copy. This will be the new size of
0125: * the list.
0126: */
0127: private void copyIn(Object[] toCopyIn, int first, int n) {
0128: int limit = first + n;
0129: if (limit > toCopyIn.length)
0130: throw new IndexOutOfBoundsException();
0131: Object[] newElements = copyOfRange(toCopyIn, first, limit,
0132: Object[].class);
0133: synchronized (this ) {
0134: setArray(newElements);
0135: }
0136: }
0137:
0138: /**
0139: * Returns the number of elements in this list.
0140: *
0141: * @return the number of elements in this list
0142: */
0143: public int size() {
0144: return getArray().length;
0145: }
0146:
0147: /**
0148: * Returns <tt>true</tt> if this list contains no elements.
0149: *
0150: * @return <tt>true</tt> if this list contains no elements
0151: */
0152: public boolean isEmpty() {
0153: return size() == 0;
0154: }
0155:
0156: /**
0157: * Test for equality, coping with nulls.
0158: */
0159: private static boolean eq(Object o1, Object o2) {
0160: return (o1 == null ? o2 == null : o1.equals(o2));
0161: }
0162:
0163: /**
0164: * static version of indexOf, to allow repeated calls without
0165: * needing to re-acquire array each time.
0166: * @param o element to search for
0167: * @param elements the array
0168: * @param index first index to search
0169: * @param fence one past last index to search
0170: * @return index of element, or -1 if absent
0171: */
0172: private static int indexOf(Object o, Object[] elements, int index,
0173: int fence) {
0174: if (o == null) {
0175: for (int i = index; i < fence; i++)
0176: if (elements[i] == null)
0177: return i;
0178: } else {
0179: for (int i = index; i < fence; i++)
0180: if (o.equals(elements[i]))
0181: return i;
0182: }
0183: return -1;
0184: }
0185:
0186: /**
0187: * static version of lastIndexOf.
0188: * @param o element to search for
0189: * @param elements the array
0190: * @param index first index to search
0191: * @return index of element, or -1 if absent
0192: */
0193: private static int lastIndexOf(Object o, Object[] elements,
0194: int index) {
0195: if (o == null) {
0196: for (int i = index; i >= 0; i--)
0197: if (elements[i] == null)
0198: return i;
0199: } else {
0200: for (int i = index; i >= 0; i--)
0201: if (o.equals(elements[i]))
0202: return i;
0203: }
0204: return -1;
0205: }
0206:
0207: /**
0208: * Returns <tt>true</tt> if this list contains the specified element.
0209: * More formally, returns <tt>true</tt> if and only if this list contains
0210: * at least one element <tt>e</tt> such that
0211: * <tt>(o==null ? e==null : o.equals(e))</tt>.
0212: *
0213: * @param o element whose presence in this list is to be tested
0214: * @return <tt>true</tt> if this list contains the specified element
0215: */
0216: public boolean contains(Object o) {
0217: Object[] elements = getArray();
0218: return indexOf(o, elements, 0, elements.length) >= 0;
0219: }
0220:
0221: /**
0222: * {@inheritDoc}
0223: */
0224: public int indexOf(Object o) {
0225: Object[] elements = getArray();
0226: return indexOf(o, elements, 0, elements.length);
0227: }
0228:
0229: /**
0230: * Returns the index of the first occurrence of the specified element in
0231: * this list, searching forwards from <tt>index</tt>, or returns -1 if
0232: * the element is not found.
0233: * More formally, returns the lowest index <tt>i</tt> such that
0234: * <tt>(i >= index && (e==null ? get(i)==null : e.equals(get(i))))</tt>,
0235: * or -1 if there is no such index.
0236: *
0237: * @param e element to search for
0238: * @param index index to start searching from
0239: * @return the index of the first occurrence of the element in
0240: * this list at position <tt>index</tt> or later in the list;
0241: * <tt>-1</tt> if the element is not found.
0242: * @throws IndexOutOfBoundsException if the specified index is negative
0243: */
0244: public int indexOf(Object e, int index) {
0245: Object[] elements = getArray();
0246: return indexOf(e, elements, index, elements.length);
0247: }
0248:
0249: /**
0250: * {@inheritDoc}
0251: */
0252: public int lastIndexOf(Object o) {
0253: Object[] elements = getArray();
0254: return lastIndexOf(o, elements, elements.length - 1);
0255: }
0256:
0257: /**
0258: * Returns the index of the last occurrence of the specified element in
0259: * this list, searching backwards from <tt>index</tt>, or returns -1 if
0260: * the element is not found.
0261: * More formally, returns the highest index <tt>i</tt> such that
0262: * <tt>(i <= index && (e==null ? get(i)==null : e.equals(get(i))))</tt>,
0263: * or -1 if there is no such index.
0264: *
0265: * @param e element to search for
0266: * @param index index to start searching backwards from
0267: * @return the index of the last occurrence of the element at position
0268: * less than or equal to <tt>index</tt> in this list;
0269: * -1 if the element is not found.
0270: * @throws IndexOutOfBoundsException if the specified index is greater
0271: * than or equal to the current size of this list
0272: */
0273: public int lastIndexOf(Object e, int index) {
0274: Object[] elements = getArray();
0275: return lastIndexOf(e, elements, index);
0276: }
0277:
0278: /**
0279: * Returns a shallow copy of this list. (The elements themselves
0280: * are not copied.)
0281: *
0282: * @return a clone of this list
0283: */
0284: public Object clone() {
0285: try {
0286: return super .clone();
0287: } catch (CloneNotSupportedException e) {
0288: // this shouldn't happen, since we are Cloneable
0289: throw new InternalError();
0290: }
0291: }
0292:
0293: /**
0294: * Returns an array containing all of the elements in this list
0295: * in proper sequence (from first to last element).
0296: *
0297: * <p>The returned array will be "safe" in that no references to it are
0298: * maintained by this list. (In other words, this method must allocate
0299: * a new array). The caller is thus free to modify the returned array.
0300: *
0301: * <p>This method acts as bridge between array-based and collection-based
0302: * APIs.
0303: *
0304: * @return an array containing all the elements in this list
0305: */
0306: public Object[] toArray() {
0307: Object[] elements = getArray();
0308: return copyOf(elements, elements.length);
0309: }
0310:
0311: /**
0312: * Returns an array containing all of the elements in this list in
0313: * proper sequence (from first to last element); the runtime type of
0314: * the returned array is that of the specified array. If the list fits
0315: * in the specified array, it is returned therein. Otherwise, a new
0316: * array is allocated with the runtime type of the specified array and
0317: * the size of this list.
0318: *
0319: * <p>If this list fits in the specified array with room to spare
0320: * (i.e., the array has more elements than this list), the element in
0321: * the array immediately following the end of the list is set to
0322: * <tt>null</tt>. (This is useful in determining the length of this
0323: * list <i>only</i> if the caller knows that this list does not contain
0324: * any null elements.)
0325: *
0326: * <p>Like the {@link #toArray()} method, this method acts as bridge between
0327: * array-based and collection-based APIs. Further, this method allows
0328: * precise control over the runtime type of the output array, and may,
0329: * under certain circumstances, be used to save allocation costs.
0330: *
0331: * <p>Suppose <tt>x</tt> is a list known to contain only strings.
0332: * The following code can be used to dump the list into a newly
0333: * allocated array of <tt>String</tt>:
0334: *
0335: * <pre>
0336: * String[] y = x.toArray(new String[0]);</pre>
0337: *
0338: * Note that <tt>toArray(new Object[0])</tt> is identical in function to
0339: * <tt>toArray()</tt>.
0340: *
0341: * @param a the array into which the elements of the list are to
0342: * be stored, if it is big enough; otherwise, a new array of the
0343: * same runtime type is allocated for this purpose.
0344: * @return an array containing all the elements in this list
0345: * @throws ArrayStoreException if the runtime type of the specified array
0346: * is not a supertype of the runtime type of every element in
0347: * this list
0348: * @throws NullPointerException if the specified array is null
0349: */
0350: public Object[] toArray(Object a[]) {
0351: Object[] elements = getArray();
0352: int len = elements.length;
0353: if (a.length < len)
0354: return copyOf(elements, len, a.getClass());
0355: else {
0356: System.arraycopy(elements, 0, a, 0, len);
0357: if (a.length > len)
0358: a[len] = null;
0359: return a;
0360: }
0361: }
0362:
0363: // Positional Access Operations
0364:
0365: /**
0366: * {@inheritDoc}
0367: *
0368: * @throws IndexOutOfBoundsException {@inheritDoc}
0369: */
0370: public Object get(int index) {
0371: return (getArray()[index]);
0372: }
0373:
0374: /**
0375: * Replaces the element at the specified position in this list with the
0376: * specified element.
0377: *
0378: * @throws IndexOutOfBoundsException {@inheritDoc}
0379: */
0380: public synchronized Object set(int index, Object element) {
0381: Object[] elements = getArray();
0382: int len = elements.length;
0383: Object oldValue = elements[index];
0384:
0385: if (oldValue != element) {
0386: Object[] newElements = copyOf(elements, len);
0387: newElements[index] = element;
0388: setArray(newElements);
0389: }
0390: return oldValue;
0391: }
0392:
0393: /**
0394: * Appends the specified element to the end of this list.
0395: *
0396: * @param e element to be appended to this list
0397: * @return <tt>true</tt> (as per the spec for {@link Collection#add})
0398: */
0399: public boolean add(Object e) {
0400: synchronized (this ) {
0401: Object[] elements = getArray();
0402: int len = elements.length;
0403: Object[] newElements = copyOf(elements, len + 1);
0404: newElements[len] = e;
0405: setArray(newElements);
0406: }
0407: return true;
0408: }
0409:
0410: /**
0411: * Inserts the specified element at the specified position in this
0412: * list. Shifts the element currently at that position (if any) and
0413: * any subsequent elements to the right (adds one to their indices).
0414: *
0415: * @throws IndexOutOfBoundsException {@inheritDoc}
0416: */
0417: public synchronized void add(int index, Object element) {
0418: Object[] elements = getArray();
0419: int len = elements.length;
0420: if (index > len || index < 0)
0421: throw new IndexOutOfBoundsException("Index: " + index
0422: + ", Size: " + len);
0423: Object[] newElements;
0424: int numMoved = len - index;
0425: if (numMoved == 0)
0426: newElements = copyOf(elements, len + 1);
0427: else {
0428: newElements = new Object[len + 1];
0429: System.arraycopy(elements, 0, newElements, 0, index);
0430: System.arraycopy(elements, index, newElements, index + 1,
0431: numMoved);
0432: }
0433: newElements[index] = element;
0434: setArray(newElements);
0435: }
0436:
0437: /**
0438: * Removes the element at the specified position in this list.
0439: * Shifts any subsequent elements to the left (subtracts one from their
0440: * indices). Returns the element that was removed from the list.
0441: *
0442: * @throws IndexOutOfBoundsException {@inheritDoc}
0443: */
0444: public synchronized Object remove(int index) {
0445: Object[] elements = getArray();
0446: int len = elements.length;
0447: Object oldValue = elements[index];
0448: int numMoved = len - index - 1;
0449: if (numMoved == 0)
0450: setArray(copyOf(elements, len - 1));
0451: else {
0452: Object[] newElements = new Object[len - 1];
0453: System.arraycopy(elements, 0, newElements, 0, index);
0454: System.arraycopy(elements, index + 1, newElements, index,
0455: numMoved);
0456: setArray(newElements);
0457: }
0458: return oldValue;
0459: }
0460:
0461: /**
0462: * Removes the first occurrence of the specified element from this list,
0463: * if it is present. If this list does not contain the element, it is
0464: * unchanged. More formally, removes the element with the lowest index
0465: * <tt>i</tt> such that
0466: * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
0467: * (if such an element exists). Returns <tt>true</tt> if this list
0468: * contained the specified element (or equivalently, if this list
0469: * changed as a result of the call).
0470: *
0471: * @param o element to be removed from this list, if present
0472: * @return <tt>true</tt> if this list contained the specified element
0473: */
0474: public synchronized boolean remove(Object o) {
0475: Object[] elements = getArray();
0476: int len = elements.length;
0477: if (len != 0) {
0478: // Copy while searching for element to remove
0479: // This wins in the normal case of element being present
0480: int newlen = len - 1;
0481: Object[] newElements = new Object[newlen];
0482:
0483: for (int i = 0; i < newlen; ++i) {
0484: if (eq(o, elements[i])) {
0485: // found one; copy remaining and exit
0486: for (int k = i + 1; k < len; ++k)
0487: newElements[k - 1] = elements[k];
0488: setArray(newElements);
0489: return true;
0490: } else
0491: newElements[i] = elements[i];
0492: }
0493:
0494: // special handling for last cell
0495: if (eq(o, elements[newlen])) {
0496: setArray(newElements);
0497: return true;
0498: }
0499: }
0500: return false;
0501: }
0502:
0503: /**
0504: * Removes from this list all of the elements whose index is between
0505: * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
0506: * Shifts any succeeding elements to the left (reduces their index).
0507: * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
0508: * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
0509: *
0510: * @param fromIndex index of first element to be removed
0511: * @param toIndex index after last element to be removed
0512: * @throws IndexOutOfBoundsException if fromIndex or toIndex out of
0513: * range (fromIndex < 0 || fromIndex >= size() || toIndex
0514: * > size() || toIndex < fromIndex)
0515: */
0516: private synchronized void removeRange(int fromIndex, int toIndex) {
0517: Object[] elements = getArray();
0518: int len = elements.length;
0519:
0520: if (fromIndex < 0 || fromIndex >= len || toIndex > len
0521: || toIndex < fromIndex)
0522: throw new IndexOutOfBoundsException();
0523: int newlen = len - (toIndex - fromIndex);
0524: int numMoved = len - toIndex;
0525: if (numMoved == 0)
0526: setArray(copyOf(elements, newlen));
0527: else {
0528: Object[] newElements = new Object[newlen];
0529: System.arraycopy(elements, 0, newElements, 0, fromIndex);
0530: System.arraycopy(elements, toIndex, newElements, fromIndex,
0531: numMoved);
0532: setArray(newElements);
0533: }
0534: }
0535:
0536: /**
0537: * Append the element if not present.
0538: *
0539: * @param e element to be added to this list, if absent
0540: * @return <tt>true</tt> if the element was added
0541: */
0542: public synchronized boolean addIfAbsent(Object e) {
0543: // Copy while checking if already present.
0544: // This wins in the most common case where it is not present
0545: Object[] elements = getArray();
0546: int len = elements.length;
0547: Object[] newElements = new Object[len + 1];
0548: for (int i = 0; i < len; ++i) {
0549: if (eq(e, elements[i]))
0550: return false; // exit, throwing away copy
0551: else
0552: newElements[i] = elements[i];
0553: }
0554: newElements[len] = e;
0555: setArray(newElements);
0556: return true;
0557: }
0558:
0559: /**
0560: * Returns <tt>true</tt> if this list contains all of the elements of the
0561: * specified collection.
0562: *
0563: * @param c collection to be checked for containment in this list
0564: * @return <tt>true</tt> if this list contains all of the elements of the
0565: * specified collection
0566: * @throws NullPointerException if the specified collection is null
0567: * @see #contains(Object)
0568: */
0569: public boolean containsAll(Collection c) {
0570: Object[] elements = getArray();
0571: int len = elements.length;
0572: for (Iterator itr = c.iterator(); itr.hasNext();) {
0573: Object e = itr.next();
0574: if (indexOf(e, elements, 0, len) < 0)
0575: return false;
0576: }
0577: return true;
0578: }
0579:
0580: /**
0581: * Removes from this list all of its elements that are contained in
0582: * the specified collection. This is a particularly expensive operation
0583: * in this class because of the need for an internal temporary array.
0584: *
0585: * @param c collection containing elements to be removed from this list
0586: * @return <tt>true</tt> if this list changed as a result of the call
0587: * @throws ClassCastException if the class of an element of this list
0588: * is incompatible with the specified collection (optional)
0589: * @throws NullPointerException if this list contains a null element and the
0590: * specified collection does not permit null elements (optional),
0591: * or if the specified collection is null
0592: * @see #remove(Object)
0593: */
0594: public synchronized boolean removeAll(Collection c) {
0595: Object[] elements = getArray();
0596: int len = elements.length;
0597: if (len != 0) {
0598: // temp array holds those elements we know we want to keep
0599: int newlen = 0;
0600: Object[] temp = new Object[len];
0601: for (int i = 0; i < len; ++i) {
0602: Object element = elements[i];
0603: if (!c.contains(element))
0604: temp[newlen++] = element;
0605: }
0606: if (newlen != len) {
0607: setArray(copyOfRange(temp, 0, newlen, Object[].class));
0608: return true;
0609: }
0610: }
0611: return false;
0612: }
0613:
0614: /**
0615: * Retains only the elements in this list that are contained in the
0616: * specified collection. In other words, removes from this list all of
0617: * its elements that are not contained in the specified collection.
0618: *
0619: * @param c collection containing elements to be retained in this list
0620: * @return <tt>true</tt> if this list changed as a result of the call
0621: * @throws ClassCastException if the class of an element of this list
0622: * is incompatible with the specified collection (optional)
0623: * @throws NullPointerException if this list contains a null element and the
0624: * specified collection does not permit null elements (optional),
0625: * or if the specified collection is null
0626: * @see #remove(Object)
0627: */
0628: public synchronized boolean retainAll(Collection c) {
0629: Object[] elements = getArray();
0630: int len = elements.length;
0631: if (len != 0) {
0632: // temp array holds those elements we know we want to keep
0633: int newlen = 0;
0634: Object[] temp = new Object[len];
0635: for (int i = 0; i < len; ++i) {
0636: Object element = elements[i];
0637: if (c.contains(element))
0638: temp[newlen++] = element;
0639: }
0640: if (newlen != len) {
0641: setArray(copyOfRange(temp, 0, newlen, Object[].class));
0642: return true;
0643: }
0644: }
0645: return false;
0646: }
0647:
0648: /**
0649: * Appends all of the elements in the specified collection that
0650: * are not already contained in this list, to the end of
0651: * this list, in the order that they are returned by the
0652: * specified collection's iterator.
0653: *
0654: * @param c collection containing elements to be added to this list
0655: * @return the number of elements added
0656: * @throws NullPointerException if the specified collection is null
0657: * @see #addIfAbsent(Object)
0658: */
0659: public int addAllAbsent(Collection c) {
0660: int numNew = c.size();
0661: if (numNew == 0)
0662: return 0;
0663: synchronized (this ) {
0664: Object[] elements = getArray();
0665: int len = elements.length;
0666:
0667: Object[] temp = new Object[numNew];
0668: int added = 0;
0669: for (Iterator itr = c.iterator(); itr.hasNext();) {
0670: Object e = itr.next();
0671: if (indexOf(e, elements, 0, len) < 0
0672: && indexOf(e, temp, 0, added) < 0)
0673: temp[added++] = e;
0674: }
0675: if (added != 0) {
0676: Object[] newElements = new Object[len + added];
0677: System.arraycopy(elements, 0, newElements, 0, len);
0678: System.arraycopy(temp, 0, newElements, len, added);
0679: setArray(newElements);
0680: }
0681: return added;
0682: }
0683: }
0684:
0685: /**
0686: * Removes all of the elements from this list.
0687: * The list will be empty after this call returns.
0688: */
0689: public synchronized void clear() {
0690: setArray(new Object[0]);
0691: }
0692:
0693: /**
0694: * Appends all of the elements in the specified collection to the end
0695: * of this list, in the order that they are returned by the specified
0696: * collection's iterator.
0697: *
0698: * @param c collection containing elements to be added to this list
0699: * @return <tt>true</tt> if this list changed as a result of the call
0700: * @throws NullPointerException if the specified collection is null
0701: * @see #add(Object)
0702: */
0703: public boolean addAll(Collection c) {
0704: int numNew = c.size();
0705: if (numNew == 0)
0706: return false;
0707: synchronized (this ) {
0708: Object[] elements = getArray();
0709: int len = elements.length;
0710: Object[] newElements = new Object[len + numNew];
0711: System.arraycopy(elements, 0, newElements, 0, len);
0712: for (Iterator itr = c.iterator(); itr.hasNext();) {
0713: Object e = itr.next();
0714: newElements[len++] = e;
0715: }
0716: setArray(newElements);
0717: return true;
0718: }
0719: }
0720:
0721: /**
0722: * Inserts all of the elements in the specified collection into this
0723: * list, starting at the specified position. Shifts the element
0724: * currently at that position (if any) and any subsequent elements to
0725: * the right (increases their indices). The new elements will appear
0726: * in this list in the order that they are returned by the
0727: * specified collection's iterator.
0728: *
0729: * @param index index at which to insert the first element
0730: * from the specified collection
0731: * @param c collection containing elements to be added to this list
0732: * @return <tt>true</tt> if this list changed as a result of the call
0733: * @throws IndexOutOfBoundsException {@inheritDoc}
0734: * @throws NullPointerException if the specified collection is null
0735: * @see #add(int,Object)
0736: */
0737: public boolean addAll(int index, Collection c) {
0738: int numNew = c.size();
0739: synchronized (this ) {
0740: Object[] elements = getArray();
0741: int len = elements.length;
0742: if (index > len || index < 0)
0743: throw new IndexOutOfBoundsException("Index: " + index
0744: + ", Size: " + len);
0745: if (numNew == 0)
0746: return false;
0747: int numMoved = len - index;
0748: Object[] newElements;
0749: if (numMoved == 0)
0750: newElements = copyOf(elements, len + numNew);
0751: else {
0752: newElements = new Object[len + numNew];
0753: System.arraycopy(elements, 0, newElements, 0, index);
0754: System.arraycopy(elements, index, newElements, index
0755: + numNew, numMoved);
0756: }
0757: for (Iterator itr = c.iterator(); itr.hasNext();) {
0758: Object e = itr.next();
0759: newElements[index++] = e;
0760: }
0761: setArray(newElements);
0762: return true;
0763: }
0764: }
0765:
0766: /**
0767: * Save the state of the list to a stream (i.e., serialize it).
0768: *
0769: * @serialData The length of the array backing the list is emitted
0770: * (int), followed by all of its elements (each an Object)
0771: * in the proper order.
0772: * @param s the stream
0773: */
0774: private void writeObject(java.io.ObjectOutputStream s)
0775: throws java.io.IOException {
0776:
0777: // Write out element count, and any hidden stuff
0778: s.defaultWriteObject();
0779:
0780: Object[] elements = getArray();
0781: int len = elements.length;
0782: // Write out array length
0783: s.writeInt(len);
0784:
0785: // Write out all elements in the proper order.
0786: for (int i = 0; i < len; i++)
0787: s.writeObject(elements[i]);
0788: }
0789:
0790: /**
0791: * Reconstitute the list from a stream (i.e., deserialize it).
0792: * @param s the stream
0793: */
0794: private void readObject(java.io.ObjectInputStream s)
0795: throws java.io.IOException, ClassNotFoundException {
0796:
0797: // Read in size, and any hidden stuff
0798: s.defaultReadObject();
0799:
0800: // Read in array length and allocate array
0801: int len = s.readInt();
0802: Object[] elements = new Object[len];
0803:
0804: // Read in all elements in the proper order.
0805: for (int i = 0; i < len; i++)
0806: elements[i] = s.readObject();
0807: setArray(elements);
0808:
0809: }
0810:
0811: /**
0812: * Returns a string representation of this list, containing
0813: * the String representation of each element.
0814: */
0815: public String toString() {
0816: Object[] elements = getArray();
0817: int maxIndex = elements.length - 1;
0818: StringBuffer buf = new StringBuffer();
0819: buf.append("[");
0820: for (int i = 0; i <= maxIndex; i++) {
0821: buf.append(String.valueOf(elements[i]));
0822: if (i < maxIndex)
0823: buf.append(", ");
0824: }
0825: buf.append("]");
0826: return buf.toString();
0827: }
0828:
0829: /**
0830: * Compares the specified object with this list for equality.
0831: * Returns true if and only if the specified object is also a {@link
0832: * List}, both lists have the same size, and all corresponding pairs
0833: * of elements in the two lists are <em>equal</em>. (Two elements
0834: * <tt>e1</tt> and <tt>e2</tt> are <em>equal</em> if <tt>(e1==null ?
0835: * e2==null : e1.equals(e2))</tt>.) In other words, two lists are
0836: * defined to be equal if they contain the same elements in the same
0837: * order.
0838: *
0839: * @param o the object to be compared for equality with this list
0840: * @return <tt>true</tt> if the specified object is equal to this list
0841: */
0842: public boolean equals(Object o) {
0843: if (o == this )
0844: return true;
0845: if (!(o instanceof List))
0846: return false;
0847:
0848: List l2 = (List) (o);
0849: if (size() != l2.size())
0850: return false;
0851:
0852: ListIterator e1 = listIterator();
0853: ListIterator e2 = l2.listIterator();
0854: while (e1.hasNext()) {
0855: if (!eq(e1.next(), e2.next()))
0856: return false;
0857: }
0858: return true;
0859: }
0860:
0861: /**
0862: * Returns the hash code value for this list.
0863: *
0864: * <p>This implementation uses the definition in {@link List#hashCode}.
0865: *
0866: * @return the hash code value for this list
0867: */
0868: public int hashCode() {
0869: int hashCode = 1;
0870: Object[] elements = getArray();
0871: int len = elements.length;
0872: for (int i = 0; i < len; ++i) {
0873: Object obj = elements[i];
0874: hashCode = 31 * hashCode
0875: + (obj == null ? 0 : obj.hashCode());
0876: }
0877: return hashCode;
0878: }
0879:
0880: /**
0881: * Returns an iterator over the elements in this list in proper sequence.
0882: *
0883: * <p>The returned iterator provides a snapshot of the state of the list
0884: * when the iterator was constructed. No synchronization is needed while
0885: * traversing the iterator. The iterator does <em>NOT</em> support the
0886: * <tt>remove</tt> method.
0887: *
0888: * @return an iterator over the elements in this list in proper sequence
0889: */
0890: public Iterator iterator() {
0891: return new COWIterator(getArray(), 0);
0892: }
0893:
0894: /**
0895: * {@inheritDoc}
0896: *
0897: * <p>The returned iterator provides a snapshot of the state of the list
0898: * when the iterator was constructed. No synchronization is needed while
0899: * traversing the iterator. The iterator does <em>NOT</em> support the
0900: * <tt>remove</tt>, <tt>set</tt> or <tt>add</tt> methods.
0901: */
0902: public ListIterator listIterator() {
0903: return new COWIterator(getArray(), 0);
0904: }
0905:
0906: /**
0907: * {@inheritDoc}
0908: *
0909: * <p>The list iterator returned by this implementation will throw an
0910: * <tt>UnsupportedOperationException</tt> in its <tt>remove</tt>,
0911: * <tt>set</tt> and <tt>add</tt> methods.
0912: *
0913: * @throws IndexOutOfBoundsException {@inheritDoc}
0914: */
0915: public ListIterator listIterator(final int index) {
0916: Object[] elements = getArray();
0917: int len = elements.length;
0918: if (index < 0 || index > len)
0919: throw new IndexOutOfBoundsException("Index: " + index);
0920:
0921: return new COWIterator(getArray(), index);
0922: }
0923:
0924: private static class COWIterator implements ListIterator {
0925: /** Snapshot of the array **/
0926: private final Object[] snapshot;
0927: /** Index of element to be returned by subsequent call to next. */
0928: private int cursor;
0929:
0930: private COWIterator(Object[] elements, int initialCursor) {
0931: cursor = initialCursor;
0932: snapshot = elements;
0933: }
0934:
0935: public boolean hasNext() {
0936: return cursor < snapshot.length;
0937: }
0938:
0939: public boolean hasPrevious() {
0940: return cursor > 0;
0941: }
0942:
0943: public Object next() {
0944: try {
0945: return (snapshot[cursor++]);
0946: } catch (IndexOutOfBoundsException ex) {
0947: throw new NoSuchElementException();
0948: }
0949: }
0950:
0951: public Object previous() {
0952: try {
0953: return (snapshot[--cursor]);
0954: } catch (IndexOutOfBoundsException e) {
0955: throw new NoSuchElementException();
0956: }
0957: }
0958:
0959: public int nextIndex() {
0960: return cursor;
0961: }
0962:
0963: public int previousIndex() {
0964: return cursor - 1;
0965: }
0966:
0967: /**
0968: * Not supported. Always throws UnsupportedOperationException.
0969: * @throws UnsupportedOperationException always; <tt>remove</tt>
0970: * is not supported by this iterator.
0971: */
0972: public void remove() {
0973: throw new UnsupportedOperationException();
0974: }
0975:
0976: /**
0977: * Not supported. Always throws UnsupportedOperationException.
0978: * @throws UnsupportedOperationException always; <tt>set</tt>
0979: * is not supported by this iterator.
0980: */
0981: public void set(Object e) {
0982: throw new UnsupportedOperationException();
0983: }
0984:
0985: /**
0986: * Not supported. Always throws UnsupportedOperationException.
0987: * @throws UnsupportedOperationException always; <tt>add</tt>
0988: * is not supported by this iterator.
0989: */
0990: public void add(Object e) {
0991: throw new UnsupportedOperationException();
0992: }
0993: }
0994:
0995: /**
0996: * Returns a view of the portion of this list between
0997: * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
0998: * The returned list is backed by this list, so changes in the
0999: * returned list are reflected in this list, and vice-versa.
1000: * While mutative operations are supported, they are probably not
1001: * very useful for CopyOnWriteArrayLists.
1002: *
1003: * <p>The semantics of the list returned by this method become
1004: * undefined if the backing list (i.e., this list) is
1005: * <i>structurally modified</i> in any way other than via the
1006: * returned list. (Structural modifications are those that change
1007: * the size of the list, or otherwise perturb it in such a fashion
1008: * that iterations in progress may yield incorrect results.)
1009: *
1010: * @param fromIndex low endpoint (inclusive) of the subList
1011: * @param toIndex high endpoint (exclusive) of the subList
1012: * @return a view of the specified range within this list
1013: * @throws IndexOutOfBoundsException {@inheritDoc}
1014: */
1015: public synchronized List subList(int fromIndex, int toIndex) {
1016: Object[] elements = getArray();
1017: int len = elements.length;
1018: if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
1019: throw new IndexOutOfBoundsException();
1020: return new COWSubList(this , fromIndex, toIndex);
1021: }
1022:
1023: /**
1024: * Sublist for CopyOnWriteArrayList.
1025: * This class extends AbstractList merely for convenience, to
1026: * avoid having to define addAll, etc. This doesn't hurt, but
1027: * is wasteful. This class does not need or use modCount
1028: * mechanics in AbstractList, but does need to check for
1029: * concurrent modification using similar mechanics. On each
1030: * operation, the array that we expect the backing list to use
1031: * is checked and updated. Since we do this for all of the
1032: * base operations invoked by those defined in AbstractList,
1033: * all is well. While inefficient, this is not worth
1034: * improving. The kinds of list operations inherited from
1035: * AbstractList are already so slow on COW sublists that
1036: * adding a bit more space/time doesn't seem even noticeable.
1037: */
1038: private static class COWSubList extends AbstractList {
1039: private final CopyOnWriteArrayList l;
1040: private final int offset;
1041: private int size;
1042: private Object[] expectedArray;
1043:
1044: // only call this holding l's lock
1045: private COWSubList(CopyOnWriteArrayList list, int fromIndex,
1046: int toIndex) {
1047: l = list;
1048: expectedArray = l.getArray();
1049: offset = fromIndex;
1050: size = toIndex - fromIndex;
1051: }
1052:
1053: // only call this holding l's lock
1054: private void checkForComodification() {
1055: if (l.getArray() != expectedArray)
1056: throw new ConcurrentModificationException();
1057: }
1058:
1059: // only call this holding l's lock
1060: private void rangeCheck(int index) {
1061: if (index < 0 || index >= size)
1062: throw new IndexOutOfBoundsException("Index: " + index
1063: + ",Size: " + size);
1064: }
1065:
1066: public Object set(int index, Object element) {
1067: synchronized (l) {
1068: rangeCheck(index);
1069: checkForComodification();
1070: Object x = l.set(index + offset, element);
1071: expectedArray = l.getArray();
1072: return x;
1073: }
1074: }
1075:
1076: public Object get(int index) {
1077: synchronized (l) {
1078: rangeCheck(index);
1079: checkForComodification();
1080: return l.get(index + offset);
1081: }
1082: }
1083:
1084: public int size() {
1085: synchronized (l) {
1086: checkForComodification();
1087: return size;
1088: }
1089: }
1090:
1091: public void add(int index, Object element) {
1092: synchronized (l) {
1093: checkForComodification();
1094: if (index < 0 || index > size)
1095: throw new IndexOutOfBoundsException();
1096: l.add(index + offset, element);
1097: expectedArray = l.getArray();
1098: size++;
1099: }
1100: }
1101:
1102: public void clear() {
1103: synchronized (l) {
1104: checkForComodification();
1105: l.removeRange(offset, offset + size);
1106: expectedArray = l.getArray();
1107: size = 0;
1108: }
1109: }
1110:
1111: public Object remove(int index) {
1112: synchronized (l) {
1113: rangeCheck(index);
1114: checkForComodification();
1115: Object result = l.remove(index + offset);
1116: expectedArray = l.getArray();
1117: size--;
1118: return result;
1119: }
1120: }
1121:
1122: public Iterator iterator() {
1123: synchronized (l) {
1124: checkForComodification();
1125: return new COWSubListIterator(l, 0, offset, size);
1126: }
1127: }
1128:
1129: public ListIterator listIterator(final int index) {
1130: synchronized (l) {
1131: checkForComodification();
1132: if (index < 0 || index > size)
1133: throw new IndexOutOfBoundsException("Index: "
1134: + index + ", Size: " + size);
1135: return new COWSubListIterator(l, index, offset, size);
1136: }
1137: }
1138:
1139: public List subList(int fromIndex, int toIndex) {
1140: synchronized (l) {
1141: checkForComodification();
1142: if (fromIndex < 0 || toIndex > size)
1143: throw new IndexOutOfBoundsException();
1144: return new COWSubList(l, fromIndex + offset, toIndex
1145: + offset);
1146: }
1147: }
1148:
1149: }
1150:
1151: private static class COWSubListIterator implements ListIterator {
1152: private final ListIterator i;
1153: private final int offset;
1154: private final int size;
1155:
1156: private COWSubListIterator(List l, int index, int offset,
1157: int size) {
1158: this .offset = offset;
1159: this .size = size;
1160: i = l.listIterator(index + offset);
1161: }
1162:
1163: public boolean hasNext() {
1164: return nextIndex() < size;
1165: }
1166:
1167: public Object next() {
1168: if (hasNext())
1169: return i.next();
1170: else
1171: throw new NoSuchElementException();
1172: }
1173:
1174: public boolean hasPrevious() {
1175: return previousIndex() >= 0;
1176: }
1177:
1178: public Object previous() {
1179: if (hasPrevious())
1180: return i.previous();
1181: else
1182: throw new NoSuchElementException();
1183: }
1184:
1185: public int nextIndex() {
1186: return i.nextIndex() - offset;
1187: }
1188:
1189: public int previousIndex() {
1190: return i.previousIndex() - offset;
1191: }
1192:
1193: public void remove() {
1194: throw new UnsupportedOperationException();
1195: }
1196:
1197: public void set(Object e) {
1198: throw new UnsupportedOperationException();
1199: }
1200:
1201: public void add(Object e) {
1202: throw new UnsupportedOperationException();
1203: }
1204: }
1205:
1206: // // Support for resetting lock while deserializing
1207: // private static final Unsafe unsafe = Unsafe.getUnsafe();
1208: // private static final long lockOffset;
1209: // static {
1210: // try {
1211: // lockOffset = unsafe.objectFieldOffset
1212: // (CopyOnWriteArrayList.class.getDeclaredField("lock"));
1213: // } catch (Exception ex) { throw new Error(ex); }
1214: // }
1215: // private void resetLock() {
1216: // unsafe.putObjectVolatile(this, lockOffset, new ReentrantLock());
1217: // }
1218: //
1219:
1220: // Temporary emulations of anticipated new j.u.Arrays functions
1221:
1222: private static Object[] copyOfRange(Object[] original, int from,
1223: int to, Class newType) {
1224: int newLength = to - from;
1225: if (newLength < 0)
1226: throw new IllegalArgumentException(from + " > " + to);
1227: Object[] copy = (Object[]) java.lang.reflect.Array.newInstance(
1228: newType.getComponentType(), newLength);
1229: System.arraycopy(original, from, copy, 0, Math.min(
1230: original.length - from, newLength));
1231: return copy;
1232: }
1233:
1234: private static Object[] copyOf(Object[] original, int newLength,
1235: Class newType) {
1236: Object[] copy = (Object[]) java.lang.reflect.Array.newInstance(
1237: newType.getComponentType(), newLength);
1238: System.arraycopy(original, 0, copy, 0, Math.min(
1239: original.length, newLength));
1240: return copy;
1241: }
1242:
1243: private static Object[] copyOf(Object[] original, int newLength) {
1244: return copyOf(original, newLength, original.getClass());
1245: }
1246: }
|