






'''simple docstring'''
import importlib.metadata
import warnings
from copy import deepcopy

from packaging import version

from ..utils import logging
from .import_utils import is_accelerate_available, is_bitsandbytes_available


if is_bitsandbytes_available():
  import bitsandbytes as bnb
  import torch
  import torch.nn as nn

  from ..pytorch_utils import ConvaD

if is_accelerate_available():
  from accelerate import init_empty_weights
  from accelerate.utils import find_tied_parameters

a_					=	logging.get_logger(__name__)





def 	_a(					UpperCamelCase__			:  Union[str, Any],		UpperCamelCase__			:  Optional[Any],		UpperCamelCase__			:  Union[str, Any],		UpperCamelCase__			:  Tuple=None,		UpperCamelCase__			:  List[Any]=None							):




    '''simple docstring'''






    if "." in tensor_name:
        SCREAMING_SNAKE_CASE__       :			Any													=tensor_name.split('''.'''							)
        for split in splits[:-1]:
            SCREAMING_SNAKE_CASE__       :			Dict													=getattr(UpperCamelCase__,		UpperCamelCase__							)
            if new_module is None:
                raise ValueError(f"{module} has no attribute {split}."							)
            SCREAMING_SNAKE_CASE__       :			List[str]													=new_module
        SCREAMING_SNAKE_CASE__       :			Optional[int]													=splits[-1]

    if tensor_name not in module._parameters and tensor_name not in module._buffers:
        raise ValueError(f"{module} does not have a parameter or a buffer named {tensor_name}."							)
    SCREAMING_SNAKE_CASE__       :			List[str]													=tensor_name in module._buffers
    SCREAMING_SNAKE_CASE__       :			int													=getattr(UpperCamelCase__,		UpperCamelCase__							)

    if old_value.device == torch.device('''meta'''							) and device not in ["meta", torch.device('''meta'''							)] and value is None:
        raise ValueError(f"{tensor_name} is on the meta device, we need a `value` to put in on {device}."							)

    SCREAMING_SNAKE_CASE__       :			Optional[Any]													=False
    SCREAMING_SNAKE_CASE__       :			Any													=False
    if is_buffer or not is_bitsandbytes_available():
        SCREAMING_SNAKE_CASE__       :			Dict													=False
        SCREAMING_SNAKE_CASE__       :			Any													=False
    else:
        SCREAMING_SNAKE_CASE__       :			Dict													=hasattr(bnb.nn,		'''Params4bit'''							) and isinstance(module._parameters[tensor_name],		bnb.nn.Paramsabit							)
        SCREAMING_SNAKE_CASE__       :			int													=isinstance(module._parameters[tensor_name],		bnb.nn.IntaParams							)

    if is_abit or is_abit:
        SCREAMING_SNAKE_CASE__       :			Optional[Any]													=module._parameters[tensor_name]
        if param.device.type != "cuda":
            if value is None:
                SCREAMING_SNAKE_CASE__       :			Optional[Any]													=old_value.to(UpperCamelCase__							)
            elif isinstance(UpperCamelCase__,		torch.Tensor							):
                SCREAMING_SNAKE_CASE__       :			Union[str, Any]													=value.to('''cpu'''							)
                if value.dtype == torch.inta:
                    SCREAMING_SNAKE_CASE__       :			str													=version.parse(importlib.metadata.version('''bitsandbytes'''							)							) > version.parse(
                        '''0.37.2'''							)
                    if not is_abit_serializable:
                        raise ValueError(
                            '''Detected int8 weights but the version of bitsandbytes is not compatible with int8 serialization. '''
                            '''Make sure to download the latest `bitsandbytes` version. `pip install --upgrade bitsandbytes`.'''							)
            else:
                SCREAMING_SNAKE_CASE__       :			Union[str, Any]													=torch.tensor(UpperCamelCase__,		device='''cpu'''							)

            # Support models using `Conv1D` in place of `nn.Linear` (e.g. gpt2) by transposing the weight matrix prior to quantization.
            # Since weights are saved in the correct "orientation", we skip transposing when loading.
            if issubclass(module.source_cls,		UpperCamelCase__							) and fpaa_statistics is None:
                SCREAMING_SNAKE_CASE__       :			Union[str, Any]													=new_value.T

            SCREAMING_SNAKE_CASE__       :			List[str]													=old_value.__dict__
            if is_abit:
                SCREAMING_SNAKE_CASE__       :			List[Any]													=bnb.nn.IntaParams(UpperCamelCase__,		requires_grad=UpperCamelCase__,		**UpperCamelCase__							).to(UpperCamelCase__							)
            elif is_abit:
                SCREAMING_SNAKE_CASE__       :			Tuple													=bnb.nn.Paramsabit(UpperCamelCase__,		requires_grad=UpperCamelCase__,		**UpperCamelCase__							).to(UpperCamelCase__							)

            SCREAMING_SNAKE_CASE__       :			List[Any]													=new_value
            if fpaa_statistics is not None:
                setattr(module.weight,		'''SCB''',		fpaa_statistics.to(UpperCamelCase__							)							)

    else:
        if value is None:
            SCREAMING_SNAKE_CASE__       :			int													=old_value.to(UpperCamelCase__							)
        elif isinstance(UpperCamelCase__,		torch.Tensor							):
            SCREAMING_SNAKE_CASE__       :			List[str]													=value.to(UpperCamelCase__							)
        else:
            SCREAMING_SNAKE_CASE__       :			List[Any]													=torch.tensor(UpperCamelCase__,		device=UpperCamelCase__							)

        if is_buffer:
            SCREAMING_SNAKE_CASE__       :			Optional[int]													=new_value
        else:
            SCREAMING_SNAKE_CASE__       :			Optional[Any]													=nn.Parameter(UpperCamelCase__,		requires_grad=old_value.requires_grad							)
            SCREAMING_SNAKE_CASE__       :			Any													=new_value





