package linked_list_set;

import kotlinx.atomicfu.AtomicRef;

public class SetImpl implements Set {
    private class Node {
        int key;
        AtomicRef<NodeRemoved> NR;

        Node(int x, Node next) {
            this.key = x;
            this.NR = new AtomicRef<>(new NodeRemoved(next));
        }
    }

    private class NodeRemoved {
        final Node next;

        NodeRemoved(Node next) {
            this.next = next;
        }
    }

    private class Removed extends NodeRemoved {

        Removed(Node next) {
            super(next);
        }
    }

    private final AtomicRef<Node> head = new AtomicRef<>(new Node(Integer.MIN_VALUE, new Node(Integer.MAX_VALUE, null)));

    private class Window {
        Node nextNR;
        NodeRemoved next;

        Window(Node nextNR, NodeRemoved next) {
            this.nextNR = nextNR;
            this.next = next;
        }
    }

    /**
     * Returns the {@link Window}, where cur.x < x <= next.x
     */
    private Window findWindow(int x) {
        while (true) {
            Node cur = head.getValue();
            NodeRemoved nextNR = cur.NR.getValue();
            Node next = nextNR.next;

            while (true) {
                if (next.NR.getValue() instanceof Removed) {
                    NodeRemoved newNext = new NodeRemoved(next.NR.getValue().next);
                    if ((nextNR instanceof Removed) || cur.NR.compareAndSet(nextNR, newNext)) {
                        nextNR = newNext;
                        next = nextNR.next;
                    } else break;
                } else if (next.key >= x) {
                    if (nextNR instanceof Removed) break;
                    return new Window(cur, nextNR);
                } else {
                    cur = next;
                    nextNR = cur.NR.getValue();
                    next = nextNR.next;
                }
            }

        }
    }

    @Override
    public boolean add(int x) {
        while (true) {
            Window w = findWindow(x);
            if (w.next.next.key == x)
                return false;
            if (w.nextNR.NR.compareAndSet(w.next, new NodeRemoved(new Node(x, w.next.next))))
                return true;
        }
    }

    @Override
    public boolean remove(int x) {
        while (true) {
            Window w = findWindow(x);
            Node toRemote = w.next.next;
            NodeRemoved next = toRemote.NR.getValue();
            if (toRemote.key != x) {
                return false;
            }
            if (!(next instanceof Removed) && toRemote.NR.compareAndSet(next, new Removed(next.next))) {
                w.nextNR.NR.compareAndSet(w.next, new NodeRemoved(next.next));
                return true;
            }
        }
    }

    @Override
    public boolean contains(int x) {
        NodeRemoved toContains = findWindow(x).next;
        return !(toContains instanceof Removed) && toContains.next.key == x;
    }
}