import Node;
import rebelsky.util.NewComparable;
import rebelsky.util.EmptyListException;
import rebelsky.util.IncomparableException;

/**
 * An implementation of lists using nodes and making the use of
 * nodes explicit.  Should not be taken as a good list implementation.
 * Written for a lab in CS152.  The code is based, in part, on
 * code from Chapter 7 of "Designing Pascal Solutions: Case Studies
 * with Data Structures" by Michael J. Clancy and Marcia C. Linn.
 * Computer Science Press (W.H. Freeman), 1996.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of March 1998
 */
public class NodeList
{
  // +------------+--------------------------------------------------------
  // | Attributes |
  // +------------+

  /**
   * The front of the list (the first element in the list).  
   * Set to null when the list is empty.
   */
  Node front;

  /**
   * The end of the list.  Set to null when the list is empty.
   */
  Node back;

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


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

  /**
   * Create a new empty list.
   */
  public NodeList()
  {
    front = null;
    back = null;
    length = 0;
  } // NodeList()

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

  /**
   * Provide a printable version of the current list.
   */
  public String toString()
  {
    // Special case: empty list
    if (empty()) {
      return "";
    }
    // Normal case: nonempty list
    else {
      String str = "";	// The stringified version of the list
      Node tmp = front;	// To step through the elements of the list
      // Step through the list, adding elements separated by commas.
      // Stop when you reach the last nonempty element of the list.
      while (tmp.getNext() != null) {
        str = str + tmp.getValue().toString() + ",";
        tmp = tmp.getNext();
      } // while
      // Add the last element of the list
      str = str + tmp.getValue().toString();
      // That's it
      return str;
    } // Normal case
  } // toString()


  // +-----------+---------------------------------------------------------
  // | Accessors |
  // +-----------+

  /**
   * Determine if the list is empty.
   */
  public boolean empty()
  {
    return (front == null);
  } // empty()

  /**
   * Get the first element in the list.
   * pre: The list is nonempty.
   * post: The first element is returned.
   * post: The original list is not modified.
   */
  public Object first()
    throws EmptyListException
  {
    // Make sure the list is nonempty.
    if (empty()) {
      throw new EmptyListException();
    }
    return front.getValue();
  } // first()

  /**
   * Get the last element in the list.
   * pre: The list is nonempty.
   * post: The last element is returned.
   * post: The original list is not modified.
   */
  public Object last()
    throws EmptyListException
  {
    // Make sure the list is nonempty.
    if (empty()) {
      throw new EmptyListException();
    }
    return back.getValue();
  } // last()

  /**
   * Get the length of the current list.
   */
  public int length()
  {
    return length;
  } // length()

  /**
   * Build and return a sorted version of the current list.
   * post: The list is not modified.
   * post: A sorted version of the list is returned.
   *
   * @exception IncomparableException
   *   When two elements of the list cannot be compared
   */
  public NodeList quickSort()
    throws IncomparableException
  {
    // The final sorted list
    NodeList sorted = new NodeList();
    // The pivot.  Set to null so that Java doesn't complain that it's
    // unitialized.
    NewComparable pivot = null;
    // The smaller elements of the current list
    NodeList smaller = new NodeList();
    // And a sorted version of that list
    NodeList sorted_smaller;
    // The bigger elements of the list
    NodeList bigger = new NodeList();
    // And a sorted version of that list
    NodeList sorted_bigger;
    // The elements equal to the pivot
    NodeList pivots = new NodeList();

    // Special case: empty list
    if (empty()) {
      return sorted;	// It's empty, it must be sorted.
    }
    // Normal case: split, recurse, and join
    else {
      // Note that picking a pivot can throw an exception if the list
      // is empty.  However, we've just verified that the list is nonempty
      // so we can successfully ignore the exception (I hope).
      try {
        pivot = pickPivot();
      }
      catch (EmptyListException e) {
        // It'll never happen
        pivot = null;
      }
      partition(pivot, smaller, pivots, bigger);
      sorted_smaller = smaller.quickSort();
      sorted_bigger = bigger.quickSort();
      sorted.appendList(sorted_smaller);
      sorted.appendList(pivots);
      sorted.appendList(sorted_bigger);
      return sorted;
    } // normal case
  } // quickSort()


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

  /**
   * Add a node to the end of the list.  If the list is empty,
   * make a list consisting of a single node.
   */
  public void addToEnd(Node n)
  {
    // Handle the empty list.  Set the front and the back to null.
    if (front == null) {
      front = n;
      back = n;
      length = 1;
    } // Empty list
    // Normal list.  Simply update the back of the list.
    else {
      // Update the next reference of the old last element
      back.setNext(n);
      // Update our view of the last element
      back = back.getNext();
      length = length + 1;
    } // Normal list
  } // addToEnd(Node)

  /**
   * Add another list to the current list.  If the current list
   * is empty, simply use that other list.
   * post: this = (old version of this) + other
   */
  public void appendList(NodeList other)
  {
    // If the current list is empty, simply copy the appropriate
    // fields of the other list.
    if (empty()) {
      this.front = other.front;
      this.back = other.back;
      this.length = other.length;
    } // current list is empty

    // Otherwise (the current list is not empty), so we need to
    // update the back half of the current list.
    else {
      // The next thing after the end of the old list is the first
      // element of the newly appended list.
      this.back.setNext(other.front);
      // The end of the joined list is the end of the appended list.
      this.back = other.back;
      // The length of the joined list is the sum of the lengths of the
      // two lists.
      this.length = this.length + other.length;
    } // current list is not empty
  } // appendList(NodeList)

  /**
   * Clear the current list.
   * post: length = 0
   * post: there are not elements in the current list
   */
  public void clear()
  {
    this.front = null;
    this.back = null;
    this.length = 0;
  } // clear()
  
  /**
   * Delete the first element of the vector.
   */
  public Object deleteFirst()
    throws EmptyListException
  {
    // Special case: Empty list
    if (empty()) {
      throw new EmptyListException();
    }
    // Normal case: Nonempty list
    else {
      // Remember the current front
      Object oldfront = front.getValue();
      // Advance
      front = front.getNext();
      // Update length
      length = length - 1;
      // Return the old front
      return oldfront;
    } // normal case
  } // deleteFirst()


  // +---------------+-----------------------------------------------------
  // | Local Methods |
  // +---------------+

  /**
   * Partition the current list into three sublists.
   */
  protected void partition(NewComparable pivot, 
                           NodeList smaller, 
                           NodeList equals, 
                           NodeList bigger)
    throws IncomparableException
  {
    // A "counter" to step through the list.
    Node current = front;
    // Step through the list, putting each element in the appropriate
    // sublist.
    while (current != null) {
      // Is it equal to the pivot?
      if (pivot.equals(current.getValue())) {
        equals.addToEnd(current);
      }
      // Does it follow the pivot?
      else if (pivot.lessThan(current.getValue())) {
        bigger.addToEnd(current);
      }
      // Otherwise, it must precede the pivot
      else {
        smaller.addToEnd(current);
      }
      // Move on to the next element
      current = current.getNext();
    } // while
  } // partitition

  /**
   * Pick a pivot from the list.
   */
  protected NewComparable pickPivot()
     throws EmptyListException, IncomparableException
  {
    // Special case: empty list.  Crash and burn.
    if (front == null) {
      throw new EmptyListException();
    } // empty list
    // Normal case: nonempty list.  Use the last element.
    else {
      try {
        return (NewComparable) back.getValue();
      }
      catch (ClassCastException cce) {
        throw new IncomparableException();
      }
    } // normal case
  } // pickPivot

} // NodeList