




'''simple docstring'''







from collections import OrderedDict
from typing import Any, Mapping, Optional

from ... import PreTrainedTokenizer
from ...configuration_utils import PretrainedConfig
from ...onnx import OnnxConfig, OnnxSeqaSeqConfigWithPast
from ...onnx.utils import compute_effective_axis_dimension
from ...utils import TensorType, is_torch_available, logging


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

_lowerCamelCase							:						Union[str, Any]								=  {
    'facebook/m2m100_418M': 'https://huggingface.co/facebook/m2m100_418M/resolve/main/config.json',
    # See all M2M100 models at https://huggingface.co/models?filter=m2m_100
}





class      lowerCamelCase_							(       UpperCAmelCase_							):




					'''simple docstring'''






					lowercase__    = """m2m_100"""
					lowercase__    = ["""past_key_values"""]
					lowercase__    = {"""num_attention_heads""": """encoder_attention_heads""", """hidden_size""": """d_model"""}






					def __init__(    self,  __UpperCamelCase=128_112,  __UpperCamelCase=1_024,  __UpperCamelCase=12,  __UpperCamelCase=4_096,  __UpperCamelCase=16,  __UpperCamelCase=12,  __UpperCamelCase=4_096,  __UpperCamelCase=16,  __UpperCamelCase=0.05,  __UpperCamelCase=0.05,  __UpperCamelCase=True,  __UpperCamelCase=True,  __UpperCamelCase="relu",  __UpperCamelCase=1_024,  __UpperCamelCase=0.1,  __UpperCamelCase=0.1,  __UpperCamelCase=0.0,  __UpperCamelCase=0.02,  __UpperCamelCase=2,  __UpperCamelCase=True,  __UpperCamelCase=1,  __UpperCamelCase=0,  __UpperCamelCase=2,  **__UpperCamelCase,  ):
							_snake_case	       =       vocab_size
							_snake_case	       =       max_position_embeddings
							_snake_case	       =       d_model
							_snake_case	       =       encoder_ffn_dim
							_snake_case	       =       encoder_layers
							_snake_case	       =       encoder_attention_heads
							_snake_case	       =       decoder_ffn_dim
							_snake_case	       =       decoder_layers
							_snake_case	       =       decoder_attention_heads
							_snake_case	       =       dropout
							_snake_case	       =       attention_dropout
							_snake_case	       =       activation_dropout
							_snake_case	       =       activation_function
							_snake_case	       =       init_std
							_snake_case	       =       encoder_layerdrop
							_snake_case	       =       decoder_layerdrop
							_snake_case	       =       use_cache
							_snake_case	       =       encoder_layers
							_snake_case	       =       scale_embedding  # scale factor will be sqrt(d_model) if True

							super().__init__(
							    pad_token_id=__UpperCamelCase,  bos_token_id=__UpperCamelCase,  eos_token_id=__UpperCamelCase,  is_encoder_decoder=__UpperCamelCase,  decoder_start_token_id=__UpperCamelCase,  **__UpperCamelCase,  )





