/**
 * Nicholas Ayala
 * I Abide by the UNCG Honor Code
 * 2/10/2014
 * CSC 330-01
 */
public class n_ayala_hwk2 {
    public static void main(String[] args) {
        int [] arr ={8, 7, 5, 3, 6, 7, 12, 4};
       CircularArrayDeque<Integer> stack = new CircularArrayDeque<>(arr);
       stack.addLast(1);
       stack.addLast(2);
       stack.addLast(3);
       stack.removeLast();
        System.out.println(stack.toString());
        stack.removeFirst();
        stack.addLast(3);
        System.out.println(stack.toString());
        System.out.println("The 5th element is:" + stack.get(5));
    }
}
//interface not from java
interface Deque<E>{
    public int size();
    public boolean isEmpty();
    public E getFirst();
    public void addFirst(E e);
    public E removeFirst();
    public E getLast();
    public void addLast(E e);
    public E removeLast();
    public E get(int idx);
    int increment (int x);
    int decrement (int x);
    void doubleDeque();
}
class CircularArrayDeque<E> implements Deque<E>{
    private int front, back, currentSize;
    private E[] items;
    private final int DEFAULT_CAPACITY = 10;
    public CircularArrayDeque(){
        front = back = currentSize = 0;
        items =(E[]) new Object[DEFAULT_CAPACITY];
    }
    //Additional constructor to accept integer type and cast to E
    public CircularArrayDeque(int [] arr){
        front = back = 0;
        items = (E[]) new Object[arr.length];
        for(int i =0; i < arr.length; i++){
            items[i]= (E) (Integer) arr[i];
        }
        back = arr.length - 1;
    }

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

    @Override
    public boolean isEmpty() {
        if(currentSize == 0)
            return true;
        else return false;
    }

    @Override
    public E getFirst() {
        return items[front];
    }

    @Override
    public void addFirst(E e) {
        if(currentSize == items.length){
            doubleDeque();}
            front = decrement(front);
            items[front] = e;
            currentSize++;
    }

    @Override
    public E removeFirst() {
        if(isEmpty()){
            System.out.println("EMPTY");
        }
        E result = items[front];
        items[front] = null;
        back =(back -1)% items.length;
        
        currentSize--;
        return result;
    }

    @Override
    public E getLast() {
        return items[back];
    }

    @Override
    public void addLast(E e) {
        if(currentSize == items.length){
            doubleDeque();}
        back= increment(back);
        items[front] = e;
        currentSize++;
    }

    @Override
    public E removeLast() {
        if(isEmpty()){
            System.out.println("EMPTY");
        }
        E result = items[front];
        items[front]= null;
        back=(back -1)% items.length;
        currentSize --;
        return result;
    }

    @Override
    public E get(int idx) {
        return items[idx];
    }

    @Override
    public int increment(int x) {
        if(++x == -1){
            x = items.length-1;
        }
        return x;
    }

    @Override
    public int decrement(int x) {
        if(--x == -1){
            x = items.length -1;
        }
        return x;
    }

    @Override
    public void doubleDeque() {
        if(!isEmpty()){
            //make the array bigger
            E[] larger =(E[]) new Object[(items.length*2) + 1];
            for(int i = 0; i <currentSize; i++){
                front = increment(front);
                larger[i] = items[front];
            }
            items = larger;
            front = 0;
            back = currentSize -1;
        }
    }
    
    @Override
    public String toString(){
        String str ="";
        for (E item : items) {
            if (item != null) {
                str += item.toString() + " ";
            }
        }
        return str;
    }
}