def 	_a(					UpperCamelCase__			:  Dict,		UpperCamelCase__			:  Dict=None,		UpperCamelCase__			:  Optional[int]=None,		UpperCamelCase__			:  Tuple=None,		UpperCamelCase__			:  Union[str, Any]=False							):




    '''simple docstring'''






    for name, module in model.named_children():
        if current_key_name is None:
            SCREAMING_SNAKE_CASE__       :			int													=[]
        current_key_name.append(UpperCamelCase__							)

        if (isinstance(UpperCamelCase__,		nn.Linear							) or isinstance(UpperCamelCase__,		UpperCamelCase__							)) and name not in modules_to_not_convert:
            # Check if the current key is not in the `modules_to_not_convert`
            if not any(key in '''.'''.join(UpperCamelCase__							) for key in modules_to_not_convert							):
                with init_empty_weights():
                    if isinstance(UpperCamelCase__,		UpperCamelCase__							):
                        SCREAMING_SNAKE_CASE__       :			str													=module.weight.shape
                    else:
                        SCREAMING_SNAKE_CASE__       :			int													=module.in_features
                        SCREAMING_SNAKE_CASE__       :			int													=module.out_features

                    if quantization_config.quantization_method() == "llm_int8":
                        SCREAMING_SNAKE_CASE__       :			Optional[Any]													=bnb.nn.LinearabitLt(
                            UpperCamelCase__,		UpperCamelCase__,		module.bias is not None,		has_fpaa_weights=quantization_config.llm_inta_has_fpaa_weight,		threshold=quantization_config.llm_inta_threshold,		)
                        SCREAMING_SNAKE_CASE__       :			Tuple													=True
                    else:
                        if (
                            quantization_config.llm_inta_skip_modules is not None
                            and name in quantization_config.llm_inta_skip_modules
                        ):
                            pass
                        else:
                            SCREAMING_SNAKE_CASE__       :			Optional[int]													=bnb.nn.Linearabit(
                                UpperCamelCase__,		UpperCamelCase__,		module.bias is not None,		quantization_config.bnb_abit_compute_dtype,		compress_statistics=quantization_config.bnb_abit_use_double_quant,		quant_type=quantization_config.bnb_abit_quant_type,		)
                            SCREAMING_SNAKE_CASE__       :			List[Any]													=True
                    # Store the module class in case we need to transpose the weight later
                    SCREAMING_SNAKE_CASE__       :			Dict													=type(UpperCamelCase__							)
                    # Force requires grad to False to avoid unexpected errors
                    model._modules[name].requires_grad_(UpperCamelCase__							)
        if len(list(module.children()							)							) > 0:
            SCREAMING_SNAKE_CASE__       :			List[Any]													=_replace_with_bnb_linear(
                UpperCamelCase__,		UpperCamelCase__,		UpperCamelCase__,		UpperCamelCase__,		has_been_replaced=UpperCamelCase__,		)
        # Remove the last key for recursion
        current_key_name.pop(-1							)
    return model, has_been_replaced





