
"""simple docstring"""
from __future__ import annotations

import os
import tempfile
import unittest

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

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


if is_tf_available():
						import tensorflow as tf

						from transformers import (
						    TFConvBertForMaskedLM,
						    TFConvBertForMultipleChoice,
						    TFConvBertForQuestionAnswering,
						    TFConvBertForSequenceClassification,
						    TFConvBertForTokenClassification,
						    TFConvBertModel,
						)
class 			UpperCamelCase      :
					def __init__(     self  ,     snake_case__  ,     snake_case__=13  ,     snake_case__=7  ,     snake_case__=True  ,     snake_case__=True  ,     snake_case__=True  ,     snake_case__=True  ,     snake_case__=99  ,     snake_case__=32  ,     snake_case__=2  ,     snake_case__=4  ,     snake_case__=37  ,     snake_case__="gelu"  ,     snake_case__=0.1  ,     snake_case__=0.1  ,     snake_case__=512  ,     snake_case__=16  ,     snake_case__=2  ,     snake_case__=0.02  ,     snake_case__=3  ,     snake_case__=4  ,     snake_case__=None  ,     ):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = parent
							_SCREAMING_SNAKE_CASE   :				List[str]							    = 13
							_SCREAMING_SNAKE_CASE   :				str							    = 7
							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = True
							_SCREAMING_SNAKE_CASE   :				Any							    = True
							_SCREAMING_SNAKE_CASE   :				int							    = True
							_SCREAMING_SNAKE_CASE   :				List[Any]							    = True
							_SCREAMING_SNAKE_CASE   :				Tuple							    = 99
							_SCREAMING_SNAKE_CASE   :				int							    = 384
							_SCREAMING_SNAKE_CASE   :				List[Any]							    = 2
							_SCREAMING_SNAKE_CASE   :				Tuple							    = 4
							_SCREAMING_SNAKE_CASE   :				str							    = 37
							_SCREAMING_SNAKE_CASE   :				List[str]							    = "gelu"
							_SCREAMING_SNAKE_CASE   :				Tuple							    = 0.1
							_SCREAMING_SNAKE_CASE   :				Tuple							    = 0.1
							_SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = 512
							_SCREAMING_SNAKE_CASE   :				Dict							    = 16
							_SCREAMING_SNAKE_CASE   :				Tuple							    = 2
							_SCREAMING_SNAKE_CASE   :				int							    = 0.02
							_SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = 3
							_SCREAMING_SNAKE_CASE   :				List[str]							    = 4
							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = 128
							_SCREAMING_SNAKE_CASE   :				str							    = 2
							_SCREAMING_SNAKE_CASE   :				str							    = 9
							_SCREAMING_SNAKE_CASE   :				Any							    = 1
							_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = None
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Dict							    = ids_tensor([self.batch_size, self.seq_length]  ,     self.vocab_size				)

							_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = None
							if self.use_input_mask:
									_SCREAMING_SNAKE_CASE   :				Any							    = random_attention_mask([self.batch_size, self.seq_length]				)

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

							_SCREAMING_SNAKE_CASE   :				Any							    = None
							_SCREAMING_SNAKE_CASE   :				int							    = None
							_SCREAMING_SNAKE_CASE   :				Any							    = None
							if self.use_labels:
									_SCREAMING_SNAKE_CASE   :				str							    = ids_tensor([self.batch_size]  ,     self.type_sequence_label_size				)
									_SCREAMING_SNAKE_CASE   :				Dict							    = ids_tensor([self.batch_size, self.seq_length]  ,     self.num_labels				)
									_SCREAMING_SNAKE_CASE   :				Optional[int]							    = ids_tensor([self.batch_size]  ,     self.num_choices				)

							_SCREAMING_SNAKE_CASE   :				int							    = ConvBertConfig(
							    vocab_size=self.vocab_size  ,     hidden_size=self.hidden_size  ,     num_hidden_layers=self.num_hidden_layers  ,     num_attention_heads=self.num_attention_heads  ,     intermediate_size=self.intermediate_size  ,     hidden_act=self.hidden_act  ,     hidden_dropout_prob=self.hidden_dropout_prob  ,     attention_probs_dropout_prob=self.attention_probs_dropout_prob  ,     max_position_embeddings=self.max_position_embeddings  ,     type_vocab_size=self.type_vocab_size  ,     initializer_range=self.initializer_range  ,     return_dict=snake_case__  ,     )

							return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels
					def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				List[Any]							    = TFConvBertModel(config=snake_case__				)
							_SCREAMING_SNAKE_CASE   :				str							    = {"input_ids": input_ids, "attention_mask": input_mask, "token_type_ids": token_type_ids}

							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = [input_ids, input_mask]
							_SCREAMING_SNAKE_CASE   :				List[str]							    = model(snake_case__				)

							_SCREAMING_SNAKE_CASE   :				Any							    = model(snake_case__				)

							self.parent.assertEqual(result.last_hidden_state.shape  ,     (self.batch_size, self.seq_length, self.hidden_size)				)
					def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Dict							    = TFConvBertForMaskedLM(config=snake_case__				)
							_SCREAMING_SNAKE_CASE   :				Any							    = {
							    "input_ids": input_ids,
							    "attention_mask": input_mask,
							    "token_type_ids": token_type_ids,
							}
							_SCREAMING_SNAKE_CASE   :				Any							    = model(snake_case__				)
							self.parent.assertEqual(result.logits.shape  ,     (self.batch_size, self.seq_length, self.vocab_size)				)
					def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				List[str]							    = self.num_labels
							_SCREAMING_SNAKE_CASE   :				List[Any]							    = TFConvBertForSequenceClassification(config=snake_case__				)
							_SCREAMING_SNAKE_CASE   :				Dict							    = {
							    "input_ids": input_ids,
							    "attention_mask": input_mask,
							    "token_type_ids": token_type_ids,
							}

							_SCREAMING_SNAKE_CASE   :				Any							    = model(snake_case__				)
							self.parent.assertEqual(result.logits.shape  ,     (self.batch_size, self.num_labels)				)
					def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = self.num_choices
							_SCREAMING_SNAKE_CASE   :				Any							    = TFConvBertForMultipleChoice(config=snake_case__				)
							_SCREAMING_SNAKE_CASE   :				str							    = tf.tile(tf.expand_dims(snake_case__  ,     1				)  ,     (1, self.num_choices, 1)				)
							_SCREAMING_SNAKE_CASE   :				List[str]							    = tf.tile(tf.expand_dims(snake_case__  ,     1				)  ,     (1, self.num_choices, 1)				)
							_SCREAMING_SNAKE_CASE   :				Tuple							    = tf.tile(tf.expand_dims(snake_case__  ,     1				)  ,     (1, self.num_choices, 1)				)
							_SCREAMING_SNAKE_CASE   :				Tuple							    = {
							    "input_ids": multiple_choice_inputs_ids,
							    "attention_mask": multiple_choice_input_mask,
							    "token_type_ids": multiple_choice_token_type_ids,
							}
							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = model(snake_case__				)
							self.parent.assertEqual(result.logits.shape  ,     (self.batch_size, self.num_choices)				)
					def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				int							    = self.num_labels
							_SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = TFConvBertForTokenClassification(config=snake_case__				)
							_SCREAMING_SNAKE_CASE   :				int							    = {
							    "input_ids": input_ids,
							    "attention_mask": input_mask,
							    "token_type_ids": token_type_ids,
							}
							_SCREAMING_SNAKE_CASE   :				str							    = model(snake_case__				)
							self.parent.assertEqual(result.logits.shape  ,     (self.batch_size, self.seq_length, self.num_labels)				)
					def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Tuple							    = TFConvBertForQuestionAnswering(config=snake_case__				)
							_SCREAMING_SNAKE_CASE   :				Tuple							    = {
							    "input_ids": input_ids,
							    "attention_mask": input_mask,
							    "token_type_ids": token_type_ids,
							}

							_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = model(snake_case__				)
							self.parent.assertEqual(result.start_logits.shape  ,     (self.batch_size, self.seq_length)				)
							self.parent.assertEqual(result.end_logits.shape  ,     (self.batch_size, self.seq_length)				)




					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				str							    = self.prepare_config_and_inputs()
							(
							    (
							    _SCREAMING_SNAKE_CASE		
							)    ,		(
							    _SCREAMING_SNAKE_CASE		
							)    ,		(
							    _SCREAMING_SNAKE_CASE		
							)    ,		(
							    _SCREAMING_SNAKE_CASE		
							)    ,		(
							    _SCREAMING_SNAKE_CASE		
							)    ,		(
							    _SCREAMING_SNAKE_CASE		
							)    ,		(
							    _SCREAMING_SNAKE_CASE		
							)    ,				
							)   :				Optional[int]							    = config_and_inputs
							_SCREAMING_SNAKE_CASE   :				List[Any]							    = {"input_ids": input_ids, "token_type_ids": token_type_ids, "attention_mask": input_mask}
							return config, inputs_dict
