"""simple docstring"""







from __future__ import annotations

import unittest

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

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


if is_tf_available():
     import tensorflow as tf

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






class      _SCREAMING_SNAKE_CASE							:



   '''simple docstring'''



   def __init__(	self ,				_SCREAMING_SNAKE_CASE ,				):


      '''simple docstring'''

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







   def    _A				(	self	):


      '''simple docstring'''

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

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

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

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

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

      __lowerCamelCase    		=					OpenAIGPTConfig(
          vocab_size=self.vocab_size ,				n_embd=self.hidden_size ,				n_layer=self.num_hidden_layers ,				n_head=self.num_attention_heads ,				n_positions=self.max_position_embeddings ,				pad_token_id=self.pad_token_id ,				)

      __lowerCamelCase    		=					ids_tensor([self.num_hidden_layers, self.num_attention_heads] ,				2	)

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







   def    _A				(	self ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				*_SCREAMING_SNAKE_CASE	):


      '''simple docstring'''

      __lowerCamelCase    		=					TFOpenAIGPTModel(config=_SCREAMING_SNAKE_CASE	)
      __lowerCamelCase    		=					{'input_ids': input_ids, 'attention_mask': input_mask, 'token_type_ids': token_type_ids}
      __lowerCamelCase    		=					model(_SCREAMING_SNAKE_CASE	)

      __lowerCamelCase    		=					[input_ids, input_mask]
      __lowerCamelCase    		=					model(_SCREAMING_SNAKE_CASE	)

      __lowerCamelCase    		=					model(_SCREAMING_SNAKE_CASE	)

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







   def    _A				(	self ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				*_SCREAMING_SNAKE_CASE	):


      '''simple docstring'''

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







   def    _A				(	self ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				*_SCREAMING_SNAKE_CASE	):


      '''simple docstring'''

      __lowerCamelCase    		=					TFOpenAIGPTDoubleHeadsModel(config=_SCREAMING_SNAKE_CASE	)

      __lowerCamelCase    		=					tf.tile(tf.expand_dims(_SCREAMING_SNAKE_CASE ,				1	) ,				(1, self.num_choices, 1)	)
      __lowerCamelCase    		=					tf.tile(tf.expand_dims(_SCREAMING_SNAKE_CASE ,				1	) ,				(1, self.num_choices, 1)	)
      __lowerCamelCase    		=					tf.tile(tf.expand_dims(_SCREAMING_SNAKE_CASE ,				1	) ,				(1, self.num_choices, 1)	)

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







   def    _A				(	self ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				*_SCREAMING_SNAKE_CASE	):


      '''simple docstring'''

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







   def    _A				(	self	):


      '''simple docstring'''

      __lowerCamelCase    		=					self.prepare_config_and_inputs()

      (
          (
          __lowerCamelCase
      )		,(
          __lowerCamelCase
      )		,(
          __lowerCamelCase
      )		,(
          __lowerCamelCase
      )		,(
          __lowerCamelCase
      )		,(
          __lowerCamelCase
      )		,(
          __lowerCamelCase
      )		,(
          __lowerCamelCase
      )		,(
          __lowerCamelCase
      )		,
      )    		=					config_and_inputs

      __lowerCamelCase    		=					{'input_ids': input_ids, 'token_type_ids': token_type_ids, 'attention_mask': input_mask}
      return config, inputs_dict






@require_tf
class      _SCREAMING_SNAKE_CASE							(			UpperCAmelCase    ,				UpperCAmelCase    ,				unittest.TestCase				):



   '''simple docstring'''



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







   def    _A				(	self ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE ,				_SCREAMING_SNAKE_CASE	):


      '''simple docstring'''

      if pipeline_test_casse_name == "ZeroShotClassificationPipelineTests":
         # Get `tokenizer does not have a padding token` error for both fast/slow tokenizers.
         # `OpenAIGPTConfig` was never used in pipeline tests, either because of a missing checkpoint or because a
         # tiny config could not be created.
         return True

      return False







   def    _A				(	self	):


      '''simple docstring'''

      __lowerCamelCase    		=					TFOpenAIGPTModelTester(self	)
      __lowerCamelCase    		=					ConfigTester(self ,				config_class=_SCREAMING_SNAKE_CASE ,				n_embd=37	)







   def    _A				(	self	):


      '''simple docstring'''

      self.config_tester.run_common_tests()







   def    _A				(	self	):


      '''simple docstring'''

      __lowerCamelCase    		=					self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_openai_gpt_model(*_SCREAMING_SNAKE_CASE	)







   def    _A				(	self	):


      '''simple docstring'''

      __lowerCamelCase    		=					self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_openai_gpt_lm_head(*_SCREAMING_SNAKE_CASE	)







   def    _A				(	self	):


      '''simple docstring'''

      __lowerCamelCase    		=					self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_openai_gpt_double_head(*_SCREAMING_SNAKE_CASE	)







   def    _A				(	self	):


      '''simple docstring'''

      __lowerCamelCase    		=					self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_openai_gpt_for_sequence_classification(*_SCREAMING_SNAKE_CASE	)







   @slow
   def    _A				(	self	):


      '''simple docstring'''

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






