
'''simple docstring'''



import unittest

from transformers import TrOCRConfig
from transformers.testing_utils import is_torch_available, require_torch, torch_device

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.models.trocr.modeling_trocr import TrOCRDecoder, TrOCRForCausalLM




@require_torch
class   UpperCAmelCase_					:






						'''simple docstring'''






						def __init__( self   ,       _lowercase   ,       _lowercase=99   ,       _lowercase=13   ,       _lowercase=16   ,       _lowercase=7   ,       _lowercase=True   ,       _lowercase=True   ,       _lowercase=True   ,       _lowercase=False   ,       _lowercase=True   ,       _lowercase=2   ,       _lowercase=32   ,       _lowercase=4   ,       _lowercase=4   ,       _lowercase=30   ,       _lowercase=0   ,       _lowercase=1   ,       _lowercase=2   ,       _lowercase=None   ,       ):

												"""simple docstring"""



												_lowerCAmelCase  						=			parent
												_lowerCAmelCase  						=			batch_size
												_lowerCAmelCase  						=			decoder_seq_length
												# For common tests
												_lowerCAmelCase  						=			self.decoder_seq_length
												_lowerCAmelCase  						=			is_training
												_lowerCAmelCase  						=			use_attention_mask
												_lowerCAmelCase  						=			use_labels

												_lowerCAmelCase  						=			vocab_size
												_lowerCAmelCase  						=			d_model
												_lowerCAmelCase  						=			d_model
												_lowerCAmelCase  						=			decoder_layers
												_lowerCAmelCase  						=			decoder_layers
												_lowerCAmelCase  						=			decoder_ffn_dim
												_lowerCAmelCase  						=			decoder_attention_heads
												_lowerCAmelCase  						=			decoder_attention_heads
												_lowerCAmelCase  						=			eos_token_id
												_lowerCAmelCase  						=			bos_token_id
												_lowerCAmelCase  						=			pad_token_id
												_lowerCAmelCase  						=			decoder_start_token_id
												_lowerCAmelCase  						=			use_cache
												_lowerCAmelCase  						=			max_position_embeddings

												_lowerCAmelCase  						=			None
												_lowerCAmelCase  						=			decoder_seq_length
												_lowerCAmelCase  						=			2
												_lowerCAmelCase  						=			1




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			ids_tensor([self.batch_size, self.decoder_seq_length]   ,       self.vocab_size				)

												_lowerCAmelCase  						=			None
												if self.use_attention_mask:
																		_lowerCAmelCase  						=			ids_tensor([self.batch_size, self.decoder_seq_length]   ,       vocab_size=2				)

												_lowerCAmelCase  						=			None
												if self.use_labels:
																		_lowerCAmelCase  						=			ids_tensor([self.batch_size, self.decoder_seq_length]   ,       self.vocab_size				)

												_lowerCAmelCase  						=			TrOCRConfig(
												    vocab_size=self.vocab_size   ,       d_model=self.d_model   ,       decoder_layers=self.decoder_layers   ,       decoder_ffn_dim=self.decoder_ffn_dim   ,       decoder_attention_heads=self.decoder_attention_heads   ,       eos_token_id=self.eos_token_id   ,       bos_token_id=self.bos_token_id   ,       use_cache=self.use_cache   ,       pad_token_id=self.pad_token_id   ,       decoder_start_token_id=self.decoder_start_token_id   ,       max_position_embeddings=self.max_position_embeddings   ,       )

												return (config, input_ids, attention_mask, lm_labels)




						def  _lowercase     ( self   ,       _lowercase   ,       _lowercase   ,       _lowercase   ,       _lowercase   ,       ):

												"""simple docstring"""



												_lowerCAmelCase  						=			True
												_lowerCAmelCase  						=			TrOCRDecoder(config=_lowercase				).to(_lowercase				).eval()
												_lowerCAmelCase  						=			input_ids[:2]

												input_ids[input_ids == 0] += 1
												# first forward pass
												_lowerCAmelCase  						=			model(_lowercase   ,       use_cache=_lowercase				)
												_lowerCAmelCase  						=			model(_lowercase				)
												_lowerCAmelCase  						=			model(_lowercase   ,       use_cache=_lowercase				)

												self.parent.assertTrue(len(_lowercase				) == len(_lowercase				)				)
												self.parent.assertTrue(len(_lowercase				) == len(_lowercase				) + 1				)

												_lowerCAmelCase  						=			outputs["""past_key_values"""]

												# create hypothetical next token and extent to next_input_ids
												_lowerCAmelCase  						=			ids_tensor((2, 1)   ,       config.vocab_size - 1				) + 1

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

												_lowerCAmelCase  						=			model(_lowercase				)["""last_hidden_state"""]
												_lowerCAmelCase  						=			model(_lowercase   ,       past_key_values=_lowercase				)["""last_hidden_state"""]

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

												# test that outputs are equal for slice
												assert torch.allclose(_lowercase   ,       _lowercase   ,       atol=1e-3				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			self.prepare_config_and_inputs()
												_lowerCAmelCase						,   _lowerCAmelCase						,   _lowerCAmelCase						,   _lowerCAmelCase  						=			config_and_inputs

												_lowerCAmelCase  						=			{"""input_ids""": input_ids, """attention_mask""": attention_mask}
												return config, inputs_dict






@require_torch
class   UpperCAmelCase_					(		_SCREAMING_SNAKE_CASE	,							_SCREAMING_SNAKE_CASE	,							_SCREAMING_SNAKE_CASE	,							unittest.TestCase			):






						'''simple docstring'''






						_lowercase		:				Any									=       (TrOCRDecoder, TrOCRForCausalLM) if is_torch_available() else ()
						_lowercase		:				List[str]									=       (TrOCRForCausalLM,) if is_torch_available() else ()
						_lowercase		:				Union[str, Any]									=       {'''text-generation''': TrOCRForCausalLM} if is_torch_available() else {}
						_lowercase		:				Tuple									=       True
						_lowercase		:				Any									=       False




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			TrOCRStandaloneDecoderModelTester(self   ,       is_training=_lowercase				)
												_lowerCAmelCase  						=			ConfigTester(self   ,       config_class=_lowercase				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												pass




						def  _lowercase     ( self				):

												"""simple docstring"""



												pass




						def  _lowercase     ( self				):

												"""simple docstring"""



												pass




						def  _lowercase     ( self				):

												"""simple docstring"""



												self.config_tester.run_common_tests()




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_decoder_model_past(*_lowercase				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												return




						@unittest.skip("""The model doesn't support left padding"""				)  # and it's not used enough to be worth fixing :)
						def  _lowercase     ( self				):

												"""simple docstring"""



												pass


'''simple docstring'''



from __future__ import annotations

# This is the precision for this function which can be altered.
# It is recommended for users to keep this number greater than or equal to 10.
_lowercase    =		10


def A				(__lowerCamelCase				:int			,     __lowerCamelCase				:int			,     __lowerCamelCase				:list[int]			,     __lowerCamelCase				:int		):
						for i in range(__lowerCamelCase			,     __lowerCamelCase		):
												if array[i] == target:
																		return i
						return -1


def A				(__lowerCamelCase				:list[int]			,     __lowerCamelCase				:int		):
						_lowerCAmelCase  						=			0
						_lowerCAmelCase  						=			len(__lowerCamelCase		)
						while left <= right:
												if right - left < precision:
																		return lin_search(__lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase		)

												_lowerCAmelCase  						=			(left + right) // 3 + 1
												_lowerCAmelCase  						=			2 * (left + right) // 3 + 1

												if array[one_third] == target:
																		return one_third
												elif array[two_third] == target:
																		return two_third

												elif target < array[one_third]:
																		_lowerCAmelCase  						=			one_third - 1
												elif array[two_third] < target:
																		_lowerCAmelCase  						=			two_third + 1

												else:
																		_lowerCAmelCase  						=			one_third + 1
																		_lowerCAmelCase  						=			two_third - 1
						else:
												return -1


def A				(__lowerCamelCase				:int			,     __lowerCamelCase				:int			,     __lowerCamelCase				:list[int]			,     __lowerCamelCase				:int		):
						if left < right:
												if right - left < precision:
																		return lin_search(__lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase		)
												_lowerCAmelCase  						=			(left + right) // 3 + 1
												_lowerCAmelCase  						=			2 * (left + right) // 3 + 1

												if array[one_third] == target:
																		return one_third
												elif array[two_third] == target:
																		return two_third

												elif target < array[one_third]:
																		return rec_ternary_search(__lowerCamelCase			,     one_third - 1			,     __lowerCamelCase			,     __lowerCamelCase		)
												elif array[two_third] < target:
																		return rec_ternary_search(two_third + 1			,     __lowerCamelCase			,     __lowerCamelCase			,     __lowerCamelCase		)
												else:
																		return rec_ternary_search(one_third + 1			,     two_third - 1			,     __lowerCamelCase			,     __lowerCamelCase		)
						else:
												return -1


if __name__ == "__main__":
						import doctest

						doctest.testmod()

						_lowercase    =		input("""Enter numbers separated by comma:\n""").strip()
						_lowercase    =		[int(item.strip()) for item in user_input.split(""",""")]
						assert collection == sorted(collection), F"List must be ordered.\n{collection}."
						_lowercase    =		int(input("""Enter the number to be found in the list:\n""").strip())
						_lowercase    =		ite_ternary_search(collection, target)
						_lowercase    =		rec_ternary_search(0, len(collection) - 1, collection, target)
						if resulta != -1:
												print(F"""Iterative search: {target} found at positions: {resulta}""")
												print(F"""Recursive search: {target} found at positions: {resulta}""")
						else:
												print("""Not found""")
