




from __future__ import annotations

import unittest
from collections.abc import Iterator




class       UpperCAmelCase_   :




							'''simple docstring'''



							def __init__(       self							:						Union[str, Any]							,  a							:						int							,  a							:						Node | None      )      ->       None:
										SCREAMING_SNAKE_CASE     =       label
										SCREAMING_SNAKE_CASE     =       parent
										SCREAMING_SNAKE_CASE     =       None
										SCREAMING_SNAKE_CASE     =       None





class       UpperCAmelCase_   :




							'''simple docstring'''



							def __init__(       self							:						Union[str, Any]      )      ->       None:
										SCREAMING_SNAKE_CASE     =       None





							def  _UpperCAmelCase  (       self							:						Dict      )      ->       None:
										SCREAMING_SNAKE_CASE     =       None





							def  _UpperCAmelCase  (       self							:						str      )      ->       bool:
										return self.root is None





							def  _UpperCAmelCase  (       self							:						Optional[int]							,  a							:						int      )      ->       None:
										SCREAMING_SNAKE_CASE     =       self._put(self.root							,  a      )





							def  _UpperCAmelCase  (       self							:						Union[str, Any]							,  a							:						Node | None							,  a							:						int							,  a							:						Node | None = None      )      ->       Node:
										if node is None:
													SCREAMING_SNAKE_CASE     =       Node(a							,  a      )
										else:
													if label < node.label:
																SCREAMING_SNAKE_CASE     =       self._put(node.left							,  a							,  a      )
													elif label > node.label:
																SCREAMING_SNAKE_CASE     =       self._put(node.right							,  a							,  a      )
													else:
																SCREAMING_SNAKE_CASE     =       f"""Node with label {label} already exists"""
																raise Exception(a      )

										return node





							def  _UpperCAmelCase  (       self							:						Optional[int]							,  a							:						int      )      ->       Node:
										return self._search(self.root							,  a      )





							def  _UpperCAmelCase  (       self							:						Dict							,  a							:						Node | None							,  a							:						int      )      ->       Node:
										if node is None:
													SCREAMING_SNAKE_CASE     =       f"""Node with label {label} does not exist"""
													raise Exception(a      )
										else:
													if label < node.label:
																SCREAMING_SNAKE_CASE     =       self._search(node.left							,  a      )
													elif label > node.label:
																SCREAMING_SNAKE_CASE     =       self._search(node.right							,  a      )

										return node





							def  _UpperCAmelCase  (       self							:						Optional[int]							,  a							:						int      )      ->       None:
										SCREAMING_SNAKE_CASE     =       self.search(a      )
										if node.right and node.left:
													SCREAMING_SNAKE_CASE     =       self._get_lowest_node(node.right      )
													SCREAMING_SNAKE_CASE     =       node.left
													SCREAMING_SNAKE_CASE     =       node.right
													SCREAMING_SNAKE_CASE     =       lowest_node
													if node.right:
																SCREAMING_SNAKE_CASE     =       lowest_node
													self._reassign_nodes(a							,  a      )
										elif not node.right and node.left:
													self._reassign_nodes(a							,  node.left      )
										elif node.right and not node.left:
													self._reassign_nodes(a							,  node.right      )
										else:
													self._reassign_nodes(a							,  a      )





							def  _UpperCAmelCase  (       self							:						str							,  a							:						Node							,  a							:						Node | None      )      ->       None:
										if new_children:
													SCREAMING_SNAKE_CASE     =       node.parent

										if node.parent:
													if node.parent.right == node:
																SCREAMING_SNAKE_CASE     =       new_children
													else:
																SCREAMING_SNAKE_CASE     =       new_children
										else:
													SCREAMING_SNAKE_CASE     =       new_children





							def  _UpperCAmelCase  (       self							:						Tuple							,  a							:						Node      )      ->       Node:
										if node.left:
													SCREAMING_SNAKE_CASE     =       self._get_lowest_node(node.left      )
										else:
													SCREAMING_SNAKE_CASE     =       node
													self._reassign_nodes(a							,  node.right      )

										return lowest_node





							def  _UpperCAmelCase  (       self							:						Tuple							,  a							:						int      )      ->       bool:
										try:
													self.search(a      )
													return True
										except Exception:
													return False





							def  _UpperCAmelCase  (       self							:						Dict      )      ->       int:
										if self.root is None:
													raise Exception("""Binary search tree is empty"""      )

										SCREAMING_SNAKE_CASE     =       self.root
										while node.right is not None:
													SCREAMING_SNAKE_CASE     =       node.right

										return node.label





							def  _UpperCAmelCase  (       self							:						Tuple      )      ->       int:
										if self.root is None:
													raise Exception("""Binary search tree is empty"""      )

										SCREAMING_SNAKE_CASE     =       self.root
										while node.left is not None:
													SCREAMING_SNAKE_CASE     =       node.left

										return node.label





							def  _UpperCAmelCase  (       self							:						List[str]      )      ->       Iterator[Node]:
										return self._inorder_traversal(self.root      )





							def  _UpperCAmelCase  (       self							:						Optional[int]							,  a							:						Node | None      )      ->       Iterator[Node]:
										if node is not None:
													yield from self._inorder_traversal(node.left      )
													yield node
													yield from self._inorder_traversal(node.right      )





							def  _UpperCAmelCase  (       self							:						Tuple      )      ->       Iterator[Node]:
										return self._preorder_traversal(self.root      )







							def  _UpperCAmelCase  (       self							:						List[Any]							,  a							:						Node | None      )      ->       Iterator[Node]:
										if node is not None:
													yield node
													yield from self._preorder_traversal(node.left      )
													yield from self._preorder_traversal(node.right      )





