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