/*
This program implements a circular queue, which uses an array underneath. It
can be used to implement stack (lifo) or queue (fifo) data structures.  This
program will also illustrate the uses of interfaces, generics, and inheritance.

The advantages of this approach, compared to a linked list implementation using
pointers to the next cell is that:

1.  Accessing the ith element becomes O(1) instead of O(n)
2.  Deleting the last cell becomes O(1) instead of O(n) in singly linked lists
3.  Binary search becomes feasible, with O(log n) time on sorted queues.
4.  It's faster to allocate a large amount of memory all at once compared
    to a few bytes at a time.

The potential disadvantage of this approach is not knowing how much
capacity to allocate.  But careful analysis (and experimentation) show
that dynamically resizing and copying the queue generates an
acceptable overhead.  If we double the size of the array each time it
needs to be resized, then the amount of copying we need to do is still
linearly proportional to n, the number of values in the queue.  For
example, if n=128 and the array initially has a capacity of one, then
resizing the queue requires creating and copying arrays of sizes:

   1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255 = 2n-1

Inserting n values into a queue, even if starting with a capacity of 1,
still takes time linearly proportional to n.

This program contains two class: CircQ and CircOQ.  CircQ implements
the basic circular queue structure for any type of value.  CircOQ
extends CircQ but requires its values to be Comparable.  It overrides the
basic operations to maintain a sorted queue.  A new operation insert,
which inserts a new value into the middle of the queue in sorted order, is
added to the subclass.  This kind of operation, however, shows the disadvantage
of the queue structure as it remains O(n).
*/

import java.util.Iterator;  // interface enables for loops

public class CircQ<T> implements Iterable<T>, Queue<T>
{
    protected T[] A; // underlying array representing the queue
    protected int front; // index of first value in queue
    protected int size;  // number of values in queue, not same as A.length
    public int size() {return size;} // readonly accessor for size.
    public int capacity() { if (A==null) return 0; else return A.length;}

    protected int lasti() // index of last value, if it exists  O(1)
    {
	return (front+size-1)%capacity();
    }
    protected int right(int i) // index to the "right" of index i  O(1)
    { return (i+1)%capacity(); }

    protected int left(int i) // index of cell to the "left" of index i O(1)
    {
        return (i+capacity()-1) % A.length;
    }

    public CircQ(int cap) // create a queue of a fixed capacity
    {
	// A = new T[cap]; // won't compile in Java
	A = (T[]) new Object[cap]; // compiles with compiler warning
	front = 0;
	size = 0;
    }//constructor

    public CircQ(T[] B) { A = B; front =0; size=0; } // alternate constructor

    public void resize() // doubles size, copy
    {
	T[] B = (T[]) new Object[A.length*2];
	for(int i=0;i<size;i++)  B[i] = A[(front+i)%A.length];
	A = B; // new array now represents queue
	front = 0;
    }//resize

    // insert x into front of queue (push)   O(1)
    public void push(T x) 
    {
	if (size>=capacity()) resize();
	// special case: front not valid if size is 0
	if (size>0) front = left(front);
	A[front] = x;
	size++;
    }

    // delete and return from front of queue  O(1)
    public T pop()
    {
	if (size<1) throw new RuntimeException("buffer underflow");
	size--;
	T answer = A[front];
	front = right(front);
	return answer;
    }
    public T peek() // return first value without delete, O(1)
    {
	if (size<1) return null;
	else return A[front];
    }
    public T first() { return peek(); } // alias for peek

    // insert into back of queue (enqueue)  O(1)
    public void enqueue(T x)
    {
	if (size>=capacity()) resize();
	int nexti = (front+size)%capacity(); // if size==0, nexti==front
	A[nexti] = x;
	size++;
    }

    // delete from back of queue  O(1) - constrast with singly linked list
    public T dequeue()
    {
	if (size<1) throw new RuntimeException("buffer underflow");
	T answer = A[lasti()];
	size--;
	return answer;
    }
    public T last() // returns last value value in list, O(1)
    {
	if (size<1) return null;
	else return A[lasti()];
    }

    // finding the nth value from the front, 0th = first
    public T getnth(int n) // return value at virtual index n,  O(1)
    {
	if (n>=size || n<0)
	    throw new RuntimeException("value doesn't exist at "+n);
	return A[ (front+n)%A.length ];
    }

    // set the nth value from front to x, return previous value  O(1)
    public T setnth(int n, T x)
    {
	if (n>=size || n<0)
	    throw new RuntimeException("value doesn't exists: "+n);
	int ni = (front+n)%A.length; // index of nth value
	T ax = A[ni];
	A[ni] = x;
	return ax;
    }

