





from __future__ import annotations

from random import random
from typing import Generic, TypeVar

UpperCAmelCase_     							= TypeVar('KT')
UpperCAmelCase_     							= TypeVar('VT')






class     lowercase__       (	Generic[KT, VT]				):

   '''simple docstring'''


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






       """simple docstring"""
       UpperCamelCase__							:				Optional[Any]          =      key
       UpperCamelCase__							:				Any          =      value
       UpperCamelCase__							:				list[Node[KT, VT]]          =      []




   def __repr__(    self							) ->      str:






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




   @property
   def       UpperCamelCase__  (    self							) ->      int:






       """simple docstring"""
       return len(self.forward							)






class     lowercase__       (	Generic[KT, VT]				):

   '''simple docstring'''


   def __init__(    self,		__magic_name__ = 0.5,		__magic_name__ = 16							) ->      Union[str, Any]:






       """simple docstring"""
       UpperCamelCase__							:				Node[KT, VT]          =      Node[KT, VT]()
       UpperCamelCase__							:				Optional[Any]          =      0
       UpperCamelCase__							:				List[Any]          =      p
       UpperCamelCase__							:				Union[str, Any]          =      max_level




   def __str__(    self							) ->      str:






       """simple docstring"""
       UpperCamelCase__							:				Union[str, Any]          =      list(self							)

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

       UpperCamelCase__							:				Dict          =      max((len(str(__magic_name__							)							) for item in items),		default=4							)
       UpperCamelCase__							:				List[str]          =      max(__magic_name__,		4							) + 4

       UpperCamelCase__							:				List[str]          =      self.head
       UpperCamelCase__							:				int          =      []

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

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

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

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




   def __iter__(    self							) ->      Tuple:






       """simple docstring"""
       UpperCamelCase__							:				Optional[int]          =      self.head

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




   def       UpperCamelCase__  (    self							) ->      int:






       """simple docstring"""
       UpperCamelCase__							:				str          =      1
       while random() < self.p and level < self.max_level:
           level += 1

       return level




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






       """simple docstring"""
       UpperCamelCase__							:				List[str]          =      []

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

       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,		__magic_name__							) ->      Optional[Any]:






       """simple docstring"""
       UpperCamelCase__   ,UpperCamelCase__							:				List[str]          =      self._locate_node(__magic_name__							)

       if node is not None:
           for i, update_node in enumerate(__magic_name__							):
               # 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__							:				Tuple          =      node.forward[i]
                   else:
                       UpperCamelCase__							:				Optional[int]          =      update_node.forward[:i]




   def       UpperCamelCase__  (    self,		__magic_name__,		__magic_name__							) ->      Any:






       """simple docstring"""
       UpperCamelCase__   ,UpperCamelCase__							:				List[str]          =      self._locate_node(__magic_name__							)
       if node is not None:
           UpperCamelCase__							:				Tuple          =      value
       else:
           UpperCamelCase__							:				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,		__magic_name__							):
                   update_vector.append(self.head							)
               UpperCamelCase__							:				Dict          =      level

           UpperCamelCase__							:				int          =      Node(__magic_name__,		__magic_name__							)

           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(__magic_name__							)
               else:
                   UpperCamelCase__							:				List[str]          =      new_node




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






       """simple docstring"""
       UpperCamelCase__   ,UpperCamelCase__							:				List[str]          =      self._locate_node(__magic_name__							)

       if node is not None:
           return node.value

       return None




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

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

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




def 		lowerCAmelCase_    (  )      ->	Any:
    UpperCamelCase__							:				Dict          =      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__							:				List[str]          =      skip_list.head
    UpperCamelCase__							:				int          =      {}
    while node.level != 0:
        UpperCamelCase__							:				Optional[Any]          =      node.forward[0]
        UpperCamelCase__							:				Tuple          =      node.value

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




def 		lowerCAmelCase_    (  )      ->	Union[str, Any]:
    UpperCamelCase__							:				Union[str, Any]          =      SkipList()
    assert skip_list.find('''Some key'''      ) is None




def 		lowerCAmelCase_    (  )      ->	Any:
    UpperCamelCase__							:				int          =      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 		lowerCAmelCase_    (  )      ->	str:
    UpperCamelCase__							:				Dict          =      SkipList()
    skip_list.delete('''Some key'''      )

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




def 		lowerCAmelCase_    (  )      ->	List[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'''      )
    skip_list.delete('''Key2'''      )

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




def 		lowerCAmelCase_    (  )      ->	Tuple:
    UpperCamelCase__							:				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 		lowerCAmelCase_    (  )      ->	List[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(__UpperCAmelCase:			Tuple      ):
        yield node.key
        for forward_node in node.forward:
            yield from traverse_keys(__UpperCAmelCase      )

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




def 		lowerCAmelCase_    (  )      ->	Tuple:
    def is_sorted(__UpperCAmelCase:			Union[str, Any]      ):
        return all(next_item >= item for item, next_item in zip(__UpperCAmelCase		,   lst[1:]      )      )

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




def 		lowerCAmelCase_    (  )      ->	Optional[Any]:
    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 		lowerCAmelCase_    (  )      ->	Union[str, Any]:
    UpperCamelCase__							:				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(__UpperCAmelCase      )


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  main()








from math import factorial




def 		lowerCAmelCase_    (  __UpperCAmelCase:			int		,   __UpperCAmelCase:			int      )      ->	int:

    # If either of the conditions are true, the function is being asked
    # to calculate a factorial of a negative number, which is not possible
    if n < k or k < 0:
        raise ValueError('''Please enter positive integers for n and k where n >= k'''      )
    return factorial(__UpperCAmelCase      ) // (factorial(__UpperCAmelCase      ) * factorial(n - k      ))


if __name__ == "__main__":
  print(
      'The number of five-card hands possible from a standard',
      F'''fifty-two card deck is: {combinations(52, 5)}\n''',
  )

  print(
      'If a class of 40 students must be arranged into groups of',
      F'''4 for group projects, there are {combinations(40, 4)} ways''',
      'to arrange them.\n',
  )

  print(
      'If 10 teams are competing in a Formula One race, there',
      F'''are {combinations(10, 3)} ways that first, second and''',
      'third place can be awarded.',
  )

