


"""simple docstring"""







import copy
import tempfile
import unittest

from transformers import MaMaaaConfig, is_torch_available
from transformers.testing_utils import require_sentencepiece, require_tokenizers, require_torch, slow, torch_device
from transformers.utils import cached_property

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
		import torch

		from transformers import MaMaaaForConditionalGeneration, MaMaaaModel, MaMaaaTokenizer
		from transformers.models.mam_aaa.modeling_mam_aaa import MaMaaaDecoder, MaMaaaEncoder




def    UpperCAmelCase__       (lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_=None  ,						lowerCAmelCase_=None  ,						lowerCAmelCase_=None  ,						lowerCAmelCase_=None  ,						lowerCAmelCase_=None  ,						):




					'''simple docstring'''


					if attention_mask is None:
										__SCREAMING_SNAKE_CASE						   =				input_ids.ne(config.pad_token_id   )
					if decoder_attention_mask is None:
										__SCREAMING_SNAKE_CASE						   =				decoder_input_ids.ne(config.pad_token_id   )
					if head_mask is None:
										__SCREAMING_SNAKE_CASE						   =				torch.ones(config.encoder_layers  ,						config.encoder_attention_heads  ,						device=SCREAMING_SNAKE_CASE__   )
					if decoder_head_mask is None:
										__SCREAMING_SNAKE_CASE						   =				torch.ones(config.decoder_layers  ,						config.decoder_attention_heads  ,						device=SCREAMING_SNAKE_CASE__   )
					if cross_attn_head_mask is None:
										__SCREAMING_SNAKE_CASE						   =				torch.ones(config.decoder_layers  ,						config.decoder_attention_heads  ,						device=SCREAMING_SNAKE_CASE__   )
					return {
					    "input_ids": input_ids,
					    "decoder_input_ids": decoder_input_ids,
					    "attention_mask": attention_mask,
					    "decoder_attention_mask": attention_mask,
					    "head_mask": head_mask,
					    "decoder_head_mask": decoder_head_mask,
					    "cross_attn_head_mask": cross_attn_head_mask,
					}




