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