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