




import inspect
import math
import tempfile
import unittest

import numpy as np

from transformers import ViTMAEConfig
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
     import torch
     from torch import nn

     from transformers import ViTMAEForPreTraining, ViTMAEModel
     from transformers.models.vit.modeling_vit import VIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
     from PIL import Image

     from transformers import ViTImageProcessor

class     __a:






    """simple docstring"""





    def __init__( self  ,_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE=13  ,_SCREAMING_SNAKE_CASE=30  ,_SCREAMING_SNAKE_CASE=2  ,_SCREAMING_SNAKE_CASE=3  ,_SCREAMING_SNAKE_CASE=True  ,_SCREAMING_SNAKE_CASE=True  ,_SCREAMING_SNAKE_CASE=32  ,_SCREAMING_SNAKE_CASE=5  ,_SCREAMING_SNAKE_CASE=4  ,_SCREAMING_SNAKE_CASE=37  ,_SCREAMING_SNAKE_CASE="gelu"  ,_SCREAMING_SNAKE_CASE=0.1  ,_SCREAMING_SNAKE_CASE=0.1  ,_SCREAMING_SNAKE_CASE=10  ,_SCREAMING_SNAKE_CASE=0.02  ,_SCREAMING_SNAKE_CASE=3  ,_SCREAMING_SNAKE_CASE=0.6  ,_SCREAMING_SNAKE_CASE=None  ,)					->						Any:
         UpperCAmelCase_     :				str  =     parent
         UpperCAmelCase_     :				Optional[int]  =     batch_size
         UpperCAmelCase_     :				Optional[int]  =     image_size
         UpperCAmelCase_     :				Tuple  =     patch_size
         UpperCAmelCase_     :				Dict  =     num_channels
         UpperCAmelCase_     :				List[Any]  =     is_training
         UpperCAmelCase_     :				str  =     use_labels
         UpperCAmelCase_     :				Optional[int]  =     hidden_size
         UpperCAmelCase_     :				Optional[int]  =     num_hidden_layers
         UpperCAmelCase_     :				Optional[Any]  =     num_attention_heads
         UpperCAmelCase_     :				List[Any]  =     intermediate_size
         UpperCAmelCase_     :				Dict  =     hidden_act
         UpperCAmelCase_     :				str  =     hidden_dropout_prob
         UpperCAmelCase_     :				Dict  =     attention_probs_dropout_prob
         UpperCAmelCase_     :				Dict  =     type_sequence_label_size
         UpperCAmelCase_     :				Union[str, Any]  =     initializer_range
         UpperCAmelCase_     :				Dict  =     mask_ratio
         UpperCAmelCase_     :				Optional[Any]  =     scope

         # in ViTMAE, the expected sequence length = (num_patches + 1) * (1 - config.mask_ratio), rounded above
         # (we add 1 for the [CLS] token)
         UpperCAmelCase_     :				Union[str, Any]  =     (image_size // patch_size) ** 2
         UpperCAmelCase_     :				str  =     int(math.ceil((1 - mask_ratio) * (num_patches + 1)    )    )





    def 				a__ ( self    )					->						Optional[int]:
         UpperCAmelCase_     :				Optional[Any]  =     floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]    )

         UpperCAmelCase_     :				Optional[Any]  =     None
         if self.use_labels:
              UpperCAmelCase_     :				Tuple  =     ids_tensor([self.batch_size]  ,self.type_sequence_label_size    )

         UpperCAmelCase_     :				int  =     self.get_config()

         return config, pixel_values, labels





    def 				a__ ( self    )					->						List[str]:
         return ViTMAEConfig(
             image_size=self.image_size  ,patch_size=self.patch_size  ,num_channels=self.num_channels  ,hidden_size=self.hidden_size  ,num_hidden_layers=self.num_hidden_layers  ,num_attention_heads=self.num_attention_heads  ,intermediate_size=self.intermediate_size  ,hidden_act=self.hidden_act  ,hidden_dropout_prob=self.hidden_dropout_prob  ,attention_probs_dropout_prob=self.attention_probs_dropout_prob  ,is_decoder=_SCREAMING_SNAKE_CASE  ,initializer_range=self.initializer_range  ,mask_ratio=self.mask_ratio  ,)





    def 				a__ ( self  ,_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE    )					->						List[str]:
         UpperCAmelCase_     :				Any  =     ViTMAEModel(config=_SCREAMING_SNAKE_CASE    )
         model.to(_SCREAMING_SNAKE_CASE    )
         model.eval()
         UpperCAmelCase_     :				Any  =     model(_SCREAMING_SNAKE_CASE    )
         self.parent.assertEqual(result.last_hidden_state.shape  ,(self.batch_size, self.seq_length, self.hidden_size)    )





    def 				a__ ( self  ,_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE    )					->						Any:
         UpperCAmelCase_     :				str  =     ViTMAEForPreTraining(_SCREAMING_SNAKE_CASE    )
         model.to(_SCREAMING_SNAKE_CASE    )
         model.eval()
         UpperCAmelCase_     :				Dict  =     model(_SCREAMING_SNAKE_CASE    )
         UpperCAmelCase_     :				List[Any]  =     (self.image_size // self.patch_size) ** 2
         UpperCAmelCase_     :				Dict  =     self.patch_size**2 * self.num_channels
         self.parent.assertEqual(result.logits.shape  ,(self.batch_size, num_patches, expected_num_channels)    )

         # test greyscale images
         UpperCAmelCase_     :				str  =     1
         UpperCAmelCase_     :				Optional[Any]  =     ViTMAEForPreTraining(_SCREAMING_SNAKE_CASE    )
         model.to(_SCREAMING_SNAKE_CASE    )
         model.eval()
         UpperCAmelCase_     :				int  =     floats_tensor([self.batch_size, 1, self.image_size, self.image_size]    )
         UpperCAmelCase_     :				Dict  =     model(_SCREAMING_SNAKE_CASE    )
         UpperCAmelCase_     :				Optional[Any]  =     self.patch_size**2
         self.parent.assertEqual(result.logits.shape  ,(self.batch_size, num_patches, expected_num_channels)    )





    def 				a__ ( self    )					->						Optional[int]:
         UpperCAmelCase_     :				Tuple  =     self.prepare_config_and_inputs()
         UpperCAmelCase_,       UpperCAmelCase_,       UpperCAmelCase_     :				Any  =     config_and_inputs
         UpperCAmelCase_     :				List[str]  =     {'''pixel_values''': pixel_values}
         return config, inputs_dict


@require_torch
class     __a(	_a							,		_a							,		unittest.TestCase  ):






    """simple docstring"""





    lowerCAmelCase         = (ViTMAEModel, ViTMAEForPreTraining) if is_torch_available() else ()
    lowerCAmelCase         = {'''feature-extraction''': ViTMAEModel} if is_torch_available() else {}

    lowerCAmelCase         = False
    lowerCAmelCase         = False
    lowerCAmelCase         = False
    lowerCAmelCase         = False





    def 				a__ ( self    )					->						List[str]:
         UpperCAmelCase_     :				Optional[Any]  =     ViTMAEModelTester(self    )
         UpperCAmelCase_     :				List[str]  =     ConfigTester(self  ,config_class=_SCREAMING_SNAKE_CASE  ,has_text_modality=_SCREAMING_SNAKE_CASE  ,hidden_size=37    )





    def 				a__ ( self    )					->						Dict:
         self.config_tester.run_common_tests()





    @unittest.skip(reason='''ViTMAE does not use inputs_embeds'''    )
    def 				a__ ( self    )					->						Dict:
         pass





    def 				a__ ( self    )					->						str:
         UpperCAmelCase_,       UpperCAmelCase_     :				Union[str, Any]  =     self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
              UpperCAmelCase_     :				Tuple  =     model_class(_SCREAMING_SNAKE_CASE    )
              self.assertIsInstance(model.get_input_embeddings()  ,(nn.Module)    )
              UpperCAmelCase_     :				int  =     model.get_output_embeddings()
              self.assertTrue(x is None or isinstance(_SCREAMING_SNAKE_CASE  ,nn.Linear    )    )





    def 				a__ ( self    )					->						List[str]:
         UpperCAmelCase_,       UpperCAmelCase_     :				List[str]  =     self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
              UpperCAmelCase_     :				Any  =     model_class(_SCREAMING_SNAKE_CASE    )
              UpperCAmelCase_     :				Dict  =     inspect.signature(model.forward    )
              # signature.parameters is an OrderedDict => so arg_names order is deterministic
              UpperCAmelCase_     :				Tuple  =     [*signature.parameters.keys()]

              UpperCAmelCase_     :				List[Any]  =     ['''pixel_values''']
              self.assertListEqual(arg_names[:1]  ,_SCREAMING_SNAKE_CASE    )





    def 				a__ ( self    )					->						Optional[int]:
         UpperCAmelCase_     :				int  =     self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_model(*_SCREAMING_SNAKE_CASE    )





    def 				a__ ( self    )					->						Tuple:
         UpperCAmelCase_     :				Dict  =     self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_pretraining(*_SCREAMING_SNAKE_CASE    )





    def 				a__ ( self  ,_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE    )					->						Tuple:
         # make masks reproducible
         np.random.seed(2    )

         UpperCAmelCase_     :				List[Any]  =     int((pt_model.config.image_size // pt_model.config.patch_size) ** 2    )
         UpperCAmelCase_     :				List[Any]  =     np.random.uniform(size=(self.model_tester.batch_size, num_patches)    )
         UpperCAmelCase_     :				Any  =     torch.from_numpy(_SCREAMING_SNAKE_CASE    )

         # Add `noise` argument.
         # PT inputs will be prepared in `super().check_pt_tf_models()` with this added `noise` argument
         UpperCAmelCase_     :				Union[str, Any]  =     pt_noise

         super().check_pt_tf_models(_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE    )





    def 				a__ ( self    )					->						Tuple:
         UpperCAmelCase_,       UpperCAmelCase_     :				Tuple  =     self.model_tester.prepare_config_and_inputs_for_common()

         for model_class in self.all_model_classes:
              UpperCAmelCase_     :				List[str]  =     model_class(_SCREAMING_SNAKE_CASE    )
              model.to(_SCREAMING_SNAKE_CASE    )
              model.eval()
              # make random mask reproducible
              torch.manual_seed(2    )
              with torch.no_grad():
                   UpperCAmelCase_     :				Dict  =     model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE    )    )

              UpperCAmelCase_     :				List[str]  =     outputs[0].cpu().numpy()
              UpperCAmelCase_     :				str  =     0

              with tempfile.TemporaryDirectory() as tmpdirname:
                   model.save_pretrained(_SCREAMING_SNAKE_CASE    )
                   UpperCAmelCase_     :				Any  =     model_class.from_pretrained(_SCREAMING_SNAKE_CASE    )
                   model.to(_SCREAMING_SNAKE_CASE    )
                   # make random mask reproducible
                   torch.manual_seed(2    )
                   with torch.no_grad():
                        UpperCAmelCase_     :				int  =     model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE  ,_SCREAMING_SNAKE_CASE    )    )

                   # Make sure we don't have nans
                   UpperCAmelCase_     :				Tuple  =     after_outputs[0].cpu().numpy()
                   UpperCAmelCase_     :				Optional[int]  =     0
                   UpperCAmelCase_     :				Tuple  =     np.amax(np.abs(out_a - out_a    )    )
                   self.assertLessEqual(_SCREAMING_SNAKE_CASE  ,1e-5    )





    @unittest.skip(
        reason='''ViTMAE returns a random mask + ids_restore in each forward pass. See test_save_load
    to get deterministic results.'''    )
    def 				a__ ( self    )					->						Union[str, Any]:
         pass





    @unittest.skip(
        reason='''ViTMAE returns a random mask + ids_restore in each forward pass. See test_save_load
    to get deterministic results.'''    )
    def 				a__ ( self    )					->						str:
         pass





    @unittest.skip(
        reason='''ViTMAE returns a random mask + ids_restore in each forward pass. See test_save_load
    to get deterministic results.'''    )
    def 				a__ ( self    )					->						Dict:
         pass





    @unittest.skip(reason='''ViTMAE returns a random mask + ids_restore in each forward pass. See test_save_load'''    )
    def 				a__ ( self    )					->						Union[str, Any]:
         pass





    @unittest.skip('''Will be fixed soon by reducing the size of the model used for common tests.'''    )
    def 				a__ ( self    )					->						str:
         pass





    @slow
    def 				a__ ( self    )					->						Dict:
         for model_name in VIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
              UpperCAmelCase_     :				Tuple  =     ViTMAEModel.from_pretrained(_SCREAMING_SNAKE_CASE    )
              self.assertIsNotNone(_SCREAMING_SNAKE_CASE    )







