





import argparse
import json
from pathlib import Path

import torch
import torchaudio
from datasets import load_dataset
from huggingface_hub import hf_hub_download

from transformers import ASTConfig, ASTFeatureExtractor, ASTForAudioClassification
from transformers.utils import logging


logging.set_verbosity_info()
__lowerCamelCase :  str										=  logging.get_logger(__name__)



def 	A_       (  _lowerCAmelCase  )		->				List[Any]:
 UpperCamelCase			:      Optional[int] 			=     ASTConfig()

 if "10-10" in model_name:
  pass
 elif "speech-commands" in model_name:
  UpperCamelCase			:      str 			=     128
 elif "12-12" in model_name:
  UpperCamelCase			:      Union[str, Any] 			=     12
  UpperCamelCase			:      Optional[int] 			=     12
 elif "14-14" in model_name:
  UpperCamelCase			:      Optional[Any] 			=     14
  UpperCamelCase			:      int 			=     14
 elif "16-16" in model_name:
  UpperCamelCase			:      Optional[Any] 			=     16
  UpperCamelCase			:      str 			=     16
 else:
  raise ValueError("Model not supported"  )

 UpperCamelCase			:      List[Any] 			=     """huggingface/label-files"""
 if "speech-commands" in model_name:
  UpperCamelCase			:      Tuple 			=     35
  UpperCamelCase			:      List[Any] 			=     """speech-commands-v2-id2label.json"""
 else:
  UpperCamelCase			:      Optional[int] 			=     527
  UpperCamelCase			:      Tuple 			=     """audioset-id2label.json"""

 UpperCamelCase			:      int 			=     json.load(open(hf_hub_download(lowerCamelCase_							,     lowerCamelCase_							,     repo_type="dataset"  )							,     "r"  )  )
 UpperCamelCase			:      int 			=     {int(lowerCamelCase_  ): v for k, v in idalabel.items()}
 UpperCamelCase			:      Optional[Any] 			=     idalabel
 UpperCamelCase			:      Union[str, Any] 			=     {v: k for k, v in idalabel.items()}

 return config



def 	A_       (  _lowerCAmelCase  )		->				Union[str, Any]:



 if "module.v" in name:
  UpperCamelCase			:      Tuple 			=     name.replace("module.v"							,     "audio_spectrogram_transformer"  )
 if "cls_token" in name:
  UpperCamelCase			:      Optional[int] 			=     name.replace("cls_token"							,     "embeddings.cls_token"  )
 if "dist_token" in name:
  UpperCamelCase			:      List[str] 			=     name.replace("dist_token"							,     "embeddings.distillation_token"  )
 if "pos_embed" in name:
  UpperCamelCase			:      Optional[Any] 			=     name.replace("pos_embed"							,     "embeddings.position_embeddings"  )
 if "patch_embed.proj" in name:
  UpperCamelCase			:      int 			=     name.replace("patch_embed.proj"							,     "embeddings.patch_embeddings.projection"  )
 # transformer blocks
 if "blocks" in name:
  UpperCamelCase			:      int 			=     name.replace("blocks"							,     "encoder.layer"  )
 if "attn.proj" in name:
  UpperCamelCase			:      Tuple 			=     name.replace("attn.proj"							,     "attention.output.dense"  )
 if "attn" in name:
  UpperCamelCase			:      Optional[Any] 			=     name.replace("attn"							,     "attention.self"  )
 if "norm1" in name:
  UpperCamelCase			:      Union[str, Any] 			=     name.replace("norm1"							,     "layernorm_before"  )
 if "norm2" in name:
  UpperCamelCase			:      Dict 			=     name.replace("norm2"							,     "layernorm_after"  )
 if "mlp.fc1" in name:
  UpperCamelCase			:      Tuple 			=     name.replace("mlp.fc1"							,     "intermediate.dense"  )
 if "mlp.fc2" in name:
  UpperCamelCase			:      List[Any] 			=     name.replace("mlp.fc2"							,     "output.dense"  )
 # final layernorm
 if "audio_spectrogram_transformer.norm" in name:
  UpperCamelCase			:      Dict 			=     name.replace("audio_spectrogram_transformer.norm"							,     "audio_spectrogram_transformer.layernorm"  )
 # classifier head
 if "module.mlp_head.0" in name:
  UpperCamelCase			:      Optional[int] 			=     name.replace("module.mlp_head.0"							,     "classifier.layernorm"  )
 if "module.mlp_head.1" in name:
  UpperCamelCase			:      Dict 			=     name.replace("module.mlp_head.1"							,     "classifier.dense"  )

 return name



