import CursoredList;
import DoublyLinkedNode;
import ListCursor;

/**
 * An implementation of cursored lists using linked nodes.
 * Interacts closely with NodeBasedListCursor.  A change to
 * one may significantly affect the other.
 *
 * @author Hermione Hacker
 * @author Herman Hacker
 * @author Samuel A. Rebelsky
 * @version 1.0 of April 2000
 */
public class NodeBasedCursoredList 
    implements CursoredList
{

    // +--------+----------------------------------------
    // | Fields |
    // +--------+

    /**
     * The front of the list.
     */
    protected DoublyLinkedNode front;

    /**
     * The back of the list.
     */
    protected DoublyLinkedNode back;

    /**
     * The length of the list.
     */
    protected int length;

    // +--------------+---------------------------------
    // | Constructors |
    // +--------------+

    /**
     * Build a new, empty, cursored list.
     */
    public NodeBasedCursoredList() {
        this.front = null;
        this.back = null;
        this.length = 0;
    } // NodeBasedCursoredList()

    // +------------+------------------------------------
    // | Extractors |
    // +------------+

    /** 
     * Determine if the list contains a particular cursor. 
     *       and false otherwise.
     */
    public boolean contains(ListCursor cursor) {
        // It must be a node-based list cursor.
        if (cursor instanceof NodeBasedListCursor) {
            NodeBasedListCursor tmp =
                (NodeBasedListCursor) cursor;
            // Using == rather than equals because we
            // want the same list, rather than equivalent
            // lists.  Note that this assumes a particular
            // implementation for the cursor.  If you change
            // that, you'll need to change this.
            return tmp.owner == this;
         }
         else {
            return false;
         }
    } // contains(ListCursor)

    /**
     * Get the length of the list.
     * Pre: None
     * Post: Returns the length of the list.
     */
    public int length() {
        return this.length;
    } // length()

    /**
     * Get a new cursor for the list.
     */
    public ListCursor newCursor() {
        return new NodeBasedListCursor(this, this.front);
    } // newCursor()

    /**
     * Determine the value associated with a cursor.
     */
    public Object valueAt(ListCursor cursor) {
        return ((NodeBasedListCursor) cursor).current.getContents();
     } // valueAt(ListCursor)

    // +-----------+-------------------------------------
    // | Modifiers |
    // +-----------+

    /**
     * Add a value after a cursor.
     */
    public void addAfter(Object newValue, ListCursor cursor) {
        // Safety check
        if (!this.contains(cursor))
            return;
        // Build a new node to hold the new value.
        DoublyLinkedNode newNode = 
            new DoublyLinkedNode(newValue);
        // Get the current and next node from the cursor.
        DoublyLinkedNode current =
            ((NodeBasedListCursor) cursor).current;
        DoublyLinkedNode next = current.getNext();
        // Update links appropriately
        newNode.setNext(next);
        newNode.setPrev(current);
        current.setNext(newNode);
        if (next != null) {
            next.setPrev(newNode);
        }
        else {
            // Whoops!  At the end of the list.  Update back
            this.back = newNode;
        }
    } // addAfter(Object, ListCursor)
     
    /**
     * Add a value before a cursor.
     */
    public void addBefore(Object newValue, ListCursor cursor) {
        // Safety check
        if (!this.contains(cursor))
            return;
        // Build a new node to hold the new value.
        DoublyLinkedNode newNode = 
            new DoublyLinkedNode(newValue);
        // Get the current and prev node from the cursor.
        DoublyLinkedNode current =
            ((NodeBasedListCursor) cursor).current;
        DoublyLinkedNode prev = current.getPrev();
        // Update links appropriately
        newNode.setPrev(prev);
        newNode.setNext(current);
        current.setPrev(newNode);
        if (prev != null) {
            prev.setNext(newNode);
        }
        else {
            // Whoops!  At the front of the list.
            this.front = newNode;
        }
    } // addBefore(Object, ListCursor)

    /**
     * Add a value to the end of the list.
     */
    public void addToEnd(Object newValue) {
        // Build a new node to hold the new value.
        DoublyLinkedNode newNode = 
            new DoublyLinkedNode(newValue);
        // Special case: empty list
        if (front == null) {
            this.front = newNode;
            this.back = newNode;
        }
        // Normal case: nonempty list
        else {
            // Update links
            this.back.setNext(newNode);
            newNode.setPrev(this.back);
            // Use the new node as the last node.
            this.back = newNode;
        } // nonempty list
    } // addToEnd(Object)

    /**
     * Add a value to the front of the list.
     * Pre: None
     * Post: The new value is the first value.  Cursors do
     *       not move.  The remaining values maintain their 
     *       relative order.
     */
    public void addToFront(Object newValue) {
        // Build a new node to hold the new value.
        DoublyLinkedNode newNode = 
            new DoublyLinkedNode(newValue);
        // Special case: empty list
        if (front == null) {
            this.front = newNode;
            this.back = newNode;
        } // empty list
        // Normal case: nonempty list
        else {
            // Update links
            this.front.setPrev(newNode);
            newNode.setNext(this.front);
            // Use the new node as the first node.
            this.front = newNode;
        } // nonempty list
    } // addToFront(Object)

    /**
     * Delete an element given by a cursor.
     */
    public void deleteAt(ListCursor cursor) {
        // Safety check
        if (!this.contains(cursor))
            return;
        // Get the node to delete.
        DoublyLinkedNode deleteMe =
            ((NodeBasedListCursor) cursor).current;
        DoublyLinkedNode next = deleteMe.getNext();
        DoublyLinkedNode prev = deleteMe.getPrev();
        // Update the previous node
        if (prev != null) {
            prev.setNext(next);
        }
        // Update the next node
        if (next != null) {
            next.setPrev(prev);
        }

        // Special case: Deleted front of list
        if (this.front == deleteMe) {
            // So use the next node
            this.front = next;
        }
        // Special case: Deleted end of list
        if (this.back == deleteMe) {
            // So use the previous node
            this.back = prev;
        }
        // Note: If we deleted the last node, the two previous
        // special cases will make the list empty, so we don't
        // need to worry about that special case.

        // Make sure the node no longer points to the list
        deleteMe.setPrev(null);
        deleteMe.setNext(null);

        // Clear the cursor, too
        ((NodeBasedListCursor) cursor).current = null;
    } // deleteAt(ListCursor)

    /** 
     * Replace an element at the position given by a cursor.
     */
    public void replaceAt(ListCursor cursor, Object newValue) {
        // Safety check
        if (!this.contains(cursor))
            return;
        // Get the corresponding node
        DoublyLinkedNode current =
            ((NodeBasedListCursor) cursor).current;
        // Set its value
        current.setContents(newValue);
    } // replaceAt(ListCursor, Object)

    /** 
     * Swap two elements of the list. 
     * Pre: Both cursors are in the list.
     * Post: The underlying elements are swapped.
     * Post: The cursors are still at the same places.
     */
    public void swap(ListCursor alpha, ListCursor beta) {
        // STUB
    } // swap(ListCursor, ListCursor}

} // class NodeBasedCursoredList

