sentinal = object()
class LRU(object):
    """
    Implementation of a length-limited O(1) LRU queue.
    Built for and used by PyPE:
    http://pype.sourceforge.net
    Copyright 2003 Josiah Carlson.
    """
    def __init__(self, count, pairs=[]):
        self.count = max(count, 2)
        self.d = {}

        self.first = None
        self.last = None

        for key, value in pairs:
            self[key] = value

    def __contains__(self, obj):
        return obj in self.d

    def _to_front(self, node):
        if node.prev:
            node.prev.next = node.next

            if node.next:
                node.next.prev = node.prev

            node.next = self.first
        node.prev = None
        self.first = node
        
    def __getitem__(self, obj):
        node = self.d[obj]
        self._to_front(node)
        return node.me[1]

    def __setitem__(self, key, val):
        d = self.d
        node = d.get(key, sentinal)
        if node is not sentinal:
            node.me = (key, val)
        else:
            node = Node(None, (key, val))
            d[key] = node

        self._to_front(node)

        if len(d) > self.count:
            self._remove(self.last)

    def _remove(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.first = node.next

        if node.next:
            node.next.prev = node.prev
        else:
            self.last = node.prev

        del self.d[node.me[0]]
        
    def __delitem__(self, key):
        node = self.d[key]
        self._remove(node)

    def __iter__(self):
        cur = self.first
        while cur != None:
            cur2 = cur.next
            yield cur.me[1]
            cur = cur2
    def iteritems(self):
        cur = self.first
        while cur != None:
            cur2 = cur.next
            yield cur.me
            cur = cur2
    def iterkeys(self):
        return iter(self.d)
    def itervalues(self):
        for i,j in self.iteritems():
            yield j
    def keys(self):
        return self.d.keys()