def 	_a(					UpperCamelCase__			:  Any,		UpperCamelCase__			:  Optional[Any]=None,		UpperCamelCase__			:  Optional[Any]=None,		UpperCamelCase__			:  Dict=None							):




    '''simple docstring'''






    SCREAMING_SNAKE_CASE__       :			List[Any]													=['''lm_head'''] if modules_to_not_convert is None else modules_to_not_convert
    SCREAMING_SNAKE_CASE__       :			Any													=_replace_with_bnb_linear(
        UpperCamelCase__,		UpperCamelCase__,		UpperCamelCase__,		UpperCamelCase__							)

    if not has_been_replaced:
        logger.warning(
            '''You are loading your model in 8bit or 4bit but no linear modules were found in your model.'''
            ''' Please double check your model architecture, or submit an issue on github if you think this is'''
            ''' a bug.'''							)

    return model





def 	_a(					*UpperCamelCase__			:  str,		**UpperCamelCase__			:  List[str]							):




    '''simple docstring'''






    warnings.warn(
        '''`replace_8bit_linear` will be deprecated in a future version, please use `replace_with_bnb_linear` instead''',		UpperCamelCase__,		)
    return replace_with_bnb_linear(*UpperCamelCase__,		**UpperCamelCase__							)





def 	_a(					*UpperCamelCase__			:  str,		**UpperCamelCase__			:  Optional[int]							):




    '''simple docstring'''






    warnings.warn(
        '''`set_module_8bit_tensor_to_device` will be deprecated in a future version, please use `set_module_quantized_tensor_to_device` instead''',		UpperCamelCase__,		)
    return set_module_quantized_tensor_to_device(*UpperCamelCase__,		**UpperCamelCase__							)







def 	_a(					UpperCamelCase__			:  Union[str, Any]							):




    '''simple docstring'''






    SCREAMING_SNAKE_CASE__       :			Optional[int]													=deepcopy(UpperCamelCase__							)  # this has 0 cost since it is done inside `init_empty_weights` context manager`
    tied_model.tie_weights()

    SCREAMING_SNAKE_CASE__       :			Dict													=find_tied_parameters(UpperCamelCase__							)
    # For compatibility with Accelerate < 0.18
    if isinstance(UpperCamelCase__,		UpperCamelCase__							):
        SCREAMING_SNAKE_CASE__       :			Optional[Any]													=sum(list(tied_params.values()							),		[]							) + list(tied_params.keys()							)
    else:
        SCREAMING_SNAKE_CASE__       :			List[str]													=sum(UpperCamelCase__,		[]							)
    SCREAMING_SNAKE_CASE__       :			List[Any]													=len(UpperCamelCase__							) > 0

    # Check if it is a base model
    SCREAMING_SNAKE_CASE__       :			Any													=not hasattr(UpperCamelCase__,		model.base_model_prefix							)

    # Ignore this for base models (BertModel, GPT2Model, etc.)
    if (not has_tied_params) and is_base_model:
        return []

    # otherwise they have an attached head
    SCREAMING_SNAKE_CASE__       :			Union[str, Any]													=list(model.named_children()							)
    SCREAMING_SNAKE_CASE__       :			int													=[list_modules[-1][0]]

    # add last module together with tied weights
    SCREAMING_SNAKE_CASE__       :			int													=set(UpperCamelCase__							) - set(UpperCamelCase__							)
    SCREAMING_SNAKE_CASE__       :			List[Any]													=list(set(UpperCamelCase__							)							) + list(UpperCamelCase__							)

    # remove ".weight" from the keys
    SCREAMING_SNAKE_CASE__       :			Optional[int]													=['''.weight''', '''.bias''']
    SCREAMING_SNAKE_CASE__       :			Optional[int]													=[]
    for name in list_untouched:
        for name_to_remove in names_to_remove:
            if name_to_remove in name:
                SCREAMING_SNAKE_CASE__       :			str													=name.replace(UpperCamelCase__,		''''''							)
        filtered_module_names.append(UpperCamelCase__							)

    return filtered_module_names







'''simple docstring'''
from __future__ import annotations

from random import random
from typing import Generic, TypeVar

a_					=	TypeVar('KT')
a_					=	TypeVar('VT')






class        __SCREAMING_SNAKE_CASE (     Generic[KT, VT]			):




 def __init__( self		:							Dict   , __lowercase		:							KT | str = "root"   , __lowercase		:							VT | None = None )		->  Dict:
       SCREAMING_SNAKE_CASE__       :			Any													=key
       SCREAMING_SNAKE_CASE__       :			Optional[int]													=value
       SCREAMING_SNAKE_CASE__       :			list[Node[KT, VT]]													=[]




 def __repr__( self		:							Any )		->  str:
       return F"Node({self.key}: {self.value})"




 @property
 def        __magic_name__		( self		:							List[Any] )		->  int:
       return len(self.forward )






