import java.util.NoSuchElementException;
import java.util.concurrent.atomic.AtomicReference;

public class LockFreeQueue<T> implements MyQueue<T> {
  private AtomicReference<Node> head;
  private AtomicReference<Node> tail;

  public LockFreeQueue() {
    Node sentinel = new Node(null);
    this.head = new AtomicReference<Node>(sentinel);
    this.tail = new AtomicReference<Node>(sentinel);
  }

  public void enq(T item) {
    if (item == null) throw new NullPointerException();

    Node node = new Node(item);

    while (true) {
      Node last = tail.get();
      Node next = last.next.get();
      if (last == tail.get()) {
        AtomicReference[] target = {last.next, tail};
        Object[] expect = {next, last};
        Object[] update = {node, node};

        if (multiCompareAndSet(
            (AtomicReference<T>[]) target,
            (T[]) expect,
            (T[]) update)){
          return;
        }
      }
    }
  }

  public T deq() throws NoSuchElementException {
    while (true) {
      Node first = head.get();
      Node last = tail.get();
      Node next = first.next.get();
      if (first == head.get()) {
        if (first == last) {
          if (next == null) {
            throw new NoSuchElementException();
          }
          tail.compareAndSet(last, next);
        } else {
          T value = next.value;
          if (head.compareAndSet(first, next))
            return value;
        }
      }
    }
  }

  public class Node {
    public T value;
    public AtomicReference<Node> next;

    public Node(T value) {
      this.value = value;
      this.next  = new AtomicReference<Node>(null);
    }
  }
  private static <T> boolean multiCompareAndSet(
      AtomicReference<T>[] target,
      T[] expect,
      T[] update) {

          if (target[0].compareAndSet(expect[0], update[0])) {
                  if (target[1].compareAndSet(expect[1], update[1])) {
                          return true;
                  } else {
                          target[0].compareAndSet(update[0], expect[0]);
                          //System.out.println("Bad?");
                          return false;
                  }
          } else {
                  //System.out.println("Failed.");
                  return false;
          }
  }

  public static void main(String [] args) {
          int runs = 10;
          int numThreads = 6;
          int numIterations = 120000;

          double runtimes[] = new double[runs];


        //If command line argument present, gives patience in seconds.
        if (args.length > 0) {
            try {
                runs = Integer.parseInt(args[0].trim());
                numThreads = Integer.parseInt(args[1].trim());
                numIterations = Integer.parseInt(args[2].trim());
                System.out.format("Runs = %d, NumThreads = %d, NumIterations = %d\n", runs, numThreads, numIterations);
            } catch (NumberFormatException e) {
                System.err.println("Argument must be an integer.");
                System.exit(1);
            }
        }


          for (int i = 0; i < runs; ++i) {
                  MyQueue<Integer> que = new LockFreeQueue<Integer>();
                  QueueTester tester = new QueueTester(que);
                  runtimes[i] = tester.runTest(numThreads, numIterations);

                  //System.out.println("Run time (" + (i + 1) + "): " + runtimes[i] + "s");
          }
          double totalRuntime = 0;
          for (int i = 0; i < runs; ++i) {
                  totalRuntime += runtimes[i];
          }

          System.out.println("Average runtime of " + runs + " runs: " + (totalRuntime / runs) + "s");
  }
}