/*
 * Written by Alexander Foster and released into the public domain
 * as explained at http://creativecommons.org/publicdomain/zero/1.0/.
 * Portions of this class were adapted from ArrayDeque.
 */
package common.collections;

import java.io.Serializable;
import java.util.AbstractCollection;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.RandomAccess;
import java.util.Spliterator;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;

public class IndexedDeque<E> extends AbstractCollection<E> implements Deque<E>, List<E>, Cloneable,
        RandomAccess, Serializable {
    /**
     * The array in which the elements of the deque are stored.
     * The capacity of the deque is the length of this array, which is
     * always a power of two. The array is never allowed to become
     * full, except transiently within an addX method where it is
     * resized (see doubleCapacity) immediately upon becoming full,
     * thus avoiding head and tail wrapping around to equal each
     * other.  We also guarantee that all array cells not holding
     * deque elements are always null.
     */
    transient E[] elements; // non-private to simplify nested class access
    /**
     * The index of the element at the head of the deque (which is the
     * element that would be removed by remove() or pop()); or an
     * arbitrary number equal to tail if the deque is empty.
     */
    transient int head;
    /**
     * The index at which the next element would be added to the tail
     * of the deque (via addLast(E), or add(E)).
     */
    transient int tail;
    /**
     * The minimum capacity that we'll use for a newly created deque.
     * Must be a power of 2.
     */
    private static final int MIN_INITIAL_CAPACITY = 8;

    // ******  Array allocation and resizing utilities ******

    /**
     * Allocates empty array to hold the given number of elements.
     *
     * @param numElements  the number of elements to hold
     */
    @SuppressWarnings("unchecked")
    private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        if (numElements >= initialCapacity) {
            initialCapacity = Integer.highestOneBit(numElements) << 1;
            if(initialCapacity < 0) throw new IllegalStateException("Sorry, deque too big");
        }
        elements = (E[])new Object[initialCapacity];
    }
    /**
     * Doubles the capacity of this deque.  Call only when full, i.e.,
     * when head and tail have wrapped around to become equal.
     */
    void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p;
        int newCapacity = n << 1;
        if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big");
        @SuppressWarnings("unchecked")
        E[] a = (E[])new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }
    /**
     * Copies the elements from our element array into the specified array,
     * in order (from first to last element in the deque).  It is assumed
     * that the array is large enough to hold all elements in the deque.
     *
     * @return its argument
     */
    <T> T[] copyElements(T[] a, int from, int to) {
        if (from < to) {
            System.arraycopy(elements, from, a, 0, to - from);
        } else if (from > to) {
            int headPortionLen = elements.length - from;
            System.arraycopy(elements, from, a, 0, headPortionLen);
            System.arraycopy(elements, 0, a, headPortionLen, to);
        }
        return a;
    }
    /**
     * Constructs an empty indexed deque.
     */
    @SuppressWarnings("unchecked")
    public IndexedDeque() {
        elements = (E[])new Object[16];
    }
    /**
     * Constructs an empty indexed deque with an initial capacity
     * sufficient to hold the specified number of elements.
     *
     * @param numElements  lower bound on initial capacity of the deque
     */
    public IndexedDeque(int numElements) {
        allocateElements(numElements);
    }
    /**
     * Constructs a deque containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.  (The first element returned by the collection's
     * iterator becomes the first element, or <i>front</i> of the
     * deque.)
     *
     * @param c the collection whose elements are to be placed into the deque
     * @throws NullPointerException if the specified collection is null
     */
    public IndexedDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }
    /**
     * Inserts the specified element at the front of this deque.
     *
     * @param e the element to add
     */
    @Override
    public void addFirst(E e) {
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail) doubleCapacity();
    }
    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #add}.
     *
     * @param e the element to add
     */
    @Override
    public void addLast(E e) {
        elements[tail] = e;
        if ((tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity();
    }
    /**
     * Inserts the specified element at the front of this deque.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Deque#offerFirst})
     */
    @Override
    public boolean offerFirst(E e){
        addFirst(e);
        return true;
    }
    /**
     * Inserts the specified element at the end of this deque.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Deque#offerLast})
     */
    @Override
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }
    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    @Override
    public E removeFirst() {
        if (isEmpty()) throw new NoSuchElementException();
        return pollFirst();
    }
    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    @Override
    public E removeLast() {
        if (isEmpty()) throw new NoSuchElementException();
        return pollLast();
    }
    @Override
    public E pollFirst() {
        int h = head;
        if(h == tail) return null;
        E result = elements[h];
        elements[h] = null;
        head = (h + 1) & (elements.length - 1);
        return result;
    }
    @Override
    public E pollLast() {
        int t = tail;
        if(t == head) return null;
        t = (t - 1) & (elements.length - 1);
        E result = elements[t];
        elements[t] = null;
        tail = t;
        return result;
    }
    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    @Override
    public E getFirst() {
        int h = head;
        if(h == tail) throw new NoSuchElementException();
        return elements[h];
    }
    /**
     * @throws NoSuchElementException {@inheritDoc}
     */
    @Override
    public E getLast() {
        int t = tail;
        if(t == head) throw new NoSuchElementException();
        return elements[(t - 1) & (elements.length - 1)];
    }
    @Override
    public E peekFirst() {
        // elements[head] is null if deque empty
        return elements[head];
    }
    @Override
    public E peekLast() {
        return elements[(tail - 1) & (elements.length - 1)];
    }
    /**
     * Removes the first occurrence of the specified element in this
     * deque (when traversing the deque from head to tail).
     * If the deque does not contain the element, it is unchanged.
     * More formally, removes the first element {@code e} such that
     * {@code o == null ? e == null : o.equals(e)} (if such an element exists).
     * Returns {@code true} if this deque contained the specified element
     * (or equivalently, if this deque changed as a result of the call).
     *
     * @param o element to be removed from this deque, if present
     * @return {@code true} if the deque contained the specified element
     */
    @Override
    public boolean removeFirstOccurrence(Object o) {
        int i = index(o, head, tail);
        if(i == -1) return false;
        delete(i);
        return true;
    }
    /**
     * Removes the last occurrence of the specified element in this
     * deque (when traversing the deque from head to tail).
     * If the deque does not contain the element, it is unchanged.
     * More formally, removes the last element {@code e} such that
     * {@code o == null ? e == null : o.equals(e)} (if such an element exists).
     * Returns {@code true} if this deque contained the specified element
     * (or equivalently, if this deque changed as a result of the call).
     *
     * @param o element to be removed from this deque, if present
     * @return {@code true} if the deque contained the specified element
     */
    @Override
    public boolean removeLastOccurrence(Object o) {
        int i = lastIndex(o, head, tail);
        if(i == -1) return false;
        delete(i);
        return true;
    }

    // *** Queue methods ***

    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     */
    @Override
    public boolean add(E e) {
        addLast(e);
        return true;
    }
    /**
     * Inserts the specified element at the end of this deque.
     *
     * <p>This method is equivalent to {@link #offerLast}.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Queue#offer})
     */
    @Override
    public boolean offer(E e) {
        return offerLast(e);
    }
    /**
     * Retrieves and removes the head of the queue represented by this deque.
     *
     * This method differs from {@link #poll poll} only in that it throws an
     * exception if this deque is empty.
     *
     * <p>This method is equivalent to {@link #removeFirst}.
     *
     * @return the head of the queue represented by this deque
     * @throws NoSuchElementException {@inheritDoc}
     */
    @Override
    public E remove() {
        return removeFirst();
    }
    /**
     * Retrieves and removes the head of the queue represented by this deque
     * (in other words, the first element of this deque), or returns
     * {@code null} if this deque is empty.
     *
     * <p>This method is equivalent to {@link #pollFirst}.
     *
     * @return the head of the queue represented by this deque, or
     *         {@code null} if this deque is empty
     */
    @Override
    public E poll() {
        return pollFirst();
    }
    /**
     * Retrieves, but does not remove, the head of the queue represented by
     * this deque.  This method differs from {@link #peek peek} only in
     * that it throws an exception if this deque is empty.
     *
     * <p>This method is equivalent to {@link #getFirst}.
     *
     * @return the head of the queue represented by this deque
     * @throws NoSuchElementException {@inheritDoc}
     */
    @Override
    public E element() {
        return getFirst();
    }
    /**
     * Retrieves, but does not remove, the head of the queue represented by
     * this deque, or returns {@code null} if this deque is empty.
     *
     * <p>This method is equivalent to {@link #peekFirst}.
     *
     * @return the head of the queue represented by this deque, or
     *         {@code null} if this deque is empty
     */
    @Override
    public E peek() {
        return peekFirst();
    }

    // *** Stack methods ***

    /**
     * Pushes an element onto the stack represented by this deque.  In other
     * words, inserts the element at the front of this deque.
     *
     * <p>This method is equivalent to {@link #addFirst}.
     *
     * @param e the element to push
     */
    @Override
    public void push(E e) {
        addFirst(e);
    }
    /**
     * Pops an element from the stack represented by this deque.  In other
     * words, removes and returns the first element of this deque.
     *
     * <p>This method is equivalent to {@link #removeFirst()}.
     *
     * @return the element at the front of this deque (which is the top
     *         of the stack represented by this deque)
     * @throws NoSuchElementException {@inheritDoc}
     */
    @Override
    public E pop() {
        return removeFirst();
    }

    // *** List Methods ***

    /**
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public E get(int index){
        if(index < 0 || index >= size()) throw new IndexOutOfBoundsException();
        return elements[(index + head) & (elements.length - 1)];
    }
    /**
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public E set(int index, E e){
        if(index < 0 || index >= size()) throw new IndexOutOfBoundsException();
        index = (index + head) & (elements.length - 1);
        E old = elements[index];
        elements[index] = e;
        return old;
    }
    /**
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public void add(int index, E e){
        if(index < 0 || index > size()) throw new IndexOutOfBoundsException();
        insert((index + head) & (elements.length - 1), e);
        if(head == tail) doubleCapacity();
    }
    /**
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public E remove(int index){
        if(index < 0 || index >= size()) throw new IndexOutOfBoundsException();
        index = (index + head) & (elements.length - 1);
        E old = elements[index];
        delete(index);
        return old;
    }
    /**
     * @throws NullPointerException if the specified collection is null.
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        if(index < 0 || index > size()) throw new IndexOutOfBoundsException();
        Object[] a = c.toArray();
        if(a.length == 0) return false;
        insert(index, a, 0, a.length);
        return true;
    }
    public void clear(int from, int to){
        if(from < 0 || to < from || to > size()) throw new IndexOutOfBoundsException();
        if((to -= from) != 0) delete(from, to);
    }
    @Override
    public int indexOf(Object o) {
        int i = index(o, head, tail);
        return i == -1 ? -1 : (i - head) & (elements.length - 1);
    }
    @Override
    public int lastIndexOf(Object o) {
        int i = lastIndex(o, head, tail);
        return i == -1 ? -1 : (i - head) & (elements.length - 1);
    }
    int index(Object o, int from, int to) {
        E[] a = elements;
        int mask = a.length - 1, i = from;
        if (o == null){
            for( ; i != to; i = (i + 1) & mask){
                if(a[i] == null) return i;
            }
        } else {
            for( ; i != to; i = (i + 1) & mask){
                if(o.equals(a[i])) return i;
            }
        }
        return -1;
    }
    int lastIndex(Object o, int to, int from) {
        E[] a = elements;
        int mask = a.length - 1, i = from;
        if (o == null){
            for( ; i != to; ){
                if(a[i = (i - 1) & mask] == null) return i;
            }
        } else {
            for( ; i != to; ){
                if(o.equals(a[i = (i - 1) & mask])) return i;
            }
        }
        return -1;
    }
    /**
     * @throws NullPointerException if the specified operator is null.
     */
    @Override
    public void replaceAll(UnaryOperator<E> f){
        replaceAll(f, head, tail);
    }
    <T> void replaceAll(UnaryOperator<E> f, int from, int to){
        Objects.requireNonNull(f);
        E[] a = elements;
        for(int i = from, m = a.length - 1; i != to; i = (i + 1) & m){
            a[i] = f.apply(a[i]);
        }
    }
    /**
     * @throws ClassCastException {@inheritDoc}
     * @throws IllegalArgumentException {@inheritDoc}
     */
    @Override
    public void sort(Comparator<? super E> order){
        sort(order, head, tail);
    }
    @SuppressWarnings("unchecked")
    void sort(Comparator<? super E> order, int from, int to){
        E[] a = elements;
        if(from <= to){
            Arrays.sort(a, from, to, order);
            return;
        }
        if(to == 0){
            Arrays.sort(a, from, a.length, order);
            return;
        }
        int end = a.length - from;
        int size = end + to;
        int t = tail;
        if(t + (long)size <= head){
            System.arraycopy(a, from, a, t, end);
            System.arraycopy(a, 0, a, t + end, to);
            try {
                Arrays.sort(a, t, t + size, order);
            } catch(RuntimeException | Error e){
                Arrays.fill(a, t, t + size, null);
                throw e;
            }
            System.arraycopy(a, t, a, from, end);
            System.arraycopy(a, t + end, a, 0, to);
            Arrays.fill(a, t, t + size, null);
            return;
        }
        E[] e = (E[]) new Object[size];
        System.arraycopy(a, from, e, 0, end);
        System.arraycopy(a, 0, e, end, to);
        Arrays.sort(e, 0, size, order);
        System.arraycopy(e, 0, a, from, end);
        System.arraycopy(e, end, a, 0, to);
    }
    /**
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public List<E> subList(int from, int to){
        sublistRangeCheck(size(), from, to);
        return new SubList(null, from, to - from);
    }
    static void sublistRangeCheck(int size, int from, int to){
        if(from < 0) throw new IndexOutOfBoundsException(from + " < 0");
        if(to > size) throw new IndexOutOfBoundsException(to + " > " + size);
        if(from > to) throw new IndexOutOfBoundsException(from + " > " + to);
    }
    private class SubList extends AbstractCollection<E> implements List<E>, RandomAccess {
        final SubList parent;
        final int offset;
        int size;

        SubList(SubList parent, int offset, int size) {
            this.parent = parent;
            this.size = size;
            this.offset = offset;
        }
        void addToSize(int s){
            size += s;
            for(SubList p = parent; p != null; p = p.parent){
                p.size += s;
            }
        }
        @Override
        public E get(int index) {
            if(index < 0 || index >= size) throw new IndexOutOfBoundsException();
            return elements[(offset + head + index) & (elements.length - 1)];
        }
        @Override
        public E set(int index, E e) {
            if(index < 0 || index >= size) throw new IndexOutOfBoundsException();
            index = (offset + head + index) & (elements.length - 1);
            E old = elements[index];
            elements[index] = e;
            return old;
        }
        @Override
        public void add(int index, E e) {
            if(index < 0 || index > size) throw new IndexOutOfBoundsException();
            insert((offset + head + index) & (elements.length - 1), e);
            if(head == tail) doubleCapacity();
            addToSize(1);
        }
        @Override
        public E remove(int index) {
            if(index < 0 || index >= size) throw new IndexOutOfBoundsException();
            index = (offset + head + index) & (elements.length - 1);
            E old = elements[index];
            delete(index);
            addToSize(-1);
            return old;
        }
        @Override
        public boolean addAll(int index, Collection<? extends E> c) {
            if(index < 0 || index > size) throw new IndexOutOfBoundsException();
            Object[] a = c.toArray();
            if(a.length == 0) return false;
            insert(index + offset, a, 0, a.length);
            addToSize(a.length);
            return true;
        }
        @Override
        public List<E> subList(int from, int to) {
            sublistRangeCheck(size, from, to);
            return new SubList(this, from + offset, to - from);
        }
        @Override
        public int size() {
            return size;
        }
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
        @Override
        public void clear() {
            if(size == 0) return;
            delete(offset, size);
            addToSize(-size);
        }
        @Override
        public boolean contains(Object o) {
            int m = elements.length - 1, s = (offset + head) & m;
            return index(o, s, (s + size) & m) != -1;
        }
        @Override
        public Object[] toArray() {
            int m = elements.length - 1, s = (offset + head) & m;
            return copyElements(new Object[size], s, (s + size) & m);
        }
        @SuppressWarnings("unchecked")
        @Override
        public <T> T[] toArray(T[] a) {
            if (a.length < size)
                a = (T[])java.lang.reflect.Array.newInstance(
                        a.getClass().getComponentType(), size);
            int m = elements.length - 1, s = (offset + head) & m;
            copyElements(a, s, (s + size) & m);
            if (a.length > size) a[size] = null;
            return a;
        }
        @Override
        public boolean add(E e) {
            insert((offset + head + size) & (elements.length - 1), e);
            if(head == tail) doubleCapacity();
            addToSize(1);
            return true;
        }
        @Override
        public boolean remove(Object o) {
            int m = elements.length - 1, s = (offset + head) & m;
            int i = index(o, s, (s + size) & m);
            if(i == -1) return false;
            delete(i);
            addToSize(-1);
            return true;
        }
        @Override
        public boolean removeIf(Predicate<? super E> remove){
            int m = elements.length - 1, s = (offset + head) & m;
            int r = IndexedDeque.this.removeIf(remove, s, (s + size) & m);
            if(r == 0) return false;
            addToSize(-r);
            return true;
        }
        @Override
        public boolean addAll(Collection<? extends E> c) {
            return addAll(size, c);
        }
        @Override
        public boolean containsAll(Collection<?> c) {
            for(Object e : c){
                if(!contains(e)) return false;
            }
            return true;
        }
        @Override
        public boolean removeAll(Collection<?> c) {
            return removeIf(c::contains);
        }
        @Override
        public boolean retainAll(Collection<?> c) {
            Objects.requireNonNull(c);
            return removeIf(e -> !c.contains(e));
        }
        @Override
        public void replaceAll(UnaryOperator<E> f){
            int m = elements.length - 1, s = (offset + head) & m;
            IndexedDeque.this.replaceAll(f, s, (s + size) & m);
        }
        @Override
        public void forEach(Consumer<? super E> f){
            int m = elements.length - 1, s = (offset + head) & m;
            IndexedDeque.this.forEach(f, s, (s + size) & m);
        }
        @Override
        public void sort(Comparator<? super E> order){
            int m = elements.length - 1, s = (offset + head) & m;
            IndexedDeque.this.sort(order, s, (s + size) & m);
        }
        @Override
        public boolean equals(Object o){
            if(o == this) return true;
            int m = elements.length - 1, s = (offset + head) & m;
            return IndexedDeque.this.equals(o, s, (s + size) & m);
        }
        @Override
        public int hashCode(){
            int m = elements.length - 1, s = (offset + head) & m;
            return IndexedDeque.this.hashCode(s, (s + size) & m);
        }
        @Override
        public int indexOf(Object o) {
            int m = elements.length - 1, s = (offset + head) & m;
            int i = index(o, s, (s + size) & m);
            return i == -1 ? -1 : (i - s) & m;
        }
        @Override
        public int lastIndexOf(Object o) {
            int m = elements.length - 1, s = (offset + head) & m;
            int i = lastIndex(o, s, (s + size) & m);
            return i == -1 ? -1 : (i - s) & m;
        }
        @Override
        public Spliterator<E> spliterator() {
            int m = elements.length - 1, s = (offset + head) & m;
            return new DeqSpliterator(s, (s + size) & m);
        }
        @Override
        public Iterator<E> iterator() {
            return new SubListIterator(0);
        }
        @Override
        public ListIterator<E> listIterator() {
            return new SubListIterator(0);
        }
        @Override
        public ListIterator<E> listIterator(final int index) {
            if(index < 0 || index > size) throw new IndexOutOfBoundsException();
            return new SubListIterator(index);
        }
        class SubListIterator implements ListIterator<E> {
            private final IndexedDeque<E> d = IndexedDeque.this;
            private int cursor, lastRet = -1;

            SubListIterator(int index){
                cursor = index;
            }
            @Override
            public boolean hasNext() {
                return cursor < size;
            }
            @Override
            public E next() {
                if(cursor == size) throw new NoSuchElementException();
                return d.elements[lastRet = (offset + d.head + cursor++) & (d.elements.length - 1)];
            }
            @Override
            public boolean hasPrevious() {
                return cursor > 0;
            }
            @Override
            public E previous() {
                if(cursor == 0) throw new NoSuchElementException();
                return d.elements[lastRet = (offset + d.head + --cursor) & (d.elements.length - 1)];
            }
            @Override
            public int nextIndex() {
                return cursor;
            }
            @Override
            public int previousIndex() {
                return cursor - 1;
            }
            @Override
            public void remove() {
                if(lastRet < 0) throw new IllegalStateException();
                if(lastRet != ((offset + d.head + cursor) & (d.elements.length - 1))){
                    cursor--;
                }
                d.delete(lastRet);
                lastRet = -1;
                addToSize(-1);
            }
            @Override
            public void set(E e) {
                if(lastRet < 0) throw new IllegalStateException();
                d.elements[lastRet] = e;
            }
            @Override
            public void add(E e) {
                d.insert((offset + d.head + cursor++) & (d.elements.length - 1), e);
                if(d.head == d.tail) d.doubleCapacity();
                addToSize(1);
                lastRet = -1;
            }
            @Override
            public void forEachRemaining(Consumer<? super E> action){
                Objects.requireNonNull(action);
                E[] a = d.elements;
                int s = offset + d.head;
                int m = a.length - 1, f = (s + cursor) & m, i = (s + size) & m;
                if(f == i) return;
                for( ; i != f; i = (i + 1) & m){
                    action.accept(a[i]);
                }
                lastRet = (f - 1) & m;
                cursor = size;
            }
        }
    }

    // *** Collection Methods ***

    /**
     * Returns the number of elements in this deque.
     *
     * @return the number of elements in this deque
     */
    @Override
    public int size() {
        return (tail - head) & (elements.length - 1);
    }
    /**
     * Returns {@code true} if this deque contains no elements.
     *
     * @return {@code true} if this deque contains no elements
     */
    @Override
    public boolean isEmpty() {
        return head == tail;
    }
    /**
     * Returns an iterator over the elements in this deque.  The elements
     * will be ordered from first (head) to last (tail).  This is the same
     * order that elements would be dequeued (via successive calls to
     * {@link #remove} or popped (via successive calls to {@link #pop}).
     *
     * @return an iterator over the elements in this deque
     */
    @Override
    public Iterator<E> iterator() {
        return new DeqIterator(head);
    }
    @Override
    public ListIterator<E> listIterator() {
        return new DeqIterator(head);
    }
    /**
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    @Override
    public ListIterator<E> listIterator(final int index) {
        if(index < 0 || index > size()) throw new IndexOutOfBoundsException();
        return new DeqIterator((index + head) & (elements.length - 1));
    }
    @Override
    public Iterator<E> descendingIterator() {
        return new DeqIterator(tail){
            @Override
            public boolean hasNext() {
                return hasPrevious();
            }
            @Override
            public E next(){
                return previous();
            }
            @Override
            public void forEachRemaining(Consumer<? super E> action) {
                Objects.requireNonNull(action);
                checkMod();
                E[] a = elements;
                int m = a.length - 1, f = start, i = cursor;
                if(i == f) return;
                for( ; i != f; ) {
                    action.accept(a[i = (i - 1) & m]);
                }
                lastRet = cursor = f;
            }
        };
    }
    private class DeqIterator implements ListIterator<E> {
        /**
         * Index of element to be returned by subsequent call to next.
         */
        int cursor;
        /**
         * Tail and head recorded at construction (also in remove),
         * to stop iterator and also to check for comodification.
         */
        int end = tail, start = head;
        /**
         * Index of element returned by most recent call to next.
         * Reset to -1 if element is deleted by a call to remove.
         */
        int lastRet = -1;

        DeqIterator(int index){
            cursor = index;
        }
        @Override
        public boolean hasNext() {
            return cursor != end;
        }
        @Override
        public boolean hasPrevious() {
            return cursor != start;
        }
        @Override
        public int nextIndex() {
            return (cursor - start) & (elements.length - 1);
        }
        @Override
        public int previousIndex() {
            return nextIndex() - 1;
        }
        final void checkMod(){
            if (tail != end || head != start) throw new ConcurrentModificationException();
        }
        @Override
        public E next() {
            int c = cursor;
            if (c == end) throw new NoSuchElementException();
            checkMod();
            E[] a = elements;
            cursor = (c + 1) & (a.length - 1);
            return a[lastRet = c];
        }
        @Override
        public E previous() {
            int c = cursor;
            if (c == start) throw new NoSuchElementException();
            checkMod();
            return elements[lastRet = cursor = (c - 1) & (elements.length - 1)];
        }
        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            checkMod();
            E[] a = elements;
            int m = a.length - 1, i = cursor, f = end;
            if(i == f) return;
            for( ; i != f; i = (i + 1) & m) {
                action.accept(a[i]);
            }
            lastRet = (f - 1) & m;
            cursor = f;
        }
        @Override
        public void remove() {
            if (lastRet < 0) throw new IllegalStateException();
            checkMod();
            boolean prev = lastRet == cursor;
            if(delete(lastRet)){
                if(!prev) cursor = (cursor - 1) & (elements.length - 1);
                end = tail;
            } else {
                if(prev) cursor = (cursor + 1) & (elements.length - 1);
                start = head;
            }
            lastRet = -1;
        }
        @Override
        public void set(E e) {
            if (lastRet < 0) throw new IllegalStateException();
            checkMod();
            elements[lastRet] = e;
        }
        @Override
        public void add(E e) {
            checkMod();
            boolean forward = insert(cursor, e);
            if(head == tail){
                int c = (cursor - start) & (elements.length - 1);
                doubleCapacity();
                start = 0;
                end = tail;
                cursor = c + 1;
            } else if(forward){
                cursor = (cursor + 1) & (elements.length - 1);
                end = tail;
            } else {
                start = head;
            }
            lastRet = -1;
        }
    }
    /**
     * Returns {@code true} if this deque contains the specified element.
     * More formally, returns {@code true} if and only if this deque contains
     * at least one element {@code e} such that
     * {@code o == null ? e == null : o.equals(e)}.
     *
     * @param o object to be checked for containment in this deque
     * @return {@code true} if this deque contains the specified element
     */
    @Override
    public boolean contains(Object o) {
        return index(o, head, tail) != -1;
    }
    /**
     * Removes a single instance of the specified element from this deque.
     * If the deque does not contain the element, it is unchanged.
     * More formally, removes the first element {@code e} such that
     * {@code o == null ? e == null : o.equals(e)} (if such an element exists).
     * Returns {@code true} if this deque contained the specified element
     * (or equivalently, if this deque changed as a result of the call).
     *
     * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}.
     *
     * @param o element to be removed from this deque, if present
     * @return {@code true} if this deque contained the specified element
     */
    @Override
    public boolean remove(Object o) {
        return removeFirstOccurrence(o);
    }
    /**
     * Removes all of the elements from this deque.
     * The deque will be empty after this call returns.
     */
    @Override
    public void clear() {
        int h = head;
        int t = tail;
        if(h == t) return;
        head = tail = 0;
        if(h < t){
            Arrays.fill(elements, h, t, null);
        } else {
            Arrays.fill(elements, h, elements.length, null);
            Arrays.fill(elements, 0, t, null);
        }
    }
    /**
     * @throws NullPointerException if the specified collection is null.
     */
    @Override
    public boolean containsAll(Collection<?> c) {
        for(Object e : c){
            if(!contains(e)) return false;
        }
        return true;
    }
    /**
     * @throws NullPointerException if the specified collection is null.
     */
    @Override
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size(), c);
    }
    /**
     * @throws NullPointerException if the specified collection is null.
     */
    @Override
    public boolean removeAll(Collection<?> c) {
        return removeIf(c::contains);
    }
    /**
     * @throws NullPointerException if the specified collection is null.
     */
    @Override
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return removeIf(e -> !c.contains(e));
    }
    /**
     * @throws NullPointerException {@inheritDoc}
     */
    @Override
    public void forEach(Consumer<? super E> action){
        forEach(action, head, tail);
    }
    void forEach(Consumer<? super E> action, int from, int to){
        Objects.requireNonNull(action);
        E[] a = elements;
        for(int i = from, m = a.length - 1; i != to; i = (i + 1) & m){
            action.accept(a[i]);
        }
    }
    /**
     * @throws NullPointerException {@inheritDoc}
     */
    @Override
    public boolean removeIf(Predicate<? super E> filter){
        return removeIf(filter, head, tail) != 0;
    }
    int removeIf(Predicate<? super E> filter, int from, int to){
        Objects.requireNonNull(filter);
        E[] a = elements;
        int m = a.length - 1, i = from;
        for( ; ; i = (i + 1) & m){
            if(i == to) return 0;
            if(filter.test(a[i])) break;
        }
        int r = i;
        i = (i + 1) & m;
        for( ; i != to; i = (i + 1) & m){
            E e = a[i];
            if(filter.test(e)) continue;
            a[r] = e;
            r = (r + 1) & m;
        }
        int s = (to - r) & m;
        delete((r - head) & m, s);
        return s;
    }
    /**
     * Returns an array containing all of the elements in this deque
     * in proper sequence (from first to last element).
     *
     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this deque.  (In other words, this method must allocate
     * a new array).  The caller is thus free to modify the returned array.
     *
     * <p>This method acts as bridge between array-based and collection-based
     * APIs.
     *
     * @return an array containing all of the elements in this deque
     */
    @Override
    public Object[] toArray() {
        return copyElements(new Object[size()], head, tail);
    }
    /**
     * Returns an array containing all of the elements in this deque in
     * proper sequence (from first to last element); the runtime type of the
     * returned array is that of the specified array.  If the deque fits in
     * the specified array, it is returned therein.  Otherwise, a new array
     * is allocated with the runtime type of the specified array and the
     * size of this deque.
     *
     * <p>If this deque fits in the specified array with room to spare
     * (i.e., the array has more elements than this deque), the element in
     * the array immediately following the end of the deque is set to
     * {@code null}.
     *
     * <p>Like the {@link #toArray()} method, this method acts as bridge between
     * array-based and collection-based APIs.  Further, this method allows
     * precise control over the runtime type of the output array, and may,
     * under certain circumstances, be used to save allocation costs.
     *
     * <p>Suppose {@code x} is a deque known to contain only strings.
     * The following code can be used to dump the deque into a newly
     * allocated array of {@code String}:
     *
     *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
     *
     * Note that {@code toArray(new Object[0])} is identical in function to
     * {@code toArray()}.
     *
     * @param a the array into which the elements of the deque are to
     *          be stored, if it is big enough; otherwise, a new array of the
     *          same runtime type is allocated for this purpose
     * @return an array containing all of the elements in this deque
     * @throws ArrayStoreException if the runtime type of the specified array
     *         is not a supertype of the runtime type of every element in
     *         this deque
     * @throws NullPointerException if the specified array is null
     */
    @SuppressWarnings("unchecked")
    @Override
    public <T> T[] toArray(T[] a) {
        int size = size();
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                    a.getClass().getComponentType(), size);
        copyElements(a, head, tail);
        if (a.length > size) a[size] = null;
        return a;
    }
    /**
     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
     * and <em>fail-fast</em> {@link Spliterator} over the elements in this
     * deque.
     *
     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
     * {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
     * Overriding implementations should document
     * the reporting of additional characteristic values.
     *
     * @return a {@code Spliterator} over the elements in this deque
     * @since 1.8
     */
    @Override
    public Spliterator<E> spliterator() {
        return new DeqSpliterator(-1, -1);
    }
    final class DeqSpliterator implements Spliterator<E> {
        private int fence;  // -1 until first use
        private int index;  // current index, modified on traverse/split

        /** Creates new spliterator covering the given array and range. */
        DeqSpliterator(int origin, int fence) {
            this.index = origin;
            this.fence = fence;
        }
        private int getFence() { // force initialization
            int t;
            if ((t = fence) < 0) {
                t = fence = tail;
                index = head;
            }
            return t;
        }
        @Override
        public DeqSpliterator trySplit() {
            int t = getFence(), h = index, n = elements.length;
            if (h != t && ((h + 1) & (n - 1)) != t) {
                if (h > t) t += n;
                int m = ((h + t) >>> 1) & (n - 1);
                return new DeqSpliterator(h, index = m);
            }
            return null;
        }
        @Override
        public void forEachRemaining(Consumer<? super E> consumer) {
            if (consumer == null) throw new NullPointerException();
            E[] a = elements;
            int m = a.length - 1, f = getFence(), i = index;
            index = f;
            for( ; i != f; i = (i + 1) & m) {
                consumer.accept(a[i]);
            }
        }
        @Override
        public boolean tryAdvance(Consumer<? super E> consumer) {
            if (consumer == null) throw new NullPointerException();
            E[] a = elements;
            int m = a.length - 1, f = getFence(), i = index;
            if(i == f) return false;
            index = (i + 1) & m;
            consumer.accept(a[i]);
            return true;
        }
        @Override
        public long estimateSize() {
            int n = getFence() - index;
            if (n < 0) n += elements.length;
            return (long) n;
        }
        @Override
        public int characteristics() {
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
        }
    }

    // *** Object methods ***

    @Override
    public boolean equals(Object o) {
        return o == this || equals(o, head, tail);
    }
    boolean equals(Object o, int from, int to) {
        if (!(o instanceof List)) return false;
        List<?> l = (List<?>)o;
        E[] a = elements;
        int i = from, m = a.length - 1, s = l.size();
        if(s != ((to - from) & m)) return false;
        if(s == 0) return true;
        if(o instanceof RandomAccess){
            for(int j = 0; i != to; i = (i + 1) & m){
                E e = a[i];
                Object c = l.get(j++);
                if(!(e == null ? c == null : e.equals(c))) return false;
            }
            return true;
        }
        ListIterator<?> it = l.listIterator();
        for( ; ; i = (i + 1) & m){
            boolean n = it.hasNext();
            if(i != to != n) return false;
            if(!n) return true;
            E e = a[i];
            Object c = it.next();
            if(!(e == null ? c == null : e.equals(c))) return false;
        }
    }
    @Override
    public int hashCode() {
        return hashCode(head, tail);
    }
    int hashCode(int from, int to) {
        int hashCode = 1;
        E[] a = elements;
        int i = from, m = a.length - 1;
        for( ; i != to; i = (i + 1) & m){
            E e = a[i];
            hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
        }
        return hashCode;
    }
    /**
     * Returns a copy of this deque.
     *
     * @return a copy of this deque
     */
    @Override
    public IndexedDeque<E> clone() {
        try {
            @SuppressWarnings("unchecked")
            IndexedDeque<E> result = (IndexedDeque<E>) super.clone();
            result.elements = Arrays.copyOf(elements, elements.length);
            return result;
        } catch (CloneNotSupportedException e) {
            throw new AssertionError();
        }
    }
    private static final long serialVersionUID = -8192327985554913705L;
    /**
     * Saves this deque to a stream (that is, serializes it).
     *
     * @param s the stream
     * @throws java.io.IOException if an I/O error occurs
     * @serialData The current size ({@code int}) of the deque,
     * followed by all of its elements (each an object reference) in
     * first-to-last order.
     */
    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
        s.defaultWriteObject();

        // Write out size
        s.writeInt(size());

        // Write out elements in order.
        int mask = elements.length - 1;
        for (int i = head; i != tail; i = (i + 1) & mask)
            s.writeObject(elements[i]);
    }
    /**
     * Reconstitutes this deque from a stream (that is, deserializes it).
     * @param s the stream
     * @throws ClassNotFoundException if the class of a serialized object
     *         could not be found
     * @throws java.io.IOException if an I/O error occurs
     */
    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
        s.defaultReadObject();

        // Read in size and allocate array
        int size = s.readInt();
        allocateElements(size);
        head = 0;
        tail = size;

        // Read in all elements in the proper order.
        for (int i = 0; i < size; i++)
            elements[i] = (E) s.readObject();
    }

    // *** Element insertion and deletion  ***

    /**
     * Removes the element at the specified position in the elements array,
     * adjusting head and tail as necessary.  This can result in motion of
     * elements backwards or forwards in the array.
     *
     * <p>This method is called delete rather than remove to emphasize
     * that its semantics differ from those of {@link List#remove(int)}.
     *
     * @return true if elements moved backwards
     */
    boolean delete(int i) {
        final E[] elements = this.elements;
        final int mask = elements.length - 1;
        final int h = head;
        final int t = tail;
        final int front = (i - h) & mask;
        final int back  = (t - i) & mask;

        // Invariant: head <= i < tail mod circularity
        if (front >= ((t - h) & mask)) throw new ConcurrentModificationException();

        // Optimize for least element motion
        if (front < back) {
            if (h <= i) {
                System.arraycopy(elements, h, elements, h + 1, front);
            } else { // Wrap around
                System.arraycopy(elements, 0, elements, 1, i);
                elements[0] = elements[mask];
                System.arraycopy(elements, h, elements, h + 1, mask - h);
            }
            elements[h] = null;
            head = (h + 1) & mask;
            return false;
        } else {
            if (i < t) { // Copy the null tail as well
                System.arraycopy(elements, i + 1, elements, i, back);
                tail = t - 1;
            } else { // Wrap around
                System.arraycopy(elements, i + 1, elements, i, mask - i);
                elements[mask] = elements[0];
                System.arraycopy(elements, 1, elements, 0, t);
                tail = (t - 1) & mask;
            }
            return true;
        }
    }
    /**
     * Inserts the element at the specified position in the elements array.
     * May either shift the element at the specified index and all after forward,
     * of shift all elements before the index backwards and insert the element
     * before the index. Caller is responsible for checking if capacity must be doubled.
     *
     * @return true if elements moved forward (and tail was incremented)
     */
    boolean insert(int i, E e){
        final E[] elements = this.elements;
        final int mask = elements.length - 1;
        int h = head;
        final int t = tail;
        final int front = (i - h) & mask;
        final int back  = (t - i) & mask;

        // Invariant: head <= i <= tail mod circularity
        if (front > ((t - h) & mask)) throw new ConcurrentModificationException();

        // Optimize for least element motion
        if (front < back) {
            i = (i - 1) & mask;
            h = (h - 1) & mask;
            if (h <= i) {
                System.arraycopy(elements, h + 1, elements, h, front);
            } else { // Wrap around
                System.arraycopy(elements, h + 1, elements, h, mask - h);
                elements[mask] = elements[0];
                System.arraycopy(elements, 1, elements, 0, i);
            }
            elements[i] = e;
            head = h;
            return false;
        } else {
            if (i <= t) {
                System.arraycopy(elements, i, elements, i + 1, back);
            } else { // Wrap around
                System.arraycopy(elements, 0, elements, 1, t);
                elements[0] = elements[mask];
                System.arraycopy(elements, i, elements, i + 1, mask - i);
            }
            elements[i] = e;
            tail = (t + 1) & mask;
            return true;
        }
    }
    /**
     * Removes length elements from the elements array starting at index + head (inclusive).
     *
     * @return true if elements moved backward (and tail was decreased)
     */
    boolean delete(int index, int length){
        int size = size();
        int ahead = size - index - length;
        E[] a = elements;
        int mask = a.length - 1;
        int i = (head + index) & mask;
        int e = (i + length) & mask;
        if(index <= ahead){
            if(head <= i){
                if(i <= e){
                    System.arraycopy(a, head, a, e - index, index);
                    Arrays.fill(a, head, head += length, null);
                } else {
                    if(e >= index){
                        System.arraycopy(a, head, a, e - index, index);
                        Arrays.fill(a, head, a.length, null);
                        Arrays.fill(a, 0, head = e - index, null);
                    } else {
                        System.arraycopy(a, i - e, a, 0, e);
                        System.arraycopy(a, head, a, head + length, index - e);
                        Arrays.fill(a, head, head += length, null);
                    }
                }
            } else {
                System.arraycopy(a, 0, a, length, i);
                int r = a.length - head;
                if(length >= r){
                    System.arraycopy(a, head, a, length - r, r);
                    Arrays.fill(a, 0, length - r, null);
                    Arrays.fill(a, head, a.length, null);
                    head = (head + length) & mask;
                } else {
                    System.arraycopy(a, a.length - length, a, 0, length);
                    System.arraycopy(a, head, a, head + length, r - length);
                    Arrays.fill(a, head, head += length, null);
                }
            }
            return false;
        } else {
            if(tail >= e){
                if(i <= e){
                    System.arraycopy(a, e, a, i, ahead);
                    Arrays.fill(a, tail - length, tail, null);
                    tail -= length;
                } else {
                    if(a.length >= i + ahead){
                        System.arraycopy(a, e, a, i, ahead);
                        Arrays.fill(a, i + ahead, a.length, null);
                        Arrays.fill(a, 0, tail, null);
                        tail = (i + ahead) & mask;
                    } else {
                        int r = a.length - i;
                        System.arraycopy(a, e, a, i, r);
                        System.arraycopy(a, e + r, a, 0, ahead - r);
                        Arrays.fill(a, ahead - r, tail, null);
                        tail = ahead - r;
                    }
                }
            } else {
                int f = a.length - e;
                System.arraycopy(a, e, a, i, f);
                if(length >= tail){
                    System.arraycopy(a, 0, a, i + f, tail);
                    Arrays.fill(a, 0, tail, null);
                    Arrays.fill(a, i + f + tail, a.length, null);
                    tail = (i + f + tail) & mask;
                } else {
                    System.arraycopy(a, 0, a, i + f, length);
                    System.arraycopy(a, length, a, 0, tail - length);
                    Arrays.fill(a, tail - length, tail, null);
                    tail -= length;
                }
            }
            return true;
        }
    }
    /**
     * Inserts length elements from a starting at offset (inclusive) into the
     * elements array at index + head. May shift elements forwards or backwards
     * or resize the elements array.
     */
    void insert(int index, Object[] a, int offset, int length) {
        int size = size();
        int newSize = size + length;
        if(newSize < 0 || newSize >= 1 << 30){
            throw new IllegalStateException("Sorry, deque too big");
        }
        E[] es = elements;
        if(newSize >= es.length){
            allocateElements(newSize);
            E[] n = elements;
            if(tail >= head){
                System.arraycopy(es, head, n, 0, index);
                System.arraycopy(a, offset, n, index, length);
                System.arraycopy(es, head + index, n, index + length, size - index);
            } else {
                int r = es.length - head;
                if(r < index){
                    System.arraycopy(es, head, n, 0, r);
                    System.arraycopy(es, 0, n, r, index - r);
                    System.arraycopy(a, offset, n, index, length);
                    System.arraycopy(es, index - r, n, index + length, size - index);
                } else {
                    System.arraycopy(es, head, n, 0, index);
                    System.arraycopy(a, offset, n, index, length);
                    System.arraycopy(es, head + index, n, index + length, r - index);
                    System.arraycopy(es, 0, n, r + length, tail);
                }
            }
            head = 0;
            tail = newSize;
            return;
        }
        int back = size - index;
        int mask = es.length - 1;
        if(index <= back){
            int h = head - length;
            if(h < 0){
                int nh = h & mask;
                if(index >= -h){
                    System.arraycopy(es, head, es, nh, -h);
                    System.arraycopy(es, head - h, es, 0, index + h);
                    System.arraycopy(a, offset, es, h + index, length);
                } else {
                    System.arraycopy(es, head, es, nh, index);
                    int f = -h - index;
                    System.arraycopy(a, offset, es, nh + index, f);
                    System.arraycopy(a, offset + f, es, 0, length - f);
                }
                h = nh;
            } else {
                int i = head + index - es.length;
                if(i <= 0){
                    System.arraycopy(es, head, es, h, index);
                    System.arraycopy(a, offset, es, h + index, length);
                } else {
                    int r = index - i;
                    System.arraycopy(es, head, es, h, r);
                    int ni = i - length;
                    if(ni >= 0){
                        System.arraycopy(es, 0, es, h + r, length);
                        System.arraycopy(es, length, es, 0, ni);
                        System.arraycopy(a, offset, es, ni, length);
                    } else {
                        System.arraycopy(es, 0, es, h + r, i);
                        System.arraycopy(a, offset, es, h + index, -ni);
                        System.arraycopy(a, offset - ni, es, 0, length + ni);
                    }
                }
            }
            head = h;
        } else {
            int t = tail + length;
            if(t > mask){
                t &= mask;
                if(t >= back){
                    int f = t - back;
                    System.arraycopy(es, tail - back, es, f, back);
                    System.arraycopy(a, offset, es, tail - back, length - f);
                    System.arraycopy(a, offset + length - f, es, 0, f);
                } else {
                    System.arraycopy(es, tail - t, es, 0, t);
                    System.arraycopy(es, tail - back, es, es.length - back + t, back - t);
                    System.arraycopy(a, offset, es, tail - back, length);
                }
            } else {
                int i = tail - back;
                if(i >= 0){
                    System.arraycopy(es, i, es, i + length, back);
                    System.arraycopy(a, offset, es, i, length);
                } else {
                    System.arraycopy(es, 0, es, t - tail, tail);
                    int ni = i + length;
                    if(ni >= 0){
                        System.arraycopy(es, i & mask, es, ni, -i);
                        System.arraycopy(a, offset, es, i & mask, -i);
                        System.arraycopy(a, offset - i, es, 0, ni);
                    } else {
                        System.arraycopy(es, (i & mask) - ni, es, 0, -i + ni);
                        System.arraycopy(es, i & mask, es, ni & mask, -ni);
                        System.arraycopy(a, offset, es, i & mask, length);
                    }
                }
            }
            tail = t;
        }
    }
}