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 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         rangeCheck(index);
 436 
 437         return elementData(index);
 438     }
 439 
 440     /**
 441      * Replaces the element at the specified position in this list with
 442      * the specified element.
 443      *
 444      * @param index index of the element to replace
 445      * @param element element to be stored at the specified position
 446      * @return the element previously at the specified position
 447      * @throws IndexOutOfBoundsException {@inheritDoc}
 448      */
 449     public E set(int index, E element) {
 450         rangeCheck(index);
 451 
 452         E oldValue = elementData(index);
 453         elementData[index] = element;
 454         return oldValue;
 455     }
 456 
 457     /**
 458      * This helper method split out from add(E) to keep method
 459      * bytecode size under 35 (the -XX:MaxInlineSize default value),
 460      * which helps when add(E) is called in a C1-compiled loop.
 461      */
 462     private void add(E e, Object[] elementData, int s) {
 463         if (s == elementData.length)
 464             elementData = grow();
 465         elementData[s] = e;
 466         size = s + 1;
 467     }
 468 
 469     /**
 470      * Appends the specified element to the end of this list.
 471      *
 472      * @param e element to be appended to this list
 473      * @return {@code true} (as specified by {@link Collection#add})
 474      */
 475     public boolean add(E e) {
 476         modCount++;
 477         add(e, elementData, size);
 478         return true;
 479     }
 480 
 481     /**
 482      * Inserts the specified element at the specified position in this
 483      * list. Shifts the element currently at that position (if any) and
 484      * any subsequent elements to the right (adds one to their indices).
 485      *
 486      * @param index index at which the specified element is to be inserted
 487      * @param element element to be inserted
 488      * @throws IndexOutOfBoundsException {@inheritDoc}
 489      */
 490     public void add(int index, E element) {
 491         rangeCheckForAdd(index);
 492         modCount++;
 493         final int s;
 494         Object[] elementData;
 495         if ((s = size) == (elementData = this.elementData).length)
 496             elementData = grow();
 497         System.arraycopy(elementData, index,
 498                          elementData, index + 1,
 499                          s - index);
 500         elementData[index] = element;
 501         size = s + 1;
 502     }
 503 
 504     /**
 505      * Removes the element at the specified position in this list.
 506      * Shifts any subsequent elements to the left (subtracts one from their
 507      * indices).
 508      *
 509      * @param index the index of the element to be removed
 510      * @return the element that was removed from the list
 511      * @throws IndexOutOfBoundsException {@inheritDoc}
 512      */
 513     public E remove(int index) {
 514         rangeCheck(index);
 515 
 516         modCount++;
 517         E oldValue = elementData(index);
 518 
 519         int numMoved = size - index - 1;
 520         if (numMoved > 0)
 521             System.arraycopy(elementData, index+1, elementData, index,
 522                              numMoved);
 523         elementData[--size] = null; // clear to let GC do its work
 524 
 525         return oldValue;
 526     }
 527 
 528     /**
 529      * Removes the first occurrence of the specified element from this list,
 530      * if it is present.  If the list does not contain the element, it is
 531      * unchanged.  More formally, removes the element with the lowest index
 532      * {@code i} such that
 533      * {@code Objects.equals(o, get(i))}
 534      * (if such an element exists).  Returns {@code true} if this list
 535      * contained the specified element (or equivalently, if this list
 536      * changed as a result of the call).
 537      *
 538      * @param o element to be removed from this list, if present
 539      * @return {@code true} if this list contained the specified element
 540      */
 541     public boolean remove(Object o) {
 542         if (o == null) {
 543             for (int index = 0; index < size; index++)
 544                 if (elementData[index] == null) {
 545                     fastRemove(index);
 546                     return true;
 547                 }
 548         } else {
 549             for (int index = 0; index < size; index++)
 550                 if (o.equals(elementData[index])) {
 551                     fastRemove(index);
 552                     return true;
 553                 }
 554         }
 555         return false;
 556     }
 557 
 558     /*
 559      * Private remove method that skips bounds checking and does not
 560      * return the value removed.
 561      */
 562     private void fastRemove(int index) {
 563         modCount++;
 564         int numMoved = size - index - 1;
 565         if (numMoved > 0)
 566             System.arraycopy(elementData, index+1, elementData, index,
 567                              numMoved);
 568         elementData[--size] = null; // clear to let GC do its work
 569     }
 570 
 571     /**
 572      * Removes all of the elements from this list.  The list will
 573      * be empty after this call returns.
 574      */
 575     public void clear() {
 576         modCount++;
 577 
 578         // clear to let GC do its work
 579         for (int i = 0; i < size; i++)
 580             elementData[i] = null;
 581 
 582         size = 0;
 583     }
 584 
 585     /**
 586      * Appends all of the elements in the specified collection to the end of
 587      * this list, in the order that they are returned by the
 588      * specified collection's Iterator.  The behavior of this operation is
 589      * undefined if the specified collection is modified while the operation
 590      * is in progress.  (This implies that the behavior of this call is
 591      * undefined if the specified collection is this list, and this
 592      * list is nonempty.)
 593      *
 594      * @param c collection containing elements to be added to this list
 595      * @return {@code true} if this list changed as a result of the call
 596      * @throws NullPointerException if the specified collection is null
 597      */
 598     public boolean addAll(Collection<? extends E> c) {
 599         Object[] a = c.toArray();
 600         modCount++;
 601         int numNew = a.length;
 602         if (numNew == 0)
 603             return false;
 604         Object[] elementData;
 605         final int s;
 606         if (numNew > (elementData = this.elementData).length - (s = size))
 607             elementData = grow(s + numNew);
 608         System.arraycopy(a, 0, elementData, s, numNew);
 609         size = s + numNew;
 610         return true;
 611     }
 612 
 613     /**
 614      * Inserts all of the elements in the specified collection into this
 615      * list, starting at the specified position.  Shifts the element
 616      * currently at that position (if any) and any subsequent elements to
 617      * the right (increases their indices).  The new elements will appear
 618      * in the list in the order that they are returned by the
 619      * specified collection's iterator.
 620      *
 621      * @param index index at which to insert the first element from the
 622      *              specified collection
 623      * @param c collection containing elements to be added to this list
 624      * @return {@code true} if this list changed as a result of the call
 625      * @throws IndexOutOfBoundsException {@inheritDoc}
 626      * @throws NullPointerException if the specified collection is null
 627      */
 628     public boolean addAll(int index, Collection<? extends E> c) {
 629         rangeCheckForAdd(index);
 630 
 631         Object[] a = c.toArray();
 632         modCount++;
 633         int numNew = a.length;
 634         if (numNew == 0)
 635             return false;
 636         Object[] elementData;
 637         final int s;
 638         if (numNew > (elementData = this.elementData).length - (s = size))
 639             elementData = grow(s + numNew);
 640 
 641         int numMoved = s - index;
 642         if (numMoved > 0)
 643             System.arraycopy(elementData, index,
 644                              elementData, index + numNew,
 645                              numMoved);
 646         System.arraycopy(a, 0, elementData, index, numNew);
 647         size = s + numNew;
 648         return true;
 649     }
 650 
 651     /**
 652      * Removes from this list all of the elements whose index is between
 653      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 654      * Shifts any succeeding elements to the left (reduces their index).
 655      * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 656      * (If {@code toIndex==fromIndex}, this operation has no effect.)
 657      *
 658      * @throws IndexOutOfBoundsException if {@code fromIndex} or
 659      *         {@code toIndex} is out of range
 660      *         ({@code fromIndex < 0 ||
 661      *          toIndex > size() ||
 662      *          toIndex < fromIndex})
 663      */
 664     protected void removeRange(int fromIndex, int toIndex) {
 665         if (fromIndex > toIndex) {
 666             throw new IndexOutOfBoundsException(
 667                     outOfBoundsMsg(fromIndex, toIndex));
 668         }
 669         modCount++;
 670         int numMoved = size - toIndex;
 671         System.arraycopy(elementData, toIndex, elementData, fromIndex,
 672                          numMoved);
 673 
 674         // clear to let GC do its work
 675         int newSize = size - (toIndex-fromIndex);
 676         for (int i = newSize; i < size; i++) {
 677             elementData[i] = null;
 678         }
 679         size = newSize;
 680     }
 681 
 682     /**
 683      * Checks if the given index is in range.  If not, throws an appropriate
 684      * runtime exception.  This method does *not* check if the index is
 685      * negative: It is always used immediately prior to an array access,
 686      * which throws an ArrayIndexOutOfBoundsException if index is negative.
 687      */
 688     private void rangeCheck(int index) {
 689         if (index >= size)
 690             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 691     }
 692 
 693     /**
 694      * A version of rangeCheck used by add and addAll.
 695      */
 696     private void rangeCheckForAdd(int index) {
 697         if (index > size || index < 0)
 698             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 699     }
 700 
 701     /**
 702      * Constructs an IndexOutOfBoundsException detail message.
 703      * Of the many possible refactorings of the error handling code,
 704      * this "outlining" performs best with both server and client VMs.
 705      */
 706     private String outOfBoundsMsg(int index) {
 707         return "Index: "+index+", Size: "+size;
 708     }
 709 
 710     /**
 711      * A version used in checking (fromIndex > toIndex) condition
 712      */
 713     private static String outOfBoundsMsg(int fromIndex, int toIndex) {
 714         return "From Index: " + fromIndex + " > To Index: " + toIndex;
 715     }
 716 
 717     /**
 718      * Removes from this list all of its elements that are contained in the
 719      * specified collection.
 720      *
 721      * @param c collection containing elements to be removed from this list
 722      * @return {@code true} if this list changed as a result of the call
 723      * @throws ClassCastException if the class of an element of this list
 724      *         is incompatible with the specified collection
 725      * (<a href="Collection.html#optional-restrictions">optional</a>)
 726      * @throws NullPointerException if this list contains a null element and the
 727      *         specified collection does not permit null elements
 728      * (<a href="Collection.html#optional-restrictions">optional</a>),
 729      *         or if the specified collection is null
 730      * @see Collection#contains(Object)
 731      */
 732     public boolean removeAll(Collection<?> c) {
 733         Objects.requireNonNull(c);
 734         return batchRemove(c, false);
 735     }
 736 
 737     /**
 738      * Retains only the elements in this list that are contained in the
 739      * specified collection.  In other words, removes from this list all
 740      * of its elements that are not contained in the specified collection.
 741      *
 742      * @param c collection containing elements to be retained in this list
 743      * @return {@code true} if this list changed as a result of the call
 744      * @throws ClassCastException if the class of an element of this list
 745      *         is incompatible with the specified collection
 746      * (<a href="Collection.html#optional-restrictions">optional</a>)
 747      * @throws NullPointerException if this list contains a null element and the
 748      *         specified collection does not permit null elements
 749      * (<a href="Collection.html#optional-restrictions">optional</a>),
 750      *         or if the specified collection is null
 751      * @see Collection#contains(Object)
 752      */
 753     public boolean retainAll(Collection<?> c) {
 754         Objects.requireNonNull(c);
 755         return batchRemove(c, true);
 756     }
 757 
 758     private boolean batchRemove(Collection<?> c, boolean complement) {
 759         final Object[] elementData = this.elementData;
 760         int r = 0, w = 0;
 761         boolean modified = false;
 762         try {
 763             for (; r < size; r++)
 764                 if (c.contains(elementData[r]) == complement)
 765                     elementData[w++] = elementData[r];
 766         } finally {
 767             // Preserve behavioral compatibility with AbstractCollection,
 768             // even if c.contains() throws.
 769             if (r != size) {
 770                 System.arraycopy(elementData, r,
 771                                  elementData, w,
 772                                  size - r);
 773                 w += size - r;
 774             }
 775             if (w != size) {
 776                 // clear to let GC do its work
 777                 for (int i = w; i < size; i++)
 778                     elementData[i] = null;
 779                 modCount += size - w;
 780                 size = w;
 781                 modified = true;
 782             }
 783         }
 784         return modified;
 785     }
 786 
 787     /**
 788      * Save the state of the {@code ArrayList} instance to a stream (that
 789      * is, serialize it).
 790      *
 791      * @serialData The length of the array backing the {@code ArrayList}
 792      *             instance is emitted (int), followed by all of its elements
 793      *             (each an {@code Object}) in the proper order.
 794      */
 795     private void writeObject(java.io.ObjectOutputStream s)
 796         throws java.io.IOException{
 797         // Write out element count, and any hidden stuff
 798         int expectedModCount = modCount;
 799         s.defaultWriteObject();
 800 
 801         // Write out size as capacity for behavioural compatibility with clone()
 802         s.writeInt(size);
 803 
 804         // Write out all elements in the proper order.
 805         for (int i=0; i<size; i++) {
 806             s.writeObject(elementData[i]);
 807         }
 808 
 809         if (modCount != expectedModCount) {
 810             throw new ConcurrentModificationException();
 811         }
 812     }
 813 
 814     /**
 815      * Reconstitute the {@code ArrayList} instance from a stream (that is,
 816      * deserialize it).
 817      */
 818     private void readObject(java.io.ObjectInputStream s)
 819         throws java.io.IOException, ClassNotFoundException {
 820 
 821         // Read in size, and any hidden stuff
 822         s.defaultReadObject();
 823 
 824         // Read in capacity
 825         s.readInt(); // ignored
 826 
 827         if (size > 0) {
 828             // like clone(), allocate array based upon size not capacity
 829             Object[] elements = new Object[size];
 830 
 831             // Read in all elements in the proper order.
 832             for (int i = 0; i < size; i++) {
 833                 elements[i] = s.readObject();
 834             }
 835 
 836             elementData = elements;
 837         } else if (size == 0) {
 838             elementData = EMPTY_ELEMENTDATA;
 839         } else {
 840             throw new java.io.InvalidObjectException("Invalid size: " + size);
 841         }
 842     }
 843 
 844     /**
 845      * Returns a list iterator over the elements in this list (in proper
 846      * sequence), starting at the specified position in the list.
 847      * The specified index indicates the first element that would be
 848      * returned by an initial call to {@link ListIterator#next next}.
 849      * An initial call to {@link ListIterator#previous previous} would
 850      * return the element with the specified index minus one.
 851      *
 852      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 853      *
 854      * @throws IndexOutOfBoundsException {@inheritDoc}
 855      */
 856     public ListIterator<E> listIterator(int index) {
 857         if (index < 0 || index > size)
 858             throw new IndexOutOfBoundsException("Index: "+index);
 859         return new ListItr(index);
 860     }
 861 
 862     /**
 863      * Returns a list iterator over the elements in this list (in proper
 864      * sequence).
 865      *
 866      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 867      *
 868      * @see #listIterator(int)
 869      */
 870     public ListIterator<E> listIterator() {
 871         return new ListItr(0);
 872     }
 873 
 874     /**
 875      * Returns an iterator over the elements in this list in proper sequence.
 876      *
 877      * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 878      *
 879      * @return an iterator over the elements in this list in proper sequence
 880      */
 881     public Iterator<E> iterator() {
 882         return new Itr();
 883     }
 884 
 885     /**
 886      * An optimized version of AbstractList.Itr
 887      */
 888     private class Itr implements Iterator<E> {
 889         int cursor;       // index of next element to return
 890         int lastRet = -1; // index of last element returned; -1 if no such
 891         int expectedModCount = modCount;
 892 
 893         public boolean hasNext() {
 894             return cursor != size;
 895         }
 896 
 897         @SuppressWarnings("unchecked")
 898         public E next() {
 899             checkForComodification();
 900             int i = cursor;
 901             if (i >= size)
 902                 throw new NoSuchElementException();
 903             Object[] elementData = ArrayList.this.elementData;
 904             if (i >= elementData.length)
 905                 throw new ConcurrentModificationException();
 906             cursor = i + 1;
 907             return (E) elementData[lastRet = i];
 908         }
 909 
 910         public void remove() {
 911             if (lastRet < 0)
 912                 throw new IllegalStateException();
 913             checkForComodification();
 914 
 915             try {
 916                 ArrayList.this.remove(lastRet);
 917                 cursor = lastRet;
 918                 lastRet = -1;
 919                 expectedModCount = modCount;
 920             } catch (IndexOutOfBoundsException ex) {
 921                 throw new ConcurrentModificationException();
 922             }
 923         }
 924 
 925         @Override
 926         @SuppressWarnings("unchecked")
 927         public void forEachRemaining(Consumer<? super E> consumer) {
 928             Objects.requireNonNull(consumer);
 929             final int size = ArrayList.this.size;
 930             int i = cursor;
 931             if (i >= size) {
 932                 return;
 933             }
 934             final Object[] elementData = ArrayList.this.elementData;
 935             if (i >= elementData.length) {
 936                 throw new ConcurrentModificationException();
 937             }
 938             while (i != size && modCount == expectedModCount) {
 939                 consumer.accept((E) elementData[i++]);
 940             }
 941             // update once at end of iteration to reduce heap write traffic
 942             cursor = i;
 943             lastRet = i - 1;
 944             checkForComodification();
 945         }
 946 
 947         final void checkForComodification() {
 948             if (modCount != expectedModCount)
 949                 throw new ConcurrentModificationException();
 950         }
 951     }
 952 
 953     /**
 954      * An optimized version of AbstractList.ListItr
 955      */
 956     private class ListItr extends Itr implements ListIterator<E> {
 957         ListItr(int index) {
 958             super();
 959             cursor = index;
 960         }
 961 
 962         public boolean hasPrevious() {
 963             return cursor != 0;
 964         }
 965 
 966         public int nextIndex() {
 967             return cursor;
 968         }
 969 
 970         public int previousIndex() {
 971             return cursor - 1;
 972         }
 973 
 974         @SuppressWarnings("unchecked")
 975         public E previous() {
 976             checkForComodification();
 977             int i = cursor - 1;
 978             if (i < 0)
 979                 throw new NoSuchElementException();
 980             Object[] elementData = ArrayList.this.elementData;
 981             if (i >= elementData.length)
 982                 throw new ConcurrentModificationException();
 983             cursor = i;
 984             return (E) elementData[lastRet = i];
 985         }
 986 
 987         public void set(E e) {
 988             if (lastRet < 0)
 989                 throw new IllegalStateException();
 990             checkForComodification();
 991 
 992             try {
 993                 ArrayList.this.set(lastRet, e);
 994             } catch (IndexOutOfBoundsException ex) {
 995                 throw new ConcurrentModificationException();
 996             }
 997         }
 998 
 999         public void add(E e) {
1000             checkForComodification();
1001 
1002             try {
1003                 int i = cursor;
1004                 ArrayList.this.add(i, e);
1005                 cursor = i + 1;
1006                 lastRet = -1;
1007                 expectedModCount = modCount;
1008             } catch (IndexOutOfBoundsException ex) {
1009                 throw new ConcurrentModificationException();
1010             }
1011         }
1012     }
1013 
1014     /**
1015      * Returns a view of the portion of this list between the specified
1016      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If
1017      * {@code fromIndex} and {@code toIndex} are equal, the returned list is
1018      * empty.)  The returned list is backed by this list, so non-structural
1019      * changes in the returned list are reflected in this list, and vice-versa.
1020      * The returned list supports all of the optional list operations.
1021      *
1022      * <p>This method eliminates the need for explicit range operations (of
1023      * the sort that commonly exist for arrays).  Any operation that expects
1024      * a list can be used as a range operation by passing a subList view
1025      * instead of a whole list.  For example, the following idiom
1026      * removes a range of elements from a list:
1027      * <pre>
1028      *      list.subList(from, to).clear();
1029      * </pre>
1030      * Similar idioms may be constructed for {@link #indexOf(Object)} and
1031      * {@link #lastIndexOf(Object)}, and all of the algorithms in the
1032      * {@link Collections} class can be applied to a subList.
1033      *
1034      * <p>The semantics of the list returned by this method become undefined if
1035      * the backing list (i.e., this list) is <i>structurally modified</i> in
1036      * any way other than via the returned list.  (Structural modifications are
1037      * those that change the size of this list, or otherwise perturb it in such
1038      * a fashion that iterations in progress may yield incorrect results.)
1039      *
1040      * @throws IndexOutOfBoundsException {@inheritDoc}
1041      * @throws IllegalArgumentException {@inheritDoc}
1042      */
1043     public List<E> subList(int fromIndex, int toIndex) {
1044         subListRangeCheck(fromIndex, toIndex, size);
1045         return new SubList(this, 0, fromIndex, toIndex);
1046     }
1047 
1048     static void subListRangeCheck(int fromIndex, int toIndex, int size) {
1049         if (fromIndex < 0)
1050             throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
1051         if (toIndex > size)
1052             throw new IndexOutOfBoundsException("toIndex = " + toIndex);
1053         if (fromIndex > toIndex)
1054             throw new IllegalArgumentException("fromIndex(" + fromIndex +
1055                                                ") > toIndex(" + toIndex + ")");
1056     }
1057 
1058     private class SubList extends AbstractList<E> implements RandomAccess {
1059         private final AbstractList<E> parent;
1060         private final int parentOffset;
1061         private final int offset;
1062         int size;
1063 
1064         SubList(AbstractList<E> parent,
1065                 int offset, int fromIndex, int toIndex) {
1066             this.parent = parent;
1067             this.parentOffset = fromIndex;
1068             this.offset = offset + fromIndex;
1069             this.size = toIndex - fromIndex;
1070             this.modCount = ArrayList.this.modCount;
1071         }
1072 
1073         public E set(int index, E e) {
1074             rangeCheck(index);
1075             checkForComodification();
1076             E oldValue = ArrayList.this.elementData(offset + index);
1077             ArrayList.this.elementData[offset + index] = e;
1078             return oldValue;
1079         }
1080 
1081         public E get(int index) {
1082             rangeCheck(index);
1083             checkForComodification();
1084             return ArrayList.this.elementData(offset + index);
1085         }
1086 
1087         public int size() {
1088             checkForComodification();
1089             return this.size;
1090         }
1091 
1092         public void add(int index, E e) {
1093             rangeCheckForAdd(index);
1094             checkForComodification();
1095             parent.add(parentOffset + index, e);
1096             this.modCount = parent.modCount;
1097             this.size++;
1098         }
1099 
1100         public E remove(int index) {
1101             rangeCheck(index);
1102             checkForComodification();
1103             E result = parent.remove(parentOffset + index);
1104             this.modCount = parent.modCount;
1105             this.size--;
1106             return result;
1107         }
1108 
1109         protected void removeRange(int fromIndex, int toIndex) {
1110             checkForComodification();
1111             parent.removeRange(parentOffset + fromIndex,
1112                                parentOffset + toIndex);
1113             this.modCount = parent.modCount;
1114             this.size -= toIndex - fromIndex;
1115         }
1116 
1117         public boolean addAll(Collection<? extends E> c) {
1118             return addAll(this.size, c);
1119         }
1120 
1121         public boolean addAll(int index, Collection<? extends E> c) {
1122             rangeCheckForAdd(index);
1123             int cSize = c.size();
1124             if (cSize==0)
1125                 return false;
1126 
1127             checkForComodification();
1128             parent.addAll(parentOffset + index, c);
1129             this.modCount = parent.modCount;
1130             this.size += cSize;
1131             return true;
1132         }
1133 
1134         public Iterator<E> iterator() {
1135             return listIterator();
1136         }
1137 
1138         public ListIterator<E> listIterator(final int index) {
1139             checkForComodification();
1140             rangeCheckForAdd(index);
1141             final int offset = this.offset;
1142 
1143             return new ListIterator<E>() {
1144                 int cursor = index;
1145                 int lastRet = -1;
1146                 int expectedModCount = ArrayList.this.modCount;
1147 
1148                 public boolean hasNext() {
1149                     return cursor != SubList.this.size;
1150                 }
1151 
1152                 @SuppressWarnings("unchecked")
1153                 public E next() {
1154                     checkForComodification();
1155                     int i = cursor;
1156                     if (i >= SubList.this.size)
1157                         throw new NoSuchElementException();
1158                     Object[] elementData = ArrayList.this.elementData;
1159                     if (offset + i >= elementData.length)
1160                         throw new ConcurrentModificationException();
1161                     cursor = i + 1;
1162                     return (E) elementData[offset + (lastRet = i)];
1163                 }
1164 
1165                 public boolean hasPrevious() {
1166                     return cursor != 0;
1167                 }
1168 
1169                 @SuppressWarnings("unchecked")
1170                 public E previous() {
1171                     checkForComodification();
1172                     int i = cursor - 1;
1173                     if (i < 0)
1174                         throw new NoSuchElementException();
1175                     Object[] elementData = ArrayList.this.elementData;
1176                     if (offset + i >= elementData.length)
1177                         throw new ConcurrentModificationException();
1178                     cursor = i;
1179                     return (E) elementData[offset + (lastRet = i)];
1180                 }
1181 
1182                 @SuppressWarnings("unchecked")
1183                 public void forEachRemaining(Consumer<? super E> consumer) {
1184                     Objects.requireNonNull(consumer);
1185                     final int size = SubList.this.size;
1186                     int i = cursor;
1187                     if (i >= size) {
1188                         return;
1189                     }
1190                     final Object[] elementData = ArrayList.this.elementData;
1191                     if (offset + i >= elementData.length) {
1192                         throw new ConcurrentModificationException();
1193                     }
1194                     while (i != size && modCount == expectedModCount) {
1195                         consumer.accept((E) elementData[offset + (i++)]);
1196                     }
1197                     // update once at end of iteration to reduce heap write traffic
1198                     lastRet = cursor = i;
1199                     checkForComodification();
1200                 }
1201 
1202                 public int nextIndex() {
1203                     return cursor;
1204                 }
1205 
1206                 public int previousIndex() {
1207                     return cursor - 1;
1208                 }
1209 
1210                 public void remove() {
1211                     if (lastRet < 0)
1212                         throw new IllegalStateException();
1213                     checkForComodification();
1214 
1215                     try {
1216                         SubList.this.remove(lastRet);
1217                         cursor = lastRet;
1218                         lastRet = -1;
1219                         expectedModCount = ArrayList.this.modCount;
1220                     } catch (IndexOutOfBoundsException ex) {
1221                         throw new ConcurrentModificationException();
1222                     }
1223                 }
1224 
1225                 public void set(E e) {
1226                     if (lastRet < 0)
1227                         throw new IllegalStateException();
1228                     checkForComodification();
1229 
1230                     try {
1231                         ArrayList.this.set(offset + lastRet, e);
1232                     } catch (IndexOutOfBoundsException ex) {
1233                         throw new ConcurrentModificationException();
1234                     }
1235                 }
1236 
1237                 public void add(E e) {
1238                     checkForComodification();
1239 
1240                     try {
1241                         int i = cursor;
1242                         SubList.this.add(i, e);
1243                         cursor = i + 1;
1244                         lastRet = -1;
1245                         expectedModCount = ArrayList.this.modCount;
1246                     } catch (IndexOutOfBoundsException ex) {
1247                         throw new ConcurrentModificationException();
1248                     }
1249                 }
1250 
1251                 final void checkForComodification() {
1252                     if (expectedModCount != ArrayList.this.modCount)
1253                         throw new ConcurrentModificationException();
1254                 }
1255             };
1256         }
1257 
1258         public List<E> subList(int fromIndex, int toIndex) {
1259             subListRangeCheck(fromIndex, toIndex, size);
1260             return new SubList(this, offset, fromIndex, toIndex);
1261         }
1262 
1263         private void rangeCheck(int index) {
1264             if (index < 0 || index >= this.size)
1265                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1266         }
1267 
1268         private void rangeCheckForAdd(int index) {
1269             if (index < 0 || index > this.size)
1270                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1271         }
1272 
1273         private String outOfBoundsMsg(int index) {
1274             return "Index: "+index+", Size: "+this.size;
1275         }
1276 
1277         private void checkForComodification() {
1278             if (ArrayList.this.modCount != this.modCount)
1279                 throw new ConcurrentModificationException();
1280         }
1281 
1282         public Spliterator<E> spliterator() {
1283             checkForComodification();
1284 
1285             // ArrayListSpliterator is not used because late-binding logic
1286             // is different here
1287             return new Spliterator<>() {
1288                 private int index = offset; // current index, modified on advance/split
1289                 private int fence = -1; // -1 until used; then one past last index
1290                 private int expectedModCount; // initialized when fence set
1291         
1292                 private int getFence() { // initialize fence to size on first use
1293                     int hi; // (a specialized variant appears in method forEach)
1294                     if ((hi = fence) < 0) {
1295                         expectedModCount = modCount;
1296                         hi = fence = offset + size;
1297                     }
1298                     return hi;
1299                 }
1300         
1301                 public ArrayListSpliterator<E> trySplit() {
1302                     int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1303                     // ArrayListSpliterator could be used here as the source is already bound
1304                     return (lo >= mid) ? null : // divide range in half unless too small
1305                         new ArrayListSpliterator<>(ArrayList.this, lo, index = mid,
1306                                                    expectedModCount);
1307                 }
1308         
1309                 public boolean tryAdvance(Consumer<? super E> action) {
1310                     Objects.requireNonNull(action);
1311                     int hi = getFence(), i = index;
1312                     if (i < hi) {
1313                         index = i + 1;
1314                         @SuppressWarnings("unchecked") E e = (E)elementData[i];
1315                         action.accept(e);
1316                         if (ArrayList.this.modCount != expectedModCount)
1317                             throw new ConcurrentModificationException();
1318                         return true;
1319                     }
1320                     return false;
1321                 }
1322         
1323                 public void forEachRemaining(Consumer<? super E> action) {
1324                     Objects.requireNonNull(action);
1325                     int i, hi, mc; // hoist accesses and checks from loop
1326                     ArrayList<E> lst = ArrayList.this;
1327                     Object[] a;
1328                     if ((a = lst.elementData) != null) {
1329                         if ((hi = fence) < 0) {
1330                             mc = modCount;
1331                             hi = offset + size;
1332                         }
1333                         else
1334                             mc = expectedModCount;
1335                         if ((i = index) >= 0 && (index = hi) <= a.length) {
1336                             for (; i < hi; ++i) {
1337                                 @SuppressWarnings("unchecked") E e = (E) a[i];
1338                                 action.accept(e);
1339                             }
1340                             if (lst.modCount == mc)
1341                                 return;
1342                         }
1343                     }
1344                     throw new ConcurrentModificationException();
1345                 }
1346         
1347                 public long estimateSize() {
1348                     return (long) (getFence() - index);
1349                 }
1350         
1351                 public int characteristics() {
1352                     return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
1353                 }
1354             };
1355         }
1356     }
1357 
1358     @Override
1359     public void forEach(Consumer<? super E> action) {
1360         Objects.requireNonNull(action);
1361         final int expectedModCount = modCount;
1362         @SuppressWarnings("unchecked")
1363         final E[] elementData = (E[]) this.elementData;
1364         final int size = this.size;
1365         for (int i=0; modCount == expectedModCount && i < size; i++) {
1366             action.accept(elementData[i]);
1367         }
1368         if (modCount != expectedModCount) {
1369             throw new ConcurrentModificationException();
1370         }
1371     }
1372 
1373     /**
1374      * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
1375      * and <em>fail-fast</em> {@link Spliterator} over the elements in this
1376      * list.
1377      *
1378      * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
1379      * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
1380      * Overriding implementations should document the reporting of additional
1381      * characteristic values.
1382      *
1383      * @return a {@code Spliterator} over the elements in this list
1384      * @since 1.8
1385      */
1386     @Override
1387     public Spliterator<E> spliterator() {
1388         return new ArrayListSpliterator<>(this, 0, -1, 0);
1389     }
1390 
1391     /** Index-based split-by-two, lazily initialized Spliterator */
1392     static final class ArrayListSpliterator<E> implements Spliterator<E> {
1393 
1394         /*
1395          * If ArrayLists were immutable, or structurally immutable (no
1396          * adds, removes, etc), we could implement their spliterators
1397          * with Arrays.spliterator. Instead we detect as much
1398          * interference during traversal as practical without
1399          * sacrificing much performance. We rely primarily on
1400          * modCounts. These are not guaranteed to detect concurrency
1401          * violations, and are sometimes overly conservative about
1402          * within-thread interference, but detect enough problems to
1403          * be worthwhile in practice. To carry this out, we (1) lazily
1404          * initialize fence and expectedModCount until the latest
1405          * point that we need to commit to the state we are checking
1406          * against; thus improving precision.  (This doesn't apply to
1407          * SubLists, that create spliterators with current non-lazy
1408          * values).  (2) We perform only a single
1409          * ConcurrentModificationException check at the end of forEach
1410          * (the most performance-sensitive method). When using forEach
1411          * (as opposed to iterators), we can normally only detect
1412          * interference after actions, not before. Further
1413          * CME-triggering checks apply to all other possible
1414          * violations of assumptions for example null or too-small
1415          * elementData array given its size(), that could only have
1416          * occurred due to interference.  This allows the inner loop
1417          * of forEach to run without any further checks, and
1418          * simplifies lambda-resolution. While this does entail a
1419          * number of checks, note that in the common case of
1420          * list.stream().forEach(a), no checks or other computation
1421          * occur anywhere other than inside forEach itself.  The other
1422          * less-often-used methods cannot take advantage of most of
1423          * these streamlinings.
1424          */
1425 
1426         private final ArrayList<E> list;
1427         private int index; // current index, modified on advance/split
1428         private int fence; // -1 until used; then one past last index
1429         private int expectedModCount; // initialized when fence set
1430 
1431         /** Create new spliterator covering the given  range */
1432         ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
1433                              int expectedModCount) {
1434             this.list = list; // OK if null unless traversed
1435             this.index = origin;
1436             this.fence = fence;
1437             this.expectedModCount = expectedModCount;
1438         }
1439 
1440         private int getFence() { // initialize fence to size on first use
1441             int hi; // (a specialized variant appears in method forEach)
1442             ArrayList<E> lst;
1443             if ((hi = fence) < 0) {
1444                 if ((lst = list) == null)
1445                     hi = fence = 0;
1446                 else {
1447                     expectedModCount = lst.modCount;
1448                     hi = fence = lst.size;
1449                 }
1450             }
1451             return hi;
1452         }
1453 
1454         public ArrayListSpliterator<E> trySplit() {
1455             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1456             return (lo >= mid) ? null : // divide range in half unless too small
1457                 new ArrayListSpliterator<>(list, lo, index = mid,
1458                                            expectedModCount);
1459         }
1460 
1461         public boolean tryAdvance(Consumer<? super E> action) {
1462             if (action == null)
1463                 throw new NullPointerException();
1464             int hi = getFence(), i = index;
1465             if (i < hi) {
1466                 index = i + 1;
1467                 @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
1468                 action.accept(e);
1469                 if (list.modCount != expectedModCount)
1470                     throw new ConcurrentModificationException();
1471                 return true;
1472             }
1473             return false;
1474         }
1475 
1476         public void forEachRemaining(Consumer<? super E> action) {
1477             int i, hi, mc; // hoist accesses and checks from loop
1478             ArrayList<E> lst; Object[] a;
1479             if (action == null)
1480                 throw new NullPointerException();
1481             if ((lst = list) != null && (a = lst.elementData) != null) {
1482                 if ((hi = fence) < 0) {
1483                     mc = lst.modCount;
1484                     hi = lst.size;
1485                 }
1486                 else
1487                     mc = expectedModCount;
1488                 if ((i = index) >= 0 && (index = hi) <= a.length) {
1489                     for (; i < hi; ++i) {
1490                         @SuppressWarnings("unchecked") E e = (E) a[i];
1491                         action.accept(e);
1492                     }
1493                     if (lst.modCount == mc)
1494                         return;
1495                 }
1496             }
1497             throw new ConcurrentModificationException();
1498         }
1499 
1500         public long estimateSize() {
1501             return (long) (getFence() - index);
1502         }
1503 
1504         public int characteristics() {
1505             return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
1506         }
1507     }
1508 
1509     @Override
1510     public boolean removeIf(Predicate<? super E> filter) {
1511         Objects.requireNonNull(filter);
1512         // figure out which elements are to be removed
1513         // any exception thrown from the filter predicate at this stage
1514         // will leave the collection unmodified
1515         int removeCount = 0;
1516         final BitSet removeSet = new BitSet(size);
1517         final int expectedModCount = modCount;
1518         final int size = this.size;
1519         for (int i=0; modCount == expectedModCount && i < size; i++) {
1520             @SuppressWarnings("unchecked")
1521             final E element = (E) elementData[i];
1522             if (filter.test(element)) {
1523                 removeSet.set(i);
1524                 removeCount++;
1525             }
1526         }
1527         if (modCount != expectedModCount) {
1528             throw new ConcurrentModificationException();
1529         }
1530 
1531         // shift surviving elements left over the spaces left by removed elements
1532         final boolean anyToRemove = removeCount > 0;
1533         if (anyToRemove) {
1534             final int newSize = size - removeCount;
1535             for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
1536                 i = removeSet.nextClearBit(i);
1537                 elementData[j] = elementData[i];
1538             }
1539             for (int k=newSize; k < size; k++) {
1540                 elementData[k] = null;  // Let gc do its work
1541             }
1542             this.size = newSize;
1543             if (modCount != expectedModCount) {
1544                 throw new ConcurrentModificationException();
1545             }
1546             modCount++;
1547         }
1548 
1549         return anyToRemove;
1550     }
1551 
1552     @Override
1553     @SuppressWarnings("unchecked")
1554     public void replaceAll(UnaryOperator<E> operator) {
1555         Objects.requireNonNull(operator);
1556         final int expectedModCount = modCount;
1557         final int size = this.size;
1558         for (int i=0; modCount == expectedModCount && i < size; i++) {
1559             elementData[i] = operator.apply((E) elementData[i]);
1560         }
1561         if (modCount != expectedModCount) {
1562             throw new ConcurrentModificationException();
1563         }
1564         modCount++;
1565     }
1566 
1567     @Override
1568     @SuppressWarnings("unchecked")
1569     public void sort(Comparator<? super E> c) {
1570         final int expectedModCount = modCount;
1571         Arrays.sort((E[]) elementData, 0, size, c);
1572         if (modCount != expectedModCount) {
1573             throw new ConcurrentModificationException();
1574         }
1575         modCount++;
1576     }
1577 }