package faaqueue;

import kotlinx.atomicfu.*;

import static faaqueue.FAAQueue.Node.NODE_SIZE;


public class FAAQueue<T> implements Queue<T> {
    private static final Object DONE = new Object(); // Marker for the "DONE" slot state; to avoid memory leaks

    private AtomicRef<Node> head; // Head pointer, similarly to the Michael-Scott queue (but the first node is _not_ sentinel)
    private AtomicRef<Node> tail; // Tail pointer, similarly to the Michael-Scott queue

    public FAAQueue() {
        Node firstNode = new Node();
        head = new AtomicRef<>(firstNode);
        tail = new AtomicRef<>(firstNode);
    }

    @Override
    public void enqueue(T x) {
        while (true) {
            Node oldTail = tail.getValue();
            int enqIdx = oldTail.enqIdx.getAndAdd(1);
            if (enqIdx >= NODE_SIZE) {
                Node newTail = new Node(x);
                this.tail.getValue().next = newTail;
                this.tail.setValue(newTail);
                return;
            } else {
                System.
                if (oldTail.data[enqIdx].compareAndSet(null, x)) {
                    return;
                }
            }
        }
    }

    @Override
    public T dequeue() {
        while (true) {
            Node oldHead = this.head.getValue();
            if (oldHead.isEmpty()) {
                Object headNext = oldHead.next;
                if (headNext == null) return null;
                this.head.compareAndSet(oldHead, (Node) headNext);
            } else {
                int deqIdx = oldHead.deqIdx.getAndAdd(1);
                if (deqIdx >= NODE_SIZE) continue;
                Object res = oldHead.data[deqIdx].getAndSet(DONE);
                if (res == null) continue;
                return (T) res;
            }
        }
    }

    static class Node {
        static final int NODE_SIZE = 2; // CHANGE ME FOR BENCHMARKING ONLY

        private Node next = null;
        private AtomicInt enqIdx = new AtomicInt(0); // index for the next enqueue operation
        private AtomicInt deqIdx = new AtomicInt(0); // index for the next dequeue operation
        private final AtomicRef[] data = new AtomicRef[NODE_SIZE];

        Node() {}

        Node(Object x) {
            this.enqIdx = new AtomicInt(1);
            this.data[0] = new AtomicRef<>(x);
        }

        private boolean isEmpty() {
            return this.deqIdx.getValue() >= this.enqIdx.getValue() || this.deqIdx.getValue() >= NODE_SIZE;
        }
    }
}