ArrayList.java revision c3a9db83a352d92d5a6e0098f22bde07e34a1d3b
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. 4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 5 * 6 * This code is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 only, as 8 * published by the Free Software Foundation. Oracle designates this 9 * particular file as subject to the "Classpath" exception as provided 10 * by Oracle in the LICENSE file that accompanied this code. 11 * 12 * This code is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 * version 2 for more details (a copy is included in the LICENSE file that 16 * accompanied this code). 17 * 18 * You should have received a copy of the GNU General Public License version 19 * 2 along with this work; if not, write to the Free Software Foundation, 20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 21 * 22 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 23 * or visit www.oracle.com if you need additional information or have any 24 * questions. 25 */ 26 27package java.util; 28 29import java.util.function.Consumer; 30 31/** 32 * Resizable-array implementation of the <tt>List</tt> interface. Implements 33 * all optional list operations, and permits all elements, including 34 * <tt>null</tt>. In addition to implementing the <tt>List</tt> interface, 35 * this class provides methods to manipulate the size of the array that is 36 * used internally to store the list. (This class is roughly equivalent to 37 * <tt>Vector</tt>, except that it is unsynchronized.) 38 * 39 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>, 40 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant 41 * time. The <tt>add</tt> operation runs in <i>amortized constant time</i>, 42 * that is, adding n elements requires O(n) time. All of the other operations 43 * run in linear time (roughly speaking). The constant factor is low compared 44 * to that for the <tt>LinkedList</tt> implementation. 45 * 46 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is 47 * the size of the array used to store the elements in the list. It is always 48 * at least as large as the list size. As elements are added to an ArrayList, 49 * its capacity grows automatically. The details of the growth policy are not 50 * specified beyond the fact that adding an element has constant amortized 51 * time cost. 52 * 53 * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance 54 * before adding a large number of elements using the <tt>ensureCapacity</tt> 55 * operation. This may reduce the amount of incremental reallocation. 56 * 57 * <p><strong>Note that this implementation is not synchronized.</strong> 58 * If multiple threads access an <tt>ArrayList</tt> instance concurrently, 59 * and at least one of the threads modifies the list structurally, it 60 * <i>must</i> be synchronized externally. (A structural modification is 61 * any operation that adds or deletes one or more elements, or explicitly 62 * resizes the backing array; merely setting the value of an element is not 63 * a structural modification.) This is typically accomplished by 64 * synchronizing on some object that naturally encapsulates the list. 65 * 66 * If no such object exists, the list should be "wrapped" using the 67 * {@link Collections#synchronizedList Collections.synchronizedList} 68 * method. This is best done at creation time, to prevent accidental 69 * unsynchronized access to the list:<pre> 70 * List list = Collections.synchronizedList(new ArrayList(...));</pre> 71 * 72 * <p><a name="fail-fast"/> 73 * The iterators returned by this class's {@link #iterator() iterator} and 74 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>: 75 * if the list is structurally modified at any time after the iterator is 76 * created, in any way except through the iterator's own 77 * {@link ListIterator#remove() remove} or 78 * {@link ListIterator#add(Object) add} methods, the iterator will throw a 79 * {@link ConcurrentModificationException}. Thus, in the face of 80 * concurrent modification, the iterator fails quickly and cleanly, rather 81 * than risking arbitrary, non-deterministic behavior at an undetermined 82 * time in the future. 83 * 84 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 85 * as it is, generally speaking, impossible to make any hard guarantees in the 86 * presence of unsynchronized concurrent modification. Fail-fast iterators 87 * throw {@code ConcurrentModificationException} on a best-effort basis. 88 * Therefore, it would be wrong to write a program that depended on this 89 * exception for its correctness: <i>the fail-fast behavior of iterators 90 * should be used only to detect bugs.</i> 91 * 92 * <p>This class is a member of the 93 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 94 * Java Collections Framework</a>. 95 * 96 * @author Josh Bloch 97 * @author Neal Gafter 98 * @see Collection 99 * @see List 100 * @see LinkedList 101 * @see Vector 102 * @since 1.2 103 */ 104 105public class ArrayList<E> extends AbstractList<E> 106 implements List<E>, RandomAccess, Cloneable, java.io.Serializable 107{ 108 private static final long serialVersionUID = 8683452581122892189L; 109 110 /** 111 * Default initial capacity. 112 */ 113 private static final int DEFAULT_CAPACITY = 10; 114 115 /** 116 * Shared empty array instance used for empty instances. 117 */ 118 private static final Object[] EMPTY_ELEMENTDATA = {}; 119 120 /** 121 * The array buffer into which the elements of the ArrayList are stored. 122 * The capacity of the ArrayList is the length of this array buffer. Any 123 * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to 124 * DEFAULT_CAPACITY when the first element is added. 125 * 126 * Package private to allow access from java.util.Collections. 127 */ 128 transient Object[] elementData; 129 130 /** 131 * The size of the ArrayList (the number of elements it contains). 132 * 133 * @serial 134 */ 135 private int size; 136 137 /** 138 * Constructs an empty list with the specified initial capacity. 139 * 140 * @param initialCapacity the initial capacity of the list 141 * @throws IllegalArgumentException if the specified initial capacity 142 * is negative 143 */ 144 public ArrayList(int initialCapacity) { 145 super(); 146 if (initialCapacity < 0) 147 throw new IllegalArgumentException("Illegal Capacity: "+ 148 initialCapacity); 149 this.elementData = new Object[initialCapacity]; 150 } 151 152 /** 153 * Constructs an empty list with an initial capacity of ten. 154 */ 155 public ArrayList() { 156 super(); 157 this.elementData = EMPTY_ELEMENTDATA; 158 } 159 160 /** 161 * Constructs a list containing the elements of the specified 162 * collection, in the order they are returned by the collection's 163 * iterator. 164 * 165 * @param c the collection whose elements are to be placed into this list 166 * @throws NullPointerException if the specified collection is null 167 */ 168 public ArrayList(Collection<? extends E> c) { 169 elementData = c.toArray(); 170 size = elementData.length; 171 // c.toArray might (incorrectly) not return Object[] (see 6260652) 172 if (elementData.getClass() != Object[].class) 173 elementData = Arrays.copyOf(elementData, size, Object[].class); 174 } 175 176 /** 177 * Trims the capacity of this <tt>ArrayList</tt> instance to be the 178 * list's current size. An application can use this operation to minimize 179 * the storage of an <tt>ArrayList</tt> instance. 180 */ 181 public void trimToSize() { 182 modCount++; 183 if (size < elementData.length) { 184 elementData = Arrays.copyOf(elementData, size); 185 } 186 } 187 188 /** 189 * Increases the capacity of this <tt>ArrayList</tt> instance, if 190 * necessary, to ensure that it can hold at least the number of elements 191 * specified by the minimum capacity argument. 192 * 193 * @param minCapacity the desired minimum capacity 194 */ 195 public void ensureCapacity(int minCapacity) { 196 int minExpand = (elementData != EMPTY_ELEMENTDATA) 197 // any size if real element table 198 ? 0 199 // larger than default for empty table. It's already supposed to be 200 // at default size. 201 : DEFAULT_CAPACITY; 202 203 if (minCapacity > minExpand) { 204 ensureExplicitCapacity(minCapacity); 205 } 206 } 207 208 private void ensureCapacityInternal(int minCapacity) { 209 if (elementData == EMPTY_ELEMENTDATA) { 210 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 211 } 212 213 ensureExplicitCapacity(minCapacity); 214 } 215 216 private void ensureExplicitCapacity(int minCapacity) { 217 modCount++; 218 219 // overflow-conscious code 220 if (minCapacity - elementData.length > 0) 221 grow(minCapacity); 222 } 223 224 /** 225 * The maximum size of array to allocate. 226 * Some VMs reserve some header words in an array. 227 * Attempts to allocate larger arrays may result in 228 * OutOfMemoryError: Requested array size exceeds VM limit 229 */ 230 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 231 232 /** 233 * Increases the capacity to ensure that it can hold at least the 234 * number of elements specified by the minimum capacity argument. 235 * 236 * @param minCapacity the desired minimum capacity 237 */ 238 private void grow(int minCapacity) { 239 // overflow-conscious code 240 int oldCapacity = elementData.length; 241 int newCapacity = oldCapacity + (oldCapacity >> 1); 242 if (newCapacity - minCapacity < 0) 243 newCapacity = minCapacity; 244 if (newCapacity - MAX_ARRAY_SIZE > 0) 245 newCapacity = hugeCapacity(minCapacity); 246 // minCapacity is usually close to size, so this is a win: 247 elementData = Arrays.copyOf(elementData, newCapacity); 248 } 249 250 private static int hugeCapacity(int minCapacity) { 251 if (minCapacity < 0) // overflow 252 throw new OutOfMemoryError(); 253 return (minCapacity > MAX_ARRAY_SIZE) ? 254 Integer.MAX_VALUE : 255 MAX_ARRAY_SIZE; 256 } 257 258 /** 259 * Returns the number of elements in this list. 260 * 261 * @return the number of elements in this list 262 */ 263 public int size() { 264 return size; 265 } 266 267 /** 268 * Returns <tt>true</tt> if this list contains no elements. 269 * 270 * @return <tt>true</tt> if this list contains no elements 271 */ 272 public boolean isEmpty() { 273 return size == 0; 274 } 275 276 /** 277 * Returns <tt>true</tt> if this list contains the specified element. 278 * More formally, returns <tt>true</tt> if and only if this list contains 279 * at least one element <tt>e</tt> such that 280 * <tt>(o==null ? e==null : o.equals(e))</tt>. 281 * 282 * @param o element whose presence in this list is to be tested 283 * @return <tt>true</tt> if this list contains the specified element 284 */ 285 public boolean contains(Object o) { 286 return indexOf(o) >= 0; 287 } 288 289 /** 290 * Returns the index of the first occurrence of the specified element 291 * in this list, or -1 if this list does not contain the element. 292 * More formally, returns the lowest index <tt>i</tt> such that 293 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 294 * or -1 if there is no such index. 295 */ 296 public int indexOf(Object o) { 297 if (o == null) { 298 for (int i = 0; i < size; i++) 299 if (elementData[i]==null) 300 return i; 301 } else { 302 for (int i = 0; i < size; i++) 303 if (o.equals(elementData[i])) 304 return i; 305 } 306 return -1; 307 } 308 309 /** 310 * Returns the index of the last occurrence of the specified element 311 * in this list, or -1 if this list does not contain the element. 312 * More formally, returns the highest index <tt>i</tt> such that 313 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 314 * or -1 if there is no such index. 315 */ 316 public int lastIndexOf(Object o) { 317 if (o == null) { 318 for (int i = size-1; i >= 0; i--) 319 if (elementData[i]==null) 320 return i; 321 } else { 322 for (int i = size-1; i >= 0; i--) 323 if (o.equals(elementData[i])) 324 return i; 325 } 326 return -1; 327 } 328 329 /** 330 * Returns a shallow copy of this <tt>ArrayList</tt> instance. (The 331 * elements themselves are not copied.) 332 * 333 * @return a clone of this <tt>ArrayList</tt> instance 334 */ 335 public Object clone() { 336 try { 337 @SuppressWarnings("unchecked") 338 ArrayList<E> v = (ArrayList<E>) super.clone(); 339 v.elementData = Arrays.copyOf(elementData, size); 340 v.modCount = 0; 341 return v; 342 } catch (CloneNotSupportedException e) { 343 // this shouldn't happen, since we are Cloneable 344 throw new InternalError(); 345 } 346 } 347 348 /** 349 * Returns an array containing all of the elements in this list 350 * in proper sequence (from first to last element). 351 * 352 * <p>The returned array will be "safe" in that no references to it are 353 * maintained by this list. (In other words, this method must allocate 354 * a new array). The caller is thus free to modify the returned array. 355 * 356 * <p>This method acts as bridge between array-based and collection-based 357 * APIs. 358 * 359 * @return an array containing all of the elements in this list in 360 * proper sequence 361 */ 362 public Object[] toArray() { 363 return Arrays.copyOf(elementData, size); 364 } 365 366 /** 367 * Returns an array containing all of the elements in this list in proper 368 * sequence (from first to last element); the runtime type of the returned 369 * array is that of the specified array. If the list fits in the 370 * specified array, it is returned therein. Otherwise, a new array is 371 * allocated with the runtime type of the specified array and the size of 372 * this list. 373 * 374 * <p>If the list fits in the specified array with room to spare 375 * (i.e., the array has more elements than the list), the element in 376 * the array immediately following the end of the collection is set to 377 * <tt>null</tt>. (This is useful in determining the length of the 378 * list <i>only</i> if the caller knows that the list does not contain 379 * any null elements.) 380 * 381 * @param a the array into which the elements of the list are to 382 * be stored, if it is big enough; otherwise, a new array of the 383 * same runtime type is allocated for this purpose. 384 * @return an array containing the elements of the list 385 * @throws ArrayStoreException if the runtime type of the specified array 386 * is not a supertype of the runtime type of every element in 387 * this list 388 * @throws NullPointerException if the specified array is null 389 */ 390 @SuppressWarnings("unchecked") 391 public <T> T[] toArray(T[] a) { 392 if (a.length < size) 393 // Make a new array of a's runtime type, but my contents: 394 return (T[]) Arrays.copyOf(elementData, size, a.getClass()); 395 System.arraycopy(elementData, 0, a, 0, size); 396 if (a.length > size) 397 a[size] = null; 398 return a; 399 } 400 401 /** 402 * Returns the element at the specified position in this list. 403 * 404 * @param index index of the element to return 405 * @return the element at the specified position in this list 406 * @throws IndexOutOfBoundsException {@inheritDoc} 407 */ 408 public E get(int index) { 409 if (index >= size) 410 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 411 412 return (E) elementData[index]; 413 } 414 415 /** 416 * Replaces the element at the specified position in this list with 417 * the specified element. 418 * 419 * @param index index of the element to replace 420 * @param element element to be stored at the specified position 421 * @return the element previously at the specified position 422 * @throws IndexOutOfBoundsException {@inheritDoc} 423 */ 424 public E set(int index, E element) { 425 if (index >= size) 426 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 427 428 E oldValue = (E) elementData[index]; 429 elementData[index] = element; 430 return oldValue; 431 } 432 433 /** 434 * Appends the specified element to the end of this list. 435 * 436 * @param e element to be appended to this list 437 * @return <tt>true</tt> (as specified by {@link Collection#add}) 438 */ 439 public boolean add(E e) { 440 ensureCapacityInternal(size + 1); // Increments modCount!! 441 elementData[size++] = e; 442 return true; 443 } 444 445 /** 446 * Inserts the specified element at the specified position in this 447 * list. Shifts the element currently at that position (if any) and 448 * any subsequent elements to the right (adds one to their indices). 449 * 450 * @param index index at which the specified element is to be inserted 451 * @param element element to be inserted 452 * @throws IndexOutOfBoundsException {@inheritDoc} 453 */ 454 public void add(int index, E element) { 455 if (index > size || index < 0) 456 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 457 458 ensureCapacityInternal(size + 1); // Increments modCount!! 459 System.arraycopy(elementData, index, elementData, index + 1, 460 size - index); 461 elementData[index] = element; 462 size++; 463 } 464 465 /** 466 * Removes the element at the specified position in this list. 467 * Shifts any subsequent elements to the left (subtracts one from their 468 * indices). 469 * 470 * @param index the index of the element to be removed 471 * @return the element that was removed from the list 472 * @throws IndexOutOfBoundsException {@inheritDoc} 473 */ 474 public E remove(int index) { 475 if (index >= size) 476 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 477 478 modCount++; 479 E oldValue = (E) elementData[index]; 480 481 int numMoved = size - index - 1; 482 if (numMoved > 0) 483 System.arraycopy(elementData, index+1, elementData, index, 484 numMoved); 485 elementData[--size] = null; // clear to let GC do its work 486 487 return oldValue; 488 } 489 490 /** 491 * Removes the first occurrence of the specified element from this list, 492 * if it is present. If the list does not contain the element, it is 493 * unchanged. More formally, removes the element with the lowest index 494 * <tt>i</tt> such that 495 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> 496 * (if such an element exists). Returns <tt>true</tt> if this list 497 * contained the specified element (or equivalently, if this list 498 * changed as a result of the call). 499 * 500 * @param o element to be removed from this list, if present 501 * @return <tt>true</tt> if this list contained the specified element 502 */ 503 public boolean remove(Object o) { 504 if (o == null) { 505 for (int index = 0; index < size; index++) 506 if (elementData[index] == null) { 507 fastRemove(index); 508 return true; 509 } 510 } else { 511 for (int index = 0; index < size; index++) 512 if (o.equals(elementData[index])) { 513 fastRemove(index); 514 return true; 515 } 516 } 517 return false; 518 } 519 520 /* 521 * Private remove method that skips bounds checking and does not 522 * return the value removed. 523 */ 524 private void fastRemove(int index) { 525 modCount++; 526 int numMoved = size - index - 1; 527 if (numMoved > 0) 528 System.arraycopy(elementData, index+1, elementData, index, 529 numMoved); 530 elementData[--size] = null; // clear to let GC do its work 531 } 532 533 /** 534 * Removes all of the elements from this list. The list will 535 * be empty after this call returns. 536 */ 537 public void clear() { 538 modCount++; 539 540 // clear to let GC do its work 541 for (int i = 0; i < size; i++) 542 elementData[i] = null; 543 544 size = 0; 545 } 546 547 /** 548 * Appends all of the elements in the specified collection to the end of 549 * this list, in the order that they are returned by the 550 * specified collection's Iterator. The behavior of this operation is 551 * undefined if the specified collection is modified while the operation 552 * is in progress. (This implies that the behavior of this call is 553 * undefined if the specified collection is this list, and this 554 * list is nonempty.) 555 * 556 * @param c collection containing elements to be added to this list 557 * @return <tt>true</tt> if this list changed as a result of the call 558 * @throws NullPointerException if the specified collection is null 559 */ 560 public boolean addAll(Collection<? extends E> c) { 561 Object[] a = c.toArray(); 562 int numNew = a.length; 563 ensureCapacityInternal(size + numNew); // Increments modCount 564 System.arraycopy(a, 0, elementData, size, numNew); 565 size += numNew; 566 return numNew != 0; 567 } 568 569 /** 570 * Inserts all of the elements in the specified collection into this 571 * list, starting at the specified position. Shifts the element 572 * currently at that position (if any) and any subsequent elements to 573 * the right (increases their indices). The new elements will appear 574 * in the list in the order that they are returned by the 575 * specified collection's iterator. 576 * 577 * @param index index at which to insert the first element from the 578 * specified collection 579 * @param c collection containing elements to be added to this list 580 * @return <tt>true</tt> if this list changed as a result of the call 581 * @throws IndexOutOfBoundsException {@inheritDoc} 582 * @throws NullPointerException if the specified collection is null 583 */ 584 public boolean addAll(int index, Collection<? extends E> c) { 585 if (index > size || index < 0) 586 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 587 588 Object[] a = c.toArray(); 589 int numNew = a.length; 590 ensureCapacityInternal(size + numNew); // Increments modCount 591 592 int numMoved = size - index; 593 if (numMoved > 0) 594 System.arraycopy(elementData, index, elementData, index + numNew, 595 numMoved); 596 597 System.arraycopy(a, 0, elementData, index, numNew); 598 size += numNew; 599 return numNew != 0; 600 } 601 602 /** 603 * Removes from this list all of the elements whose index is between 604 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 605 * Shifts any succeeding elements to the left (reduces their index). 606 * This call shortens the list by {@code (toIndex - fromIndex)} elements. 607 * (If {@code toIndex==fromIndex}, this operation has no effect.) 608 * 609 * @throws IndexOutOfBoundsException if {@code fromIndex} or 610 * {@code toIndex} is out of range 611 * ({@code fromIndex < 0 || 612 * fromIndex >= size() || 613 * toIndex > size() || 614 * toIndex < fromIndex}) 615 */ 616 protected void removeRange(int fromIndex, int toIndex) { 617 // Android-changed : Throw an IOOBE if toIndex < fromIndex as documented. 618 // All the other cases (negative indices, or indices greater than the size 619 // will be thrown by System#arrayCopy. 620 if (toIndex < fromIndex) { 621 throw new IndexOutOfBoundsException("toIndex < fromIndex"); 622 } 623 624 modCount++; 625 int numMoved = size - toIndex; 626 System.arraycopy(elementData, toIndex, elementData, fromIndex, 627 numMoved); 628 629 // clear to let GC do its work 630 int newSize = size - (toIndex-fromIndex); 631 for (int i = newSize; i < size; i++) { 632 elementData[i] = null; 633 } 634 size = newSize; 635 } 636 637 /** 638 * Constructs an IndexOutOfBoundsException detail message. 639 * Of the many possible refactorings of the error handling code, 640 * this "outlining" performs best with both server and client VMs. 641 */ 642 private String outOfBoundsMsg(int index) { 643 return "Index: "+index+", Size: "+size; 644 } 645 646 /** 647 * Removes from this list all of its elements that are contained in the 648 * specified collection. 649 * 650 * @param c collection containing elements to be removed from this list 651 * @return {@code true} if this list changed as a result of the call 652 * @throws ClassCastException if the class of an element of this list 653 * is incompatible with the specified collection 654 * (<a href="Collection.html#optional-restrictions">optional</a>) 655 * @throws NullPointerException if this list contains a null element and the 656 * specified collection does not permit null elements 657 * (<a href="Collection.html#optional-restrictions">optional</a>), 658 * or if the specified collection is null 659 * @see Collection#contains(Object) 660 */ 661 public boolean removeAll(Collection<?> c) { 662 return batchRemove(c, false); 663 } 664 665 /** 666 * Retains only the elements in this list that are contained in the 667 * specified collection. In other words, removes from this list all 668 * of its elements that are not contained in the specified collection. 669 * 670 * @param c collection containing elements to be retained in 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 retainAll(Collection<?> c) { 682 return batchRemove(c, true); 683 } 684 685 private boolean batchRemove(Collection<?> c, boolean complement) { 686 final Object[] elementData = this.elementData; 687 int r = 0, w = 0; 688 boolean modified = false; 689 try { 690 for (; r < size; r++) 691 if (c.contains(elementData[r]) == complement) 692 elementData[w++] = elementData[r]; 693 } finally { 694 // Preserve behavioral compatibility with AbstractCollection, 695 // even if c.contains() throws. 696 if (r != size) { 697 System.arraycopy(elementData, r, 698 elementData, w, 699 size - r); 700 w += size - r; 701 } 702 if (w != size) { 703 // clear to let GC do its work 704 for (int i = w; i < size; i++) 705 elementData[i] = null; 706 modCount += size - w; 707 size = w; 708 modified = true; 709 } 710 } 711 return modified; 712 } 713 714 /** 715 * Save the state of the <tt>ArrayList</tt> instance to a stream (that 716 * is, serialize it). 717 * 718 * @serialData The length of the array backing the <tt>ArrayList</tt> 719 * instance is emitted (int), followed by all of its elements 720 * (each an <tt>Object</tt>) in the proper order. 721 */ 722 private void writeObject(java.io.ObjectOutputStream s) 723 throws java.io.IOException{ 724 // Write out element count, and any hidden stuff 725 int expectedModCount = modCount; 726 s.defaultWriteObject(); 727 728 // Write out size as capacity for behavioural compatibility with clone() 729 s.writeInt(size); 730 731 // Write out all elements in the proper order. 732 for (int i=0; i<size; i++) { 733 s.writeObject(elementData[i]); 734 } 735 736 if (modCount != expectedModCount) { 737 throw new ConcurrentModificationException(); 738 } 739 } 740 741 /** 742 * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is, 743 * deserialize it). 744 */ 745 private void readObject(java.io.ObjectInputStream s) 746 throws java.io.IOException, ClassNotFoundException { 747 elementData = EMPTY_ELEMENTDATA; 748 749 // Read in size, and any hidden stuff 750 s.defaultReadObject(); 751 752 // Read in capacity 753 s.readInt(); // ignored 754 755 if (size > 0) { 756 // be like clone(), allocate array based upon size not capacity 757 ensureCapacityInternal(size); 758 759 Object[] a = elementData; 760 // Read in all elements in the proper order. 761 for (int i=0; i<size; i++) { 762 a[i] = s.readObject(); 763 } 764 } 765 } 766 767 /** 768 * Returns a list iterator over the elements in this list (in proper 769 * sequence), starting at the specified position in the list. 770 * The specified index indicates the first element that would be 771 * returned by an initial call to {@link ListIterator#next next}. 772 * An initial call to {@link ListIterator#previous previous} would 773 * return the element with the specified index minus one. 774 * 775 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>. 776 * 777 * @throws IndexOutOfBoundsException {@inheritDoc} 778 */ 779 public ListIterator<E> listIterator(int index) { 780 if (index < 0 || index > size) 781 throw new IndexOutOfBoundsException("Index: "+index); 782 return new ListItr(index); 783 } 784 785 /** 786 * Returns a list iterator over the elements in this list (in proper 787 * sequence). 788 * 789 * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>. 790 * 791 * @see #listIterator(int) 792 */ 793 public ListIterator<E> listIterator() { 794 return new ListItr(0); 795 } 796 797 /** 798 * Returns an iterator over the elements in this list in proper sequence. 799 * 800 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>. 801 * 802 * @return an iterator over the elements in this list in proper sequence 803 */ 804 public Iterator<E> iterator() { 805 return new Itr(); 806 } 807 808 /** 809 * An optimized version of AbstractList.Itr 810 */ 811 private class Itr implements Iterator<E> { 812 // The "limit" of this iterator. This is the size of the list at the time the 813 // iterator was created. Adding & removing elements will invalidate the iteration 814 // anyway (and cause next() to throw) so saving this value will guarantee that the 815 // value of hasNext() remains stable and won't flap between true and false when elements 816 // are added and removed from the list. 817 protected int limit = ArrayList.this.size; 818 819 int cursor; // index of next element to return 820 int lastRet = -1; // index of last element returned; -1 if no such 821 int expectedModCount = modCount; 822 823 public boolean hasNext() { 824 return cursor < limit; 825 } 826 827 @SuppressWarnings("unchecked") 828 public E next() { 829 if (modCount != expectedModCount) 830 throw new ConcurrentModificationException(); 831 int i = cursor; 832 if (i >= limit) 833 throw new NoSuchElementException(); 834 Object[] elementData = ArrayList.this.elementData; 835 if (i >= elementData.length) 836 throw new ConcurrentModificationException(); 837 cursor = i + 1; 838 return (E) elementData[lastRet = i]; 839 } 840 841 public void remove() { 842 if (lastRet < 0) 843 throw new IllegalStateException(); 844 if (modCount != expectedModCount) 845 throw new ConcurrentModificationException(); 846 847 try { 848 ArrayList.this.remove(lastRet); 849 cursor = lastRet; 850 lastRet = -1; 851 expectedModCount = modCount; 852 limit--; 853 } catch (IndexOutOfBoundsException ex) { 854 throw new ConcurrentModificationException(); 855 } 856 } 857 } 858 859 /** 860 * An optimized version of AbstractList.ListItr 861 */ 862 private class ListItr extends Itr implements ListIterator<E> { 863 ListItr(int index) { 864 super(); 865 cursor = index; 866 } 867 868 public boolean hasPrevious() { 869 return cursor != 0; 870 } 871 872 public int nextIndex() { 873 return cursor; 874 } 875 876 public int previousIndex() { 877 return cursor - 1; 878 } 879 880 @SuppressWarnings("unchecked") 881 public E previous() { 882 if (modCount != expectedModCount) 883 throw new ConcurrentModificationException(); 884 int i = cursor - 1; 885 if (i < 0) 886 throw new NoSuchElementException(); 887 Object[] elementData = ArrayList.this.elementData; 888 if (i >= elementData.length) 889 throw new ConcurrentModificationException(); 890 cursor = i; 891 return (E) elementData[lastRet = i]; 892 } 893 894 public void set(E e) { 895 if (lastRet < 0) 896 throw new IllegalStateException(); 897 if (modCount != expectedModCount) 898 throw new ConcurrentModificationException(); 899 900 try { 901 ArrayList.this.set(lastRet, e); 902 } catch (IndexOutOfBoundsException ex) { 903 throw new ConcurrentModificationException(); 904 } 905 } 906 907 public void add(E e) { 908 if (modCount != expectedModCount) 909 throw new ConcurrentModificationException(); 910 911 try { 912 int i = cursor; 913 ArrayList.this.add(i, e); 914 cursor = i + 1; 915 lastRet = -1; 916 expectedModCount = modCount; 917 limit++; 918 } catch (IndexOutOfBoundsException ex) { 919 throw new ConcurrentModificationException(); 920 } 921 } 922 } 923 924 /** 925 * Returns a view of the portion of this list between the specified 926 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If 927 * {@code fromIndex} and {@code toIndex} are equal, the returned list is 928 * empty.) The returned list is backed by this list, so non-structural 929 * changes in the returned list are reflected in this list, and vice-versa. 930 * The returned list supports all of the optional list operations. 931 * 932 * <p>This method eliminates the need for explicit range operations (of 933 * the sort that commonly exist for arrays). Any operation that expects 934 * a list can be used as a range operation by passing a subList view 935 * instead of a whole list. For example, the following idiom 936 * removes a range of elements from a list: 937 * <pre> 938 * list.subList(from, to).clear(); 939 * </pre> 940 * Similar idioms may be constructed for {@link #indexOf(Object)} and 941 * {@link #lastIndexOf(Object)}, and all of the algorithms in the 942 * {@link Collections} class can be applied to a subList. 943 * 944 * <p>The semantics of the list returned by this method become undefined if 945 * the backing list (i.e., this list) is <i>structurally modified</i> in 946 * any way other than via the returned list. (Structural modifications are 947 * those that change the size of this list, or otherwise perturb it in such 948 * a fashion that iterations in progress may yield incorrect results.) 949 * 950 * @throws IndexOutOfBoundsException {@inheritDoc} 951 * @throws IllegalArgumentException {@inheritDoc} 952 */ 953 public List<E> subList(int fromIndex, int toIndex) { 954 subListRangeCheck(fromIndex, toIndex, size); 955 return new SubList(this, 0, fromIndex, toIndex); 956 } 957 958 static void subListRangeCheck(int fromIndex, int toIndex, int size) { 959 if (fromIndex < 0) 960 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 961 if (toIndex > size) 962 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 963 if (fromIndex > toIndex) 964 throw new IllegalArgumentException("fromIndex(" + fromIndex + 965 ") > toIndex(" + toIndex + ")"); 966 } 967 968 private class SubList extends AbstractList<E> implements RandomAccess { 969 private final AbstractList<E> parent; 970 private final int parentOffset; 971 private final int offset; 972 int size; 973 974 SubList(AbstractList<E> parent, 975 int offset, int fromIndex, int toIndex) { 976 this.parent = parent; 977 this.parentOffset = fromIndex; 978 this.offset = offset + fromIndex; 979 this.size = toIndex - fromIndex; 980 this.modCount = ArrayList.this.modCount; 981 } 982 983 public E set(int index, E e) { 984 if (index < 0 || index >= this.size) 985 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 986 if (ArrayList.this.modCount != this.modCount) 987 throw new ConcurrentModificationException(); 988 E oldValue = (E) ArrayList.this.elementData[offset + index]; 989 ArrayList.this.elementData[offset + index] = e; 990 return oldValue; 991 } 992 993 public E get(int index) { 994 if (index < 0 || index >= this.size) 995 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 996 if (ArrayList.this.modCount != this.modCount) 997 throw new ConcurrentModificationException(); 998 return (E) ArrayList.this.elementData[offset + index]; 999 } 1000 1001 public int size() { 1002 if (ArrayList.this.modCount != this.modCount) 1003 throw new ConcurrentModificationException(); 1004 return this.size; 1005 } 1006 1007 public void add(int index, E e) { 1008 if (index < 0 || index > this.size) 1009 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1010 if (ArrayList.this.modCount != this.modCount) 1011 throw new ConcurrentModificationException(); 1012 parent.add(parentOffset + index, e); 1013 this.modCount = parent.modCount; 1014 this.size++; 1015 } 1016 1017 public E remove(int index) { 1018 if (index < 0 || index >= this.size) 1019 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1020 if (ArrayList.this.modCount != this.modCount) 1021 throw new ConcurrentModificationException(); 1022 E result = parent.remove(parentOffset + index); 1023 this.modCount = parent.modCount; 1024 this.size--; 1025 return result; 1026 } 1027 1028 protected void removeRange(int fromIndex, int toIndex) { 1029 if (ArrayList.this.modCount != this.modCount) 1030 throw new ConcurrentModificationException(); 1031 parent.removeRange(parentOffset + fromIndex, 1032 parentOffset + toIndex); 1033 this.modCount = parent.modCount; 1034 this.size -= toIndex - fromIndex; 1035 } 1036 1037 public boolean addAll(Collection<? extends E> c) { 1038 return addAll(this.size, c); 1039 } 1040 1041 public boolean addAll(int index, Collection<? extends E> c) { 1042 if (index < 0 || index > this.size) 1043 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1044 int cSize = c.size(); 1045 if (cSize==0) 1046 return false; 1047 1048 if (ArrayList.this.modCount != this.modCount) 1049 throw new ConcurrentModificationException(); 1050 parent.addAll(parentOffset + index, c); 1051 this.modCount = parent.modCount; 1052 this.size += cSize; 1053 return true; 1054 } 1055 1056 public Iterator<E> iterator() { 1057 return listIterator(); 1058 } 1059 1060 public ListIterator<E> listIterator(final int index) { 1061 if (ArrayList.this.modCount != this.modCount) 1062 throw new ConcurrentModificationException(); 1063 if (index < 0 || index > this.size) 1064 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1065 final int offset = this.offset; 1066 1067 return new ListIterator<E>() { 1068 int cursor = index; 1069 int lastRet = -1; 1070 int expectedModCount = ArrayList.this.modCount; 1071 1072 public boolean hasNext() { 1073 return cursor != SubList.this.size; 1074 } 1075 1076 @SuppressWarnings("unchecked") 1077 public E next() { 1078 if (expectedModCount != ArrayList.this.modCount) 1079 throw new ConcurrentModificationException(); 1080 int i = cursor; 1081 if (i >= SubList.this.size) 1082 throw new NoSuchElementException(); 1083 Object[] elementData = ArrayList.this.elementData; 1084 if (offset + i >= elementData.length) 1085 throw new ConcurrentModificationException(); 1086 cursor = i + 1; 1087 return (E) elementData[offset + (lastRet = i)]; 1088 } 1089 1090 public boolean hasPrevious() { 1091 return cursor != 0; 1092 } 1093 1094 @SuppressWarnings("unchecked") 1095 public E previous() { 1096 if (expectedModCount != ArrayList.this.modCount) 1097 throw new ConcurrentModificationException(); 1098 int i = cursor - 1; 1099 if (i < 0) 1100 throw new NoSuchElementException(); 1101 Object[] elementData = ArrayList.this.elementData; 1102 if (offset + i >= elementData.length) 1103 throw new ConcurrentModificationException(); 1104 cursor = i; 1105 return (E) elementData[offset + (lastRet = i)]; 1106 } 1107 1108 public int nextIndex() { 1109 return cursor; 1110 } 1111 1112 public int previousIndex() { 1113 return cursor - 1; 1114 } 1115 1116 public void remove() { 1117 if (lastRet < 0) 1118 throw new IllegalStateException(); 1119 if (expectedModCount != ArrayList.this.modCount) 1120 throw new ConcurrentModificationException(); 1121 1122 try { 1123 SubList.this.remove(lastRet); 1124 cursor = lastRet; 1125 lastRet = -1; 1126 expectedModCount = ArrayList.this.modCount; 1127 } catch (IndexOutOfBoundsException ex) { 1128 throw new ConcurrentModificationException(); 1129 } 1130 } 1131 1132 public void set(E e) { 1133 if (lastRet < 0) 1134 throw new IllegalStateException(); 1135 if (expectedModCount != ArrayList.this.modCount) 1136 throw new ConcurrentModificationException(); 1137 1138 try { 1139 ArrayList.this.set(offset + lastRet, e); 1140 } catch (IndexOutOfBoundsException ex) { 1141 throw new ConcurrentModificationException(); 1142 } 1143 } 1144 1145 public void add(E e) { 1146 if (expectedModCount != ArrayList.this.modCount) 1147 throw new ConcurrentModificationException(); 1148 1149 try { 1150 int i = cursor; 1151 SubList.this.add(i, e); 1152 cursor = i + 1; 1153 lastRet = -1; 1154 expectedModCount = ArrayList.this.modCount; 1155 } catch (IndexOutOfBoundsException ex) { 1156 throw new ConcurrentModificationException(); 1157 } 1158 } 1159 }; 1160 } 1161 1162 public List<E> subList(int fromIndex, int toIndex) { 1163 subListRangeCheck(fromIndex, toIndex, size); 1164 return new SubList(this, offset, fromIndex, toIndex); 1165 } 1166 1167 private String outOfBoundsMsg(int index) { 1168 return "Index: "+index+", Size: "+this.size; 1169 } 1170 } 1171 1172 @Override 1173 public void forEach(Consumer<? super E> action) { 1174 Objects.requireNonNull(action); 1175 final int expectedModCount = modCount; 1176 @SuppressWarnings("unchecked") 1177 final E[] elementData = (E[]) this.elementData; 1178 final int size = this.size; 1179 for (int i=0; modCount == expectedModCount && i < size; i++) { 1180 action.accept(elementData[i]); 1181 } 1182 // Note 1183 // Iterator will not throw a CME if we add something while iterating over the *last* element 1184 // forEach will throw a CME in this case. 1185 if (modCount != expectedModCount) { 1186 throw new ConcurrentModificationException(); 1187 } 1188 } 1189} 1190