


"""simple docstring"""





from __future__ import annotations

from random import random
from typing import Generic, TypeVar

snake_case__		:     Optional[int]    				=				TypeVar('''KT''')
snake_case__		:     str    				=				TypeVar('''VT''')



class 		snake_case_(       Generic[KT, VT]			):






     def __init__(	self  :					Tuple					,				UpperCamelCase_  :					KT | str = "root"					,				UpperCamelCase_  :					VT | None = None				):
           lowerCAmelCase					:	Optional[Any]       =   key
           lowerCAmelCase					:	Optional[Any]       =   value
           lowerCAmelCase					:	Dict       =   []






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






     @property
     def      lowerCamelCase__     (	self  :					str				):
           return len(self.forward				)



class 		snake_case_(       Generic[KT, VT]			):






     def __init__(	self  :					Tuple					,				UpperCamelCase_  :					float = 0.5					,				UpperCamelCase_  :					int = 1_6				):
           lowerCAmelCase					:	Tuple       =   Node[KT, VT]()
           lowerCAmelCase					:	Dict       =   0
           lowerCAmelCase					:	Tuple       =   p
           lowerCAmelCase					:	str       =   max_level






     def __str__(	self  :					int				):
           lowerCAmelCase					:	Tuple       =   list(self				)

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

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

           lowerCAmelCase					:	Any       =   self.head
           lowerCAmelCase					:	str       =   []

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

           while len(node.forward				) != 0:
                 lowerCAmelCase					:	Tuple       =   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__				)				)
                 lowerCAmelCase					:	Tuple       =   node.forward

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






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

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






     def      lowerCamelCase__     (	self  :					Tuple				):
           lowerCAmelCase					:	Union[str, Any]       =   1
           while random() < self.p and level < self.max_level:
                 level += 1

           return level






     def      lowerCamelCase__     (	self  :					Optional[Any]					,				UpperCamelCase_  :					Any				):
           lowerCAmelCase					:	List[Any]       =   []

           lowerCAmelCase					:	Optional[int]       =   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(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      lowerCamelCase__     (	self  :					List[Any]					,				UpperCamelCase_  :					KT				):
           lowerCAmelCase,      lowerCAmelCase					:	int       =   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:
                                   lowerCAmelCase					:	int       =   node.forward[i]
                             else:
                                   lowerCAmelCase					:	Optional[Any]       =   update_node.forward[:i]






     def      lowerCamelCase__     (	self  :					Union[str, Any]					,				UpperCamelCase_  :					KT					,				UpperCamelCase_  :					VT				):
           lowerCAmelCase,      lowerCAmelCase					:	Dict       =   self._locate_node(UpperCamelCase__				)
           if node is not None:
                 lowerCAmelCase					:	List[Any]       =   value
           else:
                 lowerCAmelCase					:	int       =   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				)
                       lowerCAmelCase					:	Dict       =   level

                 lowerCAmelCase					:	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:
                             lowerCAmelCase					:	List[Any]       =   new_node






     def      lowerCamelCase__     (	self  :					Optional[Any]					,				UpperCamelCase_  :					VT				):
           lowerCAmelCase,      lowerCAmelCase					:	int       =   self._locate_node(UpperCamelCase__				)

           if node is not None:
                 return node.value

           return None



def      _snake_case						(						)     ->   Tuple:
      lowerCAmelCase					:	List[str]       =   SkipList()
      skip_list.insert('''Key1''' ,   3			)
      skip_list.insert('''Key2''' ,   12			)
      skip_list.insert('''Key3''' ,   41			)
      skip_list.insert('''Key4''' ,   -19			)

      lowerCAmelCase					:	Dict       =   skip_list.head
      lowerCAmelCase					:	List[Any]       =   {}
      while node.level != 0:
            lowerCAmelCase					:	Tuple       =   node.forward[0]
            lowerCAmelCase					:	List[str]       =   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      _snake_case						(						)     ->   Union[str, Any]:
      lowerCAmelCase					:	Tuple       =   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			)

      lowerCAmelCase					:	Union[str, Any]       =   skip_list.head
      lowerCAmelCase					:	List[Any]       =   {}
      while node.level != 0:
            lowerCAmelCase					:	Any       =   node.forward[0]
            lowerCAmelCase					:	Any       =   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      _snake_case						(						)     ->   List[Any]:
      lowerCAmelCase					:	Any       =   SkipList()
      assert skip_list.find('''Some key'''			) is None


def      _snake_case						(						)     ->   Optional[int]:
      lowerCAmelCase					:	Dict       =   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      _snake_case						(						)     ->   str:
      lowerCAmelCase					:	Dict       =   SkipList()
      skip_list.delete('''Some key'''			)

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


def      _snake_case						(						)     ->   List[Any]:
      lowerCAmelCase					:	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      _snake_case						(						)     ->   List[str]:
      lowerCAmelCase					:	List[str]       =   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      _snake_case						(						)     ->   Optional[Any]:
      lowerCAmelCase					:	int       =   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				:			Union[str, Any]			):
            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      _snake_case						(						)     ->   Tuple:
      def is_sorted(_snake_case				:			Tuple			):
            return all(next_item >= item for item, next_item in zip(_snake_case ,   lst[1:]			)			)

      lowerCAmelCase					:	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      _snake_case						(						)     ->   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      _snake_case						(						)     ->   List[Any]:
      lowerCAmelCase					:	int       =   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"""





snake_case__		:     List[Any]    				=				'''Tobias Carryer'''

from time import time



class 		snake_case_:






     def __init__(	self  :					Optional[Any]					,				UpperCamelCase_  :					Optional[Any]					,				UpperCamelCase_  :					Tuple					,				UpperCamelCase_  :					Optional[int]					,				UpperCamelCase_  :					Dict=int(time()				)				):  # noqa: B008
           lowerCAmelCase					:	str       =   multiplier
           lowerCAmelCase					:	Optional[int]       =   increment
           lowerCAmelCase					:	Optional[Any]       =   modulo
           lowerCAmelCase					:	Optional[Any]       =   seed






     def      lowerCamelCase__     (	self  :					Union[str, Any]				):
           lowerCAmelCase					:	Optional[int]       =   (self.multiplier * self.seed + self.increment) % self.modulo
           return self.seed


if __name__ == "__main__":
 # Show the LCG in action.
 snake_case__		:     int    				=				LinearCongruentialGenerator(1_664_525, 1_013_904_223, 2 << 31)
 while True:
  print(lcg.next_number())


