/*

 * 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.  Sun designates this

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

 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.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 Doug Lea with assistance from members of JCP JSR-166

 * Expert Group and released to the public domain, as explained at

 * http://creativecommons.org/licenses/publicdomain

 */

package java.util.concurrent;

import java.util.AbstractQueue;

import java.util.Collection;

import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.concurrent.locks.Condition;

import java.util.concurrent.locks.ReentrantLock;

/**

 * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on

 * linked nodes.

 *

 * <p> The optional capacity bound constructor argument serves as a

 * way to prevent excessive expansion. The capacity, if unspecified,

 * is equal to {@link Integer#MAX_VALUE}.  Linked nodes are

 * dynamically created upon each insertion unless this would bring the

 * deque above capacity.

 *

 * <p>Most operations run in constant time (ignoring time spent

 * blocking).  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>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}/../technotes/guides/collections/index.html">

 * Java Collections Framework</a>.

 *

 * @since 1.6

 * @author  Doug Lea

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

 */

public class LinkedBlockingDeque<E>

    extends AbstractQueue<E>

    implements BlockingDeque<E>,  java.io.Serializable {

    /*

     * Implemented as a simple doubly-linked list protected by a

     * single lock and using conditions to manage blocking.

     *

     * To implement weakly consistent iterators, it appears we need to

     * keep all Nodes GC-reachable from a predecessor dequeued Node.

     * That would cause two problems:

     * - allow a rogue Iterator to cause unbounded memory retention

     * - cause cross-generational linking of old Nodes to new Nodes if

     *   a Node was tenured while live, which generational GCs have a

     *   hard time dealing with, causing repeated major collections.

     * However, only non-deleted Nodes need to be reachable from

     * dequeued Nodes, and reachability does not necessarily have to

     * be of the kind understood by the GC.  We use the trick of

     * linking a Node that has just been dequeued to itself.  Such a

     * self-link implicitly means to jump to "first" (for next links)

     * or "last" (for prev links).

     */

    /*

     * We have "diamond" multiple interface/abstract class inheritance

     * here, and that introduces ambiguities. Often we want the

     * BlockingDeque javadoc combined with the AbstractQueue

     * implementation, so a lot of method specs are duplicated here.

     */

    private static final long serialVersionUID = -387911632671998426L;

    /** Doubly-linked list node class */

    static final class Node<E> {

        /**

         * The item, or null if this node has been removed.

         */

        E item;

        /**

         * One of:

         * - the real predecessor Node

         * - this Node, meaning the predecessor is tail

         * - null, meaning there is no predecessor

         */

        Node<E> prev;

        /**

         * One of:

         * - the real successor Node

         * - this Node, meaning the successor is head

         * - null, meaning there is no successor

         */

        Node<E> next;

        Node(E x, Node<E> p, Node<E> n) {

            item = x;

            prev = p;

            next = n;

        }

    }

    /**

     * Pointer to first node.

     * Invariant: (first == null && last == null) ||

     *            (first.prev == null && first.item != null)

     */

    transient Node<E> first;

    /**

     * Pointer to last node.

     * Invariant: (first == null && last == null) ||

     *            (last.next == null && last.item != null)

     */

    transient Node<E> last;

    /** Number of items in the deque */

    private transient int count;

    /** Maximum number of items in the deque */

    private final int capacity;

    /** Main lock guarding all access */

    final ReentrantLock lock = new ReentrantLock();

    /** Condition for waiting takes */

    private final Condition notEmpty = lock.newCondition();

    /** Condition for waiting puts */

    private final Condition notFull = lock.newCondition();

    /**

     * Creates a {@code LinkedBlockingDeque} with a capacity of

     * {@link Integer#MAX_VALUE}.

     */

    public LinkedBlockingDeque() {

        this(Integer.MAX_VALUE);

    }

    /**

     * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.

     *

     * @param capacity the capacity of this deque

     * @throws IllegalArgumentException if {@code capacity} is less than 1

     */

    public LinkedBlockingDeque(int capacity) {

        if (capacity <= 0) throw new IllegalArgumentException();

        this.capacity = capacity;

    }

    /**

     * Creates a {@code LinkedBlockingDeque} with a capacity of

     * {@link Integer#MAX_VALUE}, initially containing the elements of

     * the given collection, added in traversal order of the

     * collection's iterator.

     *

     * @param c the collection of elements to initially contain

     * @throws NullPointerException if the specified collection or any

     *         of its elements are null

     */

    public LinkedBlockingDeque(Collection<? extends E> c) {

        this(Integer.MAX_VALUE);

        final ReentrantLock lock = this.lock;

        lock.lock(); // Never contended, but necessary for visibility

        try {

            for (E e : c) {

                if (e == null)

                    throw new NullPointerException();

                if (!linkLast(e))

                    throw new IllegalStateException("Deque full");

            }

        } finally {

            lock.unlock();

        }

    }

    // Basic linking and unlinking operations, called only while holding lock

    /**

     * Links e as first element, or returns false if full.

     */

    private boolean linkFirst(E e) {

        // assert lock.isHeldByCurrentThread();

        if (count >= capacity)

            return false;

        Node<E> f = first;

        Node<E> x = new Node<E>(e, null, f);

        first = x;

        if (last == null)

            last = x;

        else

            f.prev = x;

        ++count;

        notEmpty.signal();

        return true;

    }

    /**

     * Links e as last element, or returns false if full.

     */

    private boolean linkLast(E e) {

        // assert lock.isHeldByCurrentThread();

        if (count >= capacity)

            return false;

        Node<E> l = last;

        Node<E> x = new Node<E>(e, l, null);

        last = x;

        if (first == null)

            first = x;

        else

            l.next = x;

        ++count;

        notEmpty.signal();

        return true;

    }

    /**

     * Removes and returns first element, or null if empty.

     */

    private E unlinkFirst() {

        // assert lock.isHeldByCurrentThread();

        Node<E> f = first;

        if (f == null)

            return null;

        Node<E> n = f.next;

        E item = f.item;

        f.item = null;

        f.next = f; // help GC

        first = n;

        if (n == null)

            last = null;

        else

            n.prev = null;

        --count;

        notFull.signal();

        return item;

    }

    /**

     * Removes and returns last element, or null if empty.

     */

    private E unlinkLast() {

        // assert lock.isHeldByCurrentThread();

        Node<E> l = last;

        if (l == null)

            return null;

        Node<E> p = l.prev;

        E item = l.item;

        l.item = null;

        l.prev = l; // help GC

        last = p;

        if (p == null)

            first = null;

        else

            p.next = null;

        --count;

        notFull.signal();

        return item;

    }

    /**

     * Unlinks x.

     */

    void unlink(Node<E> x) {

        // assert lock.isHeldByCurrentThread();

        Node<E> p = x.prev;

        Node<E> n = x.next;

        if (p == null) {

            unlinkFirst();

        } else if (n == null) {

            unlinkLast();

        } else {

            p.next = n;

            n.prev = p;

            x.item = null;

            // Don't mess with x's links.  They may still be in use by

            // an iterator.

            --count;

            notFull.signal();

        }

    }

    // BlockingDeque methods

    /**

     * @throws IllegalStateException {@inheritDoc}

     * @throws NullPointerException  {@inheritDoc}

     */

    public void addFirst(E e) {

        if (!offerFirst(e))

            throw new IllegalStateException("Deque full");

    }

    /**

     * @throws IllegalStateException {@inheritDoc}

     * @throws NullPointerException  {@inheritDoc}

     */

    public void addLast(E e) {

        if (!offerLast(e))

            throw new IllegalStateException("Deque full");

    }

    /**

     * @throws NullPointerException {@inheritDoc}

     */

    public boolean offerFirst(E e) {

        if (e == null) throw new NullPointerException();

        final ReentrantLock lock = this.lock;

        lock.lock();

        try {

            return linkFirst(e);

        } finally {

            lock.unlock();

        }

    }

    /**

     * @throws NullPointerException {@inheritDoc}

     */

    public boolean offerLast(E e) {

        if (e == null) throw new NullPointerException();

        final ReentrantLock lock = this.lock;

        lock.lock();

        try {

            return linkLast(e);

        } finally {

            lock.unlock();

        }

    }

    /**

     * @throws NullPointerException {@inheritDoc}

     * @throws InterruptedException {@inheritDoc}

     */

    public void putFirst(E e) throws InterruptedException {

        if (e == null) throw new NullPointerException();

        final ReentrantLock lock = this.lock;

        lock.lock();

        try {

            while (!linkFirst(e))

                notFull.await();

        } finally {

            lock.unlock();

        }

    }

    /**

     * @throws NullPointerException {@inheritDoc}

     * @throws InterruptedException {@inheritDoc}

     */

    public void putLast(E e) throws InterruptedException {

        if (e == null) throw new NullPointerException();

        final ReentrantLock lock = this.lock;

        lock.lock();

        try {

            while (!linkLast(e))

                notFull.await();

        } finally {

            lock.unlock();

        }

    }

    /**

     * @throws NullPointerException {@inheritDoc}

     * @throws InterruptedException {@inheritDoc}

     */

    public boolean offerFirst(E e, long timeout, TimeUnit unit)

        throws InterruptedException {

        if (e == null) throw new NullPointerException();

        long nanos = unit.toNanos(timeout);

        final ReentrantLock lock = this.lock;

        lock.lockInterruptibly();

        try {

            while (!linkFirst(e)) {

                if (nanos <= 0)

                    return false;

                nanos = notFull.awaitNanos(nanos);

            }

            return true;

        } finally {

            lock.unlock();

        }

    }

    /**

     * @throws NullPointerException {@inheritDoc}

     * @throws InterruptedException {@inheritDoc}

     */

    public boolean offerLast(E e, long timeout, TimeUnit unit)

        throws InterruptedException {

        if (e == null) throw new NullPointerException();

        long nanos = unit.toNanos(timeout);

        final ReentrantLock lock = this.lock;

        lock.lockInterruptibly();

        try {

            while (!linkLast(e)) {

                if (nanos <= 0)

                    return false;

                nanos = notFull.awaitNanos(nanos);

            }

            return true;

        } finally {

            lock.unlock();

        }

    }

    /**

     * @throws NoSuchElementException {@inheritDoc}

     */

    public E removeFirst() {

        E x = pollFirst();

        if (x == null) throw new NoSuchElementException();

        return x;

    }

    /**

     * @throws NoSuchElementException {@inheritDoc}

     */

    public E removeLast() {

        E x = pollLast();

        if (x == null) throw new NoSuchElementException();

        return x;

    }

    public E pollFirst() {

        final ReentrantLock lock = this.lock;

        lock.lock();

        try {

            return unlinkFirst();

        } finally {

            lock.unlock();

        }

    }

    public E pollLast() {

        final ReentrantLock lock = this.lock;

        lock.lock();

        try {

            return unlinkLast();

        } finally {

            lock.unlock();

        }

    }

    public E takeFirst() throws InterruptedException {

        final ReentrantLock lock = this.lock;

        lock.lock();

        try {

            E x;

            while ( (x = unlinkFirst()) == null)

                notEmpty.await();

            return x;

        } finally {

            lock.unlock();

        }

    }

    public E takeLast() throws InterruptedException {

        final ReentrantLock lock = this.lock;

        lock.lock();

        try {

            E x;

            while ( (x = unlinkLast()) == null)

                notEmpty.await();

            return x;

        } finally {

            lock.unlock();

        }

    }

    public E pollFirst(long timeout, TimeUnit unit)

        throws InterruptedException {

        long nanos = unit.toNanos(timeout);

        final ReentrantLock lock = this.lock;

        lock.lockInterruptibly();

        try {

            E x;

            while ( (x = unlinkFirst()) == null) {

                if (nanos <= 0)

                    return null;

                nanos = notEmpty.awaitNanos(nanos);