Solving Problems Using Data Structures

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Linke...

class LRUDict(dict):

    """ LRU queue with dictionary lookups based on the Python Cookbook RingBuffer recipe.
     A deque-based ringbuffer expires entries past size_max.
    Doesn't allow deletion for obvious reasons.
    """

    def __init__(self, size_max):
        dict.__init__(self)
        self.queue = deque()
        self.size_max = size_max-1

    def append(self, value):
        self.queue.append(value)
        if len(self) >= self.size_max:
            self.append = self._full_append

    def _full_append(self, value):
        self.queue.append(value)
        return super(LRUDict, self).__delitem__(self.queue.popleft())

    def __repr__(self):
        return "%s(%s)" % (self.__class__.__name__, dict.__repr__(self))

    def __setitem__(self, key, value):
        if key not in self:
            self.append(key)
        return super(LRUDict, self).__setitem__(key, value)

    def __delitem__(self, key):
        pass