





import argparse

# utilities to import the model weights and config file
import os
import pickle as pkl

# PyTorch + new model classes
import torch
from torch import nn

from transformers import AutoTokenizer, MegaConfig, MegaForMaskedLM


# import the EncoderLayer class used to pretrain
# !! NOTE !! this requires the version of fairseq that is built when you install the Mega source
try:
      from fairseq.modules.mega_layer import MegaEncoderLayer
except ImportError:
      raise ImportError('You need to install the version of fairseq from the Mega repo!')






class    snake_case_				(		nn.Module						):






  def __init__(							self :     str   ,  _snake_case :     int   ,  _snake_case :     Any   ,  _snake_case :     str			)->Tuple:






   '''simple docstring'''

   super().__init__()
   __lowerCAmelCase     :       Optional[int]						=   mega_args
   __lowerCAmelCase     :       str						=   nn.Embedding(lowercase__   ,  self.mega_args.encoder_embed_dim			)
   __lowerCAmelCase     :       str						=   nn.ModuleList([MegaEncoderLayer(self.mega_args			) for _ in range(lowercase__			)]			)
   __lowerCAmelCase     :       List[Any]						=   depth






  def       UpperCAmelCase__						(							self :     Union[str, Any]   ,  _snake_case :     List[str]   ,  _snake_case :     int   ,  _snake_case :     Union[str, Any]=True   ,  _snake_case :     Tuple=0			)->str:






   '''simple docstring'''

   if batch_first:
    __lowerCAmelCase     :       Optional[int]						=   input_ids.T

   # to make things more confusing, Mega expects the attention mask to
   # be (batch, time), but with values of 0 (normal token) and 1 (ignore token)
   # which is the opposite of what HF returns
   if ignore_mask_value == 0:
    __lowerCAmelCase     :       Union[str, Any]						=   1 - attention_mask

   # get token embeddings from IDs
   __lowerCAmelCase     :       List[Any]						=   self.embedding_layer(lowercase__			)

   # pass through the Mega layers
   # input is (time, batch, encoder dim) and output is the same
   for encoder in self.encoders:
    __lowerCAmelCase     :       Optional[Any]						=   encoder(lowercase__   ,  lowercase__			)

   # return according to the shape specified
   if batch_first:
    # (T, B, H) --> (B, T, H)
    return torch.transpose(lowercase__   ,  0   ,  1			)
   else:
    return embeds






class    snake_case_				(		nn.Module						):






  def __init__(							self :     Union[str, Any]   ,  _snake_case :     Optional[int]   ,  _snake_case :     int   ,  _snake_case :     List[str]			)->List[Any]:






   '''simple docstring'''

   super().__init__()
   __lowerCAmelCase     :       str						=   MegaLM(lowercase__   ,  lowercase__   ,  lowercase__			)
   __lowerCAmelCase     :       int						=   nn.Linear(mega_args.encoder_embed_dim   ,  lowercase__			)
   __lowerCAmelCase     :       str						=   nn.Dropout(p=0.1			)






  def       UpperCAmelCase__						(							self :     Tuple   ,  _snake_case :     int   ,  _snake_case :     Optional[Any]   ,  _snake_case :     Optional[Any]=True   ,  _snake_case :     Union[str, Any]=0			)->Any:






   '''simple docstring'''

   __lowerCAmelCase     :       Dict						=   self.mega(lowercase__   ,  lowercase__   ,  lowercase__   ,  lowercase__			)
   return self.mlm_head(self.dropout(lowercase__			)			)






