lru.py

__all__ = ["DEFAULT_SIZE", "cache"]

DEFAULT_SIZE = 1024


class _cachedobject(object):
    __slots__ = ["prev", "key", "value", "next"]
    def __init__(self, **kwargs):
        for k, v in kwargs.iteritems():
            setattr(self, k, v)


class cache(object):
    def __init__(self, size=DEFAULT_SIZE):
        self._size = size
        self._head = None
        self._objs = {}

    def _put(self, key, item):
        head = self._head
        if head is None:
            item.prev = item.next = item
        else:
            tail = head.prev
            item.next = head
            item.prev = tail
            tail.next = head.prev = item
        self._head = item
        self._objs[key] = item

    def _remove(self, key):
        item = self._objs.get(key)
        if item is None:
            return None

        prev = item.prev
        next = item.next

        prev.next = next
        next.prev = prev

        item.prev = item.next = None
        del self._objs[key]

        return item

    def __getitem__(self, key):
        item = self._remove(key)
        if item is None:
            return item

        self._put(key, item)

        return item.value

    def __setitem__(self, key, value):
        old_item = self._remove(key)
        new_item = _cachedobject(key=key, value=value)
        if old_item is None:
            self._put(key, new_item)

            for i in xrange(len(self._objs) - self._size):
                tail = self._head.prev
                self._remove(tail.key)
        else:
            self._put(key, new_item)

    def __contains__(self, key):
        return key in self._objs

    def __repr__(self):
        if not self._head:
            return "{}"

        lst = ["{%r: %r" % (self._head.key, self._head.value)]
        head_key = self._head.key
        current = self._head.next
        while current.key != head_key: 
            lst.append(", %r: %r" % (current.key, current.value))
            current = current.next
        lst.append("}")
        return "".join(lst)

    __str__ = __unicode__ = __repr__