1 files changed, 34 insertions, 0 deletions
diff --git a/src/cachetools/lfu.py b/src/cachetools/lfu.py
new file mode 100644
index 0000000..6289b5c
--- /dev/null
+++ b/src/cachetools/lfu.py
@@ -0,0 +1,34 @@
+import collections
+
+from .cache import Cache
+
+
+class LFUCache(Cache):
+    """Least Frequently Used (LFU) cache implementation."""
+
+    def __init__(self, maxsize, getsizeof=None):
+        Cache.__init__(self, maxsize, getsizeof)
+        self.__counter = collections.Counter()
+
+    def __getitem__(self, key, cache_getitem=Cache.__getitem__):
+        value = cache_getitem(self, key)
+        if key in self:  # __missing__ may not store item
+            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" % type(self).__name__) from None
+        else:
+            return (key, self.pop(key))