    public boolean Contains(T x) // search for x using .equals(), O(n) ***
    {
	for (int i=0;i<size;i++) if (x.equals(getnth(i))) return true;
	return false;
    } // Contains, can be improved ... 

    ///// implementation of Iterable interface requires an interator class

    // for DEBUGGING PURPOSES:
    void printinternal()
    {
	System.out.println("Internal array:");
	for(int i=0;i<A.length;i++) System.out.print(i+":"+A[i]+" ");
	System.out.println();
	System.out.printf("front==%d, last==%d\n",front,lasti());
    }

    ///////// For Iterator and Iterable interfaces...
    class Qiterator implements Iterator<T>  // internal class has access
    {                                       // to front, size, etc
	int i = 0;
	//public Qiterator() {} // default constructor
	public boolean hasNext()
	{
	    return i<size;
	}
	public T next()
	{
           return getnth(i++);
	}
    }//Qiterator

    public Iterator<T> iterator() // required by Iterable interface
    {
	return new Qiterator();
    }


    // main is only for testing
    public static void main(String[] av)
    {
	CircQ<Integer> Q = new CircQ<Integer>(1);
	for(Integer i=2;i<10;i+=2) {Q.push(i); Q.enqueue(i+1); }
	Q.dequeue();
	Q.pop();
	for(Integer x:Q) System.out.println(x);
	Q.printinternal();
    }
}//CircQ



//// Ordered Queue, with comparable values, can be sorted, binary searched
// ... should put in another file as public class, only here for convenience:
class CircOQ<T extends Comparable<T>> extends CircQ<T>
{
    // repeat constructors
    public CircOQ(int cap)
    { 
	super( (T[]) new Comparable[cap] ); // compiles with warning
    }
    public CircOQ(T[] B) { super(B); }

    public void resize() // doubles size, O(n + ?)
    {
	T[] B = (T[]) new Comparable[A.length*2];
	for(int i=0;i<size;i++)  B[i] = A[(front+i)%A.length];
	A = B; // new array now represents queue
	front = 0;
    }//resize
    public void resizen(int n)// inc size by n
    {   if (n<1) return;
	T[] B = (T[]) new Comparable[A.length+n]; // add one at a time
	for(int i=0;i<size;i++)  B[i] = A[(front+i)%A.length];
	A = B; // new array now represents queue
	front = 0;
    }//resize    

    public void insert(T x) // ordered insertion of x, O(n)
    {
	if (size>=A.length) resize();
	// find position to insert x into:
	int i = 0; // logical index from front
	while (i<size && x.compareTo(getnth(i))>0) i++;
	size++;
	for(int k = size-1;k>i;k--) setnth(k,getnth(k-1));
	setnth(i,x);
    }

    public boolean sorted() // check if array is sorted, O(n)
    {
	for(int i=0;i<size-1;i++) // i is logical index
	    {
		T a = getnth(i), b = getnth(i+1);
		if (a.compareTo(b)>0) return false;
	    }
	return true;
    }

    public boolean Contains(T x) { return binsearch(x); } //alias, overrides
    public boolean binsearch(T x) // assumes sorted array, O(log n)
    {
	int min = 0, max = size-1;
	boolean ax = false;
	while (!ax && min<=max)
	    {
		int mid = (min+max)/2;
		int c = x.compareTo(getnth(mid));
		if (c==0) ax=true;
		else if (c<0) max = mid-1;
		else if (c>0) min = mid+1;
	    }//while
	return ax;
    }

    // override push, enqueue to enforce sorted insert, still O(1)
    public void push(T x) 
    {
	if (size>=capacity()) resize();
	// special case: front not valid if size is 0
	if (size==0)
	    { A[front] = x; size++; }
	else if (x.compareTo(A[front])<0)
	    {
		front = left(front);
		A[front] = x; size++; 
	    }
	else throw new RuntimeException("unordered insert");
    }// new push

    public void enqueue(T x)
    {
	if (size>=capacity()) resize();
	if (size==0) {A[front]=x; size++; }
	else if(x.compareTo(A[lasti()])>=0)
	    {
		int nexti = (front+size)%capacity(); // if size==0, nexti==front
		A[nexti] = x;
		size++;
	    }
	else throw new RuntimeException("unordered insert");
    }// new enqueue
    public T setnth(int n, T x) // this must also be overridden
    {
	throw new RuntimeException("setnth not supported on Ordered Queue");
    }
}// CircOQ