def 	A_       (  _lowerCAmelCase							,     _lowerCAmelCase  )		->				List[Any]:



 for key in orig_state_dict.copy().keys():
  UpperCamelCase			:      Tuple 			=     orig_state_dict.pop(lowerCamelCase_  )

  if "qkv" in key:
   UpperCamelCase			:      int 			=     key.split("."  )
   UpperCamelCase			:      int 			=     int(key_split[3]  )
   UpperCamelCase			:      int 			=     config.hidden_size
   if "weight" in key:
    UpperCamelCase			:      List[str] 			=     val[:dim, :]
    UpperCamelCase			:      Optional[Any] 			=     val[dim : dim * 2, :]
    UpperCamelCase			:      List[str] 			=     val[-dim:, :]
   else:
    UpperCamelCase			:      Dict 			=     val[:dim]
    UpperCamelCase			:      List[str] 			=     val[dim : dim * 2]
    UpperCamelCase			:      List[Any] 			=     val[-dim:]
  else:
   UpperCamelCase			:      Optional[int] 			=     val

 return orig_state_dict



def 	A_       (  _lowerCAmelCase  )		->				Union[str, Any]:
 UpperCamelCase			:      Optional[Any] 			=     [
     """module.v.head.weight""",
     """module.v.head.bias""",
     """module.v.head_dist.weight""",
     """module.v.head_dist.bias""",
 ]
 for k in ignore_keys:
  state_dict.pop(lowerCamelCase_							,     lowerCamelCase_  )



