



'''simple docstring'''






import unittest

from transformers import ElectraConfig, is_torch_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
						import torch

						from transformers import (
						    MODEL_FOR_PRETRAINING_MAPPING,
						    ElectraForCausalLM,
						    ElectraForMaskedLM,
						    ElectraForMultipleChoice,
						    ElectraForPreTraining,
						    ElectraForQuestionAnswering,
						    ElectraForSequenceClassification,
						    ElectraForTokenClassification,
						    ElectraModel,
						)
						from transformers.models.electra.modeling_electra import ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST

class     SCREAMING_SNAKE_CASE:







	"""simple docstring"""






	def __init__(						self      :					int		,      __snake_case      :					Dict		,      __snake_case      :					Optional[Any]=13		,      __snake_case      :					List[str]=7		,      __snake_case      :					int=True		,      __snake_case      :					List[Any]=True		,      __snake_case      :					Optional[Any]=True		,      __snake_case      :					int=True		,      __snake_case      :					Union[str, Any]=99		,      __snake_case      :					int=32		,      __snake_case      :					str=5		,      __snake_case      :					List[str]=4		,      __snake_case      :					Union[str, Any]=37		,      __snake_case      :					Any="gelu"		,      __snake_case      :					Tuple=0.1		,      __snake_case      :					str=0.1		,      __snake_case      :					Optional[Any]=512		,      __snake_case      :					Optional[Any]=16		,      __snake_case      :					Optional[Any]=2		,      __snake_case      :					List[str]=0.02		,      __snake_case      :					Dict=3		,      __snake_case      :					Union[str, Any]=4		,      __snake_case      :					Dict=None		,      )      ->		List[str]:
								UpperCAmelCase			:	Optional[Any]										=		parent
								UpperCAmelCase			:	List[str]										=		batch_size
								UpperCAmelCase			:	Union[str, Any]										=		seq_length
								UpperCAmelCase			:	Optional[Any]										=		is_training
								UpperCAmelCase			:	List[Any]										=		use_input_mask
								UpperCAmelCase			:	List[Any]										=		use_token_type_ids
								UpperCAmelCase			:	List[str]										=		use_labels
								UpperCAmelCase			:	int										=		vocab_size
								UpperCAmelCase			:	Any										=		hidden_size
								UpperCAmelCase			:	str										=		num_hidden_layers
								UpperCAmelCase			:	Optional[Any]										=		num_attention_heads
								UpperCAmelCase			:	Any										=		intermediate_size
								UpperCAmelCase			:	Dict										=		hidden_act
								UpperCAmelCase			:	str										=		hidden_dropout_prob
								UpperCAmelCase			:	Tuple										=		attention_probs_dropout_prob
								UpperCAmelCase			:	Any										=		max_position_embeddings
								UpperCAmelCase			:	Dict										=		type_vocab_size
								UpperCAmelCase			:	List[Any]										=		type_sequence_label_size
								UpperCAmelCase			:	Union[str, Any]										=		initializer_range
								UpperCAmelCase			:	List[Any]										=		num_labels
								UpperCAmelCase			:	Optional[Any]										=		num_choices
								UpperCAmelCase			:	List[str]										=		scope







	def 					A     (						self      :					Tuple		)      ->		int:
								UpperCAmelCase			:	List[str]										=		ids_tensor([self.batch_size, self.seq_length]		,      self.vocab_size		)

								UpperCAmelCase			:	Optional[Any]										=		None
								if self.use_input_mask:
															UpperCAmelCase			:	List[str]										=		random_attention_mask([self.batch_size, self.seq_length]		)

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

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

								UpperCAmelCase			:	Dict										=		self.get_config()

								return (
								    config,
								    input_ids,
								    token_type_ids,
								    input_mask,
								    sequence_labels,
								    token_labels,
								    choice_labels,
								    fake_token_labels,
								)







	def 					A     (						self      :					Optional[int]		)      ->		Union[str, Any]:
								return ElectraConfig(
								    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=__snake_case		,      initializer_range=self.initializer_range		,      )







	def 					A     (						self      :					Optional[Any]		)      ->		Dict:
								(
								    (
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		
								)			:	int										=		self.prepare_config_and_inputs()

								UpperCAmelCase			:	Optional[int]										=		True
								UpperCAmelCase			:	Union[str, Any]										=		floats_tensor([self.batch_size, self.seq_length, self.hidden_size]		)
								UpperCAmelCase			:	Optional[int]										=		ids_tensor([self.batch_size, self.seq_length]		,      vocab_size=2		)

								return (
								    config,
								    input_ids,
								    token_type_ids,
								    input_mask,
								    sequence_labels,
								    token_labels,
								    choice_labels,
								    encoder_hidden_states,
								    encoder_attention_mask,
								)







	def 					A     (						self      :					Union[str, Any]		,      __snake_case      :					Dict		,      __snake_case      :					List[Any]		,      __snake_case      :					Dict		,      __snake_case      :					Dict		,      __snake_case      :					Union[str, Any]		,      __snake_case      :					Dict		,      __snake_case      :					Optional[Any]		,      __snake_case      :					List[Any]		,      )      ->		Optional[Any]:
								UpperCAmelCase			:	Dict										=		ElectraModel(config=__snake_case		)
								model.to(__snake_case		)
								model.eval()
								UpperCAmelCase			:	List[Any]										=		model(__snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		)
								UpperCAmelCase			:	str										=		model(__snake_case		,      token_type_ids=__snake_case		)
								UpperCAmelCase			:	Any										=		model(__snake_case		)
								self.parent.assertEqual(result.last_hidden_state.shape		,      (self.batch_size, self.seq_length, self.hidden_size)		)







	def 					A     (						self      :					Tuple		,      __snake_case      :					Optional[Any]		,      __snake_case      :					Optional[int]		,      __snake_case      :					Any		,      __snake_case      :					Optional[int]		,      __snake_case      :					List[Any]		,      __snake_case      :					Any		,      __snake_case      :					int		,      __snake_case      :					List[Any]		,      __snake_case      :					Optional[Any]		,      )      ->		Optional[Any]:
								UpperCAmelCase			:	Optional[Any]										=		True
								UpperCAmelCase			:	str										=		ElectraModel(__snake_case		)
								model.to(__snake_case		)
								model.eval()
								UpperCAmelCase			:	str										=		model(
								    __snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		,      encoder_hidden_states=__snake_case		,      encoder_attention_mask=__snake_case		,      )
								UpperCAmelCase			:	Tuple										=		model(
								    __snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		,      encoder_hidden_states=__snake_case		,      )
								UpperCAmelCase			:	Dict										=		model(__snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		)
								self.parent.assertEqual(result.last_hidden_state.shape		,      (self.batch_size, self.seq_length, self.hidden_size)		)







	def 					A     (						self      :					str		,      __snake_case      :					int		,      __snake_case      :					int		,      __snake_case      :					Dict		,      __snake_case      :					Tuple		,      __snake_case      :					List[Any]		,      __snake_case      :					Optional[Any]		,      __snake_case      :					Optional[int]		,      __snake_case      :					Any		,      )      ->		List[Any]:
								UpperCAmelCase			:	Any										=		ElectraForMaskedLM(config=__snake_case		)
								model.to(__snake_case		)
								model.eval()
								UpperCAmelCase			:	Optional[Any]										=		model(__snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		,      labels=__snake_case		)
								self.parent.assertEqual(result.logits.shape		,      (self.batch_size, self.seq_length, self.vocab_size)		)







	def 					A     (						self      :					Optional[Any]		,      __snake_case      :					List[Any]		,      __snake_case      :					Optional[Any]		,      __snake_case      :					Dict		,      __snake_case      :					int		,      __snake_case      :					Optional[int]		,      __snake_case      :					Tuple		,      __snake_case      :					List[Any]		,      __snake_case      :					Tuple		,      __snake_case      :					int		,      )      ->		str:
								UpperCAmelCase			:	Tuple										=		ElectraForCausalLM(config=__snake_case		)
								model.to(__snake_case		)
								model.eval()
								UpperCAmelCase			:	List[Any]										=		model(__snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		,      labels=__snake_case		)
								self.parent.assertEqual(result.logits.shape		,      (self.batch_size, self.seq_length, self.vocab_size)		)







	def 					A     (						self      :					int		,      __snake_case      :					List[Any]		,      __snake_case      :					Union[str, Any]		,      __snake_case      :					int		,      __snake_case      :					List[str]		,      __snake_case      :					List[str]		,      __snake_case      :					Optional[int]		,      __snake_case      :					Tuple		,      __snake_case      :					List[Any]		,      )      ->		Any:
								UpperCAmelCase			:	List[str]										=		self.num_labels
								UpperCAmelCase			:	Dict										=		ElectraForTokenClassification(config=__snake_case		)
								model.to(__snake_case		)
								model.eval()
								UpperCAmelCase			:	Optional[Any]										=		model(__snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		,      labels=__snake_case		)
								self.parent.assertEqual(result.logits.shape		,      (self.batch_size, self.seq_length, self.num_labels)		)







	def 					A     (						self      :					Any		,      __snake_case      :					Tuple		,      __snake_case      :					List[str]		,      __snake_case      :					Optional[int]		,      __snake_case      :					Dict		,      __snake_case      :					int		,      __snake_case      :					Any		,      __snake_case      :					str		,      __snake_case      :					Dict		,      )      ->		Any:
								UpperCAmelCase			:	Optional[Any]										=		self.num_labels
								UpperCAmelCase			:	Tuple										=		ElectraForPreTraining(config=__snake_case		)
								model.to(__snake_case		)
								model.eval()
								UpperCAmelCase			:	Tuple										=		model(__snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		,      labels=__snake_case		)
								self.parent.assertEqual(result.logits.shape		,      (self.batch_size, self.seq_length)		)







	def 					A     (						self      :					Any		,      __snake_case      :					str		,      __snake_case      :					Optional[Any]		,      __snake_case      :					Dict		,      __snake_case      :					List[Any]		,      __snake_case      :					Optional[Any]		,      __snake_case      :					str		,      __snake_case      :					List[str]		,      __snake_case      :					Any		,      )      ->		str:
								UpperCAmelCase			:	Dict										=		self.num_labels
								UpperCAmelCase			:	Optional[int]										=		ElectraForSequenceClassification(__snake_case		)
								model.to(__snake_case		)
								model.eval()
								UpperCAmelCase			:	List[str]										=		model(__snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		,      labels=__snake_case		)
								self.parent.assertEqual(result.logits.shape		,      (self.batch_size, self.num_labels)		)







	def 					A     (						self      :					List[Any]		,      __snake_case      :					Optional[Any]		,      __snake_case      :					Any		,      __snake_case      :					Any		,      __snake_case      :					Optional[Any]		,      __snake_case      :					List[Any]		,      __snake_case      :					Optional[int]		,      __snake_case      :					str		,      __snake_case      :					Optional[Any]		,      )      ->		List[Any]:
								UpperCAmelCase			:	Any										=		ElectraForQuestionAnswering(config=__snake_case		)
								model.to(__snake_case		)
								model.eval()
								UpperCAmelCase			:	int										=		model(
								    __snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		,      start_positions=__snake_case		,      end_positions=__snake_case		,      )
								self.parent.assertEqual(result.start_logits.shape		,      (self.batch_size, self.seq_length)		)
								self.parent.assertEqual(result.end_logits.shape		,      (self.batch_size, self.seq_length)		)







	def 					A     (						self      :					int		,      __snake_case      :					List[Any]		,      __snake_case      :					Dict		,      __snake_case      :					Tuple		,      __snake_case      :					Dict		,      __snake_case      :					Any		,      __snake_case      :					str		,      __snake_case      :					Optional[Any]		,      __snake_case      :					Union[str, Any]		,      )      ->		List[str]:
								UpperCAmelCase			:	List[str]										=		self.num_choices
								UpperCAmelCase			:	List[str]										=		ElectraForMultipleChoice(config=__snake_case		)
								model.to(__snake_case		)
								model.eval()
								UpperCAmelCase			:	Tuple										=		input_ids.unsqueeze(1		).expand(-1		,      self.num_choices		,      -1		).contiguous()
								UpperCAmelCase			:	Tuple										=		token_type_ids.unsqueeze(1		).expand(-1		,      self.num_choices		,      -1		).contiguous()
								UpperCAmelCase			:	Any										=		input_mask.unsqueeze(1		).expand(-1		,      self.num_choices		,      -1		).contiguous()
								UpperCAmelCase			:	Any										=		model(
								    __snake_case		,      attention_mask=__snake_case		,      token_type_ids=__snake_case		,      labels=__snake_case		,      )
								self.parent.assertEqual(result.logits.shape		,      (self.batch_size, self.num_choices)		)







	def 					A     (						self      :					List[Any]		)      ->		Tuple:
								UpperCAmelCase			:	int										=		self.prepare_config_and_inputs()
								(
								    (
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		(
								    UpperCAmelCase
								)							,		
								)			:	List[Any]										=		config_and_inputs
								UpperCAmelCase			:	Tuple										=		{'''input_ids''': input_ids, '''token_type_ids''': token_type_ids, '''attention_mask''': input_mask}
								return config, inputs_dict

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







	"""simple docstring"""






	lowerCamelCase__      			=	(
	    (
	        ElectraModel,
	        ElectraForPreTraining,
	        ElectraForMaskedLM,
	        ElectraForCausalLM,
	        ElectraForMultipleChoice,
	        ElectraForTokenClassification,
	        ElectraForSequenceClassification,
	        ElectraForQuestionAnswering,
	    )
	    if is_torch_available()
	    else ()
	)
	lowerCamelCase__      			=	(
	    {
	        """feature-extraction""": ElectraModel,
	        """fill-mask""": ElectraForMaskedLM,
	        """question-answering""": ElectraForQuestionAnswering,
	        """text-classification""": ElectraForSequenceClassification,
	        """text-generation""": ElectraForCausalLM,
	        """token-classification""": ElectraForTokenClassification,
	        """zero-shot""": ElectraForSequenceClassification,
	    }
	    if is_torch_available()
	    else {}
	)
	lowerCamelCase__      			=	True







	def 					A     (						self      :					Union[str, Any]		,      __snake_case      :					int		,      __snake_case      :					int		,      __snake_case      :					Dict=False		)      ->		Union[str, Any]:
								UpperCAmelCase			:	List[Any]										=		super()._prepare_for_class(__snake_case		,      __snake_case		,      return_labels=__snake_case		)

								if return_labels:
															if model_class in get_values(__snake_case		):
																						UpperCAmelCase			:	Tuple										=		torch.zeros(
																						    (self.model_tester.batch_size, self.model_tester.seq_length)		,      dtype=torch.long		,      device=__snake_case		)
								return inputs_dict







	def 					A     (						self      :					Optional[int]		)      ->		Dict:
								UpperCAmelCase			:	List[str]										=		ElectraModelTester(self		)
								UpperCAmelCase			:	Union[str, Any]										=		ConfigTester(self		,      config_class=__snake_case		,      hidden_size=37		)







	def 					A     (						self      :					int		)      ->		List[str]:
								self.config_tester.run_common_tests()







	def 					A     (						self      :					Any		)      ->		Optional[int]:
								UpperCAmelCase			:	str										=		self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_electra_model(*__snake_case		)







	def 					A     (						self      :					List[str]		)      ->		Union[str, Any]:
								UpperCAmelCase			:	Union[str, Any]										=		self.model_tester.prepare_config_and_inputs_for_decoder()
								self.model_tester.create_and_check_electra_model_as_decoder(*__snake_case		)







	def 					A     (						self      :					Any		)      ->		int:
								UpperCAmelCase			:	int										=		self.model_tester.prepare_config_and_inputs()
								for type in ["absolute", "relative_key", "relative_key_query"]:
															UpperCAmelCase			:	List[Any]										=		type
															self.model_tester.create_and_check_electra_model(*__snake_case		)







	def 					A     (						self      :					int		)      ->		Any:
								UpperCAmelCase			:	List[Any]										=		self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_electra_for_masked_lm(*__snake_case		)







	def 					A     (						self      :					Any		)      ->		Optional[Any]:
								UpperCAmelCase			:	int										=		self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_electra_for_token_classification(*__snake_case		)







	def 					A     (						self      :					Dict		)      ->		Dict:
								UpperCAmelCase			:	Dict										=		self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_electra_for_pretraining(*__snake_case		)







	def 					A     (						self      :					Union[str, Any]		)      ->		Union[str, Any]:
								UpperCAmelCase			:	Optional[int]										=		self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_electra_for_sequence_classification(*__snake_case		)







	def 					A     (						self      :					List[str]		)      ->		Any:
								UpperCAmelCase			:	Union[str, Any]										=		self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_electra_for_question_answering(*__snake_case		)







	def 					A     (						self      :					Tuple		)      ->		Tuple:
								UpperCAmelCase			:	str										=		self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_electra_for_multiple_choice(*__snake_case		)







	@slow
	def 					A     (						self      :					List[Any]		)      ->		Optional[Any]:
								for model_name in ELECTRA_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
															UpperCAmelCase			:	Optional[int]										=		ElectraModel.from_pretrained(__snake_case		)
															self.assertIsNotNone(__snake_case		)







	def 					A     (						self      :					int		)      ->		Union[str, Any]:
								UpperCAmelCase			:	Any										=		self.model_tester.prepare_config_and_inputs_for_decoder()
								self.model_tester.create_and_check_electra_for_causal_lm(*__snake_case		)

@require_torch
class     SCREAMING_SNAKE_CASE(							unittest.TestCase      ):







	"""simple docstring"""






	@slow
	def 					A     (						self      :					Union[str, Any]		)      ->		List[Any]:
								UpperCAmelCase			:	str										=		ElectraModel.from_pretrained('''google/electra-small-discriminator'''		)
								UpperCAmelCase			:	Union[str, Any]										=		torch.tensor([[0, 345, 232, 328, 740, 140, 1695, 69, 6078, 1588, 2]]		)
								UpperCAmelCase			:	Union[str, Any]										=		torch.tensor([[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]		)
								UpperCAmelCase			:	int										=		model(__snake_case		,      attention_mask=__snake_case		)[0]
								UpperCAmelCase			:	Any										=		torch.Size((1, 11, 256)		)
								self.assertEqual(output.shape		,      __snake_case		)
								UpperCAmelCase			:	Tuple										=		torch.tensor(
								    [[[0.44_71, 0.68_21, -0.32_65], [0.46_27, 0.52_55, -0.36_68], [0.45_32, 0.33_13, -0.43_44]]]		)

								self.assertTrue(torch.allclose(output[:, 1:4, 1:4]		,      __snake_case		,      atol=1E-4		)		)










'''simple docstring'''






class     SCREAMING_SNAKE_CASE:







	"""simple docstring"""






	def __init__(						self      :					List[Any]		,      __snake_case      :					Dict		)      ->		str:
								UpperCAmelCase			:	str										=		val
								# Number of nodes in left subtree
								UpperCAmelCase			:	Optional[int]										=		0
								UpperCAmelCase			:	str										=		None
								UpperCAmelCase			:	Optional[Any]										=		None
								UpperCAmelCase			:	Dict										=		None







	def 					A     (						self      :					Tuple		,      __snake_case      :					Dict		)      ->		Dict:
								assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

								if self.val < other.val:
															UpperCAmelCase			:	Optional[int]										=		self.right
															UpperCAmelCase			:	Optional[Any]										=		None
															if self.right:
																						UpperCAmelCase			:	Tuple										=		other
															UpperCAmelCase			:	int										=		other
															UpperCAmelCase			:	Dict										=		self.left_tree_size * 2 + 1
															return self
								else:
															UpperCAmelCase			:	int										=		other.right
															UpperCAmelCase			:	List[str]										=		None
															if other.right:
																						UpperCAmelCase			:	Dict										=		self
															UpperCAmelCase			:	Optional[Any]										=		self
															UpperCAmelCase			:	Optional[int]										=		other.left_tree_size * 2 + 1
															return other

class     SCREAMING_SNAKE_CASE:







	"""simple docstring"""






	def __init__(						self      :					Union[str, Any]		,      __snake_case      :					str=None		,      __snake_case      :					Any=None		,      __snake_case      :					Any=0		)      ->		Dict:
								UpperCAmelCase			:	str										=		heap_size
								UpperCAmelCase			:	Tuple										=		bottom_root
								UpperCAmelCase			:	str										=		min_node







	def 					A     (						self      :					Tuple		,      __snake_case      :					Union[str, Any]		)      ->		Optional[Any]:

								# Empty heaps corner cases
								if other.size == 0:
															return None
								if self.size == 0:
															UpperCAmelCase			:	List[str]										=		other.size
															UpperCAmelCase			:	Union[str, Any]										=		other.bottom_root
															UpperCAmelCase			:	Optional[int]										=		other.min_node
															return None
								# Update size
								UpperCAmelCase			:	Tuple										=		self.size + other.size

								# Update min.node
								if self.min_node.val > other.min_node.val:
															UpperCAmelCase			:	Union[str, Any]										=		other.min_node
								# Merge

								# Order roots by left_subtree_size
								UpperCAmelCase			:	List[str]										=		[]
								UpperCAmelCase							,		UpperCAmelCase			:	Optional[int]										=		self.bottom_root, other.bottom_root
								while i or j:
															if i and ((not j) or i.left_tree_size < j.left_tree_size):
																						combined_roots_list.append((i, True)		)
																						UpperCAmelCase			:	Union[str, Any]										=		i.parent
															else:
																						combined_roots_list.append((j, False)		)
																						UpperCAmelCase			:	List[str]										=		j.parent
        # Insert links between them
								for i in range(len(__snake_case		) - 1		):
															if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
																						UpperCAmelCase			:	Union[str, Any]										=		combined_roots_list[i + 1][0]
																						UpperCAmelCase			:	Optional[Any]										=		combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
								UpperCAmelCase			:	Optional[int]										=		combined_roots_list[0][0]
								while i.parent:
															if (
															    (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
															) or (
															    i.left_tree_size == i.parent.left_tree_size
															    and i.left_tree_size != i.parent.parent.left_tree_size
															):
																						# Neighbouring Nodes
																						UpperCAmelCase			:	Optional[int]										=		i.left
																						UpperCAmelCase			:	List[Any]										=		i.parent.parent

																						# Merging trees
																						UpperCAmelCase			:	Optional[int]										=		i.merge_trees(i.parent		)

																						# Updating links
																						UpperCAmelCase			:	Any										=		previous_node
																						UpperCAmelCase			:	str										=		next_node
																						if previous_node:
																													UpperCAmelCase			:	Union[str, Any]										=		i
																						if next_node:
																													UpperCAmelCase			:	Optional[Any]										=		i
															else:
																						UpperCAmelCase			:	Union[str, Any]										=		i.parent
        # Updating self.bottom_root
								while i.left:
															UpperCAmelCase			:	str										=		i.left
								UpperCAmelCase			:	Optional[int]										=		i

								# Update other
								UpperCAmelCase			:	str										=		self.size
								UpperCAmelCase			:	Union[str, Any]										=		self.bottom_root
								UpperCAmelCase			:	Union[str, Any]										=		self.min_node

								# Return the merged heap
								return self







	def 					A     (						self      :					List[Any]		,      __snake_case      :					List[str]		)      ->		List[str]:
								if self.size == 0:
															UpperCAmelCase			:	List[Any]										=		Node(__snake_case		)
															UpperCAmelCase			:	List[str]										=		1
															UpperCAmelCase			:	str										=		self.bottom_root
								else:
															# Create new node
															UpperCAmelCase			:	int										=		Node(__snake_case		)

															# Update size
															self.size += 1

															# update min_node
															if val < self.min_node.val:
																						UpperCAmelCase			:	Optional[int]										=		new_node
															# Put new_node as a bottom_root in heap
															UpperCAmelCase			:	Optional[Any]										=		new_node
															UpperCAmelCase			:	Optional[Any]										=		self.bottom_root
															UpperCAmelCase			:	Union[str, Any]										=		new_node

															# Consecutively merge roots with same left_tree_size
															while (
															    self.bottom_root.parent
															    and self.bottom_root.left_tree_size
															    == self.bottom_root.parent.left_tree_size
															):
																						# Next node
																						UpperCAmelCase			:	List[str]										=		self.bottom_root.parent.parent

																						# Merge
																						UpperCAmelCase			:	int										=		self.bottom_root.merge_trees(self.bottom_root.parent		)

																						# Update Links
																						UpperCAmelCase			:	str										=		next_node
																						UpperCAmelCase			:	int										=		None
																						if next_node:
																													UpperCAmelCase			:	Dict										=		self.bottom_root







	def 					A     (						self      :					Tuple		)      ->		List[str]:
								return self.min_node.val







	def 					A     (						self      :					Optional[Any]		)      ->		int:
								return self.size == 0







	def 					A     (						self      :					List[str]		)      ->		int:
								UpperCAmelCase			:	Tuple										=		self.min_node.val

								# Last element in heap corner case
								if self.size == 1:
															# Update size
															UpperCAmelCase			:	Tuple										=		0

															# Update bottom root
															UpperCAmelCase			:	Optional[int]										=		None

															# Update min_node
															UpperCAmelCase			:	int										=		None

															return min_value
								# No right subtree corner case
								# The structure of the tree implies that this should be the bottom root
								# and there is at least one other root
								if self.min_node.right is None:
															# Update size
															self.size -= 1

															# Update bottom root
															UpperCAmelCase			:	Optional[Any]										=		self.bottom_root.parent
															UpperCAmelCase			:	List[Any]										=		None

															# Update min_node
															UpperCAmelCase			:	int										=		self.bottom_root
															UpperCAmelCase			:	Any										=		self.bottom_root.parent
															while i:
																						if i.val < self.min_node.val:
																													UpperCAmelCase			:	Dict										=		i
																						UpperCAmelCase			:	Union[str, Any]										=		i.parent
															return min_value
								# General case
								# Find the BinomialHeap of the right subtree of min_node
								UpperCAmelCase			:	List[str]										=		self.min_node.right
								UpperCAmelCase			:	Tuple										=		None
								UpperCAmelCase			:	Any										=		bottom_of_new
								UpperCAmelCase			:	str										=		1

								# Size, min_node and bottom_root
								while bottom_of_new.left:
															UpperCAmelCase			:	Tuple										=		size_of_new * 2 + 1
															UpperCAmelCase			:	Union[str, Any]										=		bottom_of_new.left
															if bottom_of_new.val < min_of_new.val:
																						UpperCAmelCase			:	Optional[int]										=		bottom_of_new
        # Corner case of single root on top left path
								if (not self.min_node.left) and (not self.min_node.parent):
															UpperCAmelCase			:	str										=		size_of_new
															UpperCAmelCase			:	str										=		bottom_of_new
															UpperCAmelCase			:	List[str]										=		min_of_new
															# print("Single root, multiple nodes case")
															return min_value
								# Remaining cases
								# Construct heap of right subtree
								UpperCAmelCase			:	int										=		BinomialHeap(
								    bottom_root=__snake_case		,      min_node=__snake_case		,      heap_size=__snake_case		)

								# Update size
								UpperCAmelCase			:	Union[str, Any]										=		self.size - 1 - size_of_new

								# Neighbour nodes
								UpperCAmelCase			:	Any										=		self.min_node.left
								UpperCAmelCase			:	Tuple										=		self.min_node.parent

								# Initialize new bottom_root and min_node
								UpperCAmelCase			:	Optional[int]										=		previous_node or next_node
								UpperCAmelCase			:	int										=		next_node

								# Update links of previous_node and search below for new min_node and
								# bottom_root
								if previous_node:
															UpperCAmelCase			:	List[Any]										=		next_node

															# Update bottom_root and search for min_node below
															UpperCAmelCase			:	Optional[Any]										=		previous_node
															UpperCAmelCase			:	Optional[Any]										=		previous_node
															while self.bottom_root.left:
																						UpperCAmelCase			:	Any										=		self.bottom_root.left
																						if self.bottom_root.val < self.min_node.val:
																													UpperCAmelCase			:	Tuple										=		self.bottom_root
								if next_node:
															UpperCAmelCase			:	Tuple										=		previous_node

															# Search for new min_node above min_node
															UpperCAmelCase			:	Tuple										=		next_node
															while i:
																						if i.val < self.min_node.val:
																													UpperCAmelCase			:	List[str]										=		i
																						UpperCAmelCase			:	Optional[int]										=		i.parent
        # Merge heaps
								self.merge_heaps(__snake_case		)

								return min_value







	def 					A     (						self      :					Union[str, Any]		)      ->		Union[str, Any]:
								UpperCAmelCase			:	Any										=		self.bottom_root
								while top_root.parent:
															UpperCAmelCase			:	Optional[Any]										=		top_root.parent
								# preorder
								UpperCAmelCase			:	List[Any]										=		[]
								self.__traversal(__snake_case		,      __snake_case		)
								return heap_pre_order







	def 					A     (						self      :					List[str]		,      __snake_case      :					Tuple		,      __snake_case      :					int		,      __snake_case      :					Union[str, Any]=0		)      ->		Optional[int]:
								if curr_node:
															preorder.append((curr_node.val, level)		)
															self.__traversal(curr_node.left		,      __snake_case		,      level + 1		)
															self.__traversal(curr_node.right		,      __snake_case		,      level + 1		)
								else:
															preorder.append(('''#''', level)		)







	def __str__(						self      :					Tuple		)      ->		Union[str, Any]:
								if self.is_empty():
															return ""
								UpperCAmelCase			:	Dict										=		self.pre_order()

								return "\n".join(('''-''' * level + str(__snake_case		)) for value, level in preorder_heap		)


# Unit Tests
if __name__ == "__main__":
						import doctest

						doctest.testmod()





