Add FIFO cache implementation.

6 files changed, 124 insertions, 0 deletions

diff --git a/cachetools/__init__.py b/cachetools/__init__.py
index 029b1a6..428ffc2 100644
--- a/cachetools/__init__.py
+++ b/cachetools/__init__.py
@@ -2,6 +2,7 @@
 
 from .cache import Cache
 from .decorators import cached, cachedmethod
+from .fifo import FIFOCache
 from .lfu import LFUCache
 from .lru import LRUCache
 from .mru import MRUCache
@@ -10,6 +11,7 @@ from .ttl import TTLCache
 
 __all__ = (
     'Cache',
+    'FIFOCache',
     'LFUCache',
     'LRUCache',
     'MRUCache',
diff --git a/cachetools/fifo.py b/cachetools/fifo.py
new file mode 100644
index 0000000..38ddca1
--- /dev/null
+++ b/cachetools/fifo.py
@@ -0,0 +1,32 @@
+import collections
+
+from .cache import Cache
+
+
+class FIFOCache(Cache):
+    """First In First Out (FIFO) cache implementation."""
+
+    def __init__(self, maxsize, getsizeof=None):
+        Cache.__init__(self, maxsize, getsizeof)
+        self.__order = collections.OrderedDict()
+
+    def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
+        cache_setitem(self, key, value)
+        try:
+            self.__order.move_to_end(key)
+        except KeyError:
+            self.__order[key] = None
+
+    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 first inserted."""
+        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))
diff --git a/cachetools/func.py b/cachetools/func.py
index 0815bac..2be517e 100644
--- a/cachetools/func.py
+++ b/cachetools/func.py
@@ -12,6 +12,7 @@ except ImportError:  # pragma: no cover
     from dummy_threading import RLock
 
 from . import keys
+from .fifo import FIFOCache
 from .lfu import LFUCache
 from .lru import LRUCache
 from .mru import MRUCache
@@ -93,6 +94,20 @@ def _cache(cache, typed):
     return decorator
 
 
+def fifo_cache(maxsize=128, typed=False):
+    """Decorator to wrap a function with a memoizing callable that saves
+    up to `maxsize` results based on a First In First Out (FIFO)
+    algorithm.
+
+    """
+    if maxsize is None:
+        return _cache(_UnboundCache(), typed)
+    elif callable(maxsize):
+        return _cache(FIFOCache(128), typed)(maxsize)
+    else:
+        return _cache(FIFOCache(maxsize), typed)
+
+
 def lfu_cache(maxsize=128, typed=False):
     """Decorator to wrap a function with a memoizing callable that saves
     up to `maxsize` results based on a Least Frequently Used (LFU)
diff --git a/docs/index.rst b/docs/index.rst
index 08374ed..945bd78 100644
--- a/docs/index.rst
+++ b/docs/index.rst
@@ -76,6 +76,12 @@ computed when the item is inserted into the cache.
    additionally need to override :meth:`__getitem__`,
    :meth:`__setitem__` and :meth:`__delitem__`.
 
+.. autoclass:: FIFOCache(maxsize, getsizeof=None)
+   :members:
+
+   This class evicts items in the order they were added to make space
+   when necessary.
+
 .. autoclass:: LFUCache(maxsize, getsizeof=None)
    :members:
 
@@ -470,6 +476,13 @@ performance and clear the cache.  Please see the
 all the decorators in this module are thread-safe by default.
 
 
+.. decorator:: fifo_cache(user_function)
+               fifo_cache(maxsize=128, typed=False)
+
+   Decorator that wraps a function with a memoizing callable that
+   saves up to `maxsize` results based on a First In First Out
+   (FIFO) algorithm.
+
 .. decorator:: lfu_cache(user_function)
                lfu_cache(maxsize=128, typed=False)
 
diff --git a/tests/test_fifo.py b/tests/test_fifo.py
new file mode 100644
index 0000000..933af56
--- /dev/null
+++ b/tests/test_fifo.py
@@ -0,0 +1,57 @@
+import unittest
+
+from cachetools import FIFOCache
+
+from . import CacheTestMixin
+
+
+class LRUCacheTest(unittest.TestCase, CacheTestMixin):
+
+    Cache = FIFOCache
+
+    def test_fifo(self):
+        cache = FIFOCache(maxsize=2)
+
+        cache[1] = 1
+        cache[2] = 2
+        cache[3] = 3
+
+        self.assertEqual(len(cache), 2)
+        self.assertEqual(cache[2], 2)
+        self.assertEqual(cache[3], 3)
+        self.assertNotIn(1, cache)
+
+        cache[2]
+        cache[4] = 4
+        self.assertEqual(len(cache), 2)
+        self.assertEqual(cache[3], 3)
+        self.assertEqual(cache[4], 4)
+        self.assertNotIn(2, cache)
+
+        cache[5] = 5
+        self.assertEqual(len(cache), 2)
+        self.assertEqual(cache[4], 4)
+        self.assertEqual(cache[5], 5)
+        self.assertNotIn(3, cache)
+
+    def test_fifo_getsizeof(self):
+        cache = FIFOCache(maxsize=3, getsizeof=lambda x: x)
+
+        cache[1] = 1
+        cache[2] = 2
+
+        self.assertEqual(len(cache), 2)
+        self.assertEqual(cache[1], 1)
+        self.assertEqual(cache[2], 2)
+
+        cache[3] = 3
+
+        self.assertEqual(len(cache), 1)
+        self.assertEqual(cache[3], 3)
+        self.assertNotIn(1, cache)
+        self.assertNotIn(2, cache)
+
+        with self.assertRaises(ValueError):
+            cache[4] = 4
+        self.assertEqual(len(cache), 1)
+        self.assertEqual(cache[3], 3)
diff --git a/tests/test_func.py b/tests/test_func.py
index 2aebbd0..b6c4fe1 100644
--- a/tests/test_func.py
+++ b/tests/test_func.py
@@ -89,6 +89,11 @@ class DecoratorTestMixin(object):
         self.assertEqual(cached.cache_info(), (2, 1, 128, 1))
 
 
+class FIFODecoratorTest(unittest.TestCase, DecoratorTestMixin):
+
+    DECORATOR = staticmethod(cachetools.func.fifo_cache)
+
+
 class LFUDecoratorTest(unittest.TestCase, DecoratorTestMixin):
 
     DECORATOR = staticmethod(cachetools.func.lfu_cache)