/* package whatever; // don't place package name! */

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

/* special for pr */
class ConcurrentNonBlockingQueue<T> {

    static class Node<T> {
        private volatile T obj;
        private volatile Node<T> next;

        private static final AtomicReferenceFieldUpdater<Node, Node> nextUpd = AtomicReferenceFieldUpdater.newUpdater(
                Node.class, Node.class, "next");

        private static final AtomicReferenceFieldUpdater<Node, Object> objUpd = AtomicReferenceFieldUpdater.newUpdater(
                Node.class, Object.class, "obj");

        boolean updateNext(Node<T> expected, Node<T> update) {
            return nextUpd.compareAndSet(this, expected, update);
        }

        void setObj(T obj) {
            objUpd.set(this, obj);
        }

        public Node(T obj, Node<T> next) {
            this.obj = obj;
            this.next = next;
        }

        Node<T> next() {
            return next;
        }

        T getObj() {
            return obj;
        }
    }

    private volatile Node<T> head = new Node<T>(null, null);
    private volatile Node<T> tail = head;

    private static final AtomicReferenceFieldUpdater<ConcurrentNonBlockingQueue, Node> tailUpdater = AtomicReferenceFieldUpdater
            .newUpdater(ConcurrentNonBlockingQueue.class, Node.class, "tail");

    private static final AtomicReferenceFieldUpdater<ConcurrentNonBlockingQueue, Node> headUpdater = AtomicReferenceFieldUpdater
            .newUpdater(ConcurrentNonBlockingQueue.class, Node.class, "head");

    public ConcurrentNonBlockingQueue() {}

    public boolean add(T t) {
        Node<T> newNode = new Node<T>(t, null);
        while (true) {
            Node<T> tailnode = this.tail;
            Node<T> tailnext = tailnode.next();
            if (tailnode == this.tail && tailnext == null) {
                if (tailnode.updateNext(tailnext, newNode)) {
                    this.tail = newNode;
                    return true;
                }
            }
        }
    }

    public T pop() {
        while(true) {
            Node<T> headnode = this.head;
            Node<T> tailnode = this.tail;
            Node<T> headnext = head.next();
            if ( headnode == this.head && headnode != tailnode ) {
                if ( headUpdater.compareAndSet(this, headnode, headnext) ) {
                    T obj = headnext.getObj();
                    headnext.setObj(null);
                    return obj;
                }
            } else {
                if (headnext == null)
                    return null;
                else
                    tailUpdater.compareAndSet(this, tailnode, headnext);
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {

        final AtomicInteger inc = new AtomicInteger(0);
        final ConcurrentNonBlockingQueue<Integer> queue = new ConcurrentNonBlockingQueue<Integer>();

        Thread t1 = new Thread() {
            public void run() {
                for ( int i = 0; i < 10; i++ ) {
                    queue.add(inc.incrementAndGet());
                }
            }
        };

        Thread t2 = new Thread() {
            public void run() {
                for ( int i = 0; i < 10; i++ ) {
                    queue.add(inc.incrementAndGet());
                }
            }
        };

        Thread t3 = new Thread() {
            public void run() {
                for ( int i = 0; i < 20; i++ ) {
                    System.out.println(queue.pop());
                }
            }
        };

        Thread t4 = new Thread() {
            public void run() {
                for ( int i = 0; i < 20; i++ ) {
                    System.out.println(queue.pop());
                }
            }
        };

        t1.start();
        t1.join();
        t3.start();
        t3.join();
        t4.start();
        t2.start();
    }
}