

"""simple docstring"""





from __future__ import annotations

from random import random
from typing import Generic, TypeVar

_a							=							TypeVar('KT')
_a							=							TypeVar('VT')




class  _lowerCAmelCase  (     Generic[KT, VT]       ):







 """simple docstring"""







 def __init__(      self							:      List[str], UpperCAmelCase__							:      KT | str = "root", UpperCAmelCase__							:      VT | None = None     ):
    __lowercase								=						key
    __lowercase								=						value
    __lowercase								=						[]


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



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







class  _lowerCAmelCase  (     Generic[KT, VT]       ):







 """simple docstring"""







 def __init__(      self							:      Union[str, Any], UpperCAmelCase__							:      float = 0.5, UpperCAmelCase__							:      int = 1_6     ):
    __lowercase								=						Node[KT, VT]()
    __lowercase								=						0
    __lowercase								=						p
    __lowercase								=						max_level


 def __str__(      self							:      Optional[Any]     ):
    __lowercase								=						list(self     )

    if len(UpperCAmelCase__     ) == 0:
       return F"""SkipList(level={self.level})"""

    __lowercase								=						max((len(str(UpperCAmelCase__     )     ) for item in items), default=4     )
    __lowercase								=						max(UpperCAmelCase__, 4     ) + 4

    __lowercase								=						self.head
    __lowercase								=						[]

    __lowercase								=						node.forward.copy()
    lines.append(F"""[{node.key}]""".ljust(UpperCAmelCase__, "-"     ) + "* " * len(UpperCAmelCase__     )     )
    lines.append(" " * label_size + "| " * len(UpperCAmelCase__     )     )

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

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


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

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


 def  _lowercase			(      self							:      int     ):
    __lowercase								=						1
    while random() < self.p and level < self.max_level:
       level += 1

    return level


 def  _lowercase			(      self							:      Union[str, Any], UpperCAmelCase__							:      Any     ):
    __lowercase								=						[]

    __lowercase								=						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:
          __lowercase								=						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  _lowercase			(      self							:      List[str], UpperCAmelCase__							:      KT     ):
    __lowercase		,__lowercase								=						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:
                __lowercase								=						node.forward[i]
             else:
                __lowercase								=						update_node.forward[:i]


 def  _lowercase			(      self							:      Optional[Any], UpperCAmelCase__							:      KT, UpperCAmelCase__							:      VT     ):
    __lowercase		,__lowercase								=						self._locate_node(UpperCAmelCase__     )
    if node is not None:
       __lowercase								=						value
    else:
       __lowercase								=						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     )
          __lowercase								=						level

       __lowercase								=						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:
             __lowercase								=						new_node



 def  _lowercase			(      self							:      str, UpperCAmelCase__							:      VT     ):
    __lowercase		,__lowercase								=						self._locate_node(UpperCAmelCase__     )

    if node is not None:
       return node.value

    return None







def   _A  (  )     ->						List[Any]:
   '''simple docstring'''


   __lowercase								=						SkipList()
   skip_list.insert("Key1",      3)
   skip_list.insert("Key2",      12)
   skip_list.insert("Key3",      41)
   skip_list.insert("Key4",      -19)

   __lowercase								=						skip_list.head
   __lowercase								=						{}
   while node.level != 0:
      __lowercase								=						node.forward[0]
      __lowercase								=						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   _A  (  )     ->						Tuple:
   '''simple docstring'''


   __lowercase								=						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)

   __lowercase								=						skip_list.head
   __lowercase								=						{}
   while node.level != 0:
      __lowercase								=						node.forward[0]
      __lowercase								=						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   _A  (  )     ->						Optional[Any]:
   '''simple docstring'''


   __lowercase								=						SkipList()
   assert skip_list.find("Some key") is None




def   _A  (  )     ->						Optional[int]:
   '''simple docstring'''


   __lowercase								=						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   _A  (  )     ->						Optional[Any]:
   '''simple docstring'''


   __lowercase								=						SkipList()
   skip_list.delete("Some key")

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




