





import inspect
import tempfile
from collections import OrderedDict, UserDict
from collections.abc import MutableMapping
from contextlib import ExitStack, contextmanager
from dataclasses import fields
from enum import Enum
from typing import Any, ContextManager, List, Tuple

import numpy as np

from .import_utils import is_flax_available, is_tf_available, is_torch_available, is_torch_fx_proxy


if is_flax_available():
    import jax.numpy as jnp



class       A__     ( __snake_case    ):

      '''simple docstring'''





      def __get__(				self ,							A_ ,							A_=None     ):
       '''simple docstring'''




       if obj is None:
        return self
       if self.fget is None:
        raise AttributeError("unreadable attribute"     )
       UpperCamelCase			:      Tuple 			=     "__cached_" + self.fget.__name__
       UpperCamelCase			:      Optional[Any] 			=     getattr(A_ ,							A_ ,							A_     )
       if cached is None:
        UpperCamelCase			:      List[str] 			=     self.fget(A_     )
        setattr(A_ ,							A_ ,							A_     )
       return cached



def 	A_       (  _lowerCAmelCase  )		->				List[Any]:
 UpperCamelCase			:      Optional[int] 			=     val.lower()
 if val in {"y", "yes", "t", "true", "on", "1"}:
  return 1
 if val in {"n", "no", "f", "false", "off", "0"}:
  return 0
 raise ValueError(F"""invalid truth value {val!r}"""  )



def 	A_       (  _lowerCAmelCase  )		->				Dict:
 if is_torch_fx_proxy(_lowerCAmelCase  ):
  return True
 if is_torch_available():
  import torch

  if isinstance(_lowerCAmelCase							,     torch.Tensor  ):
   return True
 if is_tf_available():
  import tensorflow as tf

  if isinstance(_lowerCAmelCase							,     tf.Tensor  ):
   return True

 if is_flax_available():
  import jax.numpy as jnp
  from jax.core import Tracer

  if isinstance(_lowerCAmelCase							,     (jnp.ndarray, Tracer)  ):
   return True

 return isinstance(_lowerCAmelCase							,     np.ndarray  )



def 	A_       (  _lowerCAmelCase  )		->				Tuple:
 return isinstance(_lowerCAmelCase							,     np.ndarray  )



def 	A_       (  _lowerCAmelCase  )		->				Tuple:
 return _is_numpy(_lowerCAmelCase  )



def 	A_       (  _lowerCAmelCase  )		->				Any:
 import torch

 return isinstance(_lowerCAmelCase							,     torch.Tensor  )



def 	A_       (  _lowerCAmelCase  )		->				Tuple:
 return False if not is_torch_available() else _is_torch(_lowerCAmelCase  )



def 	A_       (  _lowerCAmelCase  )		->				Optional[int]:
 import torch

 return isinstance(_lowerCAmelCase							,     torch.device  )



def 	A_       (  _lowerCAmelCase  )		->				Any:
 return False if not is_torch_available() else _is_torch_device(_lowerCAmelCase  )



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

 if isinstance(_lowerCAmelCase							,     _lowerCAmelCase  ):
  if hasattr(_lowerCAmelCase							,     _lowerCAmelCase  ):
   UpperCamelCase			:      str 			=     getattr(_lowerCAmelCase							,     _lowerCAmelCase  )
  else:
   return False
 return isinstance(_lowerCAmelCase							,     torch.dtype  )



def 	A_       (  _lowerCAmelCase  )		->				str:
 return False if not is_torch_available() else _is_torch_dtype(_lowerCAmelCase  )



def 	A_       (  _lowerCAmelCase  )		->				str:
 import tensorflow as tf

 return isinstance(_lowerCAmelCase							,     tf.Tensor  )



def 	A_       (  _lowerCAmelCase  )		->				Optional[int]:
 return False if not is_tf_available() else _is_tensorflow(_lowerCAmelCase  )



def 	A_       (  _lowerCAmelCase  )		->				Optional[int]:
 import tensorflow as tf

 # the `is_symbolic_tensor` predicate is only available starting with TF 2.14
 if hasattr(_lowerCAmelCase							,     "is_symbolic_tensor"  ):
  return tf.is_symbolic_tensor(_lowerCAmelCase  )
 return type(_lowerCAmelCase  ) == tf.Tensor



def 	A_       (  _lowerCAmelCase  )		->				List[str]:
 return False if not is_tf_available() else _is_tf_symbolic_tensor(_lowerCAmelCase  )



def 	A_       (  _lowerCAmelCase  )		->				List[str]:
 import jax.numpy as jnp  # noqa: F811

 return isinstance(_lowerCAmelCase							,     jnp.ndarray  )



def 	A_       (  _lowerCAmelCase  )		->				Union[str, Any]:
 return False if not is_flax_available() else _is_jax(_lowerCAmelCase  )