@require_tf
class      _SCREAMING_SNAKE_CASE							(			unittest.TestCase				):



   '''simple docstring'''



   @slow
   def    _A				(	self	):


      '''simple docstring'''

      __lowerCamelCase    		=					TFOpenAIGPTLMHeadModel.from_pretrained('openai-gpt'	)
      __lowerCamelCase    		=					tf.convert_to_tensor([[481, 4735, 544]] ,				dtype=tf.intaa	)  # the president is
      __lowerCamelCase    		=					[
          481,
          4735,
          544,
          246,
          963,
          870,
          762,
          239,
          244,
          40477,
          244,
          249,
          719,
          881,
          487,
          544,
          240,
          244,
          603,
          481,
      ]  # the president is a very good man. " \n " i\'m sure he is, " said the

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













'''simple docstring'''

class      SCREAMING_SNAKE_CASE__      :







					"""simple docstring"""






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







							"""simple docstring"""
							__UpperCAmelCase	:							Any     =     val
							# Number of nodes in left subtree
							__UpperCAmelCase	:							Dict     =     0
							__UpperCAmelCase	:							int     =     None
							__UpperCAmelCase	:							Optional[int]     =     None
							__UpperCAmelCase	:							List[str]     =     None






					def 		lowerCamelCase_   (   self       :      int		,	UpperCAmelCase_       :      Optional[Any]		):







							"""simple docstring"""
							assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

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






