/**
 * Linked list IList implementation.
 * @author Jeff Raab
 */
public class LinkedList implements IList {

    /** Head node in this. */
    protected Node head = new Node();
    
    /** Tail node in this. */
    protected Node tail = new Node();
    
    /** Number of objects in this. */
    protected int count = 0;
    
    /** Constructs a new linked list. */
    public LinkedList() {
        head.after = tail;
        tail.before = head;
    }
    
    /** Returns the first position in this. */
    public Position first() {
        if (isEmpty()) {
            throw new RuntimeException("List is empty");
        }
        
        return head.after;
    }
    
    /** Returns the last position in this. */
    public Position last() {
        if (isEmpty()) {
            throw new RuntimeException("List is empty");
        }
        
        return tail.before;
    }
    
    /** 
     * Returns the position in this 
     * that comes before the given position.
     * @param aPosition position for which previous position is desired
     */
    public Position before(Position aPosition) {
        if (isFirst(aPosition)) {
            throw new RuntimeException("Position is first");
        }
    
        if (notInList(aPosition)) {
            throw new RuntimeException("Position not in list");
        }
        
        Node n = (Node)aPosition;
        return n.before;
    }

    /** 
     * Returns the position in this 
     * that comes before the given position.
     * @param aPosition position for which previous position is desired
     */
    public Position after(Position aPosition) {
        if (isLast(aPosition)) {
            throw new RuntimeException("Position is last");
        }
    
        if (notInList(aPosition)) {
            throw new RuntimeException("Position not in list");
        }
        
        Node n = (Node)aPosition;
        return n.after;
    }
    
    /**
     * Returns whether or not the given position is first in this.
     * @param aPosition position to test
     */
    public boolean isFirst(Position aPosition) {
        if (isEmpty()) {
            return false;
        }
        
        return (head.after == aPosition);
    }

    /**
     * Returns whether or not the given position is last in this.
     * @param aPosition position to test
     */
    public boolean isLast(Position aPosition) {
        if (isEmpty()) {
            return false;
        }
        
        return (tail.before == aPosition);
    }

    /**
     * Inserts the given object at the beginning of this,
     * increasing the size of this by 1.
     * @param anObject object to insert
     */
    public IList insertFirst(Object anObject) {
        Node n = new Node(anObject, head, head.after);

        head.after = n;
        n.after.before = n;
        
        count++;
        
        return this;
    }
    
    /**
     * Inserts the given object at the end of this,
     * increasing the size of this by 1.
     * @param anObject object to insert
     */
    public IList insertLast(Object anObject) {
        Node n = new Node(anObject, tail.before, tail);

        tail.before = n;
        n.before.after = n;
        
        count++;
        
        return this;
    }
    
    /**
     * Inserts the given object before the given position in this, 
     * increasing the size of this by 1.
     * @param aPosition position to insert before
     * @param anObject object to insert
     */
    public IList insertBefore(Position aPosition, Object anObject) {
        if (notInList(aPosition)) {
            throw new RuntimeException("Position not in list");
        }
        
        if (isFirst(aPosition)) {
            return insertFirst(anObject);
        }
        
        Node afterN = (Node)aPosition;

        Node n = new Node(anObject, afterN.before, afterN);
        
        afterN.before = n;
        n.before.after = n;
        
        count++;
        
        return this;
    }

    /**
     * Inserts the given object after the given position in this, 
     * increasing the size of this by 1.
     * @param aPosition position to insert before
     * @param anObject object to insert
     */
    public IList insertAfter(Position aPosition, Object anObject) {
        if (notInList(aPosition)) {
            throw new RuntimeException("Position not in list");
        }
        
        if (isLast(aPosition)) {
            return insertLast(anObject);
        }
        
        Node beforeN = (Node)aPosition;

        Node n = new Node(anObject, beforeN, beforeN.after);
        
        beforeN.after = n;
        n.after.before = n;
        
        count++;
        
        return this;
    }
    
    /** Removes and returns the first element of this. */
    public IList removeFirst() {
        if (isEmpty()) {
            throw new RuntimeException("List is empty");
        }
        
        head.after = head.after.after;
        head.after.before = head;
        
        count--;
        
        return this;
    }

    /** Removes and returns the last element of this. */
    public IList removeLast() {
        if (isEmpty()) {
            throw new RuntimeException("List is empty");
        }
        
        tail.before = tail.before.before;
        tail.before.after = tail;
        
        count--;
        
        return this;
    }
    
    /** 
     * Removes the given position from this and returns its element.
     * @param aPosition position to remove
     */
    public IList remove(Position aPosition) {
        if (notInList(aPosition)) {
            throw new RuntimeException("Position not in list");
        }
        
        Node n = (Node)aPosition;
        
        n.before.after = n.after;
        n.after.before = n.before;
        
        count--;
        
        return this;
    }
    
    /**
     * Returns the element in the given position of this
     * and replaces it with the given object.
     * @param aPosition position of element to replace
     * @param anObject object to store in the given position
     */
    public Object replaceElement(Position aPosition, Object anObject) {
        if (notInList(aPosition)) {
            throw new RuntimeException("Position not in list");
        }
        
        Node n = (Node)aPosition;

        Object removed = n.element;
        n.element = anObject;
        return removed;
    }

    /** Returns the size of this. */
    public int size() {
        return count;
    }
    
    /** Returns whether or not this is empty. */
    public boolean isEmpty() {
        return (size() == 0);
    }
    
    /** Returns whether or not the given position is not in this. */
    protected boolean notInList(Position aPosition) {
        if (isEmpty()) {
            return true;
        }
        
        Node n = head.after;
        while (n != tail) {
            if (n == aPosition) {
                return false;
            }
            
            n = n.after;
        }
        
        return true;
    }
}