


'''simple docstring'''





from __future__ import annotations

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

__lowerCamelCase     :   int       				=	TypeVar('''T''')
__lowerCamelCase     :   List[str]       				=	TypeVar('''U''')




class 							UpperCAmelCase ( Generic[T, U]	):


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





 def __repr__(			self       :  Optional[int]   ):
    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 							UpperCAmelCase ( Generic[T, U]	):


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


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


 def 					__SCREAMING_SNAKE_CASE				(			self       :  Union[str, Any] ,					__lowerCamelCase       :  DoubleLinkedListNode[T, U]   ):
    UpperCAmelCase__  :Optional[Any]            =			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__  :str            =			previous
    UpperCAmelCase__  :Dict            =			node
    UpperCAmelCase__  :Any            =			self.rear
    node.freq += 1
    self._position_node(__lowerCamelCase   )


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

    while node.prev is not None and node.prev.freq > node.freq:
       # swap node with previous node
       UpperCAmelCase__  :Optional[Any]            =			node.prev

       UpperCAmelCase__  :Tuple            =			previous_node.prev
       UpperCAmelCase__  :Any            =			node.prev
       UpperCAmelCase__  :Tuple            =			previous_node
       UpperCAmelCase__  :int            =			node





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

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

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




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


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


 def __repr__(			self       :  Dict   ):
    return (
        f'''CacheInfo(hits={self.hits}, misses={self.miss}, '''
        f'''capacity={self.capacity}, current_size={self.num_keys})'''
    )


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


 def 					__SCREAMING_SNAKE_CASE				(			self       :  str ,					__lowerCamelCase       :  T   ):

    if key in self.cache:
       self.hits += 1
       UpperCAmelCase__  :DoubleLinkedListNode[T, U]            =			self.cache[key]
       UpperCAmelCase__  :Optional[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       :  Any ,					__lowerCamelCase       :  T ,					__lowerCamelCase       :  U   ):

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

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

    else:
       UpperCAmelCase__  :Optional[Any]            =			self.list.remove(self.cache[key]   )
       assert node is not None  # node guaranteed to be in list
       UpperCAmelCase__  :int            =			value
       self.list.add(__lowerCamelCase   )





 @classmethod
 def 					__SCREAMING_SNAKE_CASE				(			cls       :  type[LFUCache[T, U]] ,					__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__  :str            =			LFUCache(__lowerCamelCase   )

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

       def cache_info() -> LFUCache[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'''





import heapq


def 					a__    (				UpperCamelCase_	:			Dict,      UpperCamelCase_	:			Tuple,      UpperCamelCase_	:			Dict	):
   UpperCAmelCase__  :List[Any]            =			[(0, start)]  # cost from start node,end node
   UpperCAmelCase__  :Optional[int]            =			set()
   while heap:
      ((UpperCAmelCase__)      ,	(UpperCAmelCase__))  :Optional[Any]            =			heapq.heappop(UpperCamelCase_	)
      if u in visited:
         continue
      visited.add(UpperCamelCase_	)
      if u == end:
         return cost
      for v, c in graph[u]:
         if v in visited:
            continue
         UpperCAmelCase__  :int            =			cost + c
         heapq.heappush(UpperCamelCase_,      (next_item, v)	)
   return -1


__lowerCamelCase       				=	{
    '''A''': [['''B''', 2], ['''C''', 5]],
    '''B''': [['''A''', 2], ['''D''', 3], ['''E''', 1], ['''F''', 1]],
    '''C''': [['''A''', 5], ['''F''', 3]],
    '''D''': [['''B''', 3]],
    '''E''': [['''B''', 4], ['''F''', 3]],
    '''F''': [['''C''', 3], ['''E''', 3]],
}
__lowerCamelCase       				=	{
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''F''', 3]],
    '''F''': [],
}
__lowerCamelCase       				=	{
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''G''', 2]],
    '''F''': [],
    '''G''': [['''F''', 1]],
}

__lowerCamelCase       				=	dijkstra(G, '''E''', '''C''')
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

__lowerCamelCase       				=	dijkstra(Ga, '''E''', '''F''')
print(short_distance)  # E -- 3 --> F == 3

__lowerCamelCase       				=	dijkstra(Ga, '''E''', '''F''')
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
    import doctest

    doctest.testmod()



