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