/*
 * This class implements a generic linked list.  It operates on Objects,
 * and can therefore be used with any object type.  However, when get()
 * is used, the object must be cast back to the original type.
 */

public class LinkedList {
    // The head of the list
    private Node head;

    // The number of elements in the list
    private int count;

    /* 
     * Constructor
     * Initializes the list to be empty
     */
    public LinkedList() {
	head = null;
	count = 0;
    }

    /*
     * insert()
     * inserts item at the specified index in the list
     * throws ArrayIndexOutOfBoundsException if the index is too large
     */
    public void insert(int index, Object item)
	throws ArrayIndexOutOfBoundsException {

	// Check for a valid index
	if(index < 0 || index > count) 
	    throw(new ArrayIndexOutOfBoundsException("Bad insert (bad index(" + index + "), max(" + count + "))!"));

	// Case 1: index == 0
	// Insert at the head of the list
	if(index == 0) {
	    Node newNode = new Node(item);
	    newNode.setNext(head);
	    head = newNode;
	    count++;
	    return;
	}

	// Case 2: index != 0
	// Insert somewhere else in the list
	Node previousNode = find(index);
	Node newNode = new Node(item);
	newNode.setNext(previousNode.getNext());
	previousNode.setNext(newNode);
	count++;
    }

    /*
     * delete()
     * deletes the item at the specified index in the list
     * throws ArrayIndexOutOfBoundsException if the index is too large
     */
    public void delete(int index)
	throws ArrayIndexOutOfBoundsException {

	// Check for a valid index
	if(index < 0 || index >= count) 
	    throw(new ArrayIndexOutOfBoundsException("Bad delete (bad index(" + index + "), max(" + (count-1) + "))!"));

	// Case 1: index == 0
	// Delete the head of the list
	if(index == 0) {
	    head = head.getNext();
	    count--;
	    return;
	}

	// Case 2: index != 0
	// Delete something in the middle of the list
	Node previousNode = find(index);
	previousNode.setNext(previousNode.getNext().getNext());
	count--;
    }

    /*
     * get()
     * gets the item at the specified index in the list, without deleting it.
     * throws ArrayIndexOutOfBoundsException if the index is too large
     */
    public Object get(int index)
	throws ArrayIndexOutOfBoundsException {
	
	// Check for a valid index
	if(index < 0 || index >= count) 
	    throw(new ArrayIndexOutOfBoundsException("Bad get (bad index(" + index + "), max(" + (count-1) + "))!"));

	// Case 1: index == 0
	// Get the head of the list
	if(index == 0) {
	    return head.getItem();
	}

	// Case 2: index != 0
	// Get something from the middle of the list
	Node previousNode = find(index);
	return((previousNode.getNext()).getItem());
    }

    /*
     * find()
     * Returns the node *before* the desired one.  This is better 
     * than returning the desired node, because we want to use this
     * when we do a delete, and for insert and delete we need the 
     * node before the desired node.
     *
     * An alternative would be to write find() and findPrevious(),
     * where find() returns the desired node and findPrevious()
     * returns the node before the desired node.
     */
    private Node find(int index) {
	int i;
	Node currentNode;

	// Traverse the links until we get to the
	// one just before the desired one. 
	currentNode = head;
	for(i = 0; i < count; i++) {

	    if(i == index-1)
		return(currentNode);

	    // Oops, bad index
	    if(currentNode == null)
		return(null);

	    currentNode = currentNode.getNext();
	}
	
	/*
	 * We should never reach this statement, but the compiler isn't
	 * smart enough to realize that one of the previous two return
	 * statements must be executed, so it thinks there is a way 
	 * through this method that will fail to hit a return statement, 
	 * so...
	 */
	return null;
    }

    /*
     * removeAll()
     * empties the list
     */
    public void removeAll() {
	head = null;
	count = 0;
    }

    /*
     * length()
     * returns the length of the list
     */
    public int length() {
	return count;
    }
}