

import unittest

from parameterized import parameterized

from transformers import LlamaConfig, is_torch_available, set_seed
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, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
		import torch

		from transformers import LlamaForCausalLM, LlamaForSequenceClassification, LlamaModel, LlamaTokenizer


class SCREAMING_SNAKE_CASE  :






			"""simple docstring"""




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

				"""simple docstring"""


				snake_case_      		= parent
				snake_case_      		= batch_size
				snake_case_      		= seq_length
				snake_case_      		= is_training
				snake_case_      		= use_input_mask
				snake_case_      		= use_token_type_ids
				snake_case_      		= use_labels
				snake_case_      		= vocab_size
				snake_case_      		= hidden_size
				snake_case_      		= num_hidden_layers
				snake_case_      		= num_attention_heads
				snake_case_      		= intermediate_size
				snake_case_      		= hidden_act
				snake_case_      		= hidden_dropout_prob
				snake_case_      		= attention_probs_dropout_prob
				snake_case_      		= max_position_embeddings
				snake_case_      		= type_vocab_size
				snake_case_      		= type_sequence_label_size
				snake_case_      		= initializer_range
				snake_case_      		= num_labels
				snake_case_      		= num_choices
				snake_case_      		= scope


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


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

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

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

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

				snake_case_      		= self.get_config()

				return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				return LlamaConfig(
				    vocab_size=self.vocab_size ,				hidden_size=self.hidden_size ,				num_hidden_layers=self.num_hidden_layers ,				num_attention_heads=self.num_attention_heads ,				intermediate_size=self.intermediate_size ,				hidden_act=self.hidden_act ,				hidden_dropout_prob=self.hidden_dropout_prob ,				attention_probs_dropout_prob=self.attention_probs_dropout_prob ,				max_position_embeddings=self.max_position_embeddings ,				type_vocab_size=self.type_vocab_size ,				is_decoder=__UpperCamelCase ,				initializer_range=self.initializer_range ,				)


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase							):

				"""simple docstring"""


				snake_case_      		= LlamaModel(config=__UpperCamelCase							)
				model.to(__UpperCamelCase							)
				model.eval()
				snake_case_      		= model(__UpperCamelCase ,				attention_mask=__UpperCamelCase							)
				snake_case_      		= model(__UpperCamelCase							)
				self.parent.assertEqual(result.last_hidden_state.shape ,				(self.batch_size, self.seq_length, self.hidden_size)							)


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				):

				"""simple docstring"""


				snake_case_      		= True
				snake_case_      		= LlamaModel(__UpperCamelCase							)
				model.to(__UpperCamelCase							)
				model.eval()
				snake_case_      		= model(
				    __UpperCamelCase ,				attention_mask=__UpperCamelCase ,				encoder_hidden_states=__UpperCamelCase ,				encoder_attention_mask=__UpperCamelCase ,				)
				snake_case_      		= model(
				    __UpperCamelCase ,				attention_mask=__UpperCamelCase ,				encoder_hidden_states=__UpperCamelCase ,				)
				snake_case_      		= model(__UpperCamelCase ,				attention_mask=__UpperCamelCase							)
				self.parent.assertEqual(result.last_hidden_state.shape ,				(self.batch_size, self.seq_length, self.hidden_size)							)


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				):

				"""simple docstring"""


				snake_case_      		= LlamaForCausalLM(config=__UpperCamelCase							)
				model.to(__UpperCamelCase							)
				model.eval()
				snake_case_      		= model(__UpperCamelCase ,				attention_mask=__UpperCamelCase ,				labels=__UpperCamelCase							)
				self.parent.assertEqual(result.logits.shape ,				(self.batch_size, self.seq_length, self.vocab_size)							)


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				__UpperCamelCase ,				):

				"""simple docstring"""


				snake_case_      		= True
				snake_case_      		= True
				snake_case_      		= LlamaForCausalLM(config=__UpperCamelCase							)
				model.to(__UpperCamelCase							)
				model.eval()

				# first forward pass
				snake_case_      		= model(
				    __UpperCamelCase ,				attention_mask=__UpperCamelCase ,				encoder_hidden_states=__UpperCamelCase ,				encoder_attention_mask=__UpperCamelCase ,				use_cache=__UpperCamelCase ,				)
				snake_case_      		= outputs.past_key_values

				# create hypothetical multiple next token and extent to next_input_ids
				snake_case_      		= ids_tensor((self.batch_size, 3) ,				config.vocab_size							)
				snake_case_      		= ids_tensor((self.batch_size, 3) ,				vocab_size=2							)

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

				snake_case_      		= model(
				    __UpperCamelCase ,				attention_mask=__UpperCamelCase ,				encoder_hidden_states=__UpperCamelCase ,				encoder_attention_mask=__UpperCamelCase ,				output_hidden_states=__UpperCamelCase ,				)["hidden_states"][0]
				snake_case_      		= model(
				    __UpperCamelCase ,				attention_mask=__UpperCamelCase ,				encoder_hidden_states=__UpperCamelCase ,				encoder_attention_mask=__UpperCamelCase ,				past_key_values=__UpperCamelCase ,				output_hidden_states=__UpperCamelCase ,				)["hidden_states"][0]

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

				self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]							)

				# test that outputs are equal for slice
				self.parent.assertTrue(torch.allclose(__UpperCamelCase ,				__UpperCamelCase ,				atol=1E-3							)							)







			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= self.prepare_config_and_inputs()
				(
				    snake_case_							
				)      		= config_and_inputs
				snake_case_      		= {"input_ids": input_ids, "attention_mask": input_mask}
				return config, inputs_dict