def        _SCREAMING_SNAKE_CASE		(			SCREAMING_SNAKE_CASE		:Tuple    ,    SCREAMING_SNAKE_CASE		:Any    ,    SCREAMING_SNAKE_CASE		:str    )			->    List[str]:

 with open(os.path.join(SCREAMING_SNAKE_CASE_    ,    """model_args.pkl"""    )    ,    """rb"""    ) as f:
  __lowerCAmelCase     :       List[str]						=   pkl.load(SCREAMING_SNAKE_CASE_    )

 # load the original encoder
 __lowerCAmelCase     :       Optional[int]						=   OriginalMegaForMaskedLM(**SCREAMING_SNAKE_CASE_    ).eval()

 # load its weights
 print(
     """Original Mega encoder:"""    ,    original_mlm.mega.load_state_dict(
         torch.load(os.path.join(SCREAMING_SNAKE_CASE_    ,    """encoder_weights.pt"""    )    ,    map_location="""cpu"""    )    )    ,    )
 print(
     """Original Mega MLM layer:"""    ,    original_mlm.mlm_head.load_state_dict(
         torch.load(os.path.join(SCREAMING_SNAKE_CASE_    ,    """mlm_head_weights.pt"""    )    ,    map_location="""cpu"""    )    )    ,    )

 # create a new config from the old one
 __lowerCAmelCase     :       Optional[Any]						=   MegaConfig(
     num_hidden_layers=mega_original_args["""depth"""]    ,    vocab_size=mega_original_args["""vocab_size"""]    ,    hidden_size=mega_original_args["""mega_args"""].encoder_embed_dim    ,    shared_representation_size=mega_original_args["""mega_args"""].encoder_z_dim    ,    intermediate_size=mega_original_args["""mega_args"""].encoder_hidden_dim    ,    ema_projection_size=mega_original_args["""mega_args"""].encoder_n_dim    ,    dropout_prob=mega_original_args["""mega_args"""].dropout    ,    attention_probs_dropout_prob=mega_original_args["""mega_args"""].attention_dropout    ,    hidden_dropout_prob=mega_original_args["""mega_args"""].hidden_dropout    ,    activation=mega_original_args["""mega_args"""].activation_fn    ,    attention_activation=mega_original_args["""mega_args"""].attention_activation_fn    ,    bidirectional=mega_original_args["""mega_args"""].bidirectional    ,    use_chunking=mega_original_args["""mega_args"""].encoder_chunk_size > 0    ,    chunk_size=mega_original_args["""mega_args"""].encoder_chunk_size    ,    truncation=mega_original_args["""mega_args"""].truncation_length    ,    normalization_type=mega_original_args["""mega_args"""].normalization_type    ,    normalize_before_mega=SCREAMING_SNAKE_CASE_    ,    norm_affine=SCREAMING_SNAKE_CASE_    ,    use_feature_dropout=mega_original_args["""mega_args"""].feature_dropout    ,    relative_positional_bias=mega_original_args["""mega_args"""].rel_pos_bias    ,    max_positions=mega_original_args["""mega_args"""].max_source_positions    ,    nffn_hidden_size=mega_original_args["""mega_args"""].encoder_ffn_embed_dim    ,    normalize_before_ffn=mega_original_args["""mega_args"""].normalize_before    ,    nffn_activation_dropout_prob=0.0    ,    add_token_type_embeddings=SCREAMING_SNAKE_CASE_    ,    add_lm_hidden_dense_layer=SCREAMING_SNAKE_CASE_    ,    )

 __lowerCAmelCase     :       Tuple						=   MegaForMaskedLM(SCREAMING_SNAKE_CASE_    ).eval()

 # the originl checkpoint just uses nn.Embedding for the word embeddings
 # we use a wrapper module for embeddings to add support for positional embeddings
 __lowerCAmelCase     :       int						=   original_mlm.mega.embedding_layer.weight

 # modify the state dictionary of the original checkpoint to account for naming issues in the Hugging Face
 # ecosystem -- any names containing "beta" or "gamma" aren't safe to use and are renamed upon _load_pretrained,
 # also renaming previously confusing parameter names
 __lowerCAmelCase     :       Optional[Any]						=   original_mlm.mega.encoders.state_dict()
 __lowerCAmelCase     :       Tuple						=   {}
 for module_name in original_state_dict.keys():
  __lowerCAmelCase     :       int						=   None
  # have to handle gamma, beta, and alpha differently due to their use
  # in multiple modules within the original repository;
  # beta is used in EMA, MovingAverageGatedAttention, and RotaryRelativePositionalBias, and must be renamed due to flax/tf weights
  # the EMA sublayer was renamed from "move" to "ema_gate" for readability, so that is also done here
  if "beta" in module_name:
   # EMA sub-layers were always called "move" in the original repo
   if "move.beta" in module_name:
    __lowerCAmelCase     :       List[str]						=   module_name.replace("""move.beta"""    ,    """ema_gate.ema_expansion_matrix"""    )
   elif "mega_layer.beta" in module_name:
    __lowerCAmelCase     :       Union[str, Any]						=   module_name.replace("""beta"""    ,    """qk_bias"""    )
   else:
    __lowerCAmelCase     :       Optional[int]						=   module_name.replace("""beta"""    ,    """b_param"""    )
        # beta is used in EMA and MovingAverageGatedAttention, and must be renamed due to flax/tf weights
  elif "gamma" in module_name:
   if "move.gamma" in module_name:
    __lowerCAmelCase     :       Optional[Any]						=   module_name.replace("""move.gamma"""    ,    """ema_gate.kernel_projection_matrix"""    )
   elif "mega_layer.gamma" in module_name:
    __lowerCAmelCase     :       Tuple						=   module_name.replace("""gamma"""    ,    """qk_weight"""    )
   else:
    __lowerCAmelCase     :       Any						=   module_name.replace("""gamma"""    ,    """g_param"""    )
        # alpha is used in EMA and positional bias; renaming to improve readability
  elif "move.alpha" in module_name:
   __lowerCAmelCase     :       Optional[Any]						=   module_name.replace("""move.alpha"""    ,    """ema_gate.decay_factor"""    )
  # delta is only used in EMA; renaming to improve readability
  elif "move.delta" in module_name:
   __lowerCAmelCase     :       Optional[int]						=   module_name.replace("""move.delta"""    ,    """ema_gate.damping_factor"""    )
  # omega is only used in EMA; renaming to improve readability
  elif "omega" in module_name:
   __lowerCAmelCase     :       Optional[Any]						=   module_name.replace("""move.omega"""    ,    """ema_gate.residual_weight"""    )

  if new_module_name:
   __lowerCAmelCase     :       List[str]						=   new_module_name

 if len(SCREAMING_SNAKE_CASE_    ) != 0:
  print(F'''Renaming these keys: {updated_keys.keys()}'''    )
 else:
  print("""No need to rename state dict entries"""    )
 for old, new in updated_keys.items():
  __lowerCAmelCase     :       str						=   original_state_dict.pop(SCREAMING_SNAKE_CASE_    )

 # now attempt to load the state dictionary with updated names
 # note that we now call it `mega.layers` instead of `mega.encoders` due to hugging face style
 print("""HF Mega encoder:"""    ,    hf_mlm.mega.layers.load_state_dict(SCREAMING_SNAKE_CASE_    )    )

 # load the MLM head weights directly
 print(
     """HF Mega MLM layer:"""    ,    hf_mlm.mlm_head.load_state_dict(
         torch.load(os.path.join(SCREAMING_SNAKE_CASE_    ,    """mlm_head_weights.pt"""    )    ,    map_location="""cpu"""    )    )    ,    )

 # test on a randomly generated input sequence
 __lowerCAmelCase     :       Optional[Any]						=   torch.randint(0    ,    hf_config.vocab_size    ,    size=(4, 256)    )
 __lowerCAmelCase     :       int						=   torch.ones_like(SCREAMING_SNAKE_CASE_    )
 # mask a few tokens to make sure masking is applied appropriately :)
 __lowerCAmelCase     :       Dict						=   0

 # run forward passes
 __lowerCAmelCase     :       List[str]						=   original_mlm(SCREAMING_SNAKE_CASE_    ,    SCREAMING_SNAKE_CASE_    ,    batch_first=SCREAMING_SNAKE_CASE_    ,    ignore_mask_value=0    )
 __lowerCAmelCase     :       int						=   hf_mlm(SCREAMING_SNAKE_CASE_    ,    SCREAMING_SNAKE_CASE_    )[0]

 # print shapes and diff
 print(F'''original output {original_output.shape}'''    )
 print(F'''hf output {hf_output.shape}'''    )
 print(F'''max diff: {(original_output - hf_output).max()}'''    )  # 0.0
 __lowerCAmelCase     :       str						=   torch.allclose(SCREAMING_SNAKE_CASE_    ,    SCREAMING_SNAKE_CASE_    ,    atol=1e-3    )

 if success:
  print("""Yay!"""    )
  hf_mlm.save_pretrained(SCREAMING_SNAKE_CASE_    )
 else:
  raise RuntimeError(F'''Something\'s broken :(\nOriginal:\n{original_output}\n\nHF\n{hf_output}\n{hf_mlm}'''    )

 if includes_tokenizer:
  print("""Transferring tokenizer"""    )
  __lowerCAmelCase     :       Optional[Any]						=   AutoTokenizer.from_pretrained(SCREAMING_SNAKE_CASE_    )
  tokenizer.save_pretrained(SCREAMING_SNAKE_CASE_    )