def 	A_       (  _lowerCAmelCase  )		->				Optional[int]:
 if isinstance(_lowerCAmelCase							,     (dict, UserDict)  ):
  return {k: to_py_obj(_lowerCAmelCase  ) for k, v in obj.items()}
 elif isinstance(_lowerCAmelCase							,     (list, tuple)  ):
  return [to_py_obj(_lowerCAmelCase  ) for o in obj]
 elif is_tf_tensor(_lowerCAmelCase  ):
  return obj.numpy().tolist()
 elif is_torch_tensor(_lowerCAmelCase  ):
  return obj.detach().cpu().tolist()
 elif is_jax_tensor(_lowerCAmelCase  ):
  return np.asarray(_lowerCAmelCase  ).tolist()
 elif isinstance(_lowerCAmelCase							,     (np.ndarray, np.number)  ):  # tolist also works on 0d np arrays
  return obj.tolist()
 else:
  return obj



def 	A_       (  _lowerCAmelCase  )		->				Dict:
 if isinstance(_lowerCAmelCase							,     (dict, UserDict)  ):
  return {k: to_numpy(_lowerCAmelCase  ) for k, v in obj.items()}
 elif isinstance(_lowerCAmelCase							,     (list, tuple)  ):
  return np.array(_lowerCAmelCase  )
 elif is_tf_tensor(_lowerCAmelCase  ):
  return obj.numpy()
 elif is_torch_tensor(_lowerCAmelCase  ):
  return obj.detach().cpu().numpy()
 elif is_jax_tensor(_lowerCAmelCase  ):
  return np.asarray(_lowerCAmelCase  )
 else:
  return obj



class       A__     ( __snake_case    ):

      '''simple docstring'''





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




       UpperCamelCase			:      List[Any] 			=     fields(self     )

       # Safety and consistency checks
       if not len(A_     ):
        raise ValueError(F"""{self.__class__.__name__} has no fields."""     )
       if not all(field.default is None for field in class_fields[1:]     ):
        raise ValueError(F"""{self.__class__.__name__} should not have more than one required field."""     )

       UpperCamelCase			:      Any 			=     getattr(self ,							class_fields[0].name     )
       UpperCamelCase			:      Union[str, Any] 			=     all(getattr(self ,							field.name     ) is None for field in class_fields[1:]     )

       if other_fields_are_none and not is_tensor(A_     ):
        if isinstance(A_ ,							A_     ):
         UpperCamelCase			:      str 			=     first_field.items()
         UpperCamelCase			:      Dict 			=     True
        else:
         try:
          UpperCamelCase			:      Optional[int] 			=     iter(A_     )
          UpperCamelCase			:      int 			=     True
         except TypeError:
          UpperCamelCase			:      Optional[int] 			=     False

            # if we provided an iterator as first field and the iterator is a (key, value) iterator
            # set the associated fields
        if first_field_iterator:
         for idx, element in enumerate(A_     ):
          if (
              not isinstance(A_ ,							(list, tuple)     )
              or not len(A_     ) == 2
              or not isinstance(element[0] ,							A_     )
          ):
           if idx == 0:
            # If we do not have an iterator of key/values, set it as attribute
            UpperCamelCase			:      Dict 			=     first_field
           else:
            # If we have a mixed iterator, raise an error
            raise ValueError(
                F"""Cannot set key/value for {element}. It needs to be a tuple (key, value)."""     )
           break
          setattr(self ,							element[0] ,							element[1]     )
          if element[1] is not None:
           UpperCamelCase			:      str 			=     element[1]
        elif first_field is not None:
         UpperCamelCase			:      Optional[Any] 			=     first_field
       else:
        for field in class_fields:
         UpperCamelCase			:      Optional[Any] 			=     getattr(self ,							field.name     )
         if v is not None:
          UpperCamelCase			:      Dict 			=     v





      def __delitem__(				self ,							*A_ ,							**A_     ):
       '''simple docstring'''




       raise Exception(F"""You cannot use ``__delitem__`` on a {self.__class__.__name__} instance."""     )





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




       raise Exception(F"""You cannot use ``setdefault`` on a {self.__class__.__name__} instance."""     )





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




       raise Exception(F"""You cannot use ``pop`` on a {self.__class__.__name__} instance."""     )





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




       raise Exception(F"""You cannot use ``update`` on a {self.__class__.__name__} instance."""     )





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




       if isinstance(A_ ,							A_     ):
        UpperCamelCase			:      List[Any] 			=     dict(self.items()     )
        return inner_dict[k]
       else:
        return self.to_tuple()[k]





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




       if name in self.keys() and value is not None:
        # Don't call self.__setitem__ to avoid recursion errors
        super().__setitem__(A_ ,							A_     )
       super().__setattr__(A_ ,							A_     )





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




       super().__setitem__(A_ ,							A_     )
       # Don't call self.__setattr__ to avoid recursion errors
       super().__setattr__(A_ ,							A_     )





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




       return tuple(self[k] for k in self.keys()     )



