created drocks

1 files changed, 174 insertions, 0 deletions

diff --git a/source/lru.d b/source/lru.d
new file mode 100644
index 0000000..6d802df
--- /dev/null
+++ b/source/lru.d
@@ -0,0 +1,174 @@
+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);
+}