ArrayList.java

/* ArrayList.java -- JDK1.2's answer to Vector; this is an array-backed
   implementation of the List interface
   Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

As a special exception, if you link this library with other files to
produce an executable, this library does not by itself cause the
resulting executable to be covered by the GNU General Public License.
This exception does not however invalidate any other reasons why the
executable file might be covered by the GNU General Public License. */


package java.util;

import java.lang.reflect.Array;
import java.io.Serializable;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;

/**
 * An array-backed implementation of the List interface.  ArrayList
 * performs well on simple tasks:  random access into a list, appending
 * to or removing from the end of a list, checking the size, &c.
 *
 * @author        Jon A. Zeppieri
 * @see           java.util.AbstractList
 * @see           java.util.List
 */
public class ArrayList extends AbstractList
  implements List, Cloneable, Serializable
{
  /** the default capacity for new ArrayLists */
  private static final int DEFAULT_CAPACITY = 16;

  /** the number of elements in this list */
  int size;

  /** where the data is stored */
  transient Object[] data;

  /** 
   * Construct a new ArrayList with the supplied initial capacity. 
   *
   * @param capacity Initial capacity of this ArrayList
   */
  public ArrayList(int capacity)
  {
    data = new Object[capacity];
  }


  /**
   * Construct a new ArrayList with the default capcity 
   */
  public ArrayList()
  {
    this(DEFAULT_CAPACITY);
  }

  /** 
   * Construct a new ArrayList, and initialize it with the elements
   * in the supplied Collection; Sun specs say that the initial 
   * capacity is 110% of the Collection's size.
   *
   * @param c the collection whose elements will initialize this list
   */
  public ArrayList(Collection c)
  {
    this((int) (c.size() * 1.1));
    addAll(c);
  }

  /**
   * Guarantees that this list will have at least enough capacity to
   * hold minCapacity elements. 
   *
   * @specnote This implementation will grow the list to 
   *   max(current * 2, minCapacity) if (minCapacity > current). The JCL says
   *   explictly that "this method increases its capacity to minCap", while
   *   the JDK 1.3 online docs specify that the list will grow to at least the
   *   size specified.
   * @param minCapacity the minimum guaranteed capacity
   */
  public void ensureCapacity(int minCapacity)
  {
    Object[] newData;
    int current = data.length;

    if (minCapacity > current)
      {
	newData = new Object[Math.max((current * 2), minCapacity)];
	System.arraycopy(data, 0, newData, 0, size);
	data = newData;
      }
  }

  /**
   * Appends the supplied element to the end of this list.
   *
   * @param       e      the element to be appended to this list
   */
  public boolean add(Object e)
  {
    modCount++;
    if (size == data.length)
      ensureCapacity(size + 1);
    data[size++] = e;
    return true;
  }

  /**
   * Retrieves the element at the user-supplied index.
   *
   * @param    index        the index of the element we are fetching
   * @throws   IndexOutOfBoundsException  (iIndex < 0) || (iIndex >= size())
   */
  public Object get(int index)
  {
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    return data[index];
  }

  /**
   * Returns the number of elements in this list 
   */
  public int size()
  {
    return size;
  }

  /**
   * Removes the element at the user-supplied index
   *
   * @param     iIndex      the index of the element to be removed
   * @return    the removed Object
   * @throws    IndexOutOfBoundsException  (iIndex < 0) || (iIndex >= size())
   */
  public Object remove(int index)
  {
    modCount++;
    if (index < 0 || index > size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    Object r = data[index];
    if (index != --size)
      System.arraycopy(data, (index + 1), data, index, (size - index));
    data[size] = null;
    return r;
  }

  /**
   * Removes all elements in the half-open interval [iFromIndex, iToIndex).
   *
   * @param     fromIndex   the first index which will be removed
   * @param     toIndex     one greater than the last index which will be 
   *                         removed
   */
  protected void removeRange(int fromIndex, int toIndex)
  {
    modCount++;
    if (fromIndex != toIndex)
      {
	System.arraycopy(data, toIndex, data, fromIndex, size - toIndex);
	size -= (toIndex - fromIndex);
      }
  }

  /**
   * Adds the supplied element at the specified index, shifting all
   * elements currently at that index or higher one to the right.
   *
   * @param     index      the index at which the element is being added
   * @param     e          the item being added
   */
  public void add(int index, Object e)
  {
    modCount++;
    if (index < 0 || index > size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    if (size == data.length)
      ensureCapacity(size + 1);
    if (index != size)
      System.arraycopy(data, index, data, index + 1, size - index);    
    data[index] = e;
    size++;
  }

  /** 
   * Add each element in the supplied Collection to this List.
   *
   * @param        c          a Collection containing elements to be 
   *                          added to this List
   */
  public boolean addAll(Collection c)
  {
    return addAll(size, c);
  }

  /** 
   * Add all elements in the supplied collection, inserting them beginning
   * at the specified index.
   *
   * @param     index       the index at which the elements will be inserted
   * @param     c           the Collection containing the elements to be
   *                        inserted
   */
  public boolean addAll(int index, Collection c)
  {
    if (index < 0 || index > size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    modCount++;
    Iterator itr = c.iterator();
    int csize = c.size();

    if (csize + size > data.length)
      ensureCapacity(size + csize);
    int end = index + csize;
    if (size > 0 && index != size)
      System.arraycopy(data, index, data, end, csize);
    size += csize;
    for (; index < end; index++)
      {
        data[index] = itr.next();
      }
    return (csize > 0);
  }

  /**
   * Creates a shallow copy of this ArrayList
   */
  public Object clone()
  {
    ArrayList clone = null;
    try
      {
	clone = (ArrayList) super.clone();
	clone.data = new Object[data.length];
	System.arraycopy(data, 0, clone.data, 0, size);
      }
    catch (CloneNotSupportedException e) {}
    return clone;
  }

  /** 
   * Returns true iff oElement is in this ArrayList.
   *
   * @param     e     the element whose inclusion in the List is being
   *                  tested
   */
  public boolean contains(Object e)
  {
    return (indexOf(e) != -1);
  }

  /**
   * Returns the lowest index at which oElement appears in this List, or 
   * -1 if it does not appear.
   *
   * @param    e       the element whose inclusion in the List is being
   *                   tested
   */
  public int indexOf(Object e)
  {
    for (int i = 0; i < size; i++)
      {
	if (e == null ? data[i] == null : e.equals(data[i]))
	  return i;
      }
    return -1;
  }

  /**
   * Returns the highest index at which oElement appears in this List, or 
   * -1 if it does not appear.
   *
   * @param    e       the element whose inclusion in the List is being
   *                   tested
   */
  public int lastIndexOf(Object e)
  {
    int i;

    for (i = size - 1; i >= 0; i--)
      {
	if (e == null ? data[i] == null : e.equals(data[i]))
	  return i;
      }
    return -1;
  }

  /**
   * Removes all elements from this List
   */
  public void clear()
  {
    modCount++;
    for (int i = 0; i < size; i++)
      {
	data[i] = null;
      }    
    size = 0;
  }

  /**
   * Sets the element at the specified index.
   *
   * @param     index   the index at which the element is being set
   * @param     e       the element to be set
   * @return    the element previously at the specified index, or null if
   *            none was there
   */
  public Object set(int index, Object e)
  {
    Object result;
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException("Index: " + index + ", Size:" + 
                                          size);
    result = data[index];
    // SEH: no structural change, so don't update modCount
    data[index] = e;
    return result;
  }

  /**
   * Returns an Object Array containing all of the elements in this ArrayList
   */
  public Object[] toArray()
  {
    Object[] array = new Object[size];
    System.arraycopy(data, 0, array, 0, size);
    return array;
  }

  /**
   * Returns an Array whose component type is the runtime component type of
   * the passed-in Array.  The returned Array is populated with all of the
   * elements in this ArrayList.  If the passed-in Array is not large enough
   * to store all of the elements in this List, a new Array will be created 
   * and returned; if the passed-in Array is <i>larger</i> than the size
   * of this List, then size() index will be set to null.
   *
   * @param      array      the passed-in Array
   */
  public Object[] toArray(Object[] array)
  {
    if (array.length < size)
      array = (Object[]) Array.newInstance(array.getClass().getComponentType(), 
        				   size);
    else if (array.length > size)
      array[size] = null;
    System.arraycopy(data, 0, array, 0, size);
    return array;
  }

  /**
   * Trims the capacity of this List to be equal to its size; 
   * a memory saver.   
   */
  public void trimToSize()
  {
    // not a structural change from the perspective of iterators on this list, 
    // so don't update modCount
    Object[] newData = new Object[size];
    System.arraycopy(data, 0, newData, 0, size);
    data = newData;
  }

  private void writeObject(ObjectOutputStream out) throws IOException
  {
    int i;

    // The 'size' field.
    out.defaultWriteObject();

    // FIXME: Do we really want to serialize unused list entries??
    out.writeInt(data.length);
    for (i = 0; i < data.length; i++)
      out.writeObject(data[i]);
  }

  private void readObject(ObjectInputStream in)
    throws IOException, ClassNotFoundException
  {
    int i;
    int capacity;

    // the `size' field.
    in.defaultReadObject();

    capacity = in.readInt();
    data = new Object[capacity];

    for (i = 0; i < capacity; i++)
      data[i] = in.readObject();
  }
}