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