class  UpperCamelCase_	:

	"""simple docstring"""





	def __init__( self			:				int			,			UpperCAmelCase__			:				List[Any]			,			UpperCAmelCase__			:				List[Any]=1_3			,			UpperCAmelCase__			:				Any=7			,			UpperCAmelCase__			:				Union[str, Any]=True			,			UpperCAmelCase__			:				Union[str, Any]=False			,			UpperCAmelCase__			:				List[Any]=9_9			,			UpperCAmelCase__			:				int=1_6			,			UpperCAmelCase__			:				str=2			,			UpperCAmelCase__			:				int=4			,			UpperCAmelCase__			:				Union[str, Any]=4			,			UpperCAmelCase__			:				str="relu"			,			UpperCAmelCase__			:				int=0.1			,			UpperCAmelCase__			:				Union[str, Any]=0.1			,			UpperCAmelCase__			:				Any=0.0			,			UpperCAmelCase__			:				List[Any]=0.0			,			UpperCAmelCase__			:				int=2_0			,			UpperCAmelCase__			:				Optional[int]=2			,			UpperCAmelCase__			:				List[Any]=1			,			UpperCAmelCase__			:				int=0			,			)       ->	str:
						__SCREAMING_SNAKE_CASE						   =				parent
						__SCREAMING_SNAKE_CASE						   =				batch_size
						__SCREAMING_SNAKE_CASE						   =				seq_length
						__SCREAMING_SNAKE_CASE						   =				is_training
						__SCREAMING_SNAKE_CASE						   =				use_labels
						__SCREAMING_SNAKE_CASE						   =				vocab_size
						__SCREAMING_SNAKE_CASE						   =				hidden_size
						__SCREAMING_SNAKE_CASE						   =				num_hidden_layers
						__SCREAMING_SNAKE_CASE						   =				num_attention_heads
						__SCREAMING_SNAKE_CASE						   =				intermediate_size
						__SCREAMING_SNAKE_CASE						   =				hidden_act
						__SCREAMING_SNAKE_CASE						   =				hidden_dropout_prob
						__SCREAMING_SNAKE_CASE						   =				attention_probs_dropout_prob
						__SCREAMING_SNAKE_CASE						   =				encoder_layerdrop
						__SCREAMING_SNAKE_CASE						   =				decoder_layerdrop
						__SCREAMING_SNAKE_CASE						   =				max_position_embeddings
						__SCREAMING_SNAKE_CASE						   =				eos_token_id
						__SCREAMING_SNAKE_CASE						   =				pad_token_id
						__SCREAMING_SNAKE_CASE						   =				bos_token_id




	def   UpperCAmelCase_      ( self			:				Any   )       ->	Optional[Any]:
						__SCREAMING_SNAKE_CASE						   =				ids_tensor([self.batch_size, self.seq_length]			,			self.vocab_size   )
						__SCREAMING_SNAKE_CASE						   =				self.eos_token_id  # Eos Token
						__SCREAMING_SNAKE_CASE						   =				ids_tensor([self.batch_size, self.seq_length]			,			self.vocab_size   )

						# we need to clamp the input ids here to avoid having pad token in between
						# this is because for M2M100 the position_ids are prepared such that
						# all pad tokens have pos id = 2 and rest are between 2..seq_length
						# and the seq_length here is seq_length - num_pad_tokens
						# but when using past, there is no way of knowing if the past input ids had
						# pad tokens in them, which results in incorrect seq_lenth and which in turn results in
						# position_ids being off by num_pad_tokens in past input
						__SCREAMING_SNAKE_CASE						   =				input_ids.clamp(self.pad_token_id + 1   )
						__SCREAMING_SNAKE_CASE						   =				decoder_input_ids.clamp(self.pad_token_id + 1   )

						__SCREAMING_SNAKE_CASE						   =				self.get_config()
						__SCREAMING_SNAKE_CASE						   =				prepare_mam_aaa_inputs_dict(lowercase_			,			lowercase_			,			lowercase_   )
						return config, inputs_dict




	def   UpperCAmelCase_      ( self			:				int   )       ->	Tuple:
						return MaMaaaConfig(
						    vocab_size=self.vocab_size			,			d_model=self.hidden_size			,			encoder_layers=self.num_hidden_layers			,			decoder_layers=self.num_hidden_layers			,			encoder_attention_heads=self.num_attention_heads			,			decoder_attention_heads=self.num_attention_heads			,			encoder_ffn_dim=self.intermediate_size			,			decoder_ffn_dim=self.intermediate_size			,			dropout=self.hidden_dropout_prob			,			attention_dropout=self.attention_probs_dropout_prob			,			encoder_layerdrop=self.encoder_layerdrop			,			decoder_layerdrop=self.decoder_layerdrop			,			max_position_embeddings=self.max_position_embeddings			,			eos_token_id=self.eos_token_id			,			bos_token_id=self.bos_token_id			,			pad_token_id=self.pad_token_id			,			)




	def   UpperCAmelCase_      ( self			:				int   )       ->	Optional[Any]:
						__SCREAMING_SNAKE_CASE   ,  __SCREAMING_SNAKE_CASE						   =				self.prepare_config_and_inputs()
						return config, inputs_dict




	def   UpperCAmelCase_      ( self			:				str			,			UpperCAmelCase__			:				List[Any]			,			UpperCAmelCase__			:				Optional[Any]   )       ->	List[Any]:
						__SCREAMING_SNAKE_CASE						   =				MaMaaaModel(config=lowercase_   ).get_decoder().to(lowercase_   ).eval()
						__SCREAMING_SNAKE_CASE						   =				inputs_dict["input_ids"]
						__SCREAMING_SNAKE_CASE						   =				inputs_dict["attention_mask"]
						__SCREAMING_SNAKE_CASE						   =				inputs_dict["head_mask"]

						# first forward pass
						__SCREAMING_SNAKE_CASE						   =				model(lowercase_			,			attention_mask=lowercase_			,			head_mask=lowercase_			,			use_cache=lowercase_   )

						__SCREAMING_SNAKE_CASE   ,  __SCREAMING_SNAKE_CASE						   =				outputs.to_tuple()

						# create hypothetical multiple next token and extent to next_input_ids
						__SCREAMING_SNAKE_CASE						   =				ids_tensor((self.batch_size, 3)			,			config.vocab_size   )
						__SCREAMING_SNAKE_CASE						   =				ids_tensor((self.batch_size, 3)			,			2   )

						# append to next input_ids and
						__SCREAMING_SNAKE_CASE						   =				torch.cat([input_ids, next_tokens]			,			dim=-1   )
						__SCREAMING_SNAKE_CASE						   =				torch.cat([attention_mask, next_attn_mask]			,			dim=-1   )

						__SCREAMING_SNAKE_CASE						   =				model(lowercase_			,			attention_mask=lowercase_   )["last_hidden_state"]
						__SCREAMING_SNAKE_CASE						   =				model(lowercase_			,			attention_mask=lowercase_			,			past_key_values=lowercase_   )[
						    "last_hidden_state"
						]

						# select random slice
						__SCREAMING_SNAKE_CASE						   =				ids_tensor((1,)			,			output_from_past.shape[-1]   ).item()
						__SCREAMING_SNAKE_CASE						   =				output_from_no_past[:, -3:, random_slice_idx].detach()
						__SCREAMING_SNAKE_CASE						   =				output_from_past[:, :, random_slice_idx].detach()

						self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]   )

						# test that outputs are equal for slice
						self.parent.assertTrue(torch.allclose(lowercase_			,			lowercase_			,			atol=1E-2   )   )




	def   UpperCAmelCase_      ( self			:				Tuple			,			UpperCAmelCase__			:				List[str]			,			UpperCAmelCase__			:				str   )       ->	Tuple:
						__SCREAMING_SNAKE_CASE						   =				MaMaaaModel(config=lowercase_   ).to(lowercase_   ).eval()
						__SCREAMING_SNAKE_CASE						   =				model(**lowercase_   )

						__SCREAMING_SNAKE_CASE						   =				outputs.encoder_last_hidden_state
						__SCREAMING_SNAKE_CASE						   =				outputs.last_hidden_state

						with tempfile.TemporaryDirectory() as tmpdirname:
											__SCREAMING_SNAKE_CASE						   =				model.get_encoder()
											encoder.save_pretrained(lowercase_   )
											__SCREAMING_SNAKE_CASE						   =				MaMaaaEncoder.from_pretrained(lowercase_   ).to(lowercase_   )

						__SCREAMING_SNAKE_CASE						   =				encoder(inputs_dict["input_ids"]			,			attention_mask=inputs_dict["attention_mask"]   )[
						    0
						]

						self.parent.assertTrue((encoder_last_hidden_state_a - encoder_last_hidden_state).abs().max().item() < 1E-3   )

						with tempfile.TemporaryDirectory() as tmpdirname:
											__SCREAMING_SNAKE_CASE						   =				model.get_decoder()
											decoder.save_pretrained(lowercase_   )
											__SCREAMING_SNAKE_CASE						   =				MaMaaaDecoder.from_pretrained(lowercase_   ).to(lowercase_   )

						__SCREAMING_SNAKE_CASE						   =				decoder(
						    input_ids=inputs_dict["decoder_input_ids"]			,			attention_mask=inputs_dict["decoder_attention_mask"]			,			encoder_hidden_states=lowercase_			,			encoder_attention_mask=inputs_dict["attention_mask"]			,			)[0]

						self.parent.assertTrue((last_hidden_state_a - last_hidden_state).abs().max().item() < 1E-3   )




