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