rev 6816 : 80111200: (coll) Optimize empty HashMap and ArrayList
Reviewed-by: mduigou
Contributed-by: Sergey Linetskiy <sergey.linetskiy@oracle.com>, John Rose <john.r.rose@oracle.com>, Mike Duigou <mike.duigou@oracle.com>

   1 /*
   2  * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 /**
  29  * Resizable-array implementation of the <tt>List</tt> interface.  Implements
  30  * all optional list operations, and permits all elements, including
  31  * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
  32  * this class provides methods to manipulate the size of the array that is
  33  * used internally to store the list.  (This class is roughly equivalent to
  34  * <tt>Vector</tt>, except that it is unsynchronized.)
  35  *
  36  * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
  37  * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
  38  * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
  39  * that is, adding n elements requires O(n) time.  All of the other operations
  40  * run in linear time (roughly speaking).  The constant factor is low compared
  41  * to that for the <tt>LinkedList</tt> implementation.
  42  *
  43  * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
  44  * the size of the array used to store the elements in the list.  It is always
  45  * at least as large as the list size.  As elements are added to an ArrayList,
  46  * its capacity grows automatically.  The details of the growth policy are not
  47  * specified beyond the fact that adding an element has constant amortized
  48  * time cost.
  49  *
  50  * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
  51  * before adding a large number of elements using the <tt>ensureCapacity</tt>
  52  * operation.  This may reduce the amount of incremental reallocation.
  53  *
  54  * <p><strong>Note that this implementation is not synchronized.</strong>
  55  * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
  56  * and at least one of the threads modifies the list structurally, it
  57  * <i>must</i> be synchronized externally.  (A structural modification is
  58  * any operation that adds or deletes one or more elements, or explicitly
  59  * resizes the backing array; merely setting the value of an element is not
  60  * a structural modification.)  This is typically accomplished by
  61  * synchronizing on some object that naturally encapsulates the list.
  62  *
  63  * If no such object exists, the list should be "wrapped" using the
  64  * {@link Collections#synchronizedList Collections.synchronizedList}
  65  * method.  This is best done at creation time, to prevent accidental
  66  * unsynchronized access to the list:<pre>
  67  *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
  68  *
  69  * <p><a name="fail-fast"/>
  70  * The iterators returned by this class's {@link #iterator() iterator} and
  71  * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:
  72  * if the list is structurally modified at any time after the iterator is
  73  * created, in any way except through the iterator's own
  74  * {@link ListIterator#remove() remove} or
  75  * {@link ListIterator#add(Object) add} methods, the iterator will throw a
  76  * {@link ConcurrentModificationException}.  Thus, in the face of
  77  * concurrent modification, the iterator fails quickly and cleanly, rather
  78  * than risking arbitrary, non-deterministic behavior at an undetermined
  79  * time in the future.
  80  *
  81  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  82  * as it is, generally speaking, impossible to make any hard guarantees in the
  83  * presence of unsynchronized concurrent modification.  Fail-fast iterators
  84  * throw {@code ConcurrentModificationException} on a best-effort basis.
  85  * Therefore, it would be wrong to write a program that depended on this
  86  * exception for its correctness:  <i>the fail-fast behavior of iterators
  87  * should be used only to detect bugs.</i>
  88  *
  89  * <p>This class is a member of the
  90  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  91  * Java Collections Framework</a>.
  92  *
  93  * @author  Josh Bloch
  94  * @author  Neal Gafter
  95  * @see     Collection
  96  * @see     List
  97  * @see     LinkedList
  98  * @see     Vector
  99  * @since   1.2
 100  */
 101 
 102 public class ArrayList<E> extends AbstractList<E>
 103         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 104 {
 105     private static final long serialVersionUID = 8683452581122892189L;
 106 
 107     /**










 108      * The array buffer into which the elements of the ArrayList are stored.
 109      * The capacity of the ArrayList is the length of this array buffer.


 110      */
 111     private transient Object[] elementData;
 112 
 113     /**
 114      * The size of the ArrayList (the number of elements it contains).
 115      *
 116      * @serial
 117      */
 118     private int size;
 119 
 120     /**
 121      * Constructs an empty list with the specified initial capacity.
 122      *
 123      * @param  initialCapacity  the initial capacity of the list
 124      * @throws IllegalArgumentException if the specified initial capacity
 125      *         is negative
 126      */
 127     public ArrayList(int initialCapacity) {
 128         super();
 129         if (initialCapacity < 0)
 130             throw new IllegalArgumentException("Illegal Capacity: "+
 131                                                initialCapacity);
 132         this.elementData = new Object[initialCapacity];
 133     }
 134 
 135     /**
 136      * Constructs an empty list with an initial capacity of ten.
 137      */
 138     public ArrayList() {
 139         this(10);

 140     }
 141 
 142     /**
 143      * Constructs a list containing the elements of the specified
 144      * collection, in the order they are returned by the collection's
 145      * iterator.
 146      *
 147      * @param c the collection whose elements are to be placed into this list
 148      * @throws NullPointerException if the specified collection is null
 149      */
 150     public ArrayList(Collection<? extends E> c) {
 151         elementData = c.toArray();
 152         size = elementData.length;
 153         // c.toArray might (incorrectly) not return Object[] (see 6260652)
 154         if (elementData.getClass() != Object[].class)
 155             elementData = Arrays.copyOf(elementData, size, Object[].class);
 156     }
 157 
 158     /**
 159      * Trims the capacity of this <tt>ArrayList</tt> instance to be the
 160      * list's current size.  An application can use this operation to minimize
 161      * the storage of an <tt>ArrayList</tt> instance.
 162      */
 163     public void trimToSize() {
 164         modCount++;
 165         int oldCapacity = elementData.length;
 166         if (size < oldCapacity) {
 167             elementData = Arrays.copyOf(elementData, size);
 168         }
 169     }
 170 
 171     /**
 172      * Increases the capacity of this <tt>ArrayList</tt> instance, if
 173      * necessary, to ensure that it can hold at least the number of elements
 174      * specified by the minimum capacity argument.
 175      *
 176      * @param   minCapacity   the desired minimum capacity
 177      */
 178     public void ensureCapacity(int minCapacity) {
 179         if (minCapacity > 0)
 180             ensureCapacityInternal(minCapacity);



 181     }
 182 
 183     private void ensureCapacityInternal(int minCapacity) {








 184         modCount++;

 185         // overflow-conscious code
 186         if (minCapacity - elementData.length > 0)
 187             grow(minCapacity);
 188     }
 189 
 190     /**
 191      * The maximum size of array to allocate.
 192      * Some VMs reserve some header words in an array.
 193      * Attempts to allocate larger arrays may result in
 194      * OutOfMemoryError: Requested array size exceeds VM limit
 195      */
 196     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 197 
 198     /**
 199      * Increases the capacity to ensure that it can hold at least the
 200      * number of elements specified by the minimum capacity argument.
 201      *
 202      * @param minCapacity the desired minimum capacity
 203      */
 204     private void grow(int minCapacity) {
 205         // overflow-conscious code
 206         int oldCapacity = elementData.length;
 207         int newCapacity = oldCapacity + (oldCapacity >> 1);
 208         if (newCapacity - minCapacity < 0)
 209             newCapacity = minCapacity;
 210         if (newCapacity - MAX_ARRAY_SIZE > 0)
 211             newCapacity = hugeCapacity(minCapacity);
 212         // minCapacity is usually close to size, so this is a win:
 213         elementData = Arrays.copyOf(elementData, newCapacity);
 214     }
 215 
 216     private static int hugeCapacity(int minCapacity) {
 217         if (minCapacity < 0) // overflow
 218             throw new OutOfMemoryError();
 219         return (minCapacity > MAX_ARRAY_SIZE) ?
 220             Integer.MAX_VALUE :
 221             MAX_ARRAY_SIZE;
 222     }
 223 
 224     /**
 225      * Returns the number of elements in this list.
 226      *
 227      * @return the number of elements in this list
 228      */
 229     public int size() {
 230         return size;
 231     }
 232 
 233     /**
 234      * Returns <tt>true</tt> if this list contains no elements.
 235      *
 236      * @return <tt>true</tt> if this list contains no elements
 237      */
 238     public boolean isEmpty() {
 239         return size == 0;
 240     }
 241 
 242     /**
 243      * Returns <tt>true</tt> if this list contains the specified element.
 244      * More formally, returns <tt>true</tt> if and only if this list contains
 245      * at least one element <tt>e</tt> such that
 246      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 247      *
 248      * @param o element whose presence in this list is to be tested
 249      * @return <tt>true</tt> if this list contains the specified element
 250      */
 251     public boolean contains(Object o) {
 252         return indexOf(o) >= 0;
 253     }
 254 
 255     /**
 256      * Returns the index of the first occurrence of the specified element
 257      * in this list, or -1 if this list does not contain the element.
 258      * More formally, returns the lowest index <tt>i</tt> such that
 259      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 260      * or -1 if there is no such index.
 261      */
 262     public int indexOf(Object o) {
 263         if (o == null) {
 264             for (int i = 0; i < size; i++)
 265                 if (elementData[i]==null)
 266                     return i;
 267         } else {
 268             for (int i = 0; i < size; i++)
 269                 if (o.equals(elementData[i]))
 270                     return i;
 271         }
 272         return -1;
 273     }
 274 
 275     /**
 276      * Returns the index of the last occurrence of the specified element
 277      * in this list, or -1 if this list does not contain the element.
 278      * More formally, returns the highest index <tt>i</tt> such that
 279      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 280      * or -1 if there is no such index.
 281      */
 282     public int lastIndexOf(Object o) {
 283         if (o == null) {
 284             for (int i = size-1; i >= 0; i--)
 285                 if (elementData[i]==null)
 286                     return i;
 287         } else {
 288             for (int i = size-1; i >= 0; i--)
 289                 if (o.equals(elementData[i]))
 290                     return i;
 291         }
 292         return -1;
 293     }
 294 
 295     /**
 296      * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
 297      * elements themselves are not copied.)
 298      *
 299      * @return a clone of this <tt>ArrayList</tt> instance
 300      */
 301     public Object clone() {
 302         try {
 303             ArrayList<?> v = (ArrayList<?>) super.clone();
 304             v.elementData = Arrays.copyOf(elementData, size);
 305             v.modCount = 0;
 306             return v;
 307         } catch (CloneNotSupportedException e) {
 308             // this shouldn't happen, since we are Cloneable
 309             throw new InternalError(e);
 310         }
 311     }
 312 
 313     /**
 314      * Returns an array containing all of the elements in this list
 315      * in proper sequence (from first to last element).
 316      *
 317      * <p>The returned array will be "safe" in that no references to it are
 318      * maintained by this list.  (In other words, this method must allocate
 319      * a new array).  The caller is thus free to modify the returned array.
 320      *
 321      * <p>This method acts as bridge between array-based and collection-based
 322      * APIs.
 323      *
 324      * @return an array containing all of the elements in this list in
 325      *         proper sequence
 326      */
 327     public Object[] toArray() {
 328         return Arrays.copyOf(elementData, size);
 329     }
 330 
 331     /**
 332      * Returns an array containing all of the elements in this list in proper
 333      * sequence (from first to last element); the runtime type of the returned
 334      * array is that of the specified array.  If the list fits in the
 335      * specified array, it is returned therein.  Otherwise, a new array is
 336      * allocated with the runtime type of the specified array and the size of
 337      * this list.
 338      *
 339      * <p>If the list fits in the specified array with room to spare
 340      * (i.e., the array has more elements than the list), the element in
 341      * the array immediately following the end of the collection is set to
 342      * <tt>null</tt>.  (This is useful in determining the length of the
 343      * list <i>only</i> if the caller knows that the list does not contain
 344      * any null elements.)
 345      *
 346      * @param a the array into which the elements of the list are to
 347      *          be stored, if it is big enough; otherwise, a new array of the
 348      *          same runtime type is allocated for this purpose.
 349      * @return an array containing the elements of the list
 350      * @throws ArrayStoreException if the runtime type of the specified array
 351      *         is not a supertype of the runtime type of every element in
 352      *         this list
 353      * @throws NullPointerException if the specified array is null
 354      */
 355     @SuppressWarnings("unchecked")
 356     public <T> T[] toArray(T[] a) {
 357         if (a.length < size)
 358             // Make a new array of a's runtime type, but my contents:
 359             return (T[]) Arrays.copyOf(elementData, size, a.getClass());
 360         System.arraycopy(elementData, 0, a, 0, size);
 361         if (a.length > size)
 362             a[size] = null;
 363         return a;
 364     }
 365 
 366     // Positional Access Operations
 367 
 368     @SuppressWarnings("unchecked")
 369     E elementData(int index) {
 370         return (E) elementData[index];
 371     }
 372 
 373     /**
 374      * Returns the element at the specified position in this list.
 375      *
 376      * @param  index index of the element to return
 377      * @return the element at the specified position in this list
 378      * @throws IndexOutOfBoundsException {@inheritDoc}
 379      */
 380     public E get(int index) {
 381         rangeCheck(index);
 382 
 383         return elementData(index);
 384     }
 385 
 386     /**
 387      * Replaces the element at the specified position in this list with
 388      * the specified element.
 389      *
 390      * @param index index of the element to replace
 391      * @param element element to be stored at the specified position
 392      * @return the element previously at the specified position
 393      * @throws IndexOutOfBoundsException {@inheritDoc}
 394      */
 395     public E set(int index, E element) {
 396         rangeCheck(index);
 397 
 398         E oldValue = elementData(index);
 399         elementData[index] = element;
 400         return oldValue;
 401     }
 402 
 403     /**
 404      * Appends the specified element to the end of this list.
 405      *
 406      * @param e element to be appended to this list
 407      * @return <tt>true</tt> (as specified by {@link Collection#add})
 408      */
 409     public boolean add(E e) {
 410         ensureCapacityInternal(size + 1);  // Increments modCount!!
 411         elementData[size++] = e;
 412         return true;
 413     }
 414 
 415     /**
 416      * Inserts the specified element at the specified position in this
 417      * list. Shifts the element currently at that position (if any) and
 418      * any subsequent elements to the right (adds one to their indices).
 419      *
 420      * @param index index at which the specified element is to be inserted
 421      * @param element element to be inserted
 422      * @throws IndexOutOfBoundsException {@inheritDoc}
 423      */
 424     public void add(int index, E element) {
 425         rangeCheckForAdd(index);
 426 
 427         ensureCapacityInternal(size + 1);  // Increments modCount!!
 428         System.arraycopy(elementData, index, elementData, index + 1,
 429                          size - index);
 430         elementData[index] = element;
 431         size++;
 432     }
 433 
 434     /**
 435      * Removes the element at the specified position in this list.
 436      * Shifts any subsequent elements to the left (subtracts one from their
 437      * indices).
 438      *
 439      * @param index the index of the element to be removed
 440      * @return the element that was removed from the list
 441      * @throws IndexOutOfBoundsException {@inheritDoc}
 442      */
 443     public E remove(int index) {
 444         rangeCheck(index);
 445 
 446         modCount++;
 447         E oldValue = elementData(index);
 448 
 449         int numMoved = size - index - 1;
 450         if (numMoved > 0)
 451             System.arraycopy(elementData, index+1, elementData, index,
 452                              numMoved);
 453         elementData[--size] = null; // Let gc do its work
 454 
 455         return oldValue;
 456     }
 457 
 458     /**
 459      * Removes the first occurrence of the specified element from this list,
 460      * if it is present.  If the list does not contain the element, it is
 461      * unchanged.  More formally, removes the element with the lowest index
 462      * <tt>i</tt> such that
 463      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 464      * (if such an element exists).  Returns <tt>true</tt> if this list
 465      * contained the specified element (or equivalently, if this list
 466      * changed as a result of the call).
 467      *
 468      * @param o element to be removed from this list, if present
 469      * @return <tt>true</tt> if this list contained the specified element
 470      */
 471     public boolean remove(Object o) {
 472         if (o == null) {
 473             for (int index = 0; index < size; index++)
 474                 if (elementData[index] == null) {
 475                     fastRemove(index);
 476                     return true;
 477                 }
 478         } else {
 479             for (int index = 0; index < size; index++)
 480                 if (o.equals(elementData[index])) {
 481                     fastRemove(index);
 482                     return true;
 483                 }
 484         }
 485         return false;
 486     }
 487 
 488     /*
 489      * Private remove method that skips bounds checking and does not
 490      * return the value removed.
 491      */
 492     private void fastRemove(int index) {
 493         modCount++;
 494         int numMoved = size - index - 1;
 495         if (numMoved > 0)
 496             System.arraycopy(elementData, index+1, elementData, index,
 497                              numMoved);
 498         elementData[--size] = null; // Let gc do its work
 499     }
 500 
 501     /**
 502      * Removes all of the elements from this list.  The list will
 503      * be empty after this call returns.
 504      */
 505     public void clear() {
 506         modCount++;
 507 
 508         // Let gc do its work
 509         for (int i = 0; i < size; i++)
 510             elementData[i] = null;
 511 
 512         size = 0;
 513     }
 514 
 515     /**
 516      * Appends all of the elements in the specified collection to the end of
 517      * this list, in the order that they are returned by the
 518      * specified collection's Iterator.  The behavior of this operation is
 519      * undefined if the specified collection is modified while the operation
 520      * is in progress.  (This implies that the behavior of this call is
 521      * undefined if the specified collection is this list, and this
 522      * list is nonempty.)
 523      *
 524      * @param c collection containing elements to be added to this list
 525      * @return <tt>true</tt> if this list changed as a result of the call
 526      * @throws NullPointerException if the specified collection is null
 527      */
 528     public boolean addAll(Collection<? extends E> c) {
 529         Object[] a = c.toArray();
 530         int numNew = a.length;
 531         ensureCapacityInternal(size + numNew);  // Increments modCount
 532         System.arraycopy(a, 0, elementData, size, numNew);
 533         size += numNew;
 534         return numNew != 0;
 535     }
 536 
 537     /**
 538      * Inserts all of the elements in the specified collection into this
 539      * list, starting at the specified position.  Shifts the element
 540      * currently at that position (if any) and any subsequent elements to
 541      * the right (increases their indices).  The new elements will appear
 542      * in the list in the order that they are returned by the
 543      * specified collection's iterator.
 544      *
 545      * @param index index at which to insert the first element from the
 546      *              specified collection
 547      * @param c collection containing elements to be added to this list
 548      * @return <tt>true</tt> if this list changed as a result of the call
 549      * @throws IndexOutOfBoundsException {@inheritDoc}
 550      * @throws NullPointerException if the specified collection is null
 551      */
 552     public boolean addAll(int index, Collection<? extends E> c) {
 553         rangeCheckForAdd(index);
 554 
 555         Object[] a = c.toArray();
 556         int numNew = a.length;
 557         ensureCapacityInternal(size + numNew);  // Increments modCount
 558 
 559         int numMoved = size - index;
 560         if (numMoved > 0)
 561             System.arraycopy(elementData, index, elementData, index + numNew,
 562                              numMoved);
 563 
 564         System.arraycopy(a, 0, elementData, index, numNew);
 565         size += numNew;
 566         return numNew != 0;
 567     }
 568 
 569     /**
 570      * Removes from this list all of the elements whose index is between
 571      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 572      * Shifts any succeeding elements to the left (reduces their index).
 573      * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 574      * (If {@code toIndex==fromIndex}, this operation has no effect.)
 575      *
 576      * @throws IndexOutOfBoundsException if {@code fromIndex} or
 577      *         {@code toIndex} is out of range
 578      *         ({@code fromIndex < 0 ||
 579      *          fromIndex >= size() ||
 580      *          toIndex > size() ||
 581      *          toIndex < fromIndex})
 582      */
 583     protected void removeRange(int fromIndex, int toIndex) {
 584         modCount++;
 585         int numMoved = size - toIndex;
 586         System.arraycopy(elementData, toIndex, elementData, fromIndex,
 587                          numMoved);
 588 
 589         // Let gc do its work
 590         int newSize = size - (toIndex-fromIndex);
 591         while (size != newSize)
 592             elementData[--size] = null;


 593     }
 594 
 595     /**
 596      * Checks if the given index is in range.  If not, throws an appropriate
 597      * runtime exception.  This method does *not* check if the index is
 598      * negative: It is always used immediately prior to an array access,
 599      * which throws an ArrayIndexOutOfBoundsException if index is negative.
 600      */
 601     private void rangeCheck(int index) {
 602         if (index >= size)
 603             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 604     }
 605 
 606     /**
 607      * A version of rangeCheck used by add and addAll.
 608      */
 609     private void rangeCheckForAdd(int index) {
 610         if (index > size || index < 0)
 611             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 612     }
 613 
 614     /**
 615      * Constructs an IndexOutOfBoundsException detail message.
 616      * Of the many possible refactorings of the error handling code,
 617      * this "outlining" performs best with both server and client VMs.
 618      */
 619     private String outOfBoundsMsg(int index) {
 620         return "Index: "+index+", Size: "+size;
 621     }
 622 
 623     /**
 624      * Removes from this list all of its elements that are contained in the
 625      * specified collection.
 626      *
 627      * @param c collection containing elements to be removed from this list
 628      * @return {@code true} if this list changed as a result of the call
 629      * @throws ClassCastException if the class of an element of this list
 630      *         is incompatible with the specified collection
 631      * (<a href="Collection.html#optional-restrictions">optional</a>)
 632      * @throws NullPointerException if this list contains a null element and the
 633      *         specified collection does not permit null elements
 634      * (<a href="Collection.html#optional-restrictions">optional</a>),
 635      *         or if the specified collection is null
 636      * @see Collection#contains(Object)
 637      */
 638     public boolean removeAll(Collection<?> c) {
 639         return batchRemove(c, false);
 640     }
 641 
 642     /**
 643      * Retains only the elements in this list that are contained in the
 644      * specified collection.  In other words, removes from this list all
 645      * of its elements that are not contained in the specified collection.
 646      *
 647      * @param c collection containing elements to be retained in this list
 648      * @return {@code true} if this list changed as a result of the call
 649      * @throws ClassCastException if the class of an element of this list
 650      *         is incompatible with the specified collection
 651      * (<a href="Collection.html#optional-restrictions">optional</a>)
 652      * @throws NullPointerException if this list contains a null element and the
 653      *         specified collection does not permit null elements
 654      * (<a href="Collection.html#optional-restrictions">optional</a>),
 655      *         or if the specified collection is null
 656      * @see Collection#contains(Object)
 657      */
 658     public boolean retainAll(Collection<?> c) {
 659         return batchRemove(c, true);
 660     }
 661 
 662     private boolean batchRemove(Collection<?> c, boolean complement) {
 663         final Object[] elementData = this.elementData;
 664         int r = 0, w = 0;
 665         boolean modified = false;
 666         try {
 667             for (; r < size; r++)
 668                 if (c.contains(elementData[r]) == complement)
 669                     elementData[w++] = elementData[r];
 670         } finally {
 671             // Preserve behavioral compatibility with AbstractCollection,
 672             // even if c.contains() throws.
 673             if (r != size) {
 674                 System.arraycopy(elementData, r,
 675                                  elementData, w,
 676                                  size - r);
 677                 w += size - r;
 678             }
 679             if (w != size) {

 680                 for (int i = w; i < size; i++)
 681                     elementData[i] = null;
 682                 modCount += size - w;
 683                 size = w;
 684                 modified = true;
 685             }
 686         }
 687         return modified;
 688     }
 689 
 690     /**
 691      * Save the state of the <tt>ArrayList</tt> instance to a stream (that
 692      * is, serialize it).
 693      *
 694      * @serialData The length of the array backing the <tt>ArrayList</tt>
 695      *             instance is emitted (int), followed by all of its elements
 696      *             (each an <tt>Object</tt>) in the proper order.
 697      */
 698     private void writeObject(java.io.ObjectOutputStream s)
 699         throws java.io.IOException{
 700         // Write out element count, and any hidden stuff
 701         int expectedModCount = modCount;
 702         s.defaultWriteObject();
 703 
 704         // Write out array length
 705         s.writeInt(elementData.length);
 706 
 707         // Write out all elements in the proper order.
 708         for (int i=0; i<size; i++)
 709             s.writeObject(elementData[i]);

 710 
 711         if (modCount != expectedModCount) {
 712             throw new ConcurrentModificationException();
 713         }
 714 
 715     }
 716 
 717     /**
 718      * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
 719      * deserialize it).
 720      */
 721     private void readObject(java.io.ObjectInputStream s)
 722         throws java.io.IOException, ClassNotFoundException {


 723         // Read in size, and any hidden stuff
 724         s.defaultReadObject();
 725 
 726         // Read in array length and allocate array
 727         int arrayLength = s.readInt();
 728         Object[] a = elementData = new Object[arrayLength];



 729 

 730         // Read in all elements in the proper order.
 731         for (int i=0; i<size; i++)
 732             a[i] = s.readObject();


 733     }
 734 
 735     /**
 736      * Returns a list iterator over the elements in this list (in proper
 737      * sequence), starting at the specified position in the list.
 738      * The specified index indicates the first element that would be
 739      * returned by an initial call to {@link ListIterator#next next}.
 740      * An initial call to {@link ListIterator#previous previous} would
 741      * return the element with the specified index minus one.
 742      *
 743      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 744      *
 745      * @throws IndexOutOfBoundsException {@inheritDoc}
 746      */
 747     public ListIterator<E> listIterator(int index) {
 748         if (index < 0 || index > size)
 749             throw new IndexOutOfBoundsException("Index: "+index);
 750         return new ListItr(index);
 751     }
 752 
 753     /**
 754      * Returns a list iterator over the elements in this list (in proper
 755      * sequence).
 756      *
 757      * <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 758      *
 759      * @see #listIterator(int)
 760      */
 761     public ListIterator<E> listIterator() {
 762         return new ListItr(0);
 763     }
 764 
 765     /**
 766      * Returns an iterator over the elements in this list in proper sequence.
 767      *
 768      * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
 769      *
 770      * @return an iterator over the elements in this list in proper sequence
 771      */
 772     public Iterator<E> iterator() {
 773         return new Itr();
 774     }
 775 
 776     /**
 777      * An optimized version of AbstractList.Itr
 778      */
 779     private class Itr implements Iterator<E> {
 780         int cursor;       // index of next element to return
 781         int lastRet = -1; // index of last element returned; -1 if no such
 782         int expectedModCount = modCount;
 783 
 784         public boolean hasNext() {
 785             return cursor != size;
 786         }
 787 
 788         @SuppressWarnings("unchecked")
 789         public E next() {
 790             checkForComodification();
 791             int i = cursor;
 792             if (i >= size)
 793                 throw new NoSuchElementException();
 794             Object[] elementData = ArrayList.this.elementData;
 795             if (i >= elementData.length)
 796                 throw new ConcurrentModificationException();
 797             cursor = i + 1;
 798             return (E) elementData[lastRet = i];
 799         }
 800 
 801         public void remove() {
 802             if (lastRet < 0)
 803                 throw new IllegalStateException();
 804             checkForComodification();
 805 
 806             try {
 807                 ArrayList.this.remove(lastRet);
 808                 cursor = lastRet;
 809                 lastRet = -1;
 810                 expectedModCount = modCount;
 811             } catch (IndexOutOfBoundsException ex) {
 812                 throw new ConcurrentModificationException();
 813             }
 814         }
 815 
 816         final void checkForComodification() {
 817             if (modCount != expectedModCount)
 818                 throw new ConcurrentModificationException();
 819         }
 820     }
 821 
 822     /**
 823      * An optimized version of AbstractList.ListItr
 824      */
 825     private class ListItr extends Itr implements ListIterator<E> {
 826         ListItr(int index) {
 827             super();
 828             cursor = index;
 829         }
 830 
 831         public boolean hasPrevious() {
 832             return cursor != 0;
 833         }
 834 
 835         public int nextIndex() {
 836             return cursor;
 837         }
 838 
 839         public int previousIndex() {
 840             return cursor - 1;
 841         }
 842 
 843         @SuppressWarnings("unchecked")
 844         public E previous() {
 845             checkForComodification();
 846             int i = cursor - 1;
 847             if (i < 0)
 848                 throw new NoSuchElementException();
 849             Object[] elementData = ArrayList.this.elementData;
 850             if (i >= elementData.length)
 851                 throw new ConcurrentModificationException();
 852             cursor = i;
 853             return (E) elementData[lastRet = i];
 854         }
 855 
 856         public void set(E e) {
 857             if (lastRet < 0)
 858                 throw new IllegalStateException();
 859             checkForComodification();
 860 
 861             try {
 862                 ArrayList.this.set(lastRet, e);
 863             } catch (IndexOutOfBoundsException ex) {
 864                 throw new ConcurrentModificationException();
 865             }
 866         }
 867 
 868         public void add(E e) {
 869             checkForComodification();
 870 
 871             try {
 872                 int i = cursor;
 873                 ArrayList.this.add(i, e);
 874                 cursor = i + 1;
 875                 lastRet = -1;
 876                 expectedModCount = modCount;
 877             } catch (IndexOutOfBoundsException ex) {
 878                 throw new ConcurrentModificationException();
 879             }
 880         }
 881     }
 882 
 883     /**
 884      * Returns a view of the portion of this list between the specified
 885      * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.  (If
 886      * {@code fromIndex} and {@code toIndex} are equal, the returned list is
 887      * empty.)  The returned list is backed by this list, so non-structural
 888      * changes in the returned list are reflected in this list, and vice-versa.
 889      * The returned list supports all of the optional list operations.
 890      *
 891      * <p>This method eliminates the need for explicit range operations (of
 892      * the sort that commonly exist for arrays).  Any operation that expects
 893      * a list can be used as a range operation by passing a subList view
 894      * instead of a whole list.  For example, the following idiom
 895      * removes a range of elements from a list:
 896      * <pre>
 897      *      list.subList(from, to).clear();
 898      * </pre>
 899      * Similar idioms may be constructed for {@link #indexOf(Object)} and
 900      * {@link #lastIndexOf(Object)}, and all of the algorithms in the
 901      * {@link Collections} class can be applied to a subList.
 902      *
 903      * <p>The semantics of the list returned by this method become undefined if
 904      * the backing list (i.e., this list) is <i>structurally modified</i> in
 905      * any way other than via the returned list.  (Structural modifications are
 906      * those that change the size of this list, or otherwise perturb it in such
 907      * a fashion that iterations in progress may yield incorrect results.)
 908      *
 909      * @throws IndexOutOfBoundsException {@inheritDoc}
 910      * @throws IllegalArgumentException {@inheritDoc}
 911      */
 912     public List<E> subList(int fromIndex, int toIndex) {
 913         subListRangeCheck(fromIndex, toIndex, size);
 914         return new SubList(this, 0, fromIndex, toIndex);
 915     }
 916 
 917     static void subListRangeCheck(int fromIndex, int toIndex, int size) {
 918         if (fromIndex < 0)
 919             throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 920         if (toIndex > size)
 921             throw new IndexOutOfBoundsException("toIndex = " + toIndex);
 922         if (fromIndex > toIndex)
 923             throw new IllegalArgumentException("fromIndex(" + fromIndex +
 924                                                ") > toIndex(" + toIndex + ")");
 925     }
 926 
 927     private class SubList extends AbstractList<E> implements RandomAccess {
 928         private final AbstractList<E> parent;
 929         private final int parentOffset;
 930         private final int offset;
 931         int size;
 932 
 933         SubList(AbstractList<E> parent,
 934                 int offset, int fromIndex, int toIndex) {
 935             this.parent = parent;
 936             this.parentOffset = fromIndex;
 937             this.offset = offset + fromIndex;
 938             this.size = toIndex - fromIndex;
 939             this.modCount = ArrayList.this.modCount;
 940         }
 941 
 942         public E set(int index, E e) {
 943             rangeCheck(index);
 944             checkForComodification();
 945             E oldValue = ArrayList.this.elementData(offset + index);
 946             ArrayList.this.elementData[offset + index] = e;
 947             return oldValue;
 948         }
 949 
 950         public E get(int index) {
 951             rangeCheck(index);
 952             checkForComodification();
 953             return ArrayList.this.elementData(offset + index);
 954         }
 955 
 956         public int size() {
 957             checkForComodification();
 958             return this.size;
 959         }
 960 
 961         public void add(int index, E e) {
 962             rangeCheckForAdd(index);
 963             checkForComodification();
 964             parent.add(parentOffset + index, e);
 965             this.modCount = parent.modCount;
 966             this.size++;
 967         }
 968 
 969         public E remove(int index) {
 970             rangeCheck(index);
 971             checkForComodification();
 972             E result = parent.remove(parentOffset + index);
 973             this.modCount = parent.modCount;
 974             this.size--;
 975             return result;
 976         }
 977 
 978         protected void removeRange(int fromIndex, int toIndex) {
 979             checkForComodification();
 980             parent.removeRange(parentOffset + fromIndex,
 981                                parentOffset + toIndex);
 982             this.modCount = parent.modCount;
 983             this.size -= toIndex - fromIndex;
 984         }
 985 
 986         public boolean addAll(Collection<? extends E> c) {
 987             return addAll(this.size, c);
 988         }
 989 
 990         public boolean addAll(int index, Collection<? extends E> c) {
 991             rangeCheckForAdd(index);
 992             int cSize = c.size();
 993             if (cSize==0)
 994                 return false;
 995 
 996             checkForComodification();
 997             parent.addAll(parentOffset + index, c);
 998             this.modCount = parent.modCount;
 999             this.size += cSize;
1000             return true;
1001         }
1002 
1003         public Iterator<E> iterator() {
1004             return listIterator();
1005         }
1006 
1007         public ListIterator<E> listIterator(final int index) {
1008             checkForComodification();
1009             rangeCheckForAdd(index);
1010             final int offset = this.offset;
1011 
1012             return new ListIterator<E>() {
1013                 int cursor = index;
1014                 int lastRet = -1;
1015                 int expectedModCount = ArrayList.this.modCount;
1016 
1017                 public boolean hasNext() {
1018                     return cursor != SubList.this.size;
1019                 }
1020 
1021                 @SuppressWarnings("unchecked")
1022                 public E next() {
1023                     checkForComodification();
1024                     int i = cursor;
1025                     if (i >= SubList.this.size)
1026                         throw new NoSuchElementException();
1027                     Object[] elementData = ArrayList.this.elementData;
1028                     if (offset + i >= elementData.length)
1029                         throw new ConcurrentModificationException();
1030                     cursor = i + 1;
1031                     return (E) elementData[offset + (lastRet = i)];
1032                 }
1033 
1034                 public boolean hasPrevious() {
1035                     return cursor != 0;
1036                 }
1037 
1038                 @SuppressWarnings("unchecked")
1039                 public E previous() {
1040                     checkForComodification();
1041                     int i = cursor - 1;
1042                     if (i < 0)
1043                         throw new NoSuchElementException();
1044                     Object[] elementData = ArrayList.this.elementData;
1045                     if (offset + i >= elementData.length)
1046                         throw new ConcurrentModificationException();
1047                     cursor = i;
1048                     return (E) elementData[offset + (lastRet = i)];
1049                 }
1050 
1051                 public int nextIndex() {
1052                     return cursor;
1053                 }
1054 
1055                 public int previousIndex() {
1056                     return cursor - 1;
1057                 }
1058 
1059                 public void remove() {
1060                     if (lastRet < 0)
1061                         throw new IllegalStateException();
1062                     checkForComodification();
1063 
1064                     try {
1065                         SubList.this.remove(lastRet);
1066                         cursor = lastRet;
1067                         lastRet = -1;
1068                         expectedModCount = ArrayList.this.modCount;
1069                     } catch (IndexOutOfBoundsException ex) {
1070                         throw new ConcurrentModificationException();
1071                     }
1072                 }
1073 
1074                 public void set(E e) {
1075                     if (lastRet < 0)
1076                         throw new IllegalStateException();
1077                     checkForComodification();
1078 
1079                     try {
1080                         ArrayList.this.set(offset + lastRet, e);
1081                     } catch (IndexOutOfBoundsException ex) {
1082                         throw new ConcurrentModificationException();
1083                     }
1084                 }
1085 
1086                 public void add(E e) {
1087                     checkForComodification();
1088 
1089                     try {
1090                         int i = cursor;
1091                         SubList.this.add(i, e);
1092                         cursor = i + 1;
1093                         lastRet = -1;
1094                         expectedModCount = ArrayList.this.modCount;
1095                     } catch (IndexOutOfBoundsException ex) {
1096                         throw new ConcurrentModificationException();
1097                     }
1098                 }
1099 
1100                 final void checkForComodification() {
1101                     if (expectedModCount != ArrayList.this.modCount)
1102                         throw new ConcurrentModificationException();
1103                 }
1104             };
1105         }
1106 
1107         public List<E> subList(int fromIndex, int toIndex) {
1108             subListRangeCheck(fromIndex, toIndex, size);
1109             return new SubList(this, offset, fromIndex, toIndex);
1110         }
1111 
1112         private void rangeCheck(int index) {
1113             if (index < 0 || index >= this.size)
1114                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1115         }
1116 
1117         private void rangeCheckForAdd(int index) {
1118             if (index < 0 || index > this.size)
1119                 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
1120         }
1121 
1122         private String outOfBoundsMsg(int index) {
1123             return "Index: "+index+", Size: "+this.size;
1124         }
1125 
1126         private void checkForComodification() {
1127             if (ArrayList.this.modCount != this.modCount)
1128                 throw new ConcurrentModificationException();
1129         }
1130     }
1131 }
--- EOF ---