import java.util.*;
/**
 *This is my own work.
 * Circular Array Deque: Intended to demonstrate the array implementation of 
 * the Double-ended queue interface, such that elements can be added and removed
 * from either end.
 * @author jcsupple (Craig Supples)
 */
class jcsupple_hwk2 <E>{

    /**
     * Empty constructor, sets default values for items, back, front, 
     * currentSize, and capacity;
     * @param none
     * @return new jcsupple_hw2/Circular array deque object
     */
    public jcsupple_hwk2()
    {
        items = (E []) new Object[DEFAULT_CAPACITY];
        back = -1;
        front = 0;
        currentSize = 0;
        capacity = DEFAULT_CAPACITY;
    }

    /**
     * Constructor using an existing Collection that extends E
     * @param other (Collection that extends E)
     * sets initial values as determined by other
     */
    public jcsupple_hwk2(Collection <? extends E> other)
    {
       items = (E []) other.toArray();
       capacity = currentSize = other.size();
       front = 0;
       back = capacity-1;
    }

    /**
     * returns the size of the deque
     * @return currentSize
     */
    public int size()
    {
        return currentSize;
        // if front< back, back-front
        // if front> back, (items.length-front) + back
    }
    /**
    * Determines if it's empty, used before the execution of a removal/get
    * @return true if Empty and false if not
    */
    public boolean isEmpty()
    {
      return currentSize == 0;  
    }

    /**
     * This returns element at front index
     * @return element at the front
     * if empty, returns null
     */
    public E getFirst()
    {
        if(!isEmpty())
        {
            return items[front];
        }
        else
            return null;
    }

    /**
     * adds an element e to the front of the array, if full it doubles
     * @param e (unspecified element)
     */
    public void addFirst(E e)
    {
        if (currentSize == capacity)
        {
            doubleDeque();
        }
        front = decrement(front);
        items[front] = e;
        currentSize++;
    }

    /**
     * removes the element at front
     * @return removed element, if empty, returns null
     */
    public E removeFirst()
    {
       if(!isEmpty())
       {
            E placeholder = items[front];
            front = increment(front); 
            currentSize--;  
            return placeholder;
       }
       else 
           return null;
    }

    /**
     * returns element at back
     * @return element at back, null if empty
     */
    public E getLast()
    {
       if(!isEmpty())
        {
            return items[back];
        }
        else
            return null;
    }

    /**
     * adds element e at back, if full it doubles
     * @param e (unspecified element)
     */
    public void addLast(E e)
    {
        if(currentSize == capacity)
        {
            doubleDeque();
        }
        back = increment(back);
        items[back] = e;
        currentSize++;
    }

    /**
     * removes element at back
     * @return removed element, if empty, returns null
     */
    public E removeLast()
    {
       if(!isEmpty())
       {
            E placeholder = items[back];
            back = decrement(back); 
            currentSize--;  
            return placeholder;
       }
       else 
           return null;
    }

    /**
     * returns element at specified index in relation to front
     * @param idx index of element if front is 0
     * @return element at index idx in relation to front
     */
    public E get(int idx)
    {
        return items[(front+idx)% capacity];
    }

    /**
     * increments x and wraps around if over capacity
     * @param x
     * @return x, wrapped around if necessary
     */
    private int increment(int x)
    {
        if(++x == items.length)
        {
            x=0;
        }
        return x;
    }
    
    /**
     * decrements x, wraparound if necessary
     * @param x
     * @return x, wrapped around if necessary
     */
    private int decrement(int x)
    {
        if(--x == -1)
            x = items.length-1;
        return x;
    }

    /**
     * increases the capacity of items by doubling the capacity
     */
    private void doubleDeque()
    {
      E[] temp = (E []) new Object[capacity];//temp array to hold items w/o wrap
      for(int i = 0, j = front; i<currentSize; i++)
      {// iterates through items, adding elemnts to temp without wrap
          temp[i] = items[j];
          j = increment(j);
      }
      front = 0;
      back = capacity-1;//resets variables
      capacity = capacity*2;// doubles capacity
      items = (E[]) new Object[capacity];//sets item as new array w/capacity*2
      for(int i = 0; i<currentSize; i++)//copy temp back into items at front
      {
          items[i] = temp[i];
      }
    }

    private E [] items;

    private int currentSize, capacity, front, back;

    private static final int DEFAULT_CAPACITY =10;
    
    /**
     * main method to test.
     * Test the Deque with initial integer array int[] arr ={8, 7, 5, 3, 6, 7, 12, 4} as the parameter of constructor call;
     * Stack use: call addLast(1); addLast(2); addLast(3); removeLast(); 
     * print the array after these operations.
     * Queue use: then call removeFirst(); addLast(3); print the final Deque and
     * get(5) element.
     */
    public static void main(String[] args)
    {
        int arr[] = {8,7,5,3,6,7,12,4};
        ArrayList arrl1 = new ArrayList(arr.length);//arraylist to pass as arg
        for(int i = 0; i < arr.length; i++)
        {// adding elements to arraylist
            arrl1.add(arr[i]);
        }
        //construction of deque using arraylist as an argument (implem. collec.)
        jcsupple_hwk2 test = new jcsupple_hwk2(arrl1);
        test.addLast(1);
        test.addLast(2);
        test.addLast(3);
        test.removeLast();
        System.out.print("Current Deque[");
        for(int i = 0; i<test.size(); i++)
        { 
            if(i == test.size()-1)
            {
                System.out.println(test.get(i)+"]");
            }
            else
            {
                System.out.print(test.get(i)+", ");
            }
        }
        test.removeFirst();
        test.addLast(3);
        System.out.print("Final Deque:[");
        for(int i = 0; i<test.size(); i++)
        {
            if(i == test.size()-1)
            {
                System.out.println(test.get(i)+"]");
            }
            else
            {
                System.out.print(test.get(i)+", ");
            }
        }
        System.out.println("The element at index 5 is "+test.get(5));
    }

    }