/**
 * Queues implemented with linked cons cells.
 *
 * @author Samuel A. Rebelsky
 * @author Yvonne Palm
 */
public class LinkedQueue
  implements Queue
{
  // +--------+---------------------------------------------------
  // | Fields |
  // +--------+

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

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

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

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

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

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

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

  /**
   * Add something to the queue.
   */
  public void add(Object newThingy) {
    // Create a new cons cell.
    ConsCell newBack = new ConsCell(newThingy, null);
    // Special case: Empty list
    if (this.back == null) {
      this.back = newBack;
      this.front = newBack;
    }
    // Normal case 
    else {
      // Update the cdr of this.back
      this.back.myCdr = newBack;
      // Update this.back
      this.back = newBack;
    }
    ++this.length;
  } // add(Object)

  /**
   * Get the least recently added element.
   */
  public Object get()
    throws Exception
  { 
    // Remember the first element.
    Object first = this.front.myCar;
    // Update the front of the list to refer to the next element.
    this.front = this.front.myCdr;
    // Do we have to do anything else if the list becomes empty?
    if (null == this.front) {
      this.back = null;
    }
    // Shrink the list
    --this.length;
    // Return the thing we previously identified as first. 
    return first;  
  } // get()

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

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

  /**
   * Convert to a string for ease of printing.
   */
  public String toString()
  {
    if (null == this.front) {
      return "()";
    }
    else {
      return this.front.toString();
    }
  } // toString()

} // class LinkedQueue