class       UpperCAmelCase_   ( unittest.TestCase							):




							'''simple docstring'''



							@staticmethod
							def  _UpperCAmelCase  (       )      ->       BinarySearchTree:
										SCREAMING_SNAKE_CASE     =       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  _UpperCAmelCase  (       self							:						List[Any]      )      ->       None:
										SCREAMING_SNAKE_CASE     =       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(a      ):  # noqa: B017
													t.put(1      )





							def  _UpperCAmelCase  (       self							:						List[Any]      )      ->       None:
										SCREAMING_SNAKE_CASE     =       self._get_binary_search_tree()

										SCREAMING_SNAKE_CASE     =       t.search(6      )
										assert node.label == 6

										SCREAMING_SNAKE_CASE     =       t.search(13      )
										assert node.label == 13

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





							def  _UpperCAmelCase  (       self							:						Dict      )      ->       None:
										SCREAMING_SNAKE_CASE     =       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  _UpperCAmelCase  (       self							:						Optional[int]      )      ->       None:
										SCREAMING_SNAKE_CASE     =       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  _UpperCAmelCase  (       self							:						List[Any]      )      ->       None:
										SCREAMING_SNAKE_CASE     =       self._get_binary_search_tree()
										t.empty()
										assert t.root is None





							def  _UpperCAmelCase  (       self							:						Optional[Any]      )      ->       None:
										SCREAMING_SNAKE_CASE     =       self._get_binary_search_tree()
										assert not t.is_empty()

										t.empty()
										assert t.is_empty()





							def  _UpperCAmelCase  (       self							:						List[str]      )      ->       None:
										SCREAMING_SNAKE_CASE     =       self._get_binary_search_tree()

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





							def  _UpperCAmelCase  (       self							:						List[str]      )      ->       None:
										SCREAMING_SNAKE_CASE     =       self._get_binary_search_tree()

										assert t.get_max_label() == 14

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





							def  _UpperCAmelCase  (       self							:						Union[str, Any]      )      ->       None:
										SCREAMING_SNAKE_CASE     =       self._get_binary_search_tree()

										assert t.get_min_label() == 1

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





							def  _UpperCAmelCase  (       self							:						Dict      )      ->       None:
										SCREAMING_SNAKE_CASE     =       self._get_binary_search_tree()

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







							def  _UpperCAmelCase  (       self							:						List[Any]      )      ->       None:
										SCREAMING_SNAKE_CASE     =       self._get_binary_search_tree()

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