class       A__     ( __snake_case ,     __snake_case    ):

      '''simple docstring'''





      @classmethod
      def  __UpperCamelCase(				cls ,							A_     ):
       '''simple docstring'''




       raise ValueError(
           F"""{value} is not a valid {cls.__name__}, please select one of {list(cls._valueamember_map_.keys()     )}"""     )



class       A__     ( __snake_case    ):

      '''simple docstring'''





      _UpperCAmelCase			:str							=     'longest'
      _UpperCAmelCase			:Any							=     'max_length'
      _UpperCAmelCase			:str							=     'do_not_pad'



class       A__     ( __snake_case    ):

      '''simple docstring'''





      _UpperCAmelCase			:Dict							=     'pt'
      _UpperCAmelCase			:List[Any]							=     'tf'
      _UpperCAmelCase			:List[str]							=     'np'
      _UpperCAmelCase			:List[Any]							=     'jax'



class       A__     :

      '''simple docstring'''





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




       UpperCamelCase			:      Union[str, Any] 			=     context_managers
       UpperCamelCase			:      List[str] 			=     ExitStack()





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




       for context_manager in self.context_managers:
        self.stack.enter_context(A_     )





      def __exit__(				self ,							*A_ ,							**A_     ):
       '''simple docstring'''




       self.stack.__exit__(*A_ ,							**A_     )



def 	A_       (  _lowerCAmelCase  )		->				List[Any]:
 UpperCamelCase			:      Optional[Any] 			=     infer_framework(_lowerCAmelCase  )
 if framework == "tf":
  UpperCamelCase			:      List[str] 			=     inspect.signature(model_class.call  )  # TensorFlow models
 elif framework == "pt":
  UpperCamelCase			:      Union[str, Any] 			=     inspect.signature(model_class.forward  )  # PyTorch models
 else:
  UpperCamelCase			:      Tuple 			=     inspect.signature(model_class.__call__  )  # Flax models

 for p in signature.parameters:
  if p == "return_loss" and signature.parameters[p].default is True:
   return True

 return False



def 	A_       (  _lowerCAmelCase  )		->				int:
 UpperCamelCase			:      Dict 			=     model_class.__name__
 UpperCamelCase			:      int 			=     infer_framework(_lowerCAmelCase  )
 if framework == "tf":
  UpperCamelCase			:      int 			=     inspect.signature(model_class.call  )  # TensorFlow models
 elif framework == "pt":
  UpperCamelCase			:      str 			=     inspect.signature(model_class.forward  )  # PyTorch models
 else:
  UpperCamelCase			:      Tuple 			=     inspect.signature(model_class.__call__  )  # Flax models

 if "QuestionAnswering" in model_name:
  return [p for p in signature.parameters if "label" in p or p in ("start_positions", "end_positions")]
 else:
  return [p for p in signature.parameters if "label" in p]



def 	A_       (  _lowerCAmelCase							,     _lowerCAmelCase = ""							,     _lowerCAmelCase = "."  )		->				Optional[int]:

 def _flatten_dict(_lowerCAmelCase							,     _lowerCAmelCase=""							,     _lowerCAmelCase="."  ):
  for k, v in d.items():
   UpperCamelCase			:      List[Any] 			=     str(_lowerCAmelCase  ) + delimiter + str(_lowerCAmelCase  ) if parent_key else k
   if v and isinstance(_lowerCAmelCase							,     _lowerCAmelCase  ):
    yield from flatten_dict(_lowerCAmelCase							,     _lowerCAmelCase							,     delimiter=_lowerCAmelCase  ).items()
   else:
    yield key, v

 return dict(_flatten_dict(_lowerCAmelCase							,     _lowerCAmelCase							,     _lowerCAmelCase  )  )



@contextmanager
def 	A_       (  _lowerCAmelCase							,     _lowerCAmelCase = False  )		->				List[Any]:
 if use_temp_dir:
  with tempfile.TemporaryDirectory() as tmp_dir:
   yield tmp_dir
 else:
  yield working_dir



def 	A_       (  _lowerCAmelCase							,     _lowerCAmelCase=None  )		->				Union[str, Any]:
 if is_numpy_array(_lowerCAmelCase  ):
  return np.transpose(_lowerCAmelCase							,     axes=_lowerCAmelCase  )
 elif is_torch_tensor(_lowerCAmelCase  ):
  return array.T if axes is None else array.permute(*_lowerCAmelCase  )
 elif is_tf_tensor(_lowerCAmelCase  ):
  import tensorflow as tf

  return tf.transpose(_lowerCAmelCase							,     perm=_lowerCAmelCase  )
 elif is_jax_tensor(_lowerCAmelCase  ):
  return jnp.transpose(_lowerCAmelCase							,     axes=_lowerCAmelCase  )
 else:
  raise ValueError(F"""Type not supported for transpose: {type(_lowerCAmelCase  )}."""  )



