Index: client/third_party/cachetools/lfu.py |
diff --git a/client/third_party/cachetools/lfu.py b/client/third_party/cachetools/lfu.py |
new file mode 100644 |
index 0000000000000000000000000000000000000000..f5817a43045046a5a1bcbb5335a190a3af068edc |
--- /dev/null |
+++ b/client/third_party/cachetools/lfu.py |
@@ -0,0 +1,35 @@ |
+from __future__ import absolute_import |
+ |
+import collections |
+ |
+from .cache import Cache |
+ |
+ |
+class LFUCache(Cache): |
+ """Least Frequently Used (LFU) cache implementation.""" |
+ |
+ def __init__(self, maxsize, missing=None, getsizeof=None): |
+ Cache.__init__(self, maxsize, missing, getsizeof) |
+ self.__counter = collections.Counter() |
+ |
+ def __getitem__(self, key, cache_getitem=Cache.__getitem__): |
+ value = cache_getitem(self, key) |
+ self.__counter[key] -= 1 |
+ return value |
+ |
+ def __setitem__(self, key, value, cache_setitem=Cache.__setitem__): |
+ cache_setitem(self, key, value) |
+ self.__counter[key] -= 1 |
+ |
+ def __delitem__(self, key, cache_delitem=Cache.__delitem__): |
+ cache_delitem(self, key) |
+ del self.__counter[key] |
+ |
+ def popitem(self): |
+ """Remove and return the `(key, value)` pair least frequently used.""" |
+ try: |
+ (key, _), = self.__counter.most_common(1) |
+ except ValueError: |
+ raise KeyError('%s is empty' % self.__class__.__name__) |
+ else: |
+ return (key, self.pop(key)) |