





"""simple docstring"""





from __future__ import annotations

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

_UpperCamelCase							=      TypeVar('T')
_UpperCamelCase							=      TypeVar('U')
class 		SCREAMING_SNAKE_CASE_							(    Generic[T, U]   ):




				def __init__(     self  :Union[str, Any]						,    __lowercase  :Optional[Any]						,    __lowercase  :Dict			):
											__lowerCamelCase      :      Optional[int]         =key
											__lowerCamelCase      :      List[Any]         =val
											__lowerCamelCase      :      Optional[int]         =None
											__lowerCamelCase      :      str         =None




				def __repr__(     self  :int			):
											return (
											    f'Node: key: {self.key}, val: {self.val}, '
											    f'has next: {bool(self.next			)}, has prev: {bool(self.prev			)}'
											)

class 		SCREAMING_SNAKE_CASE_							(    Generic[T, U]   ):




				def __init__(     self  :Tuple			):
											__lowerCamelCase      :      str         =DoubleLinkedListNode(A__						,    A__			)
											__lowerCamelCase      :      List[Any]         =DoubleLinkedListNode(A__						,    A__			)
											__lowerCamelCase    ,						__lowerCamelCase      :      str         =self.rear, self.head




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




				def 					__lowercase  (     self  :str						,    __lowercase  :Optional[Any]			):
											__lowerCamelCase      :      int         =self.rear.prev

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

											__lowerCamelCase      :      Optional[Any]         =node
											__lowerCamelCase      :      int         =previous
											__lowerCamelCase      :      Tuple         =node
											__lowerCamelCase      :      Union[str, Any]         =self.rear




				def 					__lowercase  (     self  :List[str]						,    __lowercase  :str			):

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

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

class 		SCREAMING_SNAKE_CASE_							(    Generic[T, U]   ):
				__snake_case   :       int	 =		{}




				def __init__(     self  :Union[str, Any]						,    __lowercase  :Union[str, Any]			):
											__lowerCamelCase      :      List[Any]         =DoubleLinkedList()
											__lowerCamelCase      :      Dict         =capacity
											__lowerCamelCase      :      Union[str, Any]         =0
											__lowerCamelCase      :      List[Any]         =0
											__lowerCamelCase      :      List[str]         =0
											__lowerCamelCase      :      Dict         ={}




				def __repr__(     self  :List[Any]			):
											return (
											    f'CacheInfo(hits={self.hits}, misses={self.miss}, '
											    f'capacity={self.capacity}, current size={self.num_keys})'
											)




				def __contains__(     self  :List[Any]						,    __lowercase  :List[Any]			):
											return key in self.cache




				def 					__lowercase  (     self  :Union[str, Any]						,    __lowercase  :int			):
											# Note: pythonic interface would throw KeyError rather than return None

											if key in self.cache:
																		self.hits += 1
																		__lowerCamelCase      :      Optional[int]         =self.cache[key]
																		__lowerCamelCase      :      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(A__			)
																		return node.val
											self.miss += 1
											return None




				def 					__lowercase  (     self  :List[Any]						,    __lowercase  :Dict						,    __lowercase  :List[str]			):

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

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




				@classmethod
				def 					__lowercase  (     cls  :Dict						,    __lowercase  :str = 128			):

											def cache_decorator_inner(__lowercase  :Union[str, Any]			) -> Callable[..., U]:
																		def cache_decorator_wrapper(*__lowercase  :int			) -> U:
																									if func not in cls.decorator_function_to_instance_map:
																																__lowerCamelCase      :      Union[str, Any]         =LRUCache(A__			)

																									__lowerCamelCase      :      Tuple         =cls.decorator_function_to_instance_map[func].get(args[0]			)
																									if result is None:
																																__lowerCamelCase      :      Any         =func(*A__			)
																																cls.decorator_function_to_instance_map[func].put(args[0]						,    A__			)
																									return result

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

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

																		return cache_decorator_wrapper

											return cache_decorator_inner


if __name__ == "__main__":
							import doctest

							doctest.testmod()











"""simple docstring"""





from typing import Any
class 		SCREAMING_SNAKE_CASE_							:
				"""simple docstring"""




				def __init__(     self  :Tuple						,    __lowercase  :Any			):
											__lowerCamelCase      :      str         =data
											__lowerCamelCase      :      Any         =None




				def __repr__(     self  :Optional[Any]			):
											return f'Node({self.data})'