class      lowerCamelCase_							(       UpperCAmelCase_							):




					'''simple docstring'''






					@property
					def 				__SCREAMING_SNAKE_CASE	(    self ):
							_snake_case	       =       OrderedDict(
							    [
							        ("input_ids", {0: "batch", 1: "encoder_sequence"}),
							        ("attention_mask", {0: "batch", 1: "encoder_sequence"}),
							    ] )

							if self.use_past:
									_snake_case	       =       {0: "batch"}
									_snake_case	       =       {0: "batch", 1: "past_decoder_sequence + sequence"}
							else:
									_snake_case	       =       {0: "batch", 1: "decoder_sequence"}
									_snake_case	       =       {0: "batch", 1: "decoder_sequence"}

							if self.use_past:
									self.fill_with_past_key_values_(__UpperCamelCase,  direction="inputs" )
							return common_inputs






					def 				__SCREAMING_SNAKE_CASE	(    self,  __UpperCamelCase,  __UpperCamelCase = -1,  __UpperCamelCase = -1,  __UpperCamelCase = False,  __UpperCamelCase = None,  ):
							# Copied from OnnxConfig.generate_dummy_inputs
							# Did not use super(OnnxConfigWithPast, self).generate_dummy_inputs for code clarity.
							# If dynamic axis (-1) we forward with a fixed dimension of 2 samples to avoid optimizations made by ONNX
							_snake_case	       =       compute_effective_axis_dimension(
							    __UpperCamelCase,  fixed_dimension=OnnxConfig.default_fixed_batch,  num_token_to_add=0 )

							# If dynamic axis (-1) we forward with a fixed dimension of 8 tokens to avoid optimizations made by ONNX
							_snake_case	       =       tokenizer.num_special_tokens_to_add(__UpperCamelCase )
							_snake_case	       =       compute_effective_axis_dimension(
							    __UpperCamelCase,  fixed_dimension=OnnxConfig.default_fixed_sequence,  num_token_to_add=__UpperCamelCase )

							# Generate dummy inputs according to compute batch and sequence
							_snake_case	       =       [" ".join([tokenizer.unk_token] ) * seq_length] * batch_size
							_snake_case	       =       dict(tokenizer(__UpperCamelCase,  return_tensors=__UpperCamelCase ) )
							return common_inputs






					def 				__SCREAMING_SNAKE_CASE	(    self,  __UpperCamelCase,  __UpperCamelCase = -1,  __UpperCamelCase = -1,  __UpperCamelCase = False,  __UpperCamelCase = None,  ):
							_snake_case	       =       self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
							    __UpperCamelCase,  __UpperCamelCase,  __UpperCamelCase,  __UpperCamelCase,  __UpperCamelCase )

							# Generate decoder inputs
							_snake_case	       =       seq_length if not self.use_past else 1
							_snake_case	       =       self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
							    __UpperCamelCase,  __UpperCamelCase,  __UpperCamelCase,  __UpperCamelCase,  __UpperCamelCase )
							_snake_case	       =       {f'''decoder_{name}''': tensor for name, tensor in decoder_inputs.items()}
							_snake_case	       =       dict(**__UpperCamelCase,  **__UpperCamelCase )

							if self.use_past:
									if not is_torch_available():
											raise ValueError("Cannot generate dummy past_keys inputs without PyTorch installed." )
									else:
											import torch
									_snake_case       ,    _snake_case	       =       common_inputs["input_ids"].shape
									_snake_case	       =       common_inputs["decoder_input_ids"].shape[1]
									_snake_case       ,    _snake_case	       =       self.num_attention_heads
									_snake_case	       =       (
									    batch,
									    num_encoder_attention_heads,
									    encoder_seq_length,
									    self._config.hidden_size // num_encoder_attention_heads,
									)
									_snake_case	       =       decoder_seq_length + 3
									_snake_case	       =       (
									    batch,
									    num_decoder_attention_heads,
									    decoder_past_length,
									    self._config.hidden_size // num_decoder_attention_heads,
									)

									_snake_case	       =       torch.cat(
									    [common_inputs["decoder_attention_mask"], torch.ones(__UpperCamelCase,  __UpperCamelCase )],  dim=1 )

									_snake_case	       =       []
									# If the number of encoder and decoder layers are present in the model configuration, both are considered
									_snake_case       ,    _snake_case	       =       self.num_layers
									_snake_case	       =       min(__UpperCamelCase,  __UpperCamelCase )
									_snake_case	       =       max(__UpperCamelCase,  __UpperCamelCase ) - min_num_layers
									_snake_case	       =       "encoder" if num_encoder_layers > num_decoder_layers else "decoder"

									for _ in range(__UpperCamelCase ):
											common_inputs["past_key_values"].append(
											    (
											        torch.zeros(__UpperCamelCase ),
											        torch.zeros(__UpperCamelCase ),
											        torch.zeros(__UpperCamelCase ),
											        torch.zeros(__UpperCamelCase ),
											    ) )
									# TODO: test this.
									_snake_case	       =       encoder_shape if remaining_side_name == "encoder" else decoder_shape
									for _ in range(__UpperCamelCase,  __UpperCamelCase ):
											common_inputs["past_key_values"].append((torch.zeros(__UpperCamelCase ), torch.zeros(__UpperCamelCase )) )
							return common_inputs






					lowercase__    = _generate_dummy_inputs_for_default_and_seqaseq_lm








'''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()

