# -*- Mode: Cython -*-

# LRU implemented with dict + stl-map

from cython.operator cimport dereference as deref, preincrement as inc
from libc.stdint cimport uint64_t
from libcpp.utility cimport pair
from libcpp.map cimport map
from cpython.ref cimport Py_INCREF, Py_XDECREF, PyObject

class UNIQUE:
    pass

cdef class lru:

    "lru implemented with dict + stl map"

    cdef int size
    cdef uint64_t counter
    cdef map[uint64_t, PyObject *] * t
    cdef dict d

    def __init__ (self, size=100):
        self.size = size
        self.d = {}
        # monotonically increasing counter,
        # used as a 'timestamp' to order entries in the LRU
        self.counter = 0L

    def __cinit__(self):
        self.t = new map[uint64_t, PyObject*]()

    def __dealloc__ (self):
        cdef map[uint64_t, PyObject*].iterator it = self.t.begin()
        while it != self.t.end():
            Py_XDECREF(deref(it).second)
            inc(it)
        del self.t

    def keys (self):
        return self.d.keys()

    def items (self):
        return [ (key, val) for key, (pos, val) in self.d.items() ]

    def __iter__ (self):
        l = [ (val, key) for key, val in self.d.items() ]
        l.sort()
        l.reverse()
        for (pos, val), key in l:
            yield (key, val)

    def empty (self, new_size=0):
        self.d = {}
        self.t = new map[uint64_t, PyObject*]()
        self.counter = 0L
        if new_size:
            self.size = new_size

    def __len__ (self):
        return len(self.d)

    def has_key (self, key):
        return self.d.has_key (key)

    def get (self, key, instead):
        r = self.d.get (key, instead)
        if r is instead:
            return r
        else:
            return r[1]

    def __getitem__ (self, key):
        cdef map[uint64_t, PyObject*].iterator it
        cdef pair[uint64_t, PyObject*] p
        cdef uint64_t pos
        entry = self.d.get (key, UNIQUE)
        if entry is UNIQUE:
            raise KeyError, key
        else:
            # cache hit
            (pos, val) = entry
            it = self.t.find (pos)
            Py_XDECREF (deref(it).second)
            self.t.erase (it)
            self.counter += 1
            pos = self.counter
            p.first, p.second = pos, <PyObject*> key
            self.t.insert (p)
            Py_INCREF (key)
            self.d[key] = ((pos, val))
            return val

    def __setitem__ (self, key, val):
        cdef map[uint64_t, PyObject*].iterator it
        cdef pair[uint64_t, PyObject*] p
        cdef uint64_t pos
        if self.d.has_key (key):
            # remove previous key...
            (pos, _) = self.d[key]
            it = self.t.find (pos)
            Py_XDECREF (deref(it).second)
            self.t.erase (it)
        elif self.t.size() == self.size:
            # remove the oldest key...
            it = self.t.begin()
            del self.d[<object>(deref(it).second)]
            Py_XDECREF (deref(it).second)
            self.t.erase (it)
        self.counter += 1
        pos = self.counter
        p.first, p.second = pos, <PyObject*> key
        self.t.insert (p)
        Py_INCREF (key)
        self.d[key] = ((pos, val))

    def __delitem__ (self, key):
        cdef map[uint64_t, PyObject*].iterator it
        if self.d.has_key (key):
            pos, ignore = self.d[key]
            it = self.t.find (pos)
            Py_XDECREF (deref(it).second)
            self.t.erase (it)
            del self.d[key]
        else:
            raise KeyError, key