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