@torch.no_grad()
def 	A_       (  _lowerCAmelCase							,     _lowerCAmelCase							,     _lowerCAmelCase=False  )		->				Dict:
 UpperCamelCase			:      int 			=     get_audio_spectrogram_transformer_config(lowerCamelCase_  )

 UpperCamelCase			:      Optional[int] 			=     {
     """ast-finetuned-audioset-10-10-0.4593""": (
         """https://www.dropbox.com/s/ca0b1v2nlxzyeb4/audioset_10_10_0.4593.pth?dl=1"""
     ),
     """ast-finetuned-audioset-10-10-0.450""": (
         """https://www.dropbox.com/s/1tv0hovue1bxupk/audioset_10_10_0.4495.pth?dl=1"""
     ),
     """ast-finetuned-audioset-10-10-0.448""": (
         """https://www.dropbox.com/s/6u5sikl4b9wo4u5/audioset_10_10_0.4483.pth?dl=1"""
     ),
     """ast-finetuned-audioset-10-10-0.448-v2""": (
         """https://www.dropbox.com/s/kt6i0v9fvfm1mbq/audioset_10_10_0.4475.pth?dl=1"""
     ),
     """ast-finetuned-audioset-12-12-0.447""": (
         """https://www.dropbox.com/s/snfhx3tizr4nuc8/audioset_12_12_0.4467.pth?dl=1"""
     ),
     """ast-finetuned-audioset-14-14-0.443""": (
         """https://www.dropbox.com/s/z18s6pemtnxm4k7/audioset_14_14_0.4431.pth?dl=1"""
     ),
     """ast-finetuned-audioset-16-16-0.442""": (
         """https://www.dropbox.com/s/mdsa4t1xmcimia6/audioset_16_16_0.4422.pth?dl=1"""
     ),
     """ast-finetuned-speech-commands-v2""": (
         """https://www.dropbox.com/s/q0tbqpwv44pquwy/speechcommands_10_10_0.9812.pth?dl=1"""
     ),
 }

 # load original state_dict
 UpperCamelCase			:      Dict 			=     model_name_to_url[model_name]
 UpperCamelCase			:      str 			=     torch.hub.load_state_dict_from_url(lowerCamelCase_							,     map_location="cpu"  )
 # remove some keys
 remove_keys(lowerCamelCase_  )
 # rename some keys
 UpperCamelCase			:      Optional[Any] 			=     convert_state_dict(lowerCamelCase_							,     lowerCamelCase_  )

 # load 🤗 model
 UpperCamelCase			:      List[str] 			=     ASTForAudioClassification(lowerCamelCase_  )
 model.eval()

 model.load_state_dict(lowerCamelCase_  )

 # verify outputs on dummy input
 # source: https://github.com/YuanGongND/ast/blob/79e873b8a54d0a3b330dd522584ff2b9926cd581/src/run.py#L62
 UpperCamelCase			:      List[Any] 			=     -4.2_677_393 if """speech-commands""" not in model_name else -6.845_978
 UpperCamelCase			:      List[str] 			=     4.5_689_974 if """speech-commands""" not in model_name else 5.5_654_526
 UpperCamelCase			:      Union[str, Any] 			=     1024 if """speech-commands""" not in model_name else 128
 UpperCamelCase			:      Tuple 			=     ASTFeatureExtractor(mean=lowerCamelCase_							,     std=lowerCamelCase_							,     max_length=lowerCamelCase_  )

 if "speech-commands" in model_name:
  UpperCamelCase			:      Dict 			=     load_dataset("speech_commands"							,     "v0.02"							,     split="validation"  )
  UpperCamelCase			:      Tuple 			=     dataset[0]["""audio"""]["""array"""]
 else:
  UpperCamelCase			:      Optional[Any] 			=     hf_hub_download(
      repo_id="nielsr/audio-spectogram-transformer-checkpoint"							,     filename="sample_audio.flac"							,     repo_type="dataset"							,     )

  UpperCamelCase			:      Any 			=     torchaudio.load(lowerCamelCase_  )
  UpperCamelCase			:      Optional[Any] 			=     waveform.squeeze().numpy()

 UpperCamelCase			:      Dict 			=     feature_extractor(lowerCamelCase_							,     sampling_rate=1_6000							,     return_tensors="pt"  )

 # forward pass
 UpperCamelCase			:      Any 			=     model(**lowerCamelCase_  )
 UpperCamelCase			:      List[str] 			=     outputs.logits

 if model_name == "ast-finetuned-audioset-10-10-0.4593":
  UpperCamelCase			:      Optional[int] 			=     torch.tensor([-0.8_760, -7.0_042, -8.6_602]  )
 elif model_name == "ast-finetuned-audioset-10-10-0.450":
  UpperCamelCase			:      List[str] 			=     torch.tensor([-1.1_986, -7.0_903, -8.2_718]  )
 elif model_name == "ast-finetuned-audioset-10-10-0.448":
  UpperCamelCase			:      Union[str, Any] 			=     torch.tensor([-2.6_128, -8.0_080, -9.4_344]  )
 elif model_name == "ast-finetuned-audioset-10-10-0.448-v2":
  UpperCamelCase			:      Union[str, Any] 			=     torch.tensor([-1.5_080, -7.4_534, -8.8_917]  )
 elif model_name == "ast-finetuned-audioset-12-12-0.447":
  UpperCamelCase			:      Any 			=     torch.tensor([-0.5_050, -6.5_833, -8.0_843]  )
 elif model_name == "ast-finetuned-audioset-14-14-0.443":
  UpperCamelCase			:      List[str] 			=     torch.tensor([-0.3_826, -7.0_336, -8.2_413]  )
 elif model_name == "ast-finetuned-audioset-16-16-0.442":
  UpperCamelCase			:      int 			=     torch.tensor([-1.2_113, -6.9_101, -8.3_470]  )
 elif model_name == "ast-finetuned-speech-commands-v2":
  UpperCamelCase			:      int 			=     torch.tensor([6.1_589, -8.0_566, -8.7_984]  )
 else:
  raise ValueError("Unknown model name"  )
 if not torch.allclose(logits[0, :3]							,     lowerCamelCase_							,     atol=1e-4  ):
  raise ValueError("Logits don't match"  )
 print("Looks ok!"  )

 if pytorch_dump_folder_path is not None:
  Path(lowerCamelCase_  ).mkdir(exist_ok=lowerCamelCase_  )
  print(F"""Saving model {model_name} to {pytorch_dump_folder_path}"""  )
  model.save_pretrained(lowerCamelCase_  )
  print(F"""Saving feature extractor to {pytorch_dump_folder_path}"""  )
  feature_extractor.save_pretrained(lowerCamelCase_  )

 if push_to_hub:
  print("Pushing model and feature extractor to the hub..."  )
  model.push_to_hub(F"""MIT/{model_name}"""  )
  feature_extractor.push_to_hub(F"""MIT/{model_name}"""  )


