/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

/*

 * This file is available under and governed by the GNU General Public

 * License version 2 only, as published by the Free Software Foundation.

 * However, the following notice accompanied the original version of this

 * file:

 *

 * Written by Josh Bloch of Google Inc. and released to the public domain,

 * as explained at http://creativecommons.org/publicdomain/zero/1.0/.

 */

package java.util;

import java.io.Serializable;

import java.util.function.Consumer;

import java.util.function.Predicate;

import java.util.function.UnaryOperator;

/**

 * Resizable-array implementation of the {@link Deque} interface.  Array

 * deques have no capacity restrictions; they grow as necessary to support

 * usage.  They are not thread-safe; in the absence of external

 * synchronization, they do not support concurrent access by multiple threads.

 * Null elements are prohibited.  This class is likely to be faster than

 * {@link Stack} when used as a stack, and faster than {@link LinkedList}

 * when used as a queue.

 *

 * <p>Most {@code ArrayDeque} operations run in amortized constant time.

 * Exceptions include

 * {@link #remove(Object) remove},

 * {@link #removeFirstOccurrence removeFirstOccurrence},

 * {@link #removeLastOccurrence removeLastOccurrence},

 * {@link #contains contains},

 * {@link #iterator iterator.remove()},

 * and the bulk operations, all of which run in linear time.

 *

 * <p>The iterators returned by this class's {@link #iterator() iterator}

 * method are <em>fail-fast</em>: If the deque is modified at any time after

 * the iterator is created, in any way except through the iterator's own

 * {@code remove} method, the iterator will generally throw a {@link

 * ConcurrentModificationException}.  Thus, in the face of concurrent

 * modification, the iterator fails quickly and cleanly, rather than risking

 * arbitrary, non-deterministic behavior at an undetermined time in the

 * future.

 *

 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed

 * as it is, generally speaking, impossible to make any hard guarantees in the

 * presence of unsynchronized concurrent modification.  Fail-fast iterators

 * throw {@code ConcurrentModificationException} on a best-effort basis.

 * Therefore, it would be wrong to write a program that depended on this

 * exception for its correctness: <i>the fail-fast behavior of iterators

 * should be used only to detect bugs.</i>

 *

 * <p>This class and its iterator implement all of the

 * <em>optional</em> methods of the {@link Collection} and {@link

 * Iterator} interfaces.

 *

 * <p>This class is a member of the

 * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">

 * Java Collections Framework</a>.

 *

 * @author  Josh Bloch and Doug Lea

 * @param <E> the type of elements held in this deque

 * @since   1.6

 */

public class ArrayDeque<E> extends AbstractCollection<E>

                           implements Deque<E>, Cloneable, Serializable

