


from __future__ import annotations

import sys
from collections import deque
from typing import Generic, TypeVar

a : Any		=				TypeVar('''T''')
class 	lowerCamelCase_       (				Generic[T]				):



					'''simple docstring'''







					__UpperCAmelCase            =				42  # Cache store of keys
					__UpperCAmelCase            =				42  # References of the keys in cache
					__UpperCAmelCase            =				10  # Maximum capacity of cache






					def __init__(				self ,       snake_case_						)   ->			None:







								'''simple docstring'''

								__lowercase 					=   deque()
								__lowercase 					=   set()
								if not n:
											__lowercase 					=   sys.maxsize
								elif n < 0:
											raise ValueError('''n should be an integer greater than 0.'''						)
								else:
											__lowercase 					=   n






					def A      (				self ,       snake_case_						)   ->			None:







								'''simple docstring'''

								if x not in self.key_reference:
											if len(self.dq_store						) == LRUCache._MAX_CAPACITY:
														__lowercase 					=   self.dq_store.pop()
														self.key_reference.remove(snake_case_						)
								else:
											self.dq_store.remove(snake_case_						)

								self.dq_store.appendleft(snake_case_						)
								self.key_reference.add(snake_case_						)






					def A      (				self						)   ->			None:







								'''simple docstring'''

								for k in self.dq_store:
											print(snake_case_						)






					def __repr__(				self						)   ->			str:







								'''simple docstring'''

								return F'LRUCache({self._MAX_CAPACITY}) => {list(self.dq_store						)}'


if __name__ == "__main__":
	import doctest

	doctest.testmod()

	a : Optional[Any]		=				LRUCache(4)
	lru_cache.refer('''A''')
	lru_cache.refer(2)
	lru_cache.refer(3)
	lru_cache.refer('''A''')
	lru_cache.refer(4)
	lru_cache.refer(5)
	lru_cache.display()

	print(lru_cache)
	assert str(lru_cache) == "LRUCache(4) => [5, 4, 'A', 3]"






import unittest

from knapsack import knapsack as k
class 	lowerCamelCase_       (				unittest.TestCase				):



					'''simple docstring'''







					def A      (				self						)   ->			Optional[Any]:







								'''simple docstring'''

								__lowercase 					=   0
								__lowercase 					=   [0]
								__lowercase 					=   [0]
								__lowercase 					=   len(snake_case_						)
								self.assertEqual(k.knapsack(snake_case_ ,       snake_case_ ,       snake_case_ ,       snake_case_						) ,       0						)

								__lowercase 					=   [6_0]
								__lowercase 					=   [1_0]
								__lowercase 					=   len(snake_case_						)
								self.assertEqual(k.knapsack(snake_case_ ,       snake_case_ ,       snake_case_ ,       snake_case_						) ,       0						)






					def A      (				self						)   ->			Tuple:







								'''simple docstring'''

								__lowercase 					=   3
								__lowercase 					=   [1, 2, 3]
								__lowercase 					=   [3, 2, 1]
								__lowercase 					=   len(snake_case_						)
								self.assertEqual(k.knapsack(snake_case_ ,       snake_case_ ,       snake_case_ ,       snake_case_						) ,       5						)






					def A      (				self						)   ->			str:







								'''simple docstring'''

								__lowercase 					=   5_0
								__lowercase 					=   [6_0, 1_0_0, 1_2_0]
								__lowercase 					=   [1_0, 2_0, 3_0]
								__lowercase 					=   len(snake_case_						)
								self.assertEqual(k.knapsack(snake_case_ ,       snake_case_ ,       snake_case_ ,       snake_case_						) ,       2_2_0						)


if __name__ == "__main__":
	unittest.main()


