


"""simple docstring"""




from __future__ import annotations

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

__UpperCamelCase						=      TypeVar('''T''')
__UpperCamelCase						=      TypeVar('''U''')
class 					lowerCAmelCase	(					Generic[T, U]    ):




		'''simple docstring'''







		def __init__(	self						,       lowerCAmelCase__						,       lowerCAmelCase__				)     ->							Optional[int]:
								SCREAMING_SNAKE_CASE													=					key
								SCREAMING_SNAKE_CASE													=					val
								SCREAMING_SNAKE_CASE													=					None
								SCREAMING_SNAKE_CASE													=					None







		def __repr__(	self				)     ->							str:
								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				)     ->							None:
								SCREAMING_SNAKE_CASE													=					DoubleLinkedListNode(lowerCAmelCase__						,       lowerCAmelCase__				)
								SCREAMING_SNAKE_CASE													=					DoubleLinkedListNode(lowerCAmelCase__						,       lowerCAmelCase__				)
								SCREAMING_SNAKE_CASE							,				SCREAMING_SNAKE_CASE													=					self.rear, self.head







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







		def 							__A						(	self						,       lowerCAmelCase__				)     ->							None:
								SCREAMING_SNAKE_CASE													=					self.rear.prev

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

								SCREAMING_SNAKE_CASE													=					node
								SCREAMING_SNAKE_CASE													=					previous
								SCREAMING_SNAKE_CASE													=					node
								SCREAMING_SNAKE_CASE													=					self.rear







		def 							__A						(	self						,       lowerCAmelCase__				)     ->							DoubleLinkedListNode[T, U] | None:

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

								SCREAMING_SNAKE_CASE													=					node.next
								SCREAMING_SNAKE_CASE													=					node.prev
								SCREAMING_SNAKE_CASE													=					None
								SCREAMING_SNAKE_CASE													=					None
								return node





class 					lowerCAmelCase	(					Generic[T, U]    ):




		'''simple docstring'''







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







		def __init__(	self						,       lowerCAmelCase__				)     ->							int:
								SCREAMING_SNAKE_CASE													=					DoubleLinkedList()
								SCREAMING_SNAKE_CASE													=					capacity
								SCREAMING_SNAKE_CASE													=					0
								SCREAMING_SNAKE_CASE													=					0
								SCREAMING_SNAKE_CASE													=					0
								SCREAMING_SNAKE_CASE													=					{}







		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						,       lowerCAmelCase__				)     ->							bool:
								return key in self.cache







		def 							__A						(	self						,       lowerCAmelCase__				)     ->							U | None:
								# Note: pythonic interface would throw KeyError rather than return None

								if key in self.cache:
														self.hits += 1
														SCREAMING_SNAKE_CASE													=					self.cache[key]
														SCREAMING_SNAKE_CASE													=					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 							__A						(	self						,       lowerCAmelCase__						,       lowerCAmelCase__				)     ->							None:

								if key not in self.cache:
														if self.num_keys >= self.capacity:
																				# delete first node (oldest) when over capacity
																				SCREAMING_SNAKE_CASE													=					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
														SCREAMING_SNAKE_CASE													=					DoubleLinkedListNode(lowerCAmelCase__						,       lowerCAmelCase__				)
														self.list.add(self.cache[key]				)
														self.num_keys += 1

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







		@classmethod
		def 							__A						(	cls						,       lowerCAmelCase__ = 128				)     ->							Callable[[Callable[[T], U]], Callable[..., U]]:

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

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




# This is the module that test_patching.py uses to test patch_submodule()

import os  # noqa: this is just for tests
import os as renamed_os  # noqa: this is just for tests
from os import path  # noqa: this is just for tests
from os import path as renamed_path  # noqa: this is just for tests
from os.path import join  # noqa: this is just for tests
from os.path import join as renamed_join  # noqa: this is just for tests


__UpperCamelCase						=      open  # noqa: we just need to have a builtin inside this module to test it properly


