




from __future__ import annotations

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

_lowerCAmelCase				     = TypeVar('''T''')
_lowerCAmelCase				     = TypeVar('''U''')



class  A		(			Generic[T, U]		):




				'''simple docstring'''





				def __init__(self			,  _UpperCAmelCase			,  _UpperCAmelCase      )     ->	Optional[int]:
							__UpperCamelCase				:      Optional[int]									=       key
							__UpperCamelCase				:      str									=       val
							__UpperCamelCase				:      int									=       0
							__UpperCamelCase				:      DoubleLinkedListNode[T, U] | None									=       None
							__UpperCamelCase				:      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  A		(			Generic[T, U]		):




				'''simple docstring'''





				def __init__(self      )     ->	None:
							__UpperCamelCase				:      DoubleLinkedListNode[T, U]									=       DoubleLinkedListNode(_UpperCAmelCase			,  _UpperCAmelCase      )
							__UpperCamelCase				:      DoubleLinkedListNode[T, U]									=       DoubleLinkedListNode(_UpperCAmelCase			,  _UpperCAmelCase      )
							__UpperCamelCase				:      List[Any]									=       self.rear, self.head
				def __repr__(self      )     ->	str:
							__UpperCamelCase				:      Dict									=       ["DoubleLinkedList"]
							__UpperCamelCase				:      Any									=       self.head
							while node.next is not None:
										rep.append(str(_UpperCAmelCase      )      )
										__UpperCamelCase				:      Any									=       node.next
							rep.append(str(self.rear      )      )
							return ",\n    ".join(_UpperCAmelCase      )
				def 	a_	(self			,  _UpperCAmelCase      )     ->	None:
							__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				:      Union[str, Any]									=       node
							__UpperCamelCase				:      Optional[int]									=       previous
							__UpperCamelCase				:      Tuple									=       node
							__UpperCamelCase				:      int									=       self.rear
							node.freq += 1
							self._position_node(_UpperCAmelCase      )
				def 	a_	(self			,  _UpperCAmelCase      )     ->	None:

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

										__UpperCamelCase				:      int									=       previous_node.prev
										__UpperCamelCase				:      Any									=       node.prev
										__UpperCamelCase				:      str									=       previous_node
										__UpperCamelCase				:      Optional[int]									=       node





				def 	a_	(self			,  _UpperCAmelCase      )     ->	DoubleLinkedListNode[T, U] | None:

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

							__UpperCamelCase				:      str									=       node.next
							__UpperCamelCase				:      Union[str, Any]									=       node.prev
							__UpperCamelCase				:      Union[str, Any]									=       None
							__UpperCamelCase				:      Union[str, Any]									=       None
							return node







class  A		(			Generic[T, U]		):




				'''simple docstring'''





				A				     =    {}
				def __init__(self			,  _UpperCAmelCase      )     ->	Optional[Any]:
							__UpperCamelCase				:      DoubleLinkedList[T, U]									=       DoubleLinkedList()
							__UpperCamelCase				:      Optional[Any]									=       capacity
							__UpperCamelCase				:      Union[str, Any]									=       0
							__UpperCamelCase				:      Dict									=       0
							__UpperCamelCase				:      List[Any]									=       0
							__UpperCamelCase				:      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 	a_	(self			,  _UpperCAmelCase      )     ->	U | None:

							if key in self.cache:
										self.hits += 1
										__UpperCamelCase				:      DoubleLinkedListNode[T, U]									=       self.cache[key]
										__UpperCamelCase				:      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 	a_	(self			,  _UpperCAmelCase			,  _UpperCAmelCase      )     ->	None:

							if key not in self.cache:
										if self.num_keys >= self.capacity:
													# delete first node when over capacity
													__UpperCamelCase				:      Union[str, Any]									=       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
										__UpperCamelCase				:      Optional[int]									=       DoubleLinkedListNode(_UpperCAmelCase			,  _UpperCAmelCase      )
										self.list.add(self.cache[key]      )
										self.num_keys += 1

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





				@classmethod
				def 	a_	(cls			,  _UpperCAmelCase = 1_2_8      )     ->	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:
																__UpperCamelCase				:      Optional[int]									=       LFUCache(_UpperCAmelCase      )

													__UpperCamelCase				:      List[Any]									=       cls.decorator_function_to_instance_map[func].get(args[0]      )
													if result is None:
																__UpperCamelCase				:      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'''






from doctest import testmod
from math import sqrt

def       __lowerCAmelCase (   snake_case__						):
			__UpperCamelCase				:      list[int]									=       []
			if num < 1:
						return facs
			facs.append(1						)
			if num == 1:
						return facs
			facs.append(snake_case__						)
			for i in range(2 ,				int(sqrt(snake_case__						)						) + 1						):
						if num % i == 0:  # If i is a factor of num
									facs.append(snake_case__						)
									__UpperCamelCase				:      List[str]									=       num // i  # num//i is the other factor of num
									if d != i:  # If d and i are distinct
												facs.append(snake_case__						)  # we have found another factor
			facs.sort()
			return facs


if __name__ == "__main__":
				testmod(name='''factors_of_a_number''', verbose=True)



