


"""simple docstring"""







from __future__ import annotations

from random import random
from typing import Generic, TypeVar

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


class       SCREAMING_SNAKE_CASE__				(		Generic[KT, VT]				):
       """simple docstring"""


       def __init__(						self		,     snake_case__ = "root"		,     snake_case__ = None						):






         """simple docstring"""





         lowerCAmelCase     :     List[Any]								=							key
         lowerCAmelCase     :     List[Any]								=							value
         lowerCAmelCase     :     list[Node[KT, VT]]								=							[]

       def __repr__(						self						):






         """simple docstring"""





         return f"""Node({self.key}: {self.value})"""







       @property
       def        lowercase__							(						self						):






         """simple docstring"""





         return len(self.forward						)


class       SCREAMING_SNAKE_CASE__				(		Generic[KT, VT]				):
       """simple docstring"""


       def __init__(						self		,     snake_case__ = 0.5		,     snake_case__ = 16						):






         """simple docstring"""





         lowerCAmelCase     :     Node[KT, VT]								=							Node[KT, VT]()
         lowerCAmelCase     :     List[str]								=							0
         lowerCAmelCase     :     Optional[int]								=							p
         lowerCAmelCase     :     Dict								=							max_level

       def __str__(						self						):






         """simple docstring"""





         lowerCAmelCase     :     Tuple								=							list(self						)

         if len(snake_case__						) == 0:
           return f"""SkipList(level={self.level})"""

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

         lowerCAmelCase     :     List[str]								=							self.head
         lowerCAmelCase     :     Dict								=							[]

         lowerCAmelCase     :     Union[str, Any]								=							node.forward.copy()
         lines.append(f"""[{node.key}]""".ljust(snake_case__		,     "-"						) + "* " * len(snake_case__						)						)
         lines.append(" " * label_size + "| " * len(snake_case__						)						)

         while len(node.forward						) != 0:
           lowerCAmelCase     :     Optional[int]								=							node.forward[0]

           lines.append(
               f"""[{node.key}]""".ljust(snake_case__		,     "-"						)
               + " ".join(str(n.key						) if n.key == node.key else "|" for n in forwards						)						)
           lines.append(" " * label_size + "| " * len(snake_case__						)						)
           lowerCAmelCase     :     Tuple								=							node.forward

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

       def __iter__(						self						):






         """simple docstring"""





         lowerCAmelCase     :     Tuple								=							self.head

         while len(node.forward						) != 0:
           yield node.forward[0].key
           lowerCAmelCase     :     List[Any]								=							node.forward[0]

       def        lowercase__							(						self						):






         """simple docstring"""





         lowerCAmelCase     :     Dict								=							1
         while random() < self.p and level < self.max_level:
           level += 1

         return level

       def        lowercase__							(						self		,     snake_case__						):






         """simple docstring"""





         lowerCAmelCase     :     str								=							[]

         lowerCAmelCase     :     List[Any]								=							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:
             lowerCAmelCase     :     List[str]								=							node.forward[i]
           # Each leftmost node (relative to searched node) will potentially have to
           # be updated.
           update_vector.append(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        lowercase__							(						self		,     snake_case__						):






         """simple docstring"""





         lowerCAmelCase						,  lowerCAmelCase     :     Dict								=							self._locate_node(snake_case__						)

         if node is not None:
           for i, update_node in enumerate(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:
                 lowerCAmelCase     :     int								=							node.forward[i]
               else:
                 lowerCAmelCase     :     Union[str, Any]								=							update_node.forward[:i]

       def        lowercase__							(						self		,     snake_case__		,     snake_case__						):






         """simple docstring"""





         lowerCAmelCase						,  lowerCAmelCase     :     List[Any]								=							self._locate_node(snake_case__						)
         if node is not None:
           lowerCAmelCase     :     Tuple								=							value
         else:
           lowerCAmelCase     :     List[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		,     snake_case__						):
               update_vector.append(self.head						)
             lowerCAmelCase     :     List[str]								=							level

           lowerCAmelCase     :     int								=							Node(snake_case__		,     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(snake_case__						)
             else:
               lowerCAmelCase     :     Any								=							new_node







       def        lowercase__							(						self		,     snake_case__						):






         """simple docstring"""





         lowerCAmelCase						,  lowerCAmelCase     :     List[Any]								=							self._locate_node(snake_case__						)

         if node is not None:
           return node.value

         return None

def 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     Union[str, Any]								=							SkipList()
  skip_list.insert("Key1"				,      3				)
  skip_list.insert("Key2"				,      1_2				)
  skip_list.insert("Key3"				,      4_1				)
  skip_list.insert("Key4"				,      -1_9				)

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

  assert len(SCREAMING_SNAKE_CASE				) == 4
  assert all_values["Key1"] == 3
  assert all_values["Key2"] == 1_2
  assert all_values["Key3"] == 4_1
  assert all_values["Key4"] == -1_9
def 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     int								=							SkipList()
  skip_list.insert("Key1"				,      1_0				)
  skip_list.insert("Key1"				,      1_2				)

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

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

  lowerCAmelCase     :     Dict								=							skip_list.head
  lowerCAmelCase     :     Optional[Any]								=							{}
  while node.level != 0:
    lowerCAmelCase     :     Tuple								=							node.forward[0]
    lowerCAmelCase     :     str								=							node.value

  if len(SCREAMING_SNAKE_CASE				) != 4:
    print()
  assert len(SCREAMING_SNAKE_CASE				) == 4
  assert all_values["Key1"] == 1_2
  assert all_values["Key7"] == 7
  assert all_values["Key5"] == 5
  assert all_values["Key10"] == 1_0
def 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     List[Any]								=							SkipList()
  assert skip_list.find("Some key"				) is None
def 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     List[str]								=							SkipList()

  skip_list.insert("Key2"				,      2_0				)
  assert skip_list.find("Key2"				) == 2_0

  skip_list.insert("Some Key"				,      1_0				)
  skip_list.insert("Key2"				,      8				)
  skip_list.insert("V"				,      1_3				)

  assert skip_list.find("Y"				) is None
  assert skip_list.find("Key2"				) == 8
  assert skip_list.find("Some Key"				) == 1_0
  assert skip_list.find("V"				) == 1_3
def 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     Dict								=							SkipList()
  skip_list.delete("Some key"				)

  assert len(skip_list.head.forward				) == 0
def 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     Optional[int]								=							SkipList()

  skip_list.insert("Key1"				,      1_2				)
  skip_list.insert("V"				,      1_3				)
  skip_list.insert("X"				,      1_4				)
  skip_list.insert("Key2"				,      1_5				)

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

  assert skip_list.find("V"				) is None
  assert skip_list.find("Key2"				) is None
def 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     Union[str, Any]								=							SkipList()

  skip_list.insert("Key1"				,      1_2				)
  skip_list.insert("V"				,      1_3				)
  skip_list.insert("X"				,      1_4				)
  skip_list.insert("Key2"				,      1_5				)

  skip_list.delete("V"				)
  assert skip_list.find("V"				) is None
  assert skip_list.find("X"				) == 1_4
  assert skip_list.find("Key1"				) == 1_2
  assert skip_list.find("Key2"				) == 1_5

  skip_list.delete("X"				)
  assert skip_list.find("V"				) is None
  assert skip_list.find("X"				) is None
  assert skip_list.find("Key1"				) == 1_2
  assert skip_list.find("Key2"				) == 1_5

  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"				) == 1_5

  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 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     str								=							SkipList()

  skip_list.insert("Key1"				,      1_2				)
  skip_list.insert("V"				,      1_3				)
  skip_list.insert("X"				,      1_4_2				)
  skip_list.insert("Key2"				,      1_5				)

  skip_list.delete("X"				)

  def traverse_keys(SCREAMING_SNAKE_CASE    :    Optional[int]				):
    yield node.key
    for forward_node in node.forward:
      yield from traverse_keys(SCREAMING_SNAKE_CASE				)

  assert len(set(traverse_keys(skip_list.head				)				)				) == 4
def 					a__			(				):


  '''simple docstring'''







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

  lowerCAmelCase     :     Optional[int]								=							SkipList()
  for i in range(1_0				):
    skip_list.insert(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)
  assert is_sorted(list(SCREAMING_SNAKE_CASE				)				)
  skip_list.delete(5				)
  skip_list.delete(8				)
  skip_list.delete(2				)
  assert is_sorted(list(SCREAMING_SNAKE_CASE				)				)
  skip_list.insert(-1_2				,      -1_2				)
  skip_list.insert(7_7				,      7_7				)
  assert is_sorted(list(SCREAMING_SNAKE_CASE				)				)
def 					a__			(				):


  '''simple docstring'''







  for _ in range(1_0_0				):
    # 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 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     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(SCREAMING_SNAKE_CASE				)


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     main()









"""simple docstring"""







def 					a__			(				SCREAMING_SNAKE_CASE    :    int				,      SCREAMING_SNAKE_CASE    :    List[Any]				,      SCREAMING_SNAKE_CASE    :    str				,      SCREAMING_SNAKE_CASE    :    List[Any]				):


  '''simple docstring'''







  if height >= 1:
    move_tower(height - 1				,      SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)
    move_disk(SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)
    move_tower(height - 1				,      SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				,      SCREAMING_SNAKE_CASE				)
def 					a__			(				SCREAMING_SNAKE_CASE    :    Tuple				,      SCREAMING_SNAKE_CASE    :    Optional[int]				):


  '''simple docstring'''







  print("moving disk from"				,      SCREAMING_SNAKE_CASE				,      "to"				,      SCREAMING_SNAKE_CASE				)
def 					a__			(				):


  '''simple docstring'''







  lowerCAmelCase     :     Optional[int]								=							int(input("Height of hanoi: "				).strip()				)
  move_tower(SCREAMING_SNAKE_CASE				,      "A"				,      "B"				,      "C"				)


if __name__ == "__main__":
     main()





