


'''simple docstring'''






from __future__ import annotations

from random import random
from typing import Generic, TypeVar

__A   :    Any											= TypeVar("KT")
__A   :    List[str]											= TypeVar("VT")






class   __snake_case			(  Generic[KT, VT]):







    """simple docstring"""



    def __init__(  self       :    List[Any]       ,		lowerCamelCase       :    KT | str = "root"       ,		lowerCamelCase       :    VT | None = None						)  ->    Dict:
      lowerCAmelCase_     : str     =  key
      lowerCAmelCase_     : Any     =  value
      lowerCAmelCase_     : list[Node[KT, VT]]     =  []

    def __repr__(  self       :    List[Any]						)  ->    str:
      return F'Node({self.key}: {self.value})'





    @property
    def __lowercase  (  self       :    Any						)  ->    int:
      return len(self.forward						)







class   __snake_case			(  Generic[KT, VT]):







    """simple docstring"""



    def __init__(  self       :    str       ,		lowerCamelCase       :    float = 0.5       ,		lowerCamelCase       :    int = 16						)  ->    Dict:
      lowerCAmelCase_     : Node[KT, VT]     =  Node[KT, VT]()
      lowerCAmelCase_     : Optional[int]     =  0
      lowerCAmelCase_     : Optional[Any]     =  p
      lowerCAmelCase_     : Optional[Any]     =  max_level

    def __str__(  self       :    Optional[int]						)  ->    str:
      lowerCAmelCase_     : List[Any]     =  list(self						)

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

      lowerCAmelCase_     : int     =  max((len(str(lowerCamelCase						)						) for item in items)       ,		default=4						)
      lowerCAmelCase_     : Any     =  max(lowerCamelCase       ,		4						) + 4

      lowerCAmelCase_     : Optional[int]     =  self.head
      lowerCAmelCase_     : List[Any]     =  []

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

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

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

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

    def __iter__(  self       :    List[Any]						)  ->    Tuple:
      lowerCAmelCase_     : Dict     =  self.head

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

    def __lowercase  (  self       :    Tuple						)  ->    int:
      lowerCAmelCase_     : Tuple     =  1
      while random() < self.p and level < self.max_level:
        level += 1

      return level

    def __lowercase  (  self       :    int       ,		lowerCamelCase       :    Dict						)  ->    tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:
      lowerCAmelCase_     : Tuple     =  []

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

      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       :    int       ,		lowerCamelCase       :    KT						)  ->    Union[str, Any]:
      lowerCAmelCase_,				lowerCAmelCase_     : Tuple     =  self._locate_node(lowerCamelCase						)

      if node is not None:
        for i, update_node in enumerate(lowerCamelCase						):
          # 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_     : str     =  node.forward[i]
            else:
              lowerCAmelCase_     : str     =  update_node.forward[:i]

    def __lowercase  (  self       :    Optional[int]       ,		lowerCamelCase       :    KT       ,		lowerCamelCase       :    VT						)  ->    Dict:
      lowerCAmelCase_,				lowerCAmelCase_     : Tuple     =  self._locate_node(lowerCamelCase						)
      if node is not None:
        lowerCAmelCase_     : Tuple     =  value
      else:
        lowerCAmelCase_     : Optional[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       ,		lowerCamelCase						):
            update_vector.append(self.head						)
          lowerCAmelCase_     : Optional[int]     =  level

        lowerCAmelCase_     : List[str]     =  Node(lowerCamelCase       ,		lowerCamelCase						)

        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(lowerCamelCase						)
          else:
            lowerCAmelCase_     : Optional[int]     =  new_node





    def __lowercase  (  self       :    List[Any]       ,		lowerCamelCase       :    VT						)  ->    VT | None:
      lowerCAmelCase_,				lowerCAmelCase_     : List[Any]     =  self._locate_node(lowerCamelCase						)

      if node is not None:
        return node.value

      return None







def 							UpperCamelCase_     (       ):
  '''simple docstring'''





  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_     : Tuple     =  skip_list.head
  lowerCAmelCase_     : Any     =  {}
  while node.level != 0:
    lowerCAmelCase_     : Optional[Any]     =  node.forward[0]
    lowerCAmelCase_     : Tuple     =  node.value

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







def 							UpperCamelCase_     (       ):
  '''simple docstring'''





  lowerCAmelCase_     : List[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   )

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

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







def 							UpperCamelCase_     (       ):
  '''simple docstring'''





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







def 							UpperCamelCase_     (       ):
  '''simple docstring'''





  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 							UpperCamelCase_     (       ):
  '''simple docstring'''





  lowerCAmelCase_     : Optional[Any]     =  SkipList()
  skip_list.delete("""Some key"""   )

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







def 							UpperCamelCase_     (       ):
  '''simple docstring'''





  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 							UpperCamelCase_     (       ):
  '''simple docstring'''





  lowerCAmelCase_     : 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 							UpperCamelCase_     (       ):
  '''simple docstring'''





  lowerCAmelCase_     : Optional[Any]     =  SkipList()

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

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

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

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







def 							UpperCamelCase_     (       ):
  '''simple docstring'''





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

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







def 							UpperCamelCase_     (       ):
  '''simple docstring'''





  for _ in range(1_00   ):
    # 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_     (       ):
  '''simple docstring'''





  lowerCAmelCase_     : Tuple     =  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(A__   )


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  main()







'''simple docstring'''






from maths.is_square_free import is_square_free
from maths.prime_factors import prime_factors







def 							UpperCamelCase_     (       A__   :  int   ):
  '''simple docstring'''





  lowerCAmelCase_     : Any     =  prime_factors(A__   )
  if is_square_free(A__   ):
    return -1 if len(A__   ) % 2 else 1
  return 0


if __name__ == "__main__":
  import doctest

  doctest.testmod()



