Untitled

#Least Recently Used (LRU) is a common caching strategy. It defines the policy to evict elements from the cache to make room for new elements when the cache is full, meaning it discards the least recently used items first.

#Let’s take an example of a cache that has a capacity of 4 elements. We cache elements 1, 2, 3 and 4.


class LinkedList:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.head = LinkedList(0, 0)
        self.tail = LinkedList(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.key_to_node = {}

    
    def _extract_node(self, node):
        nxt, prev = node.next, node.prev
        nxt.prev = prev
        prev.next = nxt
        node.next = None
        node.prev = None
        return node


    def _insert_to_head(self, node):
        old_next = self.head.next
        self.head.next = node
        node.next = old_next
        old_next.prev = node
        node.prev = self.head
    

    def set(self, key, value):
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.value = value
            self._extract_node(node)
            self._insert_to_head(node)
        else:
            node = LinkedList(key, value)
            self.key_to_node[key] = node
            self._insert_to_head(node)
            if len(self.key_to_node) > self.capacity:
                node_to_extract = self._extract_node(self.tail.prev)
                del self.key_to_node[node_to_extract.key]


    def find(self, key):
        if key not in self.key_to_node:
            return None
        
        node = self.key_to_node[key]

        self._extract_node(node)
        self._insert_to_head(node)

        return node.value




class WebApplication:
    def __init__(self, config):
        self.cache = LRUCache(config['cache_capacity'])

    def make_key(self, req):
        return req
    
    def do_some_heavy_work(self, req):
        return req*2

    def process_request(self, request):
        key = self.make_key(request)
        value = self.cache.find(key)
        if not value:
            value = self.do_some_heavy_work(request)
            self.cache.set(key, value)

        return value

cfg = {'cache_capacity': 4}
wa = WebApplication(cfg)
wa.process_request(1)
wa.process_request(2)
wa.process_request(3)
wa.process_request(4)
wa.process_request(5)