1 /*
   2  * Copyright (c) 1997, 2016, 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 import java.util.function.Consumer;
  29 import java.util.function.Predicate;
  30 import java.util.function.UnaryOperator;
  31 
  32 /**
  33  * Resizable-array implementation of the {@code List} interface.  Implements
  34  * all optional list operations, and permits all elements, including
  35  * {@code null}.  In addition to implementing the {@code List} interface,
  36  * this class provides methods to manipulate the size of the array that is
  37  * used internally to store the list.  (This class is roughly equivalent to
  38  * {@code Vector}, except that it is unsynchronized.)
  39  *
  40  * <p>The {@code size}, {@code isEmpty}, {@code get}, {@code set},
  41  * {@code iterator}, and {@code listIterator} operations run in constant
  42  * time.  The {@code add} operation runs in <i>amortized constant time</i>,
  43  * that is, adding n elements requires O(n) time.  All of the other operations
  44  * run in linear time (roughly speaking).  The constant factor is low compared
  45  * to that for the {@code LinkedList} implementation.
  46  *
  47  * <p>Each {@code ArrayList} instance has a <i>capacity</i>.  The capacity is
  48  * the size of the array used to store the elements in the list.  It is always
  49  * at least as large as the list size.  As elements are added to an ArrayList,
  50  * its capacity grows automatically.  The details of the growth policy are not
  51  * specified beyond the fact that adding an element has constant amortized
  52  * time cost.
  53  *
  54  * <p>An application can increase the capacity of an {@code ArrayList} instance
  55  * before adding a large number of elements using the {@code ensureCapacity}
  56  * operation.  This may reduce the amount of incremental reallocation.
  57  *
  58  * <p><strong>Note that this implementation is not synchronized.</strong>
  59  * If multiple threads access an {@code ArrayList} instance concurrently,
  60  * and at least one of the threads modifies the list structurally, it
  61  * <i>must</i> be synchronized externally.  (A structural modification is
  62  * any operation that adds or deletes one or more elements, or explicitly
  63  * resizes the backing array; merely setting the value of an element is not
  64  * a structural modification.)  This is typically accomplished by
  65  * synchronizing on some object that naturally encapsulates the list.
  66  *
  67  * If no such object exists, the list should be "wrapped" using the
  68  * {@link Collections#synchronizedList Collections.synchronizedList}
  69  * method.  This is best done at creation time, to prevent accidental
  70  * unsynchronized access to the list:<pre>
  71  *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
  72  *
  73  * <p id="fail-fast">
  74  * The iterators returned by this class's {@link #iterator() iterator} and
  75  * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
  76  * if the list is structurally modified at any time after the iterator is
  77  * created, in any way except through the iterator's own
  78  * {@link ListIterator#remove() remove} or
  79  * {@link ListIterator#add(Object) add} methods, the iterator will throw a
  80  * {@link ConcurrentModificationException}.  Thus, in the face of
  81  * concurrent modification, the iterator fails quickly and cleanly, rather
  82  * than risking arbitrary, non-deterministic behavior at an undetermined
  83  * time in the future.
  84  *
  85  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  86  * as it is, generally speaking, impossible to make any hard guarantees in the
  87  * presence of unsynchronized concurrent modification.  Fail-fast iterators
  88  * throw {@code ConcurrentModificationException} on a best-effort basis.
  89  * Therefore, it would be wrong to write a program that depended on this
  90  * exception for its correctness:  <i>the fail-fast behavior of iterators
  91  * should be used only to detect bugs.</i>
  92  *
  93  * <p>This class is a member of the
  94  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  95  * Java Collections Framework</a>.
  96  *
  97  * @param <E> the type of elements in this list
  98  *
  99  * @author  Josh Bloch
 100  * @author  Neal Gafter
 101  * @see     Collection
 102  * @see     List
 103  * @see     LinkedList
 104  * @see     Vector
 105  * @since   1.2
 106  */
 107 
 108 public class ArrayList<E> extends AbstractList<E>
 109         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 110 {
 111     private static final long serialVersionUID = 8683452581122892189L;
 112 
 113     /**
 114      * Default initial capacity.
 115      */
 116     private static final int DEFAULT_CAPACITY = 10;
 117 
 118     /**
 119      * Shared empty array instance used for empty instances.
 120      */
 121     private static final Object[] EMPTY_ELEMENTDATA = {};
 122 
 123     /**
 124      * Shared empty array instance used for default sized empty instances. We
 125      * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 126      * first element is added.
 127      */
 128     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 129 
 130     /**
 131      * The array buffer into which the elements of the ArrayList are stored.
 132      * The capacity of the ArrayList is the length of this array buffer. Any
 133      * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 134      * will be expanded to DEFAULT_CAPACITY when the first element is added.
 135      */
 136     transient Object[] elementData; // non-private to simplify nested class access
 137 
 138     /**
 139      * The size of the ArrayList (the number of elements it contains).
 140      *
 141      * @serial
 142      */
 143     private int size;
 144 
 145     /**
 146      * Constructs an empty list with the specified initial capacity.
 147      *
 148      * @param  initialCapacity  the initial capacity of the list
 149      * @throws IllegalArgumentException if the specified initial capacity
 150      *         is negative
 151      */
 152     public ArrayList(int initialCapacity) {
 153         if (initialCapacity > 0) {
 154             this.elementData = new Object[initialCapacity];
 155         } else if (initialCapacity == 0) {
 156             this.elementData = EMPTY_ELEMENTDATA;
 157         } else {
 158             throw new IllegalArgumentException("Illegal Capacity: "+
 159                                                initialCapacity);
 160         }
 161     }
 162 
 163     /**
 164      * Constructs an empty list with an initial capacity of ten.
 165      */
 166     public ArrayList() {
 167         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 168     }
 169 
 170     /**
 171      * Constructs a list containing the elements of the specified
 172      * collection, in the order they are returned by the collection's
 173      * iterator.
 174      *
 175      * @param c the collection whose elements are to be placed into this list
 176      * @throws NullPointerException if the specified collection is null
 177      */
 178     public ArrayList(Collection<? extends E> c) {
 179         elementData = c.toArray();
 180         if ((size = elementData.length) != 0) {
 181             // defend against c.toArray (incorrectly) not returning Object[]
 182             // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
 183             if (elementData.getClass() != Object[].class)
 184                 elementData = Arrays.copyOf(elementData, size, Object[].class);
 185         } else {
 186             // replace with empty array.
 187             this.elementData = EMPTY_ELEMENTDATA;
 188         }
 189     }
 190 
 191     /**
 192      * Trims the capacity of this {@code ArrayList} instance to be the
 193      * list's current size.  An application can use this operation to minimize
 194      * the storage of an {@code ArrayList} instance.
 195      */
 196     public void trimToSize() {
 197         modCount++;
 198         if (size < elementData.length) {
 199             elementData = (size == 0)
 200               ? EMPTY_ELEMENTDATA
 201               : Arrays.copyOf(elementData, size);
 202         }
 203     }
 204 
 205     /**
 206      * Increases the capacity of this {@code ArrayList} instance, if
 207      * necessary, to ensure that it can hold at least the number of elements
 208      * specified by the minimum capacity argument.
 209      *
 210      * @param minCapacity the desired minimum capacity
 211      */
 212     public void ensureCapacity(int minCapacity) {
 213         if (minCapacity > elementData.length
 214             && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 215                  && minCapacity <= DEFAULT_CAPACITY)) {
 216             modCount++;
 217             grow(minCapacity);
 218         }
 219     }
 220 
 221     /**
 222      * The maximum size of array to allocate (unless necessary).
 223      * Some VMs reserve some header words in an array.
 224      * Attempts to allocate larger arrays may result in
 225      * OutOfMemoryError: Requested array size exceeds VM limit
 226      */
 227     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 228 
 229     /**
 230      * Increases the capacity to ensure that it can hold at least the
 231      * number of elements specified by the minimum capacity argument.
 232      *
 233      * @param minCapacity the desired minimum capacity
 234      * @throws OutOfMemoryError if minCapacity is less than zero
 235      */
 236     private Object[] grow(int minCapacity) {
 237         return elementData = Arrays.copyOf(elementData,
 238                                            newCapacity(minCapacity));
 239     }
 240 
 241     private Object[] grow() {
 242         return grow(size + 1);
 243     }
 244 
 245     /**
 246      * Returns a capacity at least as large as the given minimum capacity.
 247      * Returns the current capacity increased by 50% if that suffices.
 248      * Will not return a capacity greater than MAX_ARRAY_SIZE unless
 249      * the given minimum capacity is greater than MAX_ARRAY_SIZE.
 250      *
 251      * @param minCapacity the desired minimum capacity
 252      * @throws OutOfMemoryError if minCapacity is less than zero
 253      */
 254     private int newCapacity(int minCapacity) {
 255         // overflow-conscious code
 256         int oldCapacity = elementData.length;
 257         int newCapacity = oldCapacity + (oldCapacity >> 1);
 258         if (newCapacity - minCapacity <= 0) {
 259             if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
 260                 return Math.max(DEFAULT_CAPACITY, minCapacity);
 261             if (minCapacity < 0) // overflow
 262                 throw new OutOfMemoryError();
 263             return minCapacity;
 264         }
 265         return (newCapacity - MAX_ARRAY_SIZE <= 0)
 266             ? newCapacity
 267             : hugeCapacity(minCapacity);
 268     }
 269 
 270     private static int hugeCapacity(int minCapacity) {
 271         if (minCapacity < 0) // overflow
 272             throw new OutOfMemoryError();
 273         return (minCapacity > MAX_ARRAY_SIZE)
 274             ? Integer.MAX_VALUE
 275             : MAX_ARRAY_SIZE;
 276     }
 277 
 278     /**
 279      * Returns the number of elements in this list.
 280      *
 281      * @return the number of elements in this list
 282      */
 283     public int size() {
 284         return size;
 285     }
 286 
 287     /**
 288      * Returns {@code true} if this list contains no elements.
 289      *
 290      * @return {@code true} if this list contains no elements
 291      */
 292     public boolean isEmpty() {
 293         return size == 0;
 294     }
 295 
 296     /**
 297      * Returns {@code true} if this list contains the specified element.
 298      * More formally, returns {@code true} if and only if this list contains
 299      * at least one element {@code e} such that
 300      * {@code Objects.equals(o, e)}.
 301      *
 302      * @param o element whose presence in this list is to be tested
 303      * @return {@code true} if this list contains the specified element
 304      */
 305     public boolean contains(Object o) {
 306         return indexOf(o) >= 0;
 307     }
 308 
 309     /**
 310      * Returns the index of the first occurrence of the specified element
 311      * in this list, or -1 if this list does not contain the element.
 312      * More formally, returns the lowest index {@code i} such that
 313      * {@code Objects.equals(o, get(i))},
 314      * or -1 if there is no such index.
 315      */
 316     public int indexOf(Object o) {
 317         if (o == null) {
 318             for (int i = 0; i < size; i++)
 319                 if (elementData[i]==null)
 320                     return i;
 321         } else {
 322             for (int i = 0; i < size; i++)
 323                 if (o.equals(elementData[i]))
 324                     return i;
 325         }
 326         return -1;
 327     }
 328 
 329     /**
 330      * Returns the index of the last occurrence of the specified element
 331      * in this list, or -1 if this list does not contain the element.
 332      * More formally, returns the highest index {@code i} such that
 333      * {@code Objects.equals(o, get(i))},
 334      * or -1 if there is no such index.
 335      */
 336     public int lastIndexOf(Object o) {
 337         if (o == null) {
 338             for (int i = size-1; i >= 0; i--)
 339                 if (elementData[i]==null)
 340                     return i;
 341         } else {
 342             for (int i = size-1; i >= 0; i--)
 343                 if (o.equals(elementData[i]))
 344                     return i;
 345         }
 346         return -1;
 347     }
 348 
 349     /**
 350      * Returns a shallow copy of this {@code ArrayList} instance.  (The
 351      * elements themselves are not copied.)
 352      *
 353      * @return a clone of this {@code ArrayList} instance
 354      */
 355     public Object clone() {
 356         try {
 357             ArrayList<?> v = (ArrayList<?>) super.clone();
 358             v.elementData = Arrays.copyOf(elementData, size);
 359             v.modCount = 0;
 360             return v;
 361         } catch (CloneNotSupportedException e) {
 362             // this shouldn't happen, since we are Cloneable
 363             throw new InternalError(e);
 364         }
 365     }
 366 
 367     /**
 368      * Returns an array containing all of the elements in this list
 369      * in proper sequence (from first to last element).
 370      *
 371      * <p>The returned array will be "safe" in that no references to it are
 372      * maintained by this list.  (In other words, this method must allocate
 373      * a new array).  The caller is thus free to modify the returned array.
 374      *
 375      * <p>This method acts as bridge between array-based and collection-based
 376      * APIs.
 377      *
 378      * @return an array containing all of the elements in this list in
 379      *         proper sequence
 380      */
 381     public Object[] toArray() {
 382         return Arrays.copyOf(elementData, size);
 383     }
 384 
 385     /**
 386      * Returns an array containing all of the elements in this list in proper
 387      * sequence (from first to last element); the runtime type of the returned
 388      * array is that of the specified array.  If the list fits in the
 389      * specified array, it is returned therein.  Otherwise, a new array is
 390      * allocated with the runtime type of the specified array and the size of
 391      * this list.
 392      *
 393      * <p>If the list fits in the specified array with room to spare
 394      * (i.e., the array has more elements than the list), the element in
 395      * the array immediately following the end of the collection is set to
 396      * {@code null}.  (This is useful in determining the length of the
 397      * list <i>only</i> if the caller knows that the list does not contain
 398      * any null elements.)
 399      *
 400      * @param a the array into which the elements of the list are to
 401      *          be stored, if it is big enough; otherwise, a new array of the
 402      *          same runtime type is allocated for this purpose.
 403      * @return an array containing the elements of the list
 404      * @throws ArrayStoreException if the runtime type of the specified array
 405      *         is not a supertype of the runtime type of every element in
 406      *         this list
 407      * @throws NullPointerException if the specified array is null
 408      */
 409     @SuppressWarnings("unchecked")
 410     public <T> T[] toArray(T[] a) {
 411         if (a.length < size)
 412             // Make a new array of a's runtime type, but my contents:
 413             return (T[]) Arrays.copyOf(elementData, size, a.getClass());
 414         System.arraycopy(elementData, 0, a, 0, size);
 415         if (a.length > size)
 416             a[size] = null;
 417         return a;
 418     }
 419 
 420     // Positional Access Operations
 421 
 422     @SuppressWarnings("unchecked")
 423     E elementData(int index) {
 424         return (E) elementData[index];
 425     }
 426 
 427     /**
 428      * Returns the element at the specified position in this list.
 429      *
 430      * @param  index index of the element to return
 431      * @return the element at the specified position in this list
 432      * @throws IndexOutOfBoundsException {@inheritDoc}
 433      */
 434     public E get(int index) {
 435         Objects.checkIndex(index, size);
 436         return elementData(index);
 437     }
 438 
 439     /**
 440      * Replaces the element at the specified position in this list with
 441      * the specified element.
 442      *
 443      * @param index index of the element to replace
 444      * @param element element to be stored at the specified position
 445      * @return the element previously at the specified position
 446      * @throws IndexOutOfBoundsException {@inheritDoc}
 447      */
 448     public E set(int index, E element) {
 449         Objects.checkIndex(index, size);
 450         E oldValue = elementData(index);
 451         elementData[index] = element;
 452         return oldValue;
 453     }
 454 
 455     /**
 456      * This helper method split out from add(E) to keep method
 457      * bytecode size under 35 (the -XX:MaxInlineSize default value),
 458      * which helps when add(E) is called in a C1-compiled loop.
 459      */
 460     private void add(E e, Object[] elementData, int s) {
 461         if (s == elementData.length)
 462             elementData = grow();
 463         elementData[s] = e;
 464         size = s + 1;
 465     }
 466 
 467     /**
 468      * Appends the specified element to the end of this list.
 469      *
 470      * @param e element to be appended to this list
 471      * @return {@code true} (as specified by {@link Collection#add})
 472      */
 473     public boolean add(E e) {
 474         modCount++;
 475         add(e, elementData, size);
 476         return true;
 477     }
 478 
 479     /**
 480      * Inserts the specified element at the specified position in this
 481      * list. Shifts the element currently at that position (if any) and
 482      * any subsequent elements to the right (adds one to their indices).
 483      *
 484      * @param index index at which the specified element is to be inserted
 485      * @param element element to be inserted
 486      * @throws IndexOutOfBoundsException {@inheritDoc}
 487      */
 488     public void add(int index, E element) {
 489         rangeCheckForAdd(index);
 490         modCount++;
 491         final int s;
 492         Object[] elementData;
 493         if ((s = size) == (elementData = this.elementData).length)
 494             elementData = grow();
 495         System.arraycopy(elementData, index,
 496                          elementData, index + 1,
 497                          s - index);
 498         elementData[index] = element;
 499         size = s + 1;
 500     }
 501 
 502     /**
 503      * Removes the element at the specified position in this list.
 504      * Shifts any subsequent elements to the left (subtracts one from their
 505      * indices).
 506      *
 507      * @param index the index of the element to be removed
 508      * @return the element that was removed from the list
 509      * @throws IndexOutOfBoundsException {@inheritDoc}
 510      */
 511     public E remove(int index) {
 512         Objects.checkIndex(index, size);
 513 
 514         modCount++;
 515         E oldValue = elementData(index);
 516 
 517         int numMoved = size - index - 1;
 518         if (numMoved > 0)
 519             System.arraycopy(elementData, index+1, elementData, index,
 520                              numMoved);
 521         elementData[--size] = null; // clear to let GC do its work
 522 
 523         return oldValue;
 524     }
 525 
 526     /**
 527      * Removes the first occurrence of the specified element from this list,
 528      * if it is present.  If the list does not contain the element, it is
 529      * unchanged.  More formally, removes the element with the lowest index
 530      * {@code i} such that
 531      * {@code Objects.equals(o, get(i))}
 532      * (if such an element exists).  Returns {@code true} if this list
 533      * contained the specified element (or equivalently, if this list
 534      * changed as a result of the call).
 535      *
 536      * @param o element to be removed from this list, if present
 537      * @return {@code true} if this list contained the specified element
 538      */
 539     public boolean remove(Object o) {
 540         if (o == null) {
 541             for (int index = 0; index < size; index++)
 542                 if (elementData[index] == null) {
 543                     fastRemove(index);
 544                     return true;
 545                 }
 546         } else {
 547             for (int index = 0; index < size; index++)
 548                 if (o.equals(elementData[index])) {
 549                     fastRemove(index);
 550                     return true;
 551                 }
 552         }
 553         return false;
 554     }
 555 
 556     /*
 557      * Private remove method that skips bounds checking and does not
 558      * return the value removed.
 559      */
 560     private void fastRemove(int index) {
 561         modCount++;
 562         int numMoved = size - index - 1;
 563         if (numMoved > 0)
 564             System.arraycopy(elementData, index+1, elementData, index,
 565                              numMoved);
 566         elementData[--size] = null; // clear to let GC do its work
 567     }
 568 
 569     /**
 570      * Removes all of the elements from this list.  The list will
 571      * be empty after this call returns.
 572      */
 573     public void clear() {
 574         modCount++;
 575 
 576         // clear to let GC do its work
 577         for (int i = 0; i < size; i++)
 578             elementData[i] = null;
 579 
 580         size = 0;
 581     }
 582 
 583     /**
 584      * Appends all of the elements in the specified collection to the end of
 585      * this list, in the order that they are returned by the
 586      * specified collection's Iterator.  The behavior of this operation is
 587      * undefined if the specified collection is modified while the operation
 588      * is in progress.  (This implies that the behavior of this call is
 589      * undefined if the specified collection is this list, and this
 590      * list is nonempty.)
 591      *
 592      * @param c collection containing elements to be added to this list
 593      * @return {@code true} if this list changed as a result of the call
 594      * @throws NullPointerException if the specified collection is null
 595      */
 596     public boolean addAll(Collection<? extends E> c) {
 597         Object[] a = c.toArray();
 598         modCount++;
 599         int numNew = a.length;
 600         if (numNew == 0)
 601             return false;
 602         Object[] elementData;
 603         final int s;
 604         if (numNew > (elementData = this.elementData).length - (s = size))
 605             elementData = grow(s + numNew);
 606         System.arraycopy(a, 0, elementData, s, numNew);
 607         size = s + numNew;
 608         return true;
 609     }
 610 
 611     /**
 612      * Inserts all of the elements in the specified collection into this
 613      * list, starting at the specified position.  Shifts the element
 614      * currently at that position (if any) and any subsequent elements to
 615      * the right (increases their indices).  The new elements will appear
 616      * in the list in the order that they are returned by the
 617      * specified collection's iterator.
 618      *
 619      * @param index index at which to insert the first element from the
 620      *              specified collection
 621      * @param c collection containing elements to be added to this list
 622      * @return {@code true} if this list changed as a result of the call
 623      * @throws IndexOutOfBoundsException {@inheritDoc}
 624      * @throws NullPointerException if the specified collection is null
 625      */
 626     public boolean addAll(int index, Collection<? extends E> c) {
 627         rangeCheckForAdd(index);
 628 
 629         Object[] a = c.toArray();
 630         modCount++;
 631         int numNew = a.length;
 632         if (numNew == 0)
 633             return false;
 634         Object[] elementData;
 635         final int s;
 636         if (numNew > (elementData = this.elementData).length - (s = size))
 637             elementData = grow(s + numNew);
 638 
 639         int numMoved = s - index;
 640         if (numMoved > 0)
 641             System.arraycopy(elementData, index,
 642                              elementData, index + numNew,
 643                              numMoved);
 644         System.arraycopy(a, 0, elementData, index, numNew);
 645         size = s + numNew;
 646         return true;
 647     }
 648 
 649     /**
 650      * Removes from this list all of the elements whose index is between
 651      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 652      * Shifts any succeeding elements to the left (reduces their index).
 653      * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 654      * (If {@code toIndex==fromIndex}, this operation has no effect.)
 655      *
 656      * @throws IndexOutOfBoundsException if {@code fromIndex} or
 657      *         {@code toIndex} is out of range
 658      *         ({@code fromIndex < 0 ||
 659      *          toIndex > size() ||
 660      *          toIndex < fromIndex})
 661      */
 662     protected void removeRange(int fromIndex, int toIndex) {
 663         if (fromIndex > toIndex) {
 664             throw new IndexOutOfBoundsException(
 665                     outOfBoundsMsg(fromIndex, toIndex));
 666         }
 667         modCount++;
 668         int numMoved = size - toIndex;
 669         System.arraycopy(elementData, toIndex, elementData, fromIndex,
 670                          numMoved);
 671 
 672         // clear to let GC do its work
 673         int newSize = size - (toIndex-fromIndex);
 674         for (int i = newSize; i < size; i++) {
 675             elementData[i] = null;
 676         }
 677         size = newSize;
 678     }
 679 
 680     /**
 681      * A version of rangeCheck used by add and addAll.
 682      */
 683     private void rangeCheckForAdd(int index) {
 684         if (index > size || index < 0)
 685             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 686     }
 687 
 688     /**
 689      * Constructs an IndexOutOfBoundsException detail message.
 690      * Of the many possible refactorings of the error handling code,
 691      * this "outlining" performs best with both server and client VMs.
 692      */
 693     private String outOfBoundsMsg(int index) {
 694         return "Index: "+index+", Size: "+size;
 695     }
 696 
 697     /**
 698      * A version used in checking (fromIndex > toIndex) condition
 699      */
 700     private static String outOfBoundsMsg(int fromIndex, int toIndex) {
 701         return "From Index: " + fromIndex + " > To Index: " + toIndex;
 702     }
 703 
 704     /**
 705      * Removes from this list all of its elements that are contained in the
 706      * specified collection.
 707      *
 708      * @param c collection containing elements to be removed from this list
 709      * @return {@code true} if this list changed as a result of the call
 710      * @throws ClassCastException if the class of an element of this list
 711      *         is incompatible with the specified collection
 712      * (<a href="Collection.html#optional-restrictions">optional</a>)
 713      * @throws NullPointerException if this list contains a null element and the
 714      *         specified collection does not permit null elements
 715      * (<a href="Collection.html#optional-restrictions">optional</a>),
 716      *         or if the specified collection is null
 717      * @see Collection#contains(Object)
 718      */
 719     public boolean removeAll(Collection<?> c) {
 720         Objects.requireNonNull(c);
 721         return batchRemove(c, false);
 722     }
 723 
 724     /**
 725      * Retains only the elements in this list that are contained in the
 726      * specified collection.  In other words, removes from this list all
 727      * of its elements that are not contained in the specified collection.
 728      *
 729      * @param c collection containing elements to be retained in this list
 730      * @return {@code true} if this list changed as a result of the call
 731      * @throws ClassCastException if the class of an element of this list
 732      *         is incompatible with the specified collection
 733      * (<a href="Collection.html#optional-restrictions">optional</a>)
 734      * @throws NullPointerException if this list contains a null element and the
 735      *         specified collection does not permit null elements
 736      * (<a href="Collection.html#optional-restrictions">optional</a>),
 737      *         or if the specified collection is null
 738      * @see Collection#contains(Object)
 739      */
 740     public boolean retainAll(Collection<?> c) {
 741         Objects.requireNonNull(c);
 742         return batchRemove(c, true);
 743     }
 744 
 745     private boolean batchRemove(Collection<?> c, boolean complement) {
 746         final Object[] elementData = this.elementData;
 747         int r = 0, w = 0;
 748         boolean modified = false;
 749         try {
 750             for (; r < size; r++)
 751                 if (c.contains(elementData[r]) == complement)
 752                     elementData[w++] = elementData[r];
 753         } finally {
 754             // Preserve behavioral compatibility with AbstractCollection,
 755             // even if c.contains() throws.
 756             if (r != size) {
 757                 System.arraycopy(elementData, r,
 758                                  elementData, w,
 759                                  size - r);
 760                 w += size - r;
 761             }
 762             if (w != size) {
 763                 // clear to let GC do its work
 764                 for (int i = w; i < size; i++)
 765                     elementData[i] = null;
 766                 modCount += size - w;
 767                 size = w;
 768                 modified = true;
 769             }
 770         }
 771         return modified;
 772     }
 773 
 774     /**
 775      * Save the state of the {@code ArrayList} instance to a stream (that
 776      * is, serialize it).
 777      *
 778      * @serialData The length of the array backing the {@code ArrayList}
 779      *             instance is emitted (int), followed by all of its elements
 780      *             (each an {@code Object}) in the proper order.
 781      */
 782     private void writeObject(java.io.ObjectOutputStream s)
 783         throws java.io.IOException{
 784         // Write out element count, and any hidden stuff
 785         int expectedModCount = modCount;
 786         s.defaultWriteObject();
 787 
 788         // Write out size as capacity for behavioural compatibility with clone()
 789         s.writeInt(size);
 790 
 791         // Write out all elements in the proper order.
 792         for (int i=0; i<size; i++) {
 793             s.writeObject(elementData[i]);
 794         }
 795 
 796         if (modCount != expectedModCount) {
 797             throw new ConcurrentModificationException();
 798         }
 799     }
 800 
 801     /**
 802      * Reconstitute the {@code ArrayList} instance from a stream (that is,
 803      * deserialize it).
 804      */
 805     private void readObject(java.io.ObjectInputStream s)
 806         throws java.io.IOException, ClassNotFoundException {
 807 
 808         // Read in size, and any hidden stuff
 809         s.defaultReadObject();
 810 
 811         // Read in capacity
 812         s.readInt(); // ignored
 813 
 814         if (size > 0) {
 815             // like clone(), allocate array based upon size not capacity
 816             Object[] elements = new Object[size];
 817 
 818             // Read in all elements in the proper order.
 819             for (int i = 0; i < size; i++) {
 820                 elements[i] = s.readObject();
 821             }
 822 
 823             elementData = elements;
 824         } else if (size == 0) {
 825             elementData = EMPTY_ELEMENTDATA;
 826         } else {
 827             throw new java.io.InvalidObjectException("Invalid size: " + size);
 828         }
 829     }
 830 
 831     /**
 832      * Returns a list iterator over the elements in this list (in proper
 833      * sequence), starting at the specified position in the list.
 834      * The specified index indicates the first element that would be
 835      * returned by an initial call to {@link ListIterator#next next}.
 836      * An initial call to {@link ListIterator#previous previous} would
 837      * return the element with the specified index minus one.
 838      *
 839      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 840      *
 841      * @throws IndexOutOfBoundsException {@inheritDoc}
 842      */
 843     public ListIterator<E> listIterator(int index) {
 844         rangeCheckForAdd(index);
 845         return new ListItr(index);
 846     }
 847 
 848     /**
 849      * Returns a list iterator over the elements in this list (in proper
 850      * sequence).
 851      *
 852      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 853      *
 854      * @see #listIterator(int)
 855      */
 856     public ListIterator<E> listIterator() {
 857         return new ListItr(0);
 858     }
 859 
 860     /**
 861      * Returns an iterator over the elements in this list in proper sequence.
 862      *
 863      * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 864      *
 865      * @return an iterator over the elements in this list in proper sequence
 866      */
 867     public Iterator<E> iterator() {
 868         return new Itr();
 869     }
 870 
 871     /**
 872      * An optimized version of AbstractList.Itr
 873      */
 874     private class Itr implements Iterator<E> {
 875         int cursor;       // index of next element to return
 876         int lastRet = -1; // index of last element returned; -1 if no such
 877         int expectedModCount = modCount;
 878 
 879         public boolean hasNext() {
 880             return cursor != size;
 881         }
 882 
 883         @SuppressWarnings("unchecked")
 884         public E next() {
 885             checkForComodification();
 886             int i = cursor;
 887             if (i >= size)
 888                 throw new NoSuchElementException();
 889             Object[] elementData = ArrayList.this.elementData;
 890             if (i >= elementData.length)
 891                 throw new ConcurrentModificationException();
 892             cursor = i + 1;
 893             return (E) elementData[lastRet = i];
 894         }
 895 
 896         public void remove() {
 897             if (lastRet < 0)
 898                 throw new IllegalStateException();
 899             checkForComodification();
 900 
 901             try {
 902                 ArrayList.this.remove(lastRet);
 903                 cursor = lastRet;
 904                 lastRet = -1;
 905                 expectedModCount = modCount;
 906             } catch (IndexOutOfBoundsException ex) {
 907                 throw new ConcurrentModificationException();
 908             }
 909         }
 910 
 911         @Override
 912         @SuppressWarnings("unchecked")
 913         public void forEachRemaining(Consumer<? super E> consumer) {
 914             Objects.requireNonNull(consumer);
 915             final int size = ArrayList.this.size;
 916             int i = cursor;
 917             if (i >= size) {
 918                 return;
 919             }
 920             final Object[] elementData = ArrayList.this.elementData;
 921             if (i >= elementData.length) {
 922                 throw new ConcurrentModificationException();
 923             }
 924             while (i != size && modCount == expectedModCount) {
 925                 consumer.accept((E) elementData[i++]);
 926             }
 927             // update once at end of iteration to reduce heap write traffic
 928             cursor = i;
 929             lastRet = i - 1;
 930             checkForComodification();
 931         }
 932 
 933         final void checkForComodification() {
 934             if (modCount != expectedModCount)
 935                 throw new ConcurrentModificationException();
 936         }
 937     }
 938 
 939     /**
 940      * An optimized version of AbstractList.ListItr
 941      */
 942     private class ListItr extends Itr implements ListIterator<E> {
 943         ListItr(int index) {
 944             super();
 945             cursor = index;
 946         }
 947 
 948         public boolean hasPrevious() {
 949             return cursor != 0;
 950         }
 951 
 952         public int nextIndex() {
 953             return cursor;
 954         }
 955 
 956         public int previousIndex() {
 957             return cursor - 1;
 958         }
 959 
 960         @SuppressWarnings("unchecked")
 961         public E previous() {
 962             checkForComodification();
 963             int i = cursor - 1;
 964             if (i < 0)
 965                 throw new NoSuchElementException();
 966             Object[] elementData = ArrayList.this.elementData;
 967             if (i >= elementData.length)
 968                 throw new ConcurrentModificationException();
 969             cursor = i;
 970             return (E) elementData[lastRet = i];
 971         }
 972 
 973         public void set(E e) {
 974             if (lastRet < 0)
 975                 throw new IllegalStateException();
 976             checkForComodification();
 977 
 978             try {
 979                 ArrayList.this.set(lastRet, e);
 980             } catch (IndexOutOfBoundsException ex) {
 981                 throw new ConcurrentModificationException();
 982             }
 983         }
 984 
 985         public void add(E e) {
 986             checkForComodification();
 987 
 988             try {
 989                 int i = cursor;
 990                 ArrayList.this.add(i, e);
 991                 cursor = i + 1;
 992                 lastRet = -1;
 993                 expectedModCount = modCount;
 994             } catch (IndexOutOfBoundsException ex) {
 995                 throw new ConcurrentModificationException();
 996             }
 997         }
 998     }
 999 
