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 public boolean hasNext() { 880 return cursor != size; 881 } 882 883 @SuppressWarnings("unchecked") 884 public E next() { 885 checkForComodification(); 886 int i = cursor; 887 if (i >= size) 888 throw new NoSuchElementException(); 889 Object[] elementData = ArrayList.this.elementData; 890 if (i >= elementData.length) 891 throw new ConcurrentModificationException(); 892 cursor = i + 1; 893 return (E) elementData[lastRet = i]; 894 } 895 896 public void remove() { 897 if (lastRet < 0) 898 throw new IllegalStateException(); 899 checkForComodification(); 900 901 try { 902 ArrayList.this.remove(lastRet); 903 cursor = lastRet; 904 lastRet = -1; 905 expectedModCount = modCount; 906 } catch (IndexOutOfBoundsException ex) { 907 throw new ConcurrentModificationException(); 908 } 909 } 910 911 @Override 912 @SuppressWarnings("unchecked") 913 public void forEachRemaining(Consumer<? super E> consumer) { 914 Objects.requireNonNull(consumer); 915 final int size = ArrayList.this.size; 916 int i = cursor; 917 if (i >= size) { 918 return; 919 } 920 final Object[] elementData = ArrayList.this.elementData; 921 if (i >= elementData.length) { 922 throw new ConcurrentModificationException(); 923 } 924 while (i != size && modCount == expectedModCount) { 925 consumer.accept((E) elementData[i++]); 926 } 927 // update once at end of iteration to reduce heap write traffic 928 cursor = i; 929 lastRet = i - 1; 930 checkForComodification(); 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 Iterator<E> iterator() { 1118 return listIterator(); 1119 } 1120 1121 public ListIterator<E> listIterator(int index) { 1122 checkForComodification(); 1123 rangeCheckForAdd(index); 1124 1125 return new ListIterator<E>() { 1126 int cursor = index; 1127 int lastRet = -1; 1128 int expectedModCount = root.modCount; 1129 1130 public boolean hasNext() { 1131 return cursor != SubList.this.size; 1132 } 1133 1134 @SuppressWarnings("unchecked") 1135 public E next() { 1136 checkForComodification(); 1137 int i = cursor; 1138 if (i >= SubList.this.size) 1139 throw new NoSuchElementException(); 1140 Object[] elementData = root.elementData; 1141 if (offset + i >= elementData.length) 1142 throw new ConcurrentModificationException(); 1143 cursor = i + 1; 1144 return (E) elementData[offset + (lastRet = i)]; 1145 } 1146 1147 public boolean hasPrevious() { 1148 return cursor != 0; 1149 } 1150 1151 @SuppressWarnings("unchecked") 1152 public E previous() { 1153 checkForComodification(); 1154 int i = cursor - 1; 1155 if (i < 0) 1156 throw new NoSuchElementException(); 1157 Object[] elementData = root.elementData; 1158 if (offset + i >= elementData.length) 1159 throw new ConcurrentModificationException(); 1160 cursor = i; 1161 return (E) elementData[offset + (lastRet = i)]; 1162 } 1163 1164 @SuppressWarnings("unchecked") 1165 public void forEachRemaining(Consumer<? super E> consumer) { 1166 Objects.requireNonNull(consumer); 1167 final int size = SubList.this.size; 1168 int i = cursor; 1169 if (i >= size) { 1170 return; 1171 } 1172 final Object[] elementData = root.elementData; 1173 if (offset + i >= elementData.length) { 1174 throw new ConcurrentModificationException(); 1175 } 1176 while (i != size && modCount == expectedModCount) { 1177 consumer.accept((E) elementData[offset + (i++)]); 1178 } 1179 // update once at end of iteration to reduce heap write traffic 1180 lastRet = cursor = i; 1181 checkForComodification(); 1182 } 1183 1184 public int nextIndex() { 1185 return cursor; 1186 } 1187 1188 public int previousIndex() { 1189 return cursor - 1; 1190 } 1191 1192 public void remove() { 1193 if (lastRet < 0) 1194 throw new IllegalStateException(); 1195 checkForComodification(); 1196 1197 try { 1198 SubList.this.remove(lastRet); 1199 cursor = lastRet; 1200 lastRet = -1; 1201 expectedModCount = root.modCount; 1202 } catch (IndexOutOfBoundsException ex) { 1203 throw new ConcurrentModificationException(); 1204 } 1205 } 1206 1207 public void set(E e) { 1208 if (lastRet < 0) 1209 throw new IllegalStateException(); 1210 checkForComodification(); 1211 1212 try { 1213 root.set(offset + lastRet, e); 1214 } catch (IndexOutOfBoundsException ex) { 1215 throw new ConcurrentModificationException(); 1216 } 1217 } 1218 1219 public void add(E e) { 1220 checkForComodification(); 1221 1222 try { 1223 int i = cursor; 1224 SubList.this.add(i, e); 1225 cursor = i + 1; 1226 lastRet = -1; 1227 expectedModCount = root.modCount; 1228 } catch (IndexOutOfBoundsException ex) { 1229 throw new ConcurrentModificationException(); 1230 } 1231 } 1232 1233 final void checkForComodification() { 1234 if (root.modCount != expectedModCount) 1235 throw new ConcurrentModificationException(); 1236 } 1237 }; 1238 } 1239 1240 public List<E> subList(int fromIndex, int toIndex) { 1241 subListRangeCheck(fromIndex, toIndex, size); 1242 return new SubList<>(this, fromIndex, toIndex); 1243 } 1244 1245 private void rangeCheckForAdd(int index) { 1246 if (index < 0 || index > this.size) 1247 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1248 } 1249 1250 private String outOfBoundsMsg(int index) { 1251 return "Index: "+index+", Size: "+this.size; 1252 } 1253 1254 private void checkForComodification() { 1255 if (root.modCount != modCount) 1256 throw new ConcurrentModificationException(); 1257 } 1258 1259 private void updateSizeAndModCount(int sizeChange) { 1260 SubList<E> slist = this; 1261 do { 1262 slist.size += sizeChange; 1263 slist.modCount = root.modCount; 1264 slist = slist.parent; 1265 } while (slist != null); 1266 } 1267 1268 public Spliterator<E> spliterator() { 1269 checkForComodification(); 1270 1271 // ArrayListSpliterator is not used because late-binding logic 1272 // is different here 1273 return new Spliterator<>() { 1274 private int index = offset; // current index, modified on advance/split 1275 private int fence = -1; // -1 until used; then one past last index 1276 private int expectedModCount; // initialized when fence set 1277 1278 private int getFence() { // initialize fence to size on first use 1279 int hi; // (a specialized variant appears in method forEach) 1280 if ((hi = fence) < 0) { 1281 expectedModCount = modCount; 1282 hi = fence = offset + size; 1283 } 1284 return hi; 1285 } 1286 1287 public ArrayListSpliterator<E> trySplit() { 1288 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1289 // ArrayListSpliterator could be used here as the source is already bound 1290 return (lo >= mid) ? null : // divide range in half unless too small 1291 new ArrayListSpliterator<>(root, lo, index = mid, 1292 expectedModCount); 1293 } 1294 1295 public boolean tryAdvance(Consumer<? super E> action) { 1296 Objects.requireNonNull(action); 1297 int hi = getFence(), i = index; 1298 if (i < hi) { 1299 index = i + 1; 1300 @SuppressWarnings("unchecked") E e = (E)root.elementData[i]; 1301 action.accept(e); 1302 if (root.modCount != expectedModCount) 1303 throw new ConcurrentModificationException(); 1304 return true; 1305 } 1306 return false; 1307 } 1308 1309 public void forEachRemaining(Consumer<? super E> action) { 1310 Objects.requireNonNull(action); 1311 int i, hi, mc; // hoist accesses and checks from loop 1312 ArrayList<E> lst = root; 1313 Object[] a; 1314 if ((a = lst.elementData) != null) { 1315 if ((hi = fence) < 0) { 1316 mc = modCount; 1317 hi = offset + size; 1318 } 1319 else 1320 mc = expectedModCount; 1321 if ((i = index) >= 0 && (index = hi) <= a.length) { 1322 for (; i < hi; ++i) { 1323 @SuppressWarnings("unchecked") E e = (E) a[i]; 1324 action.accept(e); 1325 } 1326 if (lst.modCount == mc) 1327 return; 1328 } 1329 } 1330 throw new ConcurrentModificationException(); 1331 } 1332 1333 public long estimateSize() { 1334 return (long) (getFence() - index); 1335 } 1336 1337 public int characteristics() { 1338 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; 1339 } 1340 }; 1341 } 1342 } 1343 1344 @Override 1345 public void forEach(Consumer<? super E> action) { 1346 Objects.requireNonNull(action); 1347 final int expectedModCount = modCount; 1348 @SuppressWarnings("unchecked") 1349 final E[] elementData = (E[]) this.elementData; 1350 final int size = this.size; 1351 for (int i=0; modCount == expectedModCount && i < size; i++) { 1352 action.accept(elementData[i]); 1353 } 1354 if (modCount != expectedModCount) { 1355 throw new ConcurrentModificationException(); 1356 } 1357 } 1358 1359 /** 1360 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> 1361 * and <em>fail-fast</em> {@link Spliterator} over the elements in this 1362 * list. 1363 * 1364 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, 1365 * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}. 1366 * Overriding implementations should document the reporting of additional 1367 * characteristic values. 1368 * 1369 * @return a {@code Spliterator} over the elements in this list 1370 * @since 1.8 1371 */ 1372 @Override 1373 public Spliterator<E> spliterator() { 1374 return new ArrayListSpliterator<>(this, 0, -1, 0); 1375 } 1376 1377 /** Index-based split-by-two, lazily initialized Spliterator */ 1378 static final class ArrayListSpliterator<E> implements Spliterator<E> { 1379 1380 /* 1381 * If ArrayLists were immutable, or structurally immutable (no 1382 * adds, removes, etc), we could implement their spliterators 1383 * with Arrays.spliterator. Instead we detect as much 1384 * interference during traversal as practical without 1385 * sacrificing much performance. We rely primarily on 1386 * modCounts. These are not guaranteed to detect concurrency 1387 * violations, and are sometimes overly conservative about 1388 * within-thread interference, but detect enough problems to 1389 * be worthwhile in practice. To carry this out, we (1) lazily 1390 * initialize fence and expectedModCount until the latest 1391 * point that we need to commit to the state we are checking 1392 * against; thus improving precision. (This doesn't apply to 1393 * SubLists, that create spliterators with current non-lazy 1394 * values). (2) We perform only a single 1395 * ConcurrentModificationException check at the end of forEach 1396 * (the most performance-sensitive method). When using forEach 1397 * (as opposed to iterators), we can normally only detect 1398 * interference after actions, not before. Further 1399 * CME-triggering checks apply to all other possible 1400 * violations of assumptions for example null or too-small 1401 * elementData array given its size(), that could only have 1402 * occurred due to interference. This allows the inner loop 1403 * of forEach to run without any further checks, and 1404 * simplifies lambda-resolution. While this does entail a 1405 * number of checks, note that in the common case of 1406 * list.stream().forEach(a), no checks or other computation 1407 * occur anywhere other than inside forEach itself. The other 1408 * less-often-used methods cannot take advantage of most of 1409 * these streamlinings. 1410 */ 1411 1412 private final ArrayList<E> list; 1413 private int index; // current index, modified on advance/split 1414 private int fence; // -1 until used; then one past last index 1415 private int expectedModCount; // initialized when fence set 1416 1417 /** Create new spliterator covering the given range */ 1418 ArrayListSpliterator(ArrayList<E> list, int origin, int fence, 1419 int expectedModCount) { 1420 this.list = list; // OK if null unless traversed 1421 this.index = origin; 1422 this.fence = fence; 1423 this.expectedModCount = expectedModCount; 1424 } 1425 1426 private int getFence() { // initialize fence to size on first use 1427 int hi; // (a specialized variant appears in method forEach) 1428 ArrayList<E> lst; 1429 if ((hi = fence) < 0) { 1430 if ((lst = list) == null) 1431 hi = fence = 0; 1432 else { 1433 expectedModCount = lst.modCount; 1434 hi = fence = lst.size; 1435 } 1436 } 1437 return hi; 1438 } 1439 1440 public ArrayListSpliterator<E> trySplit() { 1441 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1442 return (lo >= mid) ? null : // divide range in half unless too small 1443 new ArrayListSpliterator<>(list, lo, index = mid, 1444 expectedModCount); 1445 } 1446 1447 public boolean tryAdvance(Consumer<? super E> action) { 1448 if (action == null) 1449 throw new NullPointerException(); 1450 int hi = getFence(), i = index; 1451 if (i < hi) { 1452 index = i + 1; 1453 @SuppressWarnings("unchecked") E e = (E)list.elementData[i]; 1454 action.accept(e); 1455 if (list.modCount != expectedModCount) 1456 throw new ConcurrentModificationException(); 1457 return true; 1458 } 1459 return false; 1460 } 1461 1462 public void forEachRemaining(Consumer<? super E> action) { 1463 int i, hi, mc; // hoist accesses and checks from loop 1464 ArrayList<E> lst; Object[] a; 1465 if (action == null) 1466 throw new NullPointerException(); 1467 if ((lst = list) != null && (a = lst.elementData) != null) { 1468 if ((hi = fence) < 0) { 1469 mc = lst.modCount; 1470 hi = lst.size; 1471 } 1472 else 1473 mc = expectedModCount; 1474 if ((i = index) >= 0 && (index = hi) <= a.length) { 1475 for (; i < hi; ++i) { 1476 @SuppressWarnings("unchecked") E e = (E) a[i]; 1477 action.accept(e); 1478 } 1479 if (lst.modCount == mc) 1480 return; 1481 } 1482 } 1483 throw new ConcurrentModificationException(); 1484 } 1485 1486 public long estimateSize() { 1487 return (long) (getFence() - index); 1488 } 1489 1490 public int characteristics() { 1491 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED; 1492 } 1493 } 1494 1495 @Override 1496 public boolean removeIf(Predicate<? super E> filter) { 1497 Objects.requireNonNull(filter); 1498 // figure out which elements are to be removed 1499 // any exception thrown from the filter predicate at this stage 1500 // will leave the collection unmodified 1501 int removeCount = 0; 1502 final BitSet removeSet = new BitSet(size); 1503 final int expectedModCount = modCount; 1504 final int size = this.size; 1505 for (int i=0; modCount == expectedModCount && i < size; i++) { 1506 @SuppressWarnings("unchecked") 1507 final E element = (E) elementData[i]; 1508 if (filter.test(element)) { 1509 removeSet.set(i); 1510 removeCount++; 1511 } 1512 } 1513 if (modCount != expectedModCount) { 1514 throw new ConcurrentModificationException(); 1515 } 1516 1517 // shift surviving elements left over the spaces left by removed elements 1518 final boolean anyToRemove = removeCount > 0; 1519 if (anyToRemove) { 1520 final int newSize = size - removeCount; 1521 for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) { 1522 i = removeSet.nextClearBit(i); 1523 elementData[j] = elementData[i]; 1524 } 1525 for (int k=newSize; k < size; k++) { 1526 elementData[k] = null; // Let gc do its work 1527 } 1528 this.size = newSize; 1529 if (modCount != expectedModCount) { 1530 throw new ConcurrentModificationException(); 1531 } 1532 modCount++; 1533 } 1534 1535 return anyToRemove; 1536 } 1537 1538 @Override 1539 @SuppressWarnings("unchecked") 1540 public void replaceAll(UnaryOperator<E> operator) { 1541 Objects.requireNonNull(operator); 1542 final int expectedModCount = modCount; 1543 final int size = this.size; 1544 for (int i=0; modCount == expectedModCount && i < size; i++) { 1545 elementData[i] = operator.apply((E) elementData[i]); 1546 } 1547 if (modCount != expectedModCount) { 1548 throw new ConcurrentModificationException(); 1549 } 1550 modCount++; 1551 } 1552 1553 @Override 1554 @SuppressWarnings("unchecked") 1555 public void sort(Comparator<? super E> c) { 1556 final int expectedModCount = modCount; 1557 Arrays.sort((E[]) elementData, 0, size, c); 1558 if (modCount != expectedModCount) { 1559 throw new ConcurrentModificationException(); 1560 } 1561 modCount++; 1562 } 1563 }