package jif.util;
/**
 * An implementatin of List, using an array to store the
 * list elements.
 */
public class ArrayList[label L] 
    extends AbstractList[L]
    implements List[L]
{

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer.
     */
    private JifObject[L]{L}[]{L} elementData;

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     */
    private int{L} size = 0;

    /**
     * Constructs an empty list 
     *
     */
    public ArrayList() {
        this.elementData = new JifObject[L][10];
        super();
    }

    /**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure  that it can hold at least the number of elements
     * specified by the minimum capacity argument. 
     *
     * @param   minCapacity   the desired minimum capacity.
     */
    public void ensureCapacity{L}(int{L} minCapacity) {
        JifObject[L]{L}[] ed = elementData;
        if (ed != null) {
            int oldCapacity = ed.length;
            if (minCapacity > oldCapacity) {
                JifObject[L]{L}[] oldData = ed;
                int newCapacity = 1 + (int)(oldCapacity * 1.5);
                if (newCapacity < minCapacity) {
                    newCapacity = minCapacity;
                }

                try {
                    ed = new JifObject[L][newCapacity];
                }
                catch (NegativeArraySizeException imposs) {}
                
                // copy the old array to the new array
                for (int i = 0; i < size ; i++) {
                    try {
                        ed[i] = oldData[i];
                    }
                    catch (ArrayIndexOutOfBoundsException e) {}
                    catch (NullPointerException e) {}
                }
                elementData = ed;
            }
        }
    }    

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


    /**
     * Returns the element at the specified position in this list.
     *
     * @param  index index of element to return.
     * @return the element at the specified position in this list.
     * @throws    IndexOutOfBoundsException if index is out of range <tt>(index
     *                   &lt; 0 || index &gt;= size())</tt>.
     */
    public JifObject[L]{L;index} get(int index):{L;index} 
        throws (IndexOutOfBoundsException{L;index}) {
	    RangeCheck(index);

	    try {
		return elementData[index];
	    }
	    catch (NullPointerException e) {}
	    catch (ArrayIndexOutOfBoundsException e) {}
	    // unreachable
	    return null;
	}

    /**
     * Replaces the element at the specified position in this list with
     * the specified element.
     *
     * @param index index of element to replace.
     * @param element element to be stored at the specified position.
     * @return the element previously at the specified position.
     * @throws    IndexOutOfBoundsException if index out of range
     *                  <tt>(index &lt; 0 || index &gt;= size())</tt>.
     */
    public JifObject[L]{L} set{L}(int{L} index, JifObject[L]{L} element):{L} 
        throws (IndexOutOfBoundsException{L}) {
	    RangeCheck(index);

	    JifObject[L] oldValue = null;
	    try {
		oldValue = elementData[index];
		elementData[index] = element;
	    }
	    catch (NullPointerException e) {}
	    catch (ArrayIndexOutOfBoundsException e) {}
        
	    return oldValue;
	}

    /**
     * Appends the specified element to the end of this list.
     *
     * @param o element to be appended to this list.
     * @return <tt>true</tt> (as per the general contract of Collection.add).
     */
    public boolean{L} add{L}(JifObject[L]{L} o) {
        ensureCapacity(size + 1);  
        try {
            elementData[size++] = o;
        }
        catch (NullPointerException e) {}
        catch (ArrayIndexOutOfBoundsException e) {}

        return true;
    }

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted.
     * @param element element to be inserted.
     * @throws    IndexOutOfBoundsException if index is out of range
     *                  <tt>(index &lt; 0 || index &gt; size())</tt>.
     */
    public void add{L}(int{L} index, JifObject[L]{L} element):{L} 
        throws (IndexOutOfBoundsException{L}) {
	    if (index > size || index < 0)
		throw new IndexOutOfBoundsException(
						    "Index: "+index+", Size: "+size);

	    ensureCapacity(size+1);  // Increments modCount!!
	    try {
		for (int i = index; i < size /*&& i<ed.length && i < oldData.length */; i++) {
		    elementData[i+1] = elementData[i];
		}
		elementData[index] = element;
	    }
	    catch (NullPointerException e) {}
	    catch (ArrayIndexOutOfBoundsException e) {}

	    size++;
	}

    public JifObject[L]{L} remove{L}(int{L} index)
        throws (IndexOutOfBoundsException{L}) {
        RangeCheck(index);
        JifObject[L]{L}[] ed = elementData;
        
        if (ed != null) {
            try {
                JifObject[L] obj = ed[index];
                
                int i = index;
                while (i+1 < size) {
                    ed[i] = ed[i+1];
                    i++;
                }
                size--;
                return obj;
            }
            catch (ArrayIndexOutOfBoundsException e) { /*cannot happen*/ }
        }
        return null;
    }

    /**
     * Check if the given index is in range.  If not, throw an appropriate
     * runtime exception.
     */
    private void RangeCheck(int index):{L;index} 
        throws (IndexOutOfBoundsException{L;index}) {
	    if (index >= size || index < 0)
		throw new IndexOutOfBoundsException("Index: " + index + 
						    ", Size: "+size);
	}
}