1000     /**
1001      * Returns a view of the portion of this list between the specified
1002      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If
1003      * {@code fromIndex} and {@code toIndex} are equal, the returned list is
1004      * empty.)  The returned list is backed by this list, so non-structural
1005      * changes in the returned list are reflected in this list, and vice-versa.
1006      * The returned list supports all of the optional list operations.
1007      *
1008      * <p>This method eliminates the need for explicit range operations (of
1009      * the sort that commonly exist for arrays).  Any operation that expects
1010      * a list can be used as a range operation by passing a subList view
1011      * instead of a whole list.  For example, the following idiom
1012      * removes a range of elements from a list:
1013      * <pre>
1014      *      list.subList(from, to).clear();
1015      * </pre>
1016      * Similar idioms may be constructed for {@link #indexOf(Object)} and
1017      * {@link #lastIndexOf(Object)}, and all of the algorithms in the
1018      * {@link Collections} class can be applied to a subList.
1019      *
1020      * <p>The semantics of the list returned by this method become undefined if
1021      * the backing list (i.e., this list) is <i>structurally modified</i> in
1022      * any way other than via the returned list.  (Structural modifications are
1023      * those that change the size of this list, or otherwise perturb it in such
1024      * a fashion that iterations in progress may yield incorrect results.)
1025      *
1026      * @throws IndexOutOfBoundsException {@inheritDoc}
1027      * @throws IllegalArgumentException {@inheritDoc}
1028      */
1029     public List<E> subList(int fromIndex, int toIndex) {
1030         subListRangeCheck(fromIndex, toIndex, size);
1031         return new SubList<>(this, fromIndex, toIndex);
1032     }
1033 
1034     private static class SubList<E> extends AbstractList<E> implements RandomAccess {
1035         private final ArrayList<E> root;
1036         private final SubList<E> parent;
1037         private final int offset;
1038         private int size;
1039 
1040         /**
1041          * Constructs a sublist of an arbitrary ArrayList.
1042          */
1043         public SubList(ArrayList<E> root, int fromIndex, int toIndex) {
1044             this.root = root;
1045             this.parent = null;
1046             this.offset = fromIndex;
1047             this.size = toIndex - fromIndex;
1048             this.modCount = root.modCount;
1049         }
1050 
1051         /**
1052          * Constructs a sublist of another SubList.
1053          */
1054         private SubList(SubList<E> parent, int fromIndex, int toIndex) {
1055             this.root = parent.root;
1056             this.parent = parent;
1057             this.offset = parent.offset + fromIndex;
1058             this.size = toIndex - fromIndex;
1059             this.modCount = root.modCount;
1060         }
1061 
1062         public E set(int index, E element) {
1063             Objects.checkIndex(index, size);
1064             checkForComodification();
1065             E oldValue = root.elementData(offset + index);
1066             root.elementData[offset + index] = element;
1067             return oldValue;
1068         }
1069 
1070         public E get(int index) {
1071             Objects.checkIndex(index, size);
1072             checkForComodification();
1073             return root.elementData(offset + index);
1074         }
1075 
1076         public int size() {
1077             checkForComodification();
1078             return size;
1079         }
1080 
1081         public void add(int index, E element) {
1082             rangeCheckForAdd(index);
1083             checkForComodification();
1084             root.add(offset + index, element);
1085             updateSizeAndModCount(1);
1086         }
1087 
1088         public E remove(int index) {
1089             Objects.checkIndex(index, size);
1090             checkForComodification();
1091             E result = root.remove(offset + index);
1092             updateSizeAndModCount(-1);
1093             return result;
1094         }
1095 
1096         protected void removeRange(int fromIndex, int toIndex) {
1097             checkForComodification();
1098             root.removeRange(offset + fromIndex, offset + toIndex);
1099             updateSizeAndModCount(fromIndex - toIndex);
1100         }
1101 
1102         public boolean addAll(Collection<? extends E> c) {
1103             return addAll(this.size, c);
1104         }
1105 
1106         public boolean addAll(int index, Collection<? extends E> c) {
1107             rangeCheckForAdd(index);
1108             int cSize = c.size();
1109             if (cSize==0)
1110                 return false;
1111             checkForComodification();
1112             root.addAll(offset + index, c);
1113             updateSizeAndModCount(cSize);
1114             return true;
1115         }
1116 
1117         public Iterator<E> iterator() {
1118             return listIterator();
1119         }
1120 
1121         public ListIterator<E> listIterator(int index) {
1122             checkForComodification();
1123             rangeCheckForAdd(index);
1124 
1125             return new ListIterator<E>() {
1126                 int cursor = index;
1127                 int lastRet = -1;
1128                 int expectedModCount = root.modCount;
1129 
1130                 public boolean hasNext() {
1131                     return cursor != SubList.this.size;
1132                 }
1133 
1134                 @SuppressWarnings("unchecked")
1135                 public E next() {
1136                     checkForComodification();
1137                     int i = cursor;
1138                     if (i >= SubList.this.size)
1139                         throw new NoSuchElementException();
1140                     Object[] elementData = root.elementData;
1141                     if (offset + i >= elementData.length)
1142                         throw new ConcurrentModificationException();
1143                     cursor = i + 1;
1144                     return (E) elementData[offset + (lastRet = i)];
1145                 }
1146 
1147                 public boolean hasPrevious() {
1148                     return cursor != 0;
1149                 }
1150 
1151                 @SuppressWarnings("unchecked")
1152                 public E previous() {
1153                     checkForComodification();
1154                     int i = cursor - 1;
1155                     if (i < 0)
1156                         throw new NoSuchElementException();
1157                     Object[] elementData = root.elementData;
1158                     if (offset + i >= elementData.length)
1159                         throw new ConcurrentModificationException();
1160                     cursor = i;
1161                     return (E) elementData[offset + (lastRet = i)];
1162                 }
1163 
1164                 @SuppressWarnings("unchecked")
1165                 public void forEachRemaining(Consumer<? super E> consumer) {
1166                     Objects.requireNonNull(consumer);
1167                     final int size = SubList.this.size;
1168                     int i = cursor;
1169                     if (i >= size) {
1170                         return;
1171                     }
1172                     final Object[] elementData = root.elementData;
1173                     if (offset + i >= elementData.length) {
1174                         throw new ConcurrentModificationException();
1175                     }
1176                     while (i != size && modCount == expectedModCount) {
1177                         consumer.accept((E) elementData[offset + (i++)]);
1178                     }
1179                     // update once at end of iteration to reduce heap write traffic
1180                     lastRet = cursor = i;
1181                     checkForComodification();
1182                 }
1183 
1184                 public int nextIndex() {
1185                     return cursor;
1186                 }
1187 
1188                 public int previousIndex() {
1189                     return cursor - 1;
1190                 }
1191 
1192                 public void remove() {
1193                     if (lastRet < 0)
1194                         throw new IllegalStateException();
1195                     checkForComodification();
1196 
1197                     try {
1198                         SubList.this.remove(lastRet);
1199                         cursor = lastRet;
1200                         lastRet = -1;
1201                         expectedModCount = root.modCount;
1202                     } catch (IndexOutOfBoundsException ex) {
1203                         throw new ConcurrentModificationException();
1204                     }
1205                 }
1206 
1207                 public void set(E e) {
1208                     if (lastRet < 0)
1209                         throw new IllegalStateException();
1210                     checkForComodification();
1211 
1212                     try {
1213                         root.set(offset + lastRet, e);
1214                     } catch (IndexOutOfBoundsException ex) {
1215                         throw new ConcurrentModificationException();
1216                     }
1217                 }
1218 
1219                 public void add(E e) {
1220                     checkForComodification();
1221 
1222                     try {
1223                         int i = cursor;
1224                         SubList.this.add(i, e);
1225                         cursor = i + 1;
1226                         lastRet = -1;
1227                         expectedModCount = root.modCount;
1228                     } catch (IndexOutOfBoundsException ex) {
1229                         throw new ConcurrentModificationException();
1230                     }
1231                 }
1232 
1233                 final void checkForComodification() {
1234                     if (root.modCount != expectedModCount)
1235                         throw new ConcurrentModificationException();
1236                 }
1237             };
1238         }
1239 
1240         public List<E> subList(int fromIndex, int toIndex) {
1241             subListRangeCheck(fromIndex, toIndex, size);
1242             return new SubList<>(this, fromIndex, toIndex);
1243         }
1244 
1245         private void rangeCheckForAdd(int index) {
1246             if (index < 0 || index > this.size)
1247                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1248         }
1249 
1250         private String outOfBoundsMsg(int index) {
1251             return "Index: "+index+", Size: "+this.size;
1252         }
1253 
1254         private void checkForComodification() {
1255             if (root.modCount != modCount)
1256                 throw new ConcurrentModificationException();
1257         }
1258 
1259         private void updateSizeAndModCount(int sizeChange) {
1260             SubList<E> slist = this;
1261             do {
1262                 slist.size += sizeChange;
1263                 slist.modCount = root.modCount;
1264                 slist = slist.parent;
1265             } while (slist != null);
1266         }
1267 
1268         public Spliterator<E> spliterator() {
1269             checkForComodification();
1270 
1271             // ArrayListSpliterator is not used because late-binding logic
1272             // is different here
1273             return new Spliterator<>() {
1274                 private int index = offset; // current index, modified on advance/split
1275                 private int fence = -1; // -1 until used; then one past last index
1276                 private int expectedModCount; // initialized when fence set
1277 
1278                 private int getFence() { // initialize fence to size on first use
1279                     int hi; // (a specialized variant appears in method forEach)
1280                     if ((hi = fence) < 0) {
1281                         expectedModCount = modCount;
1282                         hi = fence = offset + size;
1283                     }
1284                     return hi;
1285                 }
1286 
1287                 public ArrayListSpliterator<E> trySplit() {
1288                     int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1289                     // ArrayListSpliterator could be used here as the source is already bound
1290                     return (lo >= mid) ? null : // divide range in half unless too small
1291                         new ArrayListSpliterator<>(root, lo, index = mid,
1292                                                    expectedModCount);
1293                 }
1294 
1295                 public boolean tryAdvance(Consumer<? super E> action) {
1296                     Objects.requireNonNull(action);
1297                     int hi = getFence(), i = index;
1298                     if (i < hi) {
1299                         index = i + 1;
1300                         @SuppressWarnings("unchecked") E e = (E)root.elementData[i];
1301                         action.accept(e);
1302                         if (root.modCount != expectedModCount)
1303                             throw new ConcurrentModificationException();
1304                         return true;
1305                     }
1306                     return false;
1307                 }
1308 
1309                 public void forEachRemaining(Consumer<? super E> action) {
1310                     Objects.requireNonNull(action);
1311                     int i, hi, mc; // hoist accesses and checks from loop
1312                     ArrayList<E> lst = root;
1313                     Object[] a;
1314                     if ((a = lst.elementData) != null) {
1315                         if ((hi = fence) < 0) {
1316                             mc = modCount;
1317                             hi = offset + size;
1318                         }
1319                         else
1320                             mc = expectedModCount;
1321                         if ((i = index) >= 0 && (index = hi) <= a.length) {
1322                             for (; i < hi; ++i) {
1323                                 @SuppressWarnings("unchecked") E e = (E) a[i];
1324                                 action.accept(e);
1325                             }
1326                             if (lst.modCount == mc)
1327                                 return;
1328                         }
1329                     }
1330                     throw new ConcurrentModificationException();
1331                 }
1332 
1333                 public long estimateSize() {
1334                     return (long) (getFence() - index);
1335                 }
1336 
1337                 public int characteristics() {
1338                     return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
1339                 }
1340             };
1341         }
1342     }
1343 
1344     @Override
1345     public void forEach(Consumer<? super E> action) {
1346         Objects.requireNonNull(action);
1347         final int expectedModCount = modCount;
1348         @SuppressWarnings("unchecked")
1349         final E[] elementData = (E[]) this.elementData;
1350         final int size = this.size;
1351         for (int i=0; modCount == expectedModCount && i < size; i++) {
1352             action.accept(elementData[i]);
1353         }
1354         if (modCount != expectedModCount) {
1355             throw new ConcurrentModificationException();
1356         }
1357     }
1358 
1359     /**
1360      * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
1361      * and <em>fail-fast</em> {@link Spliterator} over the elements in this
1362      * list.
1363      *
1364      * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
1365      * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
1366      * Overriding implementations should document the reporting of additional
1367      * characteristic values.
1368      *
1369      * @return a {@code Spliterator} over the elements in this list
1370      * @since 1.8
1371      */
1372     @Override
1373     public Spliterator<E> spliterator() {
1374         return new ArrayListSpliterator<>(this, 0, -1, 0);
1375     }
1376 
1377     /** Index-based split-by-two, lazily initialized Spliterator */
1378     static final class ArrayListSpliterator<E> implements Spliterator<E> {
1379 
1380         /*
1381          * If ArrayLists were immutable, or structurally immutable (no
1382          * adds, removes, etc), we could implement their spliterators
1383          * with Arrays.spliterator. Instead we detect as much
1384          * interference during traversal as practical without
1385          * sacrificing much performance. We rely primarily on
1386          * modCounts. These are not guaranteed to detect concurrency
1387          * violations, and are sometimes overly conservative about
1388          * within-thread interference, but detect enough problems to
1389          * be worthwhile in practice. To carry this out, we (1) lazily
1390          * initialize fence and expectedModCount until the latest
1391          * point that we need to commit to the state we are checking
1392          * against; thus improving precision.  (This doesn't apply to
1393          * SubLists, that create spliterators with current non-lazy
1394          * values).  (2) We perform only a single
1395          * ConcurrentModificationException check at the end of forEach
1396          * (the most performance-sensitive method). When using forEach
1397          * (as opposed to iterators), we can normally only detect
1398          * interference after actions, not before. Further
1399          * CME-triggering checks apply to all other possible
1400          * violations of assumptions for example null or too-small
1401          * elementData array given its size(), that could only have
1402          * occurred due to interference.  This allows the inner loop
1403          * of forEach to run without any further checks, and
1404          * simplifies lambda-resolution. While this does entail a
1405          * number of checks, note that in the common case of
1406          * list.stream().forEach(a), no checks or other computation
1407          * occur anywhere other than inside forEach itself.  The other
1408          * less-often-used methods cannot take advantage of most of
1409          * these streamlinings.
1410          */
1411 
1412         private final ArrayList<E> list;
1413         private int index; // current index, modified on advance/split
1414         private int fence; // -1 until used; then one past last index
1415         private int expectedModCount; // initialized when fence set
1416 
1417         /** Create new spliterator covering the given  range */
1418         ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
1419                              int expectedModCount) {
1420             this.list = list; // OK if null unless traversed
1421             this.index = origin;
1422             this.fence = fence;
1423             this.expectedModCount = expectedModCount;
1424         }
1425 
1426         private int getFence() { // initialize fence to size on first use
1427             int hi; // (a specialized variant appears in method forEach)
1428             ArrayList<E> lst;
1429             if ((hi = fence) < 0) {
1430                 if ((lst = list) == null)
1431                     hi = fence = 0;
1432                 else {
1433                     expectedModCount = lst.modCount;
1434                     hi = fence = lst.size;
1435                 }
1436             }
1437             return hi;
1438         }
1439 
1440         public ArrayListSpliterator<E> trySplit() {
1441             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1442             return (lo >= mid) ? null : // divide range in half unless too small
1443                 new ArrayListSpliterator<>(list, lo, index = mid,
1444                                            expectedModCount);
1445         }
1446 
1447         public boolean tryAdvance(Consumer<? super E> action) {
1448             if (action == null)
1449                 throw new NullPointerException();
1450             int hi = getFence(), i = index;
1451             if (i < hi) {
1452                 index = i + 1;
1453                 @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
1454                 action.accept(e);
1455                 if (list.modCount != expectedModCount)
1456                     throw new ConcurrentModificationException();
1457                 return true;
1458             }
1459             return false;
1460         }
1461 
1462         public void forEachRemaining(Consumer<? super E> action) {
1463             int i, hi, mc; // hoist accesses and checks from loop
1464             ArrayList<E> lst; Object[] a;
1465             if (action == null)
1466                 throw new NullPointerException();
1467             if ((lst = list) != null && (a = lst.elementData) != null) {
1468                 if ((hi = fence) < 0) {
1469                     mc = lst.modCount;
1470                     hi = lst.size;
1471                 }
1472                 else
1473                     mc = expectedModCount;
1474                 if ((i = index) >= 0 && (index = hi) <= a.length) {
1475                     for (; i < hi; ++i) {
1476                         @SuppressWarnings("unchecked") E e = (E) a[i];
1477                         action.accept(e);
1478                     }
1479                     if (lst.modCount == mc)
1480                         return;
1481                 }
1482             }
1483             throw new ConcurrentModificationException();
1484         }
1485 
1486         public long estimateSize() {
1487             return (long) (getFence() - index);
1488         }
1489 
1490         public int characteristics() {
1491             return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
1492         }
1493     }
1494 
1495     @Override
1496     public boolean removeIf(Predicate<? super E> filter) {
1497         Objects.requireNonNull(filter);
1498         // figure out which elements are to be removed
1499         // any exception thrown from the filter predicate at this stage
1500         // will leave the collection unmodified
1501         int removeCount = 0;
1502         final BitSet removeSet = new BitSet(size);
1503         final int expectedModCount = modCount;
1504         final int size = this.size;
1505         for (int i=0; modCount == expectedModCount && i < size; i++) {
1506             @SuppressWarnings("unchecked")
1507             final E element = (E) elementData[i];
1508             if (filter.test(element)) {
1509                 removeSet.set(i);
1510                 removeCount++;
1511             }
1512         }
1513         if (modCount != expectedModCount) {
1514             throw new ConcurrentModificationException();
1515         }
1516 
1517         // shift surviving elements left over the spaces left by removed elements
1518         final boolean anyToRemove = removeCount > 0;
1519         if (anyToRemove) {
1520             final int newSize = size - removeCount;
1521             for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
1522                 i = removeSet.nextClearBit(i);
1523                 elementData[j] = elementData[i];
1524             }
1525             for (int k=newSize; k < size; k++) {
1526                 elementData[k] = null;  // Let gc do its work
1527             }
1528             this.size = newSize;
1529             if (modCount != expectedModCount) {
1530                 throw new ConcurrentModificationException();
1531             }
1532             modCount++;
1533         }
1534 
1535         return anyToRemove;
1536     }
1537 
1538     @Override
1539     @SuppressWarnings("unchecked")
1540     public void replaceAll(UnaryOperator<E> operator) {
1541         Objects.requireNonNull(operator);
1542         final int expectedModCount = modCount;
1543         final int size = this.size;
1544         for (int i=0; modCount == expectedModCount && i < size; i++) {
1545             elementData[i] = operator.apply((E) elementData[i]);
1546         }
1547         if (modCount != expectedModCount) {
1548             throw new ConcurrentModificationException();
1549         }
1550         modCount++;
1551     }
1552 
1553     @Override
1554     @SuppressWarnings("unchecked")
1555     public void sort(Comparator<? super E> c) {
1556         final int expectedModCount = modCount;
1557         Arrays.sort((E[]) elementData, 0, size, c);
1558         if (modCount != expectedModCount) {
1559             throw new ConcurrentModificationException();
1560         }
1561         modCount++;
1562     }
1563 }