0001 /*
0002 * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved.
0003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004 *
0005 * This code is free software; you can redistribute it and/or modify it
0006 * under the terms of the GNU General Public License version 2 only, as
0007 * published by the Free Software Foundation. Sun designates this
0008 * particular file as subject to the "Classpath" exception as provided
0009 * by Sun in the LICENSE file that accompanied this code.
0010 *
0011 * This code is distributed in the hope that it will be useful, but WITHOUT
0012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014 * version 2 for more details (a copy is included in the LICENSE file that
0015 * accompanied this code).
0016 *
0017 * You should have received a copy of the GNU General Public License version
0018 * 2 along with this work; if not, write to the Free Software Foundation,
0019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020 *
0021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022 * CA 95054 USA or visit www.sun.com if you need additional information or
0023 * have any questions.
0024 */
0025
0026 package java.util;
0027
0028 /**
0029 * Resizable-array implementation of the <tt>List</tt> interface. Implements
0030 * all optional list operations, and permits all elements, including
0031 * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
0032 * this class provides methods to manipulate the size of the array that is
0033 * used internally to store the list. (This class is roughly equivalent to
0034 * <tt>Vector</tt>, except that it is unsynchronized.)
0035 *
0036 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
0037 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
0038 * time. The <tt>add</tt> operation runs in <i>amortized constant time</i>,
0039 * that is, adding n elements requires O(n) time. All of the other operations
0040 * run in linear time (roughly speaking). The constant factor is low compared
0041 * to that for the <tt>LinkedList</tt> implementation.
0042 *
0043 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is
0044 * the size of the array used to store the elements in the list. It is always
0045 * at least as large as the list size. As elements are added to an ArrayList,
0046 * its capacity grows automatically. The details of the growth policy are not
0047 * specified beyond the fact that adding an element has constant amortized
0048 * time cost.
0049 *
0050 * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
0051 * before adding a large number of elements using the <tt>ensureCapacity</tt>
0052 * operation. This may reduce the amount of incremental reallocation.
0053 *
0054 * <p><strong>Note that this implementation is not synchronized.</strong>
0055 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
0056 * and at least one of the threads modifies the list structurally, it
0057 * <i>must</i> be synchronized externally. (A structural modification is
0058 * any operation that adds or deletes one or more elements, or explicitly
0059 * resizes the backing array; merely setting the value of an element is not
0060 * a structural modification.) This is typically accomplished by
0061 * synchronizing on some object that naturally encapsulates the list.
0062 *
0063 * If no such object exists, the list should be "wrapped" using the
0064 * {@link Collections#synchronizedList Collections.synchronizedList}
0065 * method. This is best done at creation time, to prevent accidental
0066 * unsynchronized access to the list:<pre>
0067 * List list = Collections.synchronizedList(new ArrayList(...));</pre>
0068 *
0069 * <p><a name="fail-fast"/>
0070 * The iterators returned by this class's {@link #iterator() iterator} and
0071 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
0072 * if the list is structurally modified at any time after the iterator is
0073 * created, in any way except through the iterator's own
0074 * {@link ListIterator#remove() remove} or
0075 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
0076 * {@link ConcurrentModificationException}. Thus, in the face of
0077 * concurrent modification, the iterator fails quickly and cleanly, rather
0078 * than risking arbitrary, non-deterministic behavior at an undetermined
0079 * time in the future.
0080 *
0081 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
0082 * as it is, generally speaking, impossible to make any hard guarantees in the
0083 * presence of unsynchronized concurrent modification. Fail-fast iterators
0084 * throw {@code ConcurrentModificationException} on a best-effort basis.
0085 * Therefore, it would be wrong to write a program that depended on this
0086 * exception for its correctness: <i>the fail-fast behavior of iterators
0087 * should be used only to detect bugs.</i>
0088 *
0089 * <p>This class is a member of the
0090 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0091 * Java Collections Framework</a>.
0092 *
0093 * @author Josh Bloch
0094 * @author Neal Gafter
0095 * @version 1.65, 06/16/07
0096 * @see Collection
0097 * @see List
0098 * @see LinkedList
0099 * @see Vector
0100 * @since 1.2
0101 */
0102
0103 public class ArrayList<E> extends AbstractList<E> implements List<E>,
0104 RandomAccess, Cloneable, java.io.Serializable {
0105 private static final long serialVersionUID = 8683452581122892189L;
0106
0107 /**
0108 * The array buffer into which the elements of the ArrayList are stored.
0109 * The capacity of the ArrayList is the length of this array buffer.
0110 */
0111 private transient Object[] elementData;
0112
0113 /**
0114 * The size of the ArrayList (the number of elements it contains).
0115 *
0116 * @serial
0117 */
0118 private int size;
0119
0120 /**
0121 * Constructs an empty list with the specified initial capacity.
0122 *
0123 * @param initialCapacity the initial capacity of the list
0124 * @exception IllegalArgumentException if the specified initial capacity
0125 * is negative
0126 */
0127 public ArrayList(int initialCapacity) {
0128 super ();
0129 if (initialCapacity < 0)
0130 throw new IllegalArgumentException("Illegal Capacity: "
0131 + initialCapacity);
0132 this .elementData = new Object[initialCapacity];
0133 }
0134
0135 /**
0136 * Constructs an empty list with an initial capacity of ten.
0137 */
0138 public ArrayList() {
0139 this (10);
0140 }
0141
0142 /**
0143 * Constructs a list containing the elements of the specified
0144 * collection, in the order they are returned by the collection's
0145 * iterator.
0146 *
0147 * @param c the collection whose elements are to be placed into this list
0148 * @throws NullPointerException if the specified collection is null
0149 */
0150 public ArrayList(Collection<? extends E> c) {
0151 elementData = c.toArray();
0152 size = elementData.length;
0153 // c.toArray might (incorrectly) not return Object[] (see 6260652)
0154 if (elementData.getClass() != Object[].class)
0155 elementData = Arrays.copyOf(elementData, size,
0156 Object[].class);
0157 }
0158
0159 /**
0160 * Trims the capacity of this <tt>ArrayList</tt> instance to be the
0161 * list's current size. An application can use this operation to minimize
0162 * the storage of an <tt>ArrayList</tt> instance.
0163 */
0164 public void trimToSize() {
0165 modCount++;
0166 int oldCapacity = elementData.length;
0167 if (size < oldCapacity) {
0168 elementData = Arrays.copyOf(elementData, size);
0169 }
0170 }
0171
0172 /**
0173 * Increases the capacity of this <tt>ArrayList</tt> instance, if
0174 * necessary, to ensure that it can hold at least the number of elements
0175 * specified by the minimum capacity argument.
0176 *
0177 * @param minCapacity the desired minimum capacity
0178 */
0179 public void ensureCapacity(int minCapacity) {
0180 modCount++;
0181 int oldCapacity = elementData.length;
0182 if (minCapacity > oldCapacity) {
0183 Object oldData[] = elementData;
0184 int newCapacity = (oldCapacity * 3) / 2 + 1;
0185 if (newCapacity < minCapacity)
0186 newCapacity = minCapacity;
0187 // minCapacity is usually close to size, so this is a win:
0188 elementData = Arrays.copyOf(elementData, newCapacity);
0189 }
0190 }
0191
0192 /**
0193 * Returns the number of elements in this list.
0194 *
0195 * @return the number of elements in this list
0196 */
0197 public int size() {
0198 return size;
0199 }
0200
0201 /**
0202 * Returns <tt>true</tt> if this list contains no elements.
0203 *
0204 * @return <tt>true</tt> if this list contains no elements
0205 */
0206 public boolean isEmpty() {
0207 return size == 0;
0208 }
0209
0210 /**
0211 * Returns <tt>true</tt> if this list contains the specified element.
0212 * More formally, returns <tt>true</tt> if and only if this list contains
0213 * at least one element <tt>e</tt> such that
0214 * <tt>(o==null ? e==null : o.equals(e))</tt>.
0215 *
0216 * @param o element whose presence in this list is to be tested
0217 * @return <tt>true</tt> if this list contains the specified element
0218 */
0219 public boolean contains(Object o) {
0220 return indexOf(o) >= 0;
0221 }
0222
0223 /**
0224 * Returns the index of the first occurrence of the specified element
0225 * in this list, or -1 if this list does not contain the element.
0226 * More formally, returns the lowest index <tt>i</tt> such that
0227 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
0228 * or -1 if there is no such index.
0229 */
0230 public int indexOf(Object o) {
0231 if (o == null) {
0232 for (int i = 0; i < size; i++)
0233 if (elementData[i] == null)
0234 return i;
0235 } else {
0236 for (int i = 0; i < size; i++)
0237 if (o.equals(elementData[i]))
0238 return i;
0239 }
0240 return -1;
0241 }
0242
0243 /**
0244 * Returns the index of the last occurrence of the specified element
0245 * in this list, or -1 if this list does not contain the element.
0246 * More formally, returns the highest index <tt>i</tt> such that
0247 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
0248 * or -1 if there is no such index.
0249 */
0250 public int lastIndexOf(Object o) {
0251 if (o == null) {
0252 for (int i = size - 1; i >= 0; i--)
0253 if (elementData[i] == null)
0254 return i;
0255 } else {
0256 for (int i = size - 1; i >= 0; i--)
0257 if (o.equals(elementData[i]))
0258 return i;
0259 }
0260 return -1;
0261 }
0262
0263 /**
0264 * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
0265 * elements themselves are not copied.)
0266 *
0267 * @return a clone of this <tt>ArrayList</tt> instance
0268 */
0269 public Object clone() {
0270 try {
0271 @SuppressWarnings("unchecked")
0272 ArrayList<E> v = (ArrayList<E>) super .clone();
0273 v.elementData = Arrays.copyOf(elementData, size);
0274 v.modCount = 0;
0275 return v;
0276 } catch (CloneNotSupportedException e) {
0277 // this shouldn't happen, since we are Cloneable
0278 throw new InternalError();
0279 }
0280 }
0281
0282 /**
0283 * Returns an array containing all of the elements in this list
0284 * in proper sequence (from first to last element).
0285 *
0286 * <p>The returned array will be "safe" in that no references to it are
0287 * maintained by this list. (In other words, this method must allocate
0288 * a new array). The caller is thus free to modify the returned array.
0289 *
0290 * <p>This method acts as bridge between array-based and collection-based
0291 * APIs.
0292 *
0293 * @return an array containing all of the elements in this list in
0294 * proper sequence
0295 */
0296 public Object[] toArray() {
0297 return Arrays.copyOf(elementData, size);
0298 }
0299
0300 /**
0301 * Returns an array containing all of the elements in this list in proper
0302 * sequence (from first to last element); the runtime type of the returned
0303 * array is that of the specified array. If the list fits in the
0304 * specified array, it is returned therein. Otherwise, a new array is
0305 * allocated with the runtime type of the specified array and the size of
0306 * this list.
0307 *
0308 * <p>If the list fits in the specified array with room to spare
0309 * (i.e., the array has more elements than the list), the element in
0310 * the array immediately following the end of the collection is set to
0311 * <tt>null</tt>. (This is useful in determining the length of the
0312 * list <i>only</i> if the caller knows that the list does not contain
0313 * any null elements.)
0314 *
0315 * @param a the array into which the elements of the list are to
0316 * be stored, if it is big enough; otherwise, a new array of the
0317 * same runtime type is allocated for this purpose.
0318 * @return an array containing the elements of the list
0319 * @throws ArrayStoreException if the runtime type of the specified array
0320 * is not a supertype of the runtime type of every element in
0321 * this list
0322 * @throws NullPointerException if the specified array is null
0323 */
0324 @SuppressWarnings("unchecked")
0325 public <T> T[] toArray(T[] a) {
0326 if (a.length < size)
0327 // Make a new array of a's runtime type, but my contents:
0328 return (T[]) Arrays.copyOf(elementData, size, a.getClass());
0329 System.arraycopy(elementData, 0, a, 0, size);
0330 if (a.length > size)
0331 a[size] = null;
0332 return a;
0333 }
0334
0335 // Positional Access Operations
0336
0337 @SuppressWarnings("unchecked")
0338 E elementData(int index) {
0339 return (E) elementData[index];
0340 }
0341
0342 /**
0343 * Returns the element at the specified position in this list.
0344 *
0345 * @param index index of the element to return
0346 * @return the element at the specified position in this list
0347 * @throws IndexOutOfBoundsException {@inheritDoc}
0348 */
0349 public E get(int index) {
0350 rangeCheck(index);
0351
0352 return elementData(index);
0353 }
0354
0355 /**
0356 * Replaces the element at the specified position in this list with
0357 * the specified element.
0358 *
0359 * @param index index of the element to replace
0360 * @param element element to be stored at the specified position
0361 * @return the element previously at the specified position
0362 * @throws IndexOutOfBoundsException {@inheritDoc}
0363 */
0364 public E set(int index, E element) {
0365 rangeCheck(index);
0366
0367 E oldValue = elementData(index);
0368 elementData[index] = element;
0369 return oldValue;
0370 }
0371
0372 /**
0373 * Appends the specified element to the end of this list.
0374 *
0375 * @param e element to be appended to this list
0376 * @return <tt>true</tt> (as specified by {@link Collection#add})
0377 */
0378 public boolean add(E e) {
0379 ensureCapacity(size + 1); // Increments modCount!!
0380 elementData[size++] = e;
0381 return true;
0382 }
0383
0384 /**
0385 * Inserts the specified element at the specified position in this
0386 * list. Shifts the element currently at that position (if any) and
0387 * any subsequent elements to the right (adds one to their indices).
0388 *
0389 * @param index index at which the specified element is to be inserted
0390 * @param element element to be inserted
0391 * @throws IndexOutOfBoundsException {@inheritDoc}
0392 */
0393 public void add(int index, E element) {
0394 rangeCheckForAdd(index);
0395
0396 ensureCapacity(size + 1); // Increments modCount!!
0397 System.arraycopy(elementData, index, elementData, index + 1,
0398 size - index);
0399 elementData[index] = element;
0400 size++;
0401 }
0402
0403 /**
0404 * Removes the element at the specified position in this list.
0405 * Shifts any subsequent elements to the left (subtracts one from their
0406 * indices).
0407 *
0408 * @param index the index of the element to be removed
0409 * @return the element that was removed from the list
0410 * @throws IndexOutOfBoundsException {@inheritDoc}
0411 */
0412 public E remove(int index) {
0413 rangeCheck(index);
0414
0415 modCount++;
0416 E oldValue = elementData(index);
0417
0418 int numMoved = size - index - 1;
0419 if (numMoved > 0)
0420 System.arraycopy(elementData, index + 1, elementData,
0421 index, numMoved);
0422 elementData[--size] = null; // Let gc do its work
0423
0424 return oldValue;
0425 }
0426
0427 /**
0428 * Removes the first occurrence of the specified element from this list,
0429 * if it is present. If the list does not contain the element, it is
0430 * unchanged. More formally, removes the element with the lowest index
0431 * <tt>i</tt> such that
0432 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
0433 * (if such an element exists). Returns <tt>true</tt> if this list
0434 * contained the specified element (or equivalently, if this list
0435 * changed as a result of the call).
0436 *
0437 * @param o element to be removed from this list, if present
0438 * @return <tt>true</tt> if this list contained the specified element
0439 */
0440 public boolean remove(Object o) {
0441 if (o == null) {
0442 for (int index = 0; index < size; index++)
0443 if (elementData[index] == null) {
0444 fastRemove(index);
0445 return true;
0446 }
0447 } else {
0448 for (int index = 0; index < size; index++)
0449 if (o.equals(elementData[index])) {
0450 fastRemove(index);
0451 return true;
0452 }
0453 }
0454 return false;
0455 }
0456
0457 /*
0458 * Private remove method that skips bounds checking and does not
0459 * return the value removed.
0460 */
0461 private void fastRemove(int index) {
0462 modCount++;
0463 int numMoved = size - index - 1;
0464 if (numMoved > 0)
0465 System.arraycopy(elementData, index + 1, elementData,
0466 index, numMoved);
0467 elementData[--size] = null; // Let gc do its work
0468 }
0469
0470 /**
0471 * Removes all of the elements from this list. The list will
0472 * be empty after this call returns.
0473 */
0474 public void clear() {
0475 modCount++;
0476
0477 // Let gc do its work
0478 for (int i = 0; i < size; i++)
0479 elementData[i] = null;
0480
0481 size = 0;
0482 }
0483
0484 /**
0485 * Appends all of the elements in the specified collection to the end of
0486 * this list, in the order that they are returned by the
0487 * specified collection's Iterator. The behavior of this operation is
0488 * undefined if the specified collection is modified while the operation
0489 * is in progress. (This implies that the behavior of this call is
0490 * undefined if the specified collection is this list, and this
0491 * list is nonempty.)
0492 *
0493 * @param c collection containing elements to be added to this list
0494 * @return <tt>true</tt> if this list changed as a result of the call
0495 * @throws NullPointerException if the specified collection is null
0496 */
0497 public boolean addAll(Collection<? extends E> c) {
0498 Object[] a = c.toArray();
0499 int numNew = a.length;
0500 ensureCapacity(size + numNew); // Increments modCount
0501 System.arraycopy(a, 0, elementData, size, numNew);
0502 size += numNew;
0503 return numNew != 0;
0504 }
0505
0506 /**
0507 * Inserts all of the elements in the specified collection into this
0508 * list, starting at the specified position. Shifts the element
0509 * currently at that position (if any) and any subsequent elements to
0510 * the right (increases their indices). The new elements will appear
0511 * in the list in the order that they are returned by the
0512 * specified collection's iterator.
0513 *
0514 * @param index index at which to insert the first element from the
0515 * specified collection
0516 * @param c collection containing elements to be added to this list
0517 * @return <tt>true</tt> if this list changed as a result of the call
0518 * @throws IndexOutOfBoundsException {@inheritDoc}
0519 * @throws NullPointerException if the specified collection is null
0520 */
0521 public boolean addAll(int index, Collection<? extends E> c) {
0522 rangeCheckForAdd(index);
0523
0524 Object[] a = c.toArray();
0525 int numNew = a.length;
0526 ensureCapacity(size + numNew); // Increments modCount
0527
0528 int numMoved = size - index;
0529 if (numMoved > 0)
0530 System.arraycopy(elementData, index, elementData, index
0531 + numNew, numMoved);
0532
0533 System.arraycopy(a, 0, elementData, index, numNew);
0534 size += numNew;
0535 return numNew != 0;
0536 }
0537
0538 /**
0539 * Removes from this list all of the elements whose index is between
0540 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
0541 * Shifts any succeeding elements to the left (reduces their index).
0542 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
0543 * (If {@code toIndex==fromIndex}, this operation has no effect.)
0544 *
0545 * @throws IndexOutOfBoundsException if {@code fromIndex} or
0546 * {@code toIndex} is out of range
0547 * ({@code fromIndex < 0 ||
0548 * fromIndex >= size() ||
0549 * toIndex > size() ||
0550 * toIndex < fromIndex})
0551 */
0552 protected void removeRange(int fromIndex, int toIndex) {
0553 modCount++;
0554 int numMoved = size - toIndex;
0555 System.arraycopy(elementData, toIndex, elementData, fromIndex,
0556 numMoved);
0557
0558 // Let gc do its work
0559 int newSize = size - (toIndex - fromIndex);
0560 while (size != newSize)
0561 elementData[--size] = null;
0562 }
0563
0564 /**
0565 * Checks if the given index is in range. If not, throws an appropriate
0566 * runtime exception. This method does *not* check if the index is
0567 * negative: It is always used immediately prior to an array access,
0568 * which throws an ArrayIndexOutOfBoundsException if index is negative.
0569 */
0570 private void rangeCheck(int index) {
0571 if (index >= size)
0572 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
0573 }
0574
0575 /**
0576 * A version of rangeCheck used by add and addAll.
0577 */
0578 private void rangeCheckForAdd(int index) {
0579 if (index > size || index < 0)
0580 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
0581 }
0582
0583 /**
0584 * Constructs an IndexOutOfBoundsException detail message.
0585 * Of the many possible refactorings of the error handling code,
0586 * this "outlining" performs best with both server and client VMs.
0587 */
0588 private String outOfBoundsMsg(int index) {
0589 return "Index: " + index + ", Size: " + size;
0590 }
0591
0592 /**
0593 * Removes from this list all of its elements that are contained in the
0594 * specified collection.
0595 *
0596 * @param c collection containing elements to be removed from this list
0597 * @return {@code true} if this list changed as a result of the call
0598 * @throws ClassCastException if the class of an element of this list
0599 * is incompatible with the specified collection (optional)
0600 * @throws NullPointerException if this list contains a null element and the
0601 * specified collection does not permit null elements (optional),
0602 * or if the specified collection is null
0603 * @see Collection#contains(Object)
0604 */
0605 public boolean removeAll(Collection<?> c) {
0606 return batchRemove(c, false);
0607 }
0608
0609 /**
0610 * Retains only the elements in this list that are contained in the
0611 * specified collection. In other words, removes from this list all
0612 * of its elements that are not contained in the specified collection.
0613 *
0614 * @param c collection containing elements to be retained in this list
0615 * @return {@code true} if this list changed as a result of the call
0616 * @throws ClassCastException if the class of an element of this list
0617 * is incompatible with the specified collection (optional)
0618 * @throws NullPointerException if this list contains a null element and the
0619 * specified collection does not permit null elements (optional),
0620 * or if the specified collection is null
0621 * @see Collection#contains(Object)
0622 */
0623 public boolean retainAll(Collection<?> c) {
0624 return batchRemove(c, true);
0625 }
0626
0627 private boolean batchRemove(Collection<?> c, boolean complement) {
0628 final Object[] elementData = this .elementData;
0629 int r = 0, w = 0;
0630 boolean modified = false;
0631 try {
0632 for (; r < size; r++)
0633 if (c.contains(elementData[r]) == complement)
0634 elementData[w++] = elementData[r];
0635 } finally {
0636 // Preserve behavioral compatibility with AbstractCollection,
0637 // even if c.contains() throws.
0638 if (r != size) {
0639 System.arraycopy(elementData, r, elementData, w, size
0640 - r);
0641 w += size - r;
0642 }
0643 if (w != size) {
0644 for (int i = w; i < size; i++)
0645 elementData[i] = null;
0646 modCount += size - w;
0647 size = w;
0648 modified = true;
0649 }
0650 }
0651 return modified;
0652 }
0653
0654 /**
0655 * Save the state of the <tt>ArrayList</tt> instance to a stream (that
0656 * is, serialize it).
0657 *
0658 * @serialData The length of the array backing the <tt>ArrayList</tt>
0659 * instance is emitted (int), followed by all of its elements
0660 * (each an <tt>Object</tt>) in the proper order.
0661 */
0662 private void writeObject(java.io.ObjectOutputStream s)
0663 throws java.io.IOException {
0664 // Write out element count, and any hidden stuff
0665 int expectedModCount = modCount;
0666 s.defaultWriteObject();
0667
0668 // Write out array length
0669 s.writeInt(elementData.length);
0670
0671 // Write out all elements in the proper order.
0672 for (int i = 0; i < size; i++)
0673 s.writeObject(elementData[i]);
0674
0675 if (modCount != expectedModCount) {
0676 throw new ConcurrentModificationException();
0677 }
0678
0679 }
0680
0681 /**
0682 * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
0683 * deserialize it).
0684 */
0685 private void readObject(java.io.ObjectInputStream s)
0686 throws java.io.IOException, ClassNotFoundException {
0687 // Read in size, and any hidden stuff
0688 s.defaultReadObject();
0689
0690 // Read in array length and allocate array
0691 int arrayLength = s.readInt();
0692 Object[] a = elementData = new Object[arrayLength];
0693
0694 // Read in all elements in the proper order.
0695 for (int i = 0; i < size; i++)
0696 a[i] = s.readObject();
0697 }
0698
0699 /**
0700 * Returns a list iterator over the elements in this list (in proper
0701 * sequence), starting at the specified position in the list.
0702 * The specified index indicates the first element that would be
0703 * returned by an initial call to {@link ListIterator#next next}.
0704 * An initial call to {@link ListIterator#previous previous} would
0705 * return the element with the specified index minus one.
0706 *
0707 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
0708 *
0709 * @throws IndexOutOfBoundsException {@inheritDoc}
0710 */
0711 public ListIterator<E> listIterator(int index) {
0712 if (index < 0 || index > size)
0713 throw new IndexOutOfBoundsException("Index: " + index);
0714 return new ListItr(index);
0715 }
0716
0717 /**
0718 * Returns a list iterator over the elements in this list (in proper
0719 * sequence).
0720 *
0721 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
0722 *
0723 * @see #listIterator(int)
0724 */
0725 public ListIterator<E> listIterator() {
0726 return new ListItr(0);
0727 }
0728
0729 /**
0730 * Returns an iterator over the elements in this list in proper sequence.
0731 *
0732 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
0733 *
0734 * @return an iterator over the elements in this list in proper sequence
0735 */
0736 public Iterator<E> iterator() {
0737 return new Itr();
0738 }
0739
0740 /**
0741 * An optimized version of AbstractList.Itr
0742 */
0743 private class Itr implements Iterator<E> {
0744 int cursor; // index of next element to return
0745 int lastRet = -1; // index of last element returned; -1 if no such
0746 int expectedModCount = modCount;
0747
0748 public boolean hasNext() {
0749 return cursor != size;
0750 }
0751
0752 @SuppressWarnings("unchecked")
0753 public E next() {
0754 checkForComodification();
0755 int i = cursor;
0756 if (i >= size)
0757 throw new NoSuchElementException();
0758 Object[] elementData = ArrayList.this .elementData;
0759 if (i >= elementData.length)
0760 throw new ConcurrentModificationException();
0761 cursor = i + 1;
0762 return (E) elementData[lastRet = i];
0763 }
0764
0765 public void remove() {
0766 if (lastRet < 0)
0767 throw new IllegalStateException();
0768 checkForComodification();
0769
0770 try {
0771 ArrayList.this .remove(lastRet);
0772 cursor = lastRet;
0773 lastRet = -1;
0774 expectedModCount = modCount;
0775 } catch (IndexOutOfBoundsException ex) {
0776 throw new ConcurrentModificationException();
0777 }
0778 }
0779
0780 final void checkForComodification() {
0781 if (modCount != expectedModCount)
0782 throw new ConcurrentModificationException();
0783 }
0784 }
0785
0786 /**
0787 * An optimized version of AbstractList.ListItr
0788 */
0789 private class ListItr extends Itr implements ListIterator<E> {
0790 ListItr(int index) {
0791 super ();
0792 cursor = index;
0793 }
0794
0795 public boolean hasPrevious() {
0796 return cursor != 0;
0797 }
0798
0799 public int nextIndex() {
0800 return cursor;
0801 }
0802
0803 public int previousIndex() {
0804 return cursor - 1;
0805 }
0806
0807 @SuppressWarnings("unchecked")
0808 public E previous() {
0809 checkForComodification();
0810 int i = cursor - 1;
0811 if (i < 0)
0812 throw new NoSuchElementException();
0813 Object[] elementData = ArrayList.this .elementData;
0814 if (i >= elementData.length)
0815 throw new ConcurrentModificationException();
0816 cursor = i;
0817 return (E) elementData[lastRet = i];
0818 }
0819
0820 public void set(E e) {
0821 if (lastRet < 0)
0822 throw new IllegalStateException();
0823 checkForComodification();
0824
0825 try {
0826 ArrayList.this .set(lastRet, e);
0827 } catch (IndexOutOfBoundsException ex) {
0828 throw new ConcurrentModificationException();
0829 }
0830 }
0831
0832 public void add(E e) {
0833 checkForComodification();
0834
0835 try {
0836 int i = cursor;
0837 ArrayList.this .add(i, e);
0838 cursor = i + 1;
0839 lastRet = -1;
0840 expectedModCount = modCount;
0841 } catch (IndexOutOfBoundsException ex) {
0842 throw new ConcurrentModificationException();
0843 }
0844 }
0845 }
0846
0847 /**
0848 * Returns a view of the portion of this list between the specified
0849 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If
0850 * {@code fromIndex} and {@code toIndex} are equal, the returned list is
0851 * empty.) The returned list is backed by this list, so non-structural
0852 * changes in the returned list are reflected in this list, and vice-versa.
0853 * The returned list supports all of the optional list operations.
0854 *
0855 * <p>This method eliminates the need for explicit range operations (of
0856 * the sort that commonly exist for arrays). Any operation that expects
0857 * a list can be used as a range operation by passing a subList view
0858 * instead of a whole list. For example, the following idiom
0859 * removes a range of elements from a list:
0860 * <pre>
0861 * list.subList(from, to).clear();
0862 * </pre>
0863 * Similar idioms may be constructed for {@link #indexOf(Object)} and
0864 * {@link #lastIndexOf(Object)}, and all of the algorithms in the
0865 * {@link Collections} class can be applied to a subList.
0866 *
0867 * <p>The semantics of the list returned by this method become undefined if
0868 * the backing list (i.e., this list) is <i>structurally modified</i> in
0869 * any way other than via the returned list. (Structural modifications are
0870 * those that change the size of this list, or otherwise perturb it in such
0871 * a fashion that iterations in progress may yield incorrect results.)
0872 *
0873 * @throws IndexOutOfBoundsException {@inheritDoc}
0874 * @throws IllegalArgumentException {@inheritDoc}
0875 */
0876 public List<E> subList(int fromIndex, int toIndex) {
0877 subListRangeCheck(fromIndex, toIndex, size);
0878 return new SubList(this , 0, fromIndex, toIndex);
0879 }
0880
0881 static void subListRangeCheck(int fromIndex, int toIndex, int size) {
0882 if (fromIndex < 0)
0883 throw new IndexOutOfBoundsException("fromIndex = "
0884 + fromIndex);
0885 if (toIndex > size)
0886 throw new IndexOutOfBoundsException("toIndex = " + toIndex);
0887 if (fromIndex > toIndex)
0888 throw new IllegalArgumentException("fromIndex(" + fromIndex
0889 + ") > toIndex(" + toIndex + ")");
0890 }
0891
0892 private class SubList extends AbstractList<E> implements
0893 RandomAccess {
0894 private final AbstractList<E> parent;
0895 private final int parentOffset;
0896 private final int offset;
0897 private int size;
0898
0899 SubList(AbstractList<E> parent, int offset, int fromIndex,
0900 int toIndex) {
0901 this .parent = parent;
0902 this .parentOffset = fromIndex;
0903 this .offset = offset + fromIndex;
0904 this .size = toIndex - fromIndex;
0905 this .modCount = ArrayList.this .modCount;
0906 }
0907
0908 public E set(int index, E e) {
0909 rangeCheck(index);
0910 checkForComodification();
0911 E oldValue = ArrayList.this .elementData(offset + index);
0912 ArrayList.this .elementData[offset + index] = e;
0913 return oldValue;
0914 }
0915
0916 public E get(int index) {
0917 rangeCheck(index);
0918 checkForComodification();
0919 return ArrayList.this .elementData(offset + index);
0920 }
0921
0922 public int size() {
0923 checkForComodification();
0924 return this .size;
0925 }
0926
0927 public void add(int index, E e) {
0928 rangeCheckForAdd(index);
0929 checkForComodification();
0930 parent.add(parentOffset + index, e);
0931 this .modCount = parent.modCount;
0932 this .size++;
0933 }
0934
0935 public E remove(int index) {
0936 rangeCheck(index);
0937 checkForComodification();
0938 E result = parent.remove(parentOffset + index);
0939 this .modCount = parent.modCount;
0940 this .size--;
0941 return result;
0942 }
0943
0944 protected void removeRange(int fromIndex, int toIndex) {
0945 checkForComodification();
0946 parent.removeRange(parentOffset + fromIndex, parentOffset
0947 + toIndex);
0948 this .modCount = parent.modCount;
0949 this .size -= toIndex - fromIndex;
0950 }
0951
0952 public boolean addAll(Collection<? extends E> c) {
0953 return addAll(this .size, c);
0954 }
0955
0956 public boolean addAll(int index, Collection<? extends E> c) {
0957 rangeCheckForAdd(index);
0958 int cSize = c.size();
0959 if (cSize == 0)
0960 return false;
0961
0962 checkForComodification();
0963 parent.addAll(parentOffset + index, c);
0964 this .modCount = parent.modCount;
0965 this .size += cSize;
0966 return true;
0967 }
0968
0969 public Iterator<E> iterator() {
0970 return listIterator();
0971 }
0972
0973 public ListIterator<E> listIterator(final int index) {
0974 checkForComodification();
0975 rangeCheckForAdd(index);
0976
0977 return new ListIterator<E>() {
0978 int cursor = index;
0979 int lastRet = -1;
0980 int expectedModCount = ArrayList.this .modCount;
0981
0982 public boolean hasNext() {
0983 return cursor != SubList.this .size;
0984 }
0985
0986 @SuppressWarnings("unchecked")
0987 public E next() {
0988 checkForComodification();
0989 int i = cursor;
0990 if (i >= SubList.this .size)
0991 throw new NoSuchElementException();
0992 Object[] elementData = ArrayList.this .elementData;
0993 if (offset + i >= elementData.length)
0994 throw new ConcurrentModificationException();
0995 cursor = i + 1;
0996 return (E) elementData[offset + (lastRet = i)];
0997 }
0998
0999 public boolean hasPrevious() {
1000 return cursor != 0;
1001 }
1002
1003 @SuppressWarnings("unchecked")
1004 public E previous() {
1005 checkForComodification();
1006 int i = cursor - 1;
1007 if (i < 0)
1008 throw new NoSuchElementException();
1009 Object[] elementData = ArrayList.this .elementData;
1010 if (offset + i >= elementData.length)
1011 throw new ConcurrentModificationException();
1012 cursor = i;
1013 return (E) elementData[offset + (lastRet = i)];
1014 }
1015
1016 public int nextIndex() {
1017 return cursor;
1018 }
1019
1020 public int previousIndex() {
1021 return cursor - 1;
1022 }
1023
1024 public void remove() {
1025 if (lastRet < 0)
1026 throw new IllegalStateException();
1027 checkForComodification();
1028
1029 try {
1030 SubList.this .remove(lastRet);
1031 cursor = lastRet;
1032 lastRet = -1;
1033 expectedModCount = ArrayList.this .modCount;
1034 } catch (IndexOutOfBoundsException ex) {
1035 throw new ConcurrentModificationException();
1036 }
1037 }
1038
1039 public void set(E e) {
1040 if (lastRet < 0)
1041 throw new IllegalStateException();
1042 checkForComodification();
1043
1044 try {
1045 ArrayList.this .set(offset + lastRet, e);
1046 } catch (IndexOutOfBoundsException ex) {
1047 throw new ConcurrentModificationException();
1048 }
1049 }
1050
1051 public void add(E e) {
1052 checkForComodification();
1053
1054 try {
1055 int i = cursor;
1056 SubList.this .add(i, e);
1057 cursor = i + 1;
1058 lastRet = -1;
1059 expectedModCount = ArrayList.this .modCount;
1060 } catch (IndexOutOfBoundsException ex) {
1061 throw new ConcurrentModificationException();
1062 }
1063 }
1064
1065 final void checkForComodification() {
1066 if (expectedModCount != ArrayList.this .modCount)
1067 throw new ConcurrentModificationException();
1068 }
1069 };
1070 }
1071
1072 public List<E> subList(int fromIndex, int toIndex) {
1073 subListRangeCheck(fromIndex, toIndex, size);
1074 return new SubList(this , offset, fromIndex, toIndex);
1075 }
1076
1077 private void rangeCheck(int index) {
1078 if (index < 0 || index >= this .size)
1079 throw new IndexOutOfBoundsException(
1080 outOfBoundsMsg(index));
1081 }
1082
1083 private void rangeCheckForAdd(int index) {
1084 if (index < 0 || index > this .size)
1085 throw new IndexOutOfBoundsException(
1086 outOfBoundsMsg(index));
1087 }
1088
1089 private String outOfBoundsMsg(int index) {
1090 return "Index: " + index + ", Size: " + this .size;
1091 }
1092
1093 private void checkForComodification() {
1094 if (ArrayList.this .modCount != this .modCount)
1095 throw new ConcurrentModificationException();
1096 }
1097 }
1098 }
|