





"""simple docstring"""


from __future__ import annotations

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

a__       :  List[str]       		=					TypeVar("""T""")
a__       :  Dict       		=					TypeVar("""U""")



class   lowercase_					(  Generic[T, U]				):

       def __init__(      self ,       __SCREAMING_SNAKE_CASE ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        snake_case__     				=					key
        snake_case__     				=					val
        snake_case__     				=					0
        snake_case__     				=					None
        snake_case__     				=					None

       def __repr__(      self  ):






        '''simple docstring'''

        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   lowercase_					(  Generic[T, U]				):

       def __init__(      self  ):






        '''simple docstring'''

        snake_case__     				=					DoubleLinkedListNode(__SCREAMING_SNAKE_CASE ,       __SCREAMING_SNAKE_CASE  )
        snake_case__     				=					DoubleLinkedListNode(__SCREAMING_SNAKE_CASE ,       __SCREAMING_SNAKE_CASE  )
        snake_case__				, snake_case__     				=					self.rear, self.head

       def __repr__(      self  ):






        '''simple docstring'''

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

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        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
        node.freq += 1
        self._position_node(__SCREAMING_SNAKE_CASE  )

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        while node.prev is not None and node.prev.freq > node.freq:
         # swap node with previous node
         snake_case__     				=					node.prev

         snake_case__     				=					previous_node.prev
         snake_case__     				=					node.prev
         snake_case__     				=					previous_node
         snake_case__     				=					node

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        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]				):
       snake_case__					:				dict[Callable[[T], U], LFUCache[T, U]]									=  {}

       def __init__(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        snake_case__     				=					DoubleLinkedList()
        snake_case__     				=					capacity
        snake_case__     				=					0
        snake_case__     				=					0
        snake_case__     				=					0
        snake_case__     				=					{}

       def __repr__(      self  ):






        '''simple docstring'''

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

       def __contains__(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        return key in self.cache

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        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(__SCREAMING_SNAKE_CASE  )
         return node.val
        self.miss += 1
        return None

       def 		_SCREAMING_SNAKE_CASE(      self ,       __SCREAMING_SNAKE_CASE ,       __SCREAMING_SNAKE_CASE  ):






        '''simple docstring'''

        if key not in self.cache:
         if self.num_keys >= self.capacity:
          # delete first node 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(__SCREAMING_SNAKE_CASE  ) is not None
          # first_node guaranteed to be in list

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

        else:
         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(__SCREAMING_SNAKE_CASE  )

       @classmethod
       def 		_SCREAMING_SNAKE_CASE(      cls ,       __SCREAMING_SNAKE_CASE = 128  ):






        '''simple docstring'''

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

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

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

         setattr(__SCREAMING_SNAKE_CASE ,       "cache_info" ,       __SCREAMING_SNAKE_CASE  )  # noqa: B010

         return cache_decorator_wrapper

        return cache_decorator_inner


if __name__ == "__main__":
   import doctest

   doctest.testmod()








"""simple docstring"""


def 				a__      (	_UpperCAmelCase						)     ->	int:

 '''simple docstring'''






 snake_case__     				=					0
 for plain_chr in plain_text:
  snake_case__     				=					(
      ord(_UpperCAmelCase						) + (hash_value << 6) + (hash_value << 1_6) - hash_value
  )
 return hash_value

