Object Oriented Design - LRUCache

In [135]:

class Cache(object):
    def get(self, key):
        pass
    def put(self, key, value):
        pass

In [136]:

class DeQueueItem(object):
        def __init__(self, value):
            self.value = value
            self.next = None
            self.prev = None

class DeQueue(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def add_to_front(self, item):
        if self.head is None:
            self.head = item
            self.tail = item
        else:
            item.next = self.head
            self.head.prev = item
            self.head = item

    def move_to_front(self, item):
        if item.prev is not None:
            item.prev.next = None
            self.tail = item.prev
            item.prev = None
            
            item.next = self.head
            self.head = item

    def remove_from_tail(self):
        if self.tail is None:
            return

        if self.tail == self.head :
            tmp = self.tail
            self.head = None
            self.tail = None
            return

        tmp = self.tail
        tmp.prev.next = None
        self.tail = tmp.prev

In [137]:

class LRUCache(Cache):
    
    # inner helper class to share Node between DeQueue and Map
    class _LRUItem(DeQueueItem):
        def __init__(self, key, value):
            DeQueueItem.__init__(self, value)
            self.key = key
    
    def __init__(self, max_size):
        if max_size < 1:
            raise ValueError('max_size should be atleast 1')
        self._max_size = max_size
        self._queue = DeQueue()
        self._map = {}
        
    def get(self, key):
        if key in self._map:
            lru_item = self._map[key]
            self._queue.move_to_front(lru_item)
            return lru_item.value
        return None
    
    def put(self, key, value):
        if key in self._map :
            # if key is already present in map update its value
            # and move to front of queue
            lru_item = self._map.get(key)
            lru_item.value = value
            self._queue.move_to_front(lru_item)
        else:
            # if not present, then add item to map and
            # front of list
            lru_item = self._LRUItem(key,value)
            self._map[key] = lru_item
            self._queue.add_to_front(lru_item)
        if len(self._map) == self._max_size + 1:
            self._map.pop(self._queue.tail.key)
            self._queue.remove_from_tail()

In [138]:

import unittest

class LRUCacheTest(unittest.TestCase):
    
    def test_illegal_size_lru(self):
        with self.assertRaises(ValueError):
            lru = LRUCache(0)
            
    def test_one_size_lru(self):
        lru = LRUCache(1)
        lru.put(1,10001)
        lru.put(2,20001)
        self.assertEqual(lru.get(1), None)
        self.assertEqual(lru.get(2), 20001)
        
    def test_least_used_item_removal(self):
        lru = LRUCache(3)
        lru.put(1,10001)
        lru.put(2,10001)
        lru.put(3,10001)
        lru.put(4,10001)
        self.assertEqual(lru.get(1), None)
        
    def test_get_becoming_queue_head(self):
        lru = LRUCache(3)
        lru.put(1,10001)
        lru.put(2,10001)
        lru.put(3,10001)
        lru.get(1)
        self.assertEqual(lru._queue.head.key, 1)
        
    def test_new_put_becoming_queue_head(self):
        lru = LRUCache(3)
        lru.put(1,10001)
        self.assertEqual(lru._queue.head.key, 1)
        lru.put(2,10001)
        self.assertEqual(lru._queue.head.key, 2)
        lru.put(3,10001)
        self.assertEqual(lru._queue.head.key, 3)
        lru.put(4,10001)
        self.assertEqual(lru._queue.head.key, 4)
        
    def test_update_put_becoming_queue_head(self):
        lru = LRUCache(3)
        lru.put(1,10001)
        lru.put(2,10001)
        lru.put(3,10001)
        lru.put(2,22222)
        self.assertEqual(lru._queue.head.key, 2)
    
if __name__ == '__main__':
        unittest.main(argv=['first-arg-is-ignored'], exit=False)

......
----------------------------------------------------------------------
Ran 6 tests in 0.004s

OK