class        __SCREAMING_SNAKE_CASE (     Generic[KT, VT]			):




 def __init__( self		:							int   , __lowercase		:							float = 0.5   , __lowercase		:							int = 16 )		->  int:
       SCREAMING_SNAKE_CASE__       :			Node[KT, VT]													=Node[KT, VT]()
       SCREAMING_SNAKE_CASE__       :			Any													=0
       SCREAMING_SNAKE_CASE__       :			Dict													=p
       SCREAMING_SNAKE_CASE__       :			Any													=max_level




 def __str__( self		:							Optional[Any] )		->  str:
       SCREAMING_SNAKE_CASE__       :			Union[str, Any]													=list(self )

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

       SCREAMING_SNAKE_CASE__       :			List[str]													=max((len(str(__lowercase ) ) for item in items)   , default=4 )
       SCREAMING_SNAKE_CASE__       :			Any													=max(__lowercase   , 4 ) + 4

       SCREAMING_SNAKE_CASE__       :			Any													=self.head
       SCREAMING_SNAKE_CASE__       :			List[Any]													=[]

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

       while len(node.forward ) != 0:
             SCREAMING_SNAKE_CASE__       :			Optional[Any]													=node.forward[0]

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

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




 def __iter__( self		:							Union[str, Any] )		->  Optional[int]:
       SCREAMING_SNAKE_CASE__       :			List[str]													=self.head

       while len(node.forward ) != 0:
             yield node.forward[0].key
             SCREAMING_SNAKE_CASE__       :			List[Any]													=node.forward[0]




 def        __magic_name__		( self		:							Any )		->  int:
       SCREAMING_SNAKE_CASE__       :			Tuple													=1
       while random() < self.p and level < self.max_level:
             level += 1

       return level




 def        __magic_name__		( self		:							str   , __lowercase		:							List[str] )		->  tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:
       SCREAMING_SNAKE_CASE__       :			Optional[int]													=[]

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

       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        __magic_name__		( self		:							Optional[int]   , __lowercase		:							KT )		->  List[Any]:
       SCREAMING_SNAKE_CASE__						,		SCREAMING_SNAKE_CASE__       :			Dict													=self._locate_node(__lowercase )

       if node is not None:
             for i, update_node in enumerate(__lowercase ):
                   # Remove or replace all references to removed node.
                   if update_node.level > i and update_node.forward[i].key == key:
                         if node.level > i:
                               SCREAMING_SNAKE_CASE__       :			List[str]													=node.forward[i]
                         else:
                               SCREAMING_SNAKE_CASE__       :			str													=update_node.forward[:i]




 def        __magic_name__		( self		:							str   , __lowercase		:							KT   , __lowercase		:							VT )		->  Optional[Any]:
       SCREAMING_SNAKE_CASE__						,		SCREAMING_SNAKE_CASE__       :			str													=self._locate_node(__lowercase )
       if node is not None:
             SCREAMING_SNAKE_CASE__       :			Dict													=value
       else:
             SCREAMING_SNAKE_CASE__       :			List[Any]													=self.random_level()

             if level > self.level:
                   # After level increase we have to add additional nodes to head.
                   for _ in range(self.level - 1   , __lowercase ):
                         update_vector.append(self.head )
                   SCREAMING_SNAKE_CASE__       :			List[str]													=level

             SCREAMING_SNAKE_CASE__       :			List[str]													=Node(__lowercase   , __lowercase )

             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(__lowercase )
                   else:
                         SCREAMING_SNAKE_CASE__       :			int													=new_node




 def        __magic_name__		( self		:							Tuple   , __lowercase		:							VT )		->  VT | None:
       SCREAMING_SNAKE_CASE__						,		SCREAMING_SNAKE_CASE__       :			List[str]													=self._locate_node(__lowercase )

       if node is not None:
             return node.value

       return None





def 	_a(					):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__       :			Union[str, Any]													=SkipList()
      skip_list.insert('''Key1''',		3							)
      skip_list.insert('''Key2''',		1_2							)
      skip_list.insert('''Key3''',		4_1							)
      skip_list.insert('''Key4''',		-1_9							)

      SCREAMING_SNAKE_CASE__       :			Any													=skip_list.head
      SCREAMING_SNAKE_CASE__       :			Union[str, Any]													={}
      while node.level != 0:
            SCREAMING_SNAKE_CASE__       :			Dict													=node.forward[0]
            SCREAMING_SNAKE_CASE__       :			Optional[Any]													=node.value

      assert len(UpperCamelCase__							) == 4
      assert all_values["Key1"] == 3
      assert all_values["Key2"] == 1_2
      assert all_values["Key3"] == 4_1
      assert all_values["Key4"] == -1_9





