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