



import unittest

import numpy as np

from transformers import (
    GPTSanJapaneseConfig,
    GPTSanJapaneseForConditionalGeneration,
    GPTSanJapaneseModel,
    GPTSanJapaneseTokenizer,
    is_torch_available,
)
from transformers.generation import GenerationConfig
from transformers.testing_utils import require_torch, slow, tooslow, 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

class      snake_case__       :







						"""simple docstring"""




						def __init__(     self      ,     __lowercase      ,     __lowercase=3_6_0_0_0      ,     __lowercase=1_3      ,     __lowercase=7      ,     __lowercase=True      ,     __lowercase=3_2      ,     __lowercase=4_2      ,     __lowercase=5      ,     __lowercase=2      ,     __lowercase=4      ,     __lowercase=2      ,     __lowercase=3_2      ,     __lowercase=8_0      ,     __lowercase=3_3      ,     __lowercase=0.0      ,     __lowercase=1E-6      ,     __lowercase=1_0_0      ,     __lowercase=0.0      ,     )      ->   Tuple:
									"""simple docstring"""




									a__     :		Any		 =						vocab_size
									a__     :		List[Any]		 =						parent
									a__     :		List[Any]		 =						batch_size
									a__     :		Optional[int]		 =						num_contexts
									# For common tests
									a__     :		int		 =						self.num_contexts
									a__     :		List[Any]		 =						is_training
									a__     :		Tuple		 =						hidden_size
									a__     :		int		 =						num_ext_layers
									a__     :		List[Any]		 =						ext_size
									a__     :		Optional[Any]		 =						num_hidden_layers
									a__     :		List[str]		 =						num_attention_heads
									a__     :		Optional[Any]		 =						num_experts
									a__     :		Optional[int]		 =						d_ff
									a__     :		Optional[Any]		 =						d_ext
									a__     :		Tuple		 =						d_spout
									a__     :		List[str]		 =						dropout_rate
									a__     :		Any		 =						layer_norm_epsilon
									a__     :		Optional[Any]		 =						expert_capacity
									a__     :		int		 =						router_jitter_noise

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Optional[Any]:
									"""simple docstring"""




									return GPTSanJapaneseConfig.from_pretrained("""Tanrei/GPTSAN-japanese"""						)

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   List[str]:
									"""simple docstring"""




									a__     :		Optional[Any]		 =						ids_tensor([self.batch_size, self.seq_length]      ,     self.vocab_size						)

									a__     :		List[Any]		 =						self.get_config()

									return (config, input_ids)

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Tuple:
									"""simple docstring"""




									a__     :		str		 =						ids_tensor([self.batch_size, self.seq_length]      ,     self.vocab_size						)

									a__     :		Tuple		 =						self.get_config()

									return (config, {"input_ids": input_ids})

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Union[str, Any]:
									"""simple docstring"""




									return GPTSanJapaneseConfig(
									    vocab_size=self.vocab_size      ,     num_contexts=self.seq_length      ,     d_model=self.hidden_size      ,     d_ff=self.d_ff      ,     d_ext=self.d_ext      ,     d_spout=self.d_spout      ,     num_switch_layers=self.num_hidden_layers - self.num_ext_layers      ,     num_ext_layers=self.num_ext_layers      ,     num_heads=self.num_attention_heads      ,     num_experts=self.num_experts      ,     expert_capacity=self.expert_capacity      ,     dropout_rate=self.dropout_rate      ,     layer_norm_epsilon=self.layer_norm_epsilon      ,     router_jitter_noise=self.router_jitter_noise      ,     )

						def 							SCREAMING_SNAKE_CASE__(     self      ,     __lowercase      ,     __lowercase      ,     )      ->   Any:
									"""simple docstring"""




									a__     :		List[str]		 =						GPTSanJapaneseForConditionalGeneration(config=__lowercase						)
									model.to(__lowercase						)
									model.eval()
									a__     :		Any		 =						model(
									    input_ids=__lowercase      ,     )
									self.parent.assertIsNotNone(__lowercase						)