@require_tf
class 			UpperCamelCase      (							__UpperCAmelCase      ,       __UpperCAmelCase      ,       unittest.TestCase  ):
					A__      =			(
					    (
					        TFConvBertModel,
					        TFConvBertForMaskedLM,
					        TFConvBertForQuestionAnswering,
					        TFConvBertForSequenceClassification,
					        TFConvBertForTokenClassification,
					        TFConvBertForMultipleChoice,
					    )
					    if is_tf_available()
					    else ()
					)
					A__      =			(
					    {
					        """feature-extraction""": TFConvBertModel,
					        """fill-mask""": TFConvBertForMaskedLM,
					        """question-answering""": TFConvBertForQuestionAnswering,
					        """text-classification""": TFConvBertForSequenceClassification,
					        """token-classification""": TFConvBertForTokenClassification,
					        """zero-shot""": TFConvBertForSequenceClassification,
					    }
					    if is_tf_available()
					    else {}
					)
					A__      =			False
					A__      =			False
					A__      =			False
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Dict							    = TFConvBertModelTester(self				)
							_SCREAMING_SNAKE_CASE   :				str							    = ConfigTester(self  ,     config_class=snake_case__  ,     hidden_size=37				)
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							self.config_tester.run_common_tests()
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				str							    = self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_model(*snake_case__				)
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Any							    = self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_masked_lm(*snake_case__				)
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_multiple_choice(*snake_case__				)
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Tuple							    = self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_question_answering(*snake_case__				)
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				str							    = self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_sequence_classification(*snake_case__				)
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				List[Any]							    = self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_token_classification(*snake_case__				)
					@slow
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				str							    = self.model_tester.prepare_config_and_inputs_for_common()
							_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = True
							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = True

							if hasattr(snake_case__  ,     "use_cache"				):
									_SCREAMING_SNAKE_CASE   :				Dict							    = True

							_SCREAMING_SNAKE_CASE   :				Dict							    = getattr(self.model_tester  ,     "encoder_seq_length"  ,     self.model_tester.seq_length				)
							_SCREAMING_SNAKE_CASE   :				Tuple							    = getattr(self.model_tester  ,     "key_length"  ,     snake_case__				)

							for model_class in self.all_model_classes:
									_SCREAMING_SNAKE_CASE   :				Optional[int]							    = self._prepare_for_class(snake_case__  ,     snake_case__				)
									_SCREAMING_SNAKE_CASE   :				List[str]							    = model_class(snake_case__				)
									_SCREAMING_SNAKE_CASE   :				int							    = len(model(snake_case__				)				)

									with tempfile.TemporaryDirectory() as tmpdirname:
											model.save_pretrained(snake_case__  ,     saved_model=snake_case__				)
											_SCREAMING_SNAKE_CASE   :				Any							    = os.path.join(snake_case__  ,     "saved_model"  ,     "1"				)
											_SCREAMING_SNAKE_CASE   :				Tuple							    = tf.keras.models.load_model(snake_case__				)
											_SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = model(snake_case__				)

											if self.is_encoder_decoder:
													_SCREAMING_SNAKE_CASE   :				Any							    = outputs["encoder_hidden_states"]
													_SCREAMING_SNAKE_CASE   :				str							    = outputs["encoder_attentions"]
											else:
													_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = outputs["hidden_states"]
													_SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = outputs["attentions"]

											self.assertEqual(len(snake_case__				)  ,     snake_case__				)

											_SCREAMING_SNAKE_CASE   :				Dict							    = getattr(
											    self.model_tester  ,     "expected_num_hidden_layers"  ,     self.model_tester.num_hidden_layers + 1				)

											self.assertEqual(len(snake_case__				)  ,     snake_case__				)
											self.assertListEqual(
											    list(output_hidden_states[0].shape[-2:]				)  ,     [self.model_tester.seq_length, self.model_tester.hidden_size]  ,     )

											self.assertEqual(len(snake_case__				)  ,     self.model_tester.num_hidden_layers				)
											self.assertListEqual(
											    list(output_attentions[0].shape[-3:]				)  ,     [self.model_tester.num_attention_heads / 2, encoder_seq_length, encoder_key_length]  ,     )
					@slow
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				str							    = TFConvBertModel.from_pretrained("YituTech/conv-bert-base"				)
							self.assertIsNotNone(snake_case__				)




					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE    ,		_SCREAMING_SNAKE_CASE   :				str							    = self.model_tester.prepare_config_and_inputs_for_common()
							_SCREAMING_SNAKE_CASE   :				Any							    = True
							_SCREAMING_SNAKE_CASE   :				str							    = getattr(self.model_tester  ,     "decoder_seq_length"  ,     self.model_tester.seq_length				)
							_SCREAMING_SNAKE_CASE   :				str							    = getattr(self.model_tester  ,     "encoder_seq_length"  ,     self.model_tester.seq_length				)
							_SCREAMING_SNAKE_CASE   :				List[str]							    = getattr(self.model_tester  ,     "key_length"  ,     snake_case__				)
							_SCREAMING_SNAKE_CASE   :				str							    = getattr(self.model_tester  ,     "key_length"  ,     snake_case__				)

							def check_decoder_attentions_output(snake_case__				):
									_SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = len(snake_case__				)
									self.assertEqual(out_len % 2  ,     0				)
									_SCREAMING_SNAKE_CASE   :				int							    = outputs.decoder_attentions
									self.assertEqual(len(snake_case__				)  ,     self.model_tester.num_hidden_layers				)
									self.assertListEqual(
									    list(decoder_attentions[0].shape[-3:]				)  ,     [self.model_tester.num_attention_heads / 2, decoder_seq_length, decoder_key_length]  ,     )

							def check_encoder_attentions_output(snake_case__				):
									_SCREAMING_SNAKE_CASE   :				Dict							    = [
									    t.numpy() for t in (outputs.encoder_attentions if config.is_encoder_decoder else outputs.attentions)
									]
									self.assertEqual(len(snake_case__				)  ,     self.model_tester.num_hidden_layers				)
									self.assertListEqual(
									    list(attentions[0].shape[-3:]				)  ,     [self.model_tester.num_attention_heads / 2, encoder_seq_length, encoder_key_length]  ,     )

							for model_class in self.all_model_classes:
									_SCREAMING_SNAKE_CASE   :				Tuple							    = True
									_SCREAMING_SNAKE_CASE   :				Tuple							    = False
									_SCREAMING_SNAKE_CASE   :				Dict							    = model_class(snake_case__				)
									_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = model(self._prepare_for_class(snake_case__  ,     snake_case__				)				)
									_SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = len(snake_case__				)
									self.assertEqual(config.output_hidden_states  ,     snake_case__				)
									check_encoder_attentions_output(snake_case__				)

									if self.is_encoder_decoder:
											_SCREAMING_SNAKE_CASE   :				Optional[int]							    = model_class(snake_case__				)
											_SCREAMING_SNAKE_CASE   :				Optional[int]							    = model(self._prepare_for_class(snake_case__  ,     snake_case__				)				)
											self.assertEqual(config.output_hidden_states  ,     snake_case__				)
											check_decoder_attentions_output(snake_case__				)

									# Check that output attentions can also be changed via the config
									del inputs_dict["output_attentions"]
									_SCREAMING_SNAKE_CASE   :				Dict							    = True
									_SCREAMING_SNAKE_CASE   :				int							    = model_class(snake_case__				)
									_SCREAMING_SNAKE_CASE   :				Optional[int]							    = model(self._prepare_for_class(snake_case__  ,     snake_case__				)				)
									self.assertEqual(config.output_hidden_states  ,     snake_case__				)
									check_encoder_attentions_output(snake_case__				)

									# Check attention is always last and order is fine
									_SCREAMING_SNAKE_CASE   :				str							    = True
									_SCREAMING_SNAKE_CASE   :				int							    = True
									_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = model_class(snake_case__				)
									_SCREAMING_SNAKE_CASE   :				int							    = model(self._prepare_for_class(snake_case__  ,     snake_case__				)				)

									self.assertEqual(out_len + (2 if self.is_encoder_decoder else 1)  ,     len(snake_case__				)				)
									self.assertEqual(model.config.output_hidden_states  ,     snake_case__				)
									check_encoder_attentions_output(snake_case__				)