/**
 * Cursors for lists implemented with nodes.  Interacts closely 
 * with NodeBasedCursoredList.  A change to one may significantly 
 * affect the other.  Because this is an internal class, no one else
 * may directly use this class (although we can still return objects
 * in that class).
 *
 * @author Herman Hacker
 * @author Hermione Hacker
 * @author Herr Doktor Professor Rebelsky
 * @version 1.0 of April 2000
 */
class NodeBasedListCursor
    implements ListCursor
{
    // +--------+----------------------------------------
    // | Fields |
    // +--------+

    /**
     * The list that this cursor belongs to.
     */
    protected NodeBasedCursoredList owner;

    /**
     * The position in the list.
     */
    protected DoublyLinkedNode current;

    // +--------------+----------------------------------
    // | Constructors |
    // +--------------+

    /**
     * Make a cursor for a particular list at a particular
     * place in that list.
     */
    protected NodeBasedListCursor(NodeBasedCursoredList list,
                                  DoublyLinkedNode position) {
        this.owner = list;
        this.current = position;
    } // NodeBasedListCursor(NodeBasedCursoredList,DoublyLinkedNode)

    // +------------+------------------------------------
    // | Extractors |
    // +------------+

    /**
     * Make a copy of the cursor.  The copy is at the same
     * place in the same list.  The two cursors move 
     * independently.
     */
    public ListCursor makeCopy() {
        return new NodeBasedListCursor(this.owner, this.current);      
    } // makeCopy()

    /**
     * Determine if the cursor equals another cursor.
     */
    public boolean equals(ListCursor other) {
        if (other instanceof NodeBasedListCursor) {
            NodeBasedListCursor otherNBLC = 
                (NodeBasedListCursor) other;
            return ( (this.owner == otherNBLC.owner)
                     && (this.current == otherNBLC.current) );
        }
        else {
            return false;
        }
    } // equals(ListCursor)

    /** 
     * Determine if the cursor is still in the list. 
     */
    public boolean inList() {
        return this.current != null;
    } // inList()

    // +-----------+-------------------------------------
    // | Modifiers |
    // +-----------+

    /** 
     * Advance the cursor. 
     */
    public void advance() {
        if (this.current != null) {
            this.current = this.current.getNext();
        }
    } // advance()

    /**  
     * Move to the same position as another cursor. 
     */
    public void moveTo(ListCursor destination) {
        if (destination instanceof NodeBasedListCursor) {
            this.current = 
                ((NodeBasedListCursor) destination).current;
        }
    } // moveTo(ListCursor)

    /** 
     * Reset to the beginning of the list. 
     */
    public void reset() {
        // Warning!  Relies on knowledge of the structure of
        // NodeBasedCursoredList
        this.current = owner.front;
    } // reset()

    /** 
     * Move the cursor back one step. 
     */
    public void retreat() {
        if (this.current != null) {
            this.current = this.current.getPrev();
        }
    } // retreat()
} // interface ListCursor