
"""simple docstring"""




from __future__ import annotations

from random import random
from typing import Generic, TypeVar

UpperCAmelCase__      :    Optional[int]    							= TypeVar('KT')
UpperCAmelCase__      :    Any    							= TypeVar('VT')



class 	lowerCAmelCase_						(Generic[KT, VT]  ):


				"""simple docstring"""



				def __init__(self   ,       SCREAMING_SNAKE_CASE__ = "root"   ,       SCREAMING_SNAKE_CASE__ = None    )					->		int:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__						:       int           =   key
											SCREAMING_SNAKE_CASE__						:       Dict           =   value
											SCREAMING_SNAKE_CASE__						:       list[Node[KT, VT]]           =   []



				def __repr__(self    )					->		str:



											"""simple docstring"""




											return F'''Node({self.key}: {self.value})'''



				@property
				def 	__magic_name__    (self    )					->		int:



											"""simple docstring"""




											return len(self.forward    )






class 	lowerCAmelCase_						(Generic[KT, VT]  ):


				"""simple docstring"""



				def __init__(self   ,       SCREAMING_SNAKE_CASE__ = 0.5   ,       SCREAMING_SNAKE_CASE__ = 16    )					->		Optional[int]:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__						:       Node[KT, VT]           =   Node[KT, VT]()
											SCREAMING_SNAKE_CASE__						:       Union[str, Any]           =   0
											SCREAMING_SNAKE_CASE__						:       Tuple           =   p
											SCREAMING_SNAKE_CASE__						:       List[Any]           =   max_level



				def __str__(self    )					->		str:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__						:       Dict           =   list(self    )

											if len(SCREAMING_SNAKE_CASE__    ) == 0:
																		return F'''SkipList(level={self.level})'''

											SCREAMING_SNAKE_CASE__						:       Dict           =   max((len(str(SCREAMING_SNAKE_CASE__    )    ) for item in items)   ,       default=4    )
											SCREAMING_SNAKE_CASE__						:       Union[str, Any]           =   max(SCREAMING_SNAKE_CASE__   ,       4    ) + 4

											SCREAMING_SNAKE_CASE__						:       Tuple           =   self.head
											SCREAMING_SNAKE_CASE__						:       List[Any]           =   []

											SCREAMING_SNAKE_CASE__						:       List[Any]           =   node.forward.copy()
											lines.append(F'''[{node.key}]'''.ljust(SCREAMING_SNAKE_CASE__   ,       """-"""    ) + """* """ * len(SCREAMING_SNAKE_CASE__    )    )
											lines.append(""" """ * label_size + """| """ * len(SCREAMING_SNAKE_CASE__    )    )

											while len(node.forward    ) != 0:
																		SCREAMING_SNAKE_CASE__						:       Union[str, Any]           =   node.forward[0]

																		lines.append(
																		    F'''[{node.key}]'''.ljust(SCREAMING_SNAKE_CASE__   ,       """-"""    )
																		    + """ """.join(str(n.key    ) if n.key == node.key else """|""" for n in forwards    )    )
																		lines.append(""" """ * label_size + """| """ * len(SCREAMING_SNAKE_CASE__    )    )
																		SCREAMING_SNAKE_CASE__						:       List[Any]           =   node.forward

											lines.append("""None""".ljust(SCREAMING_SNAKE_CASE__    ) + """* """ * len(SCREAMING_SNAKE_CASE__    )    )
											return F'''SkipList(level={self.level})\n''' + "\n".join(SCREAMING_SNAKE_CASE__    )



				def __iter__(self    )					->		Dict:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__						:       str           =   self.head

											while len(node.forward    ) != 0:
																		yield node.forward[0].key
																		SCREAMING_SNAKE_CASE__						:       Tuple           =   node.forward[0]



				def 	__magic_name__    (self    )					->		int:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__						:       int           =   1
											while random() < self.p and level < self.max_level:
																		level += 1

											return level



				def 	__magic_name__    (self   ,       SCREAMING_SNAKE_CASE__    )					->		tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__						:       List[Any]           =   []

											SCREAMING_SNAKE_CASE__						:       List[str]           =   self.head

											for i in reversed(range(self.level    )    ):
																		# i < node.level - When node level is lesser than `i` decrement `i`.
																		# node.forward[i].key < key - Jumping to node with key value higher
																		#                             or equal to searched key would result
																		#                             in skipping searched key.
																		while i < node.level and node.forward[i].key < key:
																									SCREAMING_SNAKE_CASE__						:       str           =   node.forward[i]
																		# Each leftmost node (relative to searched node) will potentially have to
																		# be updated.
																		update_vector.append(SCREAMING_SNAKE_CASE__    )

											update_vector.reverse()  # Note that we were inserting values in reverse order.

											# len(node.forward) != 0 - If current node doesn't contain any further
											#                          references then searched key is not present.
											# node.forward[0].key == key - Next node key should be equal to search key
											#                              if key is present.
											if len(node.forward    ) != 0 and node.forward[0].key == key:
																		return node.forward[0], update_vector
											else:
																		return None, update_vector



				def 	__magic_name__    (self   ,       SCREAMING_SNAKE_CASE__    )					->		Optional[int]:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__      ,      SCREAMING_SNAKE_CASE__						:       Dict           =   self._locate_node(SCREAMING_SNAKE_CASE__    )

											if node is not None:
																		for i, update_node in enumerate(SCREAMING_SNAKE_CASE__    ):
																									# Remove or replace all references to removed node.
																									if update_node.level > i and update_node.forward[i].key == key:
																																if node.level > i:
																																							SCREAMING_SNAKE_CASE__						:       Dict           =   node.forward[i]
																																else:
																																							SCREAMING_SNAKE_CASE__						:       Optional[Any]           =   update_node.forward[:i]



				def 	__magic_name__    (self   ,       SCREAMING_SNAKE_CASE__   ,       SCREAMING_SNAKE_CASE__    )					->		Tuple:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__      ,      SCREAMING_SNAKE_CASE__						:       Optional[Any]           =   self._locate_node(SCREAMING_SNAKE_CASE__    )
											if node is not None:
																		SCREAMING_SNAKE_CASE__						:       Union[str, Any]           =   value
											else:
																		SCREAMING_SNAKE_CASE__						:       str           =   self.random_level()

																		if level > self.level:
																									# After level increase we have to add additional nodes to head.
																									for _ in range(self.level - 1   ,       SCREAMING_SNAKE_CASE__    ):
																																update_vector.append(self.head    )
																									SCREAMING_SNAKE_CASE__						:       Optional[Any]           =   level

																		SCREAMING_SNAKE_CASE__						:       int           =   Node(SCREAMING_SNAKE_CASE__   ,       SCREAMING_SNAKE_CASE__    )

																		for i, update_node in enumerate(update_vector[:level]    ):
																									# Change references to pass through new node.
																									if update_node.level > i:
																																new_node.forward.append(update_node.forward[i]    )

																									if update_node.level < i + 1:
																																update_node.forward.append(SCREAMING_SNAKE_CASE__    )
																									else:
																																SCREAMING_SNAKE_CASE__						:       Dict           =   new_node



				def 	__magic_name__    (self   ,       SCREAMING_SNAKE_CASE__    )					->		VT | None:



											"""simple docstring"""




											SCREAMING_SNAKE_CASE__      ,      SCREAMING_SNAKE_CASE__						:       str           =   self._locate_node(SCREAMING_SNAKE_CASE__    )

											if node is not None:
																		return node.value

											return None






