/**
 * An array-based implementation of a Queue.
 * See QueueInterface for documentation of functions defined in the interface
 * as inicated by the @Override before most methods
 *
 * @author gtowell
 * Created: Feb 10, 2020
 * Modified: Oct 20, 2020
 * Modified: Aug 9, 2021
 * @param <Q>
 */
public class ArrayQueue<Q> implements QueueInterface<Q> {
    /** the default capacity for the backing array */
    private static final int CAPACITY = 40;

    /** The array in which the queue data is stored */
    private Q[] backingArray;

    /** The number of items in the queue */
    private int count;

    /** The array location of the end of the queue  (ie the
     * location of the item shown by the peek command
    */
    private int frontLoc;


    /**
     * Create an array backed queue with the default capacity.
     */
    public ArrayQueue() {
        this(CAPACITY);
    }

    /**
     * Create an array backed queue with the given capacity
     * 
     * @param qSize the capacity for the queue
     */
    @SuppressWarnings("unchecked")
    public ArrayQueue(int qSize) {
        count = 0;
        frontLoc = 0;
        backingArray = (Q[]) new Object[qSize];
    }
 
    @Override
    public boolean isEmpty() {
        return count == 0;
    }

    @Override
    public int size() {
        return count;
    }

    @Override
    public boolean enqueue(Q q) {
        if (count >= backingArray.length)
            return false;
        int loc = (frontLoc + count) % backingArray.length;
        backingArray[loc] = q;
        count++;
        return true;
    }

    @Override
    public Q dequeue() {
        if (isEmpty())
            return null;
        Q rtn = backingArray[frontLoc];
        backingArray[frontLoc] = null;
        count--;
        frontLoc = (frontLoc + 1) % backingArray.length;
        return rtn;
    }

    @Override
    public Q getFront() {
        if (isEmpty())
            return null;
        return backingArray[frontLoc];
    }

    /**
     * Standard toString, show all eleents in queue.  First 
     * element is the item next from poll, last item in the 
     * end of the queue
     */
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append("{ ");
        for (int i = 0; i < count; i++) {
            int loc = (frontLoc + i) % backingArray.length;
            sb.append(backingArray[loc] + " ");
        }
        sb.append("}");
        return sb.toString();
    }

    /**
     * Test that the queue operations do exactly what they 
     * are supposed to do.
     * @param args
     */
    public static void main(String[] args) {
        ArrayQueue<Integer> aq = new ArrayQueue<>(3);
        System.out.println("Was 5 added? " + aq.enqueue(5));
        System.out.println("Contents of q after adding 5 " + aq);
        System.out.println("Was 7 added? " + aq.enqueue(7));
        System.out.println("Contents of q after adding 7 " + aq);
        System.out.println("Was 9 added? " + aq.enqueue(9));
        System.out.println("Contents of q after adding 9 " + aq);
        System.out.println("Was 4 added? " + aq.enqueue(4));
        System.out.println("Contents of q after adding 4 " + aq);
        System.out.println(aq.dequeue());
        System.out.println(aq);
        System.out.println(aq.dequeue());
        System.out.println(aq);
        System.out.println(aq.dequeue());
        System.out.println(aq);
        System.out.println(aq.dequeue());
        System.out.println(aq);
    }

    @Override
    public void clear() {
        int fl = frontLoc;
        for (int i = 0; i < count; i++) {
            backingArray[fl] = null;
            fl = (fl + 1) % backingArray.length;
        }    
        count = 0;
        frontLoc=0;
    }
}