
"""simple docstring"""



from __future__ import annotations

from random import random
from typing import Generic, TypeVar

_snake_case        =    TypeVar('''KT''')
_snake_case        =    TypeVar('''VT''')
class 							_SCREAMING_SNAKE_CASE	(	Generic[KT, VT]				):






				'''simple docstring'''



				def __init__(       self						:      List[Any]					,  UpperCAmelCase_						:      Tuple = "root"					,  UpperCAmelCase_						:      str = None	)		->	int:







											"""simple docstring"""




											_lowerCAmelCase							=      key
											_lowerCAmelCase							=      value
											_lowerCAmelCase							=      []


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







											"""simple docstring"""




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







				@property
				def 					__lowerCamelCase						(       self						:      str	)		->	Optional[Any]:







											"""simple docstring"""




											return len(self.forward	)






class 							_SCREAMING_SNAKE_CASE	(	Generic[KT, VT]				):






				'''simple docstring'''



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







											"""simple docstring"""




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


				def __str__(       self						:      Optional[Any]	)		->	List[str]:







											"""simple docstring"""




											_lowerCAmelCase							=      list(self	)

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

											_lowerCAmelCase							=      max((len(str(UpperCAmelCase_	)	) for item in items)					,  default=4	)
											_lowerCAmelCase							=      max(UpperCAmelCase_					,  4	) + 4

											_lowerCAmelCase							=      self.head
											_lowerCAmelCase							=      []

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

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

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


				def __iter__(       self						:      int	)		->	int:







											"""simple docstring"""




											_lowerCAmelCase							=      self.head

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


				def 					__lowerCamelCase						(       self						:      Tuple	)		->	Tuple:







											"""simple docstring"""




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

											return level


				def 					__lowerCamelCase						(       self						:      Tuple					,  UpperCAmelCase_						:      List[str]	)		->	Union[str, Any]:







											"""simple docstring"""




											_lowerCAmelCase							=      []

											_lowerCAmelCase							=      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							=      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[str]					,  UpperCAmelCase_						:      List[Any]	)		->	Optional[Any]:







											"""simple docstring"""




											_lowerCAmelCase							=      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							=      node.forward[i]
																																else:
																																							_lowerCAmelCase							=      update_node.forward[:i]


				def 					__lowerCamelCase						(       self						:      List[Any]					,  UpperCAmelCase_						:      str					,  UpperCAmelCase_						:      Union[str, Any]	)		->	Tuple:







											"""simple docstring"""




											_lowerCAmelCase							=      self._locate_node(UpperCAmelCase_	)
											if node is not None:
																		_lowerCAmelCase							=      value
											else:
																		_lowerCAmelCase							=      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							=      level

																		_lowerCAmelCase							=      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							=      new_node







				def 					__lowerCamelCase						(       self						:      str					,  UpperCAmelCase_						:      str	)		->	Optional[int]:







											"""simple docstring"""




											_lowerCAmelCase							=      self._locate_node(UpperCAmelCase_	)

											if node is not None:
																		return node.value

											return None






def 						__snake_case	(     ):






							"""simple docstring"""



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

							_lowerCAmelCase							=      skip_list.head
							_lowerCAmelCase							=      {}
							while node.level != 0:
														_lowerCAmelCase							=      node.forward[0]
														_lowerCAmelCase							=      node.value

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






def 						__snake_case	(     ):






							"""simple docstring"""



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

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






def 						__snake_case	(     ):






							"""simple docstring"""



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






def 						__snake_case	(     ):






							"""simple docstring"""



							_lowerCAmelCase							=      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	(     ):






							"""simple docstring"""



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

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






def 						__snake_case	(     ):






							"""simple docstring"""



							_lowerCAmelCase							=      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	(     ):






							"""simple docstring"""



							_lowerCAmelCase							=      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	(     ):






							"""simple docstring"""



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

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






def 						__snake_case	(     ):






							"""simple docstring"""



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

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






def 						__snake_case	(     ):






							"""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 						__snake_case	(     ):






							"""simple docstring"""



							_lowerCAmelCase							=      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(lowercase__    )


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	main()












"""simple docstring"""






from ...configuration_utils import PretrainedConfig
from ...utils import logging


lowercase__			=		logging.get_logger(__name__)

lowercase__			=		{"""openai-gpt""": """https://huggingface.co/openai-gpt/resolve/main/config.json"""}






class lowerCAmelCase__      (	lowercase		):






			'''simple docstring'''



			lowerCamelCase__ =     """openai-gpt"""
			lowerCamelCase__ =     {
			    """max_position_embeddings""": """n_positions""",
			    """hidden_size""": """n_embd""",
			    """num_attention_heads""": """n_head""",
			    """num_hidden_layers""": """n_layer""",
			}
			def __init__(    self    , lowercase=40478    , lowercase=512    , lowercase=768    , lowercase=12    , lowercase=12    , lowercase="gelu"    , lowercase=0.1    , lowercase=0.1    , lowercase=0.1    , lowercase=1E-5    , lowercase=0.02    , lowercase="cls_index"    , lowercase=True    , lowercase=None    , lowercase=True    , lowercase=0.1    , **lowercase    , ):
							_lowerCamelCase	:     Tuple       =       vocab_size
							_lowerCamelCase	:     List[str]       =       n_positions
							_lowerCamelCase	:     Tuple       =       n_embd
							_lowerCamelCase	:     Optional[int]       =       n_layer
							_lowerCamelCase	:     List[Any]       =       n_head
							_lowerCamelCase	:     Dict       =       afn
							_lowerCamelCase	:     Union[str, Any]       =       resid_pdrop
							_lowerCamelCase	:     Dict       =       embd_pdrop
							_lowerCamelCase	:     List[Any]       =       attn_pdrop
							_lowerCamelCase	:     Any       =       layer_norm_epsilon
							_lowerCamelCase	:     List[Any]       =       initializer_range
							_lowerCamelCase	:     List[Any]       =       summary_type
							_lowerCamelCase	:     List[str]       =       summary_use_proj
							_lowerCamelCase	:     Tuple       =       summary_activation
							_lowerCamelCase	:     int       =       summary_first_dropout
							_lowerCamelCase	:     str       =       summary_proj_to_labels
							super().__init__(**lowercase    )