






'''simple docstring'''




from __future__ import annotations

from random import random
from typing import Generic, TypeVar

lowerCAmelCase__          =						TypeVar('KT')
lowerCAmelCase__          =						TypeVar('VT')

class       __lowercase					(Generic[KT, VT]    ):

	def __init__(      self   :						List[str]  ,					UpperCAmelCase_   :						KT | str = "root"  ,					UpperCAmelCase_   :						VT | None = None):
			UpperCamelCase__				:					Any					=					key
			UpperCamelCase__				:					Optional[int]					=					value
			UpperCamelCase__				:					list[Node[KT, VT]]					=					[]

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





	@property
	def      __UpperCamelCase							(      self   :						Dict):
			return len(self.forward)


class       __lowercase					(Generic[KT, VT]    ):

	def __init__(      self   :						int  ,					UpperCAmelCase_   :						float = 0.5  ,					UpperCAmelCase_   :						int = 16):
			UpperCamelCase__				:					Node[KT, VT]					=					Node[KT, VT]()
			UpperCamelCase__				:					Any					=					0
			UpperCamelCase__				:					List[str]					=					p
			UpperCamelCase__				:					List[str]					=					max_level

	def __str__(      self   :						List[str]):
			UpperCamelCase__				:					int					=					list(self)

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

			UpperCamelCase__				:					Optional[Any]					=					max((len(str(UpperCAmelCase_)) for item in items)  ,					default=4)
			UpperCamelCase__				:					int					=					max(UpperCAmelCase_  ,					4) + 4

			UpperCamelCase__				:					Any					=					self.head
			UpperCamelCase__				:					Union[str, Any]					=					[]

			UpperCamelCase__				:					Dict					=					node.forward.copy()
			lines.append(F'[{node.key}]'.ljust(UpperCAmelCase_  ,					'-') + '* ' * len(UpperCAmelCase_))
			lines.append(' ' * label_size + '| ' * len(UpperCAmelCase_))

			while len(node.forward) != 0:
					UpperCamelCase__				:					str					=					node.forward[0]

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

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

	def __iter__(      self   :						Dict):
			UpperCamelCase__				:					Optional[Any]					=					self.head

			while len(node.forward) != 0:
					yield node.forward[0].key
					UpperCamelCase__				:					str					=					node.forward[0]

	def      __UpperCamelCase							(      self   :						Any):
			UpperCamelCase__				:					List[str]					=					1
			while random() < self.p and level < self.max_level:
					level += 1

			return level

	def      __UpperCamelCase							(      self   :						Tuple  ,					UpperCAmelCase_   :						str):
			UpperCamelCase__				:					Dict					=					[]

			UpperCamelCase__				:					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:
							UpperCamelCase__				:					Dict					=					node.forward[i]
					# Each leftmost node (relative to searched node) will potentially have to
					# be updated.
					update_vector.append(UpperCAmelCase_)

			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      __UpperCamelCase							(      self   :						str  ,					UpperCAmelCase_   :						KT):
			UpperCamelCase__				:					Optional[Any]					=					self._locate_node(UpperCAmelCase_)

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

	def      __UpperCamelCase							(      self   :						Union[str, Any]  ,					UpperCAmelCase_   :						KT  ,					UpperCAmelCase_   :						VT):
			UpperCamelCase__				:					Optional[Any]					=					self._locate_node(UpperCAmelCase_)
			if node is not None:
					UpperCamelCase__				:					Optional[int]					=					value
			else:
					UpperCamelCase__				:					Tuple					=					self.random_level()

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

					UpperCamelCase__				:					List[str]					=					Node(UpperCAmelCase_  ,					UpperCAmelCase_)

					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(UpperCAmelCase_)
							else:
									UpperCamelCase__				:					Tuple					=					new_node





	def      __UpperCamelCase							(      self   :						Union[str, Any]  ,					UpperCAmelCase_   :						VT):
			UpperCamelCase__				:					Optional[Any]					=					self._locate_node(UpperCAmelCase_)

			if node is not None:
					return node.value

			return None







def       __UpperCAmelCase						(  )							->     int:
		UpperCamelCase__				:					Optional[Any]					=					SkipList()
		skip_list.insert('Key1'     ,      3)
		skip_list.insert('Key2'     ,      12)
		skip_list.insert('Key3'     ,      41)
		skip_list.insert('Key4'     ,      -19)

		UpperCamelCase__				:					str					=					skip_list.head
		UpperCamelCase__				:					Dict					=					{}
		while node.level != 0:
				UpperCamelCase__				:					Union[str, Any]					=					node.forward[0]
				UpperCamelCase__				:					List[str]					=					node.value

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







def       __UpperCAmelCase						(  )							->     List[Any]:
		UpperCamelCase__				:					Optional[Any]					=					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)

		UpperCamelCase__				:					Union[str, Any]					=					skip_list.head
		UpperCamelCase__				:					Dict					=					{}
		while node.level != 0:
				UpperCamelCase__				:					List[str]					=					node.forward[0]
				UpperCamelCase__				:					List[str]					=					node.value

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







def       __UpperCAmelCase						(  )							->     Optional[int]:
		UpperCamelCase__				:					Optional[Any]					=					SkipList()
		assert skip_list.find('Some key') is None







def       __UpperCAmelCase						(  )							->     List[str]:
		UpperCamelCase__				:					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       __UpperCAmelCase						(  )							->     Optional[Any]:
		UpperCamelCase__				:					List[str]					=					SkipList()
		skip_list.delete('Some key')

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







def       __UpperCAmelCase						(  )							->     Optional[int]:
		UpperCamelCase__				:					Tuple					=					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       __UpperCAmelCase						(  )							->     str:
		UpperCamelCase__				:					Optional[int]					=					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       __UpperCAmelCase						(  )							->     Any:
		UpperCamelCase__				:					Optional[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(lowerCamelCase_):
				yield node.key
				for forward_node in node.forward:
						yield from traverse_keys(lowerCamelCase_)

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







def       __UpperCAmelCase						(  )							->     List[str]:
		def is_sorted(lowerCamelCase_):
				return all(next_item >= item for item, next_item in zip(lowerCamelCase_     ,      lst[1:]))

		UpperCamelCase__				:					Any					=					SkipList()
		for i in range(10):
				skip_list.insert(lowerCamelCase_     ,      lowerCamelCase_)
		assert is_sorted(list(lowerCamelCase_))
		skip_list.delete(5)
		skip_list.delete(8)
		skip_list.delete(2)
		assert is_sorted(list(lowerCamelCase_))
		skip_list.insert(-12     ,      -12)
		skip_list.insert(77     ,      77)
		assert is_sorted(list(lowerCamelCase_))







def       __UpperCAmelCase						(  )							->     Optional[int]:
		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       __UpperCAmelCase						(  )							->     Any:
		UpperCamelCase__				:					List[Any]					=					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(lowerCamelCase_)


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		main()












'''simple docstring'''




def       __UpperCAmelCase						(  lowerCamelCase_     ,      lowerCamelCase_)							->     list[str]:
		return [sentence[i : i + ngram_size] for i in range(len(lowerCamelCase_) - ngram_size + 1)]


if __name__ == "__main__":
		from doctest import testmod

		testmod()




