
/*
 * Name: Jordan Davis
 * Date: 11.1.11 
 */

import java.util.NoSuchElementException;
import java.util.Scanner;

public class ArrayList<E> 
{
    private E data[];  //this is where all the data is stored
    private int size = 0; //this keeps track of the current number of items stored
    private final static int DEFAULT_CAPACITY = 5;  //default capacity for an ArrayList 
    												//if a capacity is not specified or invalid

    //default constructor - creates a new ArrayList with a specified capacity
    public ArrayList()
    {
    	data = (E[])(new Object[DEFAULT_CAPACITY]);
    }
    
    //constructor - creates a new ArrayList with a specified capacity
    public ArrayList(int capacity)
    {
    	if (capacity > 0)
    		data = (E[])(new Object[capacity]);
    	else 
    		data = (E[])(new Object[DEFAULT_CAPACITY]);
    }

    //get an item at a specific index in this ArrayList
    public E get(int index)
    {
    	if (index >= 0 && index < size)
    		return data[index];
    	else 
    		throw new NoSuchElementException();
    }

    //replace an existing item at a specific index in this ArrayList with a new item 
    public void set(E o, int index)
    {
        if (index >= 0 && index < size)
        {
            data[index] = o;
        }
        else 
        {
        	throw new NoSuchElementException();
        }
    }
    
    //add an item to the end of this ArrayList
    public void add(E o)
    {
    	//if the old array is full
        if (size == data.length) 
        {
        	//make a new array with twice the capacity of the old one
            E newData[] = (E[])(new Object[2 * data.length]);
            
            //copy all the items from the old array to the new array
            for (int i = 0; i < data.length; i++) 
            {
                newData[i] = data[i];
            }
            
            //assign the old array reference to point to the new array
            data = newData;
        }

        //add the item to the end of the array
        data[size] = o;
        //increment size, one item is added
        size++;
    }
    
    //remove an item at a specific index from this ArrayList
    public void remove(int index)
    {
    	if (index >= 0 && index < size)
    	{
    		//decrement size, one item is removed
	    	size--;
	    	
	    	//shift all items to the left by one index
	    	for (int i = index; i < size; i++)
	    	{
	    		data[i] = data[i + 1];
	    	}
	    	
	    	//remove the duplicate element
	    	data[size] = null;
	    }
    	else 
    	{
    		throw new NoSuchElementException();
    	}
    }
    
    //clears all items from this ArrayList
    public void clear()
    {
    	//clears array and defaults the capacity to 3
    	data = (E[]) new Object[3];
    	//all items have been removed
    	size = 0;
    }
    
    //returns the first index in this ArrayList that contains an item equivalent to the specified item
    public int indexOf(E o)
    {
    	//for each item in the array
    	for (int i = 0; i < size; i++)
    	{
    		//if the current item is equal to the specified item then return the current index
    		if (data[i].equals(o))
    			return i;
    	}
    	
    	//if none of the items in the array are equal to the specified item then return -1
    	return -1;
    }
    
    //remove an item at a specific index from this ArrayList and trim the capacity
    public void removeAndTrim(int index)
    {
    	if (index >= 0 && index < size)
    	{
    		//decrement size, one item is removed
    		size--;
    		
    		//shift all items to the left by one index
    		for (int i = index; i < size; i++)
    		{
    			data[i] = data[i + 1];
    		}
    		
    		//delete the duplicate item
    		data[size] = null;
    		
    		//if the ArrayList size is less than half the capacity
    		if (size < data.length / 2)
    		{
    			//create a new array with half the capacity of the old array
    			E newData[] = (E[]) new Object[size + 1];
    			
    			//copy all items from the old array to the new array
    			for (int i = 0; i < size; i++)
    			{
    				newData[i] = data[i];
    			}
    			
    			//assign the old array reference to point to the new array
    			data = newData;
    		}
    	}
    	else
    	{
    		throw new NoSuchElementException();
    	}
    	
    }
    
    //add an item to the front of this ArrayList
    public void addToFront(E o)
    {
    	//if the array is full
    	if (size == data.length)
    	{
    		//make a new array with twice the capacity of the old one
    		E newData[] = (E[]) new Object[2 * data.length];
    		
    		//copy all items from the old array to the new array
    		for (int i = 0; i < data.length; i++)
    		{
    			newData[i] = data[i];
    		}
    		
    		//assign the old array reference to point to the new array
    		data = newData;
    	}
    	
    	//shift all items to the right by one index
    	for (int i = size; i > 0; i--)
    	{
    		data[i] = data[i - 1];
    	}
    	
    	//add the specified item to the first index of the array
    	data[0] = o;
    	//increment size, one item has been added
    	size++;
    }
    
    //remove all items from this ArrayList that are the same as the specified item
    public void removeAll(E o)
    {
    	//first index to remove from
    	int index = indexOf(o);
    	
    	//while the array contains the specified item
    	while (index != -1)
    	{	
    		//remove that specified item at the first index it appears at
    		remove(index);
    		
    		//next index to remove from
    		index = indexOf(o);
    	}
    }
    
    //accessor - get current size of this ArrayList
    public int getSize()
    {
    	return size;
    }
    
    //accessor - get current capacity of this ArrayList
    public int getCapacity()
    {
    	return data.length;
    }
    
    public boolean equals(Object o)
    {
    	if (o instanceof ArrayList)
    	{
	    	ArrayList al = (ArrayList) o;
	    	
	    	//if the size and capacity of the two ArrayLists are not the same then they are not equal
	    	if (size != al.getSize() || data.length != al.getCapacity())
	    		return false;
	    	
	    	//for each item at the same index from each ArrayList
	    	for (int i = 0; i < size; i++)
	    	{
	    		//if the pair of items at a certain index is are not equal then return false
	    		if (!data[i].equals(al.get(i)))
	    			return false;
	    	}
	    	
	    	return true;
    	}	
    	else
    	{
    		return false;
    	}
    }
    
    //change data.length to size
    public String toString()
    {
    	String s = "";
    	
    	for (int i = 0; i < size; i++)
    		s += data[i] + "\n";
    	return s;
    }
}
