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