package algs13;
import  stdlib.*;
import java.util.Iterator;
import java.util.NoSuchElementException;
/* ***********************************************************************
 *  Compilation:  javac Queue.java
 *  Execution:    java Queue < input.txt
 *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt
 *
 *  A generic queue, implemented using a linked list.
 *
 *  % java Queue < tobe.txt
 *  to be or not to be (2 left on queue)
 *
 *************************************************************************/
/**
 *  The {@code Queue} class represents a first-in-first-out (FIFO)
 *  queue of generic items.
 *  It supports the usual <em>enqueue</em> and <em>dequeue</em>
 *  operations, along with methods for peeking at the top item,
 *  testing if the queue is empty, and iterating through
 *  the items in FIFO order.
 *  <p>
 *  All queue operations except iteration are constant time.
 *  <p>
 *  For additional documentation, see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 */
public class Queue<T> implements Iterable<T> {
  private int N;         // number of elements on queue
  private Node<T> first;    // beginning of queue
  private Node<T> last;     // end of queue

  // helper linked list class
  private static class Node<T> {
    public Node() { }
    public T item;
    public Node<T> next;
  }

  /**
   * Create an empty queue.
   */
  public Queue() {
    first = null;
    last  = null;
    N = 0;
  }

  /**
   * Is the queue empty?
   */
  public boolean isEmpty() {
    return first == null;
  }

  /**
   * Return the number of items in the queue.
   */
  public int size() {
    return N;
  }

  /**
   * Return the item least recently added to the queue.
   * @throws java.util.NoSuchElementException if queue is empty.
   */
  public T peek() {
    if (isEmpty()) throw new NoSuchElementException("Queue underflow");
    return first.item;
  }

  /**
   * Add the item to the queue.
   */
  public void enqueue(T item) {
    Node<T> oldlast = last;
    last = new Node<>();
    last.item = item;
    last.next = null;
    if (isEmpty()) first = last;
    else           oldlast.next = last;
    N++;
  }

  /**
   * Remove and return the item on the queue least recently added.
   * @throws java.util.NoSuchElementException if queue is empty.
   */
  public T dequeue() {
    if (isEmpty()) throw new NoSuchElementException("Queue underflow");
    T item = first.item;
    first = first.next;
    N--;
    if (isEmpty()) last = null;
    return item;
  }

  /**
   * Return string representation.
   */
  public String toString() {
    StringBuilder s = new StringBuilder();
    for (T item : this)
      s.append(item + " ");
    return s.toString();
  }

  // check internal invariants
  private static <T> boolean check(Queue<T> that) {
    int N = that.N;
    Queue.Node<T> first = that.first;
    Queue.Node<T> last = that.last;
    if (N == 0) {
      if (first != null) return false;
      if (last  != null) return false;
    }
    else if (N == 1) {
      if (first == null || last == null) return false;
      if (first != last)                 return false;
      if (first.next != null)            return false;
    }
    else {
      if (first == last)      return false;
      if (first.next == null) return false;
      if (last.next  != null) return false;

      // check internal consistency of instance variable N
      int numberOfNodes = 0;
      for (Queue.Node<T> x = first; x != null; x = x.next) {
        numberOfNodes++;
      }
      if (numberOfNodes != N) return false;

      // check internal consistency of instance variable last
      Queue.Node<T> lastNode = first;
      while (lastNode.next != null) {
        lastNode = lastNode.next;
      }
      if (last != lastNode) return false;
    }

    return true;
  }


  /**
   * Return an iterator that iterates over the items on the queue in FIFO order.
   */
  public Iterator<T> iterator()  {
    return new ListIterator();
  }

  // an iterator, doesn't implement remove() since it's optional
  private class ListIterator implements Iterator<T> {
    private Node<T> current = first;

    public boolean hasNext()  { return current != null;                     }
    public void remove()      { throw new UnsupportedOperationException();  }

    public T next() {
      if (!hasNext()) throw new NoSuchElementException();
      T item = current.item;
      current = current.next;
      return item;
    }
  }

  public void toGraphviz(String filename) {
    GraphvizBuilder gb = new GraphvizBuilder ();
    toGraphviz (gb, null, first);
    gb.toFile (filename, "rankdir=\"LR\"");
  }
  private void toGraphviz (GraphvizBuilder gb, Node<T> prev, Node<T> n) {
    if (n == null) { gb.addNullEdge (prev); return; }
    gb.addLabeledNode (n, n.item.toString ());
    if (prev != null) gb.addEdge (prev, n);
    toGraphviz (gb, n, n.next);
  }

  /**
   * A test client.
   */
  public static void main(String[] args) {
    Trace.drawStepsOfMethod("main");
    Trace.drawStepsOfMethod("enqueue");
    Trace.drawStepsOfMethod("dequeue");
    Trace.run();
    StdIn.fromString ("to be or not to - be - - that - - - is");
    Queue<String> q = new Queue<>();
    int count = 0;
    //q.toGraphviz ("queue" + count + ".png"); count++;
    while (!StdIn.isEmpty()) {
      String item = StdIn.readString();
      if (!item.equals("-")) q.enqueue(item);
      else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
      //q.toGraphviz ("queue" + count + ".png"); count++;
    }
    StdOut.println("(" + q.size() + " left on queue)");
  }
}