double linked list node built specifically for lfu cache node doublelinkedlistnode1 1 node node key 1 val 1 freq 0 has next false has prev false double linked list built specifically for lfu cache dll doublelinkedlist doublelinkedlist dll doublelinkedlist node key none val none freq 0 has next true has prev false node key none val none freq 0 has next false has prev true firstnode doublelinkedlistnode1 10 firstnode node key 1 val 10 freq 0 has next false has prev false dll addfirstnode dll doublelinkedlist node key none val none freq 0 has next true has prev false node key 1 val 10 freq 1 has next true has prev true node key none val none freq 0 has next false has prev true node is mutated firstnode node key 1 val 10 freq 1 has next true has prev true secondnode doublelinkedlistnode2 20 secondnode node key 2 val 20 freq 0 has next false has prev false dll addsecondnode dll doublelinkedlist node key none val none freq 0 has next true has prev false node key 1 val 10 freq 1 has next true has prev true node key 2 val 20 freq 1 has next true has prev true node key none val none freq 0 has next false has prev true removednode dll removefirstnode assert removednode firstnode dll doublelinkedlist node key none val none freq 0 has next true has prev false node key 2 val 20 freq 1 has next true has prev true node key none val none freq 0 has next false has prev true attempt to remove node not on list removednode dll removefirstnode removednode is none true attempt to remove head or rear dll head node key none val none freq 0 has next true has prev false dll removedll head is none true attempt to remove head or rear dll rear node key none val none freq 0 has next false has prev true dll removedll rear is none true adds the given node at the tail of the list and shifting it to proper position all nodes other than self head are guaranteed to have nonnone previous moves node forward to maintain invariant of sort by freq value swap node with previous node removes and returns the given node from the list returns none if node prev or node next is none lfu cache to store a given capacity of data can be used as a standalone object or as a function decorator cache lfucache2 cache put1 1 cache put2 2 cache get1 1 cache put3 3 cache get2 is none true cache put4 4 cache get1 is none true cache get3 3 cache get4 4 cache cacheinfohits3 misses2 capacity2 currentsize2 lfucache decorator100 def fibnum if num in 1 2 return 1 return fibnum 1 fibnum 2 for i in range1 101 res fibi fib cacheinfo cacheinfohits196 misses100 capacity100 currentsize100 class variable to map the decorator functions to their respective instance return the details for the cache instance hits misses capacity currentsize cache lfucache1 1 in cache false cache put1 1 1 in cache true returns the value for the input key and updates the double linked list returns returns none if key is not present in cache node is guaranteed not none because it is in self cache sets the value for the input key and updates the double linked list delete first node when over capacity guaranteed to have a nonnone first node when numkeys 0 explain to type checker via assertions firstnode guaranteed to be in list decorator version of lfu cache decorated function must be function of t u double linked list node built specifically for lfu cache node doublelinkedlistnode 1 1 node node key 1 val 1 freq 0 has next false has prev false double linked list built specifically for lfu cache dll doublelinkedlist doublelinkedlist dll doublelinkedlist node key none val none freq 0 has next true has prev false node key none val none freq 0 has next false has prev true first_node doublelinkedlistnode 1 10 first_node node key 1 val 10 freq 0 has next false has prev false dll add first_node dll doublelinkedlist node key none val none freq 0 has next true has prev false node key 1 val 10 freq 1 has next true has prev true node key none val none freq 0 has next false has prev true node is mutated first_node node key 1 val 10 freq 1 has next true has prev true second_node doublelinkedlistnode 2 20 second_node node key 2 val 20 freq 0 has next false has prev false dll add second_node dll doublelinkedlist node key none val none freq 0 has next true has prev false node key 1 val 10 freq 1 has next true has prev true node key 2 val 20 freq 1 has next true has prev true node key none val none freq 0 has next false has prev true removed_node dll remove first_node assert removed_node first_node dll doublelinkedlist node key none val none freq 0 has next true has prev false node key 2 val 20 freq 1 has next true has prev true node key none val none freq 0 has next false has prev true attempt to remove node not on list removed_node dll remove first_node removed_node is none true attempt to remove head or rear dll head node key none val none freq 0 has next true has prev false dll remove dll head is none true attempt to remove head or rear dll rear node key none val none freq 0 has next false has prev true dll remove dll rear is none true adds the given node at the tail of the list and shifting it to proper position all nodes other than self head are guaranteed to have non none previous moves node forward to maintain invariant of sort by freq value swap node with previous node removes and returns the given node from the list returns none if node prev or node next is none lfu cache to store a given capacity of data can be used as a stand alone object or as a function decorator cache lfucache 2 cache put 1 1 cache put 2 2 cache get 1 1 cache put 3 3 cache get 2 is none true cache put 4 4 cache get 1 is none true cache get 3 3 cache get 4 4 cache cacheinfo hits 3 misses 2 capacity 2 current_size 2 lfucache decorator 100 def fib num if num in 1 2 return 1 return fib num 1 fib num 2 for i in range 1 101 res fib i fib cache_info cacheinfo hits 196 misses 100 capacity 100 current_size 100 class variable to map the decorator functions to their respective instance return the details for the cache instance hits misses capacity current_size cache lfucache 1 1 in cache false cache put 1 1 1 in cache true returns the value for the input key and updates the double linked list returns returns none if key is not present in cache node is guaranteed not none because it is in self cache sets the value for the input key and updates the double linked list delete first node when over capacity guaranteed to have a non none first node when num_keys 0 explain to type checker via assertions first_node guaranteed to be in list node guaranteed to be in list decorator version of lfu cache decorated function must be function of t u noqa b010
from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

