ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/ArrayList.java
(Generate patch)

Comparing jsr166/src/main/java/util/ArrayList.java (file contents):
Revision 1.18 by jsr166, Sun Mar 19 17:40:40 2006 UTC vs.
Revision 1.60 by jsr166, Wed May 16 16:18:00 2018 UTC

# Line 1 | Line 1
1   /*
2 < * %W% %E%
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 < * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
6 < * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
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 <tt>List</tt> interface.  Implements
34 > * Resizable-array implementation of the {@code List} interface.  Implements
35   * all optional list operations, and permits all elements, including
36 < * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
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 < * <tt>Vector</tt>, except that it is unsynchronized.)<p>
39 > * {@code Vector}, except that it is unsynchronized.)
40   *
41 < * The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
42 < * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
43 < * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
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 <tt>LinkedList</tt> implementation.<p>
46 > * to that for the {@code LinkedList} implementation.
47   *
48 < * Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
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.<p>
53 > * time cost.
54   *
55 < * An application can increase the capacity of an <tt>ArrayList</tt> instance
56 < * before adding a large number of elements using the <tt>ensureCapacity</tt>
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 <tt>ArrayList</tt> instance concurrently,
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
# Line 48 | Line 71 | package java.util;
71   * unsynchronized access to the list:<pre>
72   *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
73   *
74 < * <p>The iterators returned by this class's <tt>iterator</tt> and
75 < * <tt>listIterator</tt> methods are <i>fail-fast</i>: if the list is
76 < * structurally modified at any time after the iterator is created, in any way
77 < * except through the iterator's own <tt>remove</tt> or <tt>add</tt> methods,
78 < * the iterator will throw a {@link ConcurrentModificationException}.  Thus, in
79 < * the face of concurrent modification, the iterator fails quickly and cleanly,
80 < * rather than risking arbitrary, non-deterministic behavior at an undetermined
81 < * time in the future.<p>
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 < * Note that the fail-fast behavior of an iterator cannot be guaranteed
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 <tt>ConcurrentModificationException</tt> on a best-effort basis.
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><p>
91 > * exception for its correctness:  <i>the fail-fast behavior of iterators
92 > * should be used only to detect bugs.</i>
93   *
94 < * This class is a member of the
95 < * <a href="{@docRoot}/../guide/collections/index.html">
94 > * <p>This class is a member of the
95 > * <a href="{@docRoot}/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 < * @version %I%, %G%
103 < * @see     Collection
104 < * @see     List
105 < * @see     LinkedList
78 < * @see     Vector
102 > * @see     Collection
103 > * @see     List
104 > * @see     LinkedList
105 > * @see     Vector
106   * @since   1.2
107   */
81
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.
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 <    private transient Object[] elementData;
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).
# Line 100 | Line 145 | public class ArrayList<E> extends Abstra
145      /**
146       * Constructs an empty list with the specified initial capacity.
147       *
148 <     * @param initialCapacity the initial capacity of the list
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 <        super();
154 <        if (initialCapacity < 0)
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 <        this.elementData = new Object[initialCapacity];
160 >        }
161      }
162  
163      /**
164       * Constructs an empty list with an initial capacity of ten.
165       */
166      public ArrayList() {
167 <        this(10);
167 >        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
168      }
169  
170      /**
# Line 128 | Line 176 | public class ArrayList<E> extends Abstra
176       * @throws NullPointerException if the specified collection is null
177       */
178      public ArrayList(Collection<? extends E> c) {
179 <        elementData = c.toArray();
180 <        size = elementData.length;
181 <        // c.toArray might (incorrectly) not return Object[] (see 6260652)
182 <        if (elementData.getClass() != Object[].class)
183 <            elementData = Arrays.copyOf(elementData, size, Object[].class);
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 <tt>ArrayList</tt> instance to be the
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 <tt>ArrayList</tt> instance.
194 >     * the storage of an {@code ArrayList} instance.
195       */
196      public void trimToSize() {
197 <        modCount++;
198 <        int oldCapacity = elementData.length;
199 <        if (size < oldCapacity) {
200 <            elementData = Arrays.copyOf(elementData, size);
201 <        }
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 <tt>ArrayList</tt> instance, if
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 <        modCount++;
214 <        if (minCapacity > elementData.length)
215 <            growArray(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 <     * Increases the capacity of the array.
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 void growArray(int minCapacity) {
255 <        if (minCapacity < 0) // overflow
256 <            throw new OutOfMemoryError();
257 <        int oldCapacity = elementData.length;
258 <        // Double size if small; else grow by 50%
259 <        int newCapacity = ((oldCapacity < 64) ?
260 <                           ((oldCapacity + 1) * 2) :
261 <                           ((oldCapacity / 2) * 3));
262 <        if (newCapacity < 0) // overflow
263 <            newCapacity = Integer.MAX_VALUE;
264 <        if (newCapacity < minCapacity)
265 <            newCapacity = minCapacity;
266 <        elementData = Arrays.copyOf(elementData, newCapacity);
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      /**
# Line 187 | Line 281 | public class ArrayList<E> extends Abstra
281       * @return the number of elements in this list
282       */
283      public int size() {
284 <        return size;
284 >        return size;
285      }
286  
287      /**
288 <     * Returns <tt>true</tt> if this list contains no elements.
288 >     * Returns {@code true} if this list contains no elements.
289       *
290 <     * @return <tt>true</tt> if this list contains no elements
290 >     * @return {@code true} if this list contains no elements
291       */
292      public boolean isEmpty() {
293 <        return size == 0;
293 >        return size == 0;
294      }
295  
296      /**
297 <     * Returns <tt>true</tt> if this list contains the specified element.
298 <     * More formally, returns <tt>true</tt> if and only if this list contains
299 <     * at least one element <tt>e</tt> such that
300 <     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
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 <tt>true</tt> if this list contains the specified element
303 >     * @return {@code true} if this list contains the specified element
304       */
305      public boolean contains(Object o) {
306 <        return indexOf(o) >= 0;
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 <tt>i</tt> such that
313 <     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
312 >     * More formally, returns the lowest index {@code i} such that
313 >     * {@code Objects.equals(o, get(i))},
314       * or -1 if there is no such index.
315       */
316      public int indexOf(Object o) {
317 <        if (o == null) {
318 <            for (int i = 0; i < size; i++)
319 <                if (elementData[i]==null)
320 <                    return i;
321 <        } else {
322 <            for (int i = 0; i < size; i++)
323 <                if (o.equals(elementData[i]))
324 <                    return i;
325 <        }
326 <        return -1;
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 <tt>i</tt> such that
342 <     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
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 <        if (o == null) {
347 <            for (int i = size-1; i >= 0; i--)
348 <                if (elementData[i]==null)
349 <                    return i;
350 <        } else {
351 <            for (int i = size-1; i >= 0; i--)
352 <                if (o.equals(elementData[i]))
353 <                    return i;
354 <        }
355 <        return -1;
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 <tt>ArrayList</tt> instance.  (The
368 >     * Returns a shallow copy of this {@code ArrayList} instance.  (The
369       * elements themselves are not copied.)
370       *
371 <     * @return a clone of this <tt>ArrayList</tt> instance
371 >     * @return a clone of this {@code ArrayList} instance
372       */
373      public Object clone() {
374 <        try {
375 <            ArrayList<E> v = (ArrayList<E>) 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();
382 <        }
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      /**
# Line 299 | Line 411 | public class ArrayList<E> extends Abstra
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 <     * <tt>null</tt>.  (This is useful in determining the length of the
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       *
# Line 312 | Line 424 | public class ArrayList<E> extends Abstra
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);
432 >        System.arraycopy(elementData, 0, a, 0, size);
433          if (a.length > size)
434              a[size] = null;
435          return a;
# Line 324 | Line 437 | public class ArrayList<E> extends Abstra
437  
438      // Positional Access Operations
439  
440 <    /**
441 <     * Returns error message string for IndexOutOfBoundsExceptions
442 <     */
443 <    private String ioobe(int index) {
444 <        return "Index: " + index + ", Size: " + size;
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      /**
# Line 339 | Line 455 | public class ArrayList<E> extends Abstra
455       * @throws IndexOutOfBoundsException {@inheritDoc}
456       */
457      public E get(int index) {
458 <        if (index >= size)
459 <            throw new IndexOutOfBoundsException(ioobe(index));
344 <        return (E)elementData[index];
458 >        Objects.checkIndex(index, size);
459 >        return elementData(index);
460      }
461  
462      /**
# Line 354 | Line 469 | public class ArrayList<E> extends Abstra
469       * @throws IndexOutOfBoundsException {@inheritDoc}
470       */
471      public E set(int index, E element) {
472 <        if (index >= size)
473 <            throw new IndexOutOfBoundsException(ioobe(index));
472 >        Objects.checkIndex(index, size);
473 >        E oldValue = elementData(index);
474 >        elementData[index] = element;
475 >        return oldValue;
476 >    }
477  
478 <        E oldValue = (E) elementData[index];
479 <        elementData[index] = element;
480 <        return oldValue;
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 <tt>true</tt> (as specified by {@link Collection#add})
494 >     * @return {@code true} (as specified by {@link Collection#add})
495       */
496      public boolean add(E e) {
497          modCount++;
498 <        int s = size;
499 <        if (s >= elementData.length)
375 <            growArray(s + 1);
376 <        elementData[s] = e;
377 <        size = s + 1;
378 <        return true;
498 >        add(e, elementData, size);
499 >        return true;
500      }
501  
502      /**
# Line 388 | Line 509 | public class ArrayList<E> extends Abstra
509       * @throws IndexOutOfBoundsException {@inheritDoc}
510       */
511      public void add(int index, E element) {
512 <        int s = size;
392 <        if (index > s || index < 0)
393 <            throw new IndexOutOfBoundsException(ioobe(index));
512 >        rangeCheckForAdd(index);
513          modCount++;
514 <        if (s >= elementData.length)
515 <            growArray(s + 1);
516 <        System.arraycopy(elementData, index,
517 <                         elementData, index + 1, s - index);
518 <        elementData[index] = element;
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 +        // checkInvariants();
524      }
525  
526      /**
# Line 410 | Line 533 | public class ArrayList<E> extends Abstra
533       * @throws IndexOutOfBoundsException {@inheritDoc}
534       */
535      public E remove(int index) {
536 <        int s = size - 1;
537 <        if (index > s)
538 <            throw new IndexOutOfBoundsException(ioobe(index));
539 <        modCount++;
540 <        E oldValue = (E)elementData[index];
541 <        int numMoved = s - index;
542 <        if (numMoved > 0)
543 <            System.arraycopy(elementData, index + 1,
544 <                             elementData, index, numMoved);
545 <        elementData[s] = null;
546 <        size = s;
547 <        return oldValue;
536 >        Objects.checkIndex(index, size);
537 >        final Object[] es = elementData;
538 >
539 >        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
540 >        fastRemove(es, index);
541 >
542 >        // checkInvariants();
543 >        return oldValue;
544 >    }
545 >
546 >    /**
547 >     * {@inheritDoc}
548 >     */
549 >    public boolean equals(Object o) {
550 >        if (o == this) {
551 >            return true;
552 >        }
553 >
554 >        if (!(o instanceof List)) {
555 >            return false;
556 >        }
557 >
558 >        final int expectedModCount = modCount;
559 >        // ArrayList can be subclassed and given arbitrary behavior, but we can
560 >        // still deal with the common case where o is ArrayList precisely
561 >        boolean equal = (o.getClass() == ArrayList.class)
562 >            ? equalsArrayList((ArrayList<?>) o)
563 >            : equalsRange((List<?>) o, 0, size);
564 >
565 >        checkForComodification(expectedModCount);
566 >        return equal;
567 >    }
568 >
569 >    boolean equalsRange(List<?> other, int from, int to) {
570 >        final Object[] es = elementData;
571 >        if (to > es.length) {
572 >            throw new ConcurrentModificationException();
573 >        }
574 >        var oit = other.iterator();
575 >        for (; from < to; from++) {
576 >            if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {
577 >                return false;
578 >            }
579 >        }
580 >        return !oit.hasNext();
581 >    }
582 >
583 >    private boolean equalsArrayList(ArrayList<?> other) {
584 >        final int otherModCount = other.modCount;
585 >        final int s = size;
586 >        boolean equal;
587 >        if (equal = (s == other.size)) {
588 >            final Object[] otherEs = other.elementData;
589 >            final Object[] es = elementData;
590 >            if (s > es.length || s > otherEs.length) {
591 >                throw new ConcurrentModificationException();
592 >            }
593 >            for (int i = 0; i < s; i++) {
594 >                if (!Objects.equals(es[i], otherEs[i])) {
595 >                    equal = false;
596 >                    break;
597 >                }
598 >            }
599 >        }
600 >        other.checkForComodification(otherModCount);
601 >        return equal;
602 >    }
603 >
604 >    private void checkForComodification(final int expectedModCount) {
605 >        if (modCount != expectedModCount) {
606 >            throw new ConcurrentModificationException();
607 >        }
608 >    }
609 >
610 >    /**
611 >     * {@inheritDoc}
612 >     */
613 >    public int hashCode() {
614 >        int expectedModCount = modCount;
615 >        int hash = hashCodeRange(0, size);
616 >        checkForComodification(expectedModCount);
617 >        return hash;
618 >    }
619 >
620 >    int hashCodeRange(int from, int to) {
621 >        final Object[] es = elementData;
622 >        if (to > es.length) {
623 >            throw new ConcurrentModificationException();
624 >        }
625 >        int hashCode = 1;
626 >        for (int i = from; i < to; i++) {
627 >            Object e = es[i];
628 >            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
629 >        }
630 >        return hashCode;
631      }
632  
633      /**
634       * Removes the first occurrence of the specified element from this list,
635       * if it is present.  If the list does not contain the element, it is
636       * unchanged.  More formally, removes the element with the lowest index
637 <     * <tt>i</tt> such that
638 <     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
639 <     * (if such an element exists).  Returns <tt>true</tt> if this list
637 >     * {@code i} such that
638 >     * {@code Objects.equals(o, get(i))}
639 >     * (if such an element exists).  Returns {@code true} if this list
640       * contained the specified element (or equivalently, if this list
641       * changed as a result of the call).
642       *
643       * @param o element to be removed from this list, if present
644 <     * @return <tt>true</tt> if this list contained the specified element
644 >     * @return {@code true} if this list contained the specified element
645       */
646      public boolean remove(Object o) {
647 <        if (o == null) {
648 <            for (int index = 0; index < size; index++)
649 <                if (elementData[index] == null) {
650 <                    fastRemove(index);
651 <                    return true;
652 <                }
653 <        } else {
654 <            for (int index = 0; index < size; index++)
655 <                if (o.equals(elementData[index])) {
656 <                    fastRemove(index);
657 <                    return true;
658 <                }
647 >        final Object[] es = elementData;
648 >        final int size = this.size;
649 >        int i = 0;
650 >        found: {
651 >            if (o == null) {
652 >                for (; i < size; i++)
653 >                    if (es[i] == null)
654 >                        break found;
655 >            } else {
656 >                for (; i < size; i++)
657 >                    if (o.equals(es[i]))
658 >                        break found;
659 >            }
660 >            return false;
661          }
662 <        return false;
662 >        fastRemove(es, i);
663 >        return true;
664      }
665  
666 <    /*
666 >    /**
667       * Private remove method that skips bounds checking and does not
668       * return the value removed.
669       */
670 <    private void fastRemove(int index) {
670 >    private void fastRemove(Object[] es, int i) {
671          modCount++;
672 <        int numMoved = size - index - 1;
673 <        if (numMoved > 0)
674 <            System.arraycopy(elementData, index+1, elementData, index,
675 <                             numMoved);
467 <        elementData[--size] = null; // Let gc do its work
672 >        final int newSize;
673 >        if ((newSize = size - 1) > i)
674 >            System.arraycopy(es, i + 1, es, i, newSize - i);
675 >        es[size = newSize] = null;
676      }
677  
678      /**
# Line 472 | Line 680 | public class ArrayList<E> extends Abstra
680       * be empty after this call returns.
681       */
682      public void clear() {
683 <        modCount++;
684 <
685 <        // Let gc do its work
686 <        for (int i = 0; i < size; i++)
479 <            elementData[i] = null;
480 <
481 <        size = 0;
683 >        modCount++;
684 >        final Object[] es = elementData;
685 >        for (int to = size, i = size = 0; i < to; i++)
686 >            es[i] = null;
687      }
688  
689      /**
# Line 491 | Line 696 | public class ArrayList<E> extends Abstra
696       * list is nonempty.)
697       *
698       * @param c collection containing elements to be added to this list
699 <     * @return <tt>true</tt> if this list changed as a result of the call
699 >     * @return {@code true} if this list changed as a result of the call
700       * @throws NullPointerException if the specified collection is null
701       */
702      public boolean addAll(Collection<? extends E> c) {
703 <        Object[] a = c.toArray();
703 >        Object[] a = c.toArray();
704 >        modCount++;
705          int numNew = a.length;
706 <        ensureCapacity(size + numNew);  // Increments modCount
707 <        System.arraycopy(a, 0, elementData, size, numNew);
708 <        size += numNew;
709 <        return numNew != 0;
706 >        if (numNew == 0)
707 >            return false;
708 >        Object[] elementData;
709 >        final int s;
710 >        if (numNew > (elementData = this.elementData).length - (s = size))
711 >            elementData = grow(s + numNew);
712 >        System.arraycopy(a, 0, elementData, s, numNew);
713 >        size = s + numNew;
714 >        // checkInvariants();
715 >        return true;
716      }
717  
718      /**
# Line 514 | Line 726 | public class ArrayList<E> extends Abstra
726       * @param index index at which to insert the first element from the
727       *              specified collection
728       * @param c collection containing elements to be added to this list
729 <     * @return <tt>true</tt> if this list changed as a result of the call
729 >     * @return {@code true} if this list changed as a result of the call
730       * @throws IndexOutOfBoundsException {@inheritDoc}
731       * @throws NullPointerException if the specified collection is null
732       */
733      public boolean addAll(int index, Collection<? extends E> c) {
734 <        if (index > size || index < 0)
523 <            throw new IndexOutOfBoundsException(ioobe(index));
734 >        rangeCheckForAdd(index);
735  
736 <        Object[] a = c.toArray();
737 <        int numNew = a.length;
738 <        ensureCapacity(size + numNew);  // Increments modCount
739 <
740 <        int numMoved = size - index;
741 <        if (numMoved > 0)
742 <            System.arraycopy(elementData, index, elementData, index + numNew,
743 <                             numMoved);
736 >        Object[] a = c.toArray();
737 >        modCount++;
738 >        int numNew = a.length;
739 >        if (numNew == 0)
740 >            return false;
741 >        Object[] elementData;
742 >        final int s;
743 >        if (numNew > (elementData = this.elementData).length - (s = size))
744 >            elementData = grow(s + numNew);
745  
746 +        int numMoved = s - index;
747 +        if (numMoved > 0)
748 +            System.arraycopy(elementData, index,
749 +                             elementData, index + numNew,
750 +                             numMoved);
751          System.arraycopy(a, 0, elementData, index, numNew);
752 <        size += numNew;
753 <        return numNew != 0;
752 >        size = s + numNew;
753 >        // checkInvariants();
754 >        return true;
755      }
756  
757      /**
758       * Removes from this list all of the elements whose index is between
759 <     * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.
759 >     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
760       * Shifts any succeeding elements to the left (reduces their index).
761 <     * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
762 <     * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
761 >     * This call shortens the list by {@code (toIndex - fromIndex)} elements.
762 >     * (If {@code toIndex==fromIndex}, this operation has no effect.)
763       *
764 <     * @param fromIndex index of first element to be removed
765 <     * @param toIndex index after last element to be removed
766 <     * @throws IndexOutOfBoundsException if fromIndex or toIndex out of
767 <     *              range (fromIndex &lt; 0 || fromIndex &gt;= size() || toIndex
768 <     *              &gt; size() || toIndex &lt; fromIndex)
764 >     * @throws IndexOutOfBoundsException if {@code fromIndex} or
765 >     *         {@code toIndex} is out of range
766 >     *         ({@code fromIndex < 0 ||
767 >     *          toIndex > size() ||
768 >     *          toIndex < fromIndex})
769       */
770      protected void removeRange(int fromIndex, int toIndex) {
771 <        modCount++;
772 <        int numMoved = size - toIndex;
773 <        System.arraycopy(elementData, toIndex, elementData, fromIndex,
774 <                         numMoved);
771 >        if (fromIndex > toIndex) {
772 >            throw new IndexOutOfBoundsException(
773 >                    outOfBoundsMsg(fromIndex, toIndex));
774 >        }
775 >        modCount++;
776 >        shiftTailOverGap(elementData, fromIndex, toIndex);
777 >        // checkInvariants();
778 >    }
779 >
780 >    /** Erases the gap from lo to hi, by sliding down following elements. */
781 >    private void shiftTailOverGap(Object[] es, int lo, int hi) {
782 >        System.arraycopy(es, hi, es, lo, size - hi);
783 >        for (int to = size, i = (size -= hi - lo); i < to; i++)
784 >            es[i] = null;
785 >    }
786 >
787 >    /**
788 >     * A version of rangeCheck used by add and addAll.
789 >     */
790 >    private void rangeCheckForAdd(int index) {
791 >        if (index > size || index < 0)
792 >            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
793 >    }
794 >
795 >    /**
796 >     * Constructs an IndexOutOfBoundsException detail message.
797 >     * Of the many possible refactorings of the error handling code,
798 >     * this "outlining" performs best with both server and client VMs.
799 >     */
800 >    private String outOfBoundsMsg(int index) {
801 >        return "Index: "+index+", Size: "+size;
802 >    }
803  
804 <        // Let gc do its work
805 <        int newSize = size - (toIndex-fromIndex);
806 <        while (size != newSize)
807 <            elementData[--size] = null;
804 >    /**
805 >     * A version used in checking (fromIndex > toIndex) condition
806 >     */
807 >    private static String outOfBoundsMsg(int fromIndex, int toIndex) {
808 >        return "From Index: " + fromIndex + " > To Index: " + toIndex;
809      }
810  
811      /**
812 <     * Save the state of the <tt>ArrayList</tt> instance to a stream (that
813 <     * is, serialize it).
812 >     * Removes from this list all of its elements that are contained in the
813 >     * specified collection.
814       *
815 <     * @serialData The length of the array backing the <tt>ArrayList</tt>
815 >     * @param c collection containing elements to be removed from this list
816 >     * @return {@code true} if this list changed as a result of the call
817 >     * @throws ClassCastException if the class of an element of this list
818 >     *         is incompatible with the specified collection
819 >     * (<a href="Collection.html#optional-restrictions">optional</a>)
820 >     * @throws NullPointerException if this list contains a null element and the
821 >     *         specified collection does not permit null elements
822 >     * (<a href="Collection.html#optional-restrictions">optional</a>),
823 >     *         or if the specified collection is null
824 >     * @see Collection#contains(Object)
825 >     */
826 >    public boolean removeAll(Collection<?> c) {
827 >        return batchRemove(c, false, 0, size);
828 >    }
829 >
830 >    /**
831 >     * Retains only the elements in this list that are contained in the
832 >     * specified collection.  In other words, removes from this list all
833 >     * of its elements that are not contained in the specified collection.
834 >     *
835 >     * @param c collection containing elements to be retained in this list
836 >     * @return {@code true} if this list changed as a result of the call
837 >     * @throws ClassCastException if the class of an element of this list
838 >     *         is incompatible with the specified collection
839 >     * (<a href="Collection.html#optional-restrictions">optional</a>)
840 >     * @throws NullPointerException if this list contains a null element and the
841 >     *         specified collection does not permit null elements
842 >     * (<a href="Collection.html#optional-restrictions">optional</a>),
843 >     *         or if the specified collection is null
844 >     * @see Collection#contains(Object)
845 >     */
846 >    public boolean retainAll(Collection<?> c) {
847 >        return batchRemove(c, true, 0, size);
848 >    }
849 >
850 >    boolean batchRemove(Collection<?> c, boolean complement,
851 >                        final int from, final int end) {
852 >        Objects.requireNonNull(c);
853 >        final Object[] es = elementData;
854 >        int r;
855 >        // Optimize for initial run of survivors
856 >        for (r = from;; r++) {
857 >            if (r == end)
858 >                return false;
859 >            if (c.contains(es[r]) != complement)
860 >                break;
861 >        }
862 >        int w = r++;
863 >        try {
864 >            for (Object e; r < end; r++)
865 >                if (c.contains(e = es[r]) == complement)
866 >                    es[w++] = e;
867 >        } catch (Throwable ex) {
868 >            // Preserve behavioral compatibility with AbstractCollection,
869 >            // even if c.contains() throws.
870 >            System.arraycopy(es, r, es, w, end - r);
871 >            w += end - r;
872 >            throw ex;
873 >        } finally {
874 >            modCount += end - w;
875 >            shiftTailOverGap(es, w, end);
876 >        }
877 >        // checkInvariants();
878 >        return true;
879 >    }
880 >
881 >    /**
882 >     * Saves the state of the {@code ArrayList} instance to a stream
883 >     * (that is, serializes it).
884 >     *
885 >     * @param s the stream
886 >     * @throws java.io.IOException if an I/O error occurs
887 >     * @serialData The length of the array backing the {@code ArrayList}
888       *             instance is emitted (int), followed by all of its elements
889 <     *             (each an <tt>Object</tt>) in the proper order.
889 >     *             (each an {@code Object}) in the proper order.
890       */
891      private void writeObject(java.io.ObjectOutputStream s)
892 <        throws java.io.IOException{
893 <        // Write out element count, and any hidden stuff
894 <        int expectedModCount = modCount;
895 <        s.defaultWriteObject();
892 >        throws java.io.IOException {
893 >        // Write out element count, and any hidden stuff
894 >        int expectedModCount = modCount;
895 >        s.defaultWriteObject();
896  
897 <        // Write out array length
898 <        s.writeInt(elementData.length);
897 >        // Write out size as capacity for behavioral compatibility with clone()
898 >        s.writeInt(size);
899  
900 <        // Write out all elements in the proper order.
901 <        for (int i=0; i<size; i++)
900 >        // Write out all elements in the proper order.
901 >        for (int i=0; i<size; i++) {
902              s.writeObject(elementData[i]);
903 +        }
904  
905 <        if (expectedModCount != modCount) {
905 >        if (modCount != expectedModCount) {
906              throw new ConcurrentModificationException();
907          }
588
908      }
909  
910      /**
911 <     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
912 <     * deserialize it).
911 >     * Reconstitutes the {@code ArrayList} instance from a stream (that is,
912 >     * deserializes it).
913 >     * @param s the stream
914 >     * @throws ClassNotFoundException if the class of a serialized object
915 >     *         could not be found
916 >     * @throws java.io.IOException if an I/O error occurs
917       */
918      private void readObject(java.io.ObjectInputStream s)
919          throws java.io.IOException, ClassNotFoundException {
597        // Read in size, and any hidden stuff
598        s.defaultReadObject();
920  
921 <        // Read in array length and allocate array
922 <        int arrayLength = s.readInt();
602 <        Object[] a = elementData = new Object[arrayLength];
921 >        // Read in size, and any hidden stuff
922 >        s.defaultReadObject();
923  
924 <        // Read in all elements in the proper order.
925 <        for (int i=0; i<size; i++)
606 <            a[i] = s.readObject();
607 <    }
924 >        // Read in capacity
925 >        s.readInt(); // ignored
926  
927 +        if (size > 0) {
928 +            // like clone(), allocate array based upon size not capacity
929 +            SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
930 +            Object[] elements = new Object[size];
931 +
932 +            // Read in all elements in the proper order.
933 +            for (int i = 0; i < size; i++) {
934 +                elements[i] = s.readObject();
935 +            }
936 +
937 +            elementData = elements;
938 +        } else if (size == 0) {
939 +            elementData = EMPTY_ELEMENTDATA;
940 +        } else {
941 +            throw new java.io.InvalidObjectException("Invalid size: " + size);
942 +        }
943 +    }
944  
945      /**
946 <     * Returns a list-iterator of the elements in this list (in proper
946 >     * Returns a list iterator over the elements in this list (in proper
947       * sequence), starting at the specified position in the list.
948 <     * Obeys the general contract of <tt>List.listIterator(int)</tt>.<p>
948 >     * The specified index indicates the first element that would be
949 >     * returned by an initial call to {@link ListIterator#next next}.
950 >     * An initial call to {@link ListIterator#previous previous} would
951 >     * return the element with the specified index minus one.
952 >     *
953 >     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
954       *
615     * The list-iterator is <i>fail-fast</i>: if the list is structurally
616     * modified at any time after the Iterator is created, in any way except
617     * through the list-iterator's own <tt>remove</tt> or <tt>add</tt>
618     * methods, the list-iterator will throw a
619     * <tt>ConcurrentModificationException</tt>.  Thus, in the face of
620     * concurrent modification, the iterator fails quickly and cleanly, rather
621     * than risking arbitrary, non-deterministic behavior at an undetermined
622     * time in the future.
623     *
624     * @param index index of the first element to be returned from the
625     *              list-iterator (by a call to <tt>next</tt>)
626     * @return a ListIterator of the elements in this list (in proper
627     *         sequence), starting at the specified position in the list
955       * @throws IndexOutOfBoundsException {@inheritDoc}
629     * @see List#listIterator(int)
956       */
957      public ListIterator<E> listIterator(int index) {
958 <        if (index < 0 || index > size)
959 <            throw new IndexOutOfBoundsException(ioobe(index));
634 <        return new ArrayListIterator(index);
958 >        rangeCheckForAdd(index);
959 >        return new ListItr(index);
960      }
961  
962      /**
963 <     * {@inheritDoc}
963 >     * Returns a list iterator over the elements in this list (in proper
964 >     * sequence).
965 >     *
966 >     * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
967 >     *
968 >     * @see #listIterator(int)
969       */
970      public ListIterator<E> listIterator() {
971 <        return new ArrayListIterator(0);
971 >        return new ListItr(0);
972      }
973  
974      /**
975       * Returns an iterator over the elements in this list in proper sequence.
976       *
977 +     * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
978 +     *
979       * @return an iterator over the elements in this list in proper sequence
980       */
981      public Iterator<E> iterator() {
982 <        return new ArrayListIterator(0);
982 >        return new Itr();
983      }
984  
985      /**
986 <     * A streamlined version of AbstractList.ListItr
986 >     * An optimized version of AbstractList.Itr
987       */
988 <    final class ArrayListIterator implements ListIterator<E> {
989 <        int cursor;           // index of next element to return;
990 <        int lastRet;          // index of last element, or -1 if no such
991 <        int expectedModCount; // to check for CME
988 >    private class Itr implements Iterator<E> {
989 >        int cursor;       // index of next element to return
990 >        int lastRet = -1; // index of last element returned; -1 if no such
991 >        int expectedModCount = modCount;
992  
993 <        ArrayListIterator(int index) {
994 <            cursor = index;
663 <            lastRet = -1;
664 <            expectedModCount = modCount;
665 <        }
993 >        // prevent creating a synthetic constructor
994 >        Itr() {}
995  
996 <        public boolean hasNext() {
996 >        public boolean hasNext() {
997              return cursor != size;
998 <        }
670 <
671 <        public boolean hasPrevious() {
672 <            return cursor != 0;
673 <        }
998 >        }
999  
1000 <        public int nextIndex() {
1001 <            return cursor;
1002 <        }
1000 >        @SuppressWarnings("unchecked")
1001 >        public E next() {
1002 >            checkForComodification();
1003 >            int i = cursor;
1004 >            if (i >= size)
1005 >                throw new NoSuchElementException();
1006 >            Object[] elementData = ArrayList.this.elementData;
1007 >            if (i >= elementData.length)
1008 >                throw new ConcurrentModificationException();
1009 >            cursor = i + 1;
1010 >            return (E) elementData[lastRet = i];
1011 >        }
1012  
1013 <        public int previousIndex() {
1014 <            return cursor - 1;
1015 <        }
1013 >        public void remove() {
1014 >            if (lastRet < 0)
1015 >                throw new IllegalStateException();
1016 >            checkForComodification();
1017  
683        public E next() {
1018              try {
1019 <                int i = cursor;
1020 <                E next = get(i);
1021 <                lastRet = i;
1022 <                cursor = i + 1;
689 <                return next;
1019 >                ArrayList.this.remove(lastRet);
1020 >                cursor = lastRet;
1021 >                lastRet = -1;
1022 >                expectedModCount = modCount;
1023              } catch (IndexOutOfBoundsException ex) {
1024 <                throw new NoSuchElementException();
1025 <            } finally {
1026 <                if (expectedModCount != modCount)
1024 >                throw new ConcurrentModificationException();
1025 >            }
1026 >        }
1027 >
1028 >        @Override
1029 >        public void forEachRemaining(Consumer<? super E> action) {
1030 >            Objects.requireNonNull(action);
1031 >            final int size = ArrayList.this.size;
1032 >            int i = cursor;
1033 >            if (i < size) {
1034 >                final Object[] es = elementData;
1035 >                if (i >= es.length)
1036                      throw new ConcurrentModificationException();
1037 +                for (; i < size && modCount == expectedModCount; i++)
1038 +                    action.accept(elementAt(es, i));
1039 +                // update once at end to reduce heap write traffic
1040 +                cursor = i;
1041 +                lastRet = i - 1;
1042 +                checkForComodification();
1043              }
1044 <        }
1044 >        }
1045 >
1046 >        final void checkForComodification() {
1047 >            if (modCount != expectedModCount)
1048 >                throw new ConcurrentModificationException();
1049 >        }
1050 >    }
1051 >
1052 >    /**
1053 >     * An optimized version of AbstractList.ListItr
1054 >     */
1055 >    private class ListItr extends Itr implements ListIterator<E> {
1056 >        ListItr(int index) {
1057 >            super();
1058 >            cursor = index;
1059 >        }
1060 >
1061 >        public boolean hasPrevious() {
1062 >            return cursor != 0;
1063 >        }
1064 >
1065 >        public int nextIndex() {
1066 >            return cursor;
1067 >        }
1068 >
1069 >        public int previousIndex() {
1070 >            return cursor - 1;
1071 >        }
1072  
1073 +        @SuppressWarnings("unchecked")
1074          public E previous() {
1075 +            checkForComodification();
1076 +            int i = cursor - 1;
1077 +            if (i < 0)
1078 +                throw new NoSuchElementException();
1079 +            Object[] elementData = ArrayList.this.elementData;
1080 +            if (i >= elementData.length)
1081 +                throw new ConcurrentModificationException();
1082 +            cursor = i;
1083 +            return (E) elementData[lastRet = i];
1084 +        }
1085 +
1086 +        public void set(E e) {
1087 +            if (lastRet < 0)
1088 +                throw new IllegalStateException();
1089 +            checkForComodification();
1090 +
1091              try {
1092 <                int i = cursor - 1;
701 <                E prev = get(i);
702 <                lastRet = i;
703 <                cursor = i;
704 <                return prev;
1092 >                ArrayList.this.set(lastRet, e);
1093              } catch (IndexOutOfBoundsException ex) {
1094 <                throw new NoSuchElementException();
707 <            } finally {
708 <                if (expectedModCount != modCount)
709 <                    throw new ConcurrentModificationException();
1094 >                throw new ConcurrentModificationException();
1095              }
1096          }
1097  
1098 <        public void remove() {
1099 <            if (lastRet < 0)
1100 <                throw new IllegalStateException();
1101 <            if (expectedModCount != modCount)
1102 <                throw new ConcurrentModificationException();
1103 <            ArrayList.this.remove(lastRet);
1104 <            if (lastRet < cursor)
1105 <                cursor--;
1106 <            lastRet = -1;
1107 <            expectedModCount = modCount;
723 <        }
724 <
725 <        public void set(E e) {
726 <            if (lastRet < 0)
727 <                throw new IllegalStateException();
728 <            if (expectedModCount != modCount)
1098 >        public void add(E e) {
1099 >            checkForComodification();
1100 >
1101 >            try {
1102 >                int i = cursor;
1103 >                ArrayList.this.add(i, e);
1104 >                cursor = i + 1;
1105 >                lastRet = -1;
1106 >                expectedModCount = modCount;
1107 >            } catch (IndexOutOfBoundsException ex) {
1108                  throw new ConcurrentModificationException();
1109 <            ArrayList.this.set(lastRet, e);
1110 <            expectedModCount = modCount;
1111 <        }
1109 >            }
1110 >        }
1111 >    }
1112 >
1113 >    /**
1114 >     * Returns a view of the portion of this list between the specified
1115 >     * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If
1116 >     * {@code fromIndex} and {@code toIndex} are equal, the returned list is
1117 >     * empty.)  The returned list is backed by this list, so non-structural
1118 >     * changes in the returned list are reflected in this list, and vice-versa.
1119 >     * The returned list supports all of the optional list operations.
1120 >     *
1121 >     * <p>This method eliminates the need for explicit range operations (of
1122 >     * the sort that commonly exist for arrays).  Any operation that expects
1123 >     * a list can be used as a range operation by passing a subList view
1124 >     * instead of a whole list.  For example, the following idiom
1125 >     * removes a range of elements from a list:
1126 >     * <pre>
1127 >     *      list.subList(from, to).clear();
1128 >     * </pre>
1129 >     * Similar idioms may be constructed for {@link #indexOf(Object)} and
1130 >     * {@link #lastIndexOf(Object)}, and all of the algorithms in the
1131 >     * {@link Collections} class can be applied to a subList.
1132 >     *
1133 >     * <p>The semantics of the list returned by this method become undefined if
1134 >     * the backing list (i.e., this list) is <i>structurally modified</i> in
1135 >     * any way other than via the returned list.  (Structural modifications are
1136 >     * those that change the size of this list, or otherwise perturb it in such
1137 >     * a fashion that iterations in progress may yield incorrect results.)
1138 >     *
1139 >     * @throws IndexOutOfBoundsException {@inheritDoc}
1140 >     * @throws IllegalArgumentException {@inheritDoc}
1141 >     */
1142 >    public List<E> subList(int fromIndex, int toIndex) {
1143 >        subListRangeCheck(fromIndex, toIndex, size);
1144 >        return new SubList<>(this, fromIndex, toIndex);
1145 >    }
1146 >
1147 >    private static class SubList<E> extends AbstractList<E> implements RandomAccess {
1148 >        private final ArrayList<E> root;
1149 >        private final SubList<E> parent;
1150 >        private final int offset;
1151 >        private int size;
1152 >
1153 >        /**
1154 >         * Constructs a sublist of an arbitrary ArrayList.
1155 >         */
1156 >        public SubList(ArrayList<E> root, int fromIndex, int toIndex) {
1157 >            this.root = root;
1158 >            this.parent = null;
1159 >            this.offset = fromIndex;
1160 >            this.size = toIndex - fromIndex;
1161 >            this.modCount = root.modCount;
1162 >        }
1163 >
1164 >        /**
1165 >         * Constructs a sublist of another SubList.
1166 >         */
1167 >        private SubList(SubList<E> parent, int fromIndex, int toIndex) {
1168 >            this.root = parent.root;
1169 >            this.parent = parent;
1170 >            this.offset = parent.offset + fromIndex;
1171 >            this.size = toIndex - fromIndex;
1172 >            this.modCount = root.modCount;
1173 >        }
1174 >
1175 >        public E set(int index, E element) {
1176 >            Objects.checkIndex(index, size);
1177 >            checkForComodification();
1178 >            E oldValue = root.elementData(offset + index);
1179 >            root.elementData[offset + index] = element;
1180 >            return oldValue;
1181 >        }
1182 >
1183 >        public E get(int index) {
1184 >            Objects.checkIndex(index, size);
1185 >            checkForComodification();
1186 >            return root.elementData(offset + index);
1187 >        }
1188 >
1189 >        public int size() {
1190 >            checkForComodification();
1191 >            return size;
1192 >        }
1193 >
1194 >        public void add(int index, E element) {
1195 >            rangeCheckForAdd(index);
1196 >            checkForComodification();
1197 >            root.add(offset + index, element);
1198 >            updateSizeAndModCount(1);
1199 >        }
1200 >
1201 >        public E remove(int index) {
1202 >            Objects.checkIndex(index, size);
1203 >            checkForComodification();
1204 >            E result = root.remove(offset + index);
1205 >            updateSizeAndModCount(-1);
1206 >            return result;
1207 >        }
1208 >
1209 >        protected void removeRange(int fromIndex, int toIndex) {
1210 >            checkForComodification();
1211 >            root.removeRange(offset + fromIndex, offset + toIndex);
1212 >            updateSizeAndModCount(fromIndex - toIndex);
1213 >        }
1214 >
1215 >        public boolean addAll(Collection<? extends E> c) {
1216 >            return addAll(this.size, c);
1217 >        }
1218 >
1219 >        public boolean addAll(int index, Collection<? extends E> c) {
1220 >            rangeCheckForAdd(index);
1221 >            int cSize = c.size();
1222 >            if (cSize==0)
1223 >                return false;
1224 >            checkForComodification();
1225 >            root.addAll(offset + index, c);
1226 >            updateSizeAndModCount(cSize);
1227 >            return true;
1228 >        }
1229 >
1230 >        public void replaceAll(UnaryOperator<E> operator) {
1231 >            root.replaceAllRange(operator, offset, offset + size);
1232 >        }
1233 >
1234 >        public boolean removeAll(Collection<?> c) {
1235 >            return batchRemove(c, false);
1236 >        }
1237 >
1238 >        public boolean retainAll(Collection<?> c) {
1239 >            return batchRemove(c, true);
1240 >        }
1241 >
1242 >        private boolean batchRemove(Collection<?> c, boolean complement) {
1243 >            checkForComodification();
1244 >            int oldSize = root.size;
1245 >            boolean modified =
1246 >                root.batchRemove(c, complement, offset, offset + size);
1247 >            if (modified)
1248 >                updateSizeAndModCount(root.size - oldSize);
1249 >            return modified;
1250 >        }
1251 >
1252 >        public boolean removeIf(Predicate<? super E> filter) {
1253 >            checkForComodification();
1254 >            int oldSize = root.size;
1255 >            boolean modified = root.removeIf(filter, offset, offset + size);
1256 >            if (modified)
1257 >                updateSizeAndModCount(root.size - oldSize);
1258 >            return modified;
1259 >        }
1260 >
1261 >        public Object[] toArray() {
1262 >            checkForComodification();
1263 >            return Arrays.copyOfRange(root.elementData, offset, offset + size);
1264 >        }
1265 >
1266 >        @SuppressWarnings("unchecked")
1267 >        public <T> T[] toArray(T[] a) {
1268 >            checkForComodification();
1269 >            if (a.length < size)
1270 >                return (T[]) Arrays.copyOfRange(
1271 >                        root.elementData, offset, offset + size, a.getClass());
1272 >            System.arraycopy(root.elementData, offset, a, 0, size);
1273 >            if (a.length > size)
1274 >                a[size] = null;
1275 >            return a;
1276 >        }
1277 >
1278 >        public boolean equals(Object o) {
1279 >            if (o == this) {
1280 >                return true;
1281 >            }
1282  
1283 <        public void add(E e) {
1284 <            if (expectedModCount != modCount)
1283 >            if (!(o instanceof List)) {
1284 >                return false;
1285 >            }
1286 >
1287 >            boolean equal = root.equalsRange((List<?>)o, offset, offset + size);
1288 >            checkForComodification();
1289 >            return equal;
1290 >        }
1291 >
1292 >        public int hashCode() {
1293 >            int hash = root.hashCodeRange(offset, offset + size);
1294 >            checkForComodification();
1295 >            return hash;
1296 >        }
1297 >
1298 >        public int indexOf(Object o) {
1299 >            int index = root.indexOfRange(o, offset, offset + size);
1300 >            checkForComodification();
1301 >            return index >= 0 ? index - offset : -1;
1302 >        }
1303 >
1304 >        public int lastIndexOf(Object o) {
1305 >            int index = root.lastIndexOfRange(o, offset, offset + size);
1306 >            checkForComodification();
1307 >            return index >= 0 ? index - offset : -1;
1308 >        }
1309 >
1310 >        public boolean contains(Object o) {
1311 >            return indexOf(o) >= 0;
1312 >        }
1313 >
1314 >        public Iterator<E> iterator() {
1315 >            return listIterator();
1316 >        }
1317 >
1318 >        public ListIterator<E> listIterator(int index) {
1319 >            checkForComodification();
1320 >            rangeCheckForAdd(index);
1321 >
1322 >            return new ListIterator<E>() {
1323 >                int cursor = index;
1324 >                int lastRet = -1;
1325 >                int expectedModCount = root.modCount;
1326 >
1327 >                public boolean hasNext() {
1328 >                    return cursor != SubList.this.size;
1329 >                }
1330 >
1331 >                @SuppressWarnings("unchecked")
1332 >                public E next() {
1333 >                    checkForComodification();
1334 >                    int i = cursor;
1335 >                    if (i >= SubList.this.size)
1336 >                        throw new NoSuchElementException();
1337 >                    Object[] elementData = root.elementData;
1338 >                    if (offset + i >= elementData.length)
1339 >                        throw new ConcurrentModificationException();
1340 >                    cursor = i + 1;
1341 >                    return (E) elementData[offset + (lastRet = i)];
1342 >                }
1343 >
1344 >                public boolean hasPrevious() {
1345 >                    return cursor != 0;
1346 >                }
1347 >
1348 >                @SuppressWarnings("unchecked")
1349 >                public E previous() {
1350 >                    checkForComodification();
1351 >                    int i = cursor - 1;
1352 >                    if (i < 0)
1353 >                        throw new NoSuchElementException();
1354 >                    Object[] elementData = root.elementData;
1355 >                    if (offset + i >= elementData.length)
1356 >                        throw new ConcurrentModificationException();
1357 >                    cursor = i;
1358 >                    return (E) elementData[offset + (lastRet = i)];
1359 >                }
1360 >
1361 >                public void forEachRemaining(Consumer<? super E> action) {
1362 >                    Objects.requireNonNull(action);
1363 >                    final int size = SubList.this.size;
1364 >                    int i = cursor;
1365 >                    if (i < size) {
1366 >                        final Object[] es = root.elementData;
1367 >                        if (offset + i >= es.length)
1368 >                            throw new ConcurrentModificationException();
1369 >                        for (; i < size && modCount == expectedModCount; i++)
1370 >                            action.accept(elementAt(es, offset + i));
1371 >                        // update once at end to reduce heap write traffic
1372 >                        cursor = i;
1373 >                        lastRet = i - 1;
1374 >                        checkForComodification();
1375 >                    }
1376 >                }
1377 >
1378 >                public int nextIndex() {
1379 >                    return cursor;
1380 >                }
1381 >
1382 >                public int previousIndex() {
1383 >                    return cursor - 1;
1384 >                }
1385 >
1386 >                public void remove() {
1387 >                    if (lastRet < 0)
1388 >                        throw new IllegalStateException();
1389 >                    checkForComodification();
1390 >
1391 >                    try {
1392 >                        SubList.this.remove(lastRet);
1393 >                        cursor = lastRet;
1394 >                        lastRet = -1;
1395 >                        expectedModCount = root.modCount;
1396 >                    } catch (IndexOutOfBoundsException ex) {
1397 >                        throw new ConcurrentModificationException();
1398 >                    }
1399 >                }
1400 >
1401 >                public void set(E e) {
1402 >                    if (lastRet < 0)
1403 >                        throw new IllegalStateException();
1404 >                    checkForComodification();
1405 >
1406 >                    try {
1407 >                        root.set(offset + lastRet, e);
1408 >                    } catch (IndexOutOfBoundsException ex) {
1409 >                        throw new ConcurrentModificationException();
1410 >                    }
1411 >                }
1412 >
1413 >                public void add(E e) {
1414 >                    checkForComodification();
1415 >
1416 >                    try {
1417 >                        int i = cursor;
1418 >                        SubList.this.add(i, e);
1419 >                        cursor = i + 1;
1420 >                        lastRet = -1;
1421 >                        expectedModCount = root.modCount;
1422 >                    } catch (IndexOutOfBoundsException ex) {
1423 >                        throw new ConcurrentModificationException();
1424 >                    }
1425 >                }
1426 >
1427 >                final void checkForComodification() {
1428 >                    if (root.modCount != expectedModCount)
1429 >                        throw new ConcurrentModificationException();
1430 >                }
1431 >            };
1432 >        }
1433 >
1434 >        public List<E> subList(int fromIndex, int toIndex) {
1435 >            subListRangeCheck(fromIndex, toIndex, size);
1436 >            return new SubList<>(this, fromIndex, toIndex);
1437 >        }
1438 >
1439 >        private void rangeCheckForAdd(int index) {
1440 >            if (index < 0 || index > this.size)
1441 >                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1442 >        }
1443 >
1444 >        private String outOfBoundsMsg(int index) {
1445 >            return "Index: "+index+", Size: "+this.size;
1446 >        }
1447 >
1448 >        private void checkForComodification() {
1449 >            if (root.modCount != modCount)
1450                  throw new ConcurrentModificationException();
1451 <            try {
1452 <                ArrayList.this.add(cursor++, e);
1453 <                lastRet = -1;
1451 >        }
1452 >
1453 >        private void updateSizeAndModCount(int sizeChange) {
1454 >            SubList<E> slist = this;
1455 >            do {
1456 >                slist.size += sizeChange;
1457 >                slist.modCount = root.modCount;
1458 >                slist = slist.parent;
1459 >            } while (slist != null);
1460 >        }
1461 >
1462 >        public Spliterator<E> spliterator() {
1463 >            checkForComodification();
1464 >
1465 >            // ArrayListSpliterator not used here due to late-binding
1466 >            return new Spliterator<E>() {
1467 >                private int index = offset; // current index, modified on advance/split
1468 >                private int fence = -1; // -1 until used; then one past last index
1469 >                private int expectedModCount; // initialized when fence set
1470 >
1471 >                private int getFence() { // initialize fence to size on first use
1472 >                    int hi; // (a specialized variant appears in method forEach)
1473 >                    if ((hi = fence) < 0) {
1474 >                        expectedModCount = modCount;
1475 >                        hi = fence = offset + size;
1476 >                    }
1477 >                    return hi;
1478 >                }
1479 >
1480 >                public ArrayList<E>.ArrayListSpliterator trySplit() {
1481 >                    int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1482 >                    // ArrayListSpliterator can be used here as the source is already bound
1483 >                    return (lo >= mid) ? null : // divide range in half unless too small
1484 >                        root.new ArrayListSpliterator(lo, index = mid, expectedModCount);
1485 >                }
1486 >
1487 >                public boolean tryAdvance(Consumer<? super E> action) {
1488 >                    Objects.requireNonNull(action);
1489 >                    int hi = getFence(), i = index;
1490 >                    if (i < hi) {
1491 >                        index = i + 1;
1492 >                        @SuppressWarnings("unchecked") E e = (E)root.elementData[i];
1493 >                        action.accept(e);
1494 >                        if (root.modCount != expectedModCount)
1495 >                            throw new ConcurrentModificationException();
1496 >                        return true;
1497 >                    }
1498 >                    return false;
1499 >                }
1500 >
1501 >                public void forEachRemaining(Consumer<? super E> action) {
1502 >                    Objects.requireNonNull(action);
1503 >                    int i, hi, mc; // hoist accesses and checks from loop
1504 >                    ArrayList<E> lst = root;
1505 >                    Object[] a;
1506 >                    if ((a = lst.elementData) != null) {
1507 >                        if ((hi = fence) < 0) {
1508 >                            mc = modCount;
1509 >                            hi = offset + size;
1510 >                        }
1511 >                        else
1512 >                            mc = expectedModCount;
1513 >                        if ((i = index) >= 0 && (index = hi) <= a.length) {
1514 >                            for (; i < hi; ++i) {
1515 >                                @SuppressWarnings("unchecked") E e = (E) a[i];
1516 >                                action.accept(e);
1517 >                            }
1518 >                            if (lst.modCount == mc)
1519 >                                return;
1520 >                        }
1521 >                    }
1522 >                    throw new ConcurrentModificationException();
1523 >                }
1524 >
1525 >                public long estimateSize() {
1526 >                    return getFence() - index;
1527 >                }
1528 >
1529 >                public int characteristics() {
1530 >                    return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
1531 >                }
1532 >            };
1533 >        }
1534 >    }
1535 >
1536 >    /**
1537 >     * @throws NullPointerException {@inheritDoc}
1538 >     */
1539 >    @Override
1540 >    public void forEach(Consumer<? super E> action) {
1541 >        Objects.requireNonNull(action);
1542 >        final int expectedModCount = modCount;
1543 >        final Object[] es = elementData;
1544 >        final int size = this.size;
1545 >        for (int i = 0; modCount == expectedModCount && i < size; i++)
1546 >            action.accept(elementAt(es, i));
1547 >        if (modCount != expectedModCount)
1548 >            throw new ConcurrentModificationException();
1549 >    }
1550 >
1551 >    /**
1552 >     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
1553 >     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
1554 >     * list.
1555 >     *
1556 >     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
1557 >     * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
1558 >     * Overriding implementations should document the reporting of additional
1559 >     * characteristic values.
1560 >     *
1561 >     * @return a {@code Spliterator} over the elements in this list
1562 >     * @since 1.8
1563 >     */
1564 >    @Override
1565 >    public Spliterator<E> spliterator() {
1566 >        return new ArrayListSpliterator(0, -1, 0);
1567 >    }
1568 >
1569 >    /** Index-based split-by-two, lazily initialized Spliterator */
1570 >    final class ArrayListSpliterator implements Spliterator<E> {
1571 >
1572 >        /*
1573 >         * If ArrayLists were immutable, or structurally immutable (no
1574 >         * adds, removes, etc), we could implement their spliterators
1575 >         * with Arrays.spliterator. Instead we detect as much
1576 >         * interference during traversal as practical without
1577 >         * sacrificing much performance. We rely primarily on
1578 >         * modCounts. These are not guaranteed to detect concurrency
1579 >         * violations, and are sometimes overly conservative about
1580 >         * within-thread interference, but detect enough problems to
1581 >         * be worthwhile in practice. To carry this out, we (1) lazily
1582 >         * initialize fence and expectedModCount until the latest
1583 >         * point that we need to commit to the state we are checking
1584 >         * against; thus improving precision.  (This doesn't apply to
1585 >         * SubLists, that create spliterators with current non-lazy
1586 >         * values).  (2) We perform only a single
1587 >         * ConcurrentModificationException check at the end of forEach
1588 >         * (the most performance-sensitive method). When using forEach
1589 >         * (as opposed to iterators), we can normally only detect
1590 >         * interference after actions, not before. Further
1591 >         * CME-triggering checks apply to all other possible
1592 >         * violations of assumptions for example null or too-small
1593 >         * elementData array given its size(), that could only have
1594 >         * occurred due to interference.  This allows the inner loop
1595 >         * of forEach to run without any further checks, and
1596 >         * simplifies lambda-resolution. While this does entail a
1597 >         * number of checks, note that in the common case of
1598 >         * list.stream().forEach(a), no checks or other computation
1599 >         * occur anywhere other than inside forEach itself.  The other
1600 >         * less-often-used methods cannot take advantage of most of
1601 >         * these streamlinings.
1602 >         */
1603 >
1604 >        private int index; // current index, modified on advance/split
1605 >        private int fence; // -1 until used; then one past last index
1606 >        private int expectedModCount; // initialized when fence set
1607 >
1608 >        /** Creates new spliterator covering the given range. */
1609 >        ArrayListSpliterator(int origin, int fence, int expectedModCount) {
1610 >            this.index = origin;
1611 >            this.fence = fence;
1612 >            this.expectedModCount = expectedModCount;
1613 >        }
1614 >
1615 >        private int getFence() { // initialize fence to size on first use
1616 >            int hi; // (a specialized variant appears in method forEach)
1617 >            if ((hi = fence) < 0) {
1618                  expectedModCount = modCount;
1619 <            } catch (IndexOutOfBoundsException ex) {
1620 <                throw new ConcurrentModificationException();
1621 <            }
1622 <        }
1619 >                hi = fence = size;
1620 >            }
1621 >            return hi;
1622 >        }
1623 >
1624 >        public ArrayListSpliterator trySplit() {
1625 >            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
1626 >            return (lo >= mid) ? null : // divide range in half unless too small
1627 >                new ArrayListSpliterator(lo, index = mid, expectedModCount);
1628 >        }
1629 >
1630 >        public boolean tryAdvance(Consumer<? super E> action) {
1631 >            if (action == null)
1632 >                throw new NullPointerException();
1633 >            int hi = getFence(), i = index;
1634 >            if (i < hi) {
1635 >                index = i + 1;
1636 >                @SuppressWarnings("unchecked") E e = (E)elementData[i];
1637 >                action.accept(e);
1638 >                if (modCount != expectedModCount)
1639 >                    throw new ConcurrentModificationException();
1640 >                return true;
1641 >            }
1642 >            return false;
1643 >        }
1644 >
1645 >        public void forEachRemaining(Consumer<? super E> action) {
1646 >            int i, hi, mc; // hoist accesses and checks from loop
1647 >            Object[] a;
1648 >            if (action == null)
1649 >                throw new NullPointerException();
1650 >            if ((a = elementData) != null) {
1651 >                if ((hi = fence) < 0) {
1652 >                    mc = modCount;
1653 >                    hi = size;
1654 >                }
1655 >                else
1656 >                    mc = expectedModCount;
1657 >                if ((i = index) >= 0 && (index = hi) <= a.length) {
1658 >                    for (; i < hi; ++i) {
1659 >                        @SuppressWarnings("unchecked") E e = (E) a[i];
1660 >                        action.accept(e);
1661 >                    }
1662 >                    if (modCount == mc)
1663 >                        return;
1664 >                }
1665 >            }
1666 >            throw new ConcurrentModificationException();
1667 >        }
1668 >
1669 >        public long estimateSize() {
1670 >            return getFence() - index;
1671 >        }
1672 >
1673 >        public int characteristics() {
1674 >            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
1675 >        }
1676 >    }
1677 >
1678 >    // A tiny bit set implementation
1679 >
1680 >    private static long[] nBits(int n) {
1681 >        return new long[((n - 1) >> 6) + 1];
1682 >    }
1683 >    private static void setBit(long[] bits, int i) {
1684 >        bits[i >> 6] |= 1L << i;
1685 >    }
1686 >    private static boolean isClear(long[] bits, int i) {
1687 >        return (bits[i >> 6] & (1L << i)) == 0;
1688 >    }
1689 >
1690 >    /**
1691 >     * @throws NullPointerException {@inheritDoc}
1692 >     */
1693 >    @Override
1694 >    public boolean removeIf(Predicate<? super E> filter) {
1695 >        return removeIf(filter, 0, size);
1696 >    }
1697 >
1698 >    /**
1699 >     * Removes all elements satisfying the given predicate, from index
1700 >     * i (inclusive) to index end (exclusive).
1701 >     */
1702 >    boolean removeIf(Predicate<? super E> filter, int i, final int end) {
1703 >        Objects.requireNonNull(filter);
1704 >        int expectedModCount = modCount;
1705 >        final Object[] es = elementData;
1706 >        // Optimize for initial run of survivors
1707 >        for (; i < end && !filter.test(elementAt(es, i)); i++)
1708 >            ;
1709 >        // Tolerate predicates that reentrantly access the collection for
1710 >        // read (but writers still get CME), so traverse once to find
1711 >        // elements to delete, a second pass to physically expunge.
1712 >        if (i < end) {
1713 >            final int beg = i;
1714 >            final long[] deathRow = nBits(end - beg);
1715 >            deathRow[0] = 1L;   // set bit 0
1716 >            for (i = beg + 1; i < end; i++)
1717 >                if (filter.test(elementAt(es, i)))
1718 >                    setBit(deathRow, i - beg);
1719 >            if (modCount != expectedModCount)
1720 >                throw new ConcurrentModificationException();
1721 >            modCount++;
1722 >            int w = beg;
1723 >            for (i = beg; i < end; i++)
1724 >                if (isClear(deathRow, i - beg))
1725 >                    es[w++] = es[i];
1726 >            shiftTailOverGap(es, w, end);
1727 >            // checkInvariants();
1728 >            return true;
1729 >        } else {
1730 >            if (modCount != expectedModCount)
1731 >                throw new ConcurrentModificationException();
1732 >            // checkInvariants();
1733 >            return false;
1734 >        }
1735 >    }
1736 >
1737 >    @Override
1738 >    public void replaceAll(UnaryOperator<E> operator) {
1739 >        replaceAllRange(operator, 0, size);
1740 >    }
1741 >
1742 >    private void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
1743 >        Objects.requireNonNull(operator);
1744 >        final int expectedModCount = modCount;
1745 >        final Object[] es = elementData;
1746 >        for (; modCount == expectedModCount && i < end; i++)
1747 >            es[i] = operator.apply(elementAt(es, i));
1748 >        if (modCount != expectedModCount)
1749 >            throw new ConcurrentModificationException();
1750 >        // checkInvariants();
1751 >    }
1752 >
1753 >    @Override
1754 >    @SuppressWarnings("unchecked")
1755 >    public void sort(Comparator<? super E> c) {
1756 >        final int expectedModCount = modCount;
1757 >        Arrays.sort((E[]) elementData, 0, size, c);
1758 >        if (modCount != expectedModCount)
1759 >            throw new ConcurrentModificationException();
1760 >        modCount++;
1761 >        // checkInvariants();
1762 >    }
1763 >
1764 >    void checkInvariants() {
1765 >        // assert size >= 0;
1766 >        // assert size == elementData.length || elementData[size] == null;
1767      }
1768   }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines