






from __future__ import annotations

from random import random
from typing import Generic, TypeVar

__A					=	TypeVar("KT")
__A					=	TypeVar("VT")



class 				_A			(     Generic[KT, VT]				):
    """simple docstring"""

    def __init__(				self      :     int ,     __SCREAMING_SNAKE_CASE      :     KT | str = "root" ,     __SCREAMING_SNAKE_CASE      :     VT | None = None      )      ->							List[Any]:
           __UpperCAmelCase     				=key
           __UpperCAmelCase     				=value
           __UpperCAmelCase     				=[]



    def __repr__(				self      :     str      )      ->							str:
           return f'''Node({self.key}: {self.value})'''



    @property
    def _a							(				self      :     str      )      ->							int:
           return len(self.forward      )




class 				_A			(     Generic[KT, VT]				):
    """simple docstring"""

    def __init__(				self      :     Optional[int] ,     __SCREAMING_SNAKE_CASE      :     float = 0.5 ,     __SCREAMING_SNAKE_CASE      :     int = 16      )      ->							Optional[int]:
           __UpperCAmelCase     				=Node[KT, VT]()
           __UpperCAmelCase     				=0
           __UpperCAmelCase     				=p
           __UpperCAmelCase     				=max_level



    def __str__(				self      :     Optional[int]      )      ->							str:
           __UpperCAmelCase     				=list(self      )

           if len(__SCREAMING_SNAKE_CASE      ) == 0:
                  return f'''SkipList(level={self.level})'''

           __UpperCAmelCase     				=max((len(str(__SCREAMING_SNAKE_CASE      )      ) for item in items) ,     default=4      )
           __UpperCAmelCase     				=max(__SCREAMING_SNAKE_CASE ,     4      ) + 4

           __UpperCAmelCase     				=self.head
           __UpperCAmelCase     				=[]

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

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

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

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



    def __iter__(				self      :     Tuple      )      ->							Optional[int]:
           __UpperCAmelCase     				=self.head

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



    def _a							(				self      :     Dict      )      ->							int:
           __UpperCAmelCase     				=1
           while random() < self.p and level < self.max_level:
                  level += 1

           return level



    def _a							(				self      :     int ,     __SCREAMING_SNAKE_CASE      :     List[str]      )      ->							tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:
           __UpperCAmelCase     				=[]

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

           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      :     Any ,     __SCREAMING_SNAKE_CASE      :     KT      )      ->							Any:
           __UpperCAmelCase				, __UpperCAmelCase     				=self._locate_node(__SCREAMING_SNAKE_CASE      )

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



    def _a							(				self      :     Dict ,     __SCREAMING_SNAKE_CASE      :     KT ,     __SCREAMING_SNAKE_CASE      :     VT      )      ->							Any:
           __UpperCAmelCase				, __UpperCAmelCase     				=self._locate_node(__SCREAMING_SNAKE_CASE      )
           if node is not None:
                  __UpperCAmelCase     				=value
           else:
                  __UpperCAmelCase     				=self.random_level()

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

                  __UpperCAmelCase     				=Node(__SCREAMING_SNAKE_CASE ,     __SCREAMING_SNAKE_CASE      )

                  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(__SCREAMING_SNAKE_CASE      )
                         else:
                                __UpperCAmelCase     				=new_node



    def _a							(				self      :     Optional[Any] ,     __SCREAMING_SNAKE_CASE      :     VT      )      ->							VT | None:
           __UpperCAmelCase				, __UpperCAmelCase     				=self._locate_node(__SCREAMING_SNAKE_CASE      )

           if node is not None:
                  return node.value

           return None







def       lowercase__	(					)	->				Any:







       """simple docstring"""






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

       __UpperCAmelCase     				=skip_list.head
       __UpperCAmelCase     				={}
       while node.level != 0:
              __UpperCAmelCase     				=node.forward[0]
              __UpperCAmelCase     				=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       lowercase__	(					)	->				Optional[Any]:







       """simple docstring"""






       __UpperCAmelCase     				=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     				=skip_list.head
       __UpperCAmelCase     				={}
       while node.level != 0:
              __UpperCAmelCase     				=node.forward[0]
              __UpperCAmelCase     				=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       lowercase__	(					)	->				Union[str, Any]:







       """simple docstring"""






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