def        lowerCamelCase_     (     ):
			'''simple docstring'''
			SCREAMING_SNAKE_CASE     =       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 )

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

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

			# Prints all the elements of the list in inorder traversal
			SCREAMING_SNAKE_CASE     =       [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     =       [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(
			    """
          4
         / \\
        1   7
             \\
              5
        """ )
			t.remove(13 )
			t.remove(10 )
			t.remove(8 )
			t.remove(3 )
			t.remove(6 )
			t.remove(14 )

			# Prints all the elements of the list in inorder traversal after delete
			SCREAMING_SNAKE_CASE     =       [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     =       [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()












from collections import OrderedDict
from typing import Mapping

from ...configuration_utils import PretrainedConfig
from ...onnx import OnnxConfig
from ...utils import logging


__A    :				List[str]    						=	logging.get_logger(__name__)

__A    :				List[Any]    						=	{
    """mnaylor/mega-base-wikitext""": """https://huggingface.co/mnaylor/mega-base-wikitext/resolve/main/config.json""",
}




class       UpperCAmelCase_   ( A							):




							'''simple docstring'''



							a__    	=  '''mega'''





							def __init__(       self							:						Any							,  a							:						List[str]=30_522							,  a							:						Dict=128							,  a							:						Dict=4							,  a							:						Union[str, Any]=256							,  a							:						Tuple=16							,  a							:						Any=True							,  a							:						Dict=64							,  a							:						Union[str, Any]=False							,  a							:						Tuple=-1							,  a							:						str=None							,  a							:						int=True							,  a							:						Optional[int]="scalenorm"							,  a							:						Optional[int]=True							,  a							:						Dict="silu"							,  a							:						Optional[Any]="softmax"							,  a							:						Any=0.1							,  a							:						List[Any]=0.1							,  a							:						Tuple=0.1							,  a							:						Optional[int]=False							,  a							:						List[str]=True							,  a							:						Optional[int]=256							,  a							:						List[str]=True							,  a							:						int=0.1							,  a							:						str=2_048							,  a							:						Tuple=False							,  a							:						Optional[int]=2							,  a							:						Optional[int]=0.02							,  a							:						Optional[int]=0.2							,  a							:						Union[str, Any]=0.02							,  a							:						str=1.0							,  a							:						Dict=1							,  a							:						Union[str, Any]=0							,  a							:						Dict=2							,  a							:						List[str]="rotary"							,  a							:						Union[str, Any]=None							,  a							:						List[Any]=True							,  a							:						Tuple=True							,  **a							:						Optional[int]							,  )      ->       Dict:
										super().__init__(pad_token_id=a							,  bos_token_id=a							,  eos_token_id=a							,  **a      )

										SCREAMING_SNAKE_CASE     =       vocab_size
										SCREAMING_SNAKE_CASE     =       hidden_size
										SCREAMING_SNAKE_CASE     =       num_hidden_layers
										SCREAMING_SNAKE_CASE     =       activation
										SCREAMING_SNAKE_CASE     =       attention_activation
										SCREAMING_SNAKE_CASE     =       intermediate_size
										SCREAMING_SNAKE_CASE     =       ema_projection_size
										SCREAMING_SNAKE_CASE     =       bidirectional
										SCREAMING_SNAKE_CASE     =       shared_representation_size
										SCREAMING_SNAKE_CASE     =       use_chunking
										SCREAMING_SNAKE_CASE     =       chunk_size
										SCREAMING_SNAKE_CASE     =       truncation
										SCREAMING_SNAKE_CASE     =       normalize_before_mega
										SCREAMING_SNAKE_CASE     =       normalization_type
										SCREAMING_SNAKE_CASE     =       norm_affine
										SCREAMING_SNAKE_CASE     =       dropout_prob
										SCREAMING_SNAKE_CASE     =       hidden_dropout_prob
										SCREAMING_SNAKE_CASE     =       attention_probs_dropout_prob
										SCREAMING_SNAKE_CASE     =       use_feature_dropout
										SCREAMING_SNAKE_CASE     =       use_normalized_ffn
										SCREAMING_SNAKE_CASE     =       nffn_hidden_size
										SCREAMING_SNAKE_CASE     =       normalize_before_ffn
										SCREAMING_SNAKE_CASE     =       nffn_activation_dropout_prob
										SCREAMING_SNAKE_CASE     =       max_positions
										SCREAMING_SNAKE_CASE     =       add_token_type_embeddings
										SCREAMING_SNAKE_CASE     =       type_vocab_size
										SCREAMING_SNAKE_CASE     =       initializer_range
										SCREAMING_SNAKE_CASE     =       ema_delta_alpha_range
										SCREAMING_SNAKE_CASE     =       ema_beta_range
										SCREAMING_SNAKE_CASE     =       ema_gamma_omega_range
										SCREAMING_SNAKE_CASE     =       relative_positional_bias
										SCREAMING_SNAKE_CASE     =       use_cache
										SCREAMING_SNAKE_CASE     =       classifier_dropout
										SCREAMING_SNAKE_CASE     =       add_lm_hidden_dense_layer
										SCREAMING_SNAKE_CASE     =       1  # not used but required by Hugging Face





class       UpperCAmelCase_   ( A							):




							'''simple docstring'''



							@property
							def  _UpperCAmelCase  (       self							:						Union[str, Any]      )      ->       Mapping[str, Mapping[int, str]]:
										if self.task == "multiple-choice":
													SCREAMING_SNAKE_CASE     =       {0: """batch""", 1: """choice""", 2: """sequence"""}
										else:
													SCREAMING_SNAKE_CASE     =       {0: """batch""", 1: """sequence"""}
										return OrderedDict(
										    [
										        ("""input_ids""", dynamic_axis),
										        ("""attention_mask""", dynamic_axis),
										    ]      )






