

from __future__ import annotations

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

__A      		=     TypeVar('''T''')
__A      		=     TypeVar('''U''')



class   lowercase_   (  Generic[T, U]					):



      def __init__(      self				:    Dict      , A__				:    T | None      , A__				:    U | None		)   ->					Union[str, Any]:
        _snake_case						=							key
        _snake_case						=							val
        _snake_case						=							None
        _snake_case						=							None







      def __repr__(      self				:    Optional[int]		)   ->					str:
        return (
            f"""Node: key: {self.key}, val: {self.val}, """
            f"""has next: {bool(self.next		)}, has prev: {bool(self.prev		)}"""
        )



class   lowercase_   (  Generic[T, U]					):



      def __init__(      self				:    Tuple		)   ->					None:
        _snake_case						=							DoubleLinkedListNode(A__      , A__		)
        _snake_case						=							DoubleLinkedListNode(A__      , A__		)
        _snake_case,					_snake_case						=							self.rear, self.head



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



      def 						UpperCamelCase_		(      self				:    Optional[int]      , A__				:    DoubleLinkedListNode[T, U]		)   ->					None:
        _snake_case						=							self.rear.prev

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

        _snake_case						=							node
        _snake_case						=							previous
        _snake_case						=							node
        _snake_case						=							self.rear







      def 						UpperCamelCase_		(      self				:    int      , A__				:    DoubleLinkedListNode[T, U]		)   ->					DoubleLinkedListNode[T, U] | None:

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

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



class   lowercase_   (  Generic[T, U]					):
      UpperCamelCase_      :		dict[Callable[[T], U], LRUCache[T, U]]										=    {}



      def __init__(      self				:    List[Any]      , A__				:    int		)   ->					Union[str, Any]:
        _snake_case						=							DoubleLinkedList()
        _snake_case						=							capacity
        _snake_case						=							0
        _snake_case						=							0
        _snake_case						=							0
        _snake_case						=							{}



      def __repr__(      self				:    str		)   ->					str:
        return (
            f"""CacheInfo(hits={self.hits}, misses={self.miss}, """
            f"""capacity={self.capacity}, current size={self.num_keys})"""
        )



      def __contains__(      self				:    str      , A__				:    T		)   ->					bool:
        return key in self.cache



      def 						UpperCamelCase_		(      self				:    List[Any]      , A__				:    T		)   ->					U | None:
        # Note: pythonic interface would throw KeyError rather than return None

        if key in self.cache:
          self.hits += 1
          _snake_case						=							self.cache[key]
          _snake_case						=							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(A__		)
          return node.val
        self.miss += 1
        return None



      def 						UpperCamelCase_		(      self				:    Dict      , A__				:    T      , A__				:    U		)   ->					None:

        if key not in self.cache:
          if self.num_keys >= self.capacity:
            # delete first node (oldest) when over capacity
            _snake_case						=							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(A__		) 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
          _snake_case						=							DoubleLinkedListNode(A__      , A__		)
          self.list.add(self.cache[key]		)
          self.num_keys += 1

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







      @classmethod
      def 						UpperCamelCase_		(      cls				:    Union[str, Any]      , A__				:    int = 128		)   ->					Callable[[Callable[[T], U]], Callable[..., U]]:

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

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

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

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

          return cache_decorator_wrapper

        return cache_decorator_inner


if __name__ == "__main__":
 import doctest

 doctest.testmod()




import os
import sys
from contextlib import contextmanager


# Windows only
if os.name == "nt":
 import ctypes
 import msvcrt  # noqa



 class   lowercase_   (  ctypes.Structure					):
       # _fields is a specific attr expected by ctypes
       UpperCamelCase_      :		List[Any]										=    [("size", ctypes.c_int), ("visible", ctypes.c_byte)]



def 				snake_case_()							->     int:



  """simple docstring"""






  if os.name == "nt":
    _snake_case						=							CursorInfo()
    _snake_case						=							ctypes.windll.kernelaa.GetStdHandle(-11					)
    ctypes.windll.kernelaa.GetConsoleCursorInfo(_UpperCamelCase			,	ctypes.byref(_UpperCamelCase					)					)
    _snake_case						=							False
    ctypes.windll.kernelaa.SetConsoleCursorInfo(_UpperCamelCase			,	ctypes.byref(_UpperCamelCase					)					)
  elif os.name == "posix":
    sys.stdout.write('''\033[?25l'''					)
    sys.stdout.flush()



def 				snake_case_()							->     Optional[Any]:



  """simple docstring"""






  if os.name == "nt":
    _snake_case						=							CursorInfo()
    _snake_case						=							ctypes.windll.kernelaa.GetStdHandle(-11					)
    ctypes.windll.kernelaa.GetConsoleCursorInfo(_UpperCamelCase			,	ctypes.byref(_UpperCamelCase					)					)
    _snake_case						=							True
    ctypes.windll.kernelaa.SetConsoleCursorInfo(_UpperCamelCase			,	ctypes.byref(_UpperCamelCase					)					)
  elif os.name == "posix":
    sys.stdout.write('''\033[?25h'''					)
    sys.stdout.flush()



@contextmanager
def 				snake_case_()							->     int:



  """simple docstring"""






  try:
    hide_cursor()
    yield
  finally:
    show_cursor()