def       lowercase__	(					)	->				int:







       """simple docstring"""






       __UpperCAmelCase     				=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       lowercase__	(					)	->				Tuple:







       """simple docstring"""






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

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







def       lowercase__	(					)	->				Dict:







       """simple docstring"""






       __UpperCAmelCase     				=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       lowercase__	(					)	->				Any:







       """simple docstring"""






       __UpperCAmelCase     				=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       lowercase__	(					)	->				Dict:







       """simple docstring"""






       __UpperCAmelCase     				=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(A_:						Dict		):
              yield node.key
              for forward_node in node.forward:
                     yield from traverse_keys(A_		)

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







def       lowercase__	(					)	->				Optional[Any]:







       """simple docstring"""






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

       __UpperCAmelCase     				=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       lowercase__	(					)	->				Dict:







       """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       lowercase__	(					)	->				Optional[int]:







       """simple docstring"""






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





import unittest

import numpy as np

from transformers import AlbertConfig, is_flax_available
from transformers.testing_utils import require_flax, slow

from ...test_modeling_flax_common import FlaxModelTesterMixin, ids_tensor, random_attention_mask


if is_flax_available():
  import jax.numpy as jnp

  from transformers.models.albert.modeling_flax_albert import (
      FlaxAlbertForMaskedLM,
      FlaxAlbertForMultipleChoice,
      FlaxAlbertForPreTraining,
      FlaxAlbertForQuestionAnswering,
      FlaxAlbertForSequenceClassification,
      FlaxAlbertForTokenClassification,
      FlaxAlbertModel,
  )




class 			__magic_name__	(		unittest.TestCase     ):





   """simple docstring"""




   def __init__(						self       :	Any		,	_lowercase       :	Optional[int]		,	_lowercase       :	Tuple=13		,	_lowercase       :	str=7		,	_lowercase       :	List[Any]=True		,	_lowercase       :	Optional[int]=True		,	_lowercase       :	str=True		,	_lowercase       :	Optional[int]=True		,	_lowercase       :	Dict=99		,	_lowercase       :	List[Any]=32		,	_lowercase       :	List[str]=5		,	_lowercase       :	str=4		,	_lowercase       :	int=37		,	_lowercase       :	List[str]="gelu"		,	_lowercase       :	Any=0.1		,	_lowercase       :	Optional[int]=0.1		,	_lowercase       :	Dict=512		,	_lowercase       :	int=16		,	_lowercase       :	Optional[Any]=2		,	_lowercase       :	Dict=0.02		,	_lowercase       :	List[Any]=4		,	):



    """simple docstring"""



    _UpperCamelCase:  List[str]    						=			parent
    _UpperCamelCase:  int    						=			batch_size
    _UpperCamelCase:  List[str]    						=			seq_length
    _UpperCamelCase:  Optional[int]    						=			is_training
    _UpperCamelCase:  Optional[Any]    						=			use_attention_mask
    _UpperCamelCase:  Any    						=			use_token_type_ids
    _UpperCamelCase:  List[str]    						=			use_labels
    _UpperCamelCase:  Optional[int]    						=			vocab_size
    _UpperCamelCase:  List[str]    						=			hidden_size
    _UpperCamelCase:  Union[str, Any]    						=			num_hidden_layers
    _UpperCamelCase:  Any    						=			num_attention_heads
    _UpperCamelCase:  List[str]    						=			intermediate_size
    _UpperCamelCase:  Union[str, Any]    						=			hidden_act
    _UpperCamelCase:  Dict    						=			hidden_dropout_prob
    _UpperCamelCase:  List[str]    						=			attention_probs_dropout_prob
    _UpperCamelCase:  str    						=			max_position_embeddings
    _UpperCamelCase:  Dict    						=			type_vocab_size
    _UpperCamelCase:  Tuple    						=			type_sequence_label_size
    _UpperCamelCase:  List[Any]    						=			initializer_range
    _UpperCamelCase:  str    						=			num_choices



   def 	lowerCAmelCase    (						self       :	str				):



    """simple docstring"""



    _UpperCamelCase:  str    						=			ids_tensor([self.batch_size, self.seq_length]		,	self.vocab_size				)

    _UpperCamelCase:  Any    						=			None
    if self.use_attention_mask:
     _UpperCamelCase:  List[str]    						=			random_attention_mask([self.batch_size, self.seq_length]				)

    _UpperCamelCase:  Optional[Any]    						=			None
    if self.use_token_type_ids:
     _UpperCamelCase:  Optional[Any]    						=			ids_tensor([self.batch_size, self.seq_length]		,	self.type_vocab_size				)

    _UpperCamelCase:  Tuple    						=			AlbertConfig(
        vocab_size=self.vocab_size		,	hidden_size=self.hidden_size		,	num_hidden_layers=self.num_hidden_layers		,	num_attention_heads=self.num_attention_heads		,	intermediate_size=self.intermediate_size		,	hidden_act=self.hidden_act		,	hidden_dropout_prob=self.hidden_dropout_prob		,	attention_probs_dropout_prob=self.attention_probs_dropout_prob		,	max_position_embeddings=self.max_position_embeddings		,	type_vocab_size=self.type_vocab_size		,	is_decoder=_lowercase		,	initializer_range=self.initializer_range		,	)

    return config, input_ids, token_type_ids, attention_mask



   def 	lowerCAmelCase    (						self       :	int				):



    """simple docstring"""



    _UpperCamelCase:  List[Any]    						=			self.prepare_config_and_inputs()
    _UpperCamelCase						,				_UpperCamelCase						,				_UpperCamelCase						,				_UpperCamelCase:  int    						=			config_and_inputs
    _UpperCamelCase:  int    						=			{'''input_ids''': input_ids, '''token_type_ids''': token_type_ids, '''attention_mask''': attention_mask}
    return config, inputs_dict




@require_flax
class 			__magic_name__	(		__a   ,						unittest.TestCase     ):





   """simple docstring"""




   lowerCAmelCase   :     Any	      = (
       (
           FlaxAlbertModel,
           FlaxAlbertForPreTraining,
           FlaxAlbertForMaskedLM,
           FlaxAlbertForMultipleChoice,
           FlaxAlbertForQuestionAnswering,
           FlaxAlbertForSequenceClassification,
           FlaxAlbertForTokenClassification,
           FlaxAlbertForQuestionAnswering,
       )
       if is_flax_available()
       else ()
   )



   def 	lowerCAmelCase    (						self       :	Union[str, Any]				):



    """simple docstring"""



    _UpperCamelCase:  Optional[int]    						=			FlaxAlbertModelTester(self				)



   @slow
   def 	lowerCAmelCase    (						self       :	Union[str, Any]				):



    """simple docstring"""



    for model_class_name in self.all_model_classes:
     _UpperCamelCase:  int    						=			model_class_name.from_pretrained('''albert-base-v2'''				)
     _UpperCamelCase:  List[Any]    						=			model(np.ones((1, 1)				)				)
     self.assertIsNotNone(_lowercase				)




@require_flax
class 			__magic_name__	(		unittest.TestCase     ):





   """simple docstring"""




   @slow
   def 	lowerCAmelCase    (						self       :	int				):



    """simple docstring"""



    _UpperCamelCase:  Optional[int]    						=			FlaxAlbertModel.from_pretrained('''albert-base-v2'''				)
    _UpperCamelCase:  List[Any]    						=			np.array([[0, 345, 232, 328, 740, 140, 1_695, 69, 6_078, 1_588, 2]]				)
    _UpperCamelCase:  Optional[int]    						=			np.array([[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]				)
    _UpperCamelCase:  Optional[int]    						=			model(_lowercase		,	attention_mask=_lowercase				)[0]
    _UpperCamelCase:  Tuple    						=			(1, 11, 768)
    self.assertEqual(output.shape		,	_lowercase				)
    _UpperCamelCase:  Tuple    						=			np.array(
        [[[-0.6513, 1.5035, -0.2766], [-0.6515, 1.5046, -0.2780], [-0.6512, 1.5049, -0.2784]]]				)

    self.assertTrue(jnp.allclose(output[:, 1:4, 1:4]		,	_lowercase		,	atol=1E-4				)				)