
'''simple docstring'''



import unittest

from transformers import is_torch_available
from transformers.testing_utils import require_torch, slow, 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 import (
						    OPENAI_GPT_PRETRAINED_MODEL_ARCHIVE_LIST,
						    OpenAIGPTConfig,
						    OpenAIGPTDoubleHeadsModel,
						    OpenAIGPTForSequenceClassification,
						    OpenAIGPTLMHeadModel,
						    OpenAIGPTModel,
						)




class   UpperCAmelCase_					:






						'''simple docstring'''






						def __init__( self   ,       _lowercase   ,       _lowercase=13   ,       _lowercase=7   ,       _lowercase=True   ,       _lowercase=True   ,       _lowercase=True   ,       _lowercase=99   ,       _lowercase=32   ,       _lowercase=5   ,       _lowercase=4   ,       _lowercase=37   ,       _lowercase="gelu"   ,       _lowercase=0.1   ,       _lowercase=0.1   ,       _lowercase=512   ,       _lowercase=16   ,       _lowercase=2   ,       _lowercase=0.02   ,       _lowercase=3   ,       _lowercase=4   ,       _lowercase=None   ,       ):

												"""simple docstring"""



												_lowerCAmelCase  						=			parent
												_lowerCAmelCase  						=			batch_size
												_lowerCAmelCase  						=			seq_length
												_lowerCAmelCase  						=			is_training
												_lowerCAmelCase  						=			use_token_type_ids
												_lowerCAmelCase  						=			use_labels
												_lowerCAmelCase  						=			vocab_size
												_lowerCAmelCase  						=			hidden_size
												_lowerCAmelCase  						=			num_hidden_layers
												_lowerCAmelCase  						=			num_attention_heads
												_lowerCAmelCase  						=			intermediate_size
												_lowerCAmelCase  						=			hidden_act
												_lowerCAmelCase  						=			hidden_dropout_prob
												_lowerCAmelCase  						=			attention_probs_dropout_prob
												_lowerCAmelCase  						=			max_position_embeddings
												_lowerCAmelCase  						=			type_vocab_size
												_lowerCAmelCase  						=			type_sequence_label_size
												_lowerCAmelCase  						=			initializer_range
												_lowerCAmelCase  						=			num_labels
												_lowerCAmelCase  						=			num_choices
												_lowerCAmelCase  						=			scope
												_lowerCAmelCase  						=			self.vocab_size - 1




						def  _lowercase     ( self				):

												"""simple docstring"""



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

												_lowerCAmelCase  						=			None
												if self.use_token_type_ids:
																		_lowerCAmelCase  						=			ids_tensor([self.batch_size, self.seq_length]   ,       self.type_vocab_size				)

												_lowerCAmelCase  						=			None
												_lowerCAmelCase  						=			None
												_lowerCAmelCase  						=			None
												if self.use_labels:
																		_lowerCAmelCase  						=			ids_tensor([self.batch_size]   ,       self.type_sequence_label_size				)
																		_lowerCAmelCase  						=			ids_tensor([self.batch_size, self.seq_length]   ,       self.num_labels				)
																		_lowerCAmelCase  						=			ids_tensor([self.batch_size]   ,       self.num_choices				)

												_lowerCAmelCase  						=			OpenAIGPTConfig(
												    vocab_size=self.vocab_size   ,       n_embd=self.hidden_size   ,       n_layer=self.num_hidden_layers   ,       n_head=self.num_attention_heads   ,       n_positions=self.max_position_embeddings   ,       pad_token_id=self.pad_token_id   ,       )

												_lowerCAmelCase  						=			ids_tensor([self.num_hidden_layers, self.num_attention_heads]   ,       2				)

												return (
												    config,
												    input_ids,
												    head_mask,
												    token_type_ids,
												    sequence_labels,
												    token_labels,
												    choice_labels,
												)




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

												"""simple docstring"""



												_lowerCAmelCase  						=			OpenAIGPTModel(config=_lowercase				)
												model.to(_lowercase				)
												model.eval()

												_lowerCAmelCase  						=			model(_lowercase   ,       token_type_ids=_lowercase   ,       head_mask=_lowercase				)
												_lowerCAmelCase  						=			model(_lowercase   ,       token_type_ids=_lowercase				)
												_lowerCAmelCase  						=			model(_lowercase				)

												self.parent.assertEqual(result.last_hidden_state.shape   ,       (self.batch_size, self.seq_length, self.hidden_size)				)




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

												"""simple docstring"""



												_lowerCAmelCase  						=			OpenAIGPTLMHeadModel(_lowercase				)
												model.to(_lowercase				)
												model.eval()

												_lowerCAmelCase  						=			model(_lowercase   ,       token_type_ids=_lowercase   ,       labels=_lowercase				)
												self.parent.assertEqual(result.loss.shape   ,       ()				)
												self.parent.assertEqual(result.logits.shape   ,       (self.batch_size, self.seq_length, self.vocab_size)				)




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

												"""simple docstring"""



												_lowerCAmelCase  						=			OpenAIGPTDoubleHeadsModel(_lowercase				)
												model.to(_lowercase				)
												model.eval()

												_lowerCAmelCase  						=			model(_lowercase   ,       token_type_ids=_lowercase   ,       labels=_lowercase				)
												self.parent.assertEqual(result.loss.shape   ,       ()				)
												self.parent.assertEqual(result.logits.shape   ,       (self.batch_size, self.seq_length, self.vocab_size)				)




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

												"""simple docstring"""



												_lowerCAmelCase  						=			self.num_labels
												_lowerCAmelCase  						=			OpenAIGPTForSequenceClassification(_lowercase				)
												model.to(_lowercase				)
												model.eval()

												_lowerCAmelCase  						=			ids_tensor([self.batch_size]   ,       self.type_sequence_label_size				)
												_lowerCAmelCase  						=			model(_lowercase   ,       token_type_ids=_lowercase   ,       labels=_lowercase				)
												self.parent.assertEqual(result.logits.shape   ,       (self.batch_size, self.num_labels)				)




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			self.prepare_config_and_inputs()
												(
												    (
												    _lowerCAmelCase   
												)						,   (
												    _lowerCAmelCase   
												)						,   (
												    _lowerCAmelCase   
												)						,   (
												    _lowerCAmelCase   
												)						,   (
												    _lowerCAmelCase   
												)						,   (
												    _lowerCAmelCase   
												)						,   (
												    _lowerCAmelCase   
												)						,      
												)  						=			config_and_inputs
												_lowerCAmelCase  						=			{
												    """input_ids""": input_ids,
												    """token_type_ids""": token_type_ids,
												    """head_mask""": head_mask,
												}

												return config, inputs_dict






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






						'''simple docstring'''






						_lowercase		:				Dict									=       (
						    (OpenAIGPTModel, OpenAIGPTLMHeadModel, OpenAIGPTDoubleHeadsModel, OpenAIGPTForSequenceClassification)
						    if is_torch_available()
						    else ()
						)
						_lowercase		:				str									=       (
						    (OpenAIGPTLMHeadModel,) if is_torch_available() else ()
						)  # TODO (PVP): Add Double HeadsModel when generate() function is changed accordingly
						_lowercase		:				int									=       (
						    {
						        '''feature-extraction''': OpenAIGPTModel,
						        '''text-classification''': OpenAIGPTForSequenceClassification,
						        '''text-generation''': OpenAIGPTLMHeadModel,
						        '''zero-shot''': OpenAIGPTForSequenceClassification,
						    }
						    if is_torch_available()
						    else {}
						)




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

												"""simple docstring"""



												if pipeline_test_casse_name == "ZeroShotClassificationPipelineTests":
																		# Get `tokenizer does not have a padding token` error for both fast/slow tokenizers.
																		# `OpenAIGPTConfig` was never used in pipeline tests, either because of a missing checkpoint or because a
																		# tiny config could not be created.
																		return True

												return False




						def  _lowercase     ( self   ,       _lowercase   ,       _lowercase   ,       _lowercase=False				):

												"""simple docstring"""



												_lowerCAmelCase  						=			super()._prepare_for_class(_lowercase   ,       _lowercase   ,       return_labels=_lowercase				)

												if return_labels:
																		if model_class.__name__ == "OpenAIGPTDoubleHeadsModel":
																								_lowerCAmelCase  						=			torch.zeros(
																								    (self.model_tester.batch_size, self.model_tester.num_choices, self.model_tester.seq_length)   ,       dtype=torch.long   ,       device=_lowercase   ,       )
																								_lowerCAmelCase  						=			inputs_dict["""labels"""]
																								_lowerCAmelCase  						=			inputs_dict["""labels"""]
																								_lowerCAmelCase  						=			torch.zeros(
																								    (self.model_tester.batch_size, self.model_tester.num_choices)   ,       dtype=torch.long   ,       device=_lowercase   ,       )
																								_lowerCAmelCase  						=			torch.zeros(
																								    self.model_tester.batch_size   ,       dtype=torch.long   ,       device=_lowercase				)
												return inputs_dict




						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			OpenAIGPTModelTester(self				)
												_lowerCAmelCase  						=			ConfigTester(self   ,       config_class=_lowercase   ,       n_embd=37				)




						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_openai_gpt_model(*_lowercase				)




						def  _lowercase     ( self				):

												"""simple docstring"""



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




						def  _lowercase     ( self				):

												"""simple docstring"""



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




						def  _lowercase     ( self				):

												"""simple docstring"""



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




						@slow
						def  _lowercase     ( self				):

												"""simple docstring"""



												for model_name in OPENAI_GPT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																		_lowerCAmelCase  						=			OpenAIGPTModel.from_pretrained(_lowercase				)
																		self.assertIsNotNone(_lowercase				)






@require_torch
class   UpperCAmelCase_					(		unittest.TestCase			):






						'''simple docstring'''






						@slow
						def  _lowercase     ( self				):

												"""simple docstring"""



												_lowerCAmelCase  						=			OpenAIGPTLMHeadModel.from_pretrained("""openai-gpt"""				)
												model.to(_lowercase				)
												_lowerCAmelCase  						=			torch.tensor([[481, 4_735, 544]]   ,       dtype=torch.long   ,       device=_lowercase				)  # the president is
												_lowerCAmelCase  						=			[
												    481,
												    4_735,
												    544,
												    246,
												    963,
												    870,
												    762,
												    239,
												    244,
												    40_477,
												    244,
												    249,
												    719,
												    881,
												    487,
												    544,
												    240,
												    244,
												    603,
												    481,
												]  # the president is a very good man. " \n " i\'m sure he is, " said the

												_lowerCAmelCase  						=			model.generate(_lowercase   ,       do_sample=_lowercase				)
												self.assertListEqual(output_ids[0].tolist()   ,       _lowercase				)


'''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""")
