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 curTail = tail.getValue();
            int enqIdx = tail.getValue().enqIdx.getAndAdd(1);
            if (enqIdx >= NODE_SIZE) {
                Node newTail = new Node(x);
                if (curTail.next.compareAndSet(null, newTail)) {
                    if (tail.compareAndSet(curTail, newTail)) {
                        //
                        //System.out.println(333);
                        return;
                    }
                    //return;
                }
//                Node newTail = new Node(x);
//                this.tail.getValue().next.setValue(newTail);
//                this.tail.setValue(newTail);
//                return;
            } else {
                //if (tail.getValue().data.get(enqIdx).compareAndSet(null, x)) {
                if (curTail.data.get(enqIdx).compareAndSet(null, x)) {
                    return;
                }
            }
        }
//        int enqIdx = tail.getValue().enqIdx++;
//        if (enqIdx >= NODE_SIZE) {
//            Node newTail = new Node(x);
//            this.tail.getValue().next = newTail;
//            this.tail.setValue(newTail);
//            return;
//        }
//        this.tail.getValue().data[enqIdx] = x;
    }

    @Override
    public T dequeue() {
        while (true) {
            Node curHead = head.getValue();
            if (curHead.isEmpty()) {
                Node curHeadNext = curHead.next.getValue();
                if (curHeadNext == null) {
                    return null;
                }
                if (head.compareAndSet(curHead, curHeadNext)) {
                    //System.out.println(222);
                }
            } else {
                int deqIdx = head.getValue().deqIdx.getAndAdd(1);
                if (deqIdx >= NODE_SIZE) {
                    continue;
                }
                Object res = head.getValue().data.get(deqIdx).getAndSet(DONE);
                if (res == null) {
                    continue;
                }
                return (T) res;
            }
        }
//        while (true) {
//            if (this.head.getValue().isEmpty()) {
//                if (this.head.getValue().next == null) return null;
//                this.head.setValue(this.head.getValue().next);
//                continue;
//            }
//            int deqIdx = this.head.getValue().deqIdx++;
//            Object res = head.getValue().data[deqIdx];
//            head.getValue().data[deqIdx] = DONE;
//            return (T) res;
//        }
    }

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

        private AtomicRef<Node> next = new AtomicRef<>(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 AtomicArray<Object> data = new AtomicArray<>(NODE_SIZE);

        Node() {
        }

        Node(Object x) {
            enqIdx.setValue(1);
            data.get(0).setValue(x);
        }

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