First go at it. Daniel ([EMAIL PROTECTED])
/** *ArrayList.java * *@author Daniel Rall (<a href="mailto:[EMAIL PROTECTED]">[EMAIL PROTECTED]</a>, <a href="http://209.146.23.49/">Fine Malt Coding</a>) *@version 1.0b */ ///////////////////////////////////////////////////////////////////////////// // This program is free software; you can redistribute it and/or modify // it under the terms of the GNU Library General Public License as published // by the Free Software Foundation, version 2. (see COPYING.LIB) // // This program 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 Library General Public License for more details. // // You should have received a copy of the GNU Library General Public License // along with this program; if not, write to the Free Software Foundation // Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307 USA ///////////////////////////////////////////////////////////////////////////// package java.util; import java.io.Serializable; public class ArrayList extends AbstractList implements List, Cloneable, Serializable { private static final short INITIAL_SIZE = 4; private transient Object[] data; private int size; /** *Constructs an ArrayList with a size of 0 (allocating a small buffer for additions). */ public ArrayList() { size = 0; data = new Object[INITIAL_SIZE]; } /** *Constructs a list containing the elements of the specified collection, *in the order they are returned by the collection's iterator. * *@param collection Initial capacity. */ public ArrayList( Collection collection ) { size = collection.size(); data = new Object[size]; Iterator iter = collection.iterator(); int index = 0; while ( iter.hasNext() ) { data[index++] = iter.next(); } } /** *Constructs an ArrayList with the specified initial capacity. * *@param capacity Initial capacity. */ public ArrayList( int capacity ) { data = new Object[capacity]; } /** *Adds an Object at the specified index. Does not allow duplicates. * *@para index Index at which to insert the element. *@param obj Object to add. *@throw IndexOutOfBoundsException */ public void add( int index, Object obj ) throws IndexOutOfBoundsException { if (index > size || index < 0) throw new IndexOutOfBoundsException(); ensureCapacity(++size); System.arraycopy(data, index, data, index + 1, size - index); data[index] = obj; } /** *Adds one element to the end of this List. * *@param obj Object to add. *@return True, since duplicate elements are allowed. */ public boolean add( Object obj ) throws IndexOutOfBoundsException { add(size, obj); return true; } /** *Adds Objects to the end of this List. Does not allow duplicates. * *@param collection Collection to add. *@return True, since duplicate elements are allowed. */ public boolean addAll( Collection collection ) { return addAll(size, collection); } /** *Adds Objects to this List at the specified index. Does not allow duplicates. * *@param index Index at which to add. *@param collection Collection to add. *@return Tests to see if addition were made. */ public boolean addAll( int index, Collection collection ) throws IndexOutOfBoundsException { if (index > size || index < 0) throw new IndexOutOfBoundsException(); int collectionSize = collection.size(); if (collectionSize == 0) return false; ensureCapacity( size + collectionSize ); Iterator iter = collection.iterator(); for (int n = 0; n < collectionSize; n++) data[size++] = iter.next(); return true; } /** *Checks public bounds of List. * *@param index Index to check. */ private final void checkBounds( int index ) throws IndexOutOfBoundsException { if ( index >= size || index < 0 ) throw new IndexOutOfBoundsException(); } /** *Removes all elements from this collection. */ public void clear() { removeRange(0, size); size = 0; } public Object clone() { // TODO: Implement last. //return new ArrayList(); return null; } /** *Tests to see if an element is in the List. * *@param obj Object to seek. */ public boolean contains( Object obj ) { for (int n = 0; n < data.length; n++) { if (data[n] == obj) return true; } return false; } /** *@return Difference of two numbers. */ private final int delta( int n, int i ) { return n - i; } /** *Makes certain the size of the List is greater than or equal to *the specified size. * *@param min New minimum size. */ public void ensureCapacity( int min ) { if (min > data.length) { Object[] oldData = data; Object[] data = new Object[ oldData.length + delta(min, oldData.length) ]; System.arraycopy(oldData, 0, data, 0, oldData.length); // Cleanup old array. System.gc(); } } /** *Returns the Object at the specified index. * *@param index Index of Object to return. *@throw IndexOutOfBoundsException */ public Object get( int index ) throws IndexOutOfBoundsException { checkBounds(index); return data[index]; } /** *Returns the first index of the specified Object (comparison uses equals method). * *@param obj Object to seek. *@return Index of Object or -1 if not found. */ public int indexOf( Object obj ) { for (int n = 0; n < size; n++) if ( obj.equals(data[n]) ) return n; return -1; } /** *Tests to see if the List is empty. * *@return Whether or not the List is empty. */ public boolean isEmpty() { // Test for emptiness. if (data == null) return true; if (size == 0) return true; // Not empty. return false; } /** *Finds the last index of an element, compares elements using the equals method. * *@param obj The element to seek. *@return The index of the last occurance of the element in the list, or -1 if not found. */ public int lastIndexOf( Object obj ) { int index = -1; for (int n = 0; n < size; n++) if ( obj.equals(data[n]) ) index = n; return index; } /** *Removes an element from the List. * *@param index The index of the element to seek. *@return The index of the element to be removed. *@throw IndexOutOfBoundsException if index is out of List bounds. */ public Object remove( int index ) throws IndexOutOfBoundsException { Object obj = data[index]; int delta = size - index - 1; if (delta > 0) System.arraycopy(data, index + 1, data, index, delta); data[--size] = null; System.gc(); return obj; } /** *Sets the value of an element. * *@param index The index of to element to set. *@param obj The element to use as a value. *@return The previous element from the specified position. */ public Object set( int index, Object obj ) throws IndexOutOfBoundsException { checkBounds(index); Object old = data[index]; data[index] = obj; return old; } /** *@return The number of elements in the List. */ public int size() { return size; } /** *Returns an array representation of the List. */ public Object[] toArray() { Object[] array = new Object[size]; System.arraycopy(data, 0, array, 0, size); return array; } /** *Returns an array containing all of the elements in this list in the *correct order. The runtime type of the returned array is that of the *specified array. If the list fits in the specified array, it is returned *therein. Otherwise, a new array is allocated with the runtime type of *the specified array and the size of this list. Any extra capacity *is initialized to null. * *@param objects Reference to array which you want to fill. *@return The specified array. */ public Object[] toArray( Object[] objects ) { if (size > objects.length) objects = (Object [])java.lang.reflect.Array.newInstance ( objects.getClass().getComponentType(), size ); System.arraycopy(data, 0, objects, 0, size); for (int n = size; n < objects.length; n++) objects[n] = null; return objects; } /** *Trims the List capacity of to current size. */ public void trimToSize() { Object[] oldData = data; data = new Object[size]; System.arraycopy(oldData, 0, data, 0, size); } }