@require_torch
class  UpperCamelCase_	( _UpperCAmelCase			,  _UpperCAmelCase			,  _UpperCAmelCase			,  unittest.TestCase):

	"""simple docstring"""





	snake_case__				:  List[Any]    					=			(
	    (
	        MaMaaaModel,
	        MaMaaaForConditionalGeneration,
	    )
	    if is_torch_available()
	    else ()
	)
	snake_case__				:  Union[str, Any]    					=			(MaMaaaForConditionalGeneration,) if is_torch_available() else ()
	snake_case__				:  Optional[Any]    					=			(
	    {
	        "conversational": MaMaaaForConditionalGeneration,
	        "feature-extraction": MaMaaaModel,
	        "summarization": MaMaaaForConditionalGeneration,
	        "text2text-generation": MaMaaaForConditionalGeneration,
	        "translation": MaMaaaForConditionalGeneration,
	    }
	    if is_torch_available()
	    else {}
	)
	snake_case__				:  int    					=			True
	snake_case__				:  List[Any]    					=			True
	snake_case__				:  Dict    					=			False
	snake_case__				:  Union[str, Any]    					=			False




	def   UpperCAmelCase_      ( self			:				Dict			,			UpperCAmelCase__			:				Union[str, Any]			,			UpperCAmelCase__			:				str			,			UpperCAmelCase__			:				List[str]			,			UpperCAmelCase__			:				List[str]			,			UpperCAmelCase__			:				int   )       ->	Optional[int]:







						if pipeline_test_casse_name == "TranslationPipelineTests":
											# Get `ValueError: Translation requires a `src_lang` and a `tgt_lang` for this model`.
											# `M2M100Config` was never used in pipeline tests: cannot create a simple tokenizer.
											return True

						return False




	def   UpperCAmelCase_      ( self			:				Any   )       ->	Dict:
						__SCREAMING_SNAKE_CASE						   =				MaMaaaModelTester(self   )
						__SCREAMING_SNAKE_CASE						   =				ConfigTester(self			,			config_class=lowercase_   )




	def   UpperCAmelCase_      ( self			:				str   )       ->	int:
						self.config_tester.run_common_tests()




	def   UpperCAmelCase_      ( self			:				Optional[Any]   )       ->	str:
						__SCREAMING_SNAKE_CASE   ,  __SCREAMING_SNAKE_CASE						   =				self.model_tester.prepare_config_and_inputs()
						for model_class in self.all_model_classes:
											__SCREAMING_SNAKE_CASE						   =				model_class(lowercase_   )

											with tempfile.TemporaryDirectory() as tmpdirname:
																model.save_pretrained(lowercase_   )
																__SCREAMING_SNAKE_CASE   ,  __SCREAMING_SNAKE_CASE						   =				model_class.from_pretrained(lowercase_			,			output_loading_info=lowercase_   )
											self.assertEqual(info["missing_keys"]			,			[]   )




	def   UpperCAmelCase_      ( self			:				int   )       ->	Optional[int]:
						__SCREAMING_SNAKE_CASE						   =				self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_decoder_model_past_large_inputs(*lowercase_   )




	def   UpperCAmelCase_      ( self			:				Optional[int]   )       ->	Union[str, Any]:
						__SCREAMING_SNAKE_CASE						   =				self.model_tester.prepare_config_and_inputs_for_common()
						self.model_tester.check_encoder_decoder_model_standalone(*lowercase_   )




	def   UpperCAmelCase_      ( self			:				int   )       ->	int:
						__SCREAMING_SNAKE_CASE   ,  __SCREAMING_SNAKE_CASE						   =				self.model_tester.prepare_config_and_inputs_for_common()

						for model_class in (MaMaaaModel, MaMaaaForConditionalGeneration):
											__SCREAMING_SNAKE_CASE						   =				model_class(lowercase_   )
											model.to(lowercase_   )
											model.eval()

											__SCREAMING_SNAKE_CASE						   =				copy.deepcopy(self._prepare_for_class(lowercase_			,			lowercase_   )   )

											if not self.is_encoder_decoder:
																__SCREAMING_SNAKE_CASE						   =				inputs["input_ids"]
																del inputs["input_ids"]
											else:
																__SCREAMING_SNAKE_CASE						   =				inputs["input_ids"]
																__SCREAMING_SNAKE_CASE						   =				inputs.get("decoder_input_ids"			,			lowercase_   )
																del inputs["input_ids"]
																inputs.pop("decoder_input_ids"			,			lowercase_   )

											__SCREAMING_SNAKE_CASE						   =				model.get_input_embeddings()
											if not self.is_encoder_decoder:
																__SCREAMING_SNAKE_CASE						   =				wte(lowercase_   )
											else:
																__SCREAMING_SNAKE_CASE						   =				wte(lowercase_   )
																__SCREAMING_SNAKE_CASE						   =				wte(lowercase_   )

											with torch.no_grad():
																model(**lowercase_   )[0]




	def   UpperCAmelCase_      ( self			:				str   )       ->	Tuple:
						__SCREAMING_SNAKE_CASE   ,  __SCREAMING_SNAKE_CASE						   =				self.model_tester.prepare_config_and_inputs()
						__SCREAMING_SNAKE_CASE						   =				input_dict["input_ids"]
						__SCREAMING_SNAKE_CASE						   =				input_ids.ne(1   ).to(lowercase_   )
						__SCREAMING_SNAKE_CASE						   =				MaMaaaForConditionalGeneration(lowercase_   ).eval().to(lowercase_   )
						if torch_device == "cuda":
											model.half()
						model.generate(lowercase_			,			attention_mask=lowercase_   )
						model.generate(num_beams=4			,			do_sample=lowercase_			,			early_stopping=lowercase_			,			num_return_sequences=3   )