@require_torch
class      snake_case__       (A__      ,			A__      ,			unittest.TestCase	):







						"""simple docstring"""




						__lowerCAmelCase  :Optional[int]			      =  (GPTSanJapaneseModel,) if is_torch_available() else ()
						__lowerCAmelCase  :Tuple			      =  (
						    {
						        "conversational": GPTSanJapaneseForConditionalGeneration,
						        "feature-extraction": GPTSanJapaneseForConditionalGeneration,
						        "summarization": GPTSanJapaneseForConditionalGeneration,
						        "text2text-generation": GPTSanJapaneseForConditionalGeneration,
						        "translation": GPTSanJapaneseForConditionalGeneration,
						    }
						    if is_torch_available()
						    else {}
						)
						__lowerCAmelCase  :Tuple			      =  False
						__lowerCAmelCase  :Any			      =  False
						__lowerCAmelCase  :Optional[int]			      =  False
						__lowerCAmelCase  :Dict			      =  False
						__lowerCAmelCase  :Tuple			      =  False
						__lowerCAmelCase  :Dict			      =  False
						__lowerCAmelCase  :Optional[int]			      =  False
						__lowerCAmelCase  :List[Any]			      =  False
						# The small GPTSAN_JAPANESE model needs higher percentages for CPU/MP tests
						__lowerCAmelCase  :List[str]			      =  [0.8, 0.9]

						def 							SCREAMING_SNAKE_CASE__(     self      ,     __lowercase      ,     __lowercase      ,     __lowercase      ,     __lowercase      ,     __lowercase						)      ->   Tuple:
									"""simple docstring"""




									if pipeline_test_casse_name == "SummarizationPipelineTests":
												# TODO: fix `_reorder_cache` is not implemented for this model
												return True
									elif pipeline_test_casse_name == "Text2TextGenerationPipelineTests":
												# TODO: check this.
												return True

									return False

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   str:
									"""simple docstring"""




									a__     :		Any		 =						GPTSanJapaneseTester(self						)
									a__     :		int		 =						ConfigTester(self      ,     config_class=__lowercase      ,     d_model=3_7						)

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   List[str]:
									"""simple docstring"""




									GPTSanJapaneseConfig()

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Optional[Any]:
									"""simple docstring"""




									a__     :		List[Any]		 =						self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_model(*__lowercase						)

						@unittest.skip(
						    reason="""skip for now as the computed `max_memory` by `model_split_percents` in the test method will be changed inside `from_pretrained`"""						)
						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Dict:
									"""simple docstring"""




									super().test_model_parallelism()

						@unittest.skip("""Will be fixed soon by reducing the size of the model used for common tests."""						)
						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   List[str]:
									"""simple docstring"""




									pass