if __name__ == "__main__":
      _UpperCAmelCase			   =							argparse.ArgumentParser()

      parser.add_argument(
          '--pretrained_checkpoint_path',
          default=None,
          type=str,
          required=True,
          help='Point to the directory containing your model weights using the official Mega repo',
      )

      parser.add_argument(
          '--output_path', default=None, type=str, required=True, help='Location to save the Hugging Face version'
      )

      parser.add_argument(
          '--includes_tokenizer',
          action='store_true',
          help='Use this flag if there is a Hugging Face tokenizer in the original checkpoint repo',
      )

      _UpperCAmelCase			   =							parser.parse_args()

      convert_checkpoint_to_huggingface(args.pretrained_checkpoint_path, args.output_path, args.includes_tokenizer)


'''simple docstring'''






from __future__ import annotations

import unittest
from collections.abc import Iterator
class 	SCREAMING_SNAKE_CASE__			:




    def __init__(					self				,     lowercase__				,     lowercase__			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			str     =       label
          SCREAMING_SNAKE_CASE_      :			Union[str, Any]     =       parent
          SCREAMING_SNAKE_CASE_      :			Node | None     =       None
          SCREAMING_SNAKE_CASE_      :			Node | None     =       None






class 	SCREAMING_SNAKE_CASE__			:




    def __init__(					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			Node | None     =       None




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			Optional[int]     =       None




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          return self.root is None




    def   __lowerCamelCase      (					self				,     lowercase__			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			Optional[int]     =       self._put(self.root				,     lowercase__			)




    def   __lowerCamelCase      (					self				,     lowercase__				,     lowercase__				,     lowercase__ = None			):






          """simple docstring"""






          if node is None:
                SCREAMING_SNAKE_CASE_      :			Optional[Any]     =       Node(lowercase__				,     lowercase__			)
          else:
                if label < node.label:
                      SCREAMING_SNAKE_CASE_      :			Union[str, Any]     =       self._put(node.left				,     lowercase__				,     lowercase__			)
                elif label > node.label:
                      SCREAMING_SNAKE_CASE_      :			List[Any]     =       self._put(node.right				,     lowercase__				,     lowercase__			)
                else:
                      SCREAMING_SNAKE_CASE_      :			str     =       F"Node with label {label} already exists"
                      raise Exception(lowercase__			)

          return node




    def   __lowerCamelCase      (					self				,     lowercase__			):






          """simple docstring"""






          return self._search(self.root				,     lowercase__			)




    def   __lowerCamelCase      (					self				,     lowercase__				,     lowercase__			):






          """simple docstring"""






          if node is None:
                SCREAMING_SNAKE_CASE_      :			Dict     =       F"Node with label {label} does not exist"
                raise Exception(lowercase__			)
          else:
                if label < node.label:
                      SCREAMING_SNAKE_CASE_      :			Optional[int]     =       self._search(node.left				,     lowercase__			)
                elif label > node.label:
                      SCREAMING_SNAKE_CASE_      :			str     =       self._search(node.right				,     lowercase__			)

          return node




    def   __lowerCamelCase      (					self				,     lowercase__			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			str     =       self.search(lowercase__			)
          if node.right and node.left:
                SCREAMING_SNAKE_CASE_      :			Dict     =       self._get_lowest_node(node.right			)
                SCREAMING_SNAKE_CASE_      :			str     =       node.left
                SCREAMING_SNAKE_CASE_      :			str     =       node.right
                SCREAMING_SNAKE_CASE_      :			Dict     =       lowest_node
                if node.right:
                      SCREAMING_SNAKE_CASE_      :			Any     =       lowest_node
                self._reassign_nodes(lowercase__				,     lowercase__			)
          elif not node.right and node.left:
                self._reassign_nodes(lowercase__				,     node.left			)
          elif node.right and not node.left:
                self._reassign_nodes(lowercase__				,     node.right			)
          else:
                self._reassign_nodes(lowercase__				,     lowercase__			)




    def   __lowerCamelCase      (					self				,     lowercase__				,     lowercase__			):






          """simple docstring"""






          if new_children:
                SCREAMING_SNAKE_CASE_      :			str     =       node.parent

          if node.parent:
                if node.parent.right == node:
                      SCREAMING_SNAKE_CASE_      :			str     =       new_children
                else:
                      SCREAMING_SNAKE_CASE_      :			Optional[Any]     =       new_children
          else:
                SCREAMING_SNAKE_CASE_      :			Tuple     =       new_children




    def   __lowerCamelCase      (					self				,     lowercase__			):






          """simple docstring"""






          if node.left:
                SCREAMING_SNAKE_CASE_      :			List[Any]     =       self._get_lowest_node(node.left			)
          else:
                SCREAMING_SNAKE_CASE_      :			Tuple     =       node
                self._reassign_nodes(lowercase__				,     node.right			)

          return lowest_node




    def   __lowerCamelCase      (					self				,     lowercase__			):






          """simple docstring"""






          try:
                self.search(lowercase__			)
                return True
          except Exception:
                return False




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          if self.root is None:
                raise Exception("Binary search tree is empty"			)

          SCREAMING_SNAKE_CASE_      :			Union[str, Any]     =       self.root
          while node.right is not None:
                SCREAMING_SNAKE_CASE_      :			Dict     =       node.right

          return node.label




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          if self.root is None:
                raise Exception("Binary search tree is empty"			)

          SCREAMING_SNAKE_CASE_      :			Any     =       self.root
          while node.left is not None:
                SCREAMING_SNAKE_CASE_      :			List[str]     =       node.left

          return node.label




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          return self._inorder_traversal(self.root			)




    def   __lowerCamelCase      (					self				,     lowercase__			):






          """simple docstring"""






          if node is not None:
                yield from self._inorder_traversal(node.left			)
                yield node
                yield from self._inorder_traversal(node.right			)




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          return self._preorder_traversal(self.root			)







    def   __lowerCamelCase      (					self				,     lowercase__			):






          """simple docstring"""






          if node is not None:
                yield node
                yield from self._preorder_traversal(node.left			)
                yield from self._preorder_traversal(node.right			)






class 	SCREAMING_SNAKE_CASE__			(				unittest.TestCase      ):




    @staticmethod
    def   __lowerCamelCase      (					):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			List[str]     =       BinarySearchTree()
          t.put(8			)
          t.put(3			)
          t.put(6			)
          t.put(1			)
          t.put(10			)
          t.put(14			)
          t.put(13			)
          t.put(4			)
          t.put(7			)
          t.put(5			)

          return t




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			Any     =       BinarySearchTree()
          assert t.is_empty()

          t.put(8			)
          assert t.root is not None
          assert t.root.parent is None
          assert t.root.label == 8

          t.put(10			)
          assert t.root.right is not None
          assert t.root.right.parent == t.root
          assert t.root.right.label == 10

          t.put(3			)
          assert t.root.left is not None
          assert t.root.left.parent == t.root
          assert t.root.left.label == 3

          t.put(6			)
          assert t.root.left.right is not None
          assert t.root.left.right.parent == t.root.left
          assert t.root.left.right.label == 6

          t.put(1			)
          assert t.root.left.left is not None
          assert t.root.left.left.parent == t.root.left
          assert t.root.left.left.label == 1

          with self.assertRaises(lowercase__			):  # noqa: B017
                t.put(1			)




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			List[Any]     =       self._get_binary_search_tree()

          SCREAMING_SNAKE_CASE_      :			str     =       t.search(6			)
          assert node.label == 6

          SCREAMING_SNAKE_CASE_      :			int     =       t.search(13			)
          assert node.label == 13

          with self.assertRaises(lowercase__			):  # noqa: B017
                t.search(2			)




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			List[str]     =       self._get_binary_search_tree()

          t.remove(13			)
          assert t.root is not None
          assert t.root.right is not None
          assert t.root.right.right is not None
          assert t.root.right.right.right is None
          assert t.root.right.right.left is None

          t.remove(7			)
          assert t.root.left is not None
          assert t.root.left.right is not None
          assert t.root.left.right.left is not None
          assert t.root.left.right.right is None
          assert t.root.left.right.left.label == 4

          t.remove(6			)
          assert t.root.left.left is not None
          assert t.root.left.right.right is not None
          assert t.root.left.left.label == 1
          assert t.root.left.right.label == 4
          assert t.root.left.right.right.label == 5
          assert t.root.left.right.left is None
          assert t.root.left.left.parent == t.root.left
          assert t.root.left.right.parent == t.root.left

          t.remove(3			)
          assert t.root is not None
          assert t.root.left.label == 4
          assert t.root.left.right.label == 5
          assert t.root.left.left.label == 1
          assert t.root.left.parent == t.root
          assert t.root.left.left.parent == t.root.left
          assert t.root.left.right.parent == t.root.left

          t.remove(4			)
          assert t.root.left is not None
          assert t.root.left.left is not None
          assert t.root.left.label == 5
          assert t.root.left.right is None
          assert t.root.left.left.label == 1
          assert t.root.left.parent == t.root
          assert t.root.left.left.parent == t.root.left




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			Dict     =       self._get_binary_search_tree()

          t.remove(3			)
          assert t.root is not None
          assert t.root.left is not None
          assert t.root.left.left is not None
          assert t.root.left.right is not None
          assert t.root.left.right.left is not None
          assert t.root.left.right.right is not None
          assert t.root.left.label == 4
          assert t.root.left.right.label == 6
          assert t.root.left.left.label == 1
          assert t.root.left.right.right.label == 7
          assert t.root.left.right.left.label == 5
          assert t.root.left.parent == t.root
          assert t.root.left.right.parent == t.root.left
          assert t.root.left.left.parent == t.root.left
          assert t.root.left.right.left.parent == t.root.left.right




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			Any     =       self._get_binary_search_tree()
          t.empty()
          assert t.root is None




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			Optional[Any]     =       self._get_binary_search_tree()
          assert not t.is_empty()

          t.empty()
          assert t.is_empty()




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			str     =       self._get_binary_search_tree()

          assert t.exists(6			)
          assert not t.exists(-1			)




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			Tuple     =       self._get_binary_search_tree()

          assert t.get_max_label() == 14

          t.empty()
          with self.assertRaises(lowercase__			):  # noqa: B017
                t.get_max_label()




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			Tuple     =       self._get_binary_search_tree()

          assert t.get_min_label() == 1

          t.empty()
          with self.assertRaises(lowercase__			):  # noqa: B017
                t.get_min_label()




    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			List[str]     =       self._get_binary_search_tree()

          SCREAMING_SNAKE_CASE_      :			Dict     =       [i.label for i in t.inorder_traversal()]
          assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]







    def   __lowerCamelCase      (					self			):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_      :			int     =       self._get_binary_search_tree()

          SCREAMING_SNAKE_CASE_      :			Any     =       [i.label for i in t.preorder_traversal()]
          assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]






def 					__lowerCamelCase			(      )							->   None:
      """simple docstring"""

      SCREAMING_SNAKE_CASE_      :			int     =       BinarySearchTree()
      t.put(8    )
      t.put(3    )
      t.put(6    )
      t.put(1    )
      t.put(1_0    )
      t.put(1_4    )
      t.put(1_3    )
      t.put(4    )
      t.put(7    )
      t.put(5    )

      print(
          "\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        "    )

      print("Label 6 exists:"  ,  t.exists(6    )    )
      print("Label 13 exists:"  ,  t.exists(1_3    )    )
      print("Label -1 exists:"  ,  t.exists(-1    )    )
      print("Label 12 exists:"  ,  t.exists(1_2    )    )

      # Prints all the elements of the list in inorder traversal
      SCREAMING_SNAKE_CASE_      :			Dict     =       [i.label for i in t.inorder_traversal()]
      print("Inorder traversal:"  ,  SCREAMING_SNAKE_CASE_    )

      # Prints all the elements of the list in preorder traversal
      SCREAMING_SNAKE_CASE_      :			Union[str, Any]     =       [i.label for i in t.preorder_traversal()]
      print("Preorder traversal:"  ,  SCREAMING_SNAKE_CASE_    )

      print("Max. label:"  ,  t.get_max_label()    )
      print("Min. label:"  ,  t.get_min_label()    )

      # Delete elements
      print("\nDeleting elements 13, 10, 8, 3, 6, 14"    )
      print(
          "\n          4\n         / \\\n        1   7\n             \\\n              5\n        "    )
      t.remove(1_3    )
      t.remove(1_0    )
      t.remove(8    )
      t.remove(3    )
      t.remove(6    )
      t.remove(1_4    )

      # Prints all the elements of the list in inorder traversal after delete
      SCREAMING_SNAKE_CASE_      :			Optional[int]     =       [i.label for i in t.inorder_traversal()]
      print("Inorder traversal after delete:"  ,  SCREAMING_SNAKE_CASE_    )

      # Prints all the elements of the list in preorder traversal after delete
      SCREAMING_SNAKE_CASE_      :			Optional[int]     =       [i.label for i in t.preorder_traversal()]
      print("Preorder traversal after delete:"  ,  SCREAMING_SNAKE_CASE_    )

      print("Max. label:"  ,  t.get_max_label()    )
      print("Min. label:"  ,  t.get_min_label()    )


if __name__ == "__main__":
      binary_search_tree_example()

