0001: /*
0002: * Copyright 2001-2005 The Apache Software Foundation
0003: *
0004: * Licensed under the Apache License, Version 2.0 (the "License");
0005: * you may not use this file except in compliance with the License.
0006: * You may obtain a copy of the License at
0007: *
0008: * http://www.apache.org/licenses/LICENSE-2.0
0009: *
0010: * Unless required by applicable law or agreed to in writing, software
0011: * distributed under the License is distributed on an "AS IS" BASIS,
0012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013: * See the License for the specific language governing permissions and
0014: * limitations under the License.
0015: */
0016: package org.apache.commons.collections;
0017:
0018: import java.util.ArrayList;
0019: import java.util.Collection;
0020: import java.util.ConcurrentModificationException;
0021: import java.util.Iterator;
0022: import java.util.List;
0023: import java.util.ListIterator;
0024:
0025: /**
0026: * <p>A customized implementation of <code>java.util.ArrayList</code> designed
0027: * to operate in a multithreaded environment where the large majority of
0028: * method calls are read-only, instead of structural changes. When operating
0029: * in "fast" mode, read calls are non-synchronized and write calls perform the
0030: * following steps:</p>
0031: * <ul>
0032: * <li>Clone the existing collection
0033: * <li>Perform the modification on the clone
0034: * <li>Replace the existing collection with the (modified) clone
0035: * </ul>
0036: * <p>When first created, objects of this class default to "slow" mode, where
0037: * all accesses of any type are synchronized but no cloning takes place. This
0038: * is appropriate for initially populating the collection, followed by a switch
0039: * to "fast" mode (by calling <code>setFast(true)</code>) after initialization
0040: * is complete.</p>
0041: *
0042: * <p><strong>NOTE</strong>: If you are creating and accessing an
0043: * <code>ArrayList</code> only within a single thread, you should use
0044: * <code>java.util.ArrayList</code> directly (with no synchronization), for
0045: * maximum performance.</p>
0046: *
0047: * <p><strong>NOTE</strong>: <i>This class is not cross-platform.
0048: * Using it may cause unexpected failures on some architectures.</i>
0049: * It suffers from the same problems as the double-checked locking idiom.
0050: * In particular, the instruction that clones the internal collection and the
0051: * instruction that sets the internal reference to the clone can be executed
0052: * or perceived out-of-order. This means that any read operation might fail
0053: * unexpectedly, as it may be reading the state of the internal collection
0054: * before the internal collection is fully formed.
0055: * For more information on the double-checked locking idiom, see the
0056: * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html">
0057: * Double-Checked Locking Idiom Is Broken Declaration</a>.</p>
0058: *
0059: * @since Commons Collections 1.0
0060: * @version $Revision: 178303 $ $Date: 2005-05-24 23:39:51 +0100 (Tue, 24 May 2005) $
0061: *
0062: * @author Craig R. McClanahan
0063: * @author Stephen Colebourne
0064: */
0065: public class FastArrayList extends ArrayList {
0066:
0067: // ----------------------------------------------------------- Constructors
0068:
0069: /**
0070: * Construct a an empty list.
0071: */
0072: public FastArrayList() {
0073:
0074: super ();
0075: this .list = new ArrayList();
0076:
0077: }
0078:
0079: /**
0080: * Construct an empty list with the specified capacity.
0081: *
0082: * @param capacity The initial capacity of the empty list
0083: */
0084: public FastArrayList(int capacity) {
0085:
0086: super ();
0087: this .list = new ArrayList(capacity);
0088:
0089: }
0090:
0091: /**
0092: * Construct a list containing the elements of the specified collection,
0093: * in the order they are returned by the collection's iterator.
0094: *
0095: * @param collection The collection whose elements initialize the contents
0096: * of this list
0097: */
0098: public FastArrayList(Collection collection) {
0099:
0100: super ();
0101: this .list = new ArrayList(collection);
0102:
0103: }
0104:
0105: // ----------------------------------------------------- Instance Variables
0106:
0107: /**
0108: * The underlying list we are managing.
0109: */
0110: protected ArrayList list = null;
0111:
0112: // ------------------------------------------------------------- Properties
0113:
0114: /**
0115: * Are we operating in "fast" mode?
0116: */
0117: protected boolean fast = false;
0118:
0119: /**
0120: * Returns true if this list is operating in fast mode.
0121: *
0122: * @return true if this list is operating in fast mode
0123: */
0124: public boolean getFast() {
0125: return (this .fast);
0126: }
0127:
0128: /**
0129: * Sets whether this list will operate in fast mode.
0130: *
0131: * @param fast true if the list should operate in fast mode
0132: */
0133: public void setFast(boolean fast) {
0134: this .fast = fast;
0135: }
0136:
0137: // --------------------------------------------------------- Public Methods
0138:
0139: /**
0140: * Appends the specified element to the end of this list.
0141: *
0142: * @param element The element to be appended
0143: */
0144: public boolean add(Object element) {
0145:
0146: if (fast) {
0147: synchronized (this ) {
0148: ArrayList temp = (ArrayList) list.clone();
0149: boolean result = temp.add(element);
0150: list = temp;
0151: return (result);
0152: }
0153: } else {
0154: synchronized (list) {
0155: return (list.add(element));
0156: }
0157: }
0158:
0159: }
0160:
0161: /**
0162: * Insert the specified element at the specified position in this list,
0163: * and shift all remaining elements up one position.
0164: *
0165: * @param index Index at which to insert this element
0166: * @param element The element to be inserted
0167: *
0168: * @exception IndexOutOfBoundsException if the index is out of range
0169: */
0170: public void add(int index, Object element) {
0171:
0172: if (fast) {
0173: synchronized (this ) {
0174: ArrayList temp = (ArrayList) list.clone();
0175: temp.add(index, element);
0176: list = temp;
0177: }
0178: } else {
0179: synchronized (list) {
0180: list.add(index, element);
0181: }
0182: }
0183:
0184: }
0185:
0186: /**
0187: * Append all of the elements in the specified Collection to the end
0188: * of this list, in the order that they are returned by the specified
0189: * Collection's Iterator.
0190: *
0191: * @param collection The collection to be appended
0192: */
0193: public boolean addAll(Collection collection) {
0194:
0195: if (fast) {
0196: synchronized (this ) {
0197: ArrayList temp = (ArrayList) list.clone();
0198: boolean result = temp.addAll(collection);
0199: list = temp;
0200: return (result);
0201: }
0202: } else {
0203: synchronized (list) {
0204: return (list.addAll(collection));
0205: }
0206: }
0207:
0208: }
0209:
0210: /**
0211: * Insert all of the elements in the specified Collection at the specified
0212: * position in this list, and shift any previous elements upwards as
0213: * needed.
0214: *
0215: * @param index Index at which insertion takes place
0216: * @param collection The collection to be added
0217: *
0218: * @exception IndexOutOfBoundsException if the index is out of range
0219: */
0220: public boolean addAll(int index, Collection collection) {
0221:
0222: if (fast) {
0223: synchronized (this ) {
0224: ArrayList temp = (ArrayList) list.clone();
0225: boolean result = temp.addAll(index, collection);
0226: list = temp;
0227: return (result);
0228: }
0229: } else {
0230: synchronized (list) {
0231: return (list.addAll(index, collection));
0232: }
0233: }
0234:
0235: }
0236:
0237: /**
0238: * Remove all of the elements from this list. The list will be empty
0239: * after this call returns.
0240: *
0241: * @exception UnsupportedOperationException if <code>clear()</code>
0242: * is not supported by this list
0243: */
0244: public void clear() {
0245:
0246: if (fast) {
0247: synchronized (this ) {
0248: ArrayList temp = (ArrayList) list.clone();
0249: temp.clear();
0250: list = temp;
0251: }
0252: } else {
0253: synchronized (list) {
0254: list.clear();
0255: }
0256: }
0257:
0258: }
0259:
0260: /**
0261: * Return a shallow copy of this <code>FastArrayList</code> instance.
0262: * The elements themselves are not copied.
0263: */
0264: public Object clone() {
0265:
0266: FastArrayList results = null;
0267: if (fast) {
0268: results = new FastArrayList(list);
0269: } else {
0270: synchronized (list) {
0271: results = new FastArrayList(list);
0272: }
0273: }
0274: results.setFast(getFast());
0275: return (results);
0276:
0277: }
0278:
0279: /**
0280: * Return <code>true</code> if this list contains the specified element.
0281: *
0282: * @param element The element to test for
0283: */
0284: public boolean contains(Object element) {
0285:
0286: if (fast) {
0287: return (list.contains(element));
0288: } else {
0289: synchronized (list) {
0290: return (list.contains(element));
0291: }
0292: }
0293:
0294: }
0295:
0296: /**
0297: * Return <code>true</code> if this list contains all of the elements
0298: * in the specified Collection.
0299: *
0300: * @param collection Collection whose elements are to be checked
0301: */
0302: public boolean containsAll(Collection collection) {
0303:
0304: if (fast) {
0305: return (list.containsAll(collection));
0306: } else {
0307: synchronized (list) {
0308: return (list.containsAll(collection));
0309: }
0310: }
0311:
0312: }
0313:
0314: /**
0315: * Increase the capacity of this <code>ArrayList</code> instance, if
0316: * necessary, to ensure that it can hold at least the number of elements
0317: * specified by the minimum capacity argument.
0318: *
0319: * @param capacity The new minimum capacity
0320: */
0321: public void ensureCapacity(int capacity) {
0322:
0323: if (fast) {
0324: synchronized (this ) {
0325: ArrayList temp = (ArrayList) list.clone();
0326: temp.ensureCapacity(capacity);
0327: list = temp;
0328: }
0329: } else {
0330: synchronized (list) {
0331: list.ensureCapacity(capacity);
0332: }
0333: }
0334:
0335: }
0336:
0337: /**
0338: * Compare the specified object with this list for equality. This
0339: * implementation uses exactly the code that is used to define the
0340: * list equals function in the documentation for the
0341: * <code>List.equals</code> method.
0342: *
0343: * @param o Object to be compared to this list
0344: */
0345: public boolean equals(Object o) {
0346:
0347: // Simple tests that require no synchronization
0348: if (o == this )
0349: return (true);
0350: else if (!(o instanceof List))
0351: return (false);
0352: List lo = (List) o;
0353:
0354: // Compare the sets of elements for equality
0355: if (fast) {
0356: ListIterator li1 = list.listIterator();
0357: ListIterator li2 = lo.listIterator();
0358: while (li1.hasNext() && li2.hasNext()) {
0359: Object o1 = li1.next();
0360: Object o2 = li2.next();
0361: if (!(o1 == null ? o2 == null : o1.equals(o2)))
0362: return (false);
0363: }
0364: return (!(li1.hasNext() || li2.hasNext()));
0365: } else {
0366: synchronized (list) {
0367: ListIterator li1 = list.listIterator();
0368: ListIterator li2 = lo.listIterator();
0369: while (li1.hasNext() && li2.hasNext()) {
0370: Object o1 = li1.next();
0371: Object o2 = li2.next();
0372: if (!(o1 == null ? o2 == null : o1.equals(o2)))
0373: return (false);
0374: }
0375: return (!(li1.hasNext() || li2.hasNext()));
0376: }
0377: }
0378:
0379: }
0380:
0381: /**
0382: * Return the element at the specified position in the list.
0383: *
0384: * @param index The index of the element to return
0385: *
0386: * @exception IndexOutOfBoundsException if the index is out of range
0387: */
0388: public Object get(int index) {
0389:
0390: if (fast) {
0391: return (list.get(index));
0392: } else {
0393: synchronized (list) {
0394: return (list.get(index));
0395: }
0396: }
0397:
0398: }
0399:
0400: /**
0401: * Return the hash code value for this list. This implementation uses
0402: * exactly the code that is used to define the list hash function in the
0403: * documentation for the <code>List.hashCode</code> method.
0404: */
0405: public int hashCode() {
0406:
0407: if (fast) {
0408: int hashCode = 1;
0409: java.util.Iterator i = list.iterator();
0410: while (i.hasNext()) {
0411: Object o = i.next();
0412: hashCode = 31 * hashCode
0413: + (o == null ? 0 : o.hashCode());
0414: }
0415: return (hashCode);
0416: } else {
0417: synchronized (list) {
0418: int hashCode = 1;
0419: java.util.Iterator i = list.iterator();
0420: while (i.hasNext()) {
0421: Object o = i.next();
0422: hashCode = 31 * hashCode
0423: + (o == null ? 0 : o.hashCode());
0424: }
0425: return (hashCode);
0426: }
0427: }
0428:
0429: }
0430:
0431: /**
0432: * Search for the first occurrence of the given argument, testing
0433: * for equality using the <code>equals()</code> method, and return
0434: * the corresponding index, or -1 if the object is not found.
0435: *
0436: * @param element The element to search for
0437: */
0438: public int indexOf(Object element) {
0439:
0440: if (fast) {
0441: return (list.indexOf(element));
0442: } else {
0443: synchronized (list) {
0444: return (list.indexOf(element));
0445: }
0446: }
0447:
0448: }
0449:
0450: /**
0451: * Test if this list has no elements.
0452: */
0453: public boolean isEmpty() {
0454:
0455: if (fast) {
0456: return (list.isEmpty());
0457: } else {
0458: synchronized (list) {
0459: return (list.isEmpty());
0460: }
0461: }
0462:
0463: }
0464:
0465: /**
0466: * Return an iterator over the elements in this list in proper sequence.
0467: * <p>
0468: * <b>Thread safety</b><br />
0469: * The iterator returned is thread-safe ONLY in FAST mode.
0470: * In slow mode there is no way to synchronize, or make the iterator thread-safe.
0471: * <p>
0472: * In fast mode iteration and modification may occur in parallel on different threads,
0473: * however there is a restriction. Modification must be EITHER via the Iterator
0474: * interface methods OR the List interface. If a mixture of modification
0475: * methods is used a ConcurrentModificationException is thrown from the iterator
0476: * modification method. If the List modification methods are used the changes are
0477: * NOT visible in the iterator (it shows the list contents at the time the iterator
0478: * was created).
0479: *
0480: * @return the iterator
0481: */
0482: public Iterator iterator() {
0483: if (fast) {
0484: return new ListIter(0);
0485: } else {
0486: return list.iterator();
0487: }
0488: }
0489:
0490: /**
0491: * Search for the last occurrence of the given argument, testing
0492: * for equality using the <code>equals()</code> method, and return
0493: * the corresponding index, or -1 if the object is not found.
0494: *
0495: * @param element The element to search for
0496: */
0497: public int lastIndexOf(Object element) {
0498:
0499: if (fast) {
0500: return (list.lastIndexOf(element));
0501: } else {
0502: synchronized (list) {
0503: return (list.lastIndexOf(element));
0504: }
0505: }
0506:
0507: }
0508:
0509: /**
0510: * Return an iterator of the elements of this list, in proper sequence.
0511: * <p>
0512: * <b>Thread safety</b><br />
0513: * The iterator returned is thread-safe ONLY in FAST mode.
0514: * In slow mode there is no way to synchronize, or make the iterator thread-safe.
0515: * <p>
0516: * In fast mode iteration and modification may occur in parallel on different threads,
0517: * however there is a restriction. Modification must be EITHER via the Iterator
0518: * interface methods OR the List interface. If a mixture of modification
0519: * methods is used a ConcurrentModificationException is thrown from the iterator
0520: * modification method. If the List modification methods are used the changes are
0521: * NOT visible in the iterator (it shows the list contents at the time the iterator
0522: * was created).
0523: *
0524: * @return the list iterator
0525: */
0526: public ListIterator listIterator() {
0527: if (fast) {
0528: return new ListIter(0);
0529: } else {
0530: return list.listIterator();
0531: }
0532: }
0533:
0534: /**
0535: * Return an iterator of the elements of this list, in proper sequence,
0536: * starting at the specified position.
0537: * <p>
0538: * <b>Thread safety</b><br />
0539: * The iterator returned is thread-safe ONLY in FAST mode.
0540: * In slow mode there is no way to synchronize, or make the iterator thread-safe.
0541: * <p>
0542: * In fast mode iteration and modification may occur in parallel on different threads,
0543: * however there is a restriction. Modification must be EITHER via the Iterator
0544: * interface methods OR the List interface. If a mixture of modification
0545: * methods is used a ConcurrentModificationException is thrown from the iterator
0546: * modification method. If the List modification methods are used the changes are
0547: * NOT visible in the iterator (it shows the list contents at the time the iterator
0548: * was created).
0549: *
0550: * @param index The starting position of the iterator to return
0551: * @return the list iterator
0552: * @exception IndexOutOfBoundsException if the index is out of range
0553: */
0554: public ListIterator listIterator(int index) {
0555: if (fast) {
0556: return new ListIter(index);
0557: } else {
0558: return list.listIterator(index);
0559: }
0560: }
0561:
0562: /**
0563: * Remove the element at the specified position in the list, and shift
0564: * any subsequent elements down one position.
0565: *
0566: * @param index Index of the element to be removed
0567: *
0568: * @exception IndexOutOfBoundsException if the index is out of range
0569: */
0570: public Object remove(int index) {
0571:
0572: if (fast) {
0573: synchronized (this ) {
0574: ArrayList temp = (ArrayList) list.clone();
0575: Object result = temp.remove(index);
0576: list = temp;
0577: return (result);
0578: }
0579: } else {
0580: synchronized (list) {
0581: return (list.remove(index));
0582: }
0583: }
0584:
0585: }
0586:
0587: /**
0588: * Remove the first occurrence of the specified element from the list,
0589: * and shift any subsequent elements down one position.
0590: *
0591: * @param element Element to be removed
0592: */
0593: public boolean remove(Object element) {
0594:
0595: if (fast) {
0596: synchronized (this ) {
0597: ArrayList temp = (ArrayList) list.clone();
0598: boolean result = temp.remove(element);
0599: list = temp;
0600: return (result);
0601: }
0602: } else {
0603: synchronized (list) {
0604: return (list.remove(element));
0605: }
0606: }
0607:
0608: }
0609:
0610: /**
0611: * Remove from this collection all of its elements that are contained
0612: * in the specified collection.
0613: *
0614: * @param collection Collection containing elements to be removed
0615: *
0616: * @exception UnsupportedOperationException if this optional operation
0617: * is not supported by this list
0618: */
0619: public boolean removeAll(Collection collection) {
0620:
0621: if (fast) {
0622: synchronized (this ) {
0623: ArrayList temp = (ArrayList) list.clone();
0624: boolean result = temp.removeAll(collection);
0625: list = temp;
0626: return (result);
0627: }
0628: } else {
0629: synchronized (list) {
0630: return (list.removeAll(collection));
0631: }
0632: }
0633:
0634: }
0635:
0636: /**
0637: * Remove from this collection all of its elements except those that are
0638: * contained in the specified collection.
0639: *
0640: * @param collection Collection containing elements to be retained
0641: *
0642: * @exception UnsupportedOperationException if this optional operation
0643: * is not supported by this list
0644: */
0645: public boolean retainAll(Collection collection) {
0646:
0647: if (fast) {
0648: synchronized (this ) {
0649: ArrayList temp = (ArrayList) list.clone();
0650: boolean result = temp.retainAll(collection);
0651: list = temp;
0652: return (result);
0653: }
0654: } else {
0655: synchronized (list) {
0656: return (list.retainAll(collection));
0657: }
0658: }
0659:
0660: }
0661:
0662: /**
0663: * Replace the element at the specified position in this list with
0664: * the specified element. Returns the previous object at that position.
0665: * <br><br>
0666: * <strong>IMPLEMENTATION NOTE</strong> - This operation is specifically
0667: * documented to not be a structural change, so it is safe to be performed
0668: * without cloning.
0669: *
0670: * @param index Index of the element to replace
0671: * @param element The new element to be stored
0672: *
0673: * @exception IndexOutOfBoundsException if the index is out of range
0674: */
0675: public Object set(int index, Object element) {
0676:
0677: if (fast) {
0678: return (list.set(index, element));
0679: } else {
0680: synchronized (list) {
0681: return (list.set(index, element));
0682: }
0683: }
0684:
0685: }
0686:
0687: /**
0688: * Return the number of elements in this list.
0689: */
0690: public int size() {
0691:
0692: if (fast) {
0693: return (list.size());
0694: } else {
0695: synchronized (list) {
0696: return (list.size());
0697: }
0698: }
0699:
0700: }
0701:
0702: /**
0703: * Return a view of the portion of this list between fromIndex
0704: * (inclusive) and toIndex (exclusive). The returned list is backed
0705: * by this list, so non-structural changes in the returned list are
0706: * reflected in this list. The returned list supports
0707: * all of the optional list operations supported by this list.
0708: *
0709: * @param fromIndex The starting index of the sublist view
0710: * @param toIndex The index after the end of the sublist view
0711: *
0712: * @exception IndexOutOfBoundsException if an index is out of range
0713: */
0714: public List subList(int fromIndex, int toIndex) {
0715: if (fast) {
0716: return new SubList(fromIndex, toIndex);
0717: } else {
0718: return list.subList(fromIndex, toIndex);
0719: }
0720: }
0721:
0722: /**
0723: * Return an array containing all of the elements in this list in the
0724: * correct order.
0725: */
0726: public Object[] toArray() {
0727:
0728: if (fast) {
0729: return (list.toArray());
0730: } else {
0731: synchronized (list) {
0732: return (list.toArray());
0733: }
0734: }
0735:
0736: }
0737:
0738: /**
0739: * Return an array containing all of the elements in this list in the
0740: * correct order. The runtime type of the returned array is that of
0741: * the specified array. If the list fits in the specified array, it is
0742: * returned therein. Otherwise, a new array is allocated with the
0743: * runtime type of the specified array, and the size of this list.
0744: *
0745: * @param array Array defining the element type of the returned list
0746: *
0747: * @exception ArrayStoreException if the runtime type of <code>array</code>
0748: * is not a supertype of the runtime type of every element in this list
0749: */
0750: public Object[] toArray(Object array[]) {
0751:
0752: if (fast) {
0753: return (list.toArray(array));
0754: } else {
0755: synchronized (list) {
0756: return (list.toArray(array));
0757: }
0758: }
0759:
0760: }
0761:
0762: /**
0763: * Return a String representation of this object.
0764: */
0765: public String toString() {
0766:
0767: StringBuffer sb = new StringBuffer("FastArrayList[");
0768: sb.append(list.toString());
0769: sb.append("]");
0770: return (sb.toString());
0771:
0772: }
0773:
0774: /**
0775: * Trim the capacity of this <code>ArrayList</code> instance to be the
0776: * list's current size. An application can use this operation to minimize
0777: * the storage of an <code>ArrayList</code> instance.
0778: */
0779: public void trimToSize() {
0780:
0781: if (fast) {
0782: synchronized (this ) {
0783: ArrayList temp = (ArrayList) list.clone();
0784: temp.trimToSize();
0785: list = temp;
0786: }
0787: } else {
0788: synchronized (list) {
0789: list.trimToSize();
0790: }
0791: }
0792:
0793: }
0794:
0795: private class SubList implements List {
0796:
0797: private int first;
0798: private int last;
0799: private List expected;
0800:
0801: public SubList(int first, int last) {
0802: this .first = first;
0803: this .last = last;
0804: this .expected = list;
0805: }
0806:
0807: private List get(List l) {
0808: if (list != expected) {
0809: throw new ConcurrentModificationException();
0810: }
0811: return l.subList(first, last);
0812: }
0813:
0814: public void clear() {
0815: if (fast) {
0816: synchronized (FastArrayList.this ) {
0817: ArrayList temp = (ArrayList) list.clone();
0818: get(temp).clear();
0819: last = first;
0820: list = temp;
0821: expected = temp;
0822: }
0823: } else {
0824: synchronized (list) {
0825: get(expected).clear();
0826: }
0827: }
0828: }
0829:
0830: public boolean remove(Object o) {
0831: if (fast) {
0832: synchronized (FastArrayList.this ) {
0833: ArrayList temp = (ArrayList) list.clone();
0834: boolean r = get(temp).remove(o);
0835: if (r)
0836: last--;
0837: list = temp;
0838: expected = temp;
0839: return r;
0840: }
0841: } else {
0842: synchronized (list) {
0843: return get(expected).remove(o);
0844: }
0845: }
0846: }
0847:
0848: public boolean removeAll(Collection o) {
0849: if (fast) {
0850: synchronized (FastArrayList.this ) {
0851: ArrayList temp = (ArrayList) list.clone();
0852: List sub = get(temp);
0853: boolean r = sub.removeAll(o);
0854: if (r)
0855: last = first + sub.size();
0856: list = temp;
0857: expected = temp;
0858: return r;
0859: }
0860: } else {
0861: synchronized (list) {
0862: return get(expected).removeAll(o);
0863: }
0864: }
0865: }
0866:
0867: public boolean retainAll(Collection o) {
0868: if (fast) {
0869: synchronized (FastArrayList.this ) {
0870: ArrayList temp = (ArrayList) list.clone();
0871: List sub = get(temp);
0872: boolean r = sub.retainAll(o);
0873: if (r)
0874: last = first + sub.size();
0875: list = temp;
0876: expected = temp;
0877: return r;
0878: }
0879: } else {
0880: synchronized (list) {
0881: return get(expected).retainAll(o);
0882: }
0883: }
0884: }
0885:
0886: public int size() {
0887: if (fast) {
0888: return get(expected).size();
0889: } else {
0890: synchronized (list) {
0891: return get(expected).size();
0892: }
0893: }
0894: }
0895:
0896: public boolean isEmpty() {
0897: if (fast) {
0898: return get(expected).isEmpty();
0899: } else {
0900: synchronized (list) {
0901: return get(expected).isEmpty();
0902: }
0903: }
0904: }
0905:
0906: public boolean contains(Object o) {
0907: if (fast) {
0908: return get(expected).contains(o);
0909: } else {
0910: synchronized (list) {
0911: return get(expected).contains(o);
0912: }
0913: }
0914: }
0915:
0916: public boolean containsAll(Collection o) {
0917: if (fast) {
0918: return get(expected).containsAll(o);
0919: } else {
0920: synchronized (list) {
0921: return get(expected).containsAll(o);
0922: }
0923: }
0924: }
0925:
0926: public Object[] toArray(Object[] o) {
0927: if (fast) {
0928: return get(expected).toArray(o);
0929: } else {
0930: synchronized (list) {
0931: return get(expected).toArray(o);
0932: }
0933: }
0934: }
0935:
0936: public Object[] toArray() {
0937: if (fast) {
0938: return get(expected).toArray();
0939: } else {
0940: synchronized (list) {
0941: return get(expected).toArray();
0942: }
0943: }
0944: }
0945:
0946: public boolean equals(Object o) {
0947: if (o == this )
0948: return true;
0949: if (fast) {
0950: return get(expected).equals(o);
0951: } else {
0952: synchronized (list) {
0953: return get(expected).equals(o);
0954: }
0955: }
0956: }
0957:
0958: public int hashCode() {
0959: if (fast) {
0960: return get(expected).hashCode();
0961: } else {
0962: synchronized (list) {
0963: return get(expected).hashCode();
0964: }
0965: }
0966: }
0967:
0968: public boolean add(Object o) {
0969: if (fast) {
0970: synchronized (FastArrayList.this ) {
0971: ArrayList temp = (ArrayList) list.clone();
0972: boolean r = get(temp).add(o);
0973: if (r)
0974: last++;
0975: list = temp;
0976: expected = temp;
0977: return r;
0978: }
0979: } else {
0980: synchronized (list) {
0981: return get(expected).add(o);
0982: }
0983: }
0984: }
0985:
0986: public boolean addAll(Collection o) {
0987: if (fast) {
0988: synchronized (FastArrayList.this ) {
0989: ArrayList temp = (ArrayList) list.clone();
0990: boolean r = get(temp).addAll(o);
0991: if (r)
0992: last += o.size();
0993: list = temp;
0994: expected = temp;
0995: return r;
0996: }
0997: } else {
0998: synchronized (list) {
0999: return get(expected).addAll(o);
1000: }
1001: }
1002: }
1003:
1004: public void add(int i, Object o) {
1005: if (fast) {
1006: synchronized (FastArrayList.this ) {
1007: ArrayList temp = (ArrayList) list.clone();
1008: get(temp).add(i, o);
1009: last++;
1010: list = temp;
1011: expected = temp;
1012: }
1013: } else {
1014: synchronized (list) {
1015: get(expected).add(i, o);
1016: }
1017: }
1018: }
1019:
1020: public boolean addAll(int i, Collection o) {
1021: if (fast) {
1022: synchronized (FastArrayList.this ) {
1023: ArrayList temp = (ArrayList) list.clone();
1024: boolean r = get(temp).addAll(i, o);
1025: list = temp;
1026: if (r)
1027: last += o.size();
1028: expected = temp;
1029: return r;
1030: }
1031: } else {
1032: synchronized (list) {
1033: return get(expected).addAll(i, o);
1034: }
1035: }
1036: }
1037:
1038: public Object remove(int i) {
1039: if (fast) {
1040: synchronized (FastArrayList.this ) {
1041: ArrayList temp = (ArrayList) list.clone();
1042: Object o = get(temp).remove(i);
1043: last--;
1044: list = temp;
1045: expected = temp;
1046: return o;
1047: }
1048: } else {
1049: synchronized (list) {
1050: return get(expected).remove(i);
1051: }
1052: }
1053: }
1054:
1055: public Object set(int i, Object a) {
1056: if (fast) {
1057: synchronized (FastArrayList.this ) {
1058: ArrayList temp = (ArrayList) list.clone();
1059: Object o = get(temp).set(i, a);
1060: list = temp;
1061: expected = temp;
1062: return o;
1063: }
1064: } else {
1065: synchronized (list) {
1066: return get(expected).set(i, a);
1067: }
1068: }
1069: }
1070:
1071: public Iterator iterator() {
1072: return new SubListIter(0);
1073: }
1074:
1075: public ListIterator listIterator() {
1076: return new SubListIter(0);
1077: }
1078:
1079: public ListIterator listIterator(int i) {
1080: return new SubListIter(i);
1081: }
1082:
1083: public Object get(int i) {
1084: if (fast) {
1085: return get(expected).get(i);
1086: } else {
1087: synchronized (list) {
1088: return get(expected).get(i);
1089: }
1090: }
1091: }
1092:
1093: public int indexOf(Object o) {
1094: if (fast) {
1095: return get(expected).indexOf(o);
1096: } else {
1097: synchronized (list) {
1098: return get(expected).indexOf(o);
1099: }
1100: }
1101: }
1102:
1103: public int lastIndexOf(Object o) {
1104: if (fast) {
1105: return get(expected).lastIndexOf(o);
1106: } else {
1107: synchronized (list) {
1108: return get(expected).lastIndexOf(o);
1109: }
1110: }
1111: }
1112:
1113: public List subList(int f, int l) {
1114: if (list != expected) {
1115: throw new ConcurrentModificationException();
1116: }
1117: return new SubList(first + f, f + l);
1118: }
1119:
1120: private class SubListIter implements ListIterator {
1121:
1122: private List expected;
1123: private ListIterator iter;
1124: private int lastReturnedIndex = -1;
1125:
1126: public SubListIter(int i) {
1127: this .expected = list;
1128: this .iter = SubList.this .get(expected).listIterator(i);
1129: }
1130:
1131: private void checkMod() {
1132: if (list != expected) {
1133: throw new ConcurrentModificationException();
1134: }
1135: }
1136:
1137: List get() {
1138: return SubList.this .get(expected);
1139: }
1140:
1141: public boolean hasNext() {
1142: checkMod();
1143: return iter.hasNext();
1144: }
1145:
1146: public Object next() {
1147: checkMod();
1148: lastReturnedIndex = iter.nextIndex();
1149: return iter.next();
1150: }
1151:
1152: public boolean hasPrevious() {
1153: checkMod();
1154: return iter.hasPrevious();
1155: }
1156:
1157: public Object previous() {
1158: checkMod();
1159: lastReturnedIndex = iter.previousIndex();
1160: return iter.previous();
1161: }
1162:
1163: public int previousIndex() {
1164: checkMod();
1165: return iter.previousIndex();
1166: }
1167:
1168: public int nextIndex() {
1169: checkMod();
1170: return iter.nextIndex();
1171: }
1172:
1173: public void remove() {
1174: checkMod();
1175: if (lastReturnedIndex < 0) {
1176: throw new IllegalStateException();
1177: }
1178: get().remove(lastReturnedIndex);
1179: last--;
1180: expected = list;
1181: iter = get().listIterator(lastReturnedIndex);
1182: lastReturnedIndex = -1;
1183: }
1184:
1185: public void set(Object o) {
1186: checkMod();
1187: if (lastReturnedIndex < 0) {
1188: throw new IllegalStateException();
1189: }
1190: get().set(lastReturnedIndex, o);
1191: expected = list;
1192: iter = get().listIterator(previousIndex() + 1);
1193: }
1194:
1195: public void add(Object o) {
1196: checkMod();
1197: int i = nextIndex();
1198: get().add(i, o);
1199: last++;
1200: expected = list;
1201: iter = get().listIterator(i + 1);
1202: lastReturnedIndex = -1;
1203: }
1204:
1205: }
1206:
1207: }
1208:
1209: private class ListIter implements ListIterator {
1210:
1211: private List expected;
1212: private ListIterator iter;
1213: private int lastReturnedIndex = -1;
1214:
1215: public ListIter(int i) {
1216: this .expected = list;
1217: this .iter = get().listIterator(i);
1218: }
1219:
1220: private void checkMod() {
1221: if (list != expected) {
1222: throw new ConcurrentModificationException();
1223: }
1224: }
1225:
1226: List get() {
1227: return expected;
1228: }
1229:
1230: public boolean hasNext() {
1231: return iter.hasNext();
1232: }
1233:
1234: public Object next() {
1235: lastReturnedIndex = iter.nextIndex();
1236: return iter.next();
1237: }
1238:
1239: public boolean hasPrevious() {
1240: return iter.hasPrevious();
1241: }
1242:
1243: public Object previous() {
1244: lastReturnedIndex = iter.previousIndex();
1245: return iter.previous();
1246: }
1247:
1248: public int previousIndex() {
1249: return iter.previousIndex();
1250: }
1251:
1252: public int nextIndex() {
1253: return iter.nextIndex();
1254: }
1255:
1256: public void remove() {
1257: checkMod();
1258: if (lastReturnedIndex < 0) {
1259: throw new IllegalStateException();
1260: }
1261: get().remove(lastReturnedIndex);
1262: expected = list;
1263: iter = get().listIterator(lastReturnedIndex);
1264: lastReturnedIndex = -1;
1265: }
1266:
1267: public void set(Object o) {
1268: checkMod();
1269: if (lastReturnedIndex < 0) {
1270: throw new IllegalStateException();
1271: }
1272: get().set(lastReturnedIndex, o);
1273: expected = list;
1274: iter = get().listIterator(previousIndex() + 1);
1275: }
1276:
1277: public void add(Object o) {
1278: checkMod();
1279: int i = nextIndex();
1280: get().add(i, o);
1281: expected = list;
1282: iter = get().listIterator(i + 1);
1283: lastReturnedIndex = -1;
1284: }
1285:
1286: }
1287: }
|