List631.java

/**
 * A subset of the Java Collections Framework List interface.
 *
 * @author Jim Glenn
 * @version 0.3 1/31/2007 removed Collection202 superclass
 * @version 0.2 4/10/2006 added indexed add and remove
 * @version 0.1 11/10/2004
 */

public interface List631
{
    /**
     * Adds the given item o this list.  Returns true if successful,
     * or false if there was some reasont he object could not be added.
     *
     * @param o the object to add
     * @return true iff the object was added
     */

    public boolean add(Object o);

    /**
     * Removes all elements from this list.
     */

    public void clear();

    /**
     * Determines if this list contains the given object.
     *
     * @param o an object
     * @return true iff this list contains that object
     */

    public boolean contains(Object o);

    /**
     * Removes the first ocurrence of the given object from this list.
     * Returns false if the object was not on this list, true
     * otherwise.
     *
     * @param o an object
     * @return true iff that object was on this list
     */

    public boolean remove(Object o);

    /**
     * Returns the number of items on this list.
     *
     * @return the size of this list
     */

    public int size();

    /**
     * Returns the object at the given position in this list.  The first
     * item on the list is at position 0.
     *
     * @param index a position in this list
     * @return the object at that position
     */

    public Object get(int index);

    /**
     * Removes the item at the given index in this list.  All of the
     * items after the given index will be moved back one index.  The
     * item removed is returned.
     *
     * @param index the index of the item to remove
     * @return the item removed
     * @throws IndexOutOfBoundsException if the index is out of range
     */

    public Object remove(int index);

    /**
     * Adds the given item at the given index in this list.  All of the
     * items after the given index will be moved up one index to make
     * room for the new element.
     *
     * @param index the index of the item to remove
     * @param o the object to add
     * @return the item removed
     * @throws IndexOutOfBoundsException if the index is out of range
     */

    public void add(int index, Object o);
}

ArrayList631.java

import java.util.*;

/**
 * A list implemented using an array to hold the elements.
 *
 * @author Jim Glenn
 * @version 0.1 11/10/2004
 */

public class ArrayList631 implements List631
{
    /**
     * The array that holds the elements in this list.  The
     * first item in the list is at index 0 in this array.
     */

    private Object[] elements;
    
    /**
     * The number of items in this list.  Note that this is not necessarily
     * the same as the size of the <CODE>elements</CODE> array since
     * the locations in the array are not necessarily all used.
     */

    private int numElements;

    /**
     * Creates an empty list.
     */

    public ArrayList631()
    {
	clear();
    }

    /**
     * Returns the object at the given position in this list.  The first
     * item on the list is at position 0.
     *
     * @param index a position in this list
     * @return the object at that position
     */

    public Object get(int index)
    {
	return elements[index];
    }

    /**
     * Returns the number of items on this list.
     *
     * @return the size of this list
     */

    public int size()
    {
	return numElements;
    }

    /**
     * Removes all elements from this list.
     */

    public void clear()
    {
	numElements = 0;
	elements = new Object[1];
    }

    /**
     * Adds the given item o this list.  
     *
     * @param o the object to add
     * @return true
     */

    public boolean add(Object o)
    {
	if (numElements == elements.length)
	    {
		// array is full; resize

		Object[] bigger = new Object[numElements * 2];
		System.arraycopy(elements, 0, bigger, 0, numElements);
		elements = bigger;
	    }

	elements[numElements] = o;
	numElements++;

	return true;
    }

    /**
     * Adds the given item at the given index in this list.  All of the
     * items after the given index will be moved up one index to make
     * room for the new element.
     *
     * @param index the index of the item to remove
     * @param o the object to add
     * @return the item removed
     * @throws IndexOutOfBoundsException if the index is out of range
     */

    public void add(int index, Object o)
    {
	// check that index is valid

	if (index < 0 || index > size())
	    throw new IndexOutOfBoundsException("" + index);

	// check if array is full

	if (numElements == elements.length)
	    {
		// make a bigger array

		Object[] bigger = new Object[numElements * 2];
		
		// copy elements before the position at which to add

		System.arraycopy(elements, 0, bigger, 0, index);

		// copy elements after the position at which to add

		System.arraycopy(elements, index, bigger, index + 1, numElements - index);

		// use bigger array

		elements = bigger;
	    }
	else
	    {
		// copy all elements after the position at which to add over 1

		for (int copyFrom = numElements -1; copyFrom >= index; copyFrom--)
		    elements[copyFrom + 1] = elements[copyFrom];
	    }

	// add the new element

	elements[index] = o;
	numElements++;
    }
   

    /**
     * Determines if this list contains the given object.
     *
     * @param o an object
     * @return true iff this list contains that object
     */

    public boolean contains(Object o)
    {
	return (find(o) != -1);
    }

    /**
     * Returns the index of the first occurrence of the given object
     * on this list, or -1 if the item is not on this list.
     *
     * @param o an object
     * @return the index in this list of the first occurrence of that object
     */
    
    private int find(Object o)
    {
	int i = 0;
	while (i < numElements && !elements[i].equals(o))
	    i++;

	if (i < numElements)
	    return i;
	else
	    return -1;
    }

    /**
     * Removes the first ocurrence of the given object from this list.
     * Returns false if the object was not on this list, true
     * otherwise.
     *
     * @param o an object
     * @return true iff that object was on this list
     */

    public boolean remove(Object o)
    {
	// find where o is

	int removeIndex = find(o);

	// remove item at that position

	if (removeIndex != -1)
	    {
		remove(removeIndex);

		return true;
	    }


	return false;
    }

    /**
     * Removes the item at the given index in this list.  All of the
     * items after the given index will be moved back one index.  The
     * item removed is returned.
     *
     * @param index the index of the item to remove
     * @return the item removed
     * @throws IndexOutOfBoundsException if the index is out of range
     */

    public Object remove(int index)
    {
	// check that index is valid

	if (index < 0 || index >= numElements)
	    throw new IndexOutOfBoundsException("" + index);

	// save removed object

	Object removed = elements[index];

	// copy elements back one space to fill the hole left by removed elt

	for (int copyTo = index; copyTo < numElements - 1; copyTo++)
	    elements[copyTo] = elements[copyTo + 1];

	numElements--;

	return removed;
    }
}