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