def 	A_       (  _lowerCAmelCase							,     _lowerCAmelCase  )		->				Any:
 if is_numpy_array(_lowerCAmelCase  ):
  return np.reshape(_lowerCAmelCase							,     _lowerCAmelCase  )
 elif is_torch_tensor(_lowerCAmelCase  ):
  return array.reshape(*_lowerCAmelCase  )
 elif is_tf_tensor(_lowerCAmelCase  ):
  import tensorflow as tf

  return tf.reshape(_lowerCAmelCase							,     _lowerCAmelCase  )
 elif is_jax_tensor(_lowerCAmelCase  ):
  return jnp.reshape(_lowerCAmelCase							,     _lowerCAmelCase  )
 else:
  raise ValueError(F"""Type not supported for reshape: {type(_lowerCAmelCase  )}."""  )



def 	A_       (  _lowerCAmelCase							,     _lowerCAmelCase=None  )		->				str:
 if is_numpy_array(_lowerCAmelCase  ):
  return np.squeeze(_lowerCAmelCase							,     axis=_lowerCAmelCase  )
 elif is_torch_tensor(_lowerCAmelCase  ):
  return array.squeeze() if axis is None else array.squeeze(dim=_lowerCAmelCase  )
 elif is_tf_tensor(_lowerCAmelCase  ):
  import tensorflow as tf

  return tf.squeeze(_lowerCAmelCase							,     axis=_lowerCAmelCase  )
 elif is_jax_tensor(_lowerCAmelCase  ):
  return jnp.squeeze(_lowerCAmelCase							,     axis=_lowerCAmelCase  )
 else:
  raise ValueError(F"""Type not supported for squeeze: {type(_lowerCAmelCase  )}."""  )



def 	A_       (  _lowerCAmelCase							,     _lowerCAmelCase  )		->				Any:
 if is_numpy_array(_lowerCAmelCase  ):
  return np.expand_dims(_lowerCAmelCase							,     _lowerCAmelCase  )
 elif is_torch_tensor(_lowerCAmelCase  ):
  return array.unsqueeze(dim=_lowerCAmelCase  )
 elif is_tf_tensor(_lowerCAmelCase  ):
  import tensorflow as tf

  return tf.expand_dims(_lowerCAmelCase							,     axis=_lowerCAmelCase  )
 elif is_jax_tensor(_lowerCAmelCase  ):
  return jnp.expand_dims(_lowerCAmelCase							,     axis=_lowerCAmelCase  )
 else:
  raise ValueError(F"""Type not supported for expand_dims: {type(_lowerCAmelCase  )}."""  )



def 	A_       (  _lowerCAmelCase  )		->				List[str]:
 if is_numpy_array(_lowerCAmelCase  ):
  return np.size(_lowerCAmelCase  )
 elif is_torch_tensor(_lowerCAmelCase  ):
  return array.numel()
 elif is_tf_tensor(_lowerCAmelCase  ):
  import tensorflow as tf

  return tf.size(_lowerCAmelCase  )
 elif is_jax_tensor(_lowerCAmelCase  ):
  return array.size
 else:
  raise ValueError(F"""Type not supported for expand_dims: {type(_lowerCAmelCase  )}."""  )



def 	A_       (  _lowerCAmelCase							,     _lowerCAmelCase  )		->				Any:
 for key, value in auto_map.items():
  if isinstance(_lowerCAmelCase							,     (tuple, list)  ):
   UpperCamelCase			:      Any 			=     [F"""{repo_id}--{v}""" if (v is not None and "--" not in v) else v for v in value]
  elif value is not None and "--" not in value:
   UpperCamelCase			:      List[Any] 			=     F"""{repo_id}--{value}"""

 return auto_map



def 	A_       (  _lowerCAmelCase  )		->				int:
 for base_class in inspect.getmro(_lowerCAmelCase  ):
  UpperCamelCase			:      List[str] 			=     base_class.__module__
  UpperCamelCase			:      Any 			=     base_class.__name__
  if module.startswith("tensorflow"  ) or module.startswith("keras"  ) or name == "TFPreTrainedModel":
   return "tf"
  elif module.startswith("torch"  ) or name == "PreTrainedModel":
   return "pt"
  elif module.startswith("flax"  ) or module.startswith("jax"  ) or name == "FlaxPreTrainedModel":
   return "flax"
 else:
  raise TypeError(F"""Could not infer framework from class {model_class}."""  )







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