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