import java.util.AbstractQueue;

import java.util.ArrayList;

import java.util.Collection;

import java.util.Iterator;

import java.util.NoSuchElementException;

import java.util.Queue;

 * A {@code ConcurrentLinkedQueue} is an appropriate choice when

 * This queue does not permit {@code null} elements.

 * <p>Beware that, unlike in most collections, the {@code size} method

     * This is a modification of the Michael & Scott algorithm,

     * adapted for a garbage-collected environment, with support for

     * interior node deletion (to support remove(Object)).  For

     * explanation, read the paper.

     * Note that like most non-blocking algorithms in this package,

     * this implementation relies on the fact that in garbage

     *

     * The fundamental invariants are:

     * - There is exactly one (last) Node with a null next reference,

     *   which is CASed when enqueueing.  This last Node can be

     *   reached in O(1) time from tail, but tail is merely an

     *   optimization - it can always be reached in O(N) time from

     *   head as well.

     * - The elements contained in the queue are the non-null items in

     *   Nodes that are reachable from head.  CASing the item

     *   reference of a Node to null atomically removes it from the

     *   queue.  Reachability of all elements from head must remain

     *   true even in the case of concurrent modifications that cause

     *   head to advance.  A dequeued Node may remain in use

     *   indefinitely due to creation of an Iterator or simply a

     *   poll() that has lost its time slice.

     *

     * The above might appear to imply that all Nodes are 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.

     *

     * Both head and tail are permitted to lag.  In fact, failing to

     * update them every time one could is a significant optimization

     * (fewer CASes). This is controlled by local "hops" variables

     * that only trigger helping-CASes after experiencing multiple

     * lags.

     *

     * Since head and tail are updated concurrently and independently,

     * it is possible for tail to lag behind head (why not)?

     *

     * CASing a Node's item reference to null atomically removes the

     * element from the queue.  Iterators skip over Nodes with null

     * items.  Prior implementations of this class had a race between

     * poll() and remove(Object) where the same element would appear

     * to be successfully removed by two concurrent operations.  The

     * method remove(Object) also lazily unlinks deleted Nodes, but

     * this is merely an optimization.

     *

     * When constructing a Node (before enqueuing it) we avoid paying

     * for a volatile write to item by using lazySet instead of a

     * normal write.  This allows the cost of enqueue to be

     * "one-and-a-half" CASes.

     *

     * Both head and tail may or may not point to a Node with a

     * non-null item.  If the queue is empty, all items must of course

     * be null.  Upon creation, both head and tail refer to a dummy

     * Node with null item.  Both head and tail are only updated using

     * CAS, so they never regress, although again this is merely an

     * optimization.

        Node(E item) {

            // Piggyback on imminent casNext()

            lazySetItem(item);

        }

            return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);

            item = val;

        }

        void lazySetItem(E val) {

            UNSAFE.putOrderedObject(this, itemOffset, val);

        }

        void lazySetNext(Node<E> val) {

            UNSAFE.putOrderedObject(this, nextOffset, val);

            return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);

        // Unsafe mechanics

        private static final sun.misc.Unsafe UNSAFE =

            sun.misc.Unsafe.getUnsafe();

        private static final long nextOffset =

            objectFieldOffset(UNSAFE, "next", Node.class);

        private static final long itemOffset =

            objectFieldOffset(UNSAFE, "item", Node.class);

    /**

     * A node from which the first live (non-deleted) node (if any)

     * can be reached in O(1) time.

     * Invariants:

     * - all live nodes are reachable from head via succ()

     * - head != null

     * - (tmp = head).next != tmp || tmp != head

     * Non-invariants:

     * - head.item may or may not be null.

     * - it is permitted for tail to lag behind head, that is, for tail

     *   to not be reachable from head!

     */

    private transient volatile Node<E> head = new Node<E>(null);

     * A node from which the last node on list (that is, the unique

     * node with node.next == null) can be reached in O(1) time.

     * Invariants:

     * - the last node is always reachable from tail via succ()

     * - tail != null

     * Non-invariants:

     * - tail.item may or may not be null.

     * - it is permitted for tail to lag behind head, that is, for tail

     *   to not be reachable from head!

     * - tail.next may or may not be self-pointing to tail.

     * Creates a {@code ConcurrentLinkedQueue} that is initially empty.

     * Creates a {@code ConcurrentLinkedQueue}

     * @return {@code true} (as specified by {@link Collection#add})

     * We don't bother to update head or tail pointers if fewer than

     * HOPS links from "true" location.  We assume that volatile

     * writes are significantly more expensive than volatile reads.

     */

    private static final int HOPS = 1;

    /**

     * Try to CAS head to p. If successful, repoint old head to itself

     * as sentinel for succ(), below.

     */

    final void updateHead(Node<E> h, Node<E> p) {

        if (h != p && casHead(h, p))

            h.lazySetNext(h);

    }

    /**

     * Returns the successor of p, or the head node if p.next has been

     * linked to self, which will only be true if traversing with a

     * stale pointer that is now off the list.

     */

    final Node<E> succ(Node<E> p) {

        Node<E> next = p.getNext();

        return (p == next) ? head : next;

    }

    /**

     * @return {@code true} (as specified by {@link Queue#offer})

        Node<E> n = new Node<E>(e);

        retry:

            Node<E> p = t;

            for (int hops = 0; ; hops++) {

                Node<E> next = succ(p);

                if (next != null) {

                    if (hops > HOPS && t != tail)

                        continue retry;

                    p = next;

                } else if (p.casNext(null, n)) {

                    if (hops >= HOPS)

                        casTail(t, n);  // Failure is OK.

                    return true;

                    p = succ(p);

        Node<E> h = head;

        Node<E> p = h;

        for (int hops = 0; ; hops++) {

            E item = p.getItem();

            if (item != null && p.casItem(item, null)) {

                if (hops >= HOPS) {

                    Node<E> q = p.getNext();

                    updateHead(h, (q != null) ? q : p);

                return item;

            Node<E> next = succ(p);

            if (next == null) {

                updateHead(h, p);

                break;

            }

            p = next;

        return null;

    public E peek() {

        Node<E> h = head;

        Node<E> p = h;

        E item;

            item = p.getItem();

            if (item != null)

                break;

            Node<E> next = succ(p);

            if (next == null) {

                break;

            p = next;

        updateHead(h, p);

        return item;

     * Returns the first live (non-deleted) node on list, or null if none.

     * This is yet another variant of poll/peek; here returning the

     * first node, not element.  We could make peek() a wrapper around

     * first(), but that would cost an extra volatile read of item,

     * and the need to add a retry loop to deal with the possibility

     * of losing a race to a concurrent poll().

        Node<E> h = head;

        Node<E> p = h;

        Node<E> result;

            E item = p.getItem();

            if (item != null) {

                result = p;

                break;

            Node<E> next = succ(p);

            if (next == null) {

                result = null;

                break;

            }

            p = next;

        updateHead(h, p);

        return result;

     * Returns {@code true} if this queue contains no elements.

     * @return {@code true} if this queue contains no elements

     * contains more than {@code Integer.MAX_VALUE} elements, returns

     * {@code Integer.MAX_VALUE}.

        for (Node<E> p = first(); p != null; p = succ(p)) {

     * Returns {@code true} if this queue contains the specified element.

     * More formally, returns {@code true} if and only if this queue contains

     * at least one element {@code e} such that {@code o.equals(e)}.

     * @return {@code true} if this queue contains the specified element

        for (Node<E> p = first(); p != null; p = succ(p)) {

     * if it is present.  More formally, removes an element {@code e} such

     * that {@code o.equals(e)}, if this queue contains one or more such

     * Returns {@code true} if this queue contained the specified element

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

        Node<E> pred = null;

        for (Node<E> p = first(); p != null; p = succ(p)) {

                p.casItem(item, null)) {

                Node<E> next = succ(p);

                if (pred != null && next != null)

                    pred.casNext(p, next);

            }

            pred = p;

        for (Node<E> p = first(); p != null; p = succ(p)) {