package algs13;
import stdlib.*;

public class XResizingArrayQueueofStrings {
	private String[] 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
	// Invariant (after the constructor):
	//   a[(first + 0) % q.length]..a[(first + N-1) % q.length] are non null
	//   a[(first + N) % q.length]..a[(first + a.length-1) % q.length] are null
	public XResizingArrayQueueofStrings() {
		this.q = new String[2];
		this.N = 0;
		this.first = 0;
		this.last = 0;
	}

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

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

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

	// remove the least recently added item
	public String dequeue() {
		if (isEmpty()) throw new Error("Queue underflow");
		String 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 String toString () {
		if (isEmpty()) return "[]";
		StringBuilder sb = new StringBuilder ("[");
		sb.append (q[first % q.length]);
		int i = 1;
		while (i < N) {
			sb.append (" ");
			sb.append (q[(first + i) % q.length]);
			i++;
		}
		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 (String iExpected, String iActual, String expected) {
		if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\"");
		check (expected);
	}
	public static void mainX (String args[]) {
		String k;
		var d1 = new XResizingArrayQueueofStrings ();
		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 XResizingArrayQueueofStrings ();
		for (int i = 10; i < 20; i++)
			d1.enqueue (Integer.toString(i));
		d1.check ("[10 11 12 13 14 15 16 17 18 19]");

		for (int i = 10; i < 20; 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");

		var q = new XResizingArrayQueueofStrings();
		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)");
	}
}