T = TypeVar("T")
U = TypeVar("U")


class DoubleLinkedListNode(Generic[T, U]):
    

    def __init__(self, key: T | None, val: U | None):
        self.key = key
        self.val = val
        self.freq: int = 0
        self.next: DoubleLinkedListNode[T, U] | None = None
        self.prev: DoubleLinkedListNode[T, U] | None = None

    def __repr__(self) -> str:
        return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
            self.key, self.val, self.freq, self.next is not None, self.prev is not None
        )


class DoubleLinkedList(Generic[T, U]):
    

    def __init__(self) -> None:
        self.head: DoubleLinkedListNode[T, U] = DoubleLinkedListNode(None, None)
        self.rear: DoubleLinkedListNode[T, U] = DoubleLinkedListNode(None, None)
        self.head.next, self.rear.prev = self.rear, self.head

    def __repr__(self) -> str:
        rep = ["DoubleLinkedList"]
        node = self.head
        while node.next is not None:
            rep.append(str(node))
            node = node.next
        rep.append(str(self.rear))
        return ",\n    ".join(rep)

    def add(self, node: DoubleLinkedListNode[T, U]) -> None:
        

        previous = self.rear.prev

        
        assert previous is not None

        previous.next = node
        node.prev = previous
        self.rear.prev = node
        node.next = self.rear
        node.freq += 1
        self._position_node(node)

    def _position_node(self, node: DoubleLinkedListNode[T, U]) -> None:
        

        while node.prev is not None and node.prev.freq > node.freq:
            
            previous_node = node.prev

            node.prev = previous_node.prev
            previous_node.next = node.prev
            node.next = previous_node
            previous_node.prev = node

    def remove(
        self, node: DoubleLinkedListNode[T, U]
    ) -> DoubleLinkedListNode[T, U] | None:
        

        if node.prev is None or node.next is None:
            return None

        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        return node


class LFUCache(Generic[T, U]):
    

    
    decorator_function_to_instance_map: dict[Callable[[T], U], LFUCache[T, U]] = {}

    def __init__(self, capacity: int):
        self.list: DoubleLinkedList[T, U] = DoubleLinkedList()
        self.capacity = capacity
        self.num_keys = 0
        self.hits = 0
        self.miss = 0
        self.cache: dict[T, DoubleLinkedListNode[T, U]] = {}

    def __repr__(self) -> str:
        

        return (
            f"CacheInfo(hits={self.hits}, misses={self.miss}, "
            f"capacity={self.capacity}, current_size={self.num_keys})"
        )

    def __contains__(self, key: T) -> bool:
        

        return key in self.cache

    def get(self, key: T) -> U | None:
        

        if key in self.cache:
            self.hits += 1
            value_node: DoubleLinkedListNode[T, U] = self.cache[key]
            node = self.list.remove(self.cache[key])
            assert node == value_node

            
            assert node is not None
            self.list.add(node)
            return node.val
        self.miss += 1
        return None

    def put(self, key: T, value: U) -> None:
        

        if key not in self.cache:
            if self.num_keys >= self.capacity:
                
                first_node = self.list.head.next

                
                
                assert first_node is not None
                assert first_node.key is not None
                assert self.list.remove(first_node) is not None
                

                del self.cache[first_node.key]
                self.num_keys -= 1
            self.cache[key] = DoubleLinkedListNode(key, value)
            self.list.add(self.cache[key])
            self.num_keys += 1

        else:
            node = self.list.remove(self.cache[key])
            assert node is not None  
            node.val = value
            self.list.add(node)

    @classmethod
    def decorator(
        cls: type[LFUCache[T, U]], size: int = 128
    ) -> Callable[[Callable[[T], U]], Callable[..., U]]:
        

        def cache_decorator_inner(func: Callable[[T], U]) -> Callable[..., U]:
            def cache_decorator_wrapper(*args: T) -> U:
                if func not in cls.decorator_function_to_instance_map:
                    cls.decorator_function_to_instance_map[func] = LFUCache(size)

                result = cls.decorator_function_to_instance_map[func].get(args[0])
                if result is None:
                    result = func(*args)
                    cls.decorator_function_to_instance_map[func].put(args[0], result)
                return result

            def cache_info() -> LFUCache[T, U]:
                return cls.decorator_function_to_instance_map[func]

            setattr(cache_decorator_wrapper, "cache_info", cache_info)  

            return cache_decorator_wrapper

        return cache_decorator_inner


if __name__ == "__main__":
    import doctest

    doctest.testmod()