package linked_list_set;

import kotlinx.atomicfu.AtomicRef;

public class SetImpl implements Set {

    private class Node {
        AtomicRef<Node> next;
        int x;
        Node() {}

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

    }

    private class Removed extends Node {
        Node realNext;
        Removed(Node other) {
            this.realNext = other;
        }
    }

    private class Window {
        Node cur;
        Node next;
        Window(Node cur, Node next) {
            this.cur = cur;
            this.next = next;
        }
    }

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

    /**
     * Returns the {@link Window}, where cur.x < x <= next.x
     */
    private Window findWindow(int x) {
        point: while (true) {
            Node cur = head;
            Node next = cur.next.getValue();
            if (next instanceof Removed) {
                next = ((Removed) next).realNext;
            }
            while (next.x < x) {
                Node node = next.next.getValue();
                if (node instanceof Removed) {
                    if (!cur.next.compareAndSet(next, ((Removed) node).realNext)) {
                        continue point;
                    }
                    next = ((Removed) node).realNext;
                } else {
                    cur = next;
                    next = cur.next.getValue();
                    if (next instanceof Removed) {
                        next = ((Removed) next).realNext;
                    }
                }
            }
            Node node = next.next.getValue();
            if (node instanceof Removed) {
                cur.next.compareAndSet(next, ((Removed) node).realNext);
                continue;
            }
            return new Window(cur, next);
        }
    }


    @Override
    public boolean add(int x) {
        while (true) {
            Window w = findWindow(x);
            if (w.next.x == x) {
                return false;
            } else {
                Node newNode = new Node(x, w.next);
                if (w.cur.next.compareAndSet(w.next, newNode)) {
                    return true;
                }
            }
        }
    }

    @Override
    public boolean remove(int x) {
        while (true) {
            Window w = findWindow(x);
            if (w.next.x != x)  {
                return false;
            } else {
                Node nextNext = w.next.next.getValue();
                if (nextNext instanceof Removed) {
                    nextNext = ((Removed) nextNext).realNext;
                }
                if (w.next.next.compareAndSet(nextNext, new Removed(nextNext))) {
                    w.cur.next.compareAndSet(w.next, nextNext);
                    return true;
                }
            }
        }
    }

    @Override
    public boolean contains(int x) {
        Window w = findWindow(x);
        return w.next.x == x;
    }
}