if __name__ == "__main__":
    __lowerCamelCase :  int										=  argparse.ArgumentParser()
    # Required parameters
    parser.add_argument(
        """--model_name""",
        default="""ast-finetuned-audioset-10-10-0.4593""",
        type=str,
        help="""Name of the Audio Spectrogram Transformer model you'd like to convert.""",
    )
    parser.add_argument(
        """--pytorch_dump_folder_path""", default=None, type=str, help="""Path to the output PyTorch model directory."""
    )
    parser.add_argument(
        """--push_to_hub""", action="""store_true""", help="""Whether or not to push the converted model to the 🤗 hub."""
    )

    __lowerCamelCase :  Union[str, Any]										=  parser.parse_args()
    convert_audio_spectrogram_transformer_checkpoint(args.model_name, args.pytorch_dump_folder_path, args.push_to_hub)







from __future__ import annotations

from random import random
from typing import Generic, TypeVar

__lowerCamelCase :  Dict										=  TypeVar("""KT""")
__lowerCamelCase :  Dict										=  TypeVar("""VT""")



class       A__     ( Generic[KT, VT]    ):





      def __init__(				self ,							A_ = "root" ,							A_ = None     ):
       '''simple docstring'''




       UpperCamelCase			:      int 			=     key
       UpperCamelCase			:      List[Any] 			=     value
       UpperCamelCase			:      list[Node[KT, VT]] 			=     []





      def __repr__(				self     ):
       '''simple docstring'''




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





      @property
      def  __UpperCamelCase(				self     ):
       '''simple docstring'''




       return len(self.forward     )



