41 lines
1.2 KiB
Python
41 lines
1.2 KiB
Python
|
import collections
|
||
|
|
|
||
|
|
from .cache import Cache
|
||
|
|
|
||
|
|
|
||
|
|
class LRUCache(Cache):
|
||
|
|
"""Least Recently Used (LRU) cache implementation."""
|
||
|
|
|
||
|
|
def __init__(self, maxsize, getsizeof=None):
|
||
|
|
Cache.__init__(self, maxsize, getsizeof)
|
||
|
|
self.__order = collections.OrderedDict()
|
||
|
|
|
||
|
|
def __getitem__(self, key, cache_getitem=Cache.__getitem__):
|
||
|
|
value = cache_getitem(self, key)
|
||
|
|
self.__update(key)
|
||
|
|
return value
|
||
|
|
|
||
|
|
def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
|
||
|
|
cache_setitem(self, key, value)
|
||
|
|
self.__update(key)
|
||
|
|
|
||
|
|
def __delitem__(self, key, cache_delitem=Cache.__delitem__):
|
||
|
|
cache_delitem(self, key)
|
||
|
|
del self.__order[key]
|
||
|
|
|
||
|
|
def popitem(self):
|
||
|
|
"""Remove and return the `(key, value)` pair least recently used."""
|
||
|
|
try:
|
||
|
|
key = next(iter(self.__order))
|
||
|
|
except StopIteration:
|
||
|
|
msg = '%s is empty' % self.__class__.__name__
|
||
|
|
raise KeyError(msg) from None
|
||
|
|
else:
|
||
|
|
return (key, self.pop(key))
|
||
|
|
|
||
|
|
def __update(self, key):
|
||
|
|
try:
|
||
|
|
self.__order.move_to_end(key)
|
||
|
|
except KeyError:
|
||
|
|
self.__order[key] = None
|