def    UpperCAmelCase__       (lowerCAmelCase_   ):




					'''simple docstring'''


					return torch.tensor(SCREAMING_SNAKE_CASE__  ,						dtype=torch.long  ,						device=SCREAMING_SNAKE_CASE__   )


a__				:							Tuple						=     1E-4




@require_torch
@require_sentencepiece
@require_tokenizers
@slow
class  UpperCamelCase_	( unittest.TestCase):

	"""simple docstring"""





	@cached_property
	def   UpperCAmelCase_      ( self			:				Any   )       ->	Any:
						return MaMaaaTokenizer.from_pretrained("facebook/m2m100_418M"   )




	def   UpperCAmelCase_      ( self			:				Optional[Any]   )       ->	int:
						__SCREAMING_SNAKE_CASE						   =				MaMaaaModel.from_pretrained("facebook/m2m100_418M"   ).to(lowercase_   )
						__SCREAMING_SNAKE_CASE						   =				_long_tensor([[1_2_8_0_2_8, 9_8, 1_2, 3_0_5_2_7, 2_7_3_2, 1_5_9, 7_7_5_5, 6_1_9_0_4, 3_9_1_4_4, 3_8, 2]]   )
						__SCREAMING_SNAKE_CASE						   =				_long_tensor([[2, 1_2_8_0_2_8, 9_8, 1_2, 3_0_5_2_7, 2_7_3_2, 1_5_9, 7_7_5_5, 6_1_9_0_4, 3_9_1_4_4, 3_8]]   )
						__SCREAMING_SNAKE_CASE						   =				prepare_mam_aaa_inputs_dict(model.config			,			lowercase_			,			lowercase_   )
						with torch.no_grad():
											__SCREAMING_SNAKE_CASE						   =				model(**lowercase_   )[0]
						__SCREAMING_SNAKE_CASE						   =				torch.Size((1, 1_1, 1_0_2_4)   )
						self.assertEqual(output.shape			,			lowercase_   )
						# change to expected output here
						__SCREAMING_SNAKE_CASE						   =				torch.tensor(
						    [[-0.7_780, -0.1_676, 0.1_038], [-6.7_556, -1.3_992, 0.0_567], [-7.5_383, -0.5_920, -0.2_779]]			,			device=lowercase_   )
						self.assertTrue(torch.allclose(output[:, :3, :3]			,			lowercase_			,			atol=lowercase_   )   )




	def   UpperCAmelCase_      ( self			:				Optional[int]   )       ->	Optional[Any]:
						__SCREAMING_SNAKE_CASE						   =				MaMaaaForConditionalGeneration.from_pretrained("facebook/m2m100_418M"   ).to(lowercase_   )

						# change to intended input
						__SCREAMING_SNAKE_CASE						   =				_long_tensor([[1_2_8_0_2_8, 9_8, 1_2, 3_0_5_2_7, 2_7_3_2, 1_5_9, 7_7_5_5, 6_1_9_0_4, 3_9_1_4_4, 3_8, 2]]   )
						__SCREAMING_SNAKE_CASE						   =				_long_tensor([[2, 1_2_8_0_2_8, 9_8, 1_2, 3_0_5_2_7, 2_7_3_2, 1_5_9, 7_7_5_5, 6_1_9_0_4, 3_9_1_4_4, 3_8]]   )
						__SCREAMING_SNAKE_CASE						   =				prepare_mam_aaa_inputs_dict(model.config			,			lowercase_			,			lowercase_   )
						with torch.no_grad():
											__SCREAMING_SNAKE_CASE						   =				model(**lowercase_   )[0]
						__SCREAMING_SNAKE_CASE						   =				torch.Size((1, 1_1, model.config.vocab_size)   )
						self.assertEqual(output.shape			,			lowercase_   )
						# change to expected output here
						__SCREAMING_SNAKE_CASE						   =				torch.tensor(
						    [[-1.0_448, -1.0_411, 3.7_992], [-3.2_191, -3.2_386, -1.3_451], [-3.6_210, -3.5_993, 0.4_925]]			,			device=lowercase_   )
						self.assertTrue(torch.allclose(output[:, :3, :3]			,			lowercase_			,			atol=lowercase_   )   )




	def   UpperCAmelCase_      ( self			:				List[Any]   )       ->	List[Any]:
						__SCREAMING_SNAKE_CASE						   =				MaMaaaForConditionalGeneration.from_pretrained("facebook/m2m100_418M"   ).to(lowercase_   )
						__SCREAMING_SNAKE_CASE						   =				MaMaaaTokenizer.from_pretrained("facebook/m2m100_418M"			,			src_lang="fr"			,			tgt_lang="en"   )

						__SCREAMING_SNAKE_CASE						   =				[
						    "L\'affaire NSA souligne l\'absence totale de débat sur le renseignement",
						    "Selon moi, il y a deux niveaux de réponse de la part du gouvernement français.",
						    "Lorsque François Hollande téléphone à Barack Obama ou quand le ministre des affaires étrangères Laurent"
						    " Fabius convoque l\'ambassadeur des Etats-Unis, ils réagissent à une vraie découverte, qui est celle de"
						    " l\'ampleur de la surveillance américaine sur l\'ensemble des communications en France.",
						]

						# The below article tests that we don't add any hypotheses outside of the top n_beams
						__SCREAMING_SNAKE_CASE						   =				tokenizer(lowercase_			,			padding=lowercase_			,			return_tensors="pt"   )

						__SCREAMING_SNAKE_CASE						   =				model.generate(
						    input_ids=dct["input_ids"].to(lowercase_   )			,			attention_mask=dct["attention_mask"].to(lowercase_   )			,			num_beams=5			,			forced_bos_token_id=tokenizer.get_lang_id("en"   )			,			)

						__SCREAMING_SNAKE_CASE						   =				[
						    "The NSA case highlights the total absence of intelligence debate",
						    "I think there are two levels of response from the French government.",
						    "When François Hollande calls Barack Obama or when Foreign Minister Laurent Fabius calls the U.S."
						    " Ambassador, they respond to a real discovery, which is that of the scale of U.S. surveillance on all"
						    " communications in France.",
						]

						__SCREAMING_SNAKE_CASE						   =				tokenizer.batch_decode(
						    hypotheses_batch.tolist()			,			clean_up_tokenization_spaces=lowercase_			,			skip_special_tokens=lowercase_   )
						assert generated == expected_en



