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