/**
 * IQueue implementation using a circular array to hold its elements.
 * @author Jeff Raab
 */
public class CircularArrayQueue implements IQueue {

    /** Array holding the elements of this. */
    protected Object[] elements = new Object[4];
    
    /** Front index in this. */
    protected int front = 0;
    
    /** Back index in this, exclusive. */
    protected int back = 0;

    /** Constructs an empty circular array queue. */
    public CircularArrayQueue() {}

    /** 
     * Enqueues the given object onto this.
     * @param anObject object to enqueue
     */
    public void enqueue(Object anObject) {
        if (shouldGrow()) {
            grow();
        }
        
        elements[back] = anObject;
        back = after(back);
    }
    
    /** Removes and returns the front object on this. */
    public Object dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        
        Object toReturn = elements[front];
        elements[front] = null;
        
        front = after(front);
        
        if (shouldShrink()) {
            shrink();
        }
        
        return toReturn;
    }
    
    /** Returns the front object on this. */
    public Object front() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        
        return elements[front];
    }
    
    /** Returns the number of objects on this. */
    public int size() {
        if (back < front) {
            return back + elements.length - front;
        }
        
        return back - front;
    }
    
    /** Returns whether or not this is empty. */
    public boolean isEmpty() {
        return (size() == 0);
    }
    
    /** Returns the index in elements after the given index. */
    private int after(int i) {
        return (i + 1) % elements.length;
    }
    
    /** Returns whether or not the array should be grown. */
    private boolean shouldGrow() {
        return (size() == elements.length - 1);
    }
    
    /** Returns whether or not the array should be shrunk. */
    private boolean shouldShrink() {
        if (size() <= 4) {
            return false;
        }
        
        return (size() <= (elements.length / 3));
    }
    
    /** Grows the array of elements. */
    private void grow() {
        Object[] newArray = new Object[elements.length * 2];
        int newBack = 0;
        
        for (int i = front; i != back; i = after(i)) {
            newArray[newBack++] = elements[i];
        }
        
        elements = newArray;
        front = 0;
        back = newBack;
    }
    
    /** Shrinks the array of elements. */
    private void shrink() {
        Object[] newArray = new Object[elements.length / 2];
        int newBack = 0;
        
        for (int i = front; i != back; i = after(i)) {
            newArray[newBack++] = elements[i];
        }
        
        elements = newArray;
        front = 0;
        back = newBack;
    }
}