def 	_a(					):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__       :			Union[str, Any]													=SkipList()
      skip_list.insert('''Key1''',		1_0							)
      skip_list.insert('''Key1''',		1_2							)

      skip_list.insert('''Key5''',		7							)
      skip_list.insert('''Key7''',		1_0							)
      skip_list.insert('''Key10''',		5							)

      skip_list.insert('''Key7''',		7							)
      skip_list.insert('''Key5''',		5							)
      skip_list.insert('''Key10''',		1_0							)

      SCREAMING_SNAKE_CASE__       :			Optional[Any]													=skip_list.head
      SCREAMING_SNAKE_CASE__       :			List[Any]													={}
      while node.level != 0:
            SCREAMING_SNAKE_CASE__       :			Union[str, Any]													=node.forward[0]
            SCREAMING_SNAKE_CASE__       :			List[Any]													=node.value

      if len(UpperCamelCase__							) != 4:
            print()
      assert len(UpperCamelCase__							) == 4
      assert all_values["Key1"] == 1_2
      assert all_values["Key7"] == 7
      assert all_values["Key5"] == 5
      assert all_values["Key10"] == 1_0





def 	_a(					):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__       :			int													=SkipList()
      assert skip_list.find('''Some key'''							) is None





def 	_a(					):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__       :			int													=SkipList()

      skip_list.insert('''Key2''',		2_0							)
      assert skip_list.find('''Key2'''							) == 2_0

      skip_list.insert('''Some Key''',		1_0							)
      skip_list.insert('''Key2''',		8							)
      skip_list.insert('''V''',		1_3							)

      assert skip_list.find('''Y'''							) is None
      assert skip_list.find('''Key2'''							) == 8
      assert skip_list.find('''Some Key'''							) == 1_0
      assert skip_list.find('''V'''							) == 1_3





def 	_a(					):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__       :			List[str]													=SkipList()
      skip_list.delete('''Some key'''							)

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





def 	_a(					):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__       :			str													=SkipList()

      skip_list.insert('''Key1''',		1_2							)
      skip_list.insert('''V''',		1_3							)
      skip_list.insert('''X''',		1_4							)
      skip_list.insert('''Key2''',		1_5							)

      skip_list.delete('''V'''							)
      skip_list.delete('''Key2'''							)

      assert skip_list.find('''V'''							) is None
      assert skip_list.find('''Key2'''							) is None





def 	_a(					):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__       :			Optional[int]													=SkipList()

      skip_list.insert('''Key1''',		1_2							)
      skip_list.insert('''V''',		1_3							)
      skip_list.insert('''X''',		1_4							)
      skip_list.insert('''Key2''',		1_5							)

      skip_list.delete('''V'''							)
      assert skip_list.find('''V'''							) is None
      assert skip_list.find('''X'''							) == 1_4
      assert skip_list.find('''Key1'''							) == 1_2
      assert skip_list.find('''Key2'''							) == 1_5

      skip_list.delete('''X'''							)
      assert skip_list.find('''V'''							) is None
      assert skip_list.find('''X'''							) is None
      assert skip_list.find('''Key1'''							) == 1_2
      assert skip_list.find('''Key2'''							) == 1_5

      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'''							) == 1_5

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




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__       :			str													=SkipList()

      skip_list.insert('''Key1''',		1_2							)
      skip_list.insert('''V''',		1_3							)
      skip_list.insert('''X''',		1_4_2							)
      skip_list.insert('''Key2''',		1_5							)

      skip_list.delete('''X'''							)

      def traverse_keys(UpperCamelCase__			:  Dict							):
            yield node.key
            for forward_node in node.forward:
                  yield from traverse_keys(UpperCamelCase__							)

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





def 	_a(					):




      '''simple docstring'''






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

      SCREAMING_SNAKE_CASE__       :			Tuple													=SkipList()
      for i in range(1_0							):
            skip_list.insert(UpperCamelCase__,		UpperCamelCase__							)
      assert is_sorted(list(UpperCamelCase__							)							)
      skip_list.delete(5							)
      skip_list.delete(8							)
      skip_list.delete(2							)
      assert is_sorted(list(UpperCamelCase__							)							)
      skip_list.insert(-1_2,		-1_2							)
      skip_list.insert(7_7,		7_7							)
      assert is_sorted(list(UpperCamelCase__							)							)





def 	_a(					):




      '''simple docstring'''






      for _ in range(1_0_0							):
            # 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(					):




      '''simple docstring'''






      SCREAMING_SNAKE_CASE__       :			Any													=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(UpperCamelCase__							)


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  main()