def   _A  (  )     ->						Union[str, Any]:
   '''simple docstring'''


   __lowercase								=						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   _A  (  )     ->						str:
   '''simple docstring'''


   __lowercase								=						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   _A  (  )     ->						Dict:
   '''simple docstring'''


   __lowercase								=						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_					:	Optional[int]):
      yield node.key
      for forward_node in node.forward:
         yield from traverse_keys(UpperCamelCase_)

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




def   _A  (  )     ->						List[str]:
   '''simple docstring'''


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

   __lowercase								=						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   _A  (  )     ->						Union[str, Any]:
   '''simple docstring'''


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


   __lowercase								=						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()







"""simple docstring"""





from __future__ import annotations

from typing import Any




class  _lowerCAmelCase  :







 """simple docstring"""







 def __init__(      self							:      Union[str, Any], UpperCAmelCase__							:      int     ):
    __lowercase								=						num_of_nodes
    __lowercase								=						[]
    __lowercase								=						{}


 def  _lowercase			(      self							:      Tuple, UpperCAmelCase__							:      int, UpperCAmelCase__							:      int, UpperCAmelCase__							:      int     ):
    self.m_edges.append([u_node, v_node, weight]     )


 def  _lowercase			(      self							:      Dict, UpperCAmelCase__							:      int     ):

    if self.m_component[u_node] == u_node:
       return u_node
    return self.find_component(self.m_component[u_node]     )


 def  _lowercase			(      self							:      Dict, UpperCAmelCase__							:      int     ):

    if self.m_component[u_node] != u_node:
       for k in self.m_component:
          __lowercase								=						self.find_component(UpperCAmelCase__     )


 def  _lowercase			(      self							:      str, UpperCAmelCase__							:      list[int], UpperCAmelCase__							:      int, UpperCAmelCase__							:      int     ):

    if component_size[u_node] <= component_size[v_node]:
       __lowercase								=						v_node
       component_size[v_node] += component_size[u_node]
       self.set_component(UpperCAmelCase__     )

    elif component_size[u_node] >= component_size[v_node]:
       __lowercase								=						self.find_component(UpperCAmelCase__     )
       component_size[u_node] += component_size[v_node]
       self.set_component(UpperCAmelCase__     )



 def  _lowercase			(      self							:      Tuple     ):
    __lowercase								=						[]
    __lowercase								=						0

    __lowercase								=						[-1] * self.m_num_of_nodes

    # A list of components (initialized to all of the nodes)
    for node in range(self.m_num_of_nodes     ):
       self.m_component.update({node: node}     )
       component_size.append(1     )

    __lowercase								=						self.m_num_of_nodes

    while num_of_components > 1:
       for edge in self.m_edges:
          __lowercase		,__lowercase		,__lowercase								=						edge

          __lowercase								=						self.m_component[u]
          __lowercase								=						self.m_component[v]

          if u_component != v_component:

             for component in (u_component, v_component):
                if (
                    minimum_weight_edge[component] == -1
                    or minimum_weight_edge[component][2] > w
                ):
                   __lowercase								=						[u, v, w]

       for edge in minimum_weight_edge:
          if isinstance(UpperCAmelCase__, UpperCAmelCase__     ):
             __lowercase		,__lowercase		,__lowercase								=						edge

             __lowercase								=						self.m_component[u]
             __lowercase								=						self.m_component[v]

             if u_component != v_component:
                mst_weight += w
                self.union(UpperCAmelCase__, UpperCAmelCase__, UpperCAmelCase__     )
                print(F"""Added edge [{u} - {v}]\nAdded weight: {w}\n"""     )
                num_of_components -= 1

       __lowercase								=						[-1] * self.m_num_of_nodes
    print(F"""The total weight of the minimal spanning tree is: {mst_weight}"""     )







def   _A  (  )     ->						None:
   '''simple docstring'''




if __name__ == "__main__":
   import doctest

   doctest.testmod()




