



"""simple docstring"""







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

lowerCAmelCase_   						=   TypeVar('KEY')
lowerCAmelCase_   						=   TypeVar('VAL')
@dataclass(frozen=A_     ,slots=A_    )
class        __A       (	Generic[KEY, VAL]    ):







		'''simple docstring'''





		lowerCAmelCase			:					Optional[int]   	=				4_2
		lowerCAmelCase			:					List[str]   	=				4_2





class        __A       (	_Item    ):







		'''simple docstring'''





		def __init__(	self						:  Optional[Any]						)					->		None:






				"""simple docstring"""



				super().__init__(_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE						)







		def __bool__(	self						:  Dict						)					->		bool:






				"""simple docstring"""



				return False





lowerCAmelCase_   						=   _DeletedItem()
class        __A       (	MutableMapping[KEY, VAL]    ):







		'''simple docstring'''





		def __init__(	self						:  List[str]			,_snake_case						:  Tuple = 8			,_snake_case						:  Optional[Any] = 0.75						)					->		None:






				"""simple docstring"""



				lowercase__   :    Any				=			initial_block_size
				lowercase__   :    list[_Item | None]				=			[None] * initial_block_size
				assert 0.0 < capacity_factor < 1.0
				lowercase__   :    int				=			capacity_factor
				lowercase__   :    str				=			0







		def 					UpperCAmelCase    (	self						:  str			,_snake_case						:  List[Any]						)					->		int:






				"""simple docstring"""



				return hash(_SCREAMING_SNAKE_CASE						) % len(self._buckets						)







		def 					UpperCAmelCase    (	self						:  Union[str, Any]			,_snake_case						:  Optional[int]						)					->		int:






				"""simple docstring"""



				return (ind + 1) % len(self._buckets						)







		def 					UpperCAmelCase    (	self						:  Union[str, Any]			,_snake_case						:  str			,_snake_case						:  Tuple			,_snake_case						:  List[str]						)					->		bool:






				"""simple docstring"""



				lowercase__   :    Optional[int]				=			self._buckets[ind]
				if not stored:
						lowercase__   :    int				=			_Item(_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE						)
						self._len += 1
						return True
				elif stored.key == key:
						lowercase__   :    str				=			_Item(_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE						)
						return True
				else:
						return False







		def 					UpperCAmelCase    (	self						:  str						)					->		bool:






				"""simple docstring"""



				lowercase__   :    Any				=			len(self._buckets						) * self._capacity_factor
				return len(self						) >= int(_SCREAMING_SNAKE_CASE						)







		def 					UpperCAmelCase    (	self						:  int						)					->		bool:






				"""simple docstring"""



				if len(self._buckets						) <= self._initial_block_size:
						return False
				lowercase__   :    List[Any]				=			len(self._buckets						) * self._capacity_factor / 2
				return len(self						) < limit







		def 					UpperCAmelCase    (	self						:  Optional[Any]			,_snake_case						:  List[Any]						)					->		None:






				"""simple docstring"""



				lowercase__   :    List[str]				=			self._buckets
				lowercase__   :    Dict				=			[None] * new_size
				lowercase__   :    Optional[Any]				=			0
				for item in old_buckets:
						if item:
								self._add_item(item.key			,item.val						)







		def 					UpperCAmelCase    (	self						:  Union[str, Any]						)					->		None:






				"""simple docstring"""



				self._resize(len(self._buckets						) * 2						)







		def 					UpperCAmelCase    (	self						:  List[Any]						)					->		None:






				"""simple docstring"""



				self._resize(len(self._buckets						) // 2						)







		def 					UpperCAmelCase    (	self						:  int			,_snake_case						:  List[Any]						)					->		Iterator[int]:






				"""simple docstring"""



				lowercase__   :    Dict				=			self._get_bucket_index(_SCREAMING_SNAKE_CASE						)
				for _ in range(len(self._buckets						)						):
						yield ind
						lowercase__   :    List[str]				=			self._get_next_ind(_SCREAMING_SNAKE_CASE						)







		def 					UpperCAmelCase    (	self						:  List[str]			,_snake_case						:  Any			,_snake_case						:  int						)					->		None:






				"""simple docstring"""



				for ind in self._iterate_buckets(_SCREAMING_SNAKE_CASE						):
						if self._try_set(_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE						):
								break







		def __setitem__(	self						:  str			,_snake_case						:  int			,_snake_case						:  Dict						)					->		None:






				"""simple docstring"""



				if self._is_full():
						self._size_up()

				self._add_item(_SCREAMING_SNAKE_CASE			,_SCREAMING_SNAKE_CASE						)







		def __delitem__(	self						:  Dict			,_snake_case						:  Any						)					->		None:






				"""simple docstring"""



				for ind in self._iterate_buckets(_SCREAMING_SNAKE_CASE						):
						lowercase__   :    Optional[Any]				=			self._buckets[ind]
						if item is None:
								raise KeyError(_SCREAMING_SNAKE_CASE						)
						if item is _deleted:
								continue
						if item.key == key:
								lowercase__   :    Any				=			_deleted
								self._len -= 1
								break
				if self._is_sparse():
						self._size_down()







		def __getitem__(	self						:  Optional[int]			,_snake_case						:  Dict						)					->		VAL:






				"""simple docstring"""



				for ind in self._iterate_buckets(_SCREAMING_SNAKE_CASE						):
						lowercase__   :    Optional[Any]				=			self._buckets[ind]
						if item is None:
								break
						if item is _deleted:
								continue
						if item.key == key:
								return item.val
				raise KeyError(_SCREAMING_SNAKE_CASE						)







		def __len__(	self						:  Union[str, Any]						)					->		int:






				"""simple docstring"""



				return self._len







		def __iter__(	self						:  Optional[int]						)					->		Iterator[KEY]:






				"""simple docstring"""



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







		def __repr__(	self						:  List[Any]						)					->		str:






				"""simple docstring"""



				lowercase__   :    Optional[int]				=			''' ,'''.join(
				    f"""{item.key}: {item.val}""" for item in self._buckets if item						)
				return f"""HashMap({val_string})"""




def   _SCREAMING_SNAKE_CASE	( SCREAMING_SNAKE_CASE       ):
  if not nums:  # Makes sure that the list is not empty
    raise ValueError('''List is empty'''       )

  A_      :				Optional[int]		     =					sum(SCREAMING_SNAKE_CASE       ) / len(SCREAMING_SNAKE_CASE       )  # Calculate the average
  return sum(abs(x - average       ) for x in nums       ) / len(SCREAMING_SNAKE_CASE       )


if __name__ == "__main__":
     import doctest

     doctest.testmod()