@require_torch
class      snake_case__       (A__      ,			A__      ,			unittest.TestCase	):







						"""simple docstring"""




						__lowerCAmelCase  :str			      =  (GPTSanJapaneseForConditionalGeneration,) if is_torch_available() else ()
						__lowerCAmelCase  :int			      =  False
						__lowerCAmelCase  :Optional[int]			      =  False
						__lowerCAmelCase  :int			      =  False
						__lowerCAmelCase  :List[Any]			      =  False
						__lowerCAmelCase  :List[Any]			      =  False
						__lowerCAmelCase  :Optional[Any]			      =  False
						# The small GPTSAN_JAPANESE model needs higher percentages for CPU/MP tests
						__lowerCAmelCase  :Any			      =  [0.8, 0.9]

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   List[Any]:
									"""simple docstring"""




									a__     :		Any		 =						GPTSanJapaneseTester(self						)
									a__     :		List[Any]		 =						ConfigTester(self      ,     config_class=__lowercase      ,     d_model=3_7						)

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Union[str, Any]:
									"""simple docstring"""




									GPTSanJapaneseConfig()

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   int:
									"""simple docstring"""




									a__     :		Dict		 =						self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_model(*__lowercase						)

						@unittest.skip(
						    reason="""skip for now as the computed `max_memory` by `model_split_percents` in the test method will be changed inside `from_pretrained`"""						)
						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Dict:
									"""simple docstring"""




									super().test_model_parallelism()

						@unittest.skip("""Will be fixed soon by reducing the size of the model used for common tests."""						)
						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Dict:
									"""simple docstring"""




									pass

						@slow
						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Dict:
									"""simple docstring"""




									a__     :		int		 =						GPTSanJapaneseForConditionalGeneration.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									a__     :		Optional[int]		 =						GPTSanJapaneseTokenizer.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									a__     :		Union[str, Any]		 =						tokenizer.encode("""武田信玄は"""      ,     return_tensors="""pt"""						)
									a__     :		str		 =						model(__lowercase						)
									a__     :		Any		 =						outputs.logits.detach().cpu().numpy()
									# Output of original model created with mesh-tensoflow
									a__     :		Dict		 =						[
									    # fmt: off
									    [-1_2.0_3_7_8_3_9_8_8_9_5_2_6_3_6_7, -1_2.4_3_3_0_6_1_5_9_9_7_3_1_4_4_5, -1_4.3_3_3_8_4_0_3_7_0_1_7_8_2_2_3, -1_2.4_5_0_3_4_5_9_9_3_0_4_1_9_9_2, -1_1.1_6_6_1_3_7_6_9_5_3_1_2_5,
									    -1_1.9_3_0_1_3_7_6_3_4_2_7_7_3_4_4, -1_0.6_5_9_7_4_0_4_4_7_9_9_8_0_4_7, -1_2.9_0_9_5_7_4_5_0_8_6_6_6_9_9_2, -1_3.2_4_1_0_4_3_0_9_0_8_2_0_3_1_2, -1_3.3_9_8_5_7_9_5_9_7_4_7_3_1_4_5,
									    -1_1.1_0_7_5_2_4_8_7_1_8_2_6_1_7_2, -1_2.3_6_8_5_9_4_1_6_9_6_1_6_7, -2_2.9_7_9_4_3_1_1_5_2_3_4_3_7_5, -1_0.4_8_1_0_6_7_6_5_7_4_7_0_7_0_3, -1_2.4_8_4_0_3_0_7_2_3_5_7_1_7_7_7,
									    -1_2.8_0_7_3_6_0_6_4_9_1_0_8_8_8_7, -1_4.7_6_9_7_0_0_0_5_0_3_5_4_0_0_4, -1_2.2_3_3_5_7_9_6_3_5_6_2_0_1_1_7, -1_3.4_2_8_1_4_5_4_0_8_6_3_0_3_7_1, -2_2.6_2_4_1_7_7_9_3_2_7_3_9_2_5_8],
									    [-7.5_1_1_1_4_9_8_8_3_2_7_0_2_6_4, -8.2_8_1_8_5_1_7_6_8_4_9_3_6_5_2, -7.9_4_3_1_2_7_1_5_5_3_0_3_9_5_5, -7.5_5_0_2_1_3_3_3_6_9_4_4_5_8, -6.4_9_8_6_9_9_6_6_5_0_6_9_5_8,
									    -7.5_8_6_7_9_6_2_8_3_7_2_1_9_2_4, -6.9_7_8_0_8_5_9_9_4_7_2_0_4_5_9, -7.8_3_9_1_4_5_1_8_3_5_6_3_2_3_2, -8.2_1_9_6_4_1_6_8_5_4_8_5_8_4, -8.6_9_5_0_9_1_2_4_7_5_5_8_5_9_4,
									    -6.7_0_6_9_1_0_6_1_0_1_9_8_9_7_5, -6.6_5_8_5_7_9_8_2_6_3_5_4_9_8_0_5, -1_9.5_6_5_6_9_8_6_2_3_6_5_7_2_2_7, -5.3_5_3_8_4_2_7_3_5_2_9_0_5_2_7, -8.3_5_0_6_8_6_0_7_3_3_0_3_2_2_3,
									    -8.0_3_9_3_8_8_6_5_6_6_1_6_2_1_1, -1_0.8_5_6_5_6_9_2_9_0_1_6_1_1_3_3, -7.7_5_1_5_4_4_4_7_5_5_5_5_4_2, -8.8_1_9_0_2_2_1_7_8_6_4_9_9_0_2, -1_9.5_1_5_3_2_7_4_5_3_6_1_3_2_8],
									    [-9.7_3_0_6_6_2_3_4_5_8_8_6_2_3, -1_0.2_2_3_9_2_2_7_2_9_4_9_2_1_8_8, -9.9_3_2_9_8_1_4_9_1_0_8_8_8_6_7, -1_1.8_5_7_8_3_6_7_2_3_3_2_7_6_3_7, -7.6_6_2_6_2_6_2_6_6_4_7_9_4_9_2,
									    -1_1.1_3_5_2_9_1_0_9_9_5_4_8_3_4, -7.7_6_5_0_9_7_6_1_8_1_0_3_0_2_7, -1_1.4_7_2_9_2_3_2_7_8_8_0_8_5_9_4, -9.5_4_3_1_4_9_9_4_8_1_2_0_1_1_7, -1_1.9_0_5_6_3_3_9_2_6_3_9_1_6_0_2,
									    -9.3_6_6_1_6_4_2_0_7_4_5_8_4_9_6, -1_1.5_7_3_4_2_8_1_5_3_9_9_1_7, -2_3.6_9_9_0_0_3_2_1_9_6_0_4_4_9_2, -9.4_2_9_5_9_0_2_2_5_2_1_9_7_2_7, -1_0.4_2_8_3_9_2_4_1_0_2_7_8_3_2,
									    -1_0.5_8_5_2_4_0_3_6_4_0_7_4_7_0_7, -1_0.9_4_7_7_1_9_5_7_3_9_7_4_6_1, -1_1.0_9_5_4_1_6_0_6_9_0_3_0_7_6_2, -1_0.3_9_0_2_4_0_6_6_9_2_5_0_4_8_8, -2_3.7_6_9_3_7_2_9_4_0_0_6_3_4_7_7],
									    [-9.7_2_8_2_6_5_7_6_2_3_2_9_1_0_2, -9.8_5_9_7_1_2_6_0_0_7_0_8_0_0_8, -1_0.0_9_7_2_9_2_9_0_0_0_8_5_4_5, -9.6_7_8_5_2_2_1_0_9_9_8_5_3_5_2, -6.8_7_9_5_1_9_9_3_9_4_2_2_6_0_7,
									    -9.6_8_4_8_7_5_4_8_8_2_8_1_2_5, -4.2_8_0_3_4_2_5_7_8_8_8_7_9_3_9_5, -1_0.0_1_8_9_1_4_2_2_2_7_1_7_2_8_5, -9.3_0_8_4_4_5_9_3_0_4_8_0_9_5_7, -1_0.6_3_3_9_4_5_4_6_5_0_8_7_8_9,
									    -8.0_8_3_6_4_6_7_7_4_2_9_1_9_9_2, -9.0_6_3_0_1_4_9_8_4_1_3_0_8_6, -2_1.9_0_4_2_6_6_3_5_7_4_2_1_8_7_5, -8.9_0_1_6_0_8_4_6_7_1_0_2_0_5, -8.8_4_1_8_7_6_0_2_9_9_6_8_2_6_2,
									    -1_1.8_5_6_7_1_9_9_7_0_7_0_3_1_2_5, -1_2.0_7_9_3_9_8_1_5_5_2_1_2_4_0_2, -1_1.2_3_3_7_5_3_2_0_4_3_4_5_7_0_3, -1_0.1_7_7_3_3_8_6_0_0_1_5_8_6_9_1, -2_1.8_7_2_5_6_6_2_2_3_1_4_4_5_3],
									    [-9.6_6_9_7_6_4_5_1_8_7_3_7_7_9_3, -9.6_1_4_1_9_8_6_8_4_6_9_2_3_8_3, -9.8_1_4_5_1_0_3_4_5_4_5_8_9_8_4, -9.9_9_6_5_0_1_9_2_2_6_0_7_4_2_2, -1_1.3_7_5_6_9_0_4_6_0_2_0_5_0_7_8,
									    -1_0.1_1_3_4_0_5_2_2_7_6_6_1_1_3_3, -1_0.5_4_6_8_6_7_3_7_0_6_0_5_4_6_9, -1_0.0_4_3_6_9_0_6_8_1_4_5_7_5_2, -1_0.9_0_7_8_0_9_2_5_7_5_0_7_3_2_4, -1_0.5_0_4_2_1_6_1_9_4_1_5_2_8_3_2,
									    -1_1.1_2_9_1_9_9_0_2_8_0_1_5_1_3_7, -1_0.1_5_1_1_2_4_0_0_0_5_4_9_3_1_6, -2_1.9_6_5_8_6_7_9_9_6_2_1_5_8_2, -9.0_8_6_3_4_9_4_8_7_3_0_4_6_8_8, -1_1.7_3_0_3_3_9_0_5_0_2_9_2_9_6_9,
									    -1_0.4_6_0_6_6_7_6_1_0_1_6_8_4_5_7, -1_0.2_9_8_0_4_9_9_2_6_7_5_7_8_1_2, -1_0.7_8_4_1_4_8_2_1_6_2_4_7_5_5_9, -1_0.8_4_0_6_9_3_4_7_3_8_1_5_9_1_8, -2_2.0_3_1_5_2_8_4_7_2_9_0_0_3_9],
									    # fmt: on
									]
									a__     :		List[str]		 =						np.array(__lowercase						).flatten()
									a__     :		Any		 =						output_logits[0, :, :2_0].flatten()

									def check(__lowercase      ,     __lowercase      ,     __lowercase=5E-4						):
												return abs(a - b						) < epsilon * max(abs(__lowercase						)      ,     abs(__lowercase						)						)

									self.assertTrue(np.all([check(target[i]      ,     predict[i]						) for i in range(len(__lowercase						)						)]						)						)

						@slow
						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Tuple:
									"""simple docstring"""




									a__     :		str		 =						GPTSanJapaneseForConditionalGeneration.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									a__     :		Optional[int]		 =						GPTSanJapaneseTokenizer.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									model.to(__lowercase						)

									# set deterministically
									a__     :		int		 =						GenerationConfig.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									a__     :		Any		 =						1

									# use different length sentences to test batching
									a__     :		Optional[Any]		 =						[
									    """甲斐なら武田と言うほど""",
									    """織田信長は、""",
									]

									a__     :		Optional[Any]		 =						"""left"""
									a__     :		str		 =						tokenizer(__lowercase      ,     return_tensors="""pt"""      ,     padding=__lowercase						)
									a__     :		Optional[Any]		 =						inputs["""input_ids"""].to(__lowercase						)

									self.assertNotEqual(inputs["""attention_mask"""][0].numpy().tolist()      ,     inputs["""attention_mask"""][1].numpy().tolist()						)

									a__     :		Tuple		 =						model.generate(
									    input_ids=__lowercase      ,     attention_mask=inputs["""attention_mask"""].to(__lowercase						)      ,     max_new_tokens=3      ,     generation_config=__lowercase      ,     )

									a__     :		Any		 =						tokenizer(sentences[0]      ,     return_tensors="""pt"""						).input_ids.to(__lowercase						)
									a__     :		Optional[Any]		 =						model.generate(
									    input_ids=__lowercase      ,     max_new_tokens=3      ,     generation_config=__lowercase						)

									a__     :		Optional[int]		 =						tokenizer(sentences[1]      ,     return_tensors="""pt"""						).input_ids.to(__lowercase						)
									a__     :		List[Any]		 =						model.generate(input_ids=__lowercase      ,     max_new_tokens=3      ,     generation_config=__lowercase						)

									self.assertNotEqual(inputs_non_padded.shape      ,     inputs_padded.shape						)

									a__     :		Dict		 =						tokenizer.batch_decode(__lowercase      ,     skip_special_tokens=__lowercase						)
									a__     :		List[str]		 =						tokenizer.decode(output_non_padded[0]      ,     skip_special_tokens=__lowercase						)
									a__     :		List[Any]		 =						tokenizer.decode(output_padded[0]      ,     skip_special_tokens=__lowercase						)

									a__     :		List[Any]		 =						[
									    """甲斐なら武田と言うほど甲斐の武田""",
									    """織田信長は、このような""",
									]
									self.assertListEqual(__lowercase      ,     __lowercase						)
									self.assertListEqual(__lowercase      ,     [non_padded_sentence, padded_sentence]						)

						@tooslow
						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Dict:
									"""simple docstring"""




									a__     :		Union[str, Any]		 =						GPTSanJapaneseForConditionalGeneration.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									a__     :		Optional[Any]		 =						GPTSanJapaneseTokenizer.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									# Output of original model created with mesh-tensoflow
									a__     :		Optional[Any]		 =						[
									    ("""武田信玄は""", 3_5_6_7_5),
									    ("""武田信玄は、""", 4_5),
									    ("""武田信玄は、この""", 2_9),
									    ("""武田信玄は、このよう""", 3_0_6_4_2),
									    ("""武田信玄は、このような""", 3_5_6_8_0),
									    ("""武田信玄は、このような「""", 8_6_4_0),
									    ("""武田信玄は、このような「武田""", 3_1_6_1_7),
									    ("""武田信玄は、このような「武田家""", 3_0_6_4_6),
									    ("""武田信玄は、このような「武田家の""", 3_1_6_1_7),
									    ("""武田信玄は、このような「武田家の家""", 3_1_3_8_1),
									]
									for input, output in target:
												a__     :		Tuple		 =						tokenizer.encode(__lowercase      ,     return_tensors="""pt"""						)
												a__     :		Any		 =						model(__lowercase						)
												a__     :		Tuple		 =						outputs.logits.detach().cpu().numpy()[0]
												a__     :		List[Any]		 =						np.argmax(output_logits[-1]						)
												self.assertEqual(__lowercase      ,     __lowercase						)

						@slow
						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   List[str]:
									"""simple docstring"""




									a__     :		int		 =						GPTSanJapaneseForConditionalGeneration.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									a__     :		List[Any]		 =						GPTSanJapaneseTokenizer.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									model.to(__lowercase						)

									# set deterministically
									a__     :		List[str]		 =						GenerationConfig.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									a__     :		List[str]		 =						1

									a__     :		int		 =						"""武田信玄は、"""
									a__     :		Optional[int]		 =						tokenizer(__lowercase      ,     return_tensors="""pt"""						).input_ids.to(__lowercase						)
									a__     :		Tuple		 =						tokenizer([input_text, input_text]      ,     return_tensors="""pt"""						).input_ids.to(__lowercase						)

									# spout from uniform and one-hot
									a__     :		Tuple		 =						[
									    # fmt: off
									    [0.8_7_8_8_2_2_0_8, 0.3_8_4_2_6_3_9_6, 0.3_3_2_2_0_2_4_8, 0.4_3_8_9_0_4_0_6, 0.1_6_5_6_2_2_5_2,
									    0.0_4_8_0_3_9_8_5, 0.2_1_1_5_7_2  , 0.2_3_1_8_8_4_7_3, 0.3_7_1_5_3_0_6_8, 0.7_8_3_6_3_7_7 ,
									    0.0_2_1_6_0_1_7_2, 0.3_8_7_6_1_7_1_9, 0.7_5_2_9_0_7_7_2, 0.9_0_1_9_8_8_5_7, 0.3_4_3_6_5_7_7_7,
									    0.6_4_1_6_8_1_6_9, 0.4_4_3_1_8_4_7_1, 0.1_4_5_7_5_7_4_6, 0.9_2_5_6_2_8_8_1, 0.4_0_8_1_2_1_4_8,
									    0.2_9_0_1_9_1_2_2, 0.8_8_8_6_1_5_9_9, 0.6_5_5_2_4_8_4_6, 0.4_3_5_6_3_4_5_6, 0.3_8_1_7_7_1_8_7,
									    0.7_0_8_3_2_9_6_5, 0.8_1_5_2_7_8_9_2, 0.6_8_8_3_2_8_1_2, 0.3_8_8_3_3_1_9_2, 0.4_5_6_1_5_2_2 ,
									    0.1_4_8_2_8_8_1_7, 0.4_7_2_4_8_2_1_3, 0.5_4_3_5_7_3_3_5, 0.8_2_0_0_9_5_6_6, 0.1_3_3_8_8_8_4 ,
									    0.0_2_7_5_5_4_1_7, 0.1_9_7_6_4_6_7_7, 0.2_4_2_2_0_8_4 , 0.0_4_7_5_7_6_7_4, 0.6_5_4_0_9_6_0_6,
									    0.0_8_2_4_5_8_9 , 0.0_3_3_0_4_3_8_3, 0.9_4_3_8_7_6_8_9, 0.9_8_7_6_4_5_0_9, 0.8_2_4_3_3_9_0_1,
									    0.2_7_6_4_6_7_4_1, 0.6_4_9_0_7_4_9_3, 0.7_6_0_0_9_4_0_6, 0.3_0_0_8_7_9_1_5, 0.1_7_9_0_4_6_8_9,
									    0.4_1_6_0_1_7_1_4, 0.6_7_0_4_6_3_9_8, 0.1_0_4_2_2_8_2_2, 0.0_8_4_4_7_3_7_4, 0.0_7_3_5_4_3_4_4,
									    0.6_1_4_2_3_5_6_5, 0.7_0_2_8_4_8_6_6, 0.7_5_3_2_3_3_3 , 0.1_9_7_2_0_3_8 , 0.2_9_5_7_5_6_5_9,
									    0.9_0_5_8_3_8_8_6, 0.2_9_2_6_5_3_0_7, 0.5_0_0_0_0_1_7_5, 0.7_0_4_0_7_6_5_5, 0.8_8_9_3_6_3  ,
									    0.8_1_9_0_4_4_1_8, 0.6_6_8_2_9_1_2_8, 0.6_4_4_6_8_8_1_5, 0.5_6_5_6_3_7_2_3, 0.8_5_6_0_1_8_7_5,
									    0.9_4_9_2_4_6_7_2, 0.0_0_1_6_6_7_6_2, 0.2_5_2_2_0_6_4_3, 0.7_4_5_4_0_2_1_9, 0.6_7_9_9_3_2_4_7,
									    0.1_5_4_9_6_7_5 , 0.3_9_3_8_5_3_5_2, 0.9_2_1_5_3_6_0_7, 0.6_3_7_4_5_9_3_1, 0.2_7_7_5_9_0_4_3,
									    0.8_4_7_0_2_2_9_5, 0.6_5_9_0_4_2_7_1, 0.5_8_6_7_6_6_1_4, 0.8_6_6_6_9_3_6 , 0.3_9_6_0_7_4_3_8,
									    0.7_9_9_5_4_9_8_3, 0.4_2_2_2_0_6_9_7, 0.3_9_6_5_0_3_8_1, 0.7_8_4_9_8_6_4 , 0.5_6_1_5_0_2_0_1,
									    0.1_5_6_7_8_9_2_5, 0.1_4_7_4_6_0_3_2, 0.3_4_5_4_2_1_1_4, 0.4_7_0_2_6_7_8_3, 0.1_1_9_5_6_4_8_9,
									    0.2_5_4_2_1_4_3_5, 0.3_3_7_8_8_9_0_1, 0.6_8_9_3_4_8_4_2, 0.3_6_4_2_4_6_8_5, 0.7_1_7_3_7_8_9_8,
									    0.3_8_9_8_3_4_4_9, 0.9_4_3_9_3_7_7_9, 0.3_9_5_7_5_5_8_8, 0.3_6_6_1_6_5_5_3, 0.8_7_1_0_4_6_6_5,
									    0.6_4_6_3_0_2_0_3, 0.2_2_5_1_6_9_0_5, 0.8_8_2_7_0_8_0_4, 0.1_5_0_3_1_3_3_8, 0.7_5_1_4_4_3_4_5,
									    0.4_6_4_5_9_0_2_5, 0.8_5_3_9_6_4_5_4, 0.8_6_3_5_5_6_4_3, 0.6_5_1_3_9_8_5_1, 0.7_0_2_6_6_0_6_1,
									    0.3_0_2_4_1_3_8_9, 0.8_1_0_5_6_4_9_7, 0.8_8_8_6_5_9_6_9, 0.3_8_7_7_3_8_0_7, 0.7_0_6_3_5_8_4_9,
									    0.9_0_7_1_8_4_5_9, 0.4_3_2_4_5_7_8_9, 0.2_8_0_0_0_6_5_4, 0.4_5_9_3_5_5_6_2, 0.0_8_7_7_3_5_1_9,
									    0.9_5_5_2_1_5_1 , 0.9_3_9_0_1_5_1_1, 0.2_2_4_8_9_2_8_8], # uniform
									    [1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
									     0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
									     0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
									     0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
									     0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
									     0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
									     0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
									     0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
									     0., 0., 0., 0., 0., 0., 0., 0.],
									    # fmt: on
									]

									a__     :		Union[str, Any]		 =						model.generate(
									    input_ids=__lowercase      ,     spout=spouts[0]      ,     max_new_tokens=2_0      ,     generation_config=__lowercase      ,     )

									a__     :		str		 =						model.generate(
									    input_ids=__lowercase      ,     spout=spouts[1]      ,     max_new_tokens=2_0      ,     generation_config=__lowercase      ,     )

									a__     :		str		 =						model.generate(
									    input_ids=__lowercase      ,     spout=__lowercase      ,     max_new_tokens=2_0      ,     generation_config=__lowercase      ,     )

									a__     :		Optional[Any]		 =						tokenizer.decode(outputa[0]						)
									a__     :		Tuple		 =						tokenizer.decode(outputa[0]						)
									a__     :		Any		 =						tokenizer.batch_decode(__lowercase						)

									a__     :		List[Any]		 =						[
									    """武田信玄は、武田氏の滅亡後、武田氏の居城であった甲斐武田氏の居城である""",
									    """武田信玄は、武田家の滅亡を防ぐため、武田家の家臣である武田信虎を討""",
									]
									self.assertListEqual(__lowercase      ,     __lowercase						)
									self.assertListEqual(__lowercase      ,     [outa_sentence, outa_sentence]						)

						@slow
						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   Union[str, Any]:
									"""simple docstring"""




									a__     :		Tuple		 =						GPTSanJapaneseForConditionalGeneration.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									a__     :		Optional[int]		 =						GPTSanJapaneseTokenizer.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									model.to(__lowercase						)

									# set deterministically
									a__     :		Optional[int]		 =						GenerationConfig.from_pretrained("""Tanrei/GPTSAN-japanese"""						)
									a__     :		Union[str, Any]		 =						1

									a__     :		Dict		 =						"""武田信玄"""
									a__     :		Optional[Any]		 =						"""織田信長"""
									a__     :		str		 =						"""は、"""
									a__     :		Union[str, Any]		 =						"""が、"""
									a__     :		List[str]		 =						tokenizer(__lowercase      ,     prefix_text=__lowercase      ,     return_tensors="""pt"""						)
									a__     :		Union[str, Any]		 =						tokenizer(__lowercase      ,     prefix_text=__lowercase      ,     return_tensors="""pt"""						)
									a__     :		Dict		 =						tokenizer([[prefix_text_a, input_text_a], [prefix_text_a, input_text_a]]      ,     return_tensors="""pt"""						)

									a__     :		List[str]		 =						model.generate(
									    input_ids=input_tok_a.input_ids.to(__lowercase						)      ,     token_type_ids=input_tok_a.token_type_ids.to(__lowercase						)      ,     max_new_tokens=2_0      ,     generation_config=__lowercase      ,     )

									a__     :		Optional[Any]		 =						model.generate(
									    input_ids=input_tok_a.input_ids.to(__lowercase						)      ,     token_type_ids=input_tok_a.token_type_ids.to(__lowercase						)      ,     max_new_tokens=2_0      ,     generation_config=__lowercase      ,     )

									a__     :		Optional[int]		 =						model.generate(
									    input_ids=input_tok_a.input_ids.to(__lowercase						)      ,     token_type_ids=input_tok_a.token_type_ids.to(__lowercase						)      ,     attention_mask=input_tok_a.attention_mask.to(__lowercase						)      ,     max_new_tokens=2_0      ,     generation_config=__lowercase      ,     )

									a__     :		Dict		 =						tokenizer.decode(outputa[0]						)
									a__     :		List[str]		 =						tokenizer.decode(outputa[0]						)
									a__     :		str		 =						tokenizer.batch_decode(__lowercase						)

									a__     :		Any		 =						[
									    """武田信玄は、武田氏の祖である武田信虎を、その子・武田信友を擁して""",
									    """織田信長が、織田信長の妻・お市の方を妻として迎えたという逸話が残""",
									]
									self.assertListEqual(__lowercase      ,     __lowercase						)
									self.assertListEqual(__lowercase      ,     [outa_sentence, outa_sentence]						)