def lowerCamelCase__  (     ):

     '''simple docstring'''


     UpperCAmelCase_     :				str  =     Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png''' )
     return image



@require_torch
@require_vision
class     __a(	unittest.TestCase  ):






    """simple docstring"""





    @cached_property
    def 				a__ ( self    )					->						Any:
         return ViTImageProcessor.from_pretrained('''facebook/vit-mae-base'''    ) if is_vision_available() else None





    @slow
    def 				a__ ( self    )					->						List[str]:
         # make random mask reproducible across the PT and TF model
         np.random.seed(2    )

         UpperCAmelCase_     :				List[str]  =     ViTMAEForPreTraining.from_pretrained('''facebook/vit-mae-base'''    ).to(_SCREAMING_SNAKE_CASE    )

         UpperCAmelCase_     :				int  =     self.default_image_processor
         UpperCAmelCase_     :				str  =     prepare_img()
         UpperCAmelCase_     :				Union[str, Any]  =     image_processor(images=_SCREAMING_SNAKE_CASE  ,return_tensors='''pt'''    ).to(_SCREAMING_SNAKE_CASE    )

         # prepare a noise vector that will be also used for testing the TF model
         # (this way we can ensure that the PT and TF models operate on the same inputs)
         UpperCAmelCase_     :				Any  =     ViTMAEConfig()
         UpperCAmelCase_     :				Any  =     int((vit_mae_config.image_size // vit_mae_config.patch_size) ** 2    )
         UpperCAmelCase_     :				Optional[Any]  =     np.random.uniform(size=(1, num_patches)    )

         # forward pass
         with torch.no_grad():
              UpperCAmelCase_     :				int  =     model(**_SCREAMING_SNAKE_CASE  ,noise=torch.from_numpy(_SCREAMING_SNAKE_CASE    ).to(device=_SCREAMING_SNAKE_CASE    )    )

         # verify the logits
         UpperCAmelCase_     :				Tuple  =     torch.Size((1, 196, 768)    )
         self.assertEqual(outputs.logits.shape  ,_SCREAMING_SNAKE_CASE    )

         UpperCAmelCase_     :				Optional[Any]  =     torch.tensor(
             [[-0.05_48, -1.70_23, -0.93_25], [0.37_21, -0.56_70, -0.22_33], [0.82_35, -1.38_78, -0.35_24]]    )

         self.assertTrue(torch.allclose(outputs.logits[0, :3, :3]  ,expected_slice.to(_SCREAMING_SNAKE_CASE    )  ,atol=1e-4    )    )





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

