import rebelsky.util.List;
import rebelsky.util.BinaryNode;
import rebelsky.util.ListException;
import rebelsky.util.EmptyListException;
import rebelsky.util.Unimplemented;

/**
 * A simple implementation of linked lists.  Currently implements 
 * singly linked lists (and therefore only a portion of the many
 * possible list functions).  This implementation does ensure that
 * the cursor is always somewhere in the list.  Hence,
 * the cursor-related functions are less likely to throw exceptions.
 * <p>
 * Copyright (c) 1998 Samuel A. Rebelsky.  All rights reserved.
 *
 * @version 1.1 of March 1998
 * @author Samuel A. Rebelsky
 */
public class LinkedList
  implements List 
{

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

  /**
   * The number of elements in the list.
   */
  protected int length;

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

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

  /**
   * The "current" element in the list.
   */
  protected BinaryNode cursor;


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

  /**
   * Create a new empty linked list.
   */
  public void LinkedList() {
    clear();
  } // LinkedList()


  // +-----------------------+-----------------------------------
  // | Information retrieval |
  // +-----------------------+

  /**
   * Get the element referred to by the cursor.
   * <br><strong>Precondition:</strong> 
   *   The list is nonempty.
   * <br><strong>Postcondition:</strong> 
   *   The first element in the list is returned.
   * <br><strong>Postcondition:</strong>
   *   The list is not modified.
   * <br><strong>Postcondition:</strong>
   *   The cursor is not affected.
   *
   * @exception EmptyListException
   *   if the list is empty.
   */
  public Object getCurrent()
    throws EmptyListException
  {
    if (empty()) {
      throw new EmptyListException();
    }
    return cursor.getContents();
  } // getCurrent()


  /**
   * Get the first element in the list.
   * <br><strong>Precondition:</strong> 
   *   The list is nonempty.
   * <br><strong>Postcondition:</strong> 
   *   The first element in the list is returned.
   * <br><strong>Postcondition:</strong>
   *   The list is not modified.
   *
   * @exception EmptyListException
   *   if the list is empty.
   */
  public Object getFirst()
    throws EmptyListException
  {
    if (empty()) {
      throw new EmptyListException();
    }
    return front.getContents();
  } // getFirst()

  /**
   * Get the last element in the list.
   * <br><strong>Precondition:</strong>
   *   The list is nonempty.
   * <br><strong>Postcondition:</strong>
   *   The last element in the list is returned.
   * <br><strong>Postcondition:</strong>
   *   The list is not modified.
   *
   * @exception EmptyListException
   *   if the list is empty.
   */
  public Object getLast()
    throws EmptyListException
  {
    if (empty()) {
      throw new EmptyListException();
    }
    return back.getContents();
  } // getLast()

  /**
   * Determine whether the list is empty.
   * <br><strong>Precondition:</strong> 
   *   (none)
   * <br><strong>Postcondition:</strong>
   *   The list is unaffected.
   */
  public boolean empty()
  {
    // The list is empty if the front does not refer to an element.
    return (front == null);
  } // empty()

  /**
   * Determine the number of elements in the list.
   * <br><strong>Precondition:</strong> 
   *   (none)
   * <br><strong>Postcondition:</strong>
   *   The list is uanffected.
   * <br><strong>Postcondition:</strong>
   *   The number of elements in the list is returned.
   */
  public int length()
  {
    return length;
  } // length()


  // +--------------------+--------------------------------------
  // | Inserting elements |
  // +--------------------+

  /**
   * Add an element at the front of the list.  If the list is
   * empty, creates a one-element list.
   * <br><strong>Precondition:</strong> 
   *   (none)
   * <br><strong>Postcondition:</strong>
   *   The element is now at the front of the list.
   * <br><strong>Postcondition:</strong>
   *   The list increases in length by one.
   * <br><strong>Postcondition:</strong>
   *   If the list was not previously empty, the cursor is
   *   unchanged (if it previously referred to the front of the list,
   *   it now refers to the second element of the list).
   * <br><strong>Postcondition:</strong>
   *   If the list was previously empty, the list now has one element  
   *   which is front, back, and cursor.
   */
  public void addAtFront(Object elt)
  {
    // Handle the empty list
    if (empty()) {
      newList(elt);
    }
    // Handle nonempty lists
    else {
      // Create the new front with the apprpropriate contents and
      // with the old front as the next element.
      BinaryNode new_front = new BinaryNode(elt, front);
      front = new_front;
      // Update the length
      length = length + 1;
    }
  } // addAtFront(Object)

  /**
   * Add an element at the end of the list.  If the list is
   * empty, creates a one-element list.
   * <br><strong>Precondition:</strong> 
   *   (none)
   * <br><strong>Postcondition:</strong>
   *   The element is now at the end of the list.
   * <br><strong>Postcondition:</strong>
   *   The list increases in length by one.
   * <br><strong>Postcondition:</strong>
   *   If the list was not previously empty, the cursor is
   *   unchanged (if it previously referred to the end of the list,
   *   it now refers to the penulitimate element of the list).
   * <br><strong>Postcondition:</strong>
   *   If the list was previously empty, the list now has one element  
   *   which is front, back, and cursor.
   */
  public void addAtEnd(Object elt)
  {
    // Handle the empty list
    if (empty()) {
      newList(elt);
    }
    // Handle nonempty lists
    else {
      // Create the new front with the apprpropriate contents and
      // no subsequent element.
      BinaryNode new_back = new BinaryNode(elt);
      back.setNext(new_back);
      back = new_back;
      // Update the length
      length = length + 1;
    }
  } // addAtEnd(Object)

  /**
   * Add an element before the cursor.
   * <br><strong>Precondition:</strong> 
   *   The list is nonempty.
   * <br><strong>Postcondition:</strong>
   *   The element is inserted before the cursor.
   * <br><strong>Postcondition:</strong>
   *   The list increases in length by one.
   * <br><strong>Postcondition:</strong>
   *   The cursor has not changed.
   *
   * @exception EmptyListException
   *   if the list is empty.
   * @exception ListException
   *   if some implementation-related error occurs.
   * @exception Unimplemented
   *   until this implementation supports this method.
   */
  public void addBeforeCurrent(Object elt)
    throws EmptyListException, ListException, Unimplemented
  {
    throw new Unimplemented();
  } // addBeforeCurrent(Object)

  /**
   * Add an element after the cursor.
   * <br><strong>Precondition:</strong> 
   *   The list is nonempty.
   * <br><strong>Postcondition:</strong>
   *   The element is inserted after the cursor .
   * <br><strong>Postcondition:</strong>
   *   The list increases in length by one.
   * <br><strong>Postcondition:</strong>
   *   The cursor has not moved.
   *
   * @exception EmptyListException
   *   if the list is empty.
   */
  public void addAfterCurrent(Object elt)
    throws EmptyListException
  {
    // Handle the empty list
    if (empty()) {
      throw new EmptyListException();
    }
    // Handle nonempty lists
    else {
      // Create a new node whose contents is the given element and
      // whose subsequent element is the old successor to the cursor
      // element.
      BinaryNode new_elt = new BinaryNode(elt, cursor.getNext());
      // Update the successor of the cursor
      cursor.setNext(new_elt);
      // Update the length
      length = length + 1;
      // Handle the special case of the cursor being the last element (in
      // which case the newly added element is now the last element).  
      if (cursor == back) { 
        back = new_elt; 
      } // if (cursor == back) 
    } // nonempty list 
  } // addAfterCurrent(Object)


  // +-------------------+---------------------------------------
  // | Deleting elements |
  // +-------------------+
 
  /**
   * Delete all the elements in the list.
   * <br><strong>Precondition:</strong>
   *   (none)
   * <br><strong>Postcondition:</strong>
   *   The list is empty (contains no elements).
   */
  public void clear()
  {
    length = 0;
    front = null;
    back = null;
    cursor = null;
  } // clear()
 
  /**
   * Delete the element referred to by the cursor.
   * <br><strong>Precondition:</strong> 
   *   The list is nonempty.
   * <br><strong>Postcondition:</strong>
   *   The element referred to by the cursor is deleted.
   * <br><strong>Postcondition:</strong>
   *   The list decreases in length by one.
   * <br><strong>Postcondition:</strong>
   *   If the cursor was at the end of the list, it is now at the front
   *   of the list.  Otherwise, it has advanced to the next element of
   *   the list.
   *
   * @return the deleted element.
   * @exception EmptyListException
   *   if the list is empty.
   * @exception ListException
   *   if some implementation-related error occurs.
   * @exception Unimplemented
   *   until this implementation supports this method.
   */
  public Object deleteCurrent()
    throws EmptyListException, ListException, Unimplemented
  {
    throw new Unimplemented();
  } // deleteCurrent()

  /**
   * Delete the first element of the list.
   * <br><strong>Precondition:</strong> 
   *   The list is nonempty.
   * <br><strong>Postcondition:</strong>
   *   The first element is deleted.
   * <br><strong>Postcondition:</strong>
   *   The list decreases in length by one.
   * <br><strong>Postcondition:</strong>
   *   If the cursor was at the front of the list, it is now at the
   *   new front of the list.  Otherwise, it is unchanged.
   *
   * @return the deleted element
   * @exception EmptyListException
   *   if the list is empty.
   */
  public Object deleteFirst()
    throws EmptyListException
  {
    // Handle the empty list
    if (empty()) {
      throw new EmptyListException();
    }
    // Grab the old front
    BinaryNode tmp = front;
    // Deal with the cursor being at the front of the list
    if (cursor == front) {
      cursor = front.getNext();
    }
    // Advance the front of the list
    front = front.getNext();
    // And update the length
    length = length - 1;
    // Return the contents of the old front.
    return tmp.getContents();
  } // deleteFirst()

  /**
   * Delete the last element of the list.
   * <br><strong>Precondition:</strong> 
   *   The list is nonempty.
   * <br><strong>Postcondition:</strong>
   *   The last element is deleted.
   * <br><strong>Postcondition:</strong>
   *   The list decreases in length by one.
   * <br><strong>Postcondition:</strong>
   *   If the cursor was at the end of the list, it is now at the new
   *   last element.  Otherwise, it is unchanged.
   *
   * @return the deleted element.
   * @exception EmptyListException
   *   if the list is empty.
   * @exception ListException
   *   if some implementation-related error occurs.
   * @exception Unimplemented
   *   until this implementation supports this method.
   */
  public Object deleteLast()
    throws EmptyListException, ListException, Unimplemented
  {
    throw new Unimplemented();
  } // deleteLast()


  // +------------------+----------------------------------------
  // | Standard Methods |
  // +------------------+

  /**
   * Develop a string version of the list.
   */
  public String toString()
  {
    // Deal with the empty list.
    if (empty()) {
      return "()";
    }
    // Nonempty lists:  Start with open paren, follow with elements
    // separated by spaces
    String str = "(";
    BinaryNode tmp = front;
    // Keep going until we reach the end of the list
    while (tmp != back) {
      str = str + tmp.getContents().toString() + " ";
      tmp = tmp.getNext();
    } // while
    // Add the last element
    str = str + tmp.getContents() + ")";
    // That's it
    return str;
  } // toString()


  // +-------------------------+---------------------------------
  // | Manipulating the cursor |
  // +-------------------------+

  /**
   * Reset the cursor to the beginning of the list.
   * <br><strong>Precondition:</strong>
   *   The list is nonempty.
   * <br><strong>Postcondition:</strong>
   *   The cursor is at the beginning of the list.
   * <br><strong>Postcondition:</strong>
   *   The list is not modified.
   *
   * @exception EmptyListException
   *   if the list is empty.
   */
  public void reset()
    throws EmptyListException
  {
    if (empty()) {
      throw new EmptyListException();
    }
    cursor = front;
  } // reset()
  
  /**
   * Advance the cursor. 
   * <br><strong>Precondition:</strong>
   *   The list is nonempty.
   * <br><strong>Precondition:</strong>
   *   The cursor is not at the end of the list.
   * <br><strong>Postcondition:</strong>
   *   The cursor is advanced to the next element.
   * <br><strong>Postcondition:</strong>
   *   The list is not modified.
   *
   * @exception EmptyListException
   *   if the list is empty.
   * @exception ListException
   *   If the cursor is at the end of the list.
   */
  public void advance()
    throws EmptyListException, ListException
  {
    if (empty()) {
      throw new EmptyListException();
    }
    if (cursor.getNext() == null) {
      throw new ListException("Cannot advance beyond end of list");
    }
    cursor = cursor.getNext();
  } // advance()

  /**
   * Move the cursor backwards one position.
   * <br><strong>Precondition:</strong>
   *   The list is nonempty.
   * <br><strong>Precondition:</strong>
   *   The cursor is not at the beginning of the list.
   * <br><strong>Postcondition:</strong>
   *   The cursor is now at the previous element.
   * <br><strong>Postcondition:</strong>
   *   The list is not modified.
   *
   * @exception EmptyListException
   *   if the list is empty.
   * @exception ListException
   *   if some implementation-related error occurs or the cursor
   *   is at the beginning of the list.
   * @exception Unimplemented
   *   until this implementation supports this method.
   */
  public void backup()
    throws EmptyListException, ListException, Unimplemented
  {
    throw new Unimplemented();
  } // backup()

  /**
   * Advance the cursor to the first element equal to obj after (or
   * including) the cursor.  If the cursor is not equal to obj and there
   * are no subsequent instances of obj, then return false and leave
   * the cursor where it was.
   * <br><strong>Precondition:</strong> 
   *   The list is nonempty.
   * <br><strong>Postcondition:</strong>
   *   If there is an appropriate element in the list (equal to
   *   obj and after or including the cursor) then the cursor
   *   is at the first such object.
   *
   * @return true if an element is found; false otherwise.
   * @exception EmptyListException
   *   if the list is empty.
   * @exception ListException
   *   if some implementation-related error occurs.
   * @exception Unimplemented
   *   until this implementation supports this method.
   */
  public boolean find(Object obj)
    throws EmptyListException, ListException, Unimplemented
  {
    throw new Unimplemented();
  } // find(Object)


  // +-----------------+-----------------------------------------
  // | Local Utilities |
  // +-----------------+

  /**
   * Make a one-element list.  Since I control who can call this, I don't
   * need to worry as much about exceptions.
   * <br><strong>Precondition:</strong>
   *   The list is empty.
   * <br><strong>Postcondition:</strong>
   *   The list contains exactly one element.
   */
  protected void newList(Object elt) 
  {
    // Create a new node
    BinaryNode new_node = new BinaryNode(elt);
    // Make everything refer to it
    front = new_node;
    back = new_node;
    cursor = new_node;
    // Set the length
    length = 1;
  } // newList(Object)

} // List