



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

SCREAMING_SNAKE_CASE__       =      TypeVar('''KEY''')
SCREAMING_SNAKE_CASE__       =      TypeVar('''VAL''')


@dataclass(frozen=UpperCAmelCase_							,     slots=UpperCAmelCase_      )
class      __lowerCAmelCase     (		Generic[KEY, VAL]      ):
					"""simple docstring"""






					A__				:		KEY
					A__				:		VAL







class      __lowerCAmelCase     (		_Item      ):
					"""simple docstring"""






					def __init__(     self					:       int					):






								"""simple docstring"""


								super().__init__(_snake_case				,					_snake_case					)



					def __bool__(     self					:       List[str]					):






								"""simple docstring"""


								return False







SCREAMING_SNAKE_CASE__       =      _DeletedItem()


class      __lowerCAmelCase     (		MutableMapping[KEY, VAL]      ):
					"""simple docstring"""






					def __init__(     self					:       List[Any]				,					_snake_case					:       int = 8				,					_snake_case					:       float = 0.75					):






								"""simple docstring"""


								A__       =    initial_block_size
								A__       =    [None] * initial_block_size
								assert 0.0 < capacity_factor < 1.0
								A__       =    capacity_factor
								A__       =    0



					def     _a							(     self					:       Dict				,					_snake_case					:       KEY					):






								"""simple docstring"""


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



					def     _a							(     self					:       Optional[Any]				,					_snake_case					:       int					):






								"""simple docstring"""


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



					def     _a							(     self					:       Any				,					_snake_case					:       int				,					_snake_case					:       KEY				,					_snake_case					:       VAL					):






								"""simple docstring"""


								A__       =    self._buckets[ind]
								if not stored:
											A__       =    _Item(_snake_case				,					_snake_case					)
											self._len += 1
											return True
								elif stored.key == key:
											A__       =    _Item(_snake_case				,					_snake_case					)
											return True
								else:
											return False



					def     _a							(     self					:       List[Any]					):






								"""simple docstring"""


								A__       =    len(self._buckets					) * self._capacity_factor
								return len(self					) >= int(_snake_case					)



					def     _a							(     self					:       Optional[int]					):






								"""simple docstring"""


								if len(self._buckets					) <= self._initial_block_size:
											return False
								A__       =    len(self._buckets					) * self._capacity_factor / 2
								return len(self					) < limit



					def     _a							(     self					:       List[Any]				,					_snake_case					:       int					):






								"""simple docstring"""


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



					def     _a							(     self					:       Optional[Any]					):






								"""simple docstring"""


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



					def     _a							(     self					:       Dict					):






								"""simple docstring"""


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



					def     _a							(     self					:       str				,					_snake_case					:       KEY					):






								"""simple docstring"""


								A__       =    self._get_bucket_index(_snake_case					)
								for _ in range(len(self._buckets					)					):
											yield ind
											A__       =    self._get_next_ind(_snake_case					)



					def     _a							(     self					:       Any				,					_snake_case					:       KEY				,					_snake_case					:       VAL					):






								"""simple docstring"""


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



					def __setitem__(     self					:       Union[str, Any]				,					_snake_case					:       KEY				,					_snake_case					:       VAL					):






								"""simple docstring"""


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

								self._add_item(_snake_case				,					_snake_case					)



					def __delitem__(     self					:       List[str]				,					_snake_case					:       KEY					):






								"""simple docstring"""


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



					def __getitem__(     self					:       List[Any]				,					_snake_case					:       KEY					):






								"""simple docstring"""


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



					def __len__(     self					:       Any					):






								"""simple docstring"""


								return self._len



					def __iter__(     self					:       List[str]					):






								"""simple docstring"""


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



					def __repr__(     self					:       Optional[int]					):






								"""simple docstring"""


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









def A						(       __UpperCamelCase					)						->      bool:
			return number & 1 == 0


if __name__ == "__main__":
							import doctest

							doctest.testmod()




