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