ArrayList.java revision bfb2104abe17ff11c4ec474af12fc7543e881f40
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 int cursor; // index of next element to return 810 int lastRet = -1; // index of last element returned; -1 if no such 811 int expectedModCount = modCount; 812 813 public boolean hasNext() { 814 return cursor != size; 815 } 816 817 @SuppressWarnings("unchecked") 818 public E next() { 819 if (modCount != expectedModCount) 820 throw new ConcurrentModificationException(); 821 int i = cursor; 822 if (i >= size) 823 throw new NoSuchElementException(); 824 Object[] elementData = ArrayList.this.elementData; 825 if (i >= elementData.length) 826 throw new ConcurrentModificationException(); 827 cursor = i + 1; 828 return (E) elementData[lastRet = i]; 829 } 830 831 public void remove() { 832 if (lastRet < 0) 833 throw new IllegalStateException(); 834 if (modCount != expectedModCount) 835 throw new ConcurrentModificationException(); 836 837 try { 838 ArrayList.this.remove(lastRet); 839 cursor = lastRet; 840 lastRet = -1; 841 expectedModCount = modCount; 842 } catch (IndexOutOfBoundsException ex) { 843 throw new ConcurrentModificationException(); 844 } 845 } 846 } 847 848 /** 849 * An optimized version of AbstractList.ListItr 850 */ 851 private class ListItr extends Itr implements ListIterator<E> { 852 ListItr(int index) { 853 super(); 854 cursor = index; 855 } 856 857 public boolean hasPrevious() { 858 return cursor != 0; 859 } 860 861 public int nextIndex() { 862 return cursor; 863 } 864 865 public int previousIndex() { 866 return cursor - 1; 867 } 868 869 @SuppressWarnings("unchecked") 870 public E previous() { 871 if (modCount != expectedModCount) 872 throw new ConcurrentModificationException(); 873 int i = cursor - 1; 874 if (i < 0) 875 throw new NoSuchElementException(); 876 Object[] elementData = ArrayList.this.elementData; 877 if (i >= elementData.length) 878 throw new ConcurrentModificationException(); 879 cursor = i; 880 return (E) elementData[lastRet = i]; 881 } 882 883 public void set(E e) { 884 if (lastRet < 0) 885 throw new IllegalStateException(); 886 if (modCount != expectedModCount) 887 throw new ConcurrentModificationException(); 888 889 try { 890 ArrayList.this.set(lastRet, e); 891 } catch (IndexOutOfBoundsException ex) { 892 throw new ConcurrentModificationException(); 893 } 894 } 895 896 public void add(E e) { 897 if (modCount != expectedModCount) 898 throw new ConcurrentModificationException(); 899 900 try { 901 int i = cursor; 902 ArrayList.this.add(i, e); 903 cursor = i + 1; 904 lastRet = -1; 905 expectedModCount = modCount; 906 } catch (IndexOutOfBoundsException ex) { 907 throw new ConcurrentModificationException(); 908 } 909 } 910 } 911 912 /** 913 * Returns a view of the portion of this list between the specified 914 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. (If 915 * {@code fromIndex} and {@code toIndex} are equal, the returned list is 916 * empty.) The returned list is backed by this list, so non-structural 917 * changes in the returned list are reflected in this list, and vice-versa. 918 * The returned list supports all of the optional list operations. 919 * 920 * <p>This method eliminates the need for explicit range operations (of 921 * the sort that commonly exist for arrays). Any operation that expects 922 * a list can be used as a range operation by passing a subList view 923 * instead of a whole list. For example, the following idiom 924 * removes a range of elements from a list: 925 * <pre> 926 * list.subList(from, to).clear(); 927 * </pre> 928 * Similar idioms may be constructed for {@link #indexOf(Object)} and 929 * {@link #lastIndexOf(Object)}, and all of the algorithms in the 930 * {@link Collections} class can be applied to a subList. 931 * 932 * <p>The semantics of the list returned by this method become undefined if 933 * the backing list (i.e., this list) is <i>structurally modified</i> in 934 * any way other than via the returned list. (Structural modifications are 935 * those that change the size of this list, or otherwise perturb it in such 936 * a fashion that iterations in progress may yield incorrect results.) 937 * 938 * @throws IndexOutOfBoundsException {@inheritDoc} 939 * @throws IllegalArgumentException {@inheritDoc} 940 */ 941 public List<E> subList(int fromIndex, int toIndex) { 942 subListRangeCheck(fromIndex, toIndex, size); 943 return new SubList(this, 0, fromIndex, toIndex); 944 } 945 946 static void subListRangeCheck(int fromIndex, int toIndex, int size) { 947 if (fromIndex < 0) 948 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 949 if (toIndex > size) 950 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 951 if (fromIndex > toIndex) 952 throw new IllegalArgumentException("fromIndex(" + fromIndex + 953 ") > toIndex(" + toIndex + ")"); 954 } 955 956 private class SubList extends AbstractList<E> implements RandomAccess { 957 private final AbstractList<E> parent; 958 private final int parentOffset; 959 private final int offset; 960 int size; 961 962 SubList(AbstractList<E> parent, 963 int offset, int fromIndex, int toIndex) { 964 this.parent = parent; 965 this.parentOffset = fromIndex; 966 this.offset = offset + fromIndex; 967 this.size = toIndex - fromIndex; 968 this.modCount = ArrayList.this.modCount; 969 } 970 971 public E set(int index, E e) { 972 if (index < 0 || index >= this.size) 973 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 974 if (ArrayList.this.modCount != this.modCount) 975 throw new ConcurrentModificationException(); 976 E oldValue = (E) ArrayList.this.elementData[offset + index]; 977 ArrayList.this.elementData[offset + index] = e; 978 return oldValue; 979 } 980 981 public E get(int index) { 982 if (index < 0 || index >= this.size) 983 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 984 if (ArrayList.this.modCount != this.modCount) 985 throw new ConcurrentModificationException(); 986 return (E) ArrayList.this.elementData[offset + index]; 987 } 988 989 public int size() { 990 if (ArrayList.this.modCount != this.modCount) 991 throw new ConcurrentModificationException(); 992 return this.size; 993 } 994 995 public void add(int index, E e) { 996 if (index < 0 || index > this.size) 997 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 998 if (ArrayList.this.modCount != this.modCount) 999 throw new ConcurrentModificationException(); 1000 parent.add(parentOffset + index, e); 1001 this.modCount = parent.modCount; 1002 this.size++; 1003 } 1004 1005 public E remove(int index) { 1006 if (index < 0 || index >= this.size) 1007 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1008 if (ArrayList.this.modCount != this.modCount) 1009 throw new ConcurrentModificationException(); 1010 E result = parent.remove(parentOffset + index); 1011 this.modCount = parent.modCount; 1012 this.size--; 1013 return result; 1014 } 1015 1016 protected void removeRange(int fromIndex, int toIndex) { 1017 if (ArrayList.this.modCount != this.modCount) 1018 throw new ConcurrentModificationException(); 1019 parent.removeRange(parentOffset + fromIndex, 1020 parentOffset + toIndex); 1021 this.modCount = parent.modCount; 1022 this.size -= toIndex - fromIndex; 1023 } 1024 1025 public boolean addAll(Collection<? extends E> c) { 1026 return addAll(this.size, c); 1027 } 1028 1029 public boolean addAll(int index, Collection<? extends E> c) { 1030 if (index < 0 || index > this.size) 1031 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1032 int cSize = c.size(); 1033 if (cSize==0) 1034 return false; 1035 1036 if (ArrayList.this.modCount != this.modCount) 1037 throw new ConcurrentModificationException(); 1038 parent.addAll(parentOffset + index, c); 1039 this.modCount = parent.modCount; 1040 this.size += cSize; 1041 return true; 1042 } 1043 1044 public Iterator<E> iterator() { 1045 return listIterator(); 1046 } 1047 1048 public ListIterator<E> listIterator(final int index) { 1049 if (ArrayList.this.modCount != this.modCount) 1050 throw new ConcurrentModificationException(); 1051 if (index < 0 || index > this.size) 1052 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 1053 final int offset = this.offset; 1054 1055 return new ListIterator<E>() { 1056 int cursor = index; 1057 int lastRet = -1; 1058 int expectedModCount = ArrayList.this.modCount; 1059 1060 public boolean hasNext() { 1061 return cursor != SubList.this.size; 1062 } 1063 1064 @SuppressWarnings("unchecked") 1065 public E next() { 1066 if (expectedModCount != ArrayList.this.modCount) 1067 throw new ConcurrentModificationException(); 1068 int i = cursor; 1069 if (i >= SubList.this.size) 1070 throw new NoSuchElementException(); 1071 Object[] elementData = ArrayList.this.elementData; 1072 if (offset + i >= elementData.length) 1073 throw new ConcurrentModificationException(); 1074 cursor = i + 1; 1075 return (E) elementData[offset + (lastRet = i)]; 1076 } 1077 1078 public boolean hasPrevious() { 1079 return cursor != 0; 1080 } 1081 1082 @SuppressWarnings("unchecked") 1083 public E previous() { 1084 if (expectedModCount != ArrayList.this.modCount) 1085 throw new ConcurrentModificationException(); 1086 int i = cursor - 1; 1087 if (i < 0) 1088 throw new NoSuchElementException(); 1089 Object[] elementData = ArrayList.this.elementData; 1090 if (offset + i >= elementData.length) 1091 throw new ConcurrentModificationException(); 1092 cursor = i; 1093 return (E) elementData[offset + (lastRet = i)]; 1094 } 1095 1096 public int nextIndex() { 1097 return cursor; 1098 } 1099 1100 public int previousIndex() { 1101 return cursor - 1; 1102 } 1103 1104 public void remove() { 1105 if (lastRet < 0) 1106 throw new IllegalStateException(); 1107 if (expectedModCount != ArrayList.this.modCount) 1108 throw new ConcurrentModificationException(); 1109 1110 try { 1111 SubList.this.remove(lastRet); 1112 cursor = lastRet; 1113 lastRet = -1; 1114 expectedModCount = ArrayList.this.modCount; 1115 } catch (IndexOutOfBoundsException ex) { 1116 throw new ConcurrentModificationException(); 1117 } 1118 } 1119 1120 public void set(E e) { 1121 if (lastRet < 0) 1122 throw new IllegalStateException(); 1123 if (expectedModCount != ArrayList.this.modCount) 1124 throw new ConcurrentModificationException(); 1125 1126 try { 1127 ArrayList.this.set(offset + lastRet, e); 1128 } catch (IndexOutOfBoundsException ex) { 1129 throw new ConcurrentModificationException(); 1130 } 1131 } 1132 1133 public void add(E e) { 1134 if (expectedModCount != ArrayList.this.modCount) 1135 throw new ConcurrentModificationException(); 1136 1137 try { 1138 int i = cursor; 1139 SubList.this.add(i, e); 1140 cursor = i + 1; 1141 lastRet = -1; 1142 expectedModCount = ArrayList.this.modCount; 1143 } catch (IndexOutOfBoundsException ex) { 1144 throw new ConcurrentModificationException(); 1145 } 1146 } 1147 }; 1148 } 1149 1150 public List<E> subList(int fromIndex, int toIndex) { 1151 subListRangeCheck(fromIndex, toIndex, size); 1152 return new SubList(this, offset, fromIndex, toIndex); 1153 } 1154 1155 private String outOfBoundsMsg(int index) { 1156 return "Index: "+index+", Size: "+this.size; 1157 } 1158 } 1159} 1160