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