// Exercise 1.3.14 (Solution published at http://algs4.cs.princeton.edu/)
package algs13;
import stdlib.*;
import java.util.Iterator;
import java.util.NoSuchElementException;
/* ***********************************************************************
 *  Compilation:  javac ResizingArrayQueue.java
 *  Execution:    java ResizingArrayQueue < input.txt
 *  Data files:   http://algs4.cs.princeton.edu/13stacks/tobe.txt
 *
 *  Queue implementation with a resizing array.
 *
 *  % java ResizingArrayQueue < tobe.txt
 *  to be or not to be (2 left on queue)
 *
 *************************************************************************/

public class ResizingArrayQueue<T> implements Iterable<T> {
	private T[] q;           // queue elements
	private int N;           // number of elements on queue
	private int first;       // index of first element of queue
	private int last;        // index of next available slot

	// cast needed since no generic array creation in Java
	@SuppressWarnings("unchecked")
	public ResizingArrayQueue() {
		this.q = (T[]) new Object[2];
		this.N = 0;
		this.first = 0;
		this.last = 0;
	}

	public boolean isEmpty() { return N == 0;    }
	public int size()        { return N;         }

	@SuppressWarnings("unchecked")
	private void resize(int capacity) {
		if (capacity <= N) throw new IllegalArgumentException ();
		T[] temp = (T[]) new Object[capacity];
		for (int i = 0; i < N; i++) temp[i] = q[(first + i) % q.length];
		q = temp;
		first = 0;
		last  = N;
	}

	public void enqueue(T item) {
		if (N == q.length) resize(2*q.length);   // double size of array if necessary
		q[last] = item;                          // add item
		last = (last + 1) % q.length;
		N++;
	}

	// remove the least recently added item
	public T dequeue() {
		if (isEmpty()) throw new Error("Queue underflow");
		T item = q[first];
		q[first] = null;                         // to avoid loitering
		N--;
		first = (first + 1) % q.length;
		if (N > 0 && N == q.length/4) resize(q.length/2); // shrink size of array if necessary
		return item;
	}

	public Iterator<T> iterator() { return new ArrayIterator(); }
	private class ArrayIterator implements Iterator<T> {
		private int i = 0;
		public boolean hasNext()  { return i < N;                               }
		public void remove()      { throw new UnsupportedOperationException();  }

		public T next() {
			if (!hasNext()) throw new NoSuchElementException();
			T item = q[(first + i) % q.length];
			i++;
			return item;
		}
	}

	public String toString () {
		if (isEmpty()) return "[]";
		StringBuilder sb = new StringBuilder ("[");
		Iterator<T> i = iterator();
		sb.append (i.next ());
		while (i.hasNext ()) {
			sb.append (" ");
			sb.append (i.next ());
		}
		sb.append ("]");
		return sb.toString ();
	}
	private void check (String expected) {
		if (N<0 || N>q.length) throw new Error ();
		if (N==0 && q.length!=2) throw new Error ("Expected length 2, got " + q.length);
		if (N!=0 && N<q.length/4) throw new Error ();
		if (((first + N) % q.length) != last) throw new Error ();
		for (int i=0; i<N; i++) {
			if (q[(first + i) % q.length] == null) throw new Error ();
		}
		for (int i=N; i<q.length; i++) {
			if (q[(first + i) % q.length] != null) throw new Error ();
		}
		if (expected != null) {
			if (!expected.equals(this.toString ())) throw new Error ("Expected \"" + expected + "\", got \"" + this + "\"");
		}
		StdOut.println (this);
	}
	private void check (T iExpected, T iActual, String expected) {
		if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\"");
		check (expected);
	}
	public static void mainx (String args[]) {
		ResizingArrayQueue<Integer> d1;
		Integer k;
		d1 = new ResizingArrayQueue<> ();
		d1.enqueue (11); d1.check ("[11]");
		d1.enqueue (12); d1.check ("[11 12]");
		k = d1.dequeue(); d1.check (11, k, "[12]");
		k = d1.dequeue(); d1.check (12, k, "[]");

		d1 = new ResizingArrayQueue<> ();
		for (int i = 10; i < 20; i++)
			d1.enqueue (i);
		d1.check ("[10 11 12 13 14 15 16 17 18 19]");

		for (int i = 0; i < 10; i++) {
			d1.dequeue (); d1.check (null);
		}
		try { d1.dequeue (); throw new Error ("Expected exception"); } catch (Error e) {}
	}

	// A test client
	public static void main (String[] args) {
		StdIn.fromString ("to be or not to - be - - that - - - is");

		ResizingArrayQueue<String> q = new ResizingArrayQueue<>();
		while (!StdIn.isEmpty()) {
			String item = StdIn.readString();
			if (!item.equals("-")) q.enqueue(item);
			else StdOut.print(q.dequeue() + " ");
		}
		StdOut.println("(" + q.size() + " left on queue)");
	}
}