//an array list implementation
//Author: Konstantin Voevodski
//Date: 6/4/07


import java.util.*;

public class myArrayList<AnyType> implements Iterable<AnyType>
{
    private static final int DEFAULT_CAPACITY = 10;
    
    private int size;
    private AnyType[] items;
    
    public myArrayList()
    {
        clear();
    }
    
    public void clear()
    {
        size = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }
    
    public int size()
    {
        return size;
    }
    
    public boolean isEmpty()
    {
        return (size == 0);
    }
    
    public void trimToSize()
    {
        ensureCapacity(size());
    }
    
    public AnyType get(int index)
    {
        if(index < 0 || index >= size)
        {
            throw new ArrayIndexOutOfBoundsException();
        }
        return items[index];
    }
    
    public AnyType set(int index, AnyType value)
    {
        if(index < 0 || index >= size)
        {
            throw new ArrayIndexOutOfBoundsException();
        }
        AnyType old = items[index];
        items[index] = value;
        return old;
    }
    
    public void ensureCapacity(int newCapacity)
    {
        if(newCapacity < size)
        //if the new capacity is less than the old capacity, do nothing
        {
            return;
        }
        AnyType[] old = items;
        items = (AnyType[]) new Object[newCapacity];
        //create a new array to hold the items and copy them over
        for(int x = 0; x < size; x++)
        {
            items[x] = old[x];
        }
    }
    
    public void add(AnyType x)
    {
        add(size,x);
    }
    
    public void add(int index, AnyType value)
    {
        if(items.length == size)
        {
            ensureCapacity(size * 2 + 1);
        }
        for(int x = size; x > index; x--)
        //shift all elements stored in position >= index to the right
        {
            items[x] = items[x-1];
        }
        items[index] = value;
        size++;
    }
    
    public AnyType remove(int index)
    {
        if(index < 0 || index >= size)
        {
            throw new ArrayIndexOutOfBoundsException();
        }
        AnyType removedItem = items[index];
        for(int x = index; x < size - 1; x++)
        //shift all elements in position > index to the left
        {
            items[x] = items[x+1];
        }
        return removedItem;
    }
    
    public Iterator<AnyType> iterator()
    {
        return new ArrayListIterator();
    }
    
    private class ArrayListIterator implements Iterator<AnyType>
    {
        private int current = 0;
        
        public boolean hasNext()
        {
            return (current < size);
        }
        
        public AnyType next()
        {
            return(items[current++]);
        }
        
        public void remove()
        {
            myArrayList.this.remove(--current);
        }
    }
    
    
}