1 /*
   2  * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 /**
  29  * Resizable-array implementation of the <tt>List</tt> interface.  Implements
  30  * all optional list operations, and permits all elements, including
  31  * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
  32  * this class provides methods to manipulate the size of the array that is
  33  * used internally to store the list.  (This class is roughly equivalent to
  34  * <tt>Vector</tt>, except that it is unsynchronized.)
  35  *
  36  * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
  37  * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
  38  * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
  39  * that is, adding n elements requires O(n) time.  All of the other operations
  40  * run in linear time (roughly speaking).  The constant factor is low compared
  41  * to that for the <tt>LinkedList</tt> implementation.
  42  *
  43  * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
  44  * the size of the array used to store the elements in the list.  It is always
  45  * at least as large as the list size.  As elements are added to an ArrayList,
  46  * its capacity grows automatically.  The details of the growth policy are not
  47  * specified beyond the fact that adding an element has constant amortized
  48  * time cost.
  49  *
  50  * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
  51  * before adding a large number of elements using the <tt>ensureCapacity</tt>
  52  * operation.  This may reduce the amount of incremental reallocation.
  53  *
  54  * <p><strong>Note that this implementation is not synchronized.</strong>
  55  * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
  56  * and at least one of the threads modifies the list structurally, it
  57  * <i>must</i> be synchronized externally.  (A structural modification is
  58  * any operation that adds or deletes one or more elements, or explicitly
  59  * resizes the backing array; merely setting the value of an element is not
  60  * a structural modification.)  This is typically accomplished by
  61  * synchronizing on some object that naturally encapsulates the list.
  62  *
  63  * If no such object exists, the list should be "wrapped" using the
  64  * {@link Collections#synchronizedList Collections.synchronizedList}
  65  * method.  This is best done at creation time, to prevent accidental
  66  * unsynchronized access to the list:<pre>
  67  *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
  68  *
  69  * <p><a name="fail-fast"/>
  70  * The iterators returned by this class's {@link #iterator() iterator} and
  71  * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
  72  * if the list is structurally modified at any time after the iterator is
  73  * created, in any way except through the iterator's own
  74  * {@link ListIterator#remove() remove} or
  75  * {@link ListIterator#add(Object) add} methods, the iterator will throw a
  76  * {@link ConcurrentModificationException}.  Thus, in the face of
  77  * concurrent modification, the iterator fails quickly and cleanly, rather
  78  * than risking arbitrary, non-deterministic behavior at an undetermined
  79  * time in the future.
  80  *
  81  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  82  * as it is, generally speaking, impossible to make any hard guarantees in the
  83  * presence of unsynchronized concurrent modification.  Fail-fast iterators
  84  * throw {@code ConcurrentModificationException} on a best-effort basis.
  85  * Therefore, it would be wrong to write a program that depended on this
  86  * exception for its correctness:  <i>the fail-fast behavior of iterators
  87  * should be used only to detect bugs.</i>
  88  *
  89  * <p>This class is a member of the
  90  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  91  * Java Collections Framework</a>.
  92  *
  93  * @author  Josh Bloch
  94  * @author  Neal Gafter
  95  * @see     Collection
  96  * @see     List
  97  * @see     LinkedList
  98  * @see     Vector
  99  * @since   1.2
 100  */
 101 
 102 public class ArrayList<E> extends AbstractList<E>
 103         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 104 {
 105     private static final long serialVersionUID = 8683452581122892189L;
 106 
 107     /**
 108      * Default initial capacity.
 109      */
 110     private static final int DEFAULT_CAPACITY= 10;
 111 
 112     /**
 113      * Shared empty array instance used for empty instances.
 114      */
 115     private static final Object[] EMPTY_ELEMENTDATA = {};
 116 
 117     /**
 118      * The array buffer into which the elements of the ArrayList are stored.
 119      * The capacity of the ArrayList is the length of this array buffer. Any
 120      * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
 121      * DEFAULT_CAPACITY when the first element is added.
 122      */
 123     private transient Object[] elementData;
 124 
 125     /**
 126      * The size of the ArrayList (the number of elements it contains).
 127      *
 128      * @serial
 129      */
 130     private int size;
 131 
 132     /**
 133      * Constructs an empty list with the specified initial capacity.
 134      *
 135      * @param  initialCapacity  the initial capacity of the list
 136      * @throws IllegalArgumentException if the specified initial capacity
 137      *         is negative
 138      */
 139     public ArrayList(int initialCapacity) {
 140         super();
 141         if (initialCapacity < 0)
 142             throw new IllegalArgumentException("Illegal Capacity: "+
 143                                                initialCapacity);
 144         this.elementData = new Object[initialCapacity];
 145     }
 146 
 147     /**
 148      * Constructs an empty list with an initial capacity of ten.
 149      */
 150     public ArrayList() {
 151         super();
 152         this.elementData = EMPTY_ELEMENTDATA;
 153     }
 154 
 155     /**
 156      * Constructs a list containing the elements of the specified
 157      * collection, in the order they are returned by the collection's
 158      * iterator.
 159      *
 160      * @param c the collection whose elements are to be placed into this list
 161      * @throws NullPointerException if the specified collection is null
 162      */
 163     public ArrayList(Collection<? extends E> c) {
 164         elementData = c.toArray();
 165         size = elementData.length;
 166         // c.toArray might (incorrectly) not return Object[] (see 6260652)
 167         if (elementData.getClass() != Object[].class)
 168             elementData = Arrays.copyOf(elementData, size, Object[].class);
 169     }
 170 
 171     /**
 172      * Trims the capacity of this <tt>ArrayList</tt> instance to be the
 173      * list's current size.  An application can use this operation to minimize
 174      * the storage of an <tt>ArrayList</tt> instance.
 175      */
 176     public void trimToSize() {
 177         modCount++;
 178         if (size < elementData.length) {
 179             elementData = Arrays.copyOf(elementData, size);
 180         }
 181     }
 182 
 183     /**
 184      * Increases the capacity of this <tt>ArrayList</tt> instance, if
 185      * necessary, to ensure that it can hold at least the number of elements
 186      * specified by the minimum capacity argument.
 187      *
 188      * @param   minCapacity   the desired minimum capacity
 189      */
 190     public void ensureCapacity(int minCapacity) {
 191         int minExpand = (elementData != EMPTY_ELEMENTDATA)
 192             // any size if real element table
 193             ? 0
 194             // larger than default for empty table. It's already supposed to be
 195             // at default size.
 196             : DEFAULT_CAPACITY;
 197 
 198         if (minCapacity > minExpand) {
 199             ensureExplicitCapacity(minCapacity);
 200         }
 201     }
 202 
 203     private void ensureCapacityInternal(int minCapacity) {
 204         if (elementData == EMPTY_ELEMENTDATA) {
 205             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 206         }
 207 
 208         ensureExplicitCapacity(minCapacity);
 209     }
 210 
 211     private void ensureExplicitCapacity(int minCapacity) {
 212         modCount++;
 213 
 214         // overflow-conscious code
 215         if (minCapacity - elementData.length > 0)
 216             grow(minCapacity);
 217     }
 218 
 219     /**
 220      * The maximum size of array to allocate.
 221      * Some VMs reserve some header words in an array.
 222      * Attempts to allocate larger arrays may result in
 223      * OutOfMemoryError: Requested array size exceeds VM limit
 224      */
 225     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 226 
 227     /**
 228      * Increases the capacity to ensure that it can hold at least the
 229      * number of elements specified by the minimum capacity argument.
 230      *
 231      * @param minCapacity the desired minimum capacity
 232      */
 233     private void grow(int minCapacity) {
 234         // overflow-conscious code
 235         int oldCapacity = elementData.length;
 236         int newCapacity = oldCapacity + (oldCapacity >> 1);
 237         if (newCapacity - minCapacity < 0)
 238             newCapacity = minCapacity;
 239         if (newCapacity - MAX_ARRAY_SIZE > 0)
 240             newCapacity = hugeCapacity(minCapacity);
 241         // minCapacity is usually close to size, so this is a win:
 242         elementData = Arrays.copyOf(elementData, newCapacity);
 243     }
 244 
 245     private static int hugeCapacity(int minCapacity) {
 246         if (minCapacity < 0) // overflow
 247             throw new OutOfMemoryError();
 248         return (minCapacity > MAX_ARRAY_SIZE) ?
 249             Integer.MAX_VALUE :
 250             MAX_ARRAY_SIZE;
 251     }
 252 
 253     /**
 254      * Returns the number of elements in this list.
 255      *
 256      * @return the number of elements in this list
 257      */
 258     public int size() {
 259         return size;
 260     }
 261 
 262     /**
 263      * Returns <tt>true</tt> if this list contains no elements.
 264      *
 265      * @return <tt>true</tt> if this list contains no elements
 266      */
 267     public boolean isEmpty() {
 268         return size == 0;
 269     }
 270 
 271     /**
 272      * Returns <tt>true</tt> if this list contains the specified element.
 273      * More formally, returns <tt>true</tt> if and only if this list contains
 274      * at least one element <tt>e</tt> such that
 275      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 276      *
 277      * @param o element whose presence in this list is to be tested
 278      * @return <tt>true</tt> if this list contains the specified element
 279      */
 280     public boolean contains(Object o) {
 281         return indexOf(o) >= 0;
 282     }
 283 
 284     /**
 285      * Returns the index of the first occurrence of the specified element
 286      * in this list, or -1 if this list does not contain the element.
 287      * More formally, returns the lowest index <tt>i</tt> such that
 288      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 289      * or -1 if there is no such index.
 290      */
 291     public int indexOf(Object o) {
 292         if (o == null) {
 293             for (int i = 0; i < size; i++)
 294                 if (elementData[i]==null)
 295                     return i;
 296         } else {
 297             for (int i = 0; i < size; i++)
 298                 if (o.equals(elementData[i]))
 299                     return i;
 300         }
 301         return -1;
 302     }
 303 
 304     /**
 305      * Returns the index of the last occurrence of the specified element
 306      * in this list, or -1 if this list does not contain the element.
 307      * More formally, returns the highest index <tt>i</tt> such that
 308      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 309      * or -1 if there is no such index.
 310      */
 311     public int lastIndexOf(Object o) {
 312         if (o == null) {
 313             for (int i = size-1; i >= 0; i--)
 314                 if (elementData[i]==null)
 315                     return i;
 316         } else {
 317             for (int i = size-1; i >= 0; i--)
 318                 if (o.equals(elementData[i]))
 319                     return i;
 320         }
 321         return -1;
 322     }
 323 
 324     /**
 325      * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
 326      * elements themselves are not copied.)
 327      *
 328      * @return a clone of this <tt>ArrayList</tt> instance
 329      */
 330     public Object clone() {
 331         try {
 332             ArrayList<?> v = (ArrayList<?>) super.clone();
 333             v.elementData = Arrays.copyOf(elementData, size);
 334             v.modCount = 0;
 335             return v;
 336         } catch (CloneNotSupportedException e) {
 337             // this shouldn't happen, since we are Cloneable
 338             throw new InternalError(e);
 339         }
 340     }
 341 
 342     /**
 343      * Returns an array containing all of the elements in this list
 344      * in proper sequence (from first to last element).
 345      *
 346      * <p>The returned array will be "safe" in that no references to it are
 347      * maintained by this list.  (In other words, this method must allocate
 348      * a new array).  The caller is thus free to modify the returned array.
 349      *
 350      * <p>This method acts as bridge between array-based and collection-based
 351      * APIs.
 352      *
 353      * @return an array containing all of the elements in this list in
 354      *         proper sequence
 355      */
 356     public Object[] toArray() {
 357         return Arrays.copyOf(elementData, size);
 358     }
 359 
 360     /**
 361      * Returns an array containing all of the elements in this list in proper
 362      * sequence (from first to last element); the runtime type of the returned
 363      * array is that of the specified array.  If the list fits in the
 364      * specified array, it is returned therein.  Otherwise, a new array is
 365      * allocated with the runtime type of the specified array and the size of
 366      * this list.
 367      *
 368      * <p>If the list fits in the specified array with room to spare
 369      * (i.e., the array has more elements than the list), the element in
 370      * the array immediately following the end of the collection is set to
 371      * <tt>null</tt>.  (This is useful in determining the length of the
 372      * list <i>only</i> if the caller knows that the list does not contain
 373      * any null elements.)
 374      *
 375      * @param a the array into which the elements of the list are to
 376      *          be stored, if it is big enough; otherwise, a new array of the
 377      *          same runtime type is allocated for this purpose.
 378      * @return an array containing the elements of the list
 379      * @throws ArrayStoreException if the runtime type of the specified array
 380      *         is not a supertype of the runtime type of every element in
 381      *         this list
 382      * @throws NullPointerException if the specified array is null
 383      */
 384     @SuppressWarnings("unchecked")
 385     public <T> T[] toArray(T[] a) {
 386         if (a.length < size)
 387             // Make a new array of a's runtime type, but my contents:
 388             return (T[]) Arrays.copyOf(elementData, size, a.getClass());
 389         System.arraycopy(elementData, 0, a, 0, size);
 390         if (a.length > size)
 391             a[size] = null;
 392         return a;
 393     }
 394 
 395     // Positional Access Operations
 396 
 397     @SuppressWarnings("unchecked")
 398     E elementData(int index) {
 399         return (E) elementData[index];
 400     }
 401 
 402     /**
 403      * Returns the element at the specified position in this list.
 404      *
 405      * @param  index index of the element to return
 406      * @return the element at the specified position in this list
 407      * @throws IndexOutOfBoundsException {@inheritDoc}
 408      */
 409     public E get(int index) {
 410         rangeCheck(index);
 411 
 412         return elementData(index);
 413     }
 414 
 415     /**
 416      * Replaces the element at the specified position in this list with
 417      * the specified element.
 418      *
 419      * @param index index of the element to replace
 420      * @param element element to be stored at the specified position
 421      * @return the element previously at the specified position
 422      * @throws IndexOutOfBoundsException {@inheritDoc}
 423      */
 424     public E set(int index, E element) {
 425         rangeCheck(index);
 426 
 427         E oldValue = elementData(index);
 428         elementData[index] = element;
 429         return oldValue;
 430     }
 431 
 432     /**
 433      * Appends the specified element to the end of this list.
 434      *
 435      * @param e element to be appended to this list
 436      * @return <tt>true</tt> (as specified by {@link Collection#add})
 437      */
 438     public boolean add(E e) {
 439         ensureCapacityInternal(size + 1);  // Increments modCount!!
 440         elementData[size++] = e;
 441         return true;
 442     }
 443 
 444     /**
 445      * Inserts the specified element at the specified position in this
 446      * list. Shifts the element currently at that position (if any) and
 447      * any subsequent elements to the right (adds one to their indices).
 448      *
 449      * @param index index at which the specified element is to be inserted
 450      * @param element element to be inserted
 451      * @throws IndexOutOfBoundsException {@inheritDoc}
 452      */
 453     public void add(int index, E element) {
 454         rangeCheckForAdd(index);
 455 
 456         ensureCapacityInternal(size + 1);  // Increments modCount!!
 457         System.arraycopy(elementData, index, elementData, index + 1,
 458                          size - index);
 459         elementData[index] = element;
 460         size++;
 461     }
 462 
 463     /**
 464      * Removes the element at the specified position in this list.
 465      * Shifts any subsequent elements to the left (subtracts one from their
 466      * indices).
 467      *
 468      * @param index the index of the element to be removed
 469      * @return the element that was removed from the list
 470      * @throws IndexOutOfBoundsException {@inheritDoc}
 471      */
 472     public E remove(int index) {
 473         rangeCheck(index);
 474 
 475         modCount++;
 476         E oldValue = elementData(index);
 477 
 478         int numMoved = size - index - 1;
 479         if (numMoved > 0)
 480             System.arraycopy(elementData, index+1, elementData, index,
 481                              numMoved);
 482         elementData[--size] = null; // clear to let GC do its work
 483 
 484         return oldValue;
 485     }
 486 
 487     /**
 488      * Removes the first occurrence of the specified element from this list,
 489      * if it is present.  If the list does not contain the element, it is
 490      * unchanged.  More formally, removes the element with the lowest index
 491      * <tt>i</tt> such that
 492      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 493      * (if such an element exists).  Returns <tt>true</tt> if this list
 494      * contained the specified element (or equivalently, if this list
 495      * changed as a result of the call).
 496      *
 497      * @param o element to be removed from this list, if present
 498      * @return <tt>true</tt> if this list contained the specified element
 499      */
 500     public boolean remove(Object o) {
 501         if (o == null) {
 502             for (int index = 0; index < size; index++)
 503                 if (elementData[index] == null) {
 504                     fastRemove(index);
 505                     return true;
 506                 }
 507         } else {
 508             for (int index = 0; index < size; index++)
 509                 if (o.equals(elementData[index])) {
 510                     fastRemove(index);
 511                     return true;
 512                 }
 513         }
 514         return false;
 515     }
 516 
 517     /*
 518      * Private remove method that skips bounds checking and does not
 519      * return the value removed.
 520      */
 521     private void fastRemove(int index) {
 522         modCount++;
 523         int numMoved = size - index - 1;
 524         if (numMoved > 0)
 525             System.arraycopy(elementData, index+1, elementData, index,
 526                              numMoved);
 527         elementData[--size] = null; // clear to let GC do its work
 528     }
 529 
 530     /**
 531      * Removes all of the elements from this list.  The list will
 532      * be empty after this call returns.
 533      */
 534     public void clear() {
 535         modCount++;
 536 
 537         // clear to let GC do its work
 538         for (int i = 0; i < size; i++)
 539             elementData[i] = null;
 540 
 541         size = 0;
 542     }
 543 
 544     /**
 545      * Appends all of the elements in the specified collection to the end of
 546      * this list, in the order that they are returned by the
 547      * specified collection's Iterator.  The behavior of this operation is
 548      * undefined if the specified collection is modified while the operation
 549      * is in progress.  (This implies that the behavior of this call is
 550      * undefined if the specified collection is this list, and this
 551      * list is nonempty.)
 552      *
 553      * @param c collection containing elements to be added to this list
 554      * @return <tt>true</tt> if this list changed as a result of the call
 555      * @throws NullPointerException if the specified collection is null
 556      */
 557     public boolean addAll(Collection<? extends E> c) {
 558         Object[] a = c.toArray();
 559         int numNew = a.length;
 560         ensureCapacityInternal(size + numNew);  // Increments modCount
 561         System.arraycopy(a, 0, elementData, size, numNew);
 562         size += numNew;
 563         return numNew != 0;
 564     }
 565 
 566     /**
 567      * Inserts all of the elements in the specified collection into this
 568      * list, starting at the specified position.  Shifts the element
 569      * currently at that position (if any) and any subsequent elements to
 570      * the right (increases their indices).  The new elements will appear
 571      * in the list in the order that they are returned by the
 572      * specified collection's iterator.
 573      *
 574      * @param index index at which to insert the first element from the
 575      *              specified collection
 576      * @param c collection containing elements to be added to this list
 577      * @return <tt>true</tt> if this list changed as a result of the call
 578      * @throws IndexOutOfBoundsException {@inheritDoc}
 579      * @throws NullPointerException if the specified collection is null
 580      */
 581     public boolean addAll(int index, Collection<? extends E> c) {
 582         rangeCheckForAdd(index);
 583 
 584         Object[] a = c.toArray();
 585         int numNew = a.length;
 586         ensureCapacityInternal(size + numNew);  // Increments modCount
 587 
 588         int numMoved = size - index;
 589         if (numMoved > 0)
 590             System.arraycopy(elementData, index, elementData, index + numNew,
 591                              numMoved);
 592 
 593         System.arraycopy(a, 0, elementData, index, numNew);
 594         size += numNew;
 595         return numNew != 0;
 596     }
 597 
 598     /**
 599      * Removes from this list all of the elements whose index is between
 600      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 601      * Shifts any succeeding elements to the left (reduces their index).
 602      * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 603      * (If {@code toIndex==fromIndex}, this operation has no effect.)
 604      *
 605      * @throws IndexOutOfBoundsException if {@code fromIndex} or
 606      *         {@code toIndex} is out of range
 607      *         ({@code fromIndex < 0 ||
 608      *          fromIndex >= size() ||
 609      *          toIndex > size() ||
 610      *          toIndex < fromIndex})
 611      */
 612     protected void removeRange(int fromIndex, int toIndex) {
 613         modCount++;
 614         int numMoved = size - toIndex;
 615         System.arraycopy(elementData, toIndex, elementData, fromIndex,
 616                          numMoved);
 617 
 618         // clear to let GC do its work
 619         int newSize = size - (toIndex-fromIndex);
 620         for (int i = newSize; i < size; i++) {
 621             elementData[i] = null;
 622         }
 623         size = newSize;
 624     }
 625 
 626     /**
 627      * Checks if the given index is in range.  If not, throws an appropriate
 628      * runtime exception.  This method does *not* check if the index is
 629      * negative: It is always used immediately prior to an array access,
 630      * which throws an ArrayIndexOutOfBoundsException if index is negative.
 631      */
 632     private void rangeCheck(int index) {
 633         if (index >= size)
 634             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 635     }
 636 
 637     /**
 638      * A version of rangeCheck used by add and addAll.
 639      */
 640     private void rangeCheckForAdd(int index) {
 641         if (index > size || index < 0)
 642             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 643     }
 644 
 645     /**
 646      * Constructs an IndexOutOfBoundsException detail message.
 647      * Of the many possible refactorings of the error handling code,
 648      * this "outlining" performs best with both server and client VMs.
 649      */
 650     private String outOfBoundsMsg(int index) {
 651         return "Index: "+index+", Size: "+size;
 652     }
 653 
 654     /**
 655      * Removes from this list all of its elements that are contained in the
 656      * specified collection.
 657      *
 658      * @param c collection containing elements to be removed from this list
 659      * @return {@code true} if this list changed as a result of the call
 660      * @throws ClassCastException if the class of an element of this list
 661      *         is incompatible with the specified collection
 662      * (<a href="Collection.html#optional-restrictions">optional</a>)
 663      * @throws NullPointerException if this list contains a null element and the
 664      *         specified collection does not permit null elements
 665      * (<a href="Collection.html#optional-restrictions">optional</a>),
 666      *         or if the specified collection is null
 667      * @see Collection#contains(Object)
 668      */
 669     public boolean removeAll(Collection<?> c) {
 670         return batchRemove(c, false);
 671     }
 672 
 673     /**
 674      * Retains only the elements in this list that are contained in the
 675      * specified collection.  In other words, removes from this list all
 676      * of its elements that are not contained in the specified collection.
 677      *
 678      * @param c collection containing elements to be retained in this list
 679      * @return {@code true} if this list changed as a result of the call
 680      * @throws ClassCastException if the class of an element of this list
 681      *         is incompatible with the specified collection
 682      * (<a href="Collection.html#optional-restrictions">optional</a>)
 683      * @throws NullPointerException if this list contains a null element and the
 684      *         specified collection does not permit null elements
 685      * (<a href="Collection.html#optional-restrictions">optional</a>),
 686      *         or if the specified collection is null
 687      * @see Collection#contains(Object)
 688      */
 689     public boolean retainAll(Collection<?> c) {
 690         return batchRemove(c, true);
 691     }
 692 
 693     private boolean batchRemove(Collection<?> c, boolean complement) {
 694         final Object[] elementData = this.elementData;
 695         int r = 0, w = 0;
 696         boolean modified = false;
 697         try {
 698             for (; r < size; r++)
 699                 if (c.contains(elementData[r]) == complement)
 700                     elementData[w++] = elementData[r];
 701         } finally {
 702             // Preserve behavioral compatibility with AbstractCollection,
 703             // even if c.contains() throws.
 704             if (r != size) {
 705                 System.arraycopy(elementData, r,
 706                                  elementData, w,
 707                                  size - r);
 708                 w += size - r;
 709             }
 710             if (w != size) {
 711                 // clear to let GC do its work
 712                 for (int i = w; i < size; i++)
 713                     elementData[i] = null;
 714                 modCount += size - w;
 715                 size = w;
 716                 modified = true;
 717             }
 718         }
 719         return modified;
 720     }
 721 
 722     /**
 723      * Save the state of the <tt>ArrayList</tt> instance to a stream (that
 724      * is, serialize it).
 725      *
 726      * @serialData The length of the array backing the <tt>ArrayList</tt>
 727      *             instance is emitted (int), followed by all of its elements
 728      *             (each an <tt>Object</tt>) in the proper order.
 729      */
 730     private void writeObject(java.io.ObjectOutputStream s)
 731         throws java.io.IOException{
 732         // Write out element count, and any hidden stuff
 733         int expectedModCount = modCount;
 734         s.defaultWriteObject();
 735 
 736         // Write out size as capacity for behavioural compatibility with clone()
 737         s.writeInt(size);
 738 
 739         // Write out all elements in the proper order.
 740         for (int i=0; i<size; i++) {
 741             s.writeObject(elementData[i]);
 742         }
 743 
 744         if (modCount != expectedModCount) {
 745             throw new ConcurrentModificationException();
 746         }
 747     }
 748 
 749     /**
 750      * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
 751      * deserialize it).
 752      */
 753     private void readObject(java.io.ObjectInputStream s)
 754         throws java.io.IOException, ClassNotFoundException {
 755          elementData = EMPTY_ELEMENTDATA;
 756 
 757         // Read in size, and any hidden stuff
 758         s.defaultReadObject();
 759 
 760         // Read in capacity
 761         s.readInt(); // ignored
 762 
 763         if (size > 0) {
 764             // be like clone(), allocate array based upon size not capacity
 765             ensureCapacityInternal(size);
 766 
 767             Object[] a = elementData;
 768             // Read in all elements in the proper order.
 769             for (int i=0; i<size; i++) {
 770                 a[i] = s.readObject();
 771             }
 772         }
 773     }
 774 
 775     /**
 776      * Returns a list iterator over the elements in this list (in proper
 777      * sequence), starting at the specified position in the list.
 778      * The specified index indicates the first element that would be
 779      * returned by an initial call to {@link ListIterator#next next}.
 780      * An initial call to {@link ListIterator#previous previous} would
 781      * return the element with the specified index minus one.
 782      *
 783      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 784      *
 785      * @throws IndexOutOfBoundsException {@inheritDoc}
 786      */
 787     public ListIterator<E> listIterator(int index) {
 788         if (index < 0 || index > size)
 789             throw new IndexOutOfBoundsException("Index: "+index);
 790         return new ListItr(index);
 791     }
 792 
 793     /**
 794      * Returns a list iterator over the elements in this list (in proper
 795      * sequence).
 796      *
 797      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 798      *
 799      * @see #listIterator(int)
 800      */
 801     public ListIterator<E> listIterator() {
 802         return new ListItr(0);
 803     }
 804 
 805     /**
 806      * Returns an iterator over the elements in this list in proper sequence.
 807      *
 808      * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 809      *
 810      * @return an iterator over the elements in this list in proper sequence
 811      */
 812     public Iterator<E> iterator() {
 813         return new Itr();
 814     }
 815 
 816     /**
 817      * An optimized version of AbstractList.Itr
 818      */
 819     private class Itr implements Iterator<E> {
 820         int cursor;       // index of next element to return
 821         int lastRet = -1; // index of last element returned; -1 if no such
 822         int expectedModCount = modCount;
 823 
 824         public boolean hasNext() {
 825             return cursor != size;
 826         }
 827 
 828         @SuppressWarnings("unchecked")
 829         public E next() {
 830             checkForComodification();
 831             int i = cursor;
 832             if (i >= size)
 833                 throw new NoSuchElementException();
 834             Object[] elementData = ArrayList.this.elementData;
 835             if (i >= elementData.length)
 836                 throw new ConcurrentModificationException();
 837             cursor = i + 1;
 838             return (E) elementData[lastRet = i];
 839         }
 840 
 841         public void remove() {
 842             if (lastRet < 0)
 843                 throw new IllegalStateException();
 844             checkForComodification();
 845 
 846             try {
 847                 ArrayList.this.remove(lastRet);
 848                 cursor = lastRet;
 849                 lastRet = -1;
 850                 expectedModCount = modCount;
 851             } catch (IndexOutOfBoundsException ex) {
 852                 throw new ConcurrentModificationException();
 853             }
 854         }
 855 
 856         final void checkForComodification() {
 857             if (modCount != expectedModCount)
 858                 throw new ConcurrentModificationException();
 859         }
 860     }
 861 
 862     /**
 863      * An optimized version of AbstractList.ListItr
 864      */
 865     private class ListItr extends Itr implements ListIterator<E> {
 866         ListItr(int index) {
 867             super();
 868             cursor = index;
 869         }
 870 
 871         public boolean hasPrevious() {
 872             return cursor != 0;
 873         }
 874 
 875         public int nextIndex() {
 876             return cursor;
 877         }
 878 
 879         public int previousIndex() {
 880             return cursor - 1;
 881         }
 882 
 883         @SuppressWarnings("unchecked")
 884         public E previous() {
 885             checkForComodification();
 886             int i = cursor - 1;
 887             if (i < 0)
 888                 throw new NoSuchElementException();
 889             Object[] elementData = ArrayList.this.elementData;
 890             if (i >= elementData.length)
 891                 throw new ConcurrentModificationException();
 892             cursor = i;
 893             return (E) elementData[lastRet = i];
 894         }
 895 
 896         public void set(E e) {
 897             if (lastRet < 0)
 898                 throw new IllegalStateException();
 899             checkForComodification();
 900 
 901             try {
 902                 ArrayList.this.set(lastRet, e);
 903             } catch (IndexOutOfBoundsException ex) {
 904                 throw new ConcurrentModificationException();
 905             }
 906         }
 907 
 908         public void add(E e) {
 909             checkForComodification();
 910 
 911             try {
 912                 int i = cursor;
 913                 ArrayList.this.add(i, e);
 914                 cursor = i + 1;
 915                 lastRet = -1;
 916                 expectedModCount = modCount;
 917             } catch (IndexOutOfBoundsException ex) {
 918                 throw new ConcurrentModificationException();
 919             }
 920         }
 921     }
 922 
 923     /**
 924      * Returns a view of the portion of this list between the specified
 925      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If
 926      * {@code fromIndex} and {@code toIndex} are equal, the returned list is
 927      * empty.)  The returned list is backed by this list, so non-structural
 928      * changes in the returned list are reflected in this list, and vice-versa.
 929      * The returned list supports all of the optional list operations.
 930      *
 931      * <p>This method eliminates the need for explicit range operations (of
 932      * the sort that commonly exist for arrays).  Any operation that expects
 933      * a list can be used as a range operation by passing a subList view
 934      * instead of a whole list.  For example, the following idiom
 935      * removes a range of elements from a list:
 936      * <pre>
 937      *      list.subList(from, to).clear();
 938      * </pre>
 939      * Similar idioms may be constructed for {@link #indexOf(Object)} and
 940      * {@link #lastIndexOf(Object)}, and all of the algorithms in the
 941      * {@link Collections} class can be applied to a subList.
 942      *
 943      * <p>The semantics of the list returned by this method become undefined if
 944      * the backing list (i.e., this list) is <i>structurally modified</i> in
 945      * any way other than via the returned list.  (Structural modifications are
 946      * those that change the size of this list, or otherwise perturb it in such
 947      * a fashion that iterations in progress may yield incorrect results.)
 948      *
 949      * @throws IndexOutOfBoundsException {@inheritDoc}
 950      * @throws IllegalArgumentException {@inheritDoc}
 951      */
 952     public List<E> subList(int fromIndex, int toIndex) {
 953         subListRangeCheck(fromIndex, toIndex, size);
 954         return new SubList(this, 0, fromIndex, toIndex);
 955     }
 956 
 957     static void subListRangeCheck(int fromIndex, int toIndex, int size) {
 958         if (fromIndex < 0)
 959             throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 960         if (toIndex > size)
 961             throw new IndexOutOfBoundsException("toIndex = " + toIndex);
 962         if (fromIndex > toIndex)
 963             throw new IllegalArgumentException("fromIndex(" + fromIndex +
 964                                                ") > toIndex(" + toIndex + ")");
 965     }
 966 
 967     private class SubList extends AbstractList<E> implements RandomAccess {
 968         private final AbstractList<E> parent;
 969         private final int parentOffset;
 970         private final int offset;
 971         int size;
 972 
 973         SubList(AbstractList<E> parent,
 974                 int offset, int fromIndex, int toIndex) {
 975             this.parent = parent;
 976             this.parentOffset = fromIndex;
 977             this.offset = offset + fromIndex;
 978             this.size = toIndex - fromIndex;
 979             this.modCount = ArrayList.this.modCount;
 980         }
 981 
 982         public E set(int index, E e) {
 983             rangeCheck(index);
 984             checkForComodification();
 985             E oldValue = ArrayList.this.elementData(offset + index);
 986             ArrayList.this.elementData[offset + index] = e;
 987             return oldValue;
 988         }
 989 
 990         public E get(int index) {
 991             rangeCheck(index);
 992             checkForComodification();
 993             return ArrayList.this.elementData(offset + index);
 994         }
 995 
 996         public int size() {
 997             checkForComodification();
 998             return this.size;
 999         }
1000 
1001         public void add(int index, E e) {
1002             rangeCheckForAdd(index);
1003             checkForComodification();
1004             parent.add(parentOffset + index, e);
1005             this.modCount = parent.modCount;
1006             this.size++;
1007         }
1008 
1009         public E remove(int index) {
1010             rangeCheck(index);
1011             checkForComodification();
1012             E result = parent.remove(parentOffset + index);
1013             this.modCount = parent.modCount;
1014             this.size--;
1015             return result;
1016         }
1017 
1018         protected void removeRange(int fromIndex, int toIndex) {
1019             checkForComodification();
1020             parent.removeRange(parentOffset + fromIndex,
1021                                parentOffset + toIndex);
1022             this.modCount = parent.modCount;
1023             this.size -= toIndex - fromIndex;
1024         }
1025 
1026         public boolean addAll(Collection<? extends E> c) {
1027             return addAll(this.size, c);
1028         }
1029 
1030         public boolean addAll(int index, Collection<? extends E> c) {
1031             rangeCheckForAdd(index);
1032             int cSize = c.size();
1033             if (cSize==0)
1034                 return false;
1035 
1036             checkForComodification();
1037             parent.addAll(parentOffset + index, c);
1038             this.modCount = parent.modCount;
1039             this.size += cSize;
1040             return true;
1041         }
1042 
1043         public Iterator<E> iterator() {
1044             return listIterator();
1045         }
1046 
1047         public ListIterator<E> listIterator(final int index) {
1048             checkForComodification();
1049             rangeCheckForAdd(index);
1050             final int offset = this.offset;
1051 
1052             return new ListIterator<E>() {
1053                 int cursor = index;
1054                 int lastRet = -1;
1055                 int expectedModCount = ArrayList.this.modCount;
1056 
1057                 public boolean hasNext() {
1058                     return cursor != SubList.this.size;
1059                 }
1060 
1061                 @SuppressWarnings("unchecked")
1062                 public E next() {
1063                     checkForComodification();
1064                     int i = cursor;
1065                     if (i >= SubList.this.size)
1066                         throw new NoSuchElementException();
1067                     Object[] elementData = ArrayList.this.elementData;
1068                     if (offset + i >= elementData.length)
1069                         throw new ConcurrentModificationException();
1070                     cursor = i + 1;
1071                     return (E) elementData[offset + (lastRet = i)];
1072                 }
1073 
1074                 public boolean hasPrevious() {
1075                     return cursor != 0;
1076                 }
1077 
1078                 @SuppressWarnings("unchecked")
1079                 public E previous() {
1080                     checkForComodification();
1081                     int i = cursor - 1;
1082                     if (i < 0)
1083                         throw new NoSuchElementException();
1084                     Object[] elementData = ArrayList.this.elementData;
1085                     if (offset + i >= elementData.length)
1086                         throw new ConcurrentModificationException();
1087                     cursor = i;
1088                     return (E) elementData[offset + (lastRet = i)];
1089                 }
1090 
1091                 public int nextIndex() {
1092                     return cursor;
1093                 }
1094 
1095                 public int previousIndex() {
1096                     return cursor - 1;
1097                 }
1098 
1099                 public void remove() {
1100                     if (lastRet < 0)
1101                         throw new IllegalStateException();
1102                     checkForComodification();
1103 
1104                     try {
1105                         SubList.this.remove(lastRet);
1106                         cursor = lastRet;
1107                         lastRet = -1;
1108                         expectedModCount = ArrayList.this.modCount;
1109                     } catch (IndexOutOfBoundsException ex) {
1110                         throw new ConcurrentModificationException();
1111                     }
1112                 }
1113 
1114                 public void set(E e) {
1115                     if (lastRet < 0)
1116                         throw new IllegalStateException();
1117                     checkForComodification();
1118 
1119                     try {
1120                         ArrayList.this.set(offset + lastRet, e);
1121                     } catch (IndexOutOfBoundsException ex) {
1122                         throw new ConcurrentModificationException();
1123                     }
1124                 }
1125 
1126                 public void add(E e) {
1127                     checkForComodification();
1128 
1129                     try {
1130                         int i = cursor;
1131                         SubList.this.add(i, e);
1132                         cursor = i + 1;
1133                         lastRet = -1;
1134                         expectedModCount = ArrayList.this.modCount;
1135                     } catch (IndexOutOfBoundsException ex) {
1136                         throw new ConcurrentModificationException();
1137                     }
1138                 }
1139 
1140                 final void checkForComodification() {
1141                     if (expectedModCount != ArrayList.this.modCount)
1142                         throw new ConcurrentModificationException();
1143                 }
1144             };
1145         }
1146 
1147         public List<E> subList(int fromIndex, int toIndex) {
1148             subListRangeCheck(fromIndex, toIndex, size);
1149             return new SubList(this, offset, fromIndex, toIndex);
1150         }
1151 
1152         private void rangeCheck(int index) {
1153             if (index < 0 || index >= this.size)
1154                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1155         }
1156 
1157         private void rangeCheckForAdd(int index) {
1158             if (index < 0 || index > this.size)
1159                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1160         }
1161 
1162         private String outOfBoundsMsg(int index) {
1163             return "Index: "+index+", Size: "+this.size;
1164         }
1165 
1166         private void checkForComodification() {
1167             if (ArrayList.this.modCount != this.modCount)
1168                 throw new ConcurrentModificationException();
1169         }
1170     }
1171 }