import std.array : appender;

private struct Node(T) {
    Node!T* prev;
    Node!T* next;
    T data;
}

private struct List(T) {
    Node!T* head;
    Node!T* tail;
    size_t length;

    invariant () {
        if (length > 0) {
            assert(head !is null);
            assert(tail !is null);
        }
    }

    /*private void check()
    {
        Node!T* cur = head;
        while (true)
        {
            if (cur != head)
                assert(cur.prev);
            if (cur == tail)
                break;
            else
                assert(cur.next);
            cur = cur.next;
        }
    }*/

    void remove(Node!T* n) {
        if (n.next)
            n.next.prev = n.prev;
        if (n.prev)
            n.prev.next = n.next;
        if (head == n)
            head = head.next;
        if (tail == n)
            tail = tail.prev;
        length--;
    }

    void push(Node!T* n) {
        n.prev = null;
        n.next = head;
        head = n;
        if (tail is null)
            tail = head;
        else
            head.next.prev = head;
        length++;
    }

    Node!T* pop()
    in {
        assert(tail);
    }
    do {
        Node!T* node = tail;
        remove(node);
        return node;
    }

}

unittest {
    List!int l;
    Node!int first;
    l.push(&first);
    assert(l.head == &first);
    assert(l.tail == &first);
    Node!int second;
    l.push(&second);
    assert(l.head == &second);
    assert(l.tail == &first);
    assert(l.pop() == &first);
    assert(l.head == &second);
    assert(l.tail == &second);
    l.push(&first);
    l.pop();
    l.pop();
}

class LRUCache(From, To) {
    private size_t _cap;
    private struct Record {
        To val;
        From key;
    }

    private Node!Record*[From] map;
    private List!Record queue;
    this(size_t cap) {
        _cap = cap;
    }

    private void checksz() {
        if (queue.length > _cap) {
            auto node = queue.pop();
            map.remove(node.data.key);
        }
    }

    bool opBinaryRight(string op : "in")(From key) {
        return cast(bool)(key in map);
    }

    To opIndex(From f)
    in {
        assert(f in map);
    }
    do {
        auto p = map[f];
        queue.remove(p);
        queue.push(p);
        return p.data.val;
    }

    void opIndexAssign(To t, From f) {
        auto p = f in map;
        Node!Record* node;
        bool alloc = p is null;
        if (!alloc) {
            queue.remove(*p);
            node = *p;
        } else
            node = new Node!Record();
        node.data.val = t;
        node.data.key = f;
        queue.push(node);
        map[f] = node;
        if (alloc)
            checksz();
    }
}

unittest {
    auto cache = new LRUCache!(int, int)(2);
    cache[0] = 1;
    cache[4] = 2;
    cache[5] = 1;
    assert(0 !in cache);
    assert(4 in cache);
    assert(5 in cache);
    assert(cache[5] == 1); // prioritizes
    cache[0] = 1;
    assert(4 !in cache);
}