@require_torch
class SCREAMING_SNAKE_CASE  (		lowercase__							,						lowercase__							,						lowercase__							,						unittest.TestCase							):






			"""simple docstring"""




			__A						  =  (LlamaModel, LlamaForCausalLM, LlamaForSequenceClassification) if is_torch_available() else ()
			__A						  =  (LlamaForCausalLM,) if is_torch_available() else ()
			__A						  =  (
			    {
			        """feature-extraction""": LlamaModel,
			        """text-classification""": LlamaForSequenceClassification,
			        """text-generation""": LlamaForCausalLM,
			        """zero-shot""": LlamaForSequenceClassification,
			    }
			    if is_torch_available()
			    else {}
			)
			__A						  =  False
			__A						  =  False


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= LlamaModelTester(self							)
				snake_case_      		= ConfigTester(self ,				config_class=__UpperCamelCase ,				hidden_size=37							)


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				self.config_tester.run_common_tests()


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= self.model_tester.prepare_config_and_inputs()
				self.model_tester.create_and_check_model(*__UpperCamelCase							)


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= self.model_tester.prepare_config_and_inputs()
				for type in ["absolute", "relative_key", "relative_key_query"]:
					snake_case_      		= type
					self.model_tester.create_and_check_model(*__UpperCamelCase							)


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= self.model_tester.prepare_config_and_inputs_for_common()
				snake_case_      		= 3
				snake_case_      		= input_dict["input_ids"]
				snake_case_      		= input_ids.ne(1							).to(__UpperCamelCase							)
				snake_case_      		= ids_tensor([self.model_tester.batch_size] ,				self.model_tester.type_sequence_label_size							)
				snake_case_      		= LlamaForSequenceClassification(__UpperCamelCase							)
				model.to(__UpperCamelCase							)
				model.eval()
				snake_case_      		= model(__UpperCamelCase ,				attention_mask=__UpperCamelCase ,				labels=__UpperCamelCase							)
				self.assertEqual(result.logits.shape ,				(self.model_tester.batch_size, self.model_tester.num_labels)							)


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= self.model_tester.prepare_config_and_inputs_for_common()
				snake_case_      		= 3
				snake_case_      		= "single_label_classification"
				snake_case_      		= input_dict["input_ids"]
				snake_case_      		= input_ids.ne(1							).to(__UpperCamelCase							)
				snake_case_      		= ids_tensor([self.model_tester.batch_size] ,				self.model_tester.type_sequence_label_size							)
				snake_case_      		= LlamaForSequenceClassification(__UpperCamelCase							)
				model.to(__UpperCamelCase							)
				model.eval()
				snake_case_      		= model(__UpperCamelCase ,				attention_mask=__UpperCamelCase ,				labels=__UpperCamelCase							)
				self.assertEqual(result.logits.shape ,				(self.model_tester.batch_size, self.model_tester.num_labels)							)


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= self.model_tester.prepare_config_and_inputs_for_common()
				snake_case_      		= 3
				snake_case_      		= "multi_label_classification"
				snake_case_      		= input_dict["input_ids"]
				snake_case_      		= input_ids.ne(1							).to(__UpperCamelCase							)
				snake_case_      		= ids_tensor(
				    [self.model_tester.batch_size, config.num_labels] ,				self.model_tester.type_sequence_label_size							).to(torch.float							)
				snake_case_      		= LlamaForSequenceClassification(__UpperCamelCase							)
				model.to(__UpperCamelCase							)
				model.eval()
				snake_case_      		= model(__UpperCamelCase ,				attention_mask=__UpperCamelCase ,				labels=__UpperCamelCase							)
				self.assertEqual(result.logits.shape ,				(self.model_tester.batch_size, self.model_tester.num_labels)							)


			@unittest.skip('LLaMA buffers include complex numbers, which breaks this test'							)
			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				pass







			@parameterized.expand([('linear',), ('dynamic',)]							)
			def 			__lowerCAmelCase (    self ,				__UpperCamelCase							):

				"""simple docstring"""


				snake_case_      		= self.model_tester.prepare_config_and_inputs_for_common()
				snake_case_      		= ids_tensor([1, 10] ,				config.vocab_size							)
				snake_case_      		= ids_tensor([1, int(config.max_position_embeddings * 1.5							)] ,				config.vocab_size							)

				set_seed(42							)  # Fixed seed at init time so the two models get the same random weights
				snake_case_      		= LlamaModel(__UpperCamelCase							)
				original_model.to(__UpperCamelCase							)
				original_model.eval()
				snake_case_      		= original_model(__UpperCamelCase							).last_hidden_state
				snake_case_      		= original_model(__UpperCamelCase							).last_hidden_state

				set_seed(42							)  # Fixed seed at init time so the two models get the same random weights
				snake_case_      		= {"type": scaling_type, "factor": 10.0}
				snake_case_      		= LlamaModel(__UpperCamelCase							)
				scaled_model.to(__UpperCamelCase							)
				scaled_model.eval()
				snake_case_      		= scaled_model(__UpperCamelCase							).last_hidden_state
				snake_case_      		= scaled_model(__UpperCamelCase							).last_hidden_state

				# Dynamic scaling does not change the RoPE embeddings until it receives an input longer than the original
				# maximum sequence length, so the outputs for the short input should match.
				if scaling_type == "dynamic":
					self.assertTrue(torch.allclose(__UpperCamelCase ,				__UpperCamelCase ,				atol=1E-5							)							)
				else:
					self.assertFalse(torch.allclose(__UpperCamelCase ,				__UpperCamelCase ,				atol=1E-5							)							)

				# The output should be different for long inputs
				self.assertFalse(torch.allclose(__UpperCamelCase ,				__UpperCamelCase ,				atol=1E-5							)							)







