

'''simple docstring'''
from ...configuration_utils import PretrainedConfig
from ...utils import logging


lowerCamelCase :      List[str]					 =     logging.get_logger(__name__)

lowerCamelCase :      Any					 =     {"ctrl": "https://huggingface.co/ctrl/resolve/main/config.json"}







class 							A__    (       A__  ):
  A__		 =				'ctrl'
  A__		 =				['past_key_values']
  A__		 =				{
      'max_position_embeddings': 'n_positions',
      'hidden_size': 'n_embd',
      'num_attention_heads': 'n_head',
      'num_hidden_layers': 'n_layer',
  }





  def __init__(		self      :	Optional[Any]							,					_a      :	str=24_6534							,					_a      :	Union[str, Any]=256							,					_a      :	List[str]=1280							,					_a      :	List[str]=8192							,					_a      :	Optional[int]=48							,					_a      :	List[Any]=16							,					_a      :	int=0.1							,					_a      :	Tuple=0.1							,					_a      :	Union[str, Any]=1e-6							,					_a      :	Optional[int]=0.02							,					_a      :	List[str]=True							,					**_a      :	Optional[Any]							,					)	->    Optional[int]:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =vocab_size
       _SCREAMING_SNAKE_CASE							    =n_positions
       _SCREAMING_SNAKE_CASE							    =n_embd
       _SCREAMING_SNAKE_CASE							    =n_layer
       _SCREAMING_SNAKE_CASE							    =n_head
       _SCREAMING_SNAKE_CASE							    =dff
       _SCREAMING_SNAKE_CASE							    =resid_pdrop
       _SCREAMING_SNAKE_CASE							    =embd_pdrop
       _SCREAMING_SNAKE_CASE							    =layer_norm_epsilon
       _SCREAMING_SNAKE_CASE							    =initializer_range

       _SCREAMING_SNAKE_CASE							    =use_cache

       super().__init__(**_a )



'''simple docstring'''
from __future__ import annotations

from random import random
from typing import Generic, TypeVar

lowerCamelCase :      Union[str, Any]					 =     TypeVar("KT")
lowerCamelCase :      Dict					 =     TypeVar("VT")







class 							A__    (       Generic[KT, VT]  ):





  def __init__(		self      :	str							,					_a      :	KT | str = "root"							,					_a      :	VT | None = None )	->    Dict:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =key
       _SCREAMING_SNAKE_CASE							    =value
       _SCREAMING_SNAKE_CASE							    =[]





  def __repr__(		self      :	Union[str, Any] )	->    str:





       '''simple docstring'''






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





  @property
  def 						A  (		self      :	int )	->    int:





       '''simple docstring'''






       return len(self.forward )







class 							A__    (       Generic[KT, VT]  ):





  def __init__(		self      :	Optional[Any]							,					_a      :	float = 0.5							,					_a      :	int = 16 )	->    str:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =Node[KT, VT]()
       _SCREAMING_SNAKE_CASE							    =0
       _SCREAMING_SNAKE_CASE							    =p
       _SCREAMING_SNAKE_CASE							    =max_level





  def __str__(		self      :	Tuple )	->    str:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =list(self )

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

       _SCREAMING_SNAKE_CASE							    =max((len(str(_a ) ) for item in items)							,					default=4 )
       _SCREAMING_SNAKE_CASE							    =max(_a							,					4 ) + 4

       _SCREAMING_SNAKE_CASE							    =self.head
       _SCREAMING_SNAKE_CASE							    =[]

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

       while len(node.forward ) != 0:
            _SCREAMING_SNAKE_CASE							    =node.forward[0]

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

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





  def __iter__(		self      :	Dict )	->    Optional[Any]:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =self.head

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





  def 						A  (		self      :	List[Any] )	->    int:





       '''simple docstring'''






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

       return level





  def 						A  (		self      :	Any							,					_a      :	Any )	->    tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE							    =[]

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

       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 						A  (		self      :	Union[str, Any]							,					_a      :	KT )	->    int:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE    ,						_SCREAMING_SNAKE_CASE							    =self._locate_node(_a )

       if node is not None:
            for i, update_node in enumerate(_a ):
                 # Remove or replace all references to removed node.
                 if update_node.level > i and update_node.forward[i].key == key:
                      if node.level > i:
                           _SCREAMING_SNAKE_CASE							    =node.forward[i]
                      else:
                           _SCREAMING_SNAKE_CASE							    =update_node.forward[:i]





  def 						A  (		self      :	Optional[Any]							,					_a      :	KT							,					_a      :	VT )	->    str:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE    ,						_SCREAMING_SNAKE_CASE							    =self._locate_node(_a )
       if node is not None:
            _SCREAMING_SNAKE_CASE							    =value
       else:
            _SCREAMING_SNAKE_CASE							    =self.random_level()

            if level > self.level:
                 # After level increase we have to add additional nodes to head.
                 for _ in range(self.level - 1							,					_a ):
                      update_vector.append(self.head )
                 _SCREAMING_SNAKE_CASE							    =level

            _SCREAMING_SNAKE_CASE							    =Node(_a							,					_a )

            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(_a )
                 else:
                      _SCREAMING_SNAKE_CASE							    =new_node





  def 						A  (		self      :	List[str]							,					_a      :	VT )	->    VT | None:





       '''simple docstring'''






       _SCREAMING_SNAKE_CASE    ,						_SCREAMING_SNAKE_CASE							    =self._locate_node(_a )

       if node is not None:
            return node.value

       return None


def        _lowerCAmelCase					(						)      ->			str:
     """simple docstring"""




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

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




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

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




     _SCREAMING_SNAKE_CASE							    =SkipList()
     assert skip_list.find('Some key'				) is None


def        _lowerCAmelCase					(						)      ->			str:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =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					(						)      ->			List[Any]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =SkipList()
     skip_list.delete('Some key'				)

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


def        _lowerCAmelCase					(						)      ->			Optional[Any]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =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					(						)      ->			List[str]:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =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					(						)      ->			Dict:
     """simple docstring"""




     _SCREAMING_SNAKE_CASE							    =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(_UpperCamelCase						:     Dict				):
          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					(						)      ->			Union[str, Any]:
     """simple docstring"""




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

     _SCREAMING_SNAKE_CASE							    =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					(						)      ->			List[str]:
     """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        _lowerCAmelCase					(						)      ->			Dict:
     """simple docstring"""




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