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)");
	}
}