rev 51958 : 8211122: Reduce the number of internal classes made accessible to jdk.unsupported
Reviewed-by: alanb, dfuchs, kvn

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