





from __future__ import annotations

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

UpperCamelCase__ :			List[Any]       	=			TypeVar("""T""")
UpperCamelCase__ :			Optional[Any]       	=			TypeVar("""U""")







class 	_UpperCamelCase	(							Generic[T, U]	):







					'''simple docstring'''

					def __init__(    self     :	Optional[int]			,       __lowercase     :	T | None			,       __lowercase     :	U | None		):






						'''simple docstring'''







						UpperCAmelCase_		    =  key
						UpperCAmelCase_		    =  val
						UpperCAmelCase_		    =  0
						UpperCAmelCase_		    =  None
						UpperCAmelCase_		    =  None





					def __repr__(    self     :	Dict		):






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







					'''simple docstring'''

					def __init__(    self     :	Tuple		):






						'''simple docstring'''







						UpperCAmelCase_		    =  DoubleLinkedListNode(__lowercase			,       __lowercase		)
						UpperCAmelCase_		    =  DoubleLinkedListNode(__lowercase			,       __lowercase		)
						UpperCAmelCase_    ,						UpperCAmelCase_		    =  self.rear, self.head





					def __repr__(    self     :	Optional[Any]		):






						'''simple docstring'''







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





					def 							SCREAMING_SNAKE_CASE				(    self     :	List[Any]			,       __lowercase     :	DoubleLinkedListNode[T, U]		):






						'''simple docstring'''







						UpperCAmelCase_		    =  self.rear.prev

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

						UpperCAmelCase_		    =  node
						UpperCAmelCase_		    =  previous
						UpperCAmelCase_		    =  node
						UpperCAmelCase_		    =  self.rear
						node.freq += 1
						self._position_node(__lowercase		)





					def 							SCREAMING_SNAKE_CASE				(    self     :	Tuple			,       __lowercase     :	DoubleLinkedListNode[T, U]		):






						'''simple docstring'''







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

							UpperCAmelCase_		    =  previous_node.prev
							UpperCAmelCase_		    =  node.prev
							UpperCAmelCase_		    =  previous_node
							UpperCAmelCase_		    =  node





					def 							SCREAMING_SNAKE_CASE				(    self     :	Optional[Any]			,       __lowercase     :	DoubleLinkedListNode[T, U]		):






						'''simple docstring'''







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

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







class 	_UpperCamelCase	(							Generic[T, U]	):







					'''simple docstring'''

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





					def __init__(    self     :	Dict			,       __lowercase     :	int		):






						'''simple docstring'''







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





					def __repr__(    self     :	int		):






						'''simple docstring'''







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





					def __contains__(    self     :	Optional[Any]			,       __lowercase     :	T		):






						'''simple docstring'''







						return key in self.cache





					def 							SCREAMING_SNAKE_CASE				(    self     :	Tuple			,       __lowercase     :	T		):






						'''simple docstring'''







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





					def 							SCREAMING_SNAKE_CASE				(    self     :	Dict			,       __lowercase     :	T			,       __lowercase     :	U		):






						'''simple docstring'''







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

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

						else:
							UpperCAmelCase_		    =  self.list.remove(self.cache[key]		)
							assert node is not None  # node guaranteed to be in list
							UpperCAmelCase_		    =  value
							self.list.add(__lowercase		)





					@classmethod
					def 							SCREAMING_SNAKE_CASE				(    cls     :	type[LFUCache[T, U]]			,       __lowercase     :	int = 1_28		):






						'''simple docstring'''







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

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

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

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

							return cache_decorator_wrapper

						return cache_decorator_inner


if __name__ == "__main__":
				import doctest

				doctest.testmod()









import doctest

import projectq
from projectq.ops import H, Measure




def  A_(      A ):
	UpperCAmelCase_		    =  quantum_engine.allocate_qubit()
	H | qubit
	Measure | qubit
	return int(A )


if __name__ == "__main__":
				doctest.testmod()

				# initialises a new quantum backend
				UpperCamelCase__ :			Dict       	=			projectq.MainEngine()

				# Generate a list of 10 random numbers
				UpperCamelCase__ :			Dict       	=			[get_random_number(quantum_engine) for _ in range(10)]

				# Flushes the quantum engine from memory
				quantum_engine.flush()

				print("""Random numbers""", random_numbers_list)


