class       __SCREAMING_SNAKE_CASE   :






						def __init__(		self       ,  _UpperCamelCase       ,  _UpperCamelCase=None       ,  _UpperCamelCase=None				):






												"""simple docstring"""
												lowerCAmelCase__        =  data
												lowerCAmelCase__        =  previous
												lowerCAmelCase__        =  next_node






						def __str__(		self				):






												"""simple docstring"""
												return F"{self.data}"






						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												return self.data






						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												return self.next







						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												return self.previous




class       __SCREAMING_SNAKE_CASE   :






						def __init__(		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												lowerCAmelCase__        =  head






						def __iter__(		self				):






												"""simple docstring"""
												return self







						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												if not self.current:
																		raise StopIteration
												else:
																		lowerCAmelCase__        =  self.current.get_data()
																		lowerCAmelCase__        =  self.current.get_next()
																		return value




class       __SCREAMING_SNAKE_CASE   :






						def __init__(		self				):






												"""simple docstring"""
												lowerCAmelCase__        =  None  # First node in list
												lowerCAmelCase__        =  None  # Last node in list






						def __str__(		self				):






												"""simple docstring"""
												lowerCAmelCase__        =  self.head
												lowerCAmelCase__        =  []
												while current is not None:
																		nodes.append(current.get_data()				)
																		lowerCAmelCase__        =  current.get_next()
												return " ".join(str(_UpperCamelCase				) for node in nodes				)






						def __contains__(		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												lowerCAmelCase__        =  self.head
												while current:
																		if current.get_data() == value:
																								return True
																		lowerCAmelCase__        =  current.get_next()
												return False






						def __iter__(		self				):






												"""simple docstring"""
												return LinkedListIterator(self.head				)






						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												if self.head:
																		return self.head.get_data()
												return None






						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												if self.tail:
																		return self.tail.get_data()
												return None






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												if self.head is None:
																		lowerCAmelCase__        =  node
																		lowerCAmelCase__        =  node
												else:
																		self.insert_before_node(self.head       ,  _UpperCamelCase				)






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												if self.head is None:
																		self.set_head(_UpperCamelCase				)
												else:
																		self.insert_after_node(self.tail       ,  _UpperCamelCase				)






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												lowerCAmelCase__        =  Node(_UpperCamelCase				)
												if self.head is None:
																		self.set_head(_UpperCamelCase				)
												else:
																		self.set_tail(_UpperCamelCase				)






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase       ,  _UpperCamelCase				):






												"""simple docstring"""
												lowerCAmelCase__        =  node
												lowerCAmelCase__        =  node.previous

												if node.get_previous() is None:
																		lowerCAmelCase__        =  node_to_insert
												else:
																		lowerCAmelCase__        =  node_to_insert

												lowerCAmelCase__        =  node_to_insert






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase       ,  _UpperCamelCase				):






												"""simple docstring"""
												lowerCAmelCase__        =  node
												lowerCAmelCase__        =  node.next

												if node.get_next() is None:
																		lowerCAmelCase__        =  node_to_insert
												else:
																		lowerCAmelCase__        =  node_to_insert

												lowerCAmelCase__        =  node_to_insert






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase       ,  _UpperCamelCase				):






												"""simple docstring"""
												lowerCAmelCase__        =  1
												lowerCAmelCase__        =  Node(_UpperCamelCase				)
												lowerCAmelCase__        =  self.head
												while node:
																		if current_position == position:
																								self.insert_before_node(_UpperCamelCase       ,  _UpperCamelCase				)
																								return
																		current_position += 1
																		lowerCAmelCase__        =  node.next
												self.insert_after_node(self.tail       ,  _UpperCamelCase				)






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												lowerCAmelCase__        =  self.head
												while node:
																		if node.get_data() == item:
																								return node
																		lowerCAmelCase__        =  node.get_next()
												raise Exception('Node not found'				)






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												if (node := self.get_node(_UpperCamelCase				)) is not None:
																		if node == self.head:
																								lowerCAmelCase__        =  self.head.get_next()

																		if node == self.tail:
																								lowerCAmelCase__        =  self.tail.get_previous()

																		self.remove_node_pointers(_UpperCamelCase				)






						@staticmethod
						def  UpperCamelCase__ (		_UpperCamelCase				):






												"""simple docstring"""
												if node.get_next():
																		lowerCAmelCase__        =  node.previous

												if node.get_previous():
																		lowerCAmelCase__        =  node.next

												lowerCAmelCase__        =  None
												lowerCAmelCase__        =  None







						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												return self.head is None







def 		_UpperCamelCase				(      )					->				None:

						"""simple docstring"""








if __name__ == "__main__":
					import doctest

					doctest.testmod()













from collections.abc import Iterator, MutableMapping
from dataclasses import dataclass
from typing import Generic, TypeVar