@require_tf
class 			UpperCamelCase      (							unittest.TestCase  ):
					@slow
					def 				__SCREAMING_SNAKE_CASE							(     self				):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Any							    = TFConvBertModel.from_pretrained("YituTech/conv-bert-base"				)
							_SCREAMING_SNAKE_CASE   :				str							    = tf.constant([[0, 1, 2, 3, 4, 5]]				)
							_SCREAMING_SNAKE_CASE   :				int							    = model(snake_case__				)[0]

							_SCREAMING_SNAKE_CASE   :				Tuple							    = [1, 6, 768]
							self.assertEqual(output.shape  ,     snake_case__				)

							_SCREAMING_SNAKE_CASE   :				Dict							    = tf.constant(
							    [
							        [
							            [-0.03_475_493, -0.4_686_034, -0.30_638_832],
							            [0.22_637_248, -0.26_988_646, -0.7_423_424],
							            [0.10_324_868, -0.45_013_508, -0.58_280_784],
							        ]
							    ]				)
							tf.debugging.assert_near(output[:, :3, :3]  ,     snake_case__  ,     atol=1E-4				)





"""simple docstring"""
from collections.abc import Iterable
from typing import Any
class 			UpperCamelCase      :
     def __init__(     self  ,     snake_case__ = None				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				List[str]							    = value
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None  # Added in order to delete a node easier
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None




     def __repr__(     self				):




       """simple docstring"""


       from pprint import pformat

       if self.left is None and self.right is None:
         return str(self.value				)
       return pformat({F'''{self.value}''': (self.left, self.right)}  ,     indent=1				)
class 			UpperCamelCase      :
     def __init__(     self  ,     snake_case__ = None				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				List[str]							    = root
     def __str__(     self				):




       """simple docstring"""


       return str(self.root				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       if new_children is not None:  # reset its kids
         _SCREAMING_SNAKE_CASE   :				Dict							    = node.parent
       if node.parent is not None:  # reset its parent
         if self.is_right(snake_case__				):  # If it is the right children
           _SCREAMING_SNAKE_CASE   :				Any							    = new_children
         else:
           _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = new_children
       else:
         _SCREAMING_SNAKE_CASE   :				Any							    = new_children
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if node.parent and node.parent.right:
         return node == node.parent.right
       return False
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return self.root is None
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Optional[int]							    = Node(snake_case__				)  # create a new Node
       if self.empty():  # if Tree is empty
         _SCREAMING_SNAKE_CASE   :				str							    = new_node  # set its root
       else:  # Tree is not empty
         _SCREAMING_SNAKE_CASE   :				Dict							    = self.root  # from root
         if parent_node is None:
           return
         while True:  # While we don't get to a leaf
           if value < parent_node.value:  # We go left
             if parent_node.left is None:
               _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = new_node  # We insert the new node in a leaf
               break
             else:
               _SCREAMING_SNAKE_CASE   :				int							    = parent_node.left
           else:
             if parent_node.right is None:
               _SCREAMING_SNAKE_CASE   :				str							    = new_node
               break
             else:
               _SCREAMING_SNAKE_CASE   :				Optional[int]							    = parent_node.right
         _SCREAMING_SNAKE_CASE   :				Any							    = parent_node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     *snake_case__				):




       """simple docstring"""


       for value in values:
         self.__insert(snake_case__				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if self.empty():
         raise IndexError("Warning: Tree is empty! please use another."				)
       else:
         _SCREAMING_SNAKE_CASE   :				Optional[int]							    = self.root
         # use lazy evaluation here to avoid NoneType Attribute error
         while node is not None and node.value is not value:
           _SCREAMING_SNAKE_CASE   :				List[Any]							    = node.left if value < node.value else node.right
         return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__ = None				):




       """simple docstring"""


       if node is None:
         if self.root is None:
           return None
         _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = self.root

       if not self.empty():
         while node.right is not None:
           _SCREAMING_SNAKE_CASE   :				Dict							    = node.right
       return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__ = None				):




       """simple docstring"""


       if node is None:
         _SCREAMING_SNAKE_CASE   :				List[Any]							    = self.root
       if self.root is None:
         return None
       if not self.empty():
         _SCREAMING_SNAKE_CASE   :				Any							    = self.root
         while node.left is not None:
           _SCREAMING_SNAKE_CASE   :				Optional[int]							    = node.left
       return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Dict							    = self.search(snake_case__				)  # Look for the node with that label
       if node is not None:
         if node.left is None and node.right is None:  # If it has no children
           self.__reassign_nodes(snake_case__  ,     snake_case__				)
         elif node.left is None:  # Has only right children
           self.__reassign_nodes(snake_case__  ,     node.right				)
         elif node.right is None:  # Has only left children
           self.__reassign_nodes(snake_case__  ,     node.left				)
         else:
           _SCREAMING_SNAKE_CASE   :				Dict							    = self.get_max(
               node.left				)  # Gets the max value of the left branch
           self.remove(tmp_node.value				)  # type: ignore
           _SCREAMING_SNAKE_CASE   :				List[Any]							    = (
               tmp_node.value  # type: ignore
           )  # Assigns the value to the node to delete and keep tree structure
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if node is not None:
         yield node  # Preorder Traversal
         yield from self.preorder_traverse(node.left				)
         yield from self.preorder_traverse(node.right				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__=None				):




       """simple docstring"""


       if traversal_function is None:
         return self.preorder_traverse(self.root				)
       else:
         return traversal_function(self.root				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       if node:
         self.inorder(snake_case__  ,     node.left				)
         arr.append(node.value				)
         self.inorder(snake_case__  ,     node.right				)




     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				list[int]							    = []
       self.inorder(snake_case__  ,     snake_case__				)  # append all values to list using inorder traversal
       return arr[k - 1]





def    _lowerCAmelCase    (     lowerCamelCase__							:							Node | None				)  ->    list[Node]:
  _SCREAMING_SNAKE_CASE   :				Optional[int]							    = []
  if curr_node is not None:
    _SCREAMING_SNAKE_CASE   :				int							    = postorder(curr_node.left				) + postorder(curr_node.right				) + [curr_node]
  return node_list





def    _lowerCAmelCase    (     )  ->    None:
  _SCREAMING_SNAKE_CASE   :				Any							    = (8, 3, 6, 1, 1_0, 1_4, 1_3, 4, 7)
  _SCREAMING_SNAKE_CASE   :				List[Any]							    = BinarySearchTree()
  for i in testlist:
    t.insert(lowerCamelCase__				)

  # Prints all the elements of the list in order traversal
  print(lowerCamelCase__				)

  if t.search(6				) is not None:
    print("The value 6 exists"				)
  else:
    print("The value 6 doesn't exist"				)

  if t.search(-1				) is not None:
    print("The value -1 exists"				)
  else:
    print("The value -1 doesn't exist"				)

  if not t.empty():
    print("Max Value: ",						t.get_max().value				)  # type: ignore
    print("Min Value: ",						t.get_min().value				)  # type: ignore

  for i in testlist:
    t.remove(lowerCamelCase__				)
    print(lowerCamelCase__				)


if __name__ == "__main__":
      import doctest

      doctest.testmod(verbose=True)



