libjava/classpath/java/util/ArrayList.java

   1 /* ArrayList.java -- JDK1.2's answer to Vector; this is an array-backed
   2    implementation of the List interface
   3    Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005  Free Software Foundation, Inc.
   4
   5 This file is part of GNU Classpath.
   6
   7 GNU Classpath is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU Classpath is distributed in the hope that it will be useful, but
  13 WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU Classpath; see the file COPYING.  If not, write to the
  19 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301 USA.
  21
  22 Linking this library statically or dynamically with other modules is
  23 making a combined work based on this library.  Thus, the terms and
  24 conditions of the GNU General Public License cover the whole
  25 combination.
  26
  27 As a special exception, the copyright holders of this library give you
  28 permission to link this library with independent modules to produce an
  29 executable, regardless of the license terms of these independent
  30 modules, and to copy and distribute the resulting executable under
  31 terms of your choice, provided that you also meet, for each linked
  32 independent module, the terms and conditions of the license of that
  33 module.  An independent module is a module which is not derived from
  34 or based on this library.  If you modify this library, you may extend
  35 this exception to your version of the library, but you are not
  36 obligated to do so.  If you do not wish to do so, delete this
  37 exception statement from your version. */
  38
  39
  40 package java.util;
  41
  42 import java.io.IOException;
  43 import java.io.ObjectInputStream;
  44 import java.io.ObjectOutputStream;
  45 import java.io.Serializable;
  46 import java.lang.reflect.Array;
  47
  48 /**
  49  * An array-backed implementation of the List interface.  This implements
  50  * all optional list operations, and permits null elements, so that it is
  51  * better than Vector, which it replaces. Random access is roughly constant
  52  * time, and iteration is roughly linear time, so it is nice and fast, with
  53  * less overhead than a LinkedList.
  54  * <p>
  55  *
  56  * Each list has a capacity, and as the array reaches that capacity it
  57  * is automatically transferred to a larger array. You also have access to
  58  * ensureCapacity and trimToSize to control the backing array's size, avoiding
  59  * reallocation or wasted memory.
  60  * <p>
  61  *
  62  * ArrayList is not synchronized, so if you need multi-threaded access,
  63  * consider using:<br>
  64  * <code>List l = Collections.synchronizedList(new ArrayList(...));</code>
  65  * <p>
  66  *
  67  * The iterators are <i>fail-fast</i>, meaning that any structural
  68  * modification, except for <code>remove()</code> called on the iterator
  69  * itself, cause the iterator to throw a
  70  * {@link ConcurrentModificationException} rather than exhibit
  71  * non-deterministic behavior.
  72  *
  73  * @author Jon A. Zeppieri
  74  * @author Bryce McKinlay
  75  * @author Eric Blake (ebb9@email.byu.edu)
  76  * @see Collection
  77  * @see List
  78  * @see LinkedList
  79  * @see Vector
  80  * @see Collections#synchronizedList(List)
  81  * @see AbstractList
  82  * @status updated to 1.4
  83  */
  84 public class ArrayList<E> extends AbstractList<E>
  85   implements List<E>, RandomAccess, Cloneable, Serializable
  86 {
  87   /**
  88    * Compatible with JDK 1.2
  89    */
  90   private static final long serialVersionUID = 8683452581122892189L;
  91
  92   /**
  93    * The default capacity for new ArrayLists.
  94    */
  95   private static final int DEFAULT_CAPACITY = 10;
  96
  97   /**
  98    * The number of elements in this list.
  99    * @serial the list size
 100    */
 101   private int size;
 102
 103   /**
 104    * Where the data is stored.
 105    */
 106   private transient E[] data;
 107
 108   /**
 109    * Construct a new ArrayList with the supplied initial capacity.
 110    *
 111    * @param capacity initial capacity of this ArrayList
 112    * @throws IllegalArgumentException if capacity is negative
 113    */
 114   public ArrayList(int capacity)
 115   {
 116     // Must explicitly check, to get correct exception.
 117     if (capacity < 0)
 118       throw new IllegalArgumentException();
 119     data = (E[]) new Object[capacity];
 120   }
 121
 122   /**
 123    * Construct a new ArrayList with the default capacity (16).
 124    */
 125   public ArrayList()
 126   {
 127     this(DEFAULT_CAPACITY);
 128   }
 129
 130   /**
 131    * Construct a new ArrayList, and initialize it with the elements
 132    * in the supplied Collection. The initial capacity is 110% of the
 133    * Collection's size.
 134    *
 135    * @param c the collection whose elements will initialize this list
 136    * @throws NullPointerException if c is null
 137    */
 138   public ArrayList(Collection<? extends E> c)
 139   {
 140     this((int) (c.size() * 1.1f));
 141     addAll(c);
 142   }
 143
 144   /**
 145    * Trims the capacity of this List to be equal to its size;
 146    * a memory saver.
 147    */
 148   public void trimToSize()
 149   {
 150     // Not a structural change from the perspective of iterators on this list,
 151     // so don't update modCount.
 152     if (size != data.length)
 153       {
 154         E[] newData = (E[]) new Object[size];
 155         System.arraycopy(data, 0, newData, 0, size);
 156         data = newData;
 157       }
 158   }
 159
 160   /**
 161    * Guarantees that this list will have at least enough capacity to
 162    * hold minCapacity elements. This implementation will grow the list to
 163    * max(current * 2, minCapacity) if (minCapacity &gt; current). The JCL says
 164    * explictly that "this method increases its capacity to minCap", while
 165    * the JDK 1.3 online docs specify that the list will grow to at least the
 166    * size specified.
 167    *
 168    * @param minCapacity the minimum guaranteed capacity
 169    */
 170   public void ensureCapacity(int minCapacity)
 171   {
 172     int current = data.length;
 173
 174     if (minCapacity > current)
 175       {
 176         E[] newData = (E[]) new Object[Math.max(current * 2, minCapacity)];
 177         System.arraycopy(data, 0, newData, 0, size);
 178         data = newData;
 179       }
 180   }
 181
 182   /**
 183    * Returns the number of elements in this list.
 184    *
 185    * @return the list size
 186    */
 187   public int size()
 188   {
 189     return size;
 190   }
 191
 192   /**
 193    * Checks if the list is empty.
 194    *
 195    * @return true if there are no elements
 196    */
 197   public boolean isEmpty()
 198   {
 199     return size == 0;
 200   }
 201
 202   /**
 203    * Returns true iff element is in this ArrayList.
 204    *
 205    * @param e the element whose inclusion in the List is being tested
 206    * @return true if the list contains e
 207    */
 208   public boolean contains(Object e)
 209   {
 210     return indexOf(e) != -1;
 211   }
 212
 213   /**
 214    * Returns the lowest index at which element appears in this List, or
 215    * -1 if it does not appear.
 216    *
 217    * @param e the element whose inclusion in the List is being tested
 218    * @return the index where e was found
 219    */
 220   public int indexOf(Object e)
 221   {
 222     for (int i = 0; i < size; i++)
 223       if (equals(e, data[i]))
 224         return i;
 225     return -1;
 226   }
 227
 228   /**
 229    * Returns the highest index at which element appears in this List, or
 230    * -1 if it does not appear.
 231    *
 232    * @param e the element whose inclusion in the List is being tested
 233    * @return the index where e was found
 234    */
 235   public int lastIndexOf(Object e)
 236   {
 237     for (int i = size - 1; i >= 0; i--)
 238       if (equals(e, data[i]))
 239         return i;
 240     return -1;
 241   }
 242
 243   /**
 244    * Creates a shallow copy of this ArrayList (elements are not cloned).
 245    *
 246    * @return the cloned object
 247    */
 248   public Object clone()
 249   {
 250     ArrayList<E> clone = null;
 251     try
 252       {
 253         clone = (ArrayList<E>) super.clone();
 254         clone.data = (E[]) data.clone();
 255       }
 256     catch (CloneNotSupportedException e)
 257       {
 258         // Impossible to get here.
 259       }
 260     return clone;
 261   }
 262
 263   /**
 264    * Returns an Object array containing all of the elements in this ArrayList.
 265    * The array is independent of this list.
 266    *
 267    * @return an array representation of this list
 268    */
 269   public Object[] toArray()
 270   {
 271     E[] array = (E[]) new Object[size];
 272     System.arraycopy(data, 0, array, 0, size);
 273     return array;
 274   }
 275
 276   /**
 277    * Returns an Array whose component type is the runtime component type of
 278    * the passed-in Array.  The returned Array is populated with all of the
 279    * elements in this ArrayList.  If the passed-in Array is not large enough
 280    * to store all of the elements in this List, a new Array will be created
 281    * and returned; if the passed-in Array is <i>larger</i> than the size
 282    * of this List, then size() index will be set to null.
 283    *
 284    * @param a the passed-in Array
 285    * @return an array representation of this list
 286    * @throws ArrayStoreException if the runtime type of a does not allow
 287    *         an element in this list
 288    * @throws NullPointerException if a is null
 289    */
 290   public <T> T[] toArray(T[] a)
 291   {
 292     if (a.length < size)
 293       a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
 294     else if (a.length > size)
 295       a[size] = null;
 296     System.arraycopy(data, 0, a, 0, size);
 297     return a;
 298   }
 299
 300   /**
 301    * Retrieves the element at the user-supplied index.
 302    *
 303    * @param index the index of the element we are fetching
 304    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 305    */
 306   public E get(int index)
 307   {
 308     checkBoundExclusive(index);
 309     return data[index];
 310   }
 311
 312   /**
 313    * Sets the element at the specified index.  The new element, e,
 314    * can be an object of any type or null.
 315    *
 316    * @param index the index at which the element is being set
 317    * @param e the element to be set
 318    * @return the element previously at the specified index
 319    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= 0
 320    */
 321   public E set(int index, E e)
 322   {
 323     checkBoundExclusive(index);
 324     E result = data[index];
 325     data[index] = e;
 326     return result;
 327   }
 328
 329   /**
 330    * Appends the supplied element to the end of this list.
 331    * The element, e, can be an object of any type or null.
 332    *
 333    * @param e the element to be appended to this list
 334    * @return true, the add will always succeed
 335    */
 336   public boolean add(E e)
 337   {
 338     modCount++;
 339     if (size == data.length)
 340       ensureCapacity(size + 1);
 341     data[size++] = e;
 342     return true;
 343   }
 344
 345   /**
 346    * Adds the supplied element at the specified index, shifting all
 347    * elements currently at that index or higher one to the right.
 348    * The element, e, can be an object of any type or null.
 349    *
 350    * @param index the index at which the element is being added
 351    * @param e the item being added
 352    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 353    */
 354   public void add(int index, E e)
 355   {
 356     checkBoundInclusive(index);
 357     modCount++;
 358     if (size == data.length)
 359       ensureCapacity(size + 1);
 360     if (index != size)
 361       System.arraycopy(data, index, data, index + 1, size - index);
 362     data[index] = e;
 363     size++;
 364   }
 365
 366   /**
 367    * Removes the element at the user-supplied index.
 368    *
 369    * @param index the index of the element to be removed
 370    * @return the removed Object
 371    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 372    */
 373   public E remove(int index)
 374   {
 375     checkBoundExclusive(index);
 376     E r = data[index];
 377     modCount++;
 378     if (index != --size)
 379       System.arraycopy(data, index + 1, data, index, size - index);
 380     // Aid for garbage collection by releasing this pointer.
 381     data[size] = null;
 382     return r;
 383   }
 384
 385   /**
 386    * Removes all elements from this List
 387    */
 388   public void clear()
 389   {
 390     if (size > 0)
 391       {
 392         modCount++;
 393         // Allow for garbage collection.
 394         Arrays.fill(data, 0, size, null);
 395         size = 0;
 396       }
 397   }
 398
 399   /**
 400    * Add each element in the supplied Collection to this List. It is undefined
 401    * what happens if you modify the list while this is taking place; for
 402    * example, if the collection contains this list.  c can contain objects
 403    * of any type, as well as null values.
 404    *
 405    * @param c a Collection containing elements to be added to this List
 406    * @return true if the list was modified, in other words c is not empty
 407    * @throws NullPointerException if c is null
 408    */
 409   public boolean addAll(Collection<? extends E> c)
 410   {
 411     return addAll(size, c);
 412   }
 413
 414   /**
 415    * Add all elements in the supplied collection, inserting them beginning
 416    * at the specified index.  c can contain objects of any type, as well
 417    * as null values.
 418    *
 419    * @param index the index at which the elements will be inserted
 420    * @param c the Collection containing the elements to be inserted
 421    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; 0
 422    * @throws NullPointerException if c is null
 423    */
 424   public boolean addAll(int index, Collection<? extends E> c)
 425   {
 426     checkBoundInclusive(index);
 427     Iterator<? extends E> itr = c.iterator();
 428     int csize = c.size();
 429
 430     modCount++;
 431     if (csize + size > data.length)
 432       ensureCapacity(size + csize);
 433     int end = index + csize;
 434     if (size > 0 && index != size)
 435       System.arraycopy(data, index, data, end, size - index);
 436     size += csize;
 437     for ( ; index < end; index++)
 438       data[index] = itr.next();
 439     return csize > 0;
 440   }
 441
 442   /**
 443    * Removes all elements in the half-open interval [fromIndex, toIndex).
 444    * Does nothing when toIndex is equal to fromIndex.
 445    *
 446    * @param fromIndex the first index which will be removed
 447    * @param toIndex one greater than the last index which will be removed
 448    * @throws IndexOutOfBoundsException if fromIndex &gt; toIndex
 449    */
 450   protected void removeRange(int fromIndex, int toIndex)
 451   {
 452     int change = toIndex - fromIndex;
 453     if (change > 0)
 454       {
 455         modCount++;
 456         System.arraycopy(data, toIndex, data, fromIndex, size - toIndex);
 457         size -= change;
 458       }
 459     else if (change < 0)
 460       throw new IndexOutOfBoundsException();
 461   }
 462
 463   /**
 464    * Checks that the index is in the range of possible elements (inclusive).
 465    *
 466    * @param index the index to check
 467    * @throws IndexOutOfBoundsException if index &gt; size
 468    */
 469   private void checkBoundInclusive(int index)
 470   {
 471     // Implementation note: we do not check for negative ranges here, since
 472     // use of a negative index will cause an ArrayIndexOutOfBoundsException,
 473     // a subclass of the required exception, with no effort on our part.
 474     if (index > size)
 475       raiseBoundsError(index);
 476   }
 477
 478   /**
 479    * Checks that the index is in the range of existing elements (exclusive).
 480    *
 481    * @param index the index to check
 482    * @throws IndexOutOfBoundsException if index &gt;= size
 483    */
 484   private void checkBoundExclusive(int index)
 485   {
 486     // Implementation note: we do not check for negative ranges here, since
 487     // use of a negative index will cause an ArrayIndexOutOfBoundsException,
 488     // a subclass of the required exception, with no effort on our part.
 489     if (index >= size)
 490       raiseBoundsError(index);
 491   }
 492
 493   /**
 494    * Raise the ArrayIndexOfOutBoundsException.
 495    *
 496    * @param index the index of the access
 497    * @throws IndexOutOfBoundsException unconditionally
 498    */
 499   private void raiseBoundsError(int index)
 500   {
 501     // Implementaion note: put in a separate method to make the JITs job easier
 502     // (separate common from uncommon code at method boundaries when trivial to
 503     // do so).
 504     throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
 505   }
 506
 507
 508   /**
 509    * Remove from this list all elements contained in the given collection.
 510    * This is not public, due to Sun's API, but this performs in linear
 511    * time while the default behavior of AbstractList would be quadratic.
 512    *
 513    * @param c the collection to filter out
 514    * @return true if this list changed
 515    * @throws NullPointerException if c is null
 516    */
 517   boolean removeAllInternal(Collection<?> c)
 518   {
 519     int i;
 520     int j;
 521     for (i = 0; i < size; i++)
 522       if (c.contains(data[i]))
 523         break;
 524     if (i == size)
 525       return false;
 526
 527     modCount++;
 528     for (j = i++; i < size; i++)
 529       if (! c.contains(data[i]))
 530         data[j++] = data[i];
 531     size -= i - j;
 532     return true;
 533   }
 534
 535   /**
 536    * Retain in this vector only the elements contained in the given collection.
 537    * This is not public, due to Sun's API, but this performs in linear
 538    * time while the default behavior of AbstractList would be quadratic.
 539    *
 540    * @param c the collection to filter by
 541    * @return true if this vector changed
 542    * @throws NullPointerException if c is null
 543    * @since 1.2
 544    */
 545   boolean retainAllInternal(Collection<?> c)
 546   {
 547     int i;
 548     int j;
 549     for (i = 0; i < size; i++)
 550       if (! c.contains(data[i]))
 551         break;
 552     if (i == size)
 553       return false;
 554
 555     modCount++;
 556     for (j = i++; i < size; i++)
 557       if (c.contains(data[i]))
 558         data[j++] = data[i];
 559     size -= i - j;
 560     return true;
 561   }
 562
 563   /**
 564    * Serializes this object to the given stream.
 565    *
 566    * @param s the stream to write to
 567    * @throws IOException if the underlying stream fails
 568    * @serialData the size field (int), the length of the backing array
 569    *             (int), followed by its elements (Objects) in proper order.
 570    */
 571   private void writeObject(ObjectOutputStream s) throws IOException
 572   {
 573     // The 'size' field.
 574     s.defaultWriteObject();
 575     // We serialize unused list entries to preserve capacity.
 576     int len = data.length;
 577     s.writeInt(len);
 578     // it would be more efficient to just write "size" items,
 579     // this need readObject read "size" items too.
 580     for (int i = 0; i < size; i++)
 581       s.writeObject(data[i]);
 582   }
 583
 584   /**
 585    * Deserializes this object from the given stream.
 586    *
 587    * @param s the stream to read from
 588    * @throws ClassNotFoundException if the underlying stream fails
 589    * @throws IOException if the underlying stream fails
 590    * @serialData the size field (int), the length of the backing array
 591    *             (int), followed by its elements (Objects) in proper order.
 592    */
 593   private void readObject(ObjectInputStream s)
 594     throws IOException, ClassNotFoundException
 595   {
 596     // the `size' field.
 597     s.defaultReadObject();
 598     int capacity = s.readInt();
 599     data = (E[]) new Object[capacity];
 600     for (int i = 0; i < size; i++)
 601       data[i] = (E) s.readObject();
 602   }
 603 }