


from __future__ import annotations

import unittest

from transformers import OpenAIGPTConfig, is_tf_available
from transformers.testing_utils import require_tf, slow

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
				import tensorflow as tf

				from transformers.models.openai.modeling_tf_openai import (
				    TF_OPENAI_GPT_PRETRAINED_MODEL_ARCHIVE_LIST,
				    TFOpenAIGPTDoubleHeadsModel,
				    TFOpenAIGPTForSequenceClassification,
				    TFOpenAIGPTLMHeadModel,
				    TFOpenAIGPTModel,
				)







class   __lowercase						:





							"""simple docstring"""







							def __init__(			self ,	lowerCAmelCase__ ,	):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    str 		=				parent
										SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				1_3
										SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				7
										SCREAMING_SNAKE_CASE_		:    List[str] 		=				True
										SCREAMING_SNAKE_CASE_		:    Any 		=				True
										SCREAMING_SNAKE_CASE_		:    Tuple 		=				True
										SCREAMING_SNAKE_CASE_		:    int 		=				True
										SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				True
										SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				9_9
										SCREAMING_SNAKE_CASE_		:    Dict 		=				3_2
										SCREAMING_SNAKE_CASE_		:    Dict 		=				2
										SCREAMING_SNAKE_CASE_		:    str 		=				4
										SCREAMING_SNAKE_CASE_		:    str 		=				3_7
										SCREAMING_SNAKE_CASE_		:    Any 		=				'gelu'
										SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				0.1
										SCREAMING_SNAKE_CASE_		:    List[str] 		=				0.1
										SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				5_1_2
										SCREAMING_SNAKE_CASE_		:    Dict 		=				1_6
										SCREAMING_SNAKE_CASE_		:    Dict 		=				2
										SCREAMING_SNAKE_CASE_		:    int 		=				0.02
										SCREAMING_SNAKE_CASE_		:    str 		=				3
										SCREAMING_SNAKE_CASE_		:    List[str] 		=				4
										SCREAMING_SNAKE_CASE_		:    Tuple 		=				None
										SCREAMING_SNAKE_CASE_		:    str 		=				self.vocab_size - 1






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				ids_tensor([self.batch_size, self.seq_length] ,	self.vocab_size					)

										SCREAMING_SNAKE_CASE_		:    Dict 		=				None
										if self.use_input_mask:
													SCREAMING_SNAKE_CASE_		:    Dict 		=				random_attention_mask([self.batch_size, self.seq_length]					)

										SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				None
										if self.use_token_type_ids:
													SCREAMING_SNAKE_CASE_		:    int 		=				ids_tensor([self.batch_size, self.seq_length] ,	self.type_vocab_size					)

										SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				None
										if self.use_mc_token_ids:
													SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				ids_tensor([self.batch_size, self.num_choices] ,	self.seq_length					)

										SCREAMING_SNAKE_CASE_		:    List[str] 		=				None
										SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				None
										SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				None
										if self.use_labels:
													SCREAMING_SNAKE_CASE_		:    List[Any] 		=				ids_tensor([self.batch_size] ,	self.type_sequence_label_size					)
													SCREAMING_SNAKE_CASE_		:    Tuple 		=				ids_tensor([self.batch_size, self.seq_length] ,	self.num_labels					)
													SCREAMING_SNAKE_CASE_		:    Tuple 		=				ids_tensor([self.batch_size] ,	self.num_choices					)

										SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				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 ,	)

										SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				ids_tensor([self.num_hidden_layers, self.num_attention_heads] ,	2					)

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






							def 				UpperCamelCase__    (			self ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	*lowerCAmelCase__					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Any 		=				TFOpenAIGPTModel(config=lowerCAmelCase__					)
										SCREAMING_SNAKE_CASE_		:    List[str] 		=				{'input_ids': input_ids, 'attention_mask': input_mask, 'token_type_ids': token_type_ids}
										SCREAMING_SNAKE_CASE_		:    Tuple 		=				model(lowerCAmelCase__					)

										SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				[input_ids, input_mask]
										SCREAMING_SNAKE_CASE_		:    Any 		=				model(lowerCAmelCase__					)

										SCREAMING_SNAKE_CASE_		:    int 		=				model(lowerCAmelCase__					)

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






							def 				UpperCamelCase__    (			self ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	*lowerCAmelCase__					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				TFOpenAIGPTLMHeadModel(config=lowerCAmelCase__					)
										SCREAMING_SNAKE_CASE_		:    Tuple 		=				{'input_ids': input_ids, 'attention_mask': input_mask, 'token_type_ids': token_type_ids}
										SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				model(lowerCAmelCase__					)
										self.parent.assertEqual(result.logits.shape ,	(self.batch_size, self.seq_length, self.vocab_size)					)






							def 				UpperCamelCase__    (			self ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	*lowerCAmelCase__					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				TFOpenAIGPTDoubleHeadsModel(config=lowerCAmelCase__					)

										SCREAMING_SNAKE_CASE_		:    List[str] 		=				tf.tile(tf.expand_dims(lowerCAmelCase__ ,	1					) ,	(1, self.num_choices, 1)					)
										SCREAMING_SNAKE_CASE_		:    int 		=				tf.tile(tf.expand_dims(lowerCAmelCase__ ,	1					) ,	(1, self.num_choices, 1)					)
										SCREAMING_SNAKE_CASE_		:    List[str] 		=				tf.tile(tf.expand_dims(lowerCAmelCase__ ,	1					) ,	(1, self.num_choices, 1)					)

										SCREAMING_SNAKE_CASE_		:    Any 		=				{
										    'input_ids': multiple_choice_inputs_ids,
										    'mc_token_ids': mc_token_ids,
										    'attention_mask': multiple_choice_input_mask,
										    'token_type_ids': multiple_choice_token_type_ids,
										}
										SCREAMING_SNAKE_CASE_		:    Any 		=				model(lowerCAmelCase__					)
										self.parent.assertEqual(
										    result.logits.shape ,	(self.batch_size, self.num_choices, self.seq_length, self.vocab_size)					)
										self.parent.assertEqual(result.mc_logits.shape ,	(self.batch_size, self.num_choices)					)






							def 				UpperCamelCase__    (			self ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	*lowerCAmelCase__					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				self.num_labels
										SCREAMING_SNAKE_CASE_		:    str 		=				ids_tensor([self.batch_size] ,	self.type_sequence_label_size					)
										SCREAMING_SNAKE_CASE_		:    Dict 		=				{
										    'input_ids': input_ids,
										    'attention_mask': input_mask,
										    'token_type_ids': token_type_ids,
										    'labels': sequence_labels,
										}
										SCREAMING_SNAKE_CASE_		:    Any 		=				TFOpenAIGPTForSequenceClassification(lowerCAmelCase__					)
										SCREAMING_SNAKE_CASE_		:    List[str] 		=				model(lowerCAmelCase__					)
										self.parent.assertEqual(result.logits.shape ,	(self.batch_size, self.num_labels)					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    str 		=				self.prepare_config_and_inputs()

										(
										    (
										    SCREAMING_SNAKE_CASE_
										)		,			(
										    SCREAMING_SNAKE_CASE_
										)		,			(
										    SCREAMING_SNAKE_CASE_
										)		,			(
										    SCREAMING_SNAKE_CASE_
										)		,			(
										    SCREAMING_SNAKE_CASE_
										)		,			(
										    SCREAMING_SNAKE_CASE_
										)		,			(
										    SCREAMING_SNAKE_CASE_
										)		,			(
										    SCREAMING_SNAKE_CASE_
										)		,			(
										    SCREAMING_SNAKE_CASE_
										)		,			
										)		:    List[Any] 		=				config_and_inputs

										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				{'input_ids': input_ids, 'token_type_ids': token_type_ids, 'attention_mask': input_mask}
										return config, inputs_dict







@require_tf
class   __lowercase						(__SCREAMING_SNAKE_CASE  ,					__SCREAMING_SNAKE_CASE  ,					unittest.TestCase     ):





							"""simple docstring"""







							_UpperCAmelCase						     =	(
							    (TFOpenAIGPTModel, TFOpenAIGPTLMHeadModel, TFOpenAIGPTDoubleHeadsModel, TFOpenAIGPTForSequenceClassification)
							    if is_tf_available()
							    else ()
							)
							_UpperCAmelCase						     =	(
							    (TFOpenAIGPTLMHeadModel,) if is_tf_available() else ()
							)  # TODO (PVP): Add Double HeadsModel when generate() function is changed accordingly
							_UpperCAmelCase						     =	(
							    {
							        """feature-extraction""": TFOpenAIGPTModel,
							        """text-classification""": TFOpenAIGPTForSequenceClassification,
							        """text-generation""": TFOpenAIGPTLMHeadModel,
							        """zero-shot""": TFOpenAIGPTForSequenceClassification,
							    }
							    if is_tf_available()
							    else {}
							)
							_UpperCAmelCase						     =	False
							_UpperCAmelCase						     =	False






							def 				UpperCamelCase__    (			self ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__ ,	lowerCAmelCase__					):





										"""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 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    int 		=				TFOpenAIGPTModelTester(self					)
										SCREAMING_SNAKE_CASE_		:    Tuple 		=				ConfigTester(self ,	config_class=lowerCAmelCase__ ,	n_embd=3_7					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										self.config_tester.run_common_tests()






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    List[str] 		=				self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_openai_gpt_model(*lowerCAmelCase__					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_openai_gpt_lm_head(*lowerCAmelCase__					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_openai_gpt_double_head(*lowerCAmelCase__					)






							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Tuple 		=				self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_openai_gpt_for_sequence_classification(*lowerCAmelCase__					)






							@slow
							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										for model_name in TF_OPENAI_GPT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
													SCREAMING_SNAKE_CASE_		:    Tuple 		=				TFOpenAIGPTModel.from_pretrained(lowerCAmelCase__					)
													self.assertIsNotNone(lowerCAmelCase__					)







@require_tf
class   __lowercase						(unittest.TestCase     ):





							"""simple docstring"""







							@slow
							def 				UpperCamelCase__    (			self					):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_		:    Dict 		=				TFOpenAIGPTLMHeadModel.from_pretrained('openai-gpt'					)
										SCREAMING_SNAKE_CASE_		:    List[Any] 		=				tf.convert_to_tensor([[4_8_1, 4_7_3_5, 5_4_4]] ,	dtype=tf.intaa					)  # the president is
										SCREAMING_SNAKE_CASE_		:    int 		=				[
										    4_8_1,
										    4_7_3_5,
										    5_4_4,
										    2_4_6,
										    9_6_3,
										    8_7_0,
										    7_6_2,
										    2_3_9,
										    2_4_4,
										    4_0_4_7_7,
										    2_4_4,
										    2_4_9,
										    7_1_9,
										    8_8_1,
										    4_8_7,
										    5_4_4,
										    2_4_0,
										    2_4_4,
										    6_0_3,
										    4_8_1,
										]  # the president is a very good man. " \n " i\'m sure he is, " said the

										SCREAMING_SNAKE_CASE_		:    List[str] 		=				model.generate(lowerCAmelCase__ ,	do_sample=lowerCAmelCase__					)
										self.assertListEqual(output_ids[0].numpy().tolist() ,	lowerCAmelCase__					)









from __future__ import annotations

from collections import deque
from queue import Queue
from timeit import timeit

lowerCAmelCase__ :			str         ={
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}






def 	a__ (							A__,			A__							):
			SCREAMING_SNAKE_CASE_		:    Optional[int] 		=				{start}
			SCREAMING_SNAKE_CASE_		:    int 		=				[start]
			SCREAMING_SNAKE_CASE_		:    Queue 		=				Queue()
			queue.put(A__							)
			while not queue.empty():
						SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				queue.get()
						for w in graph[v]:
									if w not in explored:
												explored.add(A__							)
												result.append(A__							)
												queue.put(A__							)
			return result






def 	a__ (							A__,			A__							):
			SCREAMING_SNAKE_CASE_		:    Any 		=				{start}
			SCREAMING_SNAKE_CASE_		:    str 		=				[start]
			SCREAMING_SNAKE_CASE_		:    List[Any] 		=				deque([start]							)
			while queue:
						SCREAMING_SNAKE_CASE_		:    Optional[Any] 		=				queue.popleft()
						for child in graph[v]:
									if child not in visited:
												visited.add(A__							)
												result.append(A__							)
												queue.append(A__							)
			return result






def 	a__ (							A__							):
			SCREAMING_SNAKE_CASE_		:    List[str] 		=				F'''from __main__ import G, {name}'''
			SCREAMING_SNAKE_CASE_		:    Tuple 		=				1_0_0_0_0
			SCREAMING_SNAKE_CASE_		:    Union[str, Any] 		=				timeit(F'''{name}(G, \'A\')''',			setup=A__,			number=A__							)
			print(F'''{name:<35} finished {number} runs in {res:.5f} seconds'''							)


if __name__ == "__main__":
				import doctest

				doctest.testmod()

				benchmark_function('breadth_first_search')
				benchmark_function('breadth_first_search_with_deque')
				# breadth_first_search                finished 10000 runs in 0.20999 seconds
				# breadth_first_search_with_deque     finished 10000 runs in 0.01421 seconds





