import java.util.NoSuchElementException;

/**
 * An implementation of the SimpleList interface using a circular array.
 *
 * @param <E> component type
 */
public class SimpleArrayList<E> implements SimpleList<E> {

    // Main method to test the addFirst method.
    // Add to this to test other methods.
    public static void main(String[] args) {
        SimpleList<Integer> list = new SimpleArrayList<Integer>(20);
        for (int i = 2; i <= 40; i += 2) list.addFirst(i);
        System.out.println(list);
    }

    private E[] store; // Array where list's elements are stored.
    private int head; // Index of the first element in the list
    private int tail; // Index of next available array cell at end of list
    private int size; // Number of elements in the list

    /**
     * Capacity constructor - creates an empty list with an
     * array of the given capacity.
     *
     * @param initialCapacity initial capacity (length) of the array
     */
    public SimpleArrayList(int initialCapacity) {
        store = (E[]) new Object[initialCapacity];
    }

    /**
     * Default constructor - creates an empty list with an
     * array of capacity 10.
     */
    public SimpleArrayList() {
        this(10);
    }

    @Override
    /**
     * Adds the given element to the start of the list.
     * (Increases array capacity if array is full.)
     * @param elem element to add
     */
    public void addFirst(E elem) {
        if (size == store.length) increaseCapacity();
        head = (head - 1 + store.length) % store.length;
        store[head] = elem;
        size++;
    }

    @Override
    /**
     * Removes the last element from the list.
     * @return element that was removed
     * @throws NoSuchElementException if there is no last element
     */
    public E removeLast() {
        if (size == 0) throw new NoSuchElementException("list empty");
        tail = (tail - 1 + store.length) % store.length;
        E doomed = store[tail];
        size--;
        return doomed;
    }

    @Override
    /**
     * Returns the element in the list at the given index.
     *
     * (NOTE: The given index is the list index, not the
     * array index.)
     *
     * @param index index of element to return
     * @return element at given index
     * @throws IndexOutOfBoundsException if given index is invalid
     */
    public E get(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException(
            "invalid index"
        );
        int arrayIndex = (head + index) % store.length;
        return store[arrayIndex];
    }

    @Override
    /**
     * Returns true of this list is equal to the given list.
     * Two lists are equal if they contain the same elements in the same order.
     * @param otherList list to compare to this list
     * @return true if lists are equal
     */
    public boolean equals(SimpleList<E> otherList) {
        if (otherList instanceof SimpleArrayList) {
            SimpleArrayList<E> otherArrayList = (SimpleArrayList<E>) otherList;

            if (this.size != otherArrayList.size) return false;
            for (int i = 0; i < size; i++) {
                E thisEl = this.get(i);
                E otherEl = otherArrayList.get(i);
                if (!thisEl.equals(otherEl)) return false;
            }
            return true;
        }
        return false;
    }

    @Override
    public void addLast(E elem) {
        if (size == store.length) increaseCapacity();
        store[tail] = elem;
        tail = (tail + 1) % store.length;
        size++;
    }

    @Override
    public E removeFirst() {
        if (size == 0) throw new NoSuchElementException("list empty");
        E doomed = store[head];
        head = (head + 1) % store.length;
        size--;
        return doomed;
    }

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

    @Override
    public String toString() {
        if (size == 0) return "[]";
        else {
            String s = "[";
            for (
                int i = 0, j = head;
                i < size;
                i++, j = (j + 1) % store.length
            ) s += store[j] + ", ";
            return s.substring(0, s.length() - 2) + "]";
        }
    }

    private void increaseCapacity() {
        E[] bigger = (E[]) new Object[size + size / 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = store[head];
            head = (head + 1) % size;
        }
        head = 0;
        tail = size;
        store = bigger;
    }
}