public class ArrayDeque<T> implements Deque<T> {
    private int head, tail, size;
    private Object[] deque;
    public static final int DEFAULT_CAPACITY = 16;

    public ArrayDeque() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayDeque(int initialCapacity) {
        deque = new Object[initialCapacity];
        tail = -1;
    }

    @Override
    public boolean addFirst(T obj) {
        if (atCapacity()) {
            resize(2 * deque.length);
        }
        if (isEmpty()) {
            head = tail = 0;
        } else {
            head = (deque.length + head - 1) % deque.length;
        }
        deque[head] = obj;
        size++;
        return true;
    }

    @Override
    public boolean addLast(T obj) {
        if (atCapacity()) {
            resize(2 * deque.length);
        }
        if (isEmpty()) {
            head = tail = 0;
        } else {
            tail = (tail + 1) % deque.length;
        }
        deque[tail] = obj;
        size++;
        return true;
    }

    @Override
    public boolean offerFirst(T obj) {
    try {
            addFirst(obj);
        } catch (IllegalStateException e) {
            return false;
        }
        return true;
    }

    @Override
    public boolean offerLast(T obj) {
    try {
            addLast(obj);
        } catch (IllegalStateException e) {
            return false;
        }
        return true;

    }

    @Override
    public T getFirst() {
       T t = (T) deque[head];
       if (t == null)
           throw new NoSuchElementException();
       return t;
    }

    @Override
    public T getLast() {
       T t = (T) deque[tail];
       if (t == null)
           throw new NoSuchElementException();
       return t;
    }

    @Override
    public T peekFirst() {
        return (T) deque[head];
    }

    @Override
    public T peekLast() {
        return (T) deque[tail];
    }

    @Override
    public T removeFirst() {
        T x = pollFirst();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

    @Override
    public T removeLast() {
        T x = pollLast();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

    @Override
    public T pollFirst() {
        T result = (T) deque[head]; // Element is null if deque empty
        if (result == null)
            return null;
        deque[head] = null;     // Must null out slot
        head = (head + 1) & (deque.length - 1);
        return result;
    }

    @Override
    public T pollLast() {
    int t = (tail - 1) & (deque.length - 1);
        T result = (T) deque[t];
        if (result == null)
            return null;
        deque[t] = null;
        tail = t;
        return result;
    }

    @Override
    public void clear() {
        head = tail = size = 0;
    }

    @Override
    public boolean contains(T obj) {
        for (int i = 0; i < size; i++){
            int index = (head + i) % deque.length;

            if (deque[index].equals(obj))
                return true;
        }
        return false;
    }

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

    @Override
    public boolean isEmpty() {
        return head==tail;
    }

    @Override
    public Object[] toArray() {
    Object [] array = new Object [size];
            for (int i = 0; i < size; i++){
                int index = (head + i) % deque.length;
            array[i] = deque[index];
            }
       return array;
    }

    private boolean atCapacity() {
        return size == deque.length;
    }

    private void resize(int newCapacity) {
        Object [] temp = new Object[newCapacity];
        for (int i = 0; i < size; i++){
            int index = (head+i) % deque.length;
            temp[i] = deque[index];
        }
        head = 0;
        tail = size-1;
    }
}