




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    __lowerCAmelCase			:







			def __init__(	self   :      Dict   ,   snake_case__   :      Tuple   ,   ):




									"""simple docstring"""


									_UpperCAmelCase													=					parent
									_UpperCAmelCase													=					13
									_UpperCAmelCase													=					7
									_UpperCAmelCase													=					True
									_UpperCAmelCase													=					True
									_UpperCAmelCase													=					True
									_UpperCAmelCase													=					True
									_UpperCAmelCase													=					True
									_UpperCAmelCase													=					99
									_UpperCAmelCase													=					32
									_UpperCAmelCase													=					2
									_UpperCAmelCase													=					4
									_UpperCAmelCase													=					37
									_UpperCAmelCase													=					"gelu"
									_UpperCAmelCase													=					0.1
									_UpperCAmelCase													=					0.1
									_UpperCAmelCase													=					512
									_UpperCAmelCase													=					16
									_UpperCAmelCase													=					2
									_UpperCAmelCase													=					0.02
									_UpperCAmelCase													=					3
									_UpperCAmelCase													=					4
									_UpperCAmelCase													=					None
									_UpperCAmelCase													=					self.vocab_size - 1







			def UpperCamelCase      (	self   :      int				):




									"""simple docstring"""


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

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

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

									_UpperCAmelCase													=					None
									if self.use_mc_token_ids:
															_UpperCAmelCase													=					ids_tensor([self.batch_size, self.num_choices]   ,   self.seq_length				)

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

									_UpperCAmelCase													=					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   ,   )

									_UpperCAmelCase													=					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   :      List[str]   ,   snake_case__   :      Optional[int]   ,   snake_case__   :      int   ,   snake_case__   :      Dict   ,   snake_case__   :      Tuple   ,   snake_case__   :      str   ,   *snake_case__   :      int				):




									"""simple docstring"""


									_UpperCAmelCase													=					TFOpenAIGPTModel(config=snake_case__				)
									_UpperCAmelCase													=					{"input_ids": input_ids, "attention_mask": input_mask, "token_type_ids": token_type_ids}
									_UpperCAmelCase													=					model(snake_case__				)

									_UpperCAmelCase													=					[input_ids, input_mask]
									_UpperCAmelCase													=					model(snake_case__				)

									_UpperCAmelCase													=					model(snake_case__				)

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







			def UpperCamelCase      (	self   :      Optional[int]   ,   snake_case__   :      Tuple   ,   snake_case__   :      Optional[Any]   ,   snake_case__   :      List[Any]   ,   snake_case__   :      str   ,   snake_case__   :      Tuple   ,   *snake_case__   :      int				):




									"""simple docstring"""


									_UpperCAmelCase													=					TFOpenAIGPTLMHeadModel(config=snake_case__				)
									_UpperCAmelCase													=					{"input_ids": input_ids, "attention_mask": input_mask, "token_type_ids": token_type_ids}
									_UpperCAmelCase													=					model(snake_case__				)
									self.parent.assertEqual(result.logits.shape   ,   (self.batch_size, self.seq_length, self.vocab_size)				)







			def UpperCamelCase      (	self   :      Optional[Any]   ,   snake_case__   :      List[str]   ,   snake_case__   :      Tuple   ,   snake_case__   :      str   ,   snake_case__   :      Optional[Any]   ,   snake_case__   :      Dict   ,   snake_case__   :      Union[str, Any]   ,   *snake_case__   :      Dict				):




									"""simple docstring"""


									_UpperCAmelCase													=					TFOpenAIGPTDoubleHeadsModel(config=snake_case__				)

									_UpperCAmelCase													=					tf.tile(tf.expand_dims(snake_case__   ,   1				)   ,   (1, self.num_choices, 1)				)
									_UpperCAmelCase													=					tf.tile(tf.expand_dims(snake_case__   ,   1				)   ,   (1, self.num_choices, 1)				)
									_UpperCAmelCase													=					tf.tile(tf.expand_dims(snake_case__   ,   1				)   ,   (1, self.num_choices, 1)				)

									_UpperCAmelCase													=					{
									    "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,
									}
									_UpperCAmelCase													=					model(snake_case__				)
									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   :      Dict   ,   snake_case__   :      Any   ,   snake_case__   :      Union[str, Any]   ,   snake_case__   :      Optional[int]   ,   snake_case__   :      Union[str, Any]   ,   snake_case__   :      Optional[int]   ,   *snake_case__   :      Optional[int]				):




									"""simple docstring"""


									_UpperCAmelCase													=					self.num_labels
									_UpperCAmelCase													=					ids_tensor([self.batch_size]   ,   self.type_sequence_label_size				)
									_UpperCAmelCase													=					{
									    "input_ids": input_ids,
									    "attention_mask": input_mask,
									    "token_type_ids": token_type_ids,
									    "labels": sequence_labels,
									}
									_UpperCAmelCase													=					TFOpenAIGPTForSequenceClassification(snake_case__				)
									_UpperCAmelCase													=					model(snake_case__				)
									self.parent.assertEqual(result.logits.shape   ,   (self.batch_size, self.num_labels)				)







			def UpperCamelCase      (	self   :      Tuple				):




									"""simple docstring"""


									_UpperCAmelCase													=					self.prepare_config_and_inputs()

									(
									    _UpperCAmelCase  
									)													=					config_and_inputs

									_UpperCAmelCase													=					{"input_ids": input_ids, "token_type_ids": token_type_ids, "attention_mask": input_mask}
									return config, inputs_dict






