


'''simple docstring'''





from __future__ import annotations

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

__lowerCamelCase												=						TypeVar('''T''')
__lowerCamelCase												=						TypeVar('''U''')




class 				UpperCAmelCase			(			Generic[T, U]						):


 def __init__(      self							:	List[str]			,       __lowerCamelCase							:	T | None			,       __lowerCamelCase							:	U | None ):
    UpperCAmelCase__	:Optional[int]      =      key
    UpperCAmelCase__	:List[Any]      =      val
    UpperCAmelCase__	:DoubleLinkedListNode[T, U] | None      =      None
    UpperCAmelCase__	:DoubleLinkedListNode[T, U] | None      =      None





 def __repr__(      self							:	Optional[Any] ):
    return (
        f'''Node: key: {self.key}, val: {self.val}, '''
        f'''has next: {bool(self.next )}, has prev: {bool(self.prev )}'''
    )




class 				UpperCAmelCase			(			Generic[T, U]						):


 def __init__(      self							:	Union[str, Any] ):
    UpperCAmelCase__	:DoubleLinkedListNode[T, U]      =      DoubleLinkedListNode(__lowerCamelCase			,       __lowerCamelCase )
    UpperCAmelCase__	:DoubleLinkedListNode[T, U]      =      DoubleLinkedListNode(__lowerCamelCase			,       __lowerCamelCase )
    UpperCAmelCase__   ,						UpperCAmelCase__	:Optional[int]      =      self.rear, self.head


 def __repr__(      self							:	List[str] ):
    UpperCAmelCase__	:Tuple      =      ['''DoubleLinkedList''']
    UpperCAmelCase__	:int      =      self.head
    while node.next is not None:
       rep.append(str(__lowerCamelCase ) )
       UpperCAmelCase__	:Optional[int]      =      node.next
    rep.append(str(self.rear ) )
    return ",\n    ".join(__lowerCamelCase )


 def        __SCREAMING_SNAKE_CASE					(      self							:	str			,       __lowerCamelCase							:	DoubleLinkedListNode[T, U] ):
    UpperCAmelCase__	:List[str]      =      self.rear.prev

    # All nodes other than self.head are guaranteed to have non-None previous
    assert previous is not None

    UpperCAmelCase__	:Dict      =      node
    UpperCAmelCase__	:Union[str, Any]      =      previous
    UpperCAmelCase__	:str      =      node
    UpperCAmelCase__	:List[Any]      =      self.rear





 def        __SCREAMING_SNAKE_CASE					(      self							:	Tuple			,       __lowerCamelCase							:	DoubleLinkedListNode[T, U] ):

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

    UpperCAmelCase__	:int      =      node.next
    UpperCAmelCase__	:Optional[Any]      =      node.prev
    UpperCAmelCase__	:Tuple      =      None
    UpperCAmelCase__	:Optional[int]      =      None
    return node




class 				UpperCAmelCase			(			Generic[T, U]						):
 UpperCAmelCase				=					{}


 def __init__(      self							:	Optional[int]			,       __lowerCamelCase							:	int ):
    UpperCAmelCase__	:DoubleLinkedList[T, U]      =      DoubleLinkedList()
    UpperCAmelCase__	:Optional[Any]      =      capacity
    UpperCAmelCase__	:Optional[Any]      =      0
    UpperCAmelCase__	:Union[str, Any]      =      0
    UpperCAmelCase__	:Optional[int]      =      0
    UpperCAmelCase__	:dict[T, DoubleLinkedListNode[T, U]]      =      {}


 def __repr__(      self							:	Optional[int] ):
    return (
        f'''CacheInfo(hits={self.hits}, misses={self.miss}, '''
        f'''capacity={self.capacity}, current size={self.num_keys})'''
    )


 def __contains__(      self							:	List[Any]			,       __lowerCamelCase							:	T ):
    return key in self.cache


 def        __SCREAMING_SNAKE_CASE					(      self							:	int			,       __lowerCamelCase							:	T ):
    # Note: pythonic interface would throw KeyError rather than return None

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

       # node is guaranteed not None because it is in self.cache
       assert node is not None
       self.list.add(__lowerCamelCase )
       return node.val
    self.miss += 1
    return None


 def        __SCREAMING_SNAKE_CASE					(      self							:	Dict			,       __lowerCamelCase							:	T			,       __lowerCamelCase							:	U ):

    if key not in self.cache:
       if self.num_keys >= self.capacity:
          # delete first node (oldest) when over capacity
          UpperCAmelCase__	:Optional[int]      =      self.list.head.next

          # guaranteed to have a non-None first node when num_keys > 0
          # explain to type checker via assertions
          assert first_node is not None
          assert first_node.key is not None
          assert (
              self.list.remove(__lowerCamelCase ) is not None
          )  # node guaranteed to be in list assert node.key is not None

          del self.cache[first_node.key]
          self.num_keys -= 1
       UpperCAmelCase__	:List[str]      =      DoubleLinkedListNode(__lowerCamelCase			,       __lowerCamelCase )
       self.list.add(self.cache[key] )
       self.num_keys += 1

    else:
       # bump node to the end of the list, update value
       UpperCAmelCase__	:Union[str, Any]      =      self.list.remove(self.cache[key] )
       assert node is not None  # node guaranteed to be in list
       UpperCAmelCase__	:Any      =      value
       self.list.add(__lowerCamelCase )





 @classmethod
 def        __SCREAMING_SNAKE_CASE					(      cls							:	Dict			,       __lowerCamelCase							:	int = 1_2_8 ):

    def cache_decorator_inner(__lowerCamelCase							:	Callable[[T], U] ) -> Callable[..., U]:
       def cache_decorator_wrapper(*__lowerCamelCase							:	T ) -> U:
          if func not in cls.decorator_function_to_instance_map:
             UpperCAmelCase__	:Any      =      LRUCache(__lowerCamelCase )

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

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

       setattr(__lowerCamelCase			,       '''cache_info'''			,       __lowerCamelCase )  # noqa: B010

       return cache_decorator_wrapper

    return cache_decorator_inner


if __name__ == "__main__":
    import doctest

    doctest.testmod()







'''simple docstring'''





from ..utils import DummyObject, requires_backends




class 				UpperCAmelCase			(			metaclass=_snake_case						):
 UpperCAmelCase				=					["note_seq"]


 def __init__(      self							:	List[str]			,       *__lowerCamelCase							:	int			,       **__lowerCamelCase							:	Optional[int] ):
    requires_backends(self			,       ['''note_seq'''] )


 @classmethod
 def        __SCREAMING_SNAKE_CASE					(      cls							:	Optional[Any]			,       *__lowerCamelCase							:	Dict			,       **__lowerCamelCase							:	Optional[Any] ):
    requires_backends(cls			,       ['''note_seq'''] )





 @classmethod
 def        __SCREAMING_SNAKE_CASE					(      cls							:	str			,       *__lowerCamelCase							:	Any			,       **__lowerCamelCase							:	Optional[Any] ):
    requires_backends(cls			,       ['''note_seq'''] )



