1import collections 2 3from .cache import Cache 4 5 6class LRUCache(Cache): 7 """Least Recently Used (LRU) cache implementation.""" 8 9 def __init__(self, maxsize, missing=None, getsizeof=None): 10 Cache.__init__(self, maxsize, missing, getsizeof) 11 self.__order = collections.OrderedDict() 12 13 def __getitem__(self, key, cache_getitem=Cache.__getitem__): 14 value = cache_getitem(self, key) 15 self.__update(key) 16 return value 17 18 def __setitem__(self, key, value, cache_setitem=Cache.__setitem__): 19 cache_setitem(self, key, value) 20 self.__update(key) 21 22 def __delitem__(self, key, cache_delitem=Cache.__delitem__): 23 cache_delitem(self, key) 24 del self.__order[key] 25 26 def popitem(self): 27 """Remove and return the `(key, value)` pair least recently used.""" 28 try: 29 key = next(iter(self.__order)) 30 except StopIteration: 31 raise KeyError('%s is empty' % self.__class__.__name__) 32 else: 33 return (key, self.pop(key)) 34 35 if hasattr(collections.OrderedDict, 'move_to_end'): 36 def __update(self, key): 37 try: 38 self.__order.move_to_end(key) 39 except KeyError: 40 self.__order[key] = None 41 else: 42 def __update(self, key): 43 try: 44 self.__order[key] = self.__order.pop(key) 45 except KeyError: 46 self.__order[key] = None 47