def lowercase_  (   ):
							SCREAMING_SNAKE_CASE__						:       List[Any]           =   SkipList()
							skip_list.insert("""Key1"""   ,3						)
							skip_list.insert("""Key2"""   ,12						)
							skip_list.insert("""Key3"""   ,41						)
							skip_list.insert("""Key4"""   ,-19						)

							SCREAMING_SNAKE_CASE__						:       Optional[int]           =   skip_list.head
							SCREAMING_SNAKE_CASE__						:       Tuple           =   {}
							while node.level != 0:
														SCREAMING_SNAKE_CASE__						:       List[Any]           =   node.forward[0]
														SCREAMING_SNAKE_CASE__						:       int           =   node.value

							assert len(_snake_case						) == 4
							assert all_values["Key1"] == 3
							assert all_values["Key2"] == 12
							assert all_values["Key3"] == 41
							assert all_values["Key4"] == -19

def lowercase_  (   ):
							SCREAMING_SNAKE_CASE__						:       str           =   SkipList()
							skip_list.insert("""Key1"""   ,10						)
							skip_list.insert("""Key1"""   ,12						)

							skip_list.insert("""Key5"""   ,7						)
							skip_list.insert("""Key7"""   ,10						)
							skip_list.insert("""Key10"""   ,5						)

							skip_list.insert("""Key7"""   ,7						)
							skip_list.insert("""Key5"""   ,5						)
							skip_list.insert("""Key10"""   ,10						)

							SCREAMING_SNAKE_CASE__						:       List[str]           =   skip_list.head
							SCREAMING_SNAKE_CASE__						:       Dict           =   {}
							while node.level != 0:
														SCREAMING_SNAKE_CASE__						:       List[str]           =   node.forward[0]
														SCREAMING_SNAKE_CASE__						:       Tuple           =   node.value

							if len(_snake_case						) != 4:
														print()
							assert len(_snake_case						) == 4
							assert all_values["Key1"] == 12
							assert all_values["Key7"] == 7
							assert all_values["Key5"] == 5
							assert all_values["Key10"] == 10

def lowercase_  (   ):
							SCREAMING_SNAKE_CASE__						:       Union[str, Any]           =   SkipList()
							assert skip_list.find("""Some key"""						) is None

def lowercase_  (   ):
							SCREAMING_SNAKE_CASE__						:       str           =   SkipList()

							skip_list.insert("""Key2"""   ,20						)
							assert skip_list.find("""Key2"""						) == 20

							skip_list.insert("""Some Key"""   ,10						)
							skip_list.insert("""Key2"""   ,8						)
							skip_list.insert("""V"""   ,13						)

							assert skip_list.find("""Y"""						) is None
							assert skip_list.find("""Key2"""						) == 8
							assert skip_list.find("""Some Key"""						) == 10
							assert skip_list.find("""V"""						) == 13

