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         if ((minCapacity > 0) &&
 192             ((elementData != EMPTY_ELEMENTDATA) ||
 193             ((minCapacity > DEFAULT_CAPACITY)))) {
 194             ensureExplicitCapacity(minCapacity);
 195         }
 196     }
 197 
 198     private void ensureCapacityInternal(int minCapacity) {
 199         if (elementData == EMPTY_ELEMENTDATA) {
 200             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 201         }
 202 
 203         ensureExplicitCapacity(minCapacity);
 204     }
 205 
 206     private void ensureExplicitCapacity(int minCapacity) {
 207         modCount++;
 208 
 209         // overflow-conscious code
 210         if (minCapacity - elementData.length > 0)
 211             grow(minCapacity);
 212     }
 213 
 214     /**
 215      * The maximum size of array to allocate.
 216      * Some VMs reserve some header words in an array.
 217      * Attempts to allocate larger arrays may result in
 218      * OutOfMemoryError: Requested array size exceeds VM limit
 219      */
 220     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 221 
 222     /**
 223      * Increases the capacity to ensure that it can hold at least the
 224      * number of elements specified by the minimum capacity argument.
 225      *
 226      * @param minCapacity the desired minimum capacity
 227      */
 228     private void grow(int minCapacity) {
 229         // overflow-conscious code
 230         int oldCapacity = elementData.length;
 231         int newCapacity = oldCapacity + (oldCapacity >> 1);
 232         if (newCapacity - minCapacity < 0)
 233             newCapacity = minCapacity;
 234         if (newCapacity - MAX_ARRAY_SIZE > 0)
 235             newCapacity = hugeCapacity(minCapacity);
 236         // minCapacity is usually close to size, so this is a win:
 237         elementData = Arrays.copyOf(elementData, newCapacity);
 238     }
 239 
 240     private static int hugeCapacity(int minCapacity) {
 241         if (minCapacity < 0) // overflow
 242             throw new OutOfMemoryError();
 243         return (minCapacity > MAX_ARRAY_SIZE) ?
 244             Integer.MAX_VALUE :
 245             MAX_ARRAY_SIZE;
 246     }
 247 
 248     /**
 249      * Returns the number of elements in this list.
 250      *
 251      * @return the number of elements in this list
 252      */
 253     public int size() {
 254         return size;
 255     }
 256 
 257     /**
 258      * Returns <tt>true</tt> if this list contains no elements.
 259      *
 260      * @return <tt>true</tt> if this list contains no elements
 261      */
 262     public boolean isEmpty() {
 263         return size == 0;
 264     }
 265 
 266     /**
 267      * Returns <tt>true</tt> if this list contains the specified element.
 268      * More formally, returns <tt>true</tt> if and only if this list contains
 269      * at least one element <tt>e</tt> such that
 270      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 271      *
 272      * @param o element whose presence in this list is to be tested
 273      * @return <tt>true</tt> if this list contains the specified element
 274      */
 275     public boolean contains(Object o) {
 276         return indexOf(o) >= 0;
 277     }
 278 
 279     /**
 280      * Returns the index of the first occurrence of the specified element
 281      * in this list, or -1 if this list does not contain the element.
 282      * More formally, returns the lowest index <tt>i</tt> such that
 283      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 284      * or -1 if there is no such index.
 285      */
 286     public int indexOf(Object o) {
 287         if (o == null) {
 288             for (int i = 0; i < size; i++)
 289                 if (elementData[i]==null)
 290                     return i;
 291         } else {
 292             for (int i = 0; i < size; i++)
 293                 if (o.equals(elementData[i]))
 294                     return i;
 295         }
 296         return -1;
 297     }
 298 
 299     /**
 300      * Returns the index of the last occurrence of the specified element
 301      * in this list, or -1 if this list does not contain the element.
 302      * More formally, returns the highest index <tt>i</tt> such that
 303      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 304      * or -1 if there is no such index.
 305      */
 306     public int lastIndexOf(Object o) {
 307         if (o == null) {
 308             for (int i = size-1; i >= 0; i--)
 309                 if (elementData[i]==null)
 310                     return i;
 311         } else {
 312             for (int i = size-1; i >= 0; i--)
 313                 if (o.equals(elementData[i]))
 314                     return i;
 315         }
 316         return -1;
 317     }
 318 
 319     /**
 320      * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
 321      * elements themselves are not copied.)
 322      *
 323      * @return a clone of this <tt>ArrayList</tt> instance
 324      */
 325     public Object clone() {
 326         try {
 327             ArrayList<?> v = (ArrayList<?>) super.clone();
 328             v.elementData = Arrays.copyOf(elementData, size);
 329             v.modCount = 0;
 330             return v;
 331         } catch (CloneNotSupportedException e) {
 332             // this shouldn't happen, since we are Cloneable
 333             throw new InternalError(e);
 334         }
 335     }
 336 
 337     /**
 338      * Returns an array containing all of the elements in this list
 339      * in proper sequence (from first to last element).
 340      *
 341      * <p>The returned array will be "safe" in that no references to it are
 342      * maintained by this list.  (In other words, this method must allocate
 343      * a new array).  The caller is thus free to modify the returned array.
 344      *
 345      * <p>This method acts as bridge between array-based and collection-based
 346      * APIs.
 347      *
 348      * @return an array containing all of the elements in this list in
 349      *         proper sequence
 350      */
 351     public Object[] toArray() {
 352         return Arrays.copyOf(elementData, size);
 353     }
 354 
 355     /**
 356      * Returns an array containing all of the elements in this list in proper
 357      * sequence (from first to last element); the runtime type of the returned
 358      * array is that of the specified array.  If the list fits in the
 359      * specified array, it is returned therein.  Otherwise, a new array is
 360      * allocated with the runtime type of the specified array and the size of
 361      * this list.
 362      *
 363      * <p>If the list fits in the specified array with room to spare
 364      * (i.e., the array has more elements than the list), the element in
 365      * the array immediately following the end of the collection is set to
 366      * <tt>null</tt>.  (This is useful in determining the length of the
 367      * list <i>only</i> if the caller knows that the list does not contain
 368      * any null elements.)
 369      *
 370      * @param a the array into which the elements of the list are to
 371      *          be stored, if it is big enough; otherwise, a new array of the
 372      *          same runtime type is allocated for this purpose.
 373      * @return an array containing the elements of the list
 374      * @throws ArrayStoreException if the runtime type of the specified array
 375      *         is not a supertype of the runtime type of every element in
 376      *         this list
 377      * @throws NullPointerException if the specified array is null
 378      */
 379     @SuppressWarnings("unchecked")
 380     public <T> T[] toArray(T[] a) {
 381         if (a.length < size)
 382             // Make a new array of a's runtime type, but my contents:
 383             return (T[]) Arrays.copyOf(elementData, size, a.getClass());
 384         System.arraycopy(elementData, 0, a, 0, size);
 385         if (a.length > size)
 386             a[size] = null;
 387         return a;
 388     }
 389 
 390     // Positional Access Operations
 391 
 392     @SuppressWarnings("unchecked")
 393     E elementData(int index) {
 394         return (E) elementData[index];
 395     }
 396 
 397     /**
 398      * Returns the element at the specified position in this list.
 399      *
 400      * @param  index index of the element to return
 401      * @return the element at the specified position in this list
 402      * @throws IndexOutOfBoundsException {@inheritDoc}
 403      */
 404     public E get(int index) {
 405         rangeCheck(index);
 406 
 407         return elementData(index);
 408     }
 409 
 410     /**
 411      * Replaces the element at the specified position in this list with
 412      * the specified element.
 413      *
 414      * @param index index of the element to replace
 415      * @param element element to be stored at the specified position
 416      * @return the element previously at the specified position
 417      * @throws IndexOutOfBoundsException {@inheritDoc}
 418      */
 419     public E set(int index, E element) {
 420         rangeCheck(index);
 421 
 422         E oldValue = elementData(index);
 423         elementData[index] = element;
 424         return oldValue;
 425     }
 426 
 427     /**
 428      * Appends the specified element to the end of this list.
 429      *
 430      * @param e element to be appended to this list
 431      * @return <tt>true</tt> (as specified by {@link Collection#add})
 432      */
 433     public boolean add(E e) {
 434         ensureCapacityInternal(size + 1);  // Increments modCount!!
 435         elementData[size++] = e;
 436         return true;
 437     }
 438 
 439     /**
 440      * Inserts the specified element at the specified position in this
 441      * list. Shifts the element currently at that position (if any) and
 442      * any subsequent elements to the right (adds one to their indices).
 443      *
 444      * @param index index at which the specified element is to be inserted
 445      * @param element element to be inserted
 446      * @throws IndexOutOfBoundsException {@inheritDoc}
 447      */
 448     public void add(int index, E element) {
 449         rangeCheckForAdd(index);
 450 
 451         ensureCapacityInternal(size + 1);  // Increments modCount!!
 452         System.arraycopy(elementData, index, elementData, index + 1,
 453                          size - index);
 454         elementData[index] = element;
 455         size++;
 456     }
 457 
 458     /**
 459      * Removes the element at the specified position in this list.
 460      * Shifts any subsequent elements to the left (subtracts one from their
 461      * indices).
 462      *
 463      * @param index the index of the element to be removed
 464      * @return the element that was removed from the list
 465      * @throws IndexOutOfBoundsException {@inheritDoc}
 466      */
 467     public E remove(int index) {
 468         rangeCheck(index);
 469 
 470         modCount++;
 471         E oldValue = elementData(index);
 472 
 473         int numMoved = size - index - 1;
 474         if (numMoved > 0)
 475             System.arraycopy(elementData, index+1, elementData, index,
 476                              numMoved);
 477         elementData[--size] = null; // clear to let GC do its work
 478 
 479         return oldValue;
 480     }
 481 
 482     /**
 483      * Removes the first occurrence of the specified element from this list,
 484      * if it is present.  If the list does not contain the element, it is
 485      * unchanged.  More formally, removes the element with the lowest index
 486      * <tt>i</tt> such that
 487      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 488      * (if such an element exists).  Returns <tt>true</tt> if this list
 489      * contained the specified element (or equivalently, if this list
 490      * changed as a result of the call).
 491      *
 492      * @param o element to be removed from this list, if present
 493      * @return <tt>true</tt> if this list contained the specified element
 494      */
 495     public boolean remove(Object o) {
 496         if (o == null) {
 497             for (int index = 0; index < size; index++)
 498                 if (elementData[index] == null) {
 499                     fastRemove(index);
 500                     return true;
 501                 }
 502         } else {
 503             for (int index = 0; index < size; index++)
 504                 if (o.equals(elementData[index])) {
 505                     fastRemove(index);
 506                     return true;
 507                 }
 508         }
 509         return false;
 510     }
 511 
 512     /*
 513      * Private remove method that skips bounds checking and does not
 514      * return the value removed.
 515      */
 516     private void fastRemove(int index) {
 517         modCount++;
 518         int numMoved = size - index - 1;
 519         if (numMoved > 0)
 520             System.arraycopy(elementData, index+1, elementData, index,
 521                              numMoved);
 522         elementData[--size] = null; // clear to let GC do its work
 523     }
 524 
 525     /**
 526      * Removes all of the elements from this list.  The list will
 527      * be empty after this call returns.
 528      */
 529     public void clear() {
 530         modCount++;
 531 
 532         // clear to let GC do its work
 533         for (int i = 0; i < size; i++)
 534             elementData[i] = null;
 535 
 536         size = 0;
 537     }
 538 
 539     /**
 540      * Appends all of the elements in the specified collection to the end of
 541      * this list, in the order that they are returned by the
 542      * specified collection's Iterator.  The behavior of this operation is
 543      * undefined if the specified collection is modified while the operation
 544      * is in progress.  (This implies that the behavior of this call is
 545      * undefined if the specified collection is this list, and this
 546      * list is nonempty.)
 547      *
 548      * @param c collection containing elements to be added to this list
 549      * @return <tt>true</tt> if this list changed as a result of the call
 550      * @throws NullPointerException if the specified collection is null
 551      */
 552     public boolean addAll(Collection<? extends E> c) {
 553         Object[] a = c.toArray();
 554         int numNew = a.length;
 555         ensureCapacityInternal(size + numNew);  // Increments modCount
 556         System.arraycopy(a, 0, elementData, size, numNew);
 557         size += numNew;
 558         return numNew != 0;
 559     }
 560 
 561     /**
 562      * Inserts all of the elements in the specified collection into this
 563      * list, starting at the specified position.  Shifts the element
 564      * currently at that position (if any) and any subsequent elements to
 565      * the right (increases their indices).  The new elements will appear
 566      * in the list in the order that they are returned by the
 567      * specified collection's iterator.
 568      *
 569      * @param index index at which to insert the first element from the
 570      *              specified collection
 571      * @param c collection containing elements to be added to this list
 572      * @return <tt>true</tt> if this list changed as a result of the call
 573      * @throws IndexOutOfBoundsException {@inheritDoc}
 574      * @throws NullPointerException if the specified collection is null
 575      */
 576     public boolean addAll(int index, Collection<? extends E> c) {
 577         rangeCheckForAdd(index);
 578 
 579         Object[] a = c.toArray();
 580         int numNew = a.length;
 581         ensureCapacityInternal(size + numNew);  // Increments modCount
 582 
 583         int numMoved = size - index;
 584         if (numMoved > 0)
 585             System.arraycopy(elementData, index, elementData, index + numNew,
 586                              numMoved);
 587 
 588         System.arraycopy(a, 0, elementData, index, numNew);
 589         size += numNew;
 590         return numNew != 0;
 591     }
 592 
 593     /**
 594      * Removes from this list all of the elements whose index is between
 595      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 596      * Shifts any succeeding elements to the left (reduces their index).
 597      * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 598      * (If {@code toIndex==fromIndex}, this operation has no effect.)
 599      *
 600      * @throws IndexOutOfBoundsException if {@code fromIndex} or
 601      *         {@code toIndex} is out of range
 602      *         ({@code fromIndex < 0 ||
 603      *          fromIndex >= size() ||
 604      *          toIndex > size() ||
 605      *          toIndex < fromIndex})
 606      */
 607     protected void removeRange(int fromIndex, int toIndex) {
 608         modCount++;
 609         int numMoved = size - toIndex;
 610         System.arraycopy(elementData, toIndex, elementData, fromIndex,
 611                          numMoved);
 612 
 613         // clear to let GC do its work
 614         int newSize = size - (toIndex-fromIndex);
 615         for (int i = newSize; i < size; i++) {
 616             elementData[i] = null;
 617         }
 618         size = newSize;
 619     }
 620 
 621     /**
 622      * Checks if the given index is in range.  If not, throws an appropriate
 623      * runtime exception.  This method does *not* check if the index is
 624      * negative: It is always used immediately prior to an array access,
 625      * which throws an ArrayIndexOutOfBoundsException if index is negative.
 626      */
 627     private void rangeCheck(int index) {
 628         if (index >= size)
 629             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 630     }
 631 
 632     /**
 633      * A version of rangeCheck used by add and addAll.
 634      */
 635     private void rangeCheckForAdd(int index) {
 636         if (index > size || index < 0)
 637             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 638     }
 639 
 640     /**
 641      * Constructs an IndexOutOfBoundsException detail message.
 642      * Of the many possible refactorings of the error handling code,
 643      * this "outlining" performs best with both server and client VMs.
 644      */
 645     private String outOfBoundsMsg(int index) {
 646         return "Index: "+index+", Size: "+size;
 647     }
 648 
 649     /**
 650      * Removes from this list all of its elements that are contained in the
 651      * specified collection.
 652      *
 653      * @param c collection containing elements to be removed from this list
 654      * @return {@code true} if this list changed as a result of the call
 655      * @throws ClassCastException if the class of an element of this list
 656      *         is incompatible with the specified collection
 657      * (<a href="Collection.html#optional-restrictions">optional</a>)
 658      * @throws NullPointerException if this list contains a null element and the
 659      *         specified collection does not permit null elements
 660      * (<a href="Collection.html#optional-restrictions">optional</a>),
 661      *         or if the specified collection is null
 662      * @see Collection#contains(Object)
 663      */
 664     public boolean removeAll(Collection<?> c) {
 665         return batchRemove(c, false);
 666     }
 667 
 668     /**
 669      * Retains only the elements in this list that are contained in the
 670      * specified collection.  In other words, removes from this list all
 671      * of its elements that are not contained in the specified collection.
 672      *
 673      * @param c collection containing elements to be retained in this list
 674      * @return {@code true} if this list changed as a result of the call
 675      * @throws ClassCastException if the class of an element of this list
 676      *         is incompatible with the specified collection
 677      * (<a href="Collection.html#optional-restrictions">optional</a>)
 678      * @throws NullPointerException if this list contains a null element and the
 679      *         specified collection does not permit null elements
 680      * (<a href="Collection.html#optional-restrictions">optional</a>),
 681      *         or if the specified collection is null
 682      * @see Collection#contains(Object)
 683      */
 684     public boolean retainAll(Collection<?> c) {
 685         return batchRemove(c, true);
 686     }
 687 
 688     private boolean batchRemove(Collection<?> c, boolean complement) {
 689         final Object[] elementData = this.elementData;
 690         int r = 0, w = 0;
 691         boolean modified = false;
 692         try {
 693             for (; r < size; r++)
 694                 if (c.contains(elementData[r]) == complement)
 695                     elementData[w++] = elementData[r];
 696         } finally {
 697             // Preserve behavioral compatibility with AbstractCollection,
 698             // even if c.contains() throws.
 699             if (r != size) {
 700                 System.arraycopy(elementData, r,
 701                                  elementData, w,
 702                                  size - r);
 703                 w += size - r;
 704             }
 705             if (w != size) {
 706                 // clear to let GC do its work
 707                 for (int i = w; i < size; i++)
 708                     elementData[i] = null;
 709                 modCount += size - w;
 710                 size = w;
 711                 modified = true;
 712             }
 713         }
 714         return modified;
 715     }
 716 
 717     /**
 718      * Save the state of the <tt>ArrayList</tt> instance to a stream (that
 719      * is, serialize it).
 720      *
 721      * @serialData The length of the array backing the <tt>ArrayList</tt>
 722      *             instance is emitted (int), followed by all of its elements
 723      *             (each an <tt>Object</tt>) in the proper order.
 724      */
 725     private void writeObject(java.io.ObjectOutputStream s)
 726         throws java.io.IOException{
 727         // Write out element count, and any hidden stuff
 728         int expectedModCount = modCount;
 729         s.defaultWriteObject();
 730 
 731         // Write out size as capacity for behavioural compatibility with clone()
 732         s.writeInt(size);
 733 
 734         // Write out all elements in the proper order.
 735         for (int i=0; i<size; i++) {
 736             s.writeObject(elementData[i]);
 737         }
 738 
 739         if (modCount != expectedModCount) {
 740             throw new ConcurrentModificationException();
 741         }
 742     }
 743 
 744     /**
 745      * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
 746      * deserialize it).
 747      */
 748     private void readObject(java.io.ObjectInputStream s)
 749         throws java.io.IOException, ClassNotFoundException {
 750          elementData = EMPTY_ELEMENTDATA;
 751 
 752         // Read in size, and any hidden stuff
 753         s.defaultReadObject();
 754 
 755         // Read in capacity
 756         s.readInt(); // ignored
 757 
 758         if (size > 0) {
 759             // be like clone(), allocate array based upon size not capacity
 760             ensureCapacityInternal(size);
 761 
 762             Object[] a = elementData;
 763             // Read in all elements in the proper order.
 764             for (int i=0; i<size; i++) {
 765                 a[i] = s.readObject();
 766             }
 767         }
 768     }
 769 
 770     /**
 771      * Returns a list iterator over the elements in this list (in proper
 772      * sequence), starting at the specified position in the list.
 773      * The specified index indicates the first element that would be
 774      * returned by an initial call to {@link ListIterator#next next}.
 775      * An initial call to {@link ListIterator#previous previous} would
 776      * return the element with the specified index minus one.
 777      *
 778      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 779      *
 780      * @throws IndexOutOfBoundsException {@inheritDoc}
 781      */
 782     public ListIterator<E> listIterator(int index) {
 783         if (index < 0 || index > size)
 784             throw new IndexOutOfBoundsException("Index: "+index);
 785         return new ListItr(index);
 786     }
 787 
 788     /**
 789      * Returns a list iterator over the elements in this list (in proper
 790      * sequence).
 791      *
 792      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 793      *
 794      * @see #listIterator(int)
 795      */
 796     public ListIterator<E> listIterator() {
 797         return new ListItr(0);
 798     }
 799 
 800     /**
 801      * Returns an iterator over the elements in this list in proper sequence.
 802      *
 803      * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 804      *
 805      * @return an iterator over the elements in this list in proper sequence
 806      */
 807     public Iterator<E> iterator() {
 808         return new Itr();
 809     }
 810 
 811     /**
 812      * An optimized version of AbstractList.Itr
 813      */
 814     private class Itr implements Iterator<E> {
 815         int cursor;       // index of next element to return
 816         int lastRet = -1; // index of last element returned; -1 if no such
 817         int expectedModCount = modCount;
 818 
 819         public boolean hasNext() {
 820             return cursor != size;
 821         }
 822 
 823         @SuppressWarnings("unchecked")
 824         public E next() {
 825             checkForComodification();
 826             int i = cursor;
 827             if (i >= size)
 828                 throw new NoSuchElementException();
 829             Object[] elementData = ArrayList.this.elementData;
 830             if (i >= elementData.length)
 831                 throw new ConcurrentModificationException();
 832             cursor = i + 1;
 833             return (E) elementData[lastRet = i];
 834         }
 835 
 836         public void remove() {
 837             if (lastRet < 0)
 838                 throw new IllegalStateException();
 839             checkForComodification();
 840 
 841             try {
 842                 ArrayList.this.remove(lastRet);
 843                 cursor = lastRet;
 844                 lastRet = -1;
 845                 expectedModCount = modCount;
 846             } catch (IndexOutOfBoundsException ex) {
 847                 throw new ConcurrentModificationException();
 848             }
 849         }
 850 
 851         final void checkForComodification() {
 852             if (modCount != expectedModCount)
 853                 throw new ConcurrentModificationException();
 854         }
 855     }
 856 
 857     /**
 858      * An optimized version of AbstractList.ListItr
 859      */
 860     private class ListItr extends Itr implements ListIterator<E> {
 861         ListItr(int index) {
 862             super();
 863             cursor = index;
 864         }
 865 
 866         public boolean hasPrevious() {
 867             return cursor != 0;
 868         }
 869 
 870         public int nextIndex() {
 871             return cursor;
 872         }
 873 
 874         public int previousIndex() {
 875             return cursor - 1;
 876         }
 877 
 878         @SuppressWarnings("unchecked")
 879         public E previous() {
 880             checkForComodification();
 881             int i = cursor - 1;
 882             if (i < 0)
 883                 throw new NoSuchElementException();
 884             Object[] elementData = ArrayList.this.elementData;
 885             if (i >= elementData.length)
 886                 throw new ConcurrentModificationException();
 887             cursor = i;
 888             return (E) elementData[lastRet = i];
 889         }
 890 
 891         public void set(E e) {
 892             if (lastRet < 0)
 893                 throw new IllegalStateException();
 894             checkForComodification();
 895 
 896             try {
 897                 ArrayList.this.set(lastRet, e);
 898             } catch (IndexOutOfBoundsException ex) {
 899                 throw new ConcurrentModificationException();
 900             }
 901         }
 902 
 903         public void add(E e) {
 904             checkForComodification();
 905 
 906             try {
 907                 int i = cursor;
 908                 ArrayList.this.add(i, e);
 909                 cursor = i + 1;
 910                 lastRet = -1;
 911                 expectedModCount = modCount;
 912             } catch (IndexOutOfBoundsException ex) {
 913                 throw new ConcurrentModificationException();
 914             }
 915         }
 916     }
 917 
 918     /**
 919      * Returns a view of the portion of this list between the specified
 920      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If
 921      * {@code fromIndex} and {@code toIndex} are equal, the returned list is
 922      * empty.)  The returned list is backed by this list, so non-structural
 923      * changes in the returned list are reflected in this list, and vice-versa.
 924      * The returned list supports all of the optional list operations.
 925      *
 926      * <p>This method eliminates the need for explicit range operations (of
 927      * the sort that commonly exist for arrays).  Any operation that expects
 928      * a list can be used as a range operation by passing a subList view
 929      * instead of a whole list.  For example, the following idiom
 930      * removes a range of elements from a list:
 931      * <pre>
 932      *      list.subList(from, to).clear();
 933      * </pre>
 934      * Similar idioms may be constructed for {@link #indexOf(Object)} and
 935      * {@link #lastIndexOf(Object)}, and all of the algorithms in the
 936      * {@link Collections} class can be applied to a subList.
 937      *
 938      * <p>The semantics of the list returned by this method become undefined if
 939      * the backing list (i.e., this list) is <i>structurally modified</i> in
 940      * any way other than via the returned list.  (Structural modifications are
 941      * those that change the size of this list, or otherwise perturb it in such
 942      * a fashion that iterations in progress may yield incorrect results.)
 943      *
 944      * @throws IndexOutOfBoundsException {@inheritDoc}
 945      * @throws IllegalArgumentException {@inheritDoc}
 946      */
 947     public List<E> subList(int fromIndex, int toIndex) {
 948         subListRangeCheck(fromIndex, toIndex, size);
 949         return new SubList(this, 0, fromIndex, toIndex);
 950     }
 951 
 952     static void subListRangeCheck(int fromIndex, int toIndex, int size) {
 953         if (fromIndex < 0)
 954             throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 955         if (toIndex > size)
 956             throw new IndexOutOfBoundsException("toIndex = " + toIndex);
 957         if (fromIndex > toIndex)
 958             throw new IllegalArgumentException("fromIndex(" + fromIndex +
 959                                                ") > toIndex(" + toIndex + ")");
 960     }
 961 
 962     private class SubList extends AbstractList<E> implements RandomAccess {
 963         private final AbstractList<E> parent;
 964         private final int parentOffset;
 965         private final int offset;
 966         int size;
 967 
 968         SubList(AbstractList<E> parent,
 969                 int offset, int fromIndex, int toIndex) {
 970             this.parent = parent;
 971             this.parentOffset = fromIndex;
 972             this.offset = offset + fromIndex;
 973             this.size = toIndex - fromIndex;
 974             this.modCount = ArrayList.this.modCount;
 975         }
 976 
 977         public E set(int index, E e) {
 978             rangeCheck(index);
 979             checkForComodification();
 980             E oldValue = ArrayList.this.elementData(offset + index);
 981             ArrayList.this.elementData[offset + index] = e;
 982             return oldValue;
 983         }
 984 
 985         public E get(int index) {
 986             rangeCheck(index);
 987             checkForComodification();
 988             return ArrayList.this.elementData(offset + index);
 989         }
 990 
 991         public int size() {
 992             checkForComodification();
 993             return this.size;
 994         }
 995 
 996         public void add(int index, E e) {
 997             rangeCheckForAdd(index);
 998             checkForComodification();
 999             parent.add(parentOffset + index, e);
1000             this.modCount = parent.modCount;
1001             this.size++;
1002         }
1003 
1004         public E remove(int index) {
1005             rangeCheck(index);
1006             checkForComodification();
1007             E result = parent.remove(parentOffset + index);
1008             this.modCount = parent.modCount;
1009             this.size--;
1010             return result;
1011         }
1012 
1013         protected void removeRange(int fromIndex, int toIndex) {
1014             checkForComodification();
1015             parent.removeRange(parentOffset + fromIndex,
1016                                parentOffset + toIndex);
1017             this.modCount = parent.modCount;
1018             this.size -= toIndex - fromIndex;
1019         }
1020 
1021         public boolean addAll(Collection<? extends E> c) {
1022             return addAll(this.size, c);
1023         }
1024 
1025         public boolean addAll(int index, Collection<? extends E> c) {
1026             rangeCheckForAdd(index);
1027             int cSize = c.size();
1028             if (cSize==0)
1029                 return false;
1030 
1031             checkForComodification();
1032             parent.addAll(parentOffset + index, c);
1033             this.modCount = parent.modCount;
1034             this.size += cSize;
1035             return true;
1036         }
1037 
1038         public Iterator<E> iterator() {
1039             return listIterator();
1040         }
1041 
1042         public ListIterator<E> listIterator(final int index) {
1043             checkForComodification();
1044             rangeCheckForAdd(index);
1045             final int offset = this.offset;
1046 
1047             return new ListIterator<E>() {
1048                 int cursor = index;
1049                 int lastRet = -1;
1050                 int expectedModCount = ArrayList.this.modCount;
1051 
1052                 public boolean hasNext() {
1053                     return cursor != SubList.this.size;
1054                 }
1055 
1056                 @SuppressWarnings("unchecked")
1057                 public E next() {
1058                     checkForComodification();
1059                     int i = cursor;
1060                     if (i >= SubList.this.size)
1061                         throw new NoSuchElementException();
1062                     Object[] elementData = ArrayList.this.elementData;
1063                     if (offset + i >= elementData.length)
1064                         throw new ConcurrentModificationException();
1065                     cursor = i + 1;
1066                     return (E) elementData[offset + (lastRet = i)];
1067                 }
1068 
1069                 public boolean hasPrevious() {
1070                     return cursor != 0;
1071                 }
1072 
1073                 @SuppressWarnings("unchecked")
1074                 public E previous() {
1075                     checkForComodification();
1076                     int i = cursor - 1;
1077                     if (i < 0)
1078                         throw new NoSuchElementException();
1079                     Object[] elementData = ArrayList.this.elementData;
1080                     if (offset + i >= elementData.length)
1081                         throw new ConcurrentModificationException();
1082                     cursor = i;
1083                     return (E) elementData[offset + (lastRet = i)];
1084                 }
1085 
1086                 public int nextIndex() {
1087                     return cursor;
1088                 }
1089 
1090                 public int previousIndex() {
1091                     return cursor - 1;
1092                 }
1093 
1094                 public void remove() {
1095                     if (lastRet < 0)
1096                         throw new IllegalStateException();
1097                     checkForComodification();
1098 
1099                     try {
1100                         SubList.this.remove(lastRet);
1101                         cursor = lastRet;
1102                         lastRet = -1;
1103                         expectedModCount = ArrayList.this.modCount;
1104                     } catch (IndexOutOfBoundsException ex) {
1105                         throw new ConcurrentModificationException();
1106                     }
1107                 }
1108 
1109                 public void set(E e) {
1110                     if (lastRet < 0)
1111                         throw new IllegalStateException();
1112                     checkForComodification();
1113 
1114                     try {
1115                         ArrayList.this.set(offset + lastRet, e);
1116                     } catch (IndexOutOfBoundsException ex) {
1117                         throw new ConcurrentModificationException();
1118                     }
1119                 }
1120 
1121                 public void add(E e) {
1122                     checkForComodification();
1123 
1124                     try {
1125                         int i = cursor;
1126                         SubList.this.add(i, e);
1127                         cursor = i + 1;
1128                         lastRet = -1;
1129                         expectedModCount = ArrayList.this.modCount;
1130                     } catch (IndexOutOfBoundsException ex) {
1131                         throw new ConcurrentModificationException();
1132                     }
1133                 }
1134 
1135                 final void checkForComodification() {
1136                     if (expectedModCount != ArrayList.this.modCount)
1137                         throw new ConcurrentModificationException();
1138                 }
1139             };
1140         }
1141 
1142         public List<E> subList(int fromIndex, int toIndex) {
1143             subListRangeCheck(fromIndex, toIndex, size);
1144             return new SubList(this, offset, fromIndex, toIndex);
1145         }
1146 
1147         private void rangeCheck(int index) {
1148             if (index < 0 || index >= this.size)
1149                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1150         }
1151 
1152         private void rangeCheckForAdd(int index) {
1153             if (index < 0 || index > this.size)
1154                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1155         }
1156 
1157         private String outOfBoundsMsg(int index) {
1158             return "Index: "+index+", Size: "+this.size;
1159         }
1160 
1161         private void checkForComodification() {
1162             if (ArrayList.this.modCount != this.modCount)
1163                 throw new ConcurrentModificationException();
1164         }
1165     }
1166 }