class 		SCREAMING_SNAKE_CASE_							:
				"""simple docstring"""




				def __init__(     self  :Optional[int]			):
											__lowerCamelCase      :      Union[str, Any]         =None




				def __iter__(     self  :Optional[int]			):
											__lowerCamelCase      :      Optional[Any]         =self.head
											while node:
																		yield node.data
																		__lowerCamelCase      :      str         =node.next




				def __len__(     self  :Any			):
											return sum(1 for _ in self			)




				def __repr__(     self  :Any			):
											return "->".join([str(__lowercase			) for item in self]			)




				def __getitem__(     self  :Dict						,    __lowercase  :int			):
											if not 0 <= index < len(self			):
																		raise ValueError('''list index out of range.'''			)
											for i, node in enumerate(self			):
																		if i == index:
																									return node
											return None




				def __setitem__(     self  :Dict						,    __lowercase  :int						,    __lowercase  :Any			):
											if not 0 <= index < len(self			):
																		raise ValueError('''list index out of range.'''			)
											__lowerCamelCase      :      Optional[Any]         =self.head
											for _ in range(__lowercase			):
																		__lowerCamelCase      :      List[str]         =current.next
											__lowerCamelCase      :      Optional[int]         =data




				def 					__lowercase  (     self  :Tuple						,    __lowercase  :Any			):
											self.insert_nth(len(self			)						,    __lowercase			)




				def 					__lowercase  (     self  :int						,    __lowercase  :Any			):
											self.insert_nth(0						,    __lowercase			)




				def 					__lowercase  (     self  :Dict						,    __lowercase  :int						,    __lowercase  :Any			):
											if not 0 <= index <= len(self			):
																		raise IndexError('''list index out of range'''			)
											__lowerCamelCase      :      List[Any]         =Node(__lowercase			)
											if self.head is None:
																		__lowerCamelCase      :      List[Any]         =new_node
											elif index == 0:
																		__lowerCamelCase      :      Optional[Any]         =self.head  # link new_node to head
																		__lowerCamelCase      :      Optional[Any]         =new_node
											else:
																		__lowerCamelCase      :      str         =self.head
																		for _ in range(index - 1			):
																									__lowerCamelCase      :      Any         =temp.next
																		__lowerCamelCase      :      List[Any]         =temp.next
																		__lowerCamelCase      :      List[Any]         =new_node




				def 					__lowercase  (     self  :Tuple			):  # print every node data
											print(self			)




				def 					__lowercase  (     self  :List[str]			):
											return self.delete_nth(0			)




				def 					__lowercase  (     self  :Any			):  # delete from tail
											return self.delete_nth(len(self			) - 1			)




				def 					__lowercase  (     self  :Dict						,    __lowercase  :int = 0			):
											if not 0 <= index <= len(self			) - 1:  # test if index is valid
																		raise IndexError('''List index out of range.'''			)
											__lowerCamelCase      :      List[Any]         =self.head  # default first node
											if index == 0:
																		__lowerCamelCase      :      int         =self.head.next
											else:
																		__lowerCamelCase      :      int         =self.head
																		for _ in range(index - 1			):
																									__lowerCamelCase      :      str         =temp.next
																		__lowerCamelCase      :      int         =temp.next
																		__lowerCamelCase      :      Optional[Any]         =temp.next.next
											return delete_node.data




				def 					__lowercase  (     self  :Any			):
											return self.head is None




				def 					__lowercase  (     self  :Tuple			):
											__lowerCamelCase      :      Any         =None
											__lowerCamelCase      :      Optional[int]         =self.head

											while current:
																		# Store the current node's next node.
																		__lowerCamelCase      :      Any         =current.next
																		# Make the current node's next point backwards
																		__lowerCamelCase      :      Optional[Any]         =prev
																		# Make the previous node be the current node
																		__lowerCamelCase      :      List[str]         =current
																		# Make the current node the next node (to progress iteration)
																		__lowerCamelCase      :      Tuple         =next_node
											# Return prev in order to put the head at the end
											__lowerCamelCase      :      List[str]         =prev



def 				lowerCAmelCase_			(      ):


							'''simple docstring'''







							__lowerCamelCase      :      Tuple         =LinkedList()
							assert linked_list.is_empty() is True
							assert str(SCREAMING_SNAKE_CASE   ) == ""

							try:
														linked_list.delete_head()
														raise AssertionError  # This should not happen.
							except IndexError:
														assert True  # This should happen.

							try:
														linked_list.delete_tail()
														raise AssertionError  # This should not happen.
							except IndexError:
														assert True  # This should happen.

							for i in range(10   ):
														assert len(SCREAMING_SNAKE_CASE   ) == i
														linked_list.insert_nth(SCREAMING_SNAKE_CASE    ,						i + 1   )
							assert str(SCREAMING_SNAKE_CASE   ) == "->".join(str(SCREAMING_SNAKE_CASE   ) for i in range(1    ,						11   )   )

							linked_list.insert_head(0   )
							linked_list.insert_tail(11   )
							assert str(SCREAMING_SNAKE_CASE   ) == "->".join(str(SCREAMING_SNAKE_CASE   ) for i in range(0    ,						12   )   )

							assert linked_list.delete_head() == 0
							assert linked_list.delete_nth(9   ) == 10
							assert linked_list.delete_tail() == 11
							assert len(SCREAMING_SNAKE_CASE   ) == 9
							assert str(SCREAMING_SNAKE_CASE   ) == "->".join(str(SCREAMING_SNAKE_CASE   ) for i in range(1    ,						10   )   )

							assert all(linked_list[i] == i + 1 for i in range(0    ,						9   )   ) is True

							for i in range(0    ,						9   ):
														__lowerCamelCase      :      List[Any]         =-i
							assert all(linked_list[i] == -i for i in range(0    ,						9   )   ) is True

							linked_list.reverse()
							assert str(SCREAMING_SNAKE_CASE   ) == "->".join(str(SCREAMING_SNAKE_CASE   ) for i in range(-8    ,						1   )   )