def lowercase_  (   ):
							SCREAMING_SNAKE_CASE__						:       Optional[int]           =   SkipList()
							skip_list.delete("""Some key"""						)

							assert len(skip_list.head.forward						) == 0

def lowercase_  (   ):
							SCREAMING_SNAKE_CASE__						:       Dict           =   SkipList()

							skip_list.insert("""Key1"""   ,12						)
							skip_list.insert("""V"""   ,13						)
							skip_list.insert("""X"""   ,14						)
							skip_list.insert("""Key2"""   ,15						)

							skip_list.delete("""V"""						)
							skip_list.delete("""Key2"""						)

							assert skip_list.find("""V"""						) is None
							assert skip_list.find("""Key2"""						) is None

def lowercase_  (   ):
							SCREAMING_SNAKE_CASE__						:       Any           =   SkipList()

							skip_list.insert("""Key1"""   ,12						)
							skip_list.insert("""V"""   ,13						)
							skip_list.insert("""X"""   ,14						)
							skip_list.insert("""Key2"""   ,15						)

							skip_list.delete("""V"""						)
							assert skip_list.find("""V"""						) is None
							assert skip_list.find("""X"""						) == 14
							assert skip_list.find("""Key1"""						) == 12
							assert skip_list.find("""Key2"""						) == 15

							skip_list.delete("""X"""						)
							assert skip_list.find("""V"""						) is None
							assert skip_list.find("""X"""						) is None
							assert skip_list.find("""Key1"""						) == 12
							assert skip_list.find("""Key2"""						) == 15

							skip_list.delete("""Key1"""						)
							assert skip_list.find("""V"""						) is None
							assert skip_list.find("""X"""						) is None
							assert skip_list.find("""Key1"""						) is None
							assert skip_list.find("""Key2"""						) == 15

							skip_list.delete("""Key2"""						)
							assert skip_list.find("""V"""						) is None
							assert skip_list.find("""X"""						) is None
							assert skip_list.find("""Key1"""						) is None
							assert skip_list.find("""Key2"""						) is None

def lowercase_  (   ):
							SCREAMING_SNAKE_CASE__						:       Union[str, Any]           =   SkipList()

							skip_list.insert("""Key1"""   ,12						)
							skip_list.insert("""V"""   ,13						)
							skip_list.insert("""X"""   ,142						)
							skip_list.insert("""Key2"""   ,15						)

							skip_list.delete("""X"""						)

							def traverse_keys(_snake_case						):
														yield node.key
														for forward_node in node.forward:
																					yield from traverse_keys(_snake_case						)

							assert len(set(traverse_keys(skip_list.head						)						)						) == 4

def lowercase_  (   ):
							def is_sorted(_snake_case						):
														return all(next_item >= item for item, next_item in zip(_snake_case   ,lst[1:]						)						)

							SCREAMING_SNAKE_CASE__						:       Union[str, Any]           =   SkipList()
							for i in range(10						):
														skip_list.insert(_snake_case   ,_snake_case						)
							assert is_sorted(list(_snake_case						)						)
							skip_list.delete(5						)
							skip_list.delete(8						)
							skip_list.delete(2						)
							assert is_sorted(list(_snake_case						)						)
							skip_list.insert(-12   ,-12						)
							skip_list.insert(77   ,77						)
							assert is_sorted(list(_snake_case						)						)

def lowercase_  (   ):
							for _ in range(100						):
														# Repeat test 100 times due to the probabilistic nature of skip list
														# random values == random bugs
														test_insert()
														test_insert_overrides_existing_value()

														test_searching_empty_list_returns_none()
														test_search()

														test_deleting_item_from_empty_list_do_nothing()
														test_deleted_items_are_not_founded_by_find_method()
														test_delete_removes_only_given_key()
														test_delete_doesnt_leave_dead_nodes()

														test_iter_always_yields_sorted_values()

def lowercase_  (   ):
							SCREAMING_SNAKE_CASE__						:       List[str]           =   SkipList()
							skip_list.insert(2   ,"""2"""						)
							skip_list.insert(4   ,"""4"""						)
							skip_list.insert(6   ,"""4"""						)
							skip_list.insert(4   ,"""5"""						)
							skip_list.insert(8   ,"""4"""						)
							skip_list.insert(9   ,"""4"""						)

							skip_list.delete(4						)

							print(_snake_case						)


if __name__ == "__main__":
					import doctest

					doctest.testmod()
					main()






"""simple docstring"""




def lowercase_  (   _snake_case						):
							if a < 0:
														raise ValueError("""Input value must be a positive integer"""						)
							elif isinstance(_snake_case   ,_snake_case						):
														raise TypeError("""Input value must be a 'int' type"""						)
							return bin(_snake_case						).count("""1"""						)


if __name__ == "__main__":
					import doctest

					doctest.testmod()