class      SCREAMING_SNAKE_CASE__      :







					"""simple docstring"""






					def __init__(   self       :      Optional[int]		,	UpperCAmelCase_       :      Optional[int]=None		,	UpperCAmelCase_       :      Optional[int]=None		,	UpperCAmelCase_       :      Optional[int]=0		):







							"""simple docstring"""
							__UpperCAmelCase	:							Any     =     heap_size
							__UpperCAmelCase	:							Any     =     bottom_root
							__UpperCAmelCase	:							List[str]     =     min_node
					def 		lowerCamelCase_   (   self       :      List[str]		,	UpperCAmelCase_       :      Dict		):







							"""simple docstring"""

							# Empty heaps corner cases
							if other.size == 0:
									return None
							if self.size == 0:
									__UpperCAmelCase	:							Dict     =     other.size
									__UpperCAmelCase	:							Optional[Any]     =     other.bottom_root
									__UpperCAmelCase	:							str     =     other.min_node
									return None
							# Update size
							__UpperCAmelCase	:							str     =     self.size + other.size

							# Update min.node
							if self.min_node.val > other.min_node.val:
									__UpperCAmelCase	:							Tuple     =     other.min_node
							# Merge

							# Order roots by left_subtree_size
							__UpperCAmelCase	:							int     =     []
							__UpperCAmelCase  ,			__UpperCAmelCase	:							List[str]     =     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	:							Optional[Any]     =     i.parent
									else:
											combined_roots_list.append((j, False)		)
											__UpperCAmelCase	:							Tuple     =     j.parent
        # Insert links between them
							for i in range(len(UpperCAmelCase_		) - 1		):
									if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
											__UpperCAmelCase	:							Optional[Any]     =     combined_roots_list[i + 1][0]
											__UpperCAmelCase	:							Any     =     combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
							__UpperCAmelCase	:							List[str]     =     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	:							List[str]     =     i.left
											__UpperCAmelCase	:							Dict     =     i.parent.parent

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

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

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

							# Return the merged heap
							return self
					def 		lowerCamelCase_   (   self       :      Tuple		,	UpperCAmelCase_       :      Optional[int]		):







							"""simple docstring"""
							if self.size == 0:
									__UpperCAmelCase	:							Optional[Any]     =     Node(UpperCAmelCase_		)
									__UpperCAmelCase	:							Optional[Any]     =     1
									__UpperCAmelCase	:							Optional[Any]     =     self.bottom_root
							else:
									# Create new node
									__UpperCAmelCase	:							Optional[Any]     =     Node(UpperCAmelCase_		)

									# 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	:							Union[str, Any]     =     new_node
									__UpperCAmelCase	:							Optional[Any]     =     self.bottom_root
									__UpperCAmelCase	:							List[str]     =     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	:							Optional[Any]     =     self.bottom_root.parent.parent

											# Merge
											__UpperCAmelCase	:							str     =     self.bottom_root.merge_trees(self.bottom_root.parent		)

											# Update Links
											__UpperCAmelCase	:							int     =     next_node
											__UpperCAmelCase	:							Any     =     None
											if next_node:
													__UpperCAmelCase	:							Any     =     self.bottom_root
					def 		lowerCamelCase_   (   self       :      Any		):







							"""simple docstring"""
							return self.min_node.val
					def 		lowerCamelCase_   (   self       :      str		):







							"""simple docstring"""
							return self.size == 0
					def 		lowerCamelCase_   (   self       :      int		):







							"""simple docstring"""
							__UpperCAmelCase	:							str     =     self.min_node.val

							# Last element in heap corner case
							if self.size == 1:
									# Update size
									__UpperCAmelCase	:							Optional[int]     =     0

									# Update bottom root
									__UpperCAmelCase	:							List[str]     =     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	:							Union[str, Any]     =     self.bottom_root.parent
									__UpperCAmelCase	:							str     =     None

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

							# Size, min_node and bottom_root
							while bottom_of_new.left:
									__UpperCAmelCase	:							str     =     size_of_new * 2 + 1
									__UpperCAmelCase	:							List[str]     =     bottom_of_new.left
									if bottom_of_new.val < min_of_new.val:
											__UpperCAmelCase	:							Union[str, Any]     =     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	:							Optional[Any]     =     size_of_new
									__UpperCAmelCase	:							List[str]     =     bottom_of_new
									__UpperCAmelCase	:							List[Any]     =     min_of_new
									# print("Single root, multiple nodes case")
									return min_value
							# Remaining cases
							# Construct heap of right subtree
							__UpperCAmelCase	:							Union[str, Any]     =     BinomialHeap(
							    bottom_root=UpperCAmelCase_		,	min_node=UpperCAmelCase_		,	heap_size=UpperCAmelCase_		)

							# Update size
							__UpperCAmelCase	:							Any     =     self.size - 1 - size_of_new

							# Neighbour nodes
							__UpperCAmelCase	:							Union[str, Any]     =     self.min_node.left
							__UpperCAmelCase	:							List[str]     =     self.min_node.parent

							# Initialize new bottom_root and min_node
							__UpperCAmelCase	:							Optional[Any]     =     previous_node or next_node
							__UpperCAmelCase	:							Optional[Any]     =     next_node

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

									# Update bottom_root and search for min_node below
									__UpperCAmelCase	:							List[str]     =     previous_node
									__UpperCAmelCase	:							int     =     previous_node
									while self.bottom_root.left:
											__UpperCAmelCase	:							Dict     =     self.bottom_root.left
											if self.bottom_root.val < self.min_node.val:
													__UpperCAmelCase	:							Union[str, Any]     =     self.bottom_root
							if next_node:
									__UpperCAmelCase	:							Tuple     =     previous_node

									# Search for new min_node above min_node
									__UpperCAmelCase	:							Optional[int]     =     next_node
									while i:
											if i.val < self.min_node.val:
													__UpperCAmelCase	:							List[Any]     =     i
											__UpperCAmelCase	:							List[Any]     =     i.parent
        # Merge heaps
							self.merge_heaps(UpperCAmelCase_		)

							return min_value
					def 		lowerCamelCase_   (   self       :      Union[str, Any]		):







							"""simple docstring"""
							__UpperCAmelCase	:							Tuple     =     self.bottom_root
							while top_root.parent:
									__UpperCAmelCase	:							Optional[int]     =     top_root.parent
							# preorder
							__UpperCAmelCase	:							Union[str, Any]     =     []
							self.__traversal(UpperCAmelCase_		,	UpperCAmelCase_		)
							return heap_pre_order
					def 		lowerCamelCase_   (   self       :      Optional[int]		,	UpperCAmelCase_       :      Optional[Any]		,	UpperCAmelCase_       :      int		,	UpperCAmelCase_       :      Dict=0		):







							"""simple docstring"""
							if curr_node:
									preorder.append((curr_node.val, level)		)
									self.__traversal(curr_node.left		,	UpperCAmelCase_		,	level + 1		)
									self.__traversal(curr_node.right		,	UpperCAmelCase_		,	level + 1		)
							else:
									preorder.append(("#", level)		)






					def __str__(   self       :      Optional[int]		):







							"""simple docstring"""
							if self.is_empty():
									return ""
							__UpperCAmelCase	:							Optional[Any]     =     self.pre_order()

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


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

			doctest.testmod()




