package queue;

import list.Node;

/** A generic queue implemented using a linked list of nodes
  * @author Jan Stelovsky
  * @inspiration E. Biagioni */
public class LinkedQueue<Type> {
  /** Only a single pointer to the node at the back of the queue is needed.
    * If the queue is empty, back is null. Initially, the queue is empty. */
  protected Node<Type> back = null;
  /** The the number of nodes in the queue.
    * Invariant: the number of nodes pointed to by back */
  protected int size = 0;

  // Accessor method
  
  /** Returns the size of the queue.
    * @return the number of nodes in the queue */
  public int size () {
    return size;
  }

  /** Inserts a value as a new node at the end of the queue.
    * Also called enqueue.
    * @param value to add to the end of the list
    * @return true, this method always succeeds */
  public boolean offer (Type value) {
    if (back == null) { // special case: queue is empty
      back = new Node<Type> (value, null);
      back.setNext (back); // queue is a circular list
    } else { // there are some nodes in the queue
      // back's next points to the first node in the queue
      // make a new node that points to the first node in the queue
      Node<Type> last = new Node<Type> (value, back.next ());
      // make back of the queue point to the new node
      back.setNext (last);
      // let the new node be at the back of the queue
      back = last;
    }
    size++;
    return true;
  }

  /** Removes the first node in the queue and return its value.
    * @return the value in the node that was the head of the queue,
    * null if the queue was empty */
  public Type poll () {
    if (back == null) { // special case: queue empty
      return null;
    } else { // there is a first node in the queue
      // return the first node in the queue, which in our circular
      // linked list, is the node after the last node in the queue
      Node<Type> first = back.next ();
      if (size == 1) { // special case: queue has only one node
        // remove the only node in queue
        back = null;
      } else { // there are two or more nodes in the queue
        // remove the first node from the queue
        back.setNext (first.next ());
      }
      size--;
      // return the value from the removed node in the queue
      return first.value ();
      // now first is unreachable and may be garbage collected
    }
  }

  /** Converts the queue to a printable string
    * @return a string representing the queue */
  public String toString () {
    return back == null ? "empty" 
        : toString (back.next () /* first node */, size);
  }

  /** Converts "nodesLeft" nodes to a string beginning with "node"
    * @param node the start of the list to convert
    * @param count the count of nodes to convert, 0 to end
    * @return a string representing the node values */
  private String toString (Node<Type> node, int count) {
    return count == 0 ? "" 
        : node.value () + " : " + toString (node.next (), count - 1);
    }

  /** Unit test -- tests all the methods in this class.
    * @param arguments command line arguments; ignored */
  public static void main (String [] arguments) {
    // create two empty queues, make sure they print out correctly
    LinkedQueue<String> queue1 = new LinkedQueue<String> ();
    LinkedQueue<String> queue2 = new LinkedQueue<String> ();
    System.out.println ("1: queue1 = '" + queue1 + "', queue2 = '"
        + queue2 + "'");
    System.out.println ("queue1.size() = " + queue1.size () 
        + ", queue2.size() = " + queue2.size ());
    // remove an item from an empty queue
    if ((queue1.poll () != null) || (queue2.poll () != null)) {
      System.out.println ("error: removed item from empty queue(s)");
    }
    System.out.println ("2: queue1 = '" + queue1 + "', queue2 = '" 
        + queue2 + "'");
    // insert some items, keep checking
    if (!(queue1.offer ("hello"))) {
      System.out.println ("error inserting hello into q1");
    }
    if (!(queue1.offer ("world"))) {
      System.out.println ("error inserting world into queue1");
    }
    if (!(queue2.offer ("foo"))) {
      System.out.println ("error inserting foo into queue2");
    }
    if (!(queue2.offer ("bar"))) {
      System.out.println ("error inserting bar into queue2");
    }
    if (!(queue2.offer ("baz"))) {
      System.out.println ("error inserting baz into queue2");
    }
    System.out.println ("3: queue1 = '" + queue1 + "', queue2 = '" 
        + queue2 + "'");
    System.out.println ("queue1.size() = " + queue1.size () 
        + ", queue2.size() = " + queue2.size ());
    // remove some items from the queues
    if (!(queue1.poll ().equals ("hello"))) {
      System.out.println ("error removing hello from queue1");
    }
    if (!(queue2.poll ().equals ("foo"))) {
      System.out.println ("error removing foo from queue2");
    }
    if (!(queue2.poll ().equals ("bar"))) {
      System.out.println ("error removing bar from queue2");
    }
    if (!(queue2.poll ().equals ("baz"))) {
      System.out.println ("error removing baz from queue2");
    }
    System.out.println ("4: queue1 = '" + queue1 + "', queue2 = '" 
        + queue2 + "'");
    System.out.println ("queue1.size() = " + queue1.size () 
        + ", queue2.size() = " + queue2.size ());
  }
}