@require_torch
class SCREAMING_SNAKE_CASE  (		unittest.TestCase							):






			"""simple docstring"""




			@unittest.skip('Logits are not exactly the same, once we fix the instabalities somehow, will update!'							)
			@slow
			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= [1, 3_06, 46_58, 2_78, 65_93, 3_10, 28_34, 3_38]
				snake_case_      		= LlamaForCausalLM.from_pretrained('meta-llama/Llama-2-7b-hf' ,				device_map='auto'							)
				snake_case_      		= model(torch.tensor([input_ids]							)							)
				# Expected mean on dim = -1
				snake_case_      		= torch.tensor([[-6.6550, -4.1227, -4.9859, -3.2406, 0.8262, -3.0033, 1.2964, -3.3699]]							)
				torch.testing.assert_close(out.mean(-1							) ,				__UpperCamelCase ,				atol=1E-2 ,				rtol=1E-2							)
				# slicing logits[0, 0, 0:30]
				# fmt: off
				snake_case_      		= torch.tensor([-12.8281, -7.4453, -0.4639, -8.0625, -7.2500, -8.0000, -6.4883, -7.7695, -7.8438, -7.0312, -6.2188, -7.1328, -1.8496, 1.9961, -8.6250, -6.7227, -12.8281, -6.9492, -7.0742, -7.7852, -7.5820, -7.9062, -6.9375, -7.9805, -8.3438, -8.1562, -8.0469, -7.6250, -7.7422, -7.3398,]							)
				# fmt: on
				torch.testing.assert_close(out[0, 0, :30] ,				__UpperCamelCase ,				atol=1E-5 ,				rtol=1E-5							)


			@unittest.skip('Logits are not exactly the same, once we fix the instabalities somehow, will update!'							)
			@slow
			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= [1, 3_06, 46_58, 2_78, 65_93, 3_10, 28_34, 3_38]
				snake_case_      		= LlamaForCausalLM.from_pretrained('meta-llama/Llama-2-13b-hf' ,				device_map='auto'							)
				snake_case_      		= model(torch.tensor(__UpperCamelCase							)							)
				# Expected mean on dim = -1
				snake_case_      		= torch.tensor([[-2.0622, -1.2794, -1.1638, -0.9788, -1.4603, -1.0238, -1.7893, -1.4411]]							)
				torch.testing.assert_close(out.mean(-1							) ,				__UpperCamelCase ,				atol=1E-2 ,				rtol=1E-2							)
				# slicing logits[0, 0, 0:30]
				# fmt: off
				snake_case_      		= torch.tensor([-8.1406, -8.0547, 2.7461, -1.2344, -0.1448, -1.8262, -1.0020, -1.8154, -1.6895, -1.8516, -2.3574, -0.9277, 3.7598, 6.5742, -1.2998, -0.1177, -8.1406, -2.9688, -2.9199, -3.1699, -3.5254, -2.3555, -2.7988, -3.4141, -2.8262, -4.5195, -3.3379, -3.3164, -2.7832, -3.0273]							)
				# fmt: on
				torch.testing.assert_close(out[0, 0, :30] ,				__UpperCamelCase ,				atol=1E-5 ,				rtol=1E-5							)


			@unittest.skip('Logits are not exactly the same, once we fix the instabalities somehow, will update!'							)
			@slow
			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= [1, 3_06, 46_58, 2_78, 65_93, 3_10, 28_34, 3_38]
				snake_case_      		= LlamaForCausalLM.from_pretrained('meta-llama/Llama-2-13b-chat-hf' ,				device_map='auto'							)
				snake_case_      		= model(torch.tensor(__UpperCamelCase							)							)
				# Expected mean on dim = -1
				snake_case_      		= torch.tensor([[-0.8562, -1.8520, -0.7551, -0.4162, -1.5161, -1.2038, -2.4823, -2.3254]]							)
				torch.testing.assert_close(out.mean(-1							) ,				__UpperCamelCase ,				atol=1E-2 ,				rtol=1E-2							)
				# slicing logits[0, 0, 0:30]
				# fmt: off
				snake_case_      		= torch.tensor([-2.2227, 4.8828, 0.9023, -0.4578, -0.7871, -0.1033, -0.6221, -0.5786, -0.7803, -1.0674, -1.2920, -0.1570, 0.8008, 2.0723, -0.9497, 0.2771, -2.2227, -0.7612, -1.4346, -1.2061, -1.6426, -0.3000, -0.7139, -1.1934, -1.8691, -1.6973, -1.5947, -1.2705, -0.3523, -0.5513]							)
				# fmt: on
				torch.testing.assert_close(out.mean(-1							) ,				__UpperCamelCase ,				atol=1E-2 ,				rtol=1E-2							)


			@unittest.skip(
			    'Logits are not exactly the same, once we fix the instabalities somehow, will update! Also it is gonna be a `too_slow` test'							)
			@slow
			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= [1, 3_06, 46_58, 2_78, 65_93, 3_10, 28_34, 3_38]
				snake_case_      		= LlamaForCausalLM.from_pretrained('meta-llama/Llama-2-70b-hf' ,				device_map='auto'							)
				snake_case_      		= model(torch.tensor(__UpperCamelCase							)							)

				snake_case_      		= torch.tensor(
				    [[-4.2327, -3.3360, -4.6665, -4.7631, -1.8180, -3.4170, -1.4211, -3.1810]] ,				dtype=torch.floataa							)
				torch.testing.assert_close(out.mean(-1							) ,				__UpperCamelCase ,				atol=1E-2 ,				rtol=1E-2							)
				# fmt: off
				snake_case_      		= torch.tensor([-9.4922, -3.9551, 1.7998, -5.6758, -5.1055, -5.8984, -4.8320, -6.8086, -6.5391, -5.6172, -5.5820, -5.5352, 1.7881, 3.6289, -6.5117, -3.4785, -9.5000, -6.0352, -6.8125, -6.0195, -6.6836, -5.4727, -6.2812, -6.0391, -7.3398, -7.4297, -7.4844, -6.5820, -5.8789, -5.5312]							)
				# fmt: on
				torch.testing.assert_close(out[0, 0, :30] ,				__UpperCamelCase ,				atol=1E-5 ,				rtol=1E-5							)







			@unittest.skip('Model is curently gated'							)
			@slow
			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_      		= "Simply put, the theory of relativity states that 1) the laws of physics are the same everywhere in the universe and 2) the passage of time and the length of objects can vary depending on the observer\'s frame of reference.\n\nThe first part of the theory, that the laws of physics are the same everywhere, is known as the \"princi"
				snake_case_      		= "Simply put, the theory of relativity states that "
				snake_case_      		= LlamaTokenizer.from_pretrained('meta-llama/Llama-2-13b-chat-hf'							)
				snake_case_      		= tokenizer.encode(__UpperCamelCase ,				return_tensors='pt'							)
				snake_case_      		= LlamaForCausalLM.from_pretrained(
				    'meta-llama/Llama-2-13b-chat-hf' ,				device_map='sequential' ,				use_safetensors=__UpperCamelCase							)

				# greedy generation outputs
				snake_case_      		= model.generate(__UpperCamelCase ,				max_new_tokens=64 ,				top_p=__UpperCamelCase ,				temperature=1 ,				do_sample=__UpperCamelCase							)
				snake_case_      		= tokenizer.decode(generated_ids[0] ,				skip_special_tokens=__UpperCamelCase							)
				self.assertEqual(__UpperCamelCase ,				__UpperCamelCase							)







