lru.py

"""
max size
least recently used policy for eviction

API
write
read
delete
clear
count

reading is the most common one
ideally writing is very fast

1. LRUCache class
2. Tests
"""

from unittest import TestCase
from collections import OrderedDict

class LRUCache():

    def __init__(self, max_size: int):
        if max_size == 0:
            raise ValueError("Your cache must be larger than 0.")
        self._max_size = max_size
        self._cache = OrderedDict()

    def _evict_least_recently_used(self):
        self._cache.popitem(last=False)

    def _mark_most_recently_used(self, key):
        self._cache.move_to_end(key)

    def _in(self, key):
        return key in self._cache

    def _last_key(self):
        last_key = list(self._cache.keys())[-1]
        return last_key

    def read(self, key):
        """
        throws: KeyError
        """
        if key not in self._cache:
            raise KeyError("This key {} is not in our cache".format(key))

        self._mark_most_recently_used(key)
        return self._cache[key]

    def write(self, key, value):
        # is the key already in the cache
        if key in self._cache:
            self._cache[key] = value
            self._mark_most_recently_used(key)
            return

        # cache is already full - evict mru item
        if len(self._cache) == self._max_size:
            self._evict_least_recently_used()

        self._cache[key] = value

    def delete(self, key):
        if key not in self._cache:
            return
        del self._cache[key]

    def clear(self):
        self._cache.clear()

    def count(self):
        return len(self._cache)


class LRUCacheTests(TestCase):
    """
    Refactor to not use private attributes
    """

    def setUp(self):
        self.lru_cache = LRUCache(max_size=3)

    def test_write(self):
        self.lru_cache.write('Apple', 1)
        self.assertEqual(1, self.lru_cache.count())

    def test_write__evicts_most_recently_used(self):
        self.lru_cache.write('Apple', 1)
        self.lru_cache.write('Banana', 2)
        self.lru_cache.write('Orange', 3)
        self.lru_cache.write('Grapes', 4)

        # we would expect Apple to be evicted
        self.assertFalse(self.lru_cache._in('Apple'))

    def test_write__does_not_evict_if_key_already_exists(self):
        self.lru_cache.write('Apple', 1)
        self.lru_cache.write('Banana', 2)
        self.lru_cache.write('Orange', 3)
        self.lru_cache.write('Apple', 4)

        # we would expect Apple to not to be evicted
        self.assertTrue(self.lru_cache._in('Apple'))
        self.assertEqual(4, self.lru_cache.read('Apple'))
        self.assertEqual('Apple', self.lru_cache._last_key())

    def test_read__throws_error_if_key_not_cache(self):
        with self.assertRaises(KeyError):
            self.lru_cache.read('Apple')

    def test_read__marks_item_as_most_recently_used(self):
        self.lru_cache.write('Apple', 1)
        self.lru_cache.write('Banana', 2)

        result = self.lru_cache.read('Apple')
        self.assertEqual(1, result)
        self.assertEqual('Apple', self.lru_cache._last_key())

    def test_delete__not_in_cache(self):
        self.lru_cache.delete('Apple')

    def test_delete__in_cache(self):
        self.lru_cache.write('Apple', 1)
        self.lru_cache.delete('Apple')
        self.assertFalse(self.lru_cache._in('Apple'))

    def test_clear(self):
        self.lru_cache.write('Apple', 1)
        self.lru_cache.clear()
        self.assertEqual(0, self.lru_cache.count())

    def test_count(self):
        self.assertEqual(0, self.lru_cache.count())
        self.lru_cache.write('Apple', 1)
        self.assertEqual(1, self.lru_cache.count())