def 				lowerCAmelCase_			(      ):


							'''simple docstring'''







							__lowerCamelCase      :      Any         =[
							    -9,
							    100,
							    Node(77345112   ),
							    '''dlrow olleH''',
							    7,
							    5555,
							    0,
							    -192.55_555,
							    '''Hello, world!''',
							    77.9,
							    Node(10   ),
							    None,
							    None,
							    12.20,
							]
							__lowerCamelCase      :      str         =LinkedList()

							for i in test_input:
														linked_list.insert_tail(SCREAMING_SNAKE_CASE   )

							# Check if it's empty or not
							assert linked_list.is_empty() is False
							assert (
							    str(SCREAMING_SNAKE_CASE   ) == "-9->100->Node(77345112)->dlrow olleH->7->5555->0->"
							    "-192.55555->Hello, world!->77.9->Node(10)->None->None->12.2"
							)

							# Delete the head
							__lowerCamelCase      :      str         =linked_list.delete_head()
							assert result == -9
							assert (
							    str(SCREAMING_SNAKE_CASE   ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
							    "Hello, world!->77.9->Node(10)->None->None->12.2"
							)

							# Delete the tail
							__lowerCamelCase      :      Union[str, Any]         =linked_list.delete_tail()
							assert result == 12.2
							assert (
							    str(SCREAMING_SNAKE_CASE   ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
							    "Hello, world!->77.9->Node(10)->None->None"
							)

							# Delete a node in specific location in linked list
							__lowerCamelCase      :      Union[str, Any]         =linked_list.delete_nth(10   )
							assert result is None
							assert (
							    str(SCREAMING_SNAKE_CASE   ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
							    "Hello, world!->77.9->Node(10)->None"
							)

							# Add a Node instance to its head
							linked_list.insert_head(Node('''Hello again, world!'''   )   )
							assert (
							    str(SCREAMING_SNAKE_CASE   )
							    == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
							    "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None"
							)

							# Add None to its tail
							linked_list.insert_tail(SCREAMING_SNAKE_CASE   )
							assert (
							    str(SCREAMING_SNAKE_CASE   )
							    == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
							    "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None->None"
							)

							# Reverse the linked list
							linked_list.reverse()
							assert (
							    str(SCREAMING_SNAKE_CASE   )
							    == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
							    "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
							)



def 				lowerCAmelCase_			(      ):


							'''simple docstring'''







							from doctest import testmod

							testmod()

							__lowerCamelCase      :      Optional[Any]         =LinkedList()
							linked_list.insert_head(input('''Inserting 1st at head '''   ).strip()   )
							linked_list.insert_head(input('''Inserting 2nd at head '''   ).strip()   )
							print('''\nPrint list:'''   )
							linked_list.print_list()
							linked_list.insert_tail(input('''\nInserting 1st at tail '''   ).strip()   )
							linked_list.insert_tail(input('''Inserting 2nd at tail '''   ).strip()   )
							print('''\nPrint list:'''   )
							linked_list.print_list()
							print('''\nDelete head'''   )
							linked_list.delete_head()
							print('''Delete tail'''   )
							linked_list.delete_tail()
							print('''\nPrint list:'''   )
							linked_list.print_list()
							print('''\nReverse linked list'''   )
							linked_list.reverse()
							print('''\nPrint list:'''   )
							linked_list.print_list()
							print('''\nString representation of linked list:'''   )
							print(SCREAMING_SNAKE_CASE   )
							print('''\nReading/changing Node data using indexing:'''   )
							print(F'Element at Position 1: {linked_list[1]}'   )
							__lowerCamelCase      :      Any         =input('''Enter New Value: '''   ).strip()
							print('''New list:'''   )
							print(SCREAMING_SNAKE_CASE   )
							print(F'length of linked_list is : {len(SCREAMING_SNAKE_CASE   )}'   )


if __name__ == "__main__":
							main()




