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