import java.util.AbstractQueue;
import java.util.Iterator;
import java.util.concurrent.atomic.AtomicReference;

/** Queue of non-null values */
public class ConcurrentLinkedQueue<E> extends AbstractQueue<E> {
	private class Node {
		/** Never null. Content is originally non-null.
                  * The content is only from its original value to null.
		  * If the content is null, then this Node should be ignored/removed . */
		public final AtomicReference<E> element;
		/** Never null. Content is originally null.
                  * The content is only changed from null to some non-null value. */
		public final AtomicReference<Node> next = new AtomicReference<Node>(null);
		/** Precondition: element is not null */
		public Node(E element) { this.element = new AtomicReference<E>(element); }
	}
	
	/** Never null. */
	private final AtomicReference<Node> head = new AtomicReference<Node>(null);

	/** Add e to the end of the queue */
	public boolean offer(E e) {
		if (e == null)
			throw new IllegalArgumentException();
		getHead();
		Node add = new Node(e);
		AtomicReference<Node> ref = head;
		while (!ref.compareAndSet(null, add)) {
			Node node = ref.get();
			ref = node == null ? head : node.next;
		}
		return true;
	}

	/** Return the head of the queue at the time of or after being called */
	public E poll() {
		Node h = getHead();
		if (h == null)
			return null;
		E element = h.element.get();
		while (element == null || !h.element.compareAndSet(element, null)) {
			h = h.next.get();
			if (h == null)
				return null;
			element = h.element.get();
		}
		return element;
	}

	/** Return the front of the queue at the time of or after being called */
	public E peek() {
		Node h = getHead();
		if (h == null)
			return null;
		E element = h.element.get();
		while (element == null) {
			h = h.next.get();
			if (h == null)
				return null;
			element = h.element.get();
		}
		return element;
	}
	
	/** Return the head, removing unnecessary nodes when appropriate/possible. */
	protected Node getHead() {
		Node old = head.get();
		Node h = old;
		while (h != null && h.element.get() == null) {
			Node temp = h.next.get();
			if (temp == null)
				break;
			h = temp;
		}
		if (old != h) {
			if (head.compareAndSet(old, h))
				return h;
		}
		return head.get();
	}

	@Override
	public Iterator<E> iterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return 0;
	}
}