class SCREAMING_SNAKE_CASE  :






			"""simple docstring"""




			def __init__(    self ,				__UpperCamelCase ,				__UpperCamelCase							):

				"""simple docstring"""


				snake_case_      		= name
				snake_case_      		= val


			def __str__(    self							):

				"""simple docstring"""


				return f"""{self.__class__.__name__}({self.name}, {self.val})"""







			def __lt__(    self ,				__UpperCamelCase							):

				"""simple docstring"""


				return self.val < other.val







class SCREAMING_SNAKE_CASE  :






			"""simple docstring"""




			def __init__(    self ,				__UpperCamelCase							):

				"""simple docstring"""


				snake_case_      		= {}
				snake_case_      		= {}
				snake_case_      		= self.build_heap(__UpperCamelCase							)


			def __getitem__(    self ,				__UpperCamelCase							):

				"""simple docstring"""


				return self.get_value(__UpperCamelCase							)


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase							):

				"""simple docstring"""


				return (idx - 1) // 2


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase							):

				"""simple docstring"""


				return idx * 2 + 1


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase							):

				"""simple docstring"""


				return idx * 2 + 2


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase							):

				"""simple docstring"""


				return self.heap_dict[key]


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase							):

				"""simple docstring"""


				snake_case_      		= len(__UpperCamelCase							) - 1
				snake_case_      		= self.get_parent_idx(__UpperCamelCase							)

				for idx, i in enumerate(__UpperCamelCase							):
					snake_case_      		= idx
					snake_case_      		= i.val

				for i in range(__UpperCamelCase ,				-1 ,				-1							):
					self.sift_down(__UpperCamelCase ,				__UpperCamelCase							)
				return array


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase ,				__UpperCamelCase							):

				"""simple docstring"""


				while True:
					snake_case_      		= self.get_left_child_idx(__UpperCamelCase							)  # noqa: E741
					snake_case_      		= self.get_right_child_idx(__UpperCamelCase							)

					snake_case_      		= idx
					if l < len(__UpperCamelCase							) and array[l] < array[idx]:
						snake_case_      		= l
					if r < len(__UpperCamelCase							) and array[r] < array[smallest]:
						snake_case_      		= r

					if smallest != idx:
						snake_case_		,       snake_case_      		= array[smallest], array[idx]
						(
						    (
						    snake_case_
						)		,       (
						    snake_case_
						)		,       
						)      		= (
						    self.idx_of_element[array[smallest]],
						    self.idx_of_element[array[idx]],
						)
						snake_case_      		= smallest
					else:
						break


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase							):

				"""simple docstring"""


				snake_case_      		= self.get_parent_idx(__UpperCamelCase							)
				while p >= 0 and self.heap[p] > self.heap[idx]:
					snake_case_		,       snake_case_      		= self.heap[idx], self.heap[p]
					snake_case_		,       snake_case_      		= (
					    self.idx_of_element[self.heap[idx]],
					    self.idx_of_element[self.heap[p]],
					)
					snake_case_      		= p
					snake_case_      		= self.get_parent_idx(__UpperCamelCase							)


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				return self.heap[0]


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				snake_case_		,       snake_case_      		= self.heap[-1], self.heap[0]
				snake_case_		,       snake_case_      		= (
				    self.idx_of_element[self.heap[-1]],
				    self.idx_of_element[self.heap[0]],
				)

				snake_case_      		= self.heap.pop()
				del self.idx_of_element[x]
				self.sift_down(0 ,				self.heap							)
				return x


			def 			__lowerCAmelCase (    self ,				__UpperCamelCase							):

				"""simple docstring"""


				self.heap.append(__UpperCamelCase							)
				snake_case_      		= len(self.heap							) - 1
				snake_case_      		= node.val
				self.sift_up(len(self.heap							) - 1							)


			def 			__lowerCAmelCase (    self							):

				"""simple docstring"""


				return len(self.heap							) == 0







			def 			__lowerCAmelCase (    self ,				__UpperCamelCase ,				__UpperCamelCase							):

				"""simple docstring"""


				assert (
				    self.heap[self.idx_of_element[node]].val > new_value
				), "newValue must be less that current value"
				snake_case_      		= new_value
				snake_case_      		= new_value
				self.sift_up(self.idx_of_element[node]							)







A											=     Node('R', -1)
A											=     Node('B', 6)
A											=     Node('A', 3)
A											=     Node('X', 1)
A											=     Node('E', 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
A											=     MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print('Min Heap - before decrease key')
for i in my_min_heap.heap:
		print(i)

print('Min Heap - After decrease key of node [B -> -17]')
my_min_heap.decrease_key(b, -17)

# After
for i in my_min_heap.heap:
		print(i)

if __name__ == "__main__":
		import doctest

		doctest.testmod()
