package faaqueue;

import kotlinx.atomicfu.*;

import java.sql.PreparedStatement;
import java.util.ArrayList;

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();
            Node tailNext = curTail.next.getValue();
            if (tailNext != null) {
                tail.compareAndSet(curTail, tailNext);
                continue;
            }
            int enqIdx = curTail.enqIdx.getAndIncrement();
            if (enqIdx >= NODE_SIZE) {
                Node newTail = new Node(x);
                Node curT = tail.getValue();
                Node Tnext = curT.next.getValue();
                if (curT == tail.getValue()) {
                    if (Tnext == null) {
                        if (tail.getValue().next.compareAndSet(null, newTail)) {
                            break;
                        }
                    } else {
                        tail.compareAndSet(curT, Tnext);
                    }
                }
            } else {
                if (curTail.data.get(enqIdx).compareAndSet(null, x)) {
                    return;
                }
            }
        }
    }

    @Override
    public T dequeue() {
        while (true) {
            Node curHead = head.getValue();
            if (curHead.isEmpty()) {
                Node headNext = curHead.next.getValue();
                if (headNext == null)
                    return null;
                head.compareAndSet(curHead, headNext);
            } else {
                int deqInd = head.getValue().deqIdx.getAndIncrement();
                if (deqInd >= NODE_SIZE) continue;
                Object res = curHead.data.get(deqInd).getAndSet(DONE);
                if (res != null) {
                    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 ArrayList<AtomicRef<Object>> data = new ArrayList<>();

        Node() {
            for (int i = 0; i < NODE_SIZE; i++)
                data.add(new AtomicRef<>(null));
        }

        Node(Object x) {
            for (int i = 0; i < NODE_SIZE; i++)
                data.add(new AtomicRef<>(null));
            this.enqIdx.setValue(1);
            this.data.get(0).setValue(x);
        }

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