@require_tf
class    __lowerCAmelCase			(	snake_case__ ,		snake_case__ ,		unittest.TestCase			):
			snake_case_				:			int								=					(
			    (TFOpenAIGPTModel, TFOpenAIGPTLMHeadModel, TFOpenAIGPTDoubleHeadsModel, TFOpenAIGPTForSequenceClassification)
			    if is_tf_available()
			    else ()
			)
			snake_case_				:			Optional[Any]								=					(
			    (TFOpenAIGPTLMHeadModel,) if is_tf_available() else ()
			)  # TODO (PVP): Add Double HeadsModel when generate() function is changed accordingly
			snake_case_				:			int								=					(
			    {
			        "feature-extraction": TFOpenAIGPTModel,
			        "text-classification": TFOpenAIGPTForSequenceClassification,
			        "text-generation": TFOpenAIGPTLMHeadModel,
			        "zero-shot": TFOpenAIGPTForSequenceClassification,
			    }
			    if is_tf_available()
			    else {}
			)
			snake_case_				:			str								=					False
			snake_case_				:			Dict								=					False







			def UpperCamelCase      (	self   :      Any   ,   snake_case__   :      str   ,   snake_case__   :      str   ,   snake_case__   :      Tuple   ,   snake_case__   :      Dict   ,   snake_case__   :      Any				):




									"""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   :      Any				):




									"""simple docstring"""


									_UpperCAmelCase													=					TFOpenAIGPTModelTester(self				)
									_UpperCAmelCase													=					ConfigTester(self   ,   config_class=snake_case__   ,   n_embd=37				)







			def UpperCamelCase      (	self   :      Union[str, Any]				):




									"""simple docstring"""


									self.config_tester.run_common_tests()







			def UpperCamelCase      (	self   :      str				):




									"""simple docstring"""


									_UpperCAmelCase													=					self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_openai_gpt_model(*snake_case__				)







			def UpperCamelCase      (	self   :      Any				):




									"""simple docstring"""


									_UpperCAmelCase													=					self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_openai_gpt_lm_head(*snake_case__				)







			def UpperCamelCase      (	self   :      Tuple				):




									"""simple docstring"""


									_UpperCAmelCase													=					self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_openai_gpt_double_head(*snake_case__				)







			def UpperCamelCase      (	self   :      Dict				):




									"""simple docstring"""


									_UpperCAmelCase													=					self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_openai_gpt_for_sequence_classification(*snake_case__				)







			@slow
			def UpperCamelCase      (	self   :      Dict				):




									"""simple docstring"""


									for model_name in TF_OPENAI_GPT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
															_UpperCAmelCase													=					TFOpenAIGPTModel.from_pretrained(snake_case__				)
															self.assertIsNotNone(snake_case__				)






@require_tf
class    __lowerCAmelCase			(	unittest.TestCase			):







			@slow
			def UpperCamelCase      (	self   :      Optional[Any]				):




									"""simple docstring"""


									_UpperCAmelCase													=					TFOpenAIGPTLMHeadModel.from_pretrained("openai-gpt"				)
									_UpperCAmelCase													=					tf.convert_to_tensor([[481, 4_735, 544]]   ,   dtype=tf.intaa				)  # the president is
									_UpperCAmelCase													=					[
									    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

									_UpperCAmelCase													=					model.generate(snake_case__   ,   do_sample=snake_case__				)
									self.assertListEqual(output_ids[0].numpy().tolist()   ,   snake_case__				)










from __future__ import annotations

from abc import abstractmethod
from collections.abc import Iterable
from typing import Generic, Protocol, TypeVar






class    __lowerCAmelCase			(	UpperCAmelCase__			):







			@abstractmethod
			def __lt__(	self   :      T   ,   snake_case__   :      T				):




									"""simple docstring"""


									pass







			@abstractmethod
			def __gt__(	self   :      T   ,   snake_case__   :      T				):




									"""simple docstring"""


									pass







			@abstractmethod
			def __eq__(	self   :      T   ,   snake_case__   :      object				):




									"""simple docstring"""


									pass




lowercase_     :    Tuple      =			TypeVar('T', bound=Comparable)






class    __lowerCAmelCase			(	Generic[T]			):







			def __init__(	self   :      Optional[int]				):




									"""simple docstring"""


									_UpperCAmelCase													=					[]
									_UpperCAmelCase													=					0







			def __repr__(	self   :      Dict				):




									"""simple docstring"""


									return str(self.h				)







			def UpperCamelCase      (	self   :      Optional[Any]   ,   snake_case__   :      int				):




									"""simple docstring"""


									if child_idx > 0:
															return (child_idx - 1) // 2
									return None







			def UpperCamelCase      (	self   :      Tuple   ,   snake_case__   :      int				):




									"""simple docstring"""


									_UpperCAmelCase													=					2 * parent_idx + 1
									if left_child_index < self.heap_size:
															return left_child_index
									return None







			def UpperCamelCase      (	self   :      Union[str, Any]   ,   snake_case__   :      int				):




									"""simple docstring"""


									_UpperCAmelCase													=					2 * parent_idx + 2
									if right_child_index < self.heap_size:
															return right_child_index
									return None







			def UpperCamelCase      (	self   :      Dict   ,   snake_case__   :      int				):




									"""simple docstring"""


									if index < self.heap_size:
															_UpperCAmelCase													=					index
															_UpperCAmelCase													=					self.left_child_idx(snake_case__				)
															_UpperCAmelCase													=					self.right_child_idx(snake_case__				)
															# check which child is larger than its parent
															if left_child is not None and self.h[left_child] > self.h[violation]:
																					_UpperCAmelCase													=					left_child
															if right_child is not None and self.h[right_child] > self.h[violation]:
																					_UpperCAmelCase													=					right_child
															# if violation indeed exists
															if violation != index:
																					# swap to fix the violation
																					_UpperCAmelCase							,			_UpperCAmelCase													=					self.h[index], self.h[violation]
																					# fix the subsequent violation recursively if any
																					self.max_heapify(snake_case__				)







			def UpperCamelCase      (	self   :      Tuple   ,   snake_case__   :      Iterable[T]				):




									"""simple docstring"""


									_UpperCAmelCase													=					list(snake_case__				)
									_UpperCAmelCase													=					len(self.h				)
									if self.heap_size > 1:
															# max_heapify from right to left but exclude leaves (last level)
															for i in range(self.heap_size // 2 - 1   ,   -1   ,   -1				):
																					self.max_heapify(snake_case__				)







			def UpperCamelCase      (	self   :      Tuple				):




									"""simple docstring"""


									if self.heap_size >= 2:
															_UpperCAmelCase													=					self.h[0]
															_UpperCAmelCase													=					self.h.pop(-1				)
															self.heap_size -= 1
															self.max_heapify(0				)
															return me
									elif self.heap_size == 1:
															self.heap_size -= 1
															return self.h.pop(-1				)
									else:
															raise Exception("Empty heap"				)







			def UpperCamelCase      (	self   :      str   ,   snake_case__   :      T				):




									"""simple docstring"""


									self.h.append(snake_case__				)
									_UpperCAmelCase													=					(self.heap_size - 1) // 2
									self.heap_size += 1
									while idx >= 0:
															self.max_heapify(snake_case__				)
															_UpperCAmelCase													=					(idx - 1) // 2







			def UpperCamelCase      (	self   :      Any				):




									"""simple docstring"""


									_UpperCAmelCase													=					self.heap_size
									for j in range(size - 1   ,   0   ,   -1				):
															_UpperCAmelCase							,			_UpperCAmelCase													=					self.h[j], self.h[0]
															self.heap_size -= 1
															self.max_heapify(0				)
									_UpperCAmelCase													=					size


if __name__ == "__main__":
				import doctest

				# run doc test
				doctest.testmod()

				# demo
				for unsorted in [
				    [0],
				    [2],
				    [3, 5],
				    [5, 3],
				    [5, 5],
				    [0, 0, 0, 0],
				    [1, 1, 1, 1],
				    [2, 2, 3, 5],
				    [0, 2, 2, 3, 5],
				    [2, 5, 3, 0, 2, 3, 0, 3],
				    [6, 1, 2, 7, 9, 3, 4, 5, 10, 8],
				    [1_03, 9, 1, 7, 11, 15, 25, 2_01, 2_09, 1_07, 5],
				    [-45, -2, -5],
				]:
								print(f"""unsorted array: {unsorted}""")

								lowercase_     :    Heap[int]      =			Heap()
								heap.build_max_heap(unsorted)
								print(f"""after build heap: {heap}""")

								print(f"""max value: {heap.extract_max()}""")
								print(f"""after max value removed: {heap}""")

								heap.insert(1_00)
								print(f"""after new value 100 inserted: {heap}""")

								heap.heap_sort()
								print(f"""heap-sorted array: {heap}\n""")




