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 advance to head.
     */

    /*
     * 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.
        */
        // 1
	    E item;

        /**
         * One of:
         * - the real predecessor Node
         * - this Node, meaning the predecessor is tail
         * - null, meaning there is no predecessor
         */
        // 2
        Node<E> prev;

        /**
         * One of:
         * - the real successor Node
         * - this Node, meaning the successor is head
         * - null, meaning there is no successor
         */
        // 3
        Node<E> next;
        Node(E x, Node<E> p, Node<E> n) {
            item = x;
            prev = p;
            next = n;
        }
    }

    /** Pointer to first node */
    // 4
    transient Node<E> first;
    /** Pointer to last node */
    // 5
    transient Node<E> last;
    /** Number of items in the deque */
    // 6
    private transient int count;
    /** Maximum number of items in the deque */
    // 7
    private final int capacity;
    /** Main lock guarding all access */
    // 8
    final ReentrantLock lock = new ReentrantLock();
    /** Condition for waiting takes */
    // 9
    private final Condition notEmpty = lock.newCondition();
    /** Condition for waiting puts */
    // 10
    private final Condition notFull = lock.newCondition();

    /**
     * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
     * {@link Integer#MAX_VALUE}.
     */
    // 11
    public LinkedBlockingDeque() {
        this(Integer.MAX_VALUE);
    }

    /**
     * Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed) capacity.
     *
     * @param capacity the capacity of this deque
     * @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
     */
    public LinkedBlockingDeque(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
    }

/**
 * Links e as first element, or returns false if full.
 */
private boolean linkFirst(E e) {
    // assert lock.isHeldByCurrentThread();
    // 1
    if (count >= capacity)
        return false;
    Node<E> f = first;
    // 2
    Node<E> x = new Node<E>(e, null, f);
    // 3
    first = x;
    if (last == null)
        // 4
        last = x;
    else
        // 5
        f.prev = x;
    // 6
    ++count;
    // 7
    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;
    // 1
    Node<E> x = new Node<E>(e, l, null);
    last = x;
    if (first == null)
        // 2
        first = x;
    else
        // 3
        l.next = x;
    // 4
    ++count;
    // 5
    notEmpty.signal();
    return true;
}

/**
 * Removes and returns first element, or null if empty.
 */
private E unlinkFirst() {
    // assert lock.isHeldByCurrentThread();
    // 1
    Node<E> f = first;
    // 2
    if (f == null)
        return null;
    // 3
    Node<E> n = f.next;
    // 4
    E item = f.item;
    // 5
    f.item = null;
    // 6
    f.next = f; // help GC
    // 7
    first = n;
    if (n == null)
        // 8
        last = null;
    else
        // 9
        n.prev = null;
    // 10
    --count;
    // 11
    notFull.signal();
    // 12
    return item;
}

/**
 * Removes and returns last element, or null if empty.
 */
private E unlinkLast() {
    // assert lock.isHeldByCurrentThread();
    // 1
    Node<E> l = last;
    // 2
    if (l == null)
        return null;
    // 3
    Node<E> p = l.prev;
    // 4
    E item = l.item;
    // 5
    l.item = null;
    // 6
    l.prev = l; // help GC
    // 7
    last = p;
    if (p == null)
        // 8
        first = null;
    else
        // 9
        p.next = null;
    // 10
    --count;
    // 11
    notFull.signal();
    // 12
    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) {
       // 1
       unlinkFirst();
    } else if (n == null) {
      // 2
      unlinkLast();
    } else {
        // 3
        p.next = n;
        // 4
        n.prev = p;
        // 5
        x.item = null;
        // Don't mess with x's links. They may still be in use by
        // an iterator.
        // 6
        --count;
        // 7
        notFull.signal();
    }
}

/**
 * @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 {
        // 1
        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 {
        // 1
        while (!linkLast(e))
            notFull.await();
    } finally {
        lock.unlock();
    }
}

public E takeFirst() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            E x;
            // 1
            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;
            // 1
            while ( (x = unlinkLast()) == null)
                notEmpty.await();
            return x;
        } finally {
            lock.unlock();
        }
    }

/**
     * Returns an iterator over the elements in this deque in proper sequence.
     * The elements will be returned in order from first (head) to last (tail).
     * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
     * will never throw {@link ConcurrentModificationException},
     * and guarantees to traverse elements as they existed upon
     * construction of the iterator, and may (but is not guaranteed to)
     * reflect any modifications subsequent to construction.
     *
     * @return an iterator over the elements in this deque in proper sequence
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

/** Forward iterator */
private class Itr extends AbstractItr {
    Node<E> firstNode() { return first; }
    Node<E> nextNode(Node<E> n) { return n.next; }
}