001/* ArrayList.java -- JDK1.2's answer to Vector; this is an array-backed
002   implementation of the List interface
003   Copyright (C) 1998, 1999, 2000, 2001, 2004, 2005  Free Software Foundation, Inc.
004
005This file is part of GNU Classpath.
006
007GNU Classpath is free software; you can redistribute it and/or modify
008it under the terms of the GNU General Public License as published by
009the Free Software Foundation; either version 2, or (at your option)
010any later version.
011
012GNU Classpath is distributed in the hope that it will be useful, but
013WITHOUT ANY WARRANTY; without even the implied warranty of
014MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
015General Public License for more details.
016
017You should have received a copy of the GNU General Public License
018along with GNU Classpath; see the file COPYING.  If not, write to the
019Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02002110-1301 USA.
021
022Linking this library statically or dynamically with other modules is
023making a combined work based on this library.  Thus, the terms and
024conditions of the GNU General Public License cover the whole
025combination.
026
027As a special exception, the copyright holders of this library give you
028permission to link this library with independent modules to produce an
029executable, regardless of the license terms of these independent
030modules, and to copy and distribute the resulting executable under
031terms of your choice, provided that you also meet, for each linked
032independent module, the terms and conditions of the license of that
033module.  An independent module is a module which is not derived from
034or based on this library.  If you modify this library, you may extend
035this exception to your version of the library, but you are not
036obligated to do so.  If you do not wish to do so, delete this
037exception statement from your version. */
038
039
040package java.util;
041
042import java.io.IOException;
043import java.io.ObjectInputStream;
044import java.io.ObjectOutputStream;
045import java.io.Serializable;
046import java.lang.reflect.Array;
047
048/**
049 * An array-backed implementation of the List interface.  This implements
050 * all optional list operations, and permits null elements, so that it is
051 * better than Vector, which it replaces. Random access is roughly constant
052 * time, and iteration is roughly linear time, so it is nice and fast, with
053 * less overhead than a LinkedList.
054 * <p>
055 *
056 * Each list has a capacity, and as the array reaches that capacity it
057 * is automatically transferred to a larger array. You also have access to
058 * ensureCapacity and trimToSize to control the backing array's size, avoiding
059 * reallocation or wasted memory.
060 * <p>
061 *
062 * ArrayList is not synchronized, so if you need multi-threaded access,
063 * consider using:<br>
064 * <code>List l = Collections.synchronizedList(new ArrayList(...));</code>
065 * <p>
066 *
067 * The iterators are <i>fail-fast</i>, meaning that any structural
068 * modification, except for <code>remove()</code> called on the iterator
069 * itself, cause the iterator to throw a
070 * {@link ConcurrentModificationException} rather than exhibit
071 * non-deterministic behavior.
072 *
073 * @author Jon A. Zeppieri
074 * @author Bryce McKinlay
075 * @author Eric Blake (ebb9@email.byu.edu)
076 * @see Collection
077 * @see List
078 * @see LinkedList
079 * @see Vector
080 * @see Collections#synchronizedList(List)
081 * @see AbstractList
082 * @status updated to 1.4
083 */
084public class ArrayList<E> extends AbstractList<E>
085  implements List<E>, RandomAccess, Cloneable, Serializable
086{
087  /**
088   * Compatible with JDK 1.2
089   */
090  private static final long serialVersionUID = 8683452581122892189L;
091
092  /**
093   * The default capacity for new ArrayLists.
094   */
095  private static final int DEFAULT_CAPACITY = 10;
096
097  /**
098   * The number of elements in this list.
099   * @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}