LRUCache

LRUCache.py

#
#
# Implement a LRU cache
# key, value
# bounded -> not more than 'n' entries
# If cache is full, and you want to add another key value pair,
# oldest accessed entry will be removed
#
# Operations like get, put, remove are constant time.
#

# n < 1000, 2000
#
# get --> mark that entry as recently accessed
# put --> mark the inserted key as recently accessed

# [(1, 1), (2, 2), (3, 3)]


class Node:

    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

    def __repr__(self):
        return f"key={self.key}, val:{self.val}"


class LRUCache:

    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}  # will hold the instance of 'Node'
        self.left = Node(None, None)
        self.right = Node(None, None)
        self.left.next = self.right
        self.right.prev = self.left

    def _insert(self, node):
        temp = self.left.next
        self.left.next = node
        node.next = temp
        temp.prev = node

    def _delete(self, node):
        # if we are deleting the head, the prev can be none
        if node.prev:
            node.prev.next = node.next
        node.next.prev = node.prev

    def put(self, key, val):
        if key in self.cache:
            # key already present, make it recently used and update the node val
            node = self.cache[key]
            self._delete(node)
            node.val = val
        else:
            # put the key:val as most recently used
            node = Node(key, val)
        self._insert(node)
        self.cache[key] = node

        # check if cache is full
        if len(self.cache) > self.cap:
            # remove the oldest entry
            temp = self.right.prev
            self._delete(temp)
            # remove from the dict
            del self.cache[temp.key]

    def get(self, key):
        val = None
        if key in self.cache:
            val = self.cache[key]
            self._delete(val)
            self._insert(val)

        return val.val if val else -1

    def remove(self, key):
        if key in self.cache:
            node = self.cache[key]
            # remove it from the LL
            self._delete(node)
            del self.cache[key]  # if key is not present


#
# tests
#
def test_put_and_get():
    lc = LRUCache(2)
    lc.put(1, 1)
    assert lc.get(1) == 1


def test_remove():
    lc = LRUCache(2)
    lc.put(1, 1)
    lc.put(2, 2)
    lc.remove(1)
    assert lc.get(1) == -1
    assert lc.get(2) == 2


def test_same_key_inserted_twice_will_update_the_value():
    lc = LRUCache(2)
    lc.put(1, 1)
    lc.put(1, 2)
    lc.put(1, 3)

    assert lc.get(1) == 3


def test_least_recently_used_removed_when_cache_reached_to_capacity():
    lc = LRUCache(2)
    lc.put(1, 1)
    lc.put(2, 2)
    lc.put(3, 3)  # it will kick out the entry 1

    assert lc.get(1) == -1


def test_recently_used_entry_removed():
    lc = LRUCache(2)
    lc.put(1, 1)
    lc.put(2, 2)  # 2 is recently used, now remove it

    lc.remove(2)

    assert lc.get(1) == 1
    assert lc.get(2) == -1


def test_least_recently_used_entry_removed():
    lc = LRUCache(2)
    lc.put(1, 1)
    lc.put(2, 2)

    # 1 is least recently used, lets remove it
    lc.remove(1)

    assert lc.get(1) == -1
    assert lc.get(2) == 2


# run tests
test_put_and_get()
test_remove()
test_same_key_inserted_twice_will_update_the_value()
test_least_recently_used_removed_when_cache_reached_to_capacity()
test_recently_used_entry_removed()
test_least_recently_used_entry_removed()