libjava/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., 59 Temple Place, Suite 330, Boston, MA
  20 02111-1307 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 extends AbstractList
  85   implements List, 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 = 16;
  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 Object[] 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 = 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 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         Object[] newData = 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         Object[] newData = 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 clone = null;
 251     try
 252       {
 253         clone = (ArrayList) super.clone();
 254         clone.data = (Object[]) 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     Object[] array = 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 Object[] toArray(Object[] a)
 291   {
 292     if (a.length < size)
 293       a = (Object[]) Array.newInstance(a.getClass().getComponentType(),
 294                                        size);
 295     else if (a.length > size)
 296       a[size] = null;
 297     System.arraycopy(data, 0, a, 0, size);
 298     return a;
 299   }
 300
 301   /**
 302    * Retrieves the element at the user-supplied index.
 303    *
 304    * @param index the index of the element we are fetching
 305    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 306    */
 307   public Object get(int index)
 308   {
 309     checkBoundExclusive(index);
 310     return data[index];
 311   }
 312
 313   /**
 314    * Sets the element at the specified index.  The new element, e,
 315    * can be an object of any type or null.
 316    *
 317    * @param index the index at which the element is being set
 318    * @param e the element to be set
 319    * @return the element previously at the specified index
 320    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= 0
 321    */
 322   public Object set(int index, Object e)
 323   {
 324     checkBoundExclusive(index);
 325     Object result = data[index];
 326     data[index] = e;
 327     return result;
 328   }
 329
 330   /**
 331    * Appends the supplied element to the end of this list.
 332    * The element, e, can be an object of any type or null.
 333    *
 334    * @param e the element to be appended to this list
 335    * @return true, the add will always succeed
 336    */
 337   public boolean add(Object e)
 338   {
 339     modCount++;
 340     if (size == data.length)
 341       ensureCapacity(size + 1);
 342     data[size++] = e;
 343     return true;
 344   }
 345
 346   /**
 347    * Adds the supplied element at the specified index, shifting all
 348    * elements currently at that index or higher one to the right.
 349    * The element, e, can be an object of any type or null.
 350    *
 351    * @param index the index at which the element is being added
 352    * @param e the item being added
 353    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
 354    */
 355   public void add(int index, Object e)
 356   {
 357     checkBoundInclusive(index);
 358     modCount++;
 359     if (size == data.length)
 360       ensureCapacity(size + 1);
 361     if (index != size)
 362       System.arraycopy(data, index, data, index + 1, size - index);
 363     data[index] = e;
 364     size++;
 365   }
 366
 367   /**
 368    * Removes the element at the user-supplied index.
 369    *
 370    * @param index the index of the element to be removed
 371    * @return the removed Object
 372    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
 373    */
 374   public Object remove(int index)
 375   {
 376     checkBoundExclusive(index);
 377     Object r = data[index];
 378     modCount++;
 379     if (index != --size)
 380       System.arraycopy(data, index + 1, data, index, size - index);
 381     // Aid for garbage collection by releasing this pointer.
 382     data[size] = null;
 383     return r;
 384   }
 385
 386   /**
 387    * Removes all elements from this List
 388    */
 389   public void clear()
 390   {
 391     if (size > 0)
 392       {
 393         modCount++;
 394         // Allow for garbage collection.
 395         Arrays.fill(data, 0, size, null);
 396         size = 0;
 397       }
 398   }
 399
 400   /**
 401    * Add each element in the supplied Collection to this List. It is undefined
 402    * what happens if you modify the list while this is taking place; for
 403    * example, if the collection contains this list.  c can contain objects
 404    * of any type, as well as null values.
 405    *
 406    * @param c a Collection containing elements to be added to this List
 407    * @return true if the list was modified, in other words c is not empty
 408    * @throws NullPointerException if c is null
 409    */
 410   public boolean addAll(Collection c)
 411   {
 412     return addAll(size, c);
 413   }
 414
 415   /**
 416    * Add all elements in the supplied collection, inserting them beginning
 417    * at the specified index.  c can contain objects of any type, as well
 418    * as null values.
 419    *
 420    * @param index the index at which the elements will be inserted
 421    * @param c the Collection containing the elements to be inserted
 422    * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; 0
 423    * @throws NullPointerException if c is null
 424    */
 425   public boolean addAll(int index, Collection c)
 426   {
 427     checkBoundInclusive(index);
 428     Iterator itr = c.iterator();
 429     int csize = c.size();
 430
 431     modCount++;
 432     if (csize + size > data.length)
 433       ensureCapacity(size + csize);
 434     int end = index + csize;
 435     if (size > 0 && index != size)
 436       System.arraycopy(data, index, data, end, size - index);
 437     size += csize;
 438     for ( ; index < end; index++)
 439       data[index] = itr.next();
 440     return csize > 0;
 441   }
 442
 443   /**
 444    * Removes all elements in the half-open interval [fromIndex, toIndex).
 445    * Does nothing when toIndex is equal to fromIndex.
 446    *
 447    * @param fromIndex the first index which will be removed
 448    * @param toIndex one greater than the last index which will be removed
 449    * @throws IndexOutOfBoundsException if fromIndex &gt; toIndex
 450    */
 451   protected void removeRange(int fromIndex, int toIndex)
 452   {
 453     int change = toIndex - fromIndex;
 454     if (change > 0)
 455       {
 456         modCount++;
 457         System.arraycopy(data, toIndex, data, fromIndex, size - toIndex);
 458         size -= change;
 459       }
 460     else if (change < 0)
 461       throw new IndexOutOfBoundsException();
 462   }
 463
 464   /**
 465    * Checks that the index is in the range of possible elements (inclusive).
 466    *
 467    * @param index the index to check
 468    * @throws IndexOutOfBoundsException if index &gt; size
 469    */
 470   private void checkBoundInclusive(int index)
 471   {
 472     // Implementation note: we do not check for negative ranges here, since
 473     // use of a negative index will cause an ArrayIndexOutOfBoundsException,
 474     // a subclass of the required exception, with no effort on our part.
 475     if (index > size)
 476       throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
 477                                           + size);
 478   }
 479
 480   /**
 481    * Checks that the index is in the range of existing elements (exclusive).
 482    *
 483    * @param index the index to check
 484    * @throws IndexOutOfBoundsException if index &gt;= size
 485    */
 486   private void checkBoundExclusive(int index)
 487   {
 488     // Implementation note: we do not check for negative ranges here, since
 489     // use of a negative index will cause an ArrayIndexOutOfBoundsException,
 490     // a subclass of the required exception, with no effort on our part.
 491     if (index >= size)
 492       throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
 493                                           + size);
 494   }
 495
 496   /**
 497    * Remove from this list all elements contained in the given collection.
 498    * This is not public, due to Sun's API, but this performs in linear
 499    * time while the default behavior of AbstractList would be quadratic.
 500    *
 501    * @param c the collection to filter out
 502    * @return true if this list changed
 503    * @throws NullPointerException if c is null
 504    */
 505   boolean removeAllInternal(Collection c)
 506   {
 507     int i;
 508     int j;
 509     for (i = 0; i < size; i++)
 510       if (c.contains(data[i]))
 511         break;
 512     if (i == size)
 513       return false;
 514
 515     modCount++;
 516     for (j = i++; i < size; i++)
 517       if (! c.contains(data[i]))
 518         data[j++] = data[i];
 519     size -= i - j;
 520     return true;
 521   }
 522
 523   /**
 524    * Retain in this vector only the elements contained in the given collection.
 525    * This is not public, due to Sun's API, but this performs in linear
 526    * time while the default behavior of AbstractList would be quadratic.
 527    *
 528    * @param c the collection to filter by
 529    * @return true if this vector changed
 530    * @throws NullPointerException if c is null
 531    * @since 1.2
 532    */
 533   boolean retainAllInternal(Collection c)
 534   {
 535     int i;
 536     int j;
 537     for (i = 0; i < size; i++)
 538       if (! c.contains(data[i]))
 539         break;
 540     if (i == size)
 541       return false;
 542
 543     modCount++;
 544     for (j = i++; i < size; i++)
 545       if (c.contains(data[i]))
 546         data[j++] = data[i];
 547     size -= i - j;
 548     return true;
 549   }
 550
 551   /**
 552    * Serializes this object to the given stream.
 553    *
 554    * @param out the stream to write to
 555    * @throws IOException if the underlying stream fails
 556    * @serialData the size field (int), the length of the backing array
 557    *             (int), followed by its elements (Objects) in proper order.
 558    */
 559   private void writeObject(ObjectOutputStream s) throws IOException
 560   {
 561     // The 'size' field.
 562     s.defaultWriteObject();
 563     // We serialize unused list entries to preserve capacity.
 564     int len = data.length;
 565     s.writeInt(len);
 566     // it would be more efficient to just write "size" items,
 567     // this need readObject read "size" items too.
 568     for (int i = 0; i < size; i++)
 569       s.writeObject(data[i]);
 570   }
 571
 572   /**
 573    * Deserializes this object from the given stream.
 574    *
 575    * @param in the stream to read from
 576    * @throws ClassNotFoundException if the underlying stream fails
 577    * @throws IOException if the underlying stream fails
 578    * @serialData the size field (int), the length of the backing array
 579    *             (int), followed by its elements (Objects) in proper order.
 580    */
 581   private void readObject(ObjectInputStream s)
 582     throws IOException, ClassNotFoundException
 583   {
 584     // the `size' field.
 585     s.defaultReadObject();
 586     int capacity = s.readInt();
 587     data = new Object[capacity];
 588     for (int i = 0; i < size; i++)
 589       data[i] = s.readObject();
 590   }
 591 }