




"""simple docstring"""




from __future__ import annotations

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

a_            =   TypeVar('T')
a_            =   TypeVar('U')

class        UpperCAmelCase_  (	Generic[T, U]						):
		def __init__(		self							,		UpperCamelCase_							,		UpperCamelCase_   )		->   List[Any]:
					__lowercase	:       List[Any]				=   key
					__lowercase	:       Optional[int]				=   val
					__lowercase	:       int				=   0
					__lowercase	:       DoubleLinkedListNode[T, U] | None				=   None
					__lowercase	:       DoubleLinkedListNode[T, U] | None				=   None
		def __repr__(		self   )		->   str:
					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   )		->   None:
					__lowercase	:       DoubleLinkedListNode[T, U]				=   DoubleLinkedListNode(UpperCamelCase_							,		UpperCamelCase_   )
					__lowercase	:       DoubleLinkedListNode[T, U]				=   DoubleLinkedListNode(UpperCamelCase_							,		UpperCamelCase_   )
					__lowercase	,__lowercase	:       Dict				=   self.rear, self.head
		def __repr__(		self   )		->   str:
					__lowercase	:       List[Any]				=   ['''DoubleLinkedList''']
					__lowercase	:       Tuple				=   self.head
					while node.next is not None:
								rep.append(str(UpperCamelCase_   )   )
								__lowercase	:       List[Any]				=   node.next
					rep.append(str(self.rear   )   )
					return ",\n    ".join(UpperCamelCase_   )
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_   )		->   None:
					__lowercase	:       Optional[int]				=   self.rear.prev

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

					__lowercase	:       Any				=   node
					__lowercase	:       List[str]				=   previous
					__lowercase	:       int				=   node
					__lowercase	:       List[str]				=   self.rear
					node.freq += 1
					self._position_node(UpperCamelCase_   )
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_   )		->   None:

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

								__lowercase	:       Tuple				=   previous_node.prev
								__lowercase	:       Optional[Any]				=   node.prev
								__lowercase	:       str				=   previous_node
								__lowercase	:       Union[str, Any]				=   node
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_   )		->   DoubleLinkedListNode[T, U] | None:

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

					__lowercase	:       List[Any]				=   node.next
					__lowercase	:       int				=   node.prev
					__lowercase	:       Dict				=   None
					__lowercase	:       Union[str, Any]				=   None
					return node


class        UpperCAmelCase_  (	Generic[T, U]						):
		UpperCamelCase									={}
		def __init__(		self							,		UpperCamelCase_   )		->   Optional[int]:
					__lowercase	:       DoubleLinkedList[T, U]				=   DoubleLinkedList()
					__lowercase	:       Optional[Any]				=   capacity
					__lowercase	:       str				=   0
					__lowercase	:       Any				=   0
					__lowercase	:       Optional[int]				=   0
					__lowercase	:       dict[T, DoubleLinkedListNode[T, U]]				=   {}
		def __repr__(		self   )		->   str:
					return (
					    F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
					    F"""capacity={self.capacity}, current_size={self.num_keys})"""
					)
		def __contains__(		self							,		UpperCamelCase_   )		->   bool:
					return key in self.cache
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_   )		->   U | None:

					if key in self.cache:
								self.hits += 1
								__lowercase	:       DoubleLinkedListNode[T, U]				=   self.cache[key]
								__lowercase	:       List[str]				=   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(UpperCamelCase_   )
								return node.val
					self.miss += 1
					return None
		def 					_lowerCamelCase    (		self							,		UpperCamelCase_							,		UpperCamelCase_   )		->   None:

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

											del self.cache[first_node.key]
											self.num_keys -= 1
								__lowercase	:       Union[str, Any]				=   DoubleLinkedListNode(UpperCamelCase_							,		UpperCamelCase_   )
								self.list.add(self.cache[key]   )
								self.num_keys += 1

					else:
								__lowercase	:       Union[str, Any]				=   self.list.remove(self.cache[key]   )
								assert node is not None  # node guaranteed to be in list
								__lowercase	:       Dict				=   value
								self.list.add(UpperCamelCase_   )
		@classmethod
		def 					_lowerCamelCase    (		cls							,		UpperCamelCase_ = 1_28   )		->   Callable[[Callable[[T], U]], Callable[..., U]]:

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

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

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

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

								return cache_decorator_wrapper

					return cache_decorator_inner


if __name__ == "__main__":
			import doctest

			doctest.testmod()









"""simple docstring"""




a_            =   1_0_0_0







def       __UpperCAmelCase      (				__UpperCamelCase					):
			return x * x







def       __UpperCAmelCase      (				__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase					,							__UpperCamelCase = 4					):
			assert callable(
			    __UpperCamelCase					), f"""the function(object) passed should be callable your input : {function}"""
			assert isinstance(__UpperCamelCase					,							(float, int)					), f"""a should be float or integer your input : {a}"""
			assert isinstance(function(__UpperCamelCase					)					,							(float, int)					), (
			    "the function should return integer or float return type of your function, "
			    f"""{type(__UpperCamelCase					)}"""
			)
			assert isinstance(__UpperCamelCase					,							(float, int)					), f"""b should be float or integer your input : {b}"""
			assert (
			    isinstance(__UpperCamelCase					,							__UpperCamelCase					) and precision > 0
			), f"""precision should be positive integer your input : {precision}"""

			# just applying the formula of simpson for approximate integration written in
			# mentioned article in first comment of this file and above this function

			__lowercase	:       Optional[Any]				=   (b - a) / N_STEPS
			__lowercase	:       Optional[int]				=   function(__UpperCamelCase					) + function(__UpperCamelCase					)

			for i in range(1					,							__UpperCamelCase					):
						__lowercase	:       Union[str, Any]				=   a + h * i
						result += function(__UpperCamelCase					) * (4 if i % 2 else 2)

			result *= h / 3
			return round(__UpperCamelCase					,							__UpperCamelCase					)


if __name__ == "__main__":
			import doctest

			doctest.testmod()