__snake_case      :      Optional[Any]             =       TypeVar("""KEY""")
__snake_case      :      str             =       TypeVar("""VAL""")


@dataclass(frozen=__lowercase						,   slots=__lowercase)
class       __SCREAMING_SNAKE_CASE   (				Generic[KEY, VAL]):
						_SCREAMING_SNAKE_CASE		:    KEY
						_SCREAMING_SNAKE_CASE		:    VAL




class       __SCREAMING_SNAKE_CASE   (				_Item):






						def __init__(		self				):






												"""simple docstring"""
												super().__init__(_UpperCamelCase       ,  _UpperCamelCase				)







						def __bool__(		self				):






												"""simple docstring"""
												return False




__snake_case      :      int             =       _DeletedItem()


class       __SCREAMING_SNAKE_CASE   (				MutableMapping[KEY, VAL]):






						def __init__(		self       ,  _UpperCamelCase = 8       ,  _UpperCamelCase = 0.75				):






												"""simple docstring"""
												lowerCAmelCase__        =  initial_block_size
												lowerCAmelCase__        =  [None] * initial_block_size
												assert 0.0 < capacity_factor < 1.0
												lowerCAmelCase__        =  capacity_factor
												lowerCAmelCase__        =  0






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												return hash(_UpperCamelCase				) % len(self._buckets				)






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												return (ind + 1) % len(self._buckets				)






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase       ,  _UpperCamelCase       ,  _UpperCamelCase				):






												"""simple docstring"""
												lowerCAmelCase__        =  self._buckets[ind]
												if not stored:
																		lowerCAmelCase__        =  _Item(_UpperCamelCase       ,  _UpperCamelCase				)
																		self._len += 1
																		return True
												elif stored.key == key:
																		lowerCAmelCase__        =  _Item(_UpperCamelCase       ,  _UpperCamelCase				)
																		return True
												else:
																		return False






						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												lowerCAmelCase__        =  len(self._buckets				) * self._capacity_factor
												return len(self				) >= int(_UpperCamelCase				)






						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												if len(self._buckets				) <= self._initial_block_size:
																		return False
												lowerCAmelCase__        =  len(self._buckets				) * self._capacity_factor / 2
												return len(self				) < limit






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												lowerCAmelCase__        =  self._buckets
												lowerCAmelCase__        =  [None] * new_size
												lowerCAmelCase__        =  0
												for item in old_buckets:
																		if item:
																								self._add_item(item.key       ,  item.val				)






						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												self._resize(len(self._buckets				) * 2				)






						def  UpperCamelCase__ (		self				):






												"""simple docstring"""
												self._resize(len(self._buckets				) // 2				)






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												lowerCAmelCase__        =  self._get_bucket_index(_UpperCamelCase				)
												for _ in range(len(self._buckets				)				):
																		yield ind
																		lowerCAmelCase__        =  self._get_next_ind(_UpperCamelCase				)






						def  UpperCamelCase__ (		self       ,  _UpperCamelCase       ,  _UpperCamelCase				):






												"""simple docstring"""
												for ind in self._iterate_buckets(_UpperCamelCase				):
																		if self._try_set(_UpperCamelCase       ,  _UpperCamelCase       ,  _UpperCamelCase				):
																								break






						def __setitem__(		self       ,  _UpperCamelCase       ,  _UpperCamelCase				):






												"""simple docstring"""
												if self._is_full():
																		self._size_up()

												self._add_item(_UpperCamelCase       ,  _UpperCamelCase				)






						def __delitem__(		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												for ind in self._iterate_buckets(_UpperCamelCase				):
																		lowerCAmelCase__        =  self._buckets[ind]
																		if item is None:
																								raise KeyError(_UpperCamelCase				)
																		if item is _deleted:
																								continue
																		if item.key == key:
																								lowerCAmelCase__        =  _deleted
																								self._len -= 1
																								break
												if self._is_sparse():
																		self._size_down()






						def __getitem__(		self       ,  _UpperCamelCase				):






												"""simple docstring"""
												for ind in self._iterate_buckets(_UpperCamelCase				):
																		lowerCAmelCase__        =  self._buckets[ind]
																		if item is None:
																								break
																		if item is _deleted:
																								continue
																		if item.key == key:
																								return item.val
												raise KeyError(_UpperCamelCase				)






						def __len__(		self				):






												"""simple docstring"""
												return self._len






						def __iter__(		self				):






												"""simple docstring"""
												yield from (item.key for item in self._buckets if item)







						def __repr__(		self				):






												"""simple docstring"""
												lowerCAmelCase__        =  ' ,'.join(
												    F"{item.key}: {item.val}" for item in self._buckets if item				)
												return F"HashMap({val_string})"