def 						_snake_case(    SCREAMING_SNAKE_CASE__			:	Optional[Any]    ,			SCREAMING_SNAKE_CASE__			:	Union[str, Any]      )							->      Tuple:





    '''simple docstring'''






    A__          =   0
    A__          =   len(SCREAMING_SNAKE_CASE__      ) - 1

    while left <= right:
        # avoid divided by 0 during interpolation
        if sorted_collection[left] == sorted_collection[right]:
            if sorted_collection[left] == item:
                return left
            else:
                return None

        A__          =   left + ((item - sorted_collection[left]) * (right - left)) // (
            sorted_collection[right] - sorted_collection[left]
        )

        # out of range check
        if point < 0 or point >= len(SCREAMING_SNAKE_CASE__      ):
            return None

        A__          =   sorted_collection[point]
        if current_item == item:
            return point
        else:
            if point < left:
                A__          =   left
                A__          =   point
            elif point > right:
                A__          =   right
                A__          =   point
            else:
                if item < current_item:
                    A__          =   point - 1
                else:
                    A__          =   point + 1
    return None
def 						_snake_case(    SCREAMING_SNAKE_CASE__			:	Optional[Any]    ,			SCREAMING_SNAKE_CASE__			:	List[str]    ,			SCREAMING_SNAKE_CASE__			:	Optional[Any]    ,			SCREAMING_SNAKE_CASE__			:	List[str]      )							->      str:





    '''simple docstring'''






    if sorted_collection[left] == sorted_collection[right]:
        if sorted_collection[left] == item:
            return left
        else:
            return None

    A__          =   left + ((item - sorted_collection[left]) * (right - left)) // (
        sorted_collection[right] - sorted_collection[left]
    )

    # out of range check
    if point < 0 or point >= len(SCREAMING_SNAKE_CASE__      ):
        return None

    if sorted_collection[point] == item:
        return point
    elif point < left:
        return interpolation_search_by_recursion(SCREAMING_SNAKE_CASE__    ,			SCREAMING_SNAKE_CASE__    ,			SCREAMING_SNAKE_CASE__    ,			SCREAMING_SNAKE_CASE__      )
    elif point > right:
        return interpolation_search_by_recursion(SCREAMING_SNAKE_CASE__    ,			SCREAMING_SNAKE_CASE__    ,			SCREAMING_SNAKE_CASE__    ,			SCREAMING_SNAKE_CASE__      )
    else:
        if sorted_collection[point] > item:
            return interpolation_search_by_recursion(
                SCREAMING_SNAKE_CASE__    ,			SCREAMING_SNAKE_CASE__    ,			SCREAMING_SNAKE_CASE__    ,			point - 1      )
        else:
            return interpolation_search_by_recursion(
                SCREAMING_SNAKE_CASE__    ,			SCREAMING_SNAKE_CASE__    ,			point + 1    ,			SCREAMING_SNAKE_CASE__      )
def 						_snake_case(    SCREAMING_SNAKE_CASE__			:	Tuple      )							->      Tuple:





    '''simple docstring'''






    if collection != sorted(SCREAMING_SNAKE_CASE__      ):
        raise ValueError('Collection must be ascending sorted'      )
    return True


if __name__ == "__main__":
     import sys
     lowercase_       		=  0
     if debug == 1:
          lowercase_       		=  [10, 30, 40, 45, 50, 66, 77, 93]
          try:
               __assert_sorted(collection)
          except ValueError:
               sys.exit("Sequence must be ascending sorted to apply interpolation search")
          lowercase_       		=  67

     lowercase_       		=  interpolation_search(collection, target)
     if result is not None:
          print(f"""{target} found at positions: {result}""")
     else:
          print("Not found")

