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