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