/**
 * Doubly Linked Lists.
 *
 * @author Samuel A. Rebelsky
 * @author Yvonne Palm
 * @author Jonathan Wellons
 * @author Alex Leach
 */

public class YDLL
  implements MutableList
{
  // +--------+---------------------------------------------------
  // | Fields |
  // +--------+

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

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

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


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

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

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

  /**
   * Get a new iterator for this list.
   */
  public ListIterator newIterator() {
    return new YDLLIterator(this.front);
  } // newIterator()

  /**
   * Determine if the list is empty
   */
  public boolean isEmpty() {
    return (0 == length);
  } // isEmpty()

  /**
   * Update the list by adding an element to the front.
   */
  public void addToFront(Object newThingy)
  {
    if (this.isEmpty()) {
      this.front = new DoublyLinkedNode(newThingy);
      this.back = this.front;
    }
    else {
      DoublyLinkedNode newFront = 
        new DoublyLinkedNode(null,newThingy, this.front);
      this.front.prev = newFront;
      this.front = newFront;
    }
    ++this.length;
  } // addToFront(Object newThingy)

  /**
   * Update the list by adding an element to the end.
   */
  public void addToEnd(Object newThingy) {
    // Create a new cons cell.
    DoublyLinkedNode newBack = new DoublyLinkedNode(newThingy);
    // Special case: Empty list
    if (this.back == null) {
      this.back = newBack;
      this.front = newBack;
    }
    // Normal case 
    else {
      // Update the links.
      this.back.next = newBack;
      newBack.prev = this.back;
      // The back is now the newback.
      this.back = newBack;
    }
    ++this.length;
  } // addToEnd(Object)

  /**
   * Update the list by removing the first element.  Return
   * that element.
   */
  public Object removeFirst()
    throws Exception
  { 
    // Remember the first element.
    Object first = this.front.contents;
    // Update the front of the list to refer to the next element.
    this.front = this.front.next;
    // If the list becomes empty, update the back, too.
    if (null == this.front) {
      this.back = null;
    }
    // If the list is not empty
    else {
      // Forget about the previous element.
      this.front.prev = null;
    }
    // Shrink the list
    --this.length;
    // Return the thing we previously identified as first. 
    return first;  
  } // removeFirst()

  /**
   * Remove the last element.
   */
  public Object removeLast()
    throws Exception
  {
    // Remember the last value
    Object last = this.back.contents;
    // Special case: The list contains only one element.
    if (this.front == this.back) {
      this.front = null;
      this.back = null;
    }
    else {
      this.back = this.back.prev;
      this.back.next = null;
    }
    // Update the length
    --this.length;
    // Return the old last value
    return last;
  } // removeLast()

  /**
   * Get the length.
   */
  public int length()
  {
    int count = 0;
    DoublyLinkedNode temp = this.front;
    while (temp != null) {
      ++count;
      temp = temp.next;
    }
    return count; 
  } // length()


  /**
   * Get the first element (non-destructively).
   */
  public Object getFirst()
    throws Exception
  {
    return this.front.contents;
  } // getFirst()

  /**
   * Convert to a string for ease of printing.
   */
  public String toString()
  {
    if (null == this.front) {
      return "()";
    }//if
    else { 
				String result = "(" + this.front.contents;
    		DoublyLinkedNode remainder = this.front.next;
        try {
      			while (remainder != null) {
        		result = result + " " + remainder.contents;
       			remainder = remainder.next;
      			}//while
    		}//try
    		catch (Exception e) {
    		}//catch
    	return result + ")";
		}//else
   } // toString()

  /**
   * Make an independent copy of this list.
   */
  public MutableList copyMe() {
    return null;
  }
} // class LinkedList