class       A__     ( Generic[KT, VT]    ):





      def __init__(				self ,							A_ = 0.5 ,							A_ = 16     ):
       '''simple docstring'''




       UpperCamelCase			:      Node[KT, VT] 			=     Node[KT, VT]()
       UpperCamelCase			:      List[Any] 			=     0
       UpperCamelCase			:      Union[str, Any] 			=     p
       UpperCamelCase			:      List[str] 			=     max_level





      def __str__(				self     ):
       '''simple docstring'''




       UpperCamelCase			:      int 			=     list(self     )

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

       UpperCamelCase			:      str 			=     max((len(str(A_     )     ) for item in items) ,							default=4     )
       UpperCamelCase			:      Dict 			=     max(A_ ,							4     ) + 4

       UpperCamelCase			:      str 			=     self.head
       UpperCamelCase			:      List[Any] 			=     []

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

       while len(node.forward     ) != 0:
        UpperCamelCase			:      Union[str, Any] 			=     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_     )     )
        UpperCamelCase			:      Tuple 			=     node.forward

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





      def __iter__(				self     ):
       '''simple docstring'''




       UpperCamelCase			:      Union[str, Any] 			=     self.head

       while len(node.forward     ) != 0:
        yield node.forward[0].key
        UpperCamelCase			:      Union[str, Any] 			=     node.forward[0]





      def  __UpperCamelCase(				self     ):
       '''simple docstring'''




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

       return level





      def  __UpperCamelCase(				self ,							A_     ):
       '''simple docstring'''




       UpperCamelCase			:      List[str] 			=     []

       UpperCamelCase			:      List[Any] 			=     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			:      str 			=     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  __UpperCamelCase(				self ,							A_     ):
       '''simple docstring'''




       UpperCamelCase			,					UpperCamelCase			:      str 			=     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:
           UpperCamelCase			:      Tuple 			=     node.forward[i]
          else:
           UpperCamelCase			:      List[Any] 			=     update_node.forward[:i]





      def  __UpperCamelCase(				self ,							A_ ,							A_     ):
       '''simple docstring'''




       UpperCamelCase			,					UpperCamelCase			:      Optional[int] 			=     self._locate_node(A_     )
       if node is not None:
        UpperCamelCase			:      Union[str, Any] 			=     value
       else:
        UpperCamelCase			:      Dict 			=     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     )
         UpperCamelCase			:      Optional[int] 			=     level

        UpperCamelCase			:      Dict 			=     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:
          UpperCamelCase			:      List[Any] 			=     new_node





      def  __UpperCamelCase(				self ,							A_     ):
       '''simple docstring'''




       UpperCamelCase			,					UpperCamelCase			:      Union[str, Any] 			=     self._locate_node(A_     )

       if node is not None:
        return node.value

       return None



def 	A_       (  )		->				List[Any]:
 UpperCamelCase			:      int 			=     SkipList()
 skip_list.insert("Key1"							,     3  )
 skip_list.insert("Key2"							,     12  )
 skip_list.insert("Key3"							,     41  )
 skip_list.insert("Key4"							,     -19  )

 UpperCamelCase			:      Optional[int] 			=     skip_list.head
 UpperCamelCase			:      List[str] 			=     {}
 while node.level != 0:
  UpperCamelCase			:      str 			=     node.forward[0]
  UpperCamelCase			:      Optional[int] 			=     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_       (  )		->				List[Any]:
 UpperCamelCase			:      Optional[int] 			=     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			:      Dict 			=     skip_list.head
 UpperCamelCase			:      Tuple 			=     {}
 while node.level != 0:
  UpperCamelCase			:      List[str] 			=     node.forward[0]
  UpperCamelCase			:      Dict 			=     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_       (  )		->				List[Any]:
 UpperCamelCase			:      List[Any] 			=     SkipList()
 assert skip_list.find("Some key"  ) is None



def 	A_       (  )		->				Tuple:
 UpperCamelCase			:      Optional[int] 			=     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_       (  )		->				Dict:
 UpperCamelCase			:      Optional[int] 			=     SkipList()
 skip_list.delete("Some key"  )

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



def 	A_       (  )		->				Dict:
 UpperCamelCase			:      List[Any] 			=     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_       (  )		->				List[str]:
 UpperCamelCase			:      int 			=     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_       (  )		->				List[Any]:
 UpperCamelCase			:      List[Any] 			=     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_       (  )		->				Union[str, Any]:
 def is_sorted(_lowerCAmelCase  ):
  return all(next_item >= item for item, next_item in zip(_lowerCAmelCase							,     lst[1:]  )  )

 UpperCamelCase			:      int 			=     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_       (  )		->				Tuple:
 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_       (  )		->				List[str]:
 UpperCamelCase			:      Optional[int] 			=     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()