from __future__ import annotations

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

class      snake_case__       (A__	):







						"""simple docstring"""




						@abstractmethod
						def __lt__(     self      ,     __lowercase						)      ->   bool:
									"""simple docstring"""




									pass

						@abstractmethod
						def __gt__(     self      ,     __lowercase						)      ->   bool:
									"""simple docstring"""




									pass

						@abstractmethod
						def __eq__(     self      ,     __lowercase						)      ->   bool:
									"""simple docstring"""




									pass




_lowercase	:   List[str]    	=TypeVar("T", bound=Comparable)

class      snake_case__       (Generic[T]	):







						"""simple docstring"""




						def __init__(     self						)      ->   None:
									"""simple docstring"""




									a__     :		list[T]		 =						[]
									a__     :		int		 =						0

						def __repr__(     self						)      ->   str:
									"""simple docstring"""




									return str(self.h						)

						def 							SCREAMING_SNAKE_CASE__(     self      ,     __lowercase						)      ->   int | None:
									"""simple docstring"""




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

						def 							SCREAMING_SNAKE_CASE__(     self      ,     __lowercase						)      ->   int | None:
									"""simple docstring"""




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

						def 							SCREAMING_SNAKE_CASE__(     self      ,     __lowercase						)      ->   int | None:
									"""simple docstring"""




									a__     :		Optional[Any]		 =						2 * parent_idx + 2
									if right_child_index < self.heap_size:
												return right_child_index
									return None

						def 							SCREAMING_SNAKE_CASE__(     self      ,     __lowercase						)      ->   None:
									"""simple docstring"""




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

						def 							SCREAMING_SNAKE_CASE__(     self      ,     __lowercase						)      ->   None:
									"""simple docstring"""




									a__     :		Tuple		 =						list(__lowercase						)
									a__     :		Union[str, Any]		 =						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(__lowercase						)

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   T:
									"""simple docstring"""




									if self.heap_size >= 2:
												a__     :		Tuple		 =						self.h[0]
												a__     :		Union[str, Any]		 =						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 							SCREAMING_SNAKE_CASE__(     self      ,     __lowercase						)      ->   None:
									"""simple docstring"""




									self.h.append(__lowercase						)
									a__     :		Optional[int]		 =						(self.heap_size - 1) // 2
									self.heap_size += 1
									while idx >= 0:
												self.max_heapify(__lowercase						)
												a__     :		Union[str, Any]		 =						(idx - 1) // 2

						def 							SCREAMING_SNAKE_CASE__(     self						)      ->   None:
									"""simple docstring"""




									a__     :		Any		 =						self.heap_size
									for j in range(size - 1      ,     0      ,     -1						):
												a__ ,		a__     :		Dict		 =						self.h[j], self.h[0]
												self.heap_size -= 1
												self.max_heapify(0						)
									a__     :		List[Any]		 =						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],
		    [103, 9, 1, 7, 11, 15, 25, 201, 209, 107, 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(100)
				print(f'after new value 100 inserted: {heap}')

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




