



from __future__ import annotations

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

__SCREAMING_SNAKE_CASE  :						Optional[Any]    							=      TypeVar('''T''')
__SCREAMING_SNAKE_CASE  :						List[str]    							=      TypeVar('''U''')


class 							lowerCamelCase_(   Generic[T, U]    ):





					'''simple docstring'''



					def __init__(    self				,       lowerCamelCase__				,       lowerCamelCase__   ):
									_lowerCamelCase        =				key
									_lowerCamelCase        =				val
									_lowerCamelCase        =				None
									_lowerCamelCase        =				None





					def __repr__(    self   ):
									return (
									    F"""Node: key: {self.key}, val: {self.val}, """
									    F"""has next: {bool(self.next   )}, has prev: {bool(self.prev   )}"""
									)


class 							lowerCamelCase_(   Generic[T, U]    ):





					'''simple docstring'''



					def __init__(    self   ):
									_lowerCamelCase        =				DoubleLinkedListNode(lowerCamelCase__				,       lowerCamelCase__   )
									_lowerCamelCase        =				DoubleLinkedListNode(lowerCamelCase__				,       lowerCamelCase__   )
									_lowerCamelCase  ,     _lowerCamelCase        =				self.rear, self.head

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

					def 			snake_case__      (    self				,       lowerCamelCase__   ):
									_lowerCamelCase        =				self.rear.prev

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

									_lowerCamelCase        =				node
									_lowerCamelCase        =				previous
									_lowerCamelCase        =				node
									_lowerCamelCase        =				self.rear





					def 			snake_case__      (    self				,       lowerCamelCase__   ):

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

									_lowerCamelCase        =				node.next
									_lowerCamelCase        =				node.prev
									_lowerCamelCase        =				None
									_lowerCamelCase        =				None
									return node


class 							lowerCamelCase_(   Generic[T, U]    ):





					'''simple docstring'''



					lowercase__   :       dict[Callable[[T], U], LRUCache[T, U]]										= {}

					def __init__(    self				,       lowerCamelCase__   ):
									_lowerCamelCase        =				DoubleLinkedList()
									_lowerCamelCase        =				capacity
									_lowerCamelCase        =				0
									_lowerCamelCase        =				0
									_lowerCamelCase        =				0
									_lowerCamelCase        =				{}

					def __repr__(    self   ):
									return (
									    F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
									    F"""capacity={self.capacity}, current size={self.num_keys})"""
									)

					def __contains__(    self				,       lowerCamelCase__   ):
									return key in self.cache

					def 			snake_case__      (    self				,       lowerCamelCase__   ):
									# Note: pythonic interface would throw KeyError rather than return None

									if key in self.cache:
													self.hits += 1
													_lowerCamelCase        =				self.cache[key]
													_lowerCamelCase        =				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 			snake_case__      (    self				,       lowerCamelCase__				,       lowerCamelCase__   ):

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

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

									else:
													# bump node to the end of the list, update value
													_lowerCamelCase        =				self.list.remove(self.cache[key]   )
													assert node is not None  # node guaranteed to be in list
													_lowerCamelCase        =				value
													self.list.add(lowerCamelCase__   )





					@classmethod
					def 			snake_case__      (    cls				,       lowerCamelCase__ = 1_2_8   ):

									def cache_decorator_inner(lowerCamelCase__   ) -> Callable[..., U]:
													def cache_decorator_wrapper(*lowerCamelCase__   ) -> U:
																	if func not in cls.decorator_function_to_instance_map:
																					_lowerCamelCase        =				LRUCache(lowerCamelCase__   )

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

													def cache_info() -> LRUCache[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"""
from __future__ import annotations

from typing import Any



def        lowerCAmelCase_(   lowercase_     :							list[Any]							)	->       None:
				create_state_space_tree(lowercase_						,   []						,   0							)



def        lowerCAmelCase_(   lowercase_     :							list[Any]						,   lowercase_     :							list[Any]						,   lowercase_     :							int							)	->       None:

				if index == len(lowercase_							):
								print(lowercase_							)
								return

				create_state_space_tree(lowercase_						,   lowercase_						,   index + 1							)
				current_subsequence.append(sequence[index]							)
				create_state_space_tree(lowercase_						,   lowercase_						,   index + 1							)
				current_subsequence.pop()


if __name__ == "__main__":
			__SCREAMING_SNAKE_CASE  :						list[Any]    							=      [3, 1, 2, 4]
			generate_all_subsequences(seq)

			seq.clear()
			seq.extend(['''A''', '''B''', '''C'''])
			generate_all_subsequences(seq)