{

    /*

     * VMs excel at optimizing simple array loops where indices are

     * incrementing or decrementing over a valid slice, e.g.

     *

     * for (int i = start; i < end; i++) ... elements[i]

     *

     * Because in a circular array, elements are in general stored in

     * two disjoint such slices, we help the VM by writing unusual

     * nested loops for all traversals over the elements.  Having only

     * one hot inner loop body instead of two or three eases human

     * maintenance and encourages VM loop inlining into the caller.

     */

    /**

     * The array in which the elements of the deque are stored.

     * All array cells not holding deque elements are always null.

     * The array always has at least one null slot (at tail).

     */

    transient Object[] elements;

    /**

     * 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 0 <= head < elements.length 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), add(E), or push(E));

     * elements[tail] is always null.

     */

    transient int tail;

    /**

     * The maximum size of array to allocate.

     * Some VMs reserve some header words in an array.

     * Attempts to allocate larger arrays may result in

     * OutOfMemoryError: Requested array size exceeds VM limit

     */

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**

     * Increases the capacity of this deque by at least the given amount.

     *

     * @param needed the required minimum extra capacity; must be positive

     */

    private void grow(int needed) {

        // overflow-conscious code

        final int oldCapacity = elements.length;

        int newCapacity;

        // Double capacity if small; else grow by 50%

        int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);

        if (jump < needed

            || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)

            newCapacity = newCapacity(needed, jump);

        final Object[] es = elements = Arrays.copyOf(elements, newCapacity);

        // Exceptionally, here tail == head needs to be disambiguated

        if (tail < head || (tail == head && es[head] != null)) {

            // wrap around; slide first leg forward to end of array

            int newSpace = newCapacity - oldCapacity;

            System.arraycopy(es, head,

                             es, head + newSpace,

                             oldCapacity - head);

            for (int i = head, to = (head += newSpace); i < to; i++)

                es[i] = null;

        }

    }

    /** Capacity calculation for edge conditions, especially overflow. */

    private int newCapacity(int needed, int jump) {

        final int oldCapacity = elements.length, minCapacity;

        if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {

            if (minCapacity < 0)

                throw new IllegalStateException("Sorry, deque too big");

            return Integer.MAX_VALUE;

        }

        if (needed > jump)

            return minCapacity;

        return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)

            ? oldCapacity + jump

            : MAX_ARRAY_SIZE;

    }

    /**

     * Constructs an empty array deque with an initial capacity

     * sufficient to hold 16 elements.

     */

    public ArrayDeque() {

        elements = new Object[16];

    }

    /**

     * Constructs an empty array deque with an initial capacity

     * sufficient to hold the specified number of elements.

     *

     * @param numElements lower bound on initial capacity of the deque

     */

    public ArrayDeque(int numElements) {

        elements =

            new Object[(numElements < 1) ? 1 :

                       (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :

                       numElements + 1];

    }

    /**

     * 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 ArrayDeque(Collection<? extends E> c) {

        this(c.size());

        addAll(c);

    }

    /**

     * Increments i, mod modulus.

     * Precondition and postcondition: 0 <= i < modulus.

     */

    static final int inc(int i, int modulus) {

        if (++i >= modulus) i = 0;

        return i;

    }

    /**

     * Decrements i, mod modulus.

     * Precondition and postcondition: 0 <= i < modulus.

     */

    static final int dec(int i, int modulus) {

        if (--i < 0) i = modulus - 1;

        return i;

    }

    /**

     * Circularly adds the given distance to index i, mod modulus.

     * Precondition: 0 <= i < modulus, 0 <= distance <= modulus.

     * @return index 0 <= i < modulus

     */

    static final int add(int i, int distance, int modulus) {

        if ((i += distance) - modulus >= 0) i -= modulus;

        return i;

    }

    /**

     * Subtracts j from i, mod modulus.

     * Index i must be logically ahead of index j.

     * Precondition: 0 <= i < modulus, 0 <= j < modulus.

     * @return the "circular distance" from j to i; corner case i == j

     */

    static final int sub(int i, int j, int modulus) {

        if ((i -= j) < 0) i += modulus;

        return i;

    }

    /**

     * Returns element at array index i.

     * This is a slight abuse of generics, accepted by javac.

     */

    @SuppressWarnings("unchecked")

    static final <E> E elementAt(Object[] es, int i) {

        return (E) es[i];

    }

    /**

     * A version of elementAt that checks for null elements.

     * This check doesn't catch all possible comodifications,

     * but does catch ones that corrupt traversal.

     */

    static final <E> E nonNullElementAt(Object[] es, int i) {

        @SuppressWarnings("unchecked") E e = (E) es[i];

        if (e == null)

            throw new ConcurrentModificationException();

        return e;

    }

    // The main insertion and extraction methods are addFirst,

    // addLast, pollFirst, pollLast. The other methods are defined in

    // terms of these.

    /**

     * Inserts the specified element at the front of this deque.

     *

     * @param e the element to add

     * @throws NullPointerException if the specified element is null

     */

    public void addFirst(E e) {

        if (e == null)

            throw new NullPointerException();

        final Object[] es = elements;

        es[head = dec(head, es.length)] = e;

        if (head == tail)

            grow(1);

    }

    /**

     * Inserts the specified element at the end of this deque.

     *

     * <p>This method is equivalent to {@link #add}.

     *

     * @param e the element to add

     * @throws NullPointerException if the specified element is null

     */

    public void addLast(E e) {

        if (e == null)

            throw new NullPointerException();

        final Object[] es = elements;

        es[tail] = e;

        if (head == (tail = inc(tail, es.length)))

            grow(1);

    }

    /**

     * Adds all of the elements in the specified collection at the end

     * of this deque, as if by calling {@link #addLast} on each one,

     *

     * @param c the elements to be inserted into this deque

     * @return {@code true} if this deque changed as a result of the call

     * @throws NullPointerException if the specified collection or any

     *         of its elements are null

     */

    public boolean addAll(Collection<? extends E> c) {

        final int s, needed;

        if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0)

            grow(needed);

        c.forEach(this::addLast);

        return size() > s;

    }

    /**

     * 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})

     * @throws NullPointerException if the specified element is null

     */

    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})

     * @throws NullPointerException if the specified element is null

     */

    public boolean offerLast(E e) {

        addLast(e);

        return true;

    }

    /**

     * @throws NoSuchElementException {@inheritDoc}

     */

    public E removeFirst() {

        E e = pollFirst();

        if (e == null)

            throw new NoSuchElementException();

        return e;

    }

    /**

     * @throws NoSuchElementException {@inheritDoc}

     */

    public E removeLast() {

        E e = pollLast();

        if (e == null)

            throw new NoSuchElementException();

        return e;

    }

    public E pollFirst() {

        final Object[] es;

        final int h;

        E e = elementAt(es = elements, h = head);

        if (e != null) {

            es[h] = null;

            head = inc(h, es.length);

        }

        return e;

    }

    public E pollLast() {

        final Object[] es;

        final int t;

        E e = elementAt(es = elements, t = dec(tail, es.length));

        if (e != null)

            es[tail = t] = null;

        return e;

    }

    /**

     * @throws NoSuchElementException {@inheritDoc}

     */

    public E getFirst() {

        E e = elementAt(elements, head);

        if (e == null)

            throw new NoSuchElementException();

        return e;

    }

    /**

     * @throws NoSuchElementException {@inheritDoc}

     */

    public E getLast() {

        final Object[] es = elements;

        E e = elementAt(es, dec(tail, es.length));

        if (e == null)

            throw new NoSuchElementException();

        return e;

    }

    public E peekFirst() {

        return elementAt(elements, head);

    }

    public E peekLast() {

        final Object[] es;

        return elementAt(es = elements, dec(tail, es.length));

    }

    /**

     * 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.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

     */

    public boolean removeFirstOccurrence(Object o) {

        if (o != null) {

            final Object[] es = elements;

            for (int i = head, end = tail, to = (i <= end) ? end : es.length;

                 ; i = 0, to = end) {

                for (; i < to; i++)

                    if (o.equals(es[i])) {

                        delete(i);

                        return true;

                    }

                if (to == end) break;

            }

        }

        return false;

    }

    /**

     * 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.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

     */

    public boolean removeLastOccurrence(Object o) {

        if (o != null) {

            final Object[] es = elements;

            for (int i = tail, end = head, to = (i >= end) ? end : 0;

                 ; i = es.length, to = end) {

                for (i--; i > to - 1; i--)

                    if (o.equals(es[i])) {

                        delete(i);

                        return true;

                    }

                if (to == end) break;

            }

        }

        return false;

    }

    // *** 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})

     * @throws NullPointerException if the specified element is null

     */

    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})

     * @throws NullPointerException if the specified element is null

     */

    public boolean offer(E e) {

        return offerLast(e);