






"""simple docstring"""




from __future__ import annotations

import unittest
from collections.abc import Iterator

class 			_UpperCAmelCase  :



      '''simple docstring'''

      def __init__(					self ,				snake_case_ ,				snake_case_  ):

        """simple docstring"""

        A_  :	int    						=  label
        A_  :	Optional[Any]    						=  parent
        A_  :	Optional[Any]    						=  None
        A_  :	str    						=  None


class 			_UpperCAmelCase  :



      '''simple docstring'''

      def __init__(					self  ):

        """simple docstring"""

        A_  :	Optional[Any]    						=  None

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

        A_  :	List[str]    						=  None

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

        return self.root is None

      def  lowerCamelCase_      (					self ,				snake_case_  ):

        """simple docstring"""

        A_  :	Union[str, Any]    						=  self._put(self.root ,				lowerCAmelCase__  )

      def  lowerCamelCase_      (					self ,				snake_case_ ,				snake_case_ ,				snake_case_ = None  ):

        """simple docstring"""

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

        return node

      def  lowerCamelCase_      (					self ,				snake_case_  ):

        """simple docstring"""

        return self._search(self.root ,				lowerCAmelCase__  )

      def  lowerCamelCase_      (					self ,				snake_case_ ,				snake_case_  ):

        """simple docstring"""

        if node is None:
          A_  :	Any    						=  F"""Node with label {label} does not exist"""
          raise Exception(lowerCAmelCase__  )
        else:
          if label < node.label:
            A_  :	List[str]    						=  self._search(node.left ,				lowerCAmelCase__  )
          elif label > node.label:
            A_  :	Union[str, Any]    						=  self._search(node.right ,				lowerCAmelCase__  )

        return node

      def  lowerCamelCase_      (					self ,				snake_case_  ):

        """simple docstring"""

        A_  :	int    						=  self.search(lowerCAmelCase__  )
        if node.right and node.left:
          A_  :	Dict    						=  self._get_lowest_node(node.right  )
          A_  :	Dict    						=  node.left
          A_  :	int    						=  node.right
          A_  :	List[Any]    						=  lowest_node
          if node.right:
            A_  :	str    						=  lowest_node
          self._reassign_nodes(lowerCAmelCase__ ,				lowerCAmelCase__  )
        elif not node.right and node.left:
          self._reassign_nodes(lowerCAmelCase__ ,				node.left  )
        elif node.right and not node.left:
          self._reassign_nodes(lowerCAmelCase__ ,				node.right  )
        else:
          self._reassign_nodes(lowerCAmelCase__ ,				lowerCAmelCase__  )

      def  lowerCamelCase_      (					self ,				snake_case_ ,				snake_case_  ):

        """simple docstring"""

        if new_children:
          A_  :	int    						=  node.parent

        if node.parent:
          if node.parent.right == node:
            A_  :	List[str]    						=  new_children
          else:
            A_  :	Dict    						=  new_children
        else:
          A_  :	str    						=  new_children

      def  lowerCamelCase_      (					self ,				snake_case_  ):

        """simple docstring"""

        if node.left:
          A_  :	List[str]    						=  self._get_lowest_node(node.left  )
        else:
          A_  :	Dict    						=  node
          self._reassign_nodes(lowerCAmelCase__ ,				node.right  )

        return lowest_node

      def  lowerCamelCase_      (					self ,				snake_case_  ):

        """simple docstring"""

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

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

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

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

        return node.label

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

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

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

        return node.label

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

        return self._inorder_traversal(self.root  )

      def  lowerCamelCase_      (					self ,				snake_case_  ):

        """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 ,				snake_case_  ):

        """simple docstring"""

        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  lowerCamelCase_      (					):

        """simple docstring"""

        A_  :	Tuple    						=  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  )

        return t

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

        A_  :	str    						=  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(1_0  )
        assert t.root.right is not None
        assert t.root.right.parent == t.root
        assert t.root.right.label == 1_0

        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(lowerCAmelCase__  ):  # noqa: B017
          t.put(1  )

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

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

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

        A_  :	Any    						=  t.search(1_3  )
        assert node.label == 1_3

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

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

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

        t.remove(1_3  )
        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"""

        A_  :	List[str]    						=  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"""

        A_  :	Tuple    						=  self._get_binary_search_tree()
        t.empty()
        assert t.root is None

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

        A_  :	Any    						=  self._get_binary_search_tree()
        assert not t.is_empty()

        t.empty()
        assert t.is_empty()

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

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

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

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

        A_  :	Optional[int]    						=  self._get_binary_search_tree()

        assert t.get_max_label() == 1_4

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

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

        A_  :	int    						=  self._get_binary_search_tree()

        assert t.get_min_label() == 1

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

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

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

        A_  :	Any    						=  [i.label for i in t.inorder_traversal()]
        assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]

      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

        A_  :	Dict    						=  self._get_binary_search_tree()

        A_  :	Any    						=  [i.label for i in t.preorder_traversal()]
        assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]





def 						UpperCAmelCase__		(					):






  """simple docstring"""





  A_  :	List[Any]    						=  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(
      '\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(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
  A_  :	List[str]    						=  [i.label for i in t.inorder_traversal()]
  print('Inorder traversal:'			, lowercase_ )

  # Prints all the elements of the list in preorder traversal
  A_  :	Optional[int]    						=  [i.label for i in t.preorder_traversal()]
  print('Preorder traversal:'			, lowercase_ )

  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(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
  A_  :	Any    						=  [i.label for i in t.inorder_traversal()]
  print('Inorder traversal after delete:'			, lowercase_ )

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

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


if __name__ == "__main__":
   binary_search_tree_example()






"""simple docstring"""




from collections import OrderedDict
from typing import Mapping

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


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

lowerCamelCase_					:						Optional[int]      = {
    'google/electra-small-generator': 'https://huggingface.co/google/electra-small-generator/resolve/main/config.json',
    'google/electra-base-generator': 'https://huggingface.co/google/electra-base-generator/resolve/main/config.json',
    'google/electra-large-generator': 'https://huggingface.co/google/electra-large-generator/resolve/main/config.json',
    'google/electra-small-discriminator': (
        'https://huggingface.co/google/electra-small-discriminator/resolve/main/config.json'
    ),
    'google/electra-base-discriminator': (
        'https://huggingface.co/google/electra-base-discriminator/resolve/main/config.json'
    ),
    'google/electra-large-discriminator': (
        'https://huggingface.co/google/electra-large-discriminator/resolve/main/config.json'
    ),
}

class 			_UpperCAmelCase  (       UpperCAmelCase__		):



      '''simple docstring'''
      lowercase_				:			Tuple        =       """electra"""

      def __init__(					self ,				snake_case_=3_0_5_2_2 ,				snake_case_=1_2_8 ,				snake_case_=2_5_6 ,				snake_case_=1_2 ,				snake_case_=4 ,				snake_case_=1_0_2_4 ,				snake_case_="gelu" ,				snake_case_=0.1 ,				snake_case_=0.1 ,				snake_case_=5_1_2 ,				snake_case_=2 ,				snake_case_=0.02 ,				snake_case_=1E-12 ,				snake_case_="first" ,				snake_case_=True ,				snake_case_="gelu" ,				snake_case_=0.1 ,				snake_case_=0 ,				snake_case_="absolute" ,				snake_case_=True ,				snake_case_=None ,				**snake_case_ ,				):

        """simple docstring"""

        super().__init__(pad_token_id=snake_case_ ,				**snake_case_  )

        A_  :	Optional[Any]    						=  vocab_size
        A_  :	Any    						=  embedding_size
        A_  :	Optional[int]    						=  hidden_size
        A_  :	Tuple    						=  num_hidden_layers
        A_  :	Tuple    						=  num_attention_heads
        A_  :	List[Any]    						=  intermediate_size
        A_  :	Any    						=  hidden_act
        A_  :	str    						=  hidden_dropout_prob
        A_  :	Any    						=  attention_probs_dropout_prob
        A_  :	str    						=  max_position_embeddings
        A_  :	Optional[Any]    						=  type_vocab_size
        A_  :	Dict    						=  initializer_range
        A_  :	Optional[int]    						=  layer_norm_eps

        A_  :	int    						=  summary_type
        A_  :	List[str]    						=  summary_use_proj
        A_  :	Optional[Any]    						=  summary_activation
        A_  :	Optional[Any]    						=  summary_last_dropout
        A_  :	List[Any]    						=  position_embedding_type
        A_  :	Union[str, Any]    						=  use_cache
        A_  :	Tuple    						=  classifier_dropout


class 			_UpperCAmelCase  (       UpperCAmelCase__		):



      '''simple docstring'''

      @property
      def  lowerCamelCase_      (					self  ):

        """simple docstring"""

        if self.task == "multiple-choice":
          A_  :	int    						=  {0: 'batch', 1: 'choice', 2: 'sequence'}
        else:
          A_  :	Optional[Any]    						=  {0: 'batch', 1: 'sequence'}
        return OrderedDict(
            [
                ('input_ids', dynamic_axis),
                ('attention_mask', dynamic_axis),
                ('token_type_ids', dynamic_axis),
            ]  )