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