



"""simple docstring"""







import argparse
import os

import gluonnlp as nlp
import mxnet as mx
import numpy as np
import torch
from gluonnlp.base import get_home_dir
from gluonnlp.model.bert import BERTEncoder
from gluonnlp.model.utils import _load_vocab
from gluonnlp.vocab import Vocab
from packaging import version
from torch import nn

from transformers import BertConfig, BertForMaskedLM, BertModel, RobertaTokenizer
from transformers.models.bert.modeling_bert import (
    BertIntermediate,
    BertLayer,
    BertOutput,
    BertSelfAttention,
    BertSelfOutput,
)
from transformers.utils import logging


if version.parse(nlp.__version__) != version.parse("0.8.3"):
       raise Exception("requires gluonnlp == 0.8.3")

if version.parse(mx.__version__) != version.parse("1.5.0"):
       raise Exception("requires mxnet == 1.5.0")

logging.set_verbosity_info()
lowerCAmelCase__									=logging.get_logger(__name__)

lowerCAmelCase__									="The Nymphenburg Palace is a beautiful palace in Munich!"






def     _a (	UpperCAmelCase__     ,	UpperCAmelCase__     )						->    Optional[int]:
      __SCREAMING_SNAKE_CASE       		=   {
          '''attention_cell''': '''multi_head''',
          '''num_layers''': 4,
          '''units''': 10_24,
          '''hidden_size''': 7_68,
          '''max_length''': 5_12,
          '''num_heads''': 8,
          '''scaled''': True,
          '''dropout''': 0.1,
          '''use_residual''': True,
          '''embed_size''': 10_24,
          '''embed_dropout''': 0.1,
          '''word_embed''': None,
          '''layer_norm_eps''': 1E-5,
          '''token_type_vocab_size''': 2,
      }

      __SCREAMING_SNAKE_CASE       		=   bort_4_8_768_1024_hparams

      # Let's construct the original Bort model here
      # Taken from official BERT implementation, see:
      # https://github.com/alexa/bort/blob/master/bort/bort.py
      __SCREAMING_SNAKE_CASE       		=   BERTEncoder(
          attention_cell=predefined_args['''attention_cell''']     ,	num_layers=predefined_args['''num_layers''']     ,	units=predefined_args['''units''']     ,	hidden_size=predefined_args['''hidden_size''']     ,	max_length=predefined_args['''max_length''']     ,	num_heads=predefined_args['''num_heads''']     ,	scaled=predefined_args['''scaled''']     ,	dropout=predefined_args['''dropout''']     ,	output_attention=__lowerCamelCase     ,	output_all_encodings=__lowerCamelCase     ,	use_residual=predefined_args['''use_residual''']     ,	activation=predefined_args.get('''activation'''     ,	'''gelu'''     )     ,	layer_norm_eps=predefined_args.get('''layer_norm_eps'''     ,	__lowerCamelCase     )     ,	)

      # Vocab information needs to be fetched first
      # It's the same as RoBERTa, so RobertaTokenizer can be used later
      __SCREAMING_SNAKE_CASE       		=   '''openwebtext_ccnews_stories_books_cased'''

      # Specify download folder to Gluonnlp's vocab
      __SCREAMING_SNAKE_CASE       		=   os.path.join(get_home_dir()     ,	'''models'''     )
      __SCREAMING_SNAKE_CASE       		=   _load_vocab(__lowerCamelCase     ,	__lowerCamelCase     ,	__lowerCamelCase     ,	cls=__lowerCamelCase     )

      __SCREAMING_SNAKE_CASE       		=   nlp.model.BERTModel(
          __lowerCamelCase     ,	len(__lowerCamelCase     )     ,	units=predefined_args['''units''']     ,	embed_size=predefined_args['''embed_size''']     ,	embed_dropout=predefined_args['''embed_dropout''']     ,	word_embed=predefined_args['''word_embed''']     ,	use_pooler=__lowerCamelCase     ,	use_token_type_embed=__lowerCamelCase     ,	token_type_vocab_size=predefined_args['''token_type_vocab_size''']     ,	use_classifier=__lowerCamelCase     ,	use_decoder=__lowerCamelCase     ,	)

      original_bort.load_parameters(__lowerCamelCase     ,	cast_dtype=__lowerCamelCase     ,	ignore_extra=__lowerCamelCase     )
      __SCREAMING_SNAKE_CASE       		=   original_bort._collect_params_with_prefix()

      # Build our config 🤗
      __SCREAMING_SNAKE_CASE       		=   {
          '''architectures''': ['''BertForMaskedLM'''],
          '''attention_probs_dropout_prob''': predefined_args['''dropout'''],
          '''hidden_act''': '''gelu''',
          '''hidden_dropout_prob''': predefined_args['''dropout'''],
          '''hidden_size''': predefined_args['''embed_size'''],
          '''initializer_range''': 0.02,
          '''intermediate_size''': predefined_args['''hidden_size'''],
          '''layer_norm_eps''': predefined_args['''layer_norm_eps'''],
          '''max_position_embeddings''': predefined_args['''max_length'''],
          '''model_type''': '''bort''',
          '''num_attention_heads''': predefined_args['''num_heads'''],
          '''num_hidden_layers''': predefined_args['''num_layers'''],
          '''pad_token_id''': 1,  # 2 = BERT, 1 = RoBERTa
          '''type_vocab_size''': 1,  # 2 = BERT, 1 = RoBERTa
          '''vocab_size''': len(__lowerCamelCase     ),
      }

      __SCREAMING_SNAKE_CASE       		=   BertConfig.from_dict(__lowerCamelCase     )
      __SCREAMING_SNAKE_CASE       		=   BertForMaskedLM(__lowerCamelCase     )
      hf_bort_model.eval()

      # Parameter mapping table (Gluonnlp to Transformers)
      # * denotes layer index
      #
      # | Gluon Parameter                                                | Transformers Parameter
      # | -------------------------------------------------------------- | ----------------------
      # | `encoder.layer_norm.beta`                                      | `bert.embeddings.LayerNorm.bias`
      # | `encoder.layer_norm.gamma`                                     | `bert.embeddings.LayerNorm.weight`
      # | `encoder.position_weight`                                      | `bert.embeddings.position_embeddings.weight`
      # | `word_embed.0.weight`                                          | `bert.embeddings.word_embeddings.weight`
      # | `encoder.transformer_cells.*.attention_cell.proj_key.bias`     | `bert.encoder.layer.*.attention.self.key.bias`
      # | `encoder.transformer_cells.*.attention_cell.proj_key.weight`   | `bert.encoder.layer.*.attention.self.key.weight`
      # | `encoder.transformer_cells.*.attention_cell.proj_query.bias`   | `bert.encoder.layer.*.attention.self.query.bias`
      # | `encoder.transformer_cells.*.attention_cell.proj_query.weight` | `bert.encoder.layer.*.attention.self.query.weight`
      # | `encoder.transformer_cells.*.attention_cell.proj_value.bias`   | `bert.encoder.layer.*.attention.self.value.bias`
      # | `encoder.transformer_cells.*.attention_cell.proj_value.weight` | `bert.encoder.layer.*.attention.self.value.weight`
      # | `encoder.transformer_cells.*.ffn.ffn_2.bias`                   | `bert.encoder.layer.*.attention.output.dense.bias`
      # | `encoder.transformer_cells.*.ffn.ffn_2.weight`                 | `bert.encoder.layer.*.attention.output.dense.weight`
      # | `encoder.transformer_cells.*.layer_norm.beta`                  | `bert.encoder.layer.*.attention.output.LayerNorm.bias`
      # | `encoder.transformer_cells.*.layer_norm.gamma`                 | `bert.encoder.layer.*.attention.output.LayerNorm.weight`
      # | `encoder.transformer_cells.*.ffn.ffn_1.bias`                   | `bert.encoder.layer.*.intermediate.dense.bias`
      # | `encoder.transformer_cells.*.ffn.ffn_1.weight`                 | `bert.encoder.layer.*.intermediate.dense.weight`
      # | `encoder.transformer_cells.*.ffn.layer_norm.beta`              | `bert.encoder.layer.*.output.LayerNorm.bias`
      # | `encoder.transformer_cells.*.ffn.layer_norm.gamma`             | `bert.encoder.layer.*.output.LayerNorm.weight`
      # | `encoder.transformer_cells.*.proj.bias`                        | `bert.encoder.layer.*.output.dense.bias`
      # | `encoder.transformer_cells.*.proj.weight`                      | `bert.encoder.layer.*.output.dense.weight`

      # Helper function to convert MXNET Arrays to PyTorch
      def to_torch(UpperCAmelCase__     ) -> nn.Parameter:
            return nn.Parameter(torch.FloatTensor(mx_array.data().asnumpy()     )     )

      # Check param shapes and map new HF param back
      def check_and_map_params(UpperCAmelCase__     ,	UpperCAmelCase__     ):
            __SCREAMING_SNAKE_CASE       		=   hf_param.shape

            __SCREAMING_SNAKE_CASE       		=   to_torch(params[gluon_param]     )
            __SCREAMING_SNAKE_CASE       		=   gluon_param.shape

            assert (
                shape_hf == shape_gluon
            ), f"""The gluon parameter {gluon_param} has shape {shape_gluon}, but expects shape {shape_hf} for Transformers"""

            return gluon_param

      __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
          hf_bort_model.bert.embeddings.word_embeddings.weight     ,	'''word_embed.0.weight'''     )
      __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
          hf_bort_model.bert.embeddings.position_embeddings.weight     ,	'''encoder.position_weight'''     )
      __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
          hf_bort_model.bert.embeddings.LayerNorm.bias     ,	'''encoder.layer_norm.beta'''     )
      __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
          hf_bort_model.bert.embeddings.LayerNorm.weight     ,	'''encoder.layer_norm.gamma'''     )

      # Inspired by RoBERTa conversion script, we just zero them out (Bort does not use them)
      __SCREAMING_SNAKE_CASE       		=   torch.zeros_like(
          hf_bort_model.bert.embeddings.token_type_embeddings.weight.data     )

      for i in range(hf_bort_config.num_hidden_layers     ):
            __SCREAMING_SNAKE_CASE       		=   hf_bort_model.bert.encoder.layer[i]

            # self attention
            __SCREAMING_SNAKE_CASE       		=   layer.attention.self

            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                self_attn.key.bias.data     ,	f"""encoder.transformer_cells.{i}.attention_cell.proj_key.bias"""     )

            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                self_attn.key.weight.data     ,	f"""encoder.transformer_cells.{i}.attention_cell.proj_key.weight"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                self_attn.query.bias.data     ,	f"""encoder.transformer_cells.{i}.attention_cell.proj_query.bias"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                self_attn.query.weight.data     ,	f"""encoder.transformer_cells.{i}.attention_cell.proj_query.weight"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                self_attn.value.bias.data     ,	f"""encoder.transformer_cells.{i}.attention_cell.proj_value.bias"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                self_attn.value.weight.data     ,	f"""encoder.transformer_cells.{i}.attention_cell.proj_value.weight"""     )

            # self attention output
            __SCREAMING_SNAKE_CASE       		=   layer.attention.output

            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                self_output.dense.bias     ,	f"""encoder.transformer_cells.{i}.proj.bias"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                self_output.dense.weight     ,	f"""encoder.transformer_cells.{i}.proj.weight"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                self_output.LayerNorm.bias     ,	f"""encoder.transformer_cells.{i}.layer_norm.beta"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                self_output.LayerNorm.weight     ,	f"""encoder.transformer_cells.{i}.layer_norm.gamma"""     )

            # intermediate
            __SCREAMING_SNAKE_CASE       		=   layer.intermediate

            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                intermediate.dense.bias     ,	f"""encoder.transformer_cells.{i}.ffn.ffn_1.bias"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                intermediate.dense.weight     ,	f"""encoder.transformer_cells.{i}.ffn.ffn_1.weight"""     )

            # output
            __SCREAMING_SNAKE_CASE       		=   layer.output

            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                bert_output.dense.bias     ,	f"""encoder.transformer_cells.{i}.ffn.ffn_2.bias"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                bert_output.dense.weight     ,	f"""encoder.transformer_cells.{i}.ffn.ffn_2.weight"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                bert_output.LayerNorm.bias     ,	f"""encoder.transformer_cells.{i}.ffn.layer_norm.beta"""     )
            __SCREAMING_SNAKE_CASE       		=   check_and_map_params(
                bert_output.LayerNorm.weight     ,	f"""encoder.transformer_cells.{i}.ffn.layer_norm.gamma"""     )

      # Save space and energy 🎄
      hf_bort_model.half()

      # Compare output of both models
      __SCREAMING_SNAKE_CASE       		=   RobertaTokenizer.from_pretrained('''roberta-base'''     )

      __SCREAMING_SNAKE_CASE       		=   tokenizer.encode_plus(__lowerCamelCase     )['''input_ids''']

      # Get gluon output
      __SCREAMING_SNAKE_CASE       		=   mx.nd.array([input_ids]     )
      __SCREAMING_SNAKE_CASE       		=   original_bort(inputs=__lowerCamelCase     ,	token_types=[]     )

      # Get Transformer output (save and reload model again)
      hf_bort_model.save_pretrained(__lowerCamelCase     )
      __SCREAMING_SNAKE_CASE       		=   BertModel.from_pretrained(__lowerCamelCase     )
      hf_bort_model.eval()

      __SCREAMING_SNAKE_CASE       		=   tokenizer.encode_plus(__lowerCamelCase     ,	return_tensors='''pt'''     )
      __SCREAMING_SNAKE_CASE       		=   hf_bort_model(**__lowerCamelCase     )[0]

      __SCREAMING_SNAKE_CASE       		=   output_gluon[0].asnumpy()
      __SCREAMING_SNAKE_CASE       		=   output_hf[0].detach().numpy()

      __SCREAMING_SNAKE_CASE       		=   np.max(np.abs(hf_layer - gluon_layer     )     ).item()
      __SCREAMING_SNAKE_CASE       		=   np.allclose(__lowerCamelCase     ,	__lowerCamelCase     ,	atol=1E-3     )

      if success:
            print('''✔️ Both model do output the same tensors'''     )
      else:
            print('''❌ Both model do **NOT** output the same tensors'''     )
            print('''Absolute difference is:'''     ,	__lowerCamelCase     )


if __name__ == "__main__":
       lowerCAmelCase__									=argparse.ArgumentParser()
       # Required parameters
       parser.add_argument(
           "--bort_checkpoint_path", default=None, type=str, required=True, help="Path the official Bort params file."
       )
       parser.add_argument(
           "--pytorch_dump_folder_path", default=None, type=str, required=True, help="Path to the output PyTorch model."
       )
       lowerCAmelCase__									=parser.parse_args()
       convert_bort_checkpoint_to_pytorch(args.bort_checkpoint_path, args.pytorch_dump_folder_path)






from __future__ import annotations

from random import random
from typing import Generic, TypeVar

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

class 						__lowerCAmelCase      (      Generic[KT, VT]					):
							def __init__(		self		:Union[str, Any]						, __magic_name__		:KT | str = "root"						, __magic_name__		:VT | None = None							):







								'''simple docstring'''







								a									=				key
								a									=				value
								a									=				[]
							def __repr__(		self		:List[Any]							):







								'''simple docstring'''







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





							@property
							def  lowerCamelCase__				(		self		:List[str]							):







								'''simple docstring'''







								return len(self.forward							)







class 						__lowerCAmelCase      (      Generic[KT, VT]					):
							def __init__(		self		:Optional[Any]						, __magic_name__		:float = 0.5						, __magic_name__		:int = 16							):







								'''simple docstring'''







								a									=				Node[KT, VT]()
								a									=				0
								a									=				p
								a									=				max_level
							def __str__(		self		:Tuple							):







								'''simple docstring'''







								a									=				list(self							)

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

								a									=				max((len(str(__magic_name__							)							) for item in items)						, default=4							)
								a									=				max(__magic_name__						, 4							) + 4

								a									=				self.head
								a									=				[]

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

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

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

								lines.append("""None""".ljust(__magic_name__							) + """* """ * len(__magic_name__							)							)
								return F'SkipList(level={self.level})\n' + "\n".join(__magic_name__							)
							def __iter__(		self		:int							):







								'''simple docstring'''







								a									=				self.head

								while len(node.forward							) != 0:
									yield node.forward[0].key
									a									=				node.forward[0]
							def  lowerCamelCase__				(		self		:int							):







								'''simple docstring'''







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

								return level
							def  lowerCamelCase__				(		self		:Dict						, __magic_name__		:int							):







								'''simple docstring'''







								a									=				[]

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

								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]						, __magic_name__		:KT							):







								'''simple docstring'''







								a							,					a									=				self._locate_node(__magic_name__							)

								if node is not None:
									for i, update_node in enumerate(__magic_name__							):
										# Remove or replace all references to removed node.
										if update_node.level > i and update_node.forward[i].key == key:
											if node.level > i:
												a									=				node.forward[i]
											else:
												a									=				update_node.forward[:i]
							def  lowerCamelCase__				(		self		:List[str]						, __magic_name__		:KT						, __magic_name__		:VT							):







								'''simple docstring'''







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

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

									a									=				Node(__magic_name__						, __magic_name__							)

									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(__magic_name__							)
										else:
											a									=				new_node





							def  lowerCamelCase__				(		self		:Dict						, __magic_name__		:VT							):







								'''simple docstring'''







								a							,					a									=				self._locate_node(__magic_name__							)

								if node is not None:
									return node.value

								return None







def 						__A						(      ) ->			Tuple:
	a									=				SkipList()
	skip_list.insert("""Key1"""				,     3       )
	skip_list.insert("""Key2"""				,     12       )
	skip_list.insert("""Key3"""				,     41       )
	skip_list.insert("""Key4"""				,     -19       )

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

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





def 						__A						(      ) ->			Tuple:
	a									=				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       )

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

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





def 						__A						(      ) ->			Optional[int]:
	a									=				SkipList()
	assert skip_list.find("""Some key"""       ) is None





def 						__A						(      ) ->			Optional[int]:
	a									=				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						(      ) ->			str:
	a									=				SkipList()
	skip_list.delete("""Some key"""       )

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





def 						__A						(      ) ->			int:
	a									=				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						(      ) ->			Union[str, Any]:
	a									=				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:
	a									=				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(__lowerCamelCase       ):
		yield node.key
		for forward_node in node.forward:
			yield from traverse_keys(__lowerCamelCase       )

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





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

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





def 						__A						(      ) ->			Optional[Any]:
	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						(      ) ->			Optional[int]:
	a									=				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(__lowerCamelCase       )


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		main()

