package msqueue;

import kotlinx.atomicfu.AtomicRef;

public class MSQueue implements Queue {
    private AtomicRef<Node> head;
    private AtomicRef<Node> tail;

    public MSQueue() {
        Node dummy = new Node(0);
        head = new AtomicRef<>(dummy);
        tail = new AtomicRef<>(dummy);
    }

    @Override
    public void enqueue(int x) {
        Node newTail = new Node(x);
        while (true) {
            Node curTail = tail.getValue();
            if (tail.getValue().next.compareAndSet(null, newTail)) {
                tail.compareAndSet(curTail, newTail);
                break;
            } else {
                tail.compareAndSet(curTail, curTail.next.getValue());
            }
        }
    }

    @Override
    public int dequeue() {
        while (true) {
            Node curHead = head.getValue();
            Node nextHead = curHead.next.getValue();
            Node curTail = tail.getValue();
            if (curHead == curTail) {
                if (nextHead == null) {
                    return Integer.MIN_VALUE;
                } else {
                    tail.compareAndSet(curTail, curTail.next.getValue());
                }
            } else {
                if (nextHead == null) {
                    return Integer.MIN_VALUE;
                } else {
                    if (head.compareAndSet(curHead, nextHead)) {
                        return nextHead.x;
                    }
                }
            }
        }
    }

    @Override
    public int peek() {
        while (true) {
            Node curHead = head.getValue();
            Node nextHead = curHead.next.getValue();
            Node curTail = tail.getValue();
            if (curHead == curTail) {
                if (nextHead == null) {
                    return Integer.MIN_VALUE;
                } else {
                    tail.compareAndSet(curTail, curTail.next.getValue());
                }
            } else {
                if (nextHead == null) {
                    return Integer.MIN_VALUE;
                } else {
                    if (head.getValue() == curHead) {
                        return nextHead.x;
                    }
                }
            }
        }
    }

    private class Node {
        final int x;
        AtomicRef<Node> next = new AtomicRef<>(null);
        Node(int x) {
            this.x = x;
        }
    }
}