


'''simple docstring'''



import collections
import tempfile
import unittest

import numpy as np

from transformers.testing_utils import (
    is_pt_flax_cross_test,
    require_flax,
    require_torch,
    require_vision,
    slow,
    torch_device,
)
from transformers.utils import is_flax_available, is_torch_available, is_vision_available

from ...test_modeling_flax_common import floats_tensor, ids_tensor, random_attention_mask
from ..bert.test_modeling_flax_bert import FlaxBertModelTester
from ..clip.test_modeling_flax_clip import FlaxCLIPVisionModelTester
from ..vit.test_modeling_flax_vit import FlaxViTModelTester


if is_flax_available():
      from transformers import (
          FlaxBertModel,
          FlaxCLIPVisionModel,
          FlaxVisionTextDualEncoderModel,
          FlaxViTModel,
          VisionTextDualEncoderConfig,
          VisionTextDualEncoderProcessor,
      )
      from transformers.modeling_flax_pytorch_utils import (
          convert_pytorch_state_dict_to_flax,
          load_flax_weights_in_pytorch_model,
      )


if is_torch_available():
      import torch

      from transformers import VisionTextDualEncoderModel

if is_vision_available():
      from PIL import Image




def 			_a			(		_lowercase      :			Optional[int]						):





     '''simple docstring'''






     if isinstance(_lowercase    ,      collections.abc.Iterable						):
          return x
     return (x, x)



@require_flax
class 			a       :


     """simple docstring"""






     def 				lowerCamelCase__				(       self  :	List[Any]							,				snake_case  :	int							,				snake_case  :	Optional[int]    )		->							Optional[int]:
          pass

     def 				lowerCamelCase__				(       self  :	Any    )		->							int:
          pass

     def 				lowerCamelCase__				(       self  :	Optional[Any]    )		->							str:
          pass

     def 				lowerCamelCase__				(       self  :	str							,				snake_case  :	np.ndarray							,				snake_case  :	np.ndarray							,				snake_case  :	float    )		->							Optional[int]:
          __UpperCAmelCase			:				Optional[Any]													=    np.abs((a - b)    ).max()
          self.assertLessEqual(snake_case							,				snake_case							,				f'Difference between torch and flax is {diff} (>= {tol}).'    )

     def 				lowerCamelCase__				(       self  :	int							,				snake_case  :	Optional[Any]							,				snake_case  :	int							,				snake_case  :	Tuple							,				snake_case  :	List[str]							,				snake_case  :	Optional[Any]=None							,				**snake_case  :	int    )		->							Optional[int]:
          __UpperCAmelCase			:				int													=    VisionTextDualEncoderConfig.from_vision_text_configs(snake_case							,				snake_case    )

          __UpperCAmelCase			:				str													=    FlaxVisionTextDualEncoderModel(snake_case    )

          __UpperCAmelCase			:				Dict													=    model(input_ids=snake_case							,				pixel_values=snake_case							,				attention_mask=snake_case    )

          self.assertEqual(output['''text_embeds'''].shape							,				(input_ids.shape[0], config.projection_dim)    )
          self.assertEqual(output['''image_embeds'''].shape							,				(pixel_values.shape[0], config.projection_dim)    )

     def 				lowerCamelCase__				(       self  :	Optional[Any]							,				snake_case  :	Optional[int]							,				snake_case  :	int							,				snake_case  :	Tuple							,				snake_case  :	List[str]							,				snake_case  :	int=None							,				**snake_case  :	int    )		->							Dict:
          __UpperCAmelCase							,     __UpperCAmelCase			:				str													=    self.get_vision_text_model(snake_case							,				snake_case    )
          __UpperCAmelCase			:				Tuple													=    {'''vision_model''': vision_model, '''text_model''': text_model}
          __UpperCAmelCase			:				List[Any]													=    FlaxVisionTextDualEncoderModel.from_vision_text_pretrained(**snake_case    )

          __UpperCAmelCase			:				Optional[int]													=    model(input_ids=snake_case							,				pixel_values=snake_case							,				attention_mask=snake_case    )

          self.assertEqual(output['''text_embeds'''].shape							,				(input_ids.shape[0], model.config.projection_dim)    )
          self.assertEqual(output['''image_embeds'''].shape							,				(pixel_values.shape[0], model.config.projection_dim)    )

     def 				lowerCamelCase__				(       self  :	Optional[int]							,				snake_case  :	Any							,				snake_case  :	List[Any]							,				snake_case  :	Optional[Any]							,				snake_case  :	Any							,				snake_case  :	List[str]=None							,				**snake_case  :	int    )		->							List[str]:
          __UpperCAmelCase							,     __UpperCAmelCase			:				Dict													=    self.get_vision_text_model(snake_case							,				snake_case    )
          __UpperCAmelCase			:				Dict													=    {'''vision_model''': vision_model, '''text_model''': text_model}
          __UpperCAmelCase			:				List[str]													=    FlaxVisionTextDualEncoderModel.from_vision_text_pretrained(**snake_case    )

          __UpperCAmelCase			:				Any													=    model(input_ids=snake_case							,				pixel_values=snake_case							,				attention_mask=snake_case    )
          __UpperCAmelCase			:				List[str]													=    output[0]

          with tempfile.TemporaryDirectory() as tmpdirname:
               model.save_pretrained(snake_case    )
               __UpperCAmelCase			:				Optional[int]													=    FlaxVisionTextDualEncoderModel.from_pretrained(snake_case    )

               __UpperCAmelCase			:				Dict													=    model(input_ids=snake_case							,				pixel_values=snake_case							,				attention_mask=snake_case    )
               __UpperCAmelCase			:				Any													=    after_output[0]
               __UpperCAmelCase			:				List[str]													=    np.amax(np.abs(out_a - out_a    )    )
               self.assertLessEqual(snake_case							,				1E-3    )

     def 				lowerCamelCase__				(       self  :	int							,				snake_case  :	Any							,				snake_case  :	Dict							,				snake_case  :	Optional[Any]							,				snake_case  :	str							,				snake_case  :	Optional[int]=None							,				**snake_case  :	Union[str, Any]    )		->							Union[str, Any]:
          __UpperCAmelCase							,     __UpperCAmelCase			:				List[Any]													=    self.get_vision_text_model(snake_case							,				snake_case    )
          __UpperCAmelCase			:				str													=    {'''vision_model''': vision_model, '''text_model''': text_model}
          __UpperCAmelCase			:				Tuple													=    FlaxVisionTextDualEncoderModel.from_vision_text_pretrained(**snake_case    )

          __UpperCAmelCase			:				List[Any]													=    model(
              input_ids=snake_case							,				pixel_values=snake_case							,				attention_mask=snake_case							,				output_attentions=snake_case    )

          __UpperCAmelCase			:				Union[str, Any]													=    output.vision_model_output.attentions
          self.assertEqual(len(snake_case    )							,				vision_config.num_hidden_layers    )

          # in ViT, the seq_len equals the number of patches + 1 (we add 1 for the [CLS] token)
          __UpperCAmelCase			:				Tuple													=    to_atuple(vision_model.config.image_size    )
          __UpperCAmelCase			:				Any													=    to_atuple(vision_model.config.patch_size    )
          __UpperCAmelCase			:				str													=    (image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])
          __UpperCAmelCase			:				Dict													=    num_patches + 1
          self.assertEqual(vision_attentions[0].shape[-3:]							,				(vision_config.num_attention_heads, seq_len, seq_len)    )

          __UpperCAmelCase			:				Dict													=    output.text_model_output.attentions
          self.assertEqual(len(snake_case    )							,				text_config.num_hidden_layers    )

          self.assertEqual(
              text_attentions[0].shape[-3:]							,				(text_config.num_attention_heads, input_ids.shape[-1], input_ids.shape[-1])							,				)

     def 				lowerCamelCase__				(       self  :	Optional[Any]							,				snake_case  :	Union[str, Any]							,				snake_case  :	Tuple							,				snake_case  :	int    )		->							Optional[int]:
          pt_model.to(snake_case    )
          pt_model.eval()

          # prepare inputs
          __UpperCAmelCase			:				str													=    inputs_dict
          __UpperCAmelCase			:				List[str]													=    {k: torch.tensor(v.tolist()    ) for k, v in flax_inputs.items()}

          with torch.no_grad():
               __UpperCAmelCase			:				Union[str, Any]													=    pt_model(**snake_case    ).to_tuple()

          __UpperCAmelCase			:				str													=    fx_model(**snake_case    ).to_tuple()
          self.assertEqual(len(snake_case    )							,				len(snake_case    )							,				'''Output lengths differ between Flax and PyTorch'''    )
          for fx_output, pt_output in zip(fx_outputs[:4]							,				pt_outputs[:4]    ):
               self.assert_almost_equals(snake_case							,				pt_output.numpy()							,				4E-2    )

          # PT -> Flax
          with tempfile.TemporaryDirectory() as tmpdirname:
               pt_model.save_pretrained(snake_case    )
               __UpperCAmelCase			:				Tuple													=    FlaxVisionTextDualEncoderModel.from_pretrained(snake_case							,				from_pt=snake_case    )

          __UpperCAmelCase			:				str													=    fx_model_loaded(**snake_case    ).to_tuple()
          self.assertEqual(len(snake_case    )							,				len(snake_case    )							,				'''Output lengths differ between Flax and PyTorch'''    )
          for fx_output_loaded, pt_output in zip(fx_outputs_loaded[:4]							,				pt_outputs[:4]    ):
               self.assert_almost_equals(snake_case							,				pt_output.numpy()							,				4E-2    )

          # Flax -> PT
          with tempfile.TemporaryDirectory() as tmpdirname:
               fx_model.save_pretrained(snake_case    )
               __UpperCAmelCase			:				Tuple													=    VisionTextDualEncoderModel.from_pretrained(snake_case							,				from_flax=snake_case    )

          pt_model_loaded.to(snake_case    )
          pt_model_loaded.eval()

          with torch.no_grad():
               __UpperCAmelCase			:				int													=    pt_model_loaded(**snake_case    ).to_tuple()

          self.assertEqual(len(snake_case    )							,				len(snake_case    )							,				'''Output lengths differ between Flax and PyTorch'''    )
          for fx_output, pt_output_loaded in zip(fx_outputs[:4]							,				pt_outputs_loaded[:4]    ):
               self.assert_almost_equals(snake_case							,				pt_output_loaded.numpy()							,				4E-2    )

     def 				lowerCamelCase__				(       self  :	Dict							,				snake_case  :	Any							,				snake_case  :	List[Any]							,				snake_case  :	List[str]    )		->							str:
          __UpperCAmelCase			:				List[Any]													=    VisionTextDualEncoderConfig.from_vision_text_configs(snake_case							,				snake_case    )

          __UpperCAmelCase			:				Dict													=    VisionTextDualEncoderModel(snake_case    )
          __UpperCAmelCase			:				str													=    FlaxVisionTextDualEncoderModel(snake_case    )

          __UpperCAmelCase			:				Tuple													=    convert_pytorch_state_dict_to_flax(pt_model.state_dict()							,				snake_case    )
          __UpperCAmelCase			:				Tuple													=    fx_state

          self.check_pt_flax_equivalence(snake_case							,				snake_case							,				snake_case    )

     def 				lowerCamelCase__				(       self  :	Tuple							,				snake_case  :	Optional[Any]							,				snake_case  :	Optional[int]							,				snake_case  :	Dict    )		->							Tuple:
          __UpperCAmelCase			:				Optional[int]													=    VisionTextDualEncoderConfig.from_vision_text_configs(snake_case							,				snake_case    )

          __UpperCAmelCase			:				Optional[Any]													=    VisionTextDualEncoderModel(snake_case    )
          __UpperCAmelCase			:				Tuple													=    FlaxVisionTextDualEncoderModel(snake_case    )

          __UpperCAmelCase			:				int													=    load_flax_weights_in_pytorch_model(snake_case							,				fx_model.params    )

          self.check_pt_flax_equivalence(snake_case							,				snake_case							,				snake_case    )

     def 				lowerCamelCase__				(       self  :	List[str]    )		->							Union[str, Any]:
          __UpperCAmelCase			:				List[Any]													=    self.prepare_config_and_inputs()
          self.check_model_from_pretrained_configs(**snake_case    )

     def 				lowerCamelCase__				(       self  :	Dict    )		->							str:
          __UpperCAmelCase			:				Optional[Any]													=    self.prepare_config_and_inputs()
          self.check_vision_text_dual_encoder_from_pretrained(**snake_case    )

     def 				lowerCamelCase__				(       self  :	List[Any]    )		->							str:
          __UpperCAmelCase			:				Any													=    self.prepare_config_and_inputs()
          self.check_save_load(**snake_case    )

     def 				lowerCamelCase__				(       self  :	str    )		->							Dict:
          __UpperCAmelCase			:				int													=    self.prepare_config_and_inputs()
          self.check_vision_text_output_attention(**snake_case    )

     @is_pt_flax_cross_test
     def 				lowerCamelCase__				(       self  :	Any    )		->							str:
          __UpperCAmelCase			:				Optional[Any]													=    self.prepare_config_and_inputs()
          __UpperCAmelCase			:				Tuple													=    config_inputs_dict.pop('''vision_config'''    )
          __UpperCAmelCase			:				Union[str, Any]													=    config_inputs_dict.pop('''text_config'''    )

          __UpperCAmelCase			:				List[Any]													=    config_inputs_dict

          self.check_equivalence_pt_to_flax(snake_case							,				snake_case							,				snake_case    )
          self.check_equivalence_flax_to_pt(snake_case							,				snake_case							,				snake_case    )






     @slow
     def 				lowerCamelCase__				(       self  :	List[str]    )		->							int:
          __UpperCAmelCase							,     __UpperCAmelCase			:				Any													=    self.get_pretrained_model_and_inputs()

          __UpperCAmelCase			:				str													=    model_a(**snake_case    )
          __UpperCAmelCase			:				int													=    outputs[0]

          with tempfile.TemporaryDirectory() as tmp_dirname:
               model_a.save_pretrained(snake_case    )
               __UpperCAmelCase			:				List[Any]													=    FlaxVisionTextDualEncoderModel.from_pretrained(snake_case    )

               __UpperCAmelCase			:				Any													=    model_a(**snake_case    )
               __UpperCAmelCase			:				str													=    after_outputs[0]
               __UpperCAmelCase			:				Dict													=    np.amax(np.abs(out_a - out_a    )    )
               self.assertLessEqual(snake_case							,				1E-5    )



@require_flax
class 			a       (	_a			,						unittest.TestCase ):


     """simple docstring"""






     def 				lowerCamelCase__				(       self  :	int    )		->							Union[str, Any]:
          __UpperCAmelCase			:				List[Any]													=    FlaxVisionTextDualEncoderModel.from_vision_text_pretrained(
              '''hf-internal-testing/tiny-random-vit'''							,				'''hf-internal-testing/tiny-bert'''							,				vision_from_pt=snake_case							,				text_from_pt=snake_case							,				)
          __UpperCAmelCase			:				Any													=    13
          __UpperCAmelCase			:				List[Any]													=    floats_tensor(
              [
                  batch_size,
                  model.config.vision_config.num_channels,
                  model.config.vision_config.image_size,
                  model.config.vision_config.image_size,
              ]    )
          __UpperCAmelCase			:				Dict													=    ids_tensor([batch_size, 4]							,				model.config.text_config.vocab_size    )
          __UpperCAmelCase			:				Optional[int]													=    random_attention_mask([batch_size, 4]    )
          __UpperCAmelCase			:				Any													=    {'''pixel_values''': pixel_values, '''input_ids''': input_ids, '''attention_mask''': attention_mask}

          return model, inputs

     def 				lowerCamelCase__				(       self  :	List[str]							,				snake_case  :	Optional[Any]							,				snake_case  :	Optional[Any]    )		->							Union[str, Any]:
          __UpperCAmelCase			:				Union[str, Any]													=    FlaxViTModel(snake_case    )
          __UpperCAmelCase			:				Dict													=    FlaxBertModel(snake_case    )
          return vision_model, text_model






     def 				lowerCamelCase__				(       self  :	int    )		->							List[Any]:
          __UpperCAmelCase			:				List[Any]													=    FlaxViTModelTester(self    )
          __UpperCAmelCase			:				Tuple													=    FlaxBertModelTester(self    )
          __UpperCAmelCase			:				str													=    vit_model_tester.prepare_config_and_inputs()
          __UpperCAmelCase			:				Tuple													=    bert_model_tester.prepare_config_and_inputs()

          __UpperCAmelCase							,     __UpperCAmelCase			:				Union[str, Any]													=    vision_config_and_inputs

          __UpperCAmelCase							,     __UpperCAmelCase							,     __UpperCAmelCase							,     __UpperCAmelCase			:				Union[str, Any]													=    text_config_and_inputs

          # make sure that cross attention layers are added
          return {
              "text_config": text_config,
              "vision_config": vision_config,
              "pixel_values": pixel_values,
              "attention_mask": attention_mask,
              "input_ids": input_ids,
              "token_type_ids": token_type_ids,
          }



@require_torch
class 			a       (	_a			,						unittest.TestCase ):


     """simple docstring"""






     def 				lowerCamelCase__				(       self  :	Optional[int]    )		->							Tuple:
          __UpperCAmelCase			:				List[Any]													=    FlaxVisionTextDualEncoderModel.from_vision_text_pretrained(
              '''hf-internal-testing/tiny-random-clip'''							,				'''hf-internal-testing/tiny-bert'''							,				vision_from_pt=snake_case							,				text_from_pt=snake_case							,				)
          __UpperCAmelCase			:				Any													=    13
          __UpperCAmelCase			:				str													=    floats_tensor(
              [
                  batch_size,
                  model.config.vision_config.num_channels,
                  model.config.vision_config.image_size,
                  model.config.vision_config.image_size,
              ]    )
          __UpperCAmelCase			:				Optional[Any]													=    ids_tensor([batch_size, 4]							,				model.config.text_config.vocab_size    )
          __UpperCAmelCase			:				Dict													=    random_attention_mask([batch_size, 4]    )
          __UpperCAmelCase			:				Optional[int]													=    {'''pixel_values''': pixel_values, '''input_ids''': input_ids, '''attention_mask''': attention_mask}

          return model, inputs

     def 				lowerCamelCase__				(       self  :	List[Any]							,				snake_case  :	Union[str, Any]							,				snake_case  :	Union[str, Any]    )		->							Union[str, Any]:
          __UpperCAmelCase			:				Optional[Any]													=    FlaxCLIPVisionModel(snake_case    )
          __UpperCAmelCase			:				Any													=    FlaxBertModel(snake_case    )
          return vision_model, text_model






     def 				lowerCamelCase__				(       self  :	int    )		->							Optional[int]:
          __UpperCAmelCase			:				List[str]													=    FlaxCLIPVisionModelTester(self    )
          __UpperCAmelCase			:				Dict													=    FlaxBertModelTester(self    )
          __UpperCAmelCase			:				Any													=    clip_model_tester.prepare_config_and_inputs()
          __UpperCAmelCase			:				Union[str, Any]													=    bert_model_tester.prepare_config_and_inputs()

          __UpperCAmelCase							,     __UpperCAmelCase			:				Any													=    vision_config_and_inputs

          __UpperCAmelCase							,     __UpperCAmelCase							,     __UpperCAmelCase							,     __UpperCAmelCase			:				Dict													=    text_config_and_inputs

          # make sure that cross attention layers are added
          return {
              "text_config": text_config,
              "vision_config": vision_config,
              "pixel_values": pixel_values,
              "attention_mask": attention_mask,
              "input_ids": input_ids,
              "token_type_ids": token_type_ids,
          }



@require_flax
@require_vision
class 			a       (	unittest.TestCase ):


     """simple docstring"""






     @slow
     def 				lowerCamelCase__				(       self  :	List[Any]    )		->							List[Any]:
          __UpperCAmelCase			:				Any													=    FlaxVisionTextDualEncoderModel.from_pretrained('''clip-italian/clip-italian'''							,				logit_scale_init_value=1.0    )
          __UpperCAmelCase			:				str													=    VisionTextDualEncoderProcessor.from_pretrained('''clip-italian/clip-italian'''    )

          __UpperCAmelCase			:				Optional[int]													=    Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''    )
          __UpperCAmelCase			:				Any													=    processor(
              text=['''una foto di un gatto''', '''una foto di un cane''']							,				images=snake_case							,				padding=snake_case							,				return_tensors='''np'''    )

          __UpperCAmelCase			:				List[str]													=    model(**snake_case    )

          # verify the logits
          self.assertEqual(outputs.logits_per_image.shape							,				(inputs.pixel_values.shape[0], inputs.input_ids.shape[0])    )
          self.assertEqual(
              outputs.logits_per_text.shape							,				(inputs.input_ids.shape[0], inputs.pixel_values.shape[0])							,				)

          __UpperCAmelCase			:				Optional[Any]													=    np.array([[1.2_284_727, 0.3_104_122]]    )

          self.assertTrue(np.allclose(outputs.logits_per_image							,				snake_case							,				atol=1E-3    )    )



'''simple docstring'''



from collections.abc import Iterable
from typing import Any



class 			a       :


     """simple docstring"""






     def __init__(       self  :	Any							,				snake_case  :	int | None = None    )		->							int:
          __UpperCAmelCase			:				str													=    value
          __UpperCAmelCase			:				Node | None													=    None  # Added in order to delete a node easier
          __UpperCAmelCase			:				Node | None													=    None
          __UpperCAmelCase			:				Node | None													=    None






     def __repr__(       self  :	str    )		->							str:
          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 			a       :


     """simple docstring"""






     def __init__(       self  :	Optional[int]							,				snake_case  :	Node | None = None    )		->							str:
          __UpperCAmelCase			:				Optional[Any]													=    root

     def __str__(       self  :	str    )		->							str:
          return str(self.root    )

     def 				lowerCamelCase__				(       self  :	Union[str, Any]							,				snake_case  :	Node							,				snake_case  :	Node | None    )		->							None:
          if new_children is not None:  # reset its kids
               __UpperCAmelCase			:				List[str]													=    node.parent
          if node.parent is not None:  # reset its parent
               if self.is_right(snake_case    ):  # If it is the right children
                    __UpperCAmelCase			:				int													=    new_children
               else:
                    __UpperCAmelCase			:				Tuple													=    new_children
          else:
               __UpperCAmelCase			:				List[Any]													=    new_children

     def 				lowerCamelCase__				(       self  :	Optional[int]							,				snake_case  :	Node    )		->							bool:
          if node.parent and node.parent.right:
               return node == node.parent.right
          return False

     def 				lowerCamelCase__				(       self  :	int    )		->							bool:
          return self.root is None

     def 				lowerCamelCase__				(       self  :	Optional[int]							,				snake_case  :	Optional[Any]    )		->							None:
          __UpperCAmelCase			:				int													=    Node(snake_case    )  # create a new Node
          if self.empty():  # if Tree is empty
               __UpperCAmelCase			:				List[Any]													=    new_node  # set its root
          else:  # Tree is not empty
               __UpperCAmelCase			:				Tuple													=    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:
                              __UpperCAmelCase			:				Optional[int]													=    new_node  # We insert the new node in a leaf
                              break
                         else:
                              __UpperCAmelCase			:				List[Any]													=    parent_node.left
                    else:
                         if parent_node.right is None:
                              __UpperCAmelCase			:				Optional[int]													=    new_node
                              break
                         else:
                              __UpperCAmelCase			:				List[str]													=    parent_node.right
               __UpperCAmelCase			:				int													=    parent_node

     def 				lowerCamelCase__				(       self  :	Optional[int]							,				*snake_case  :	List[Any]    )		->							None:
          for value in values:
               self.__insert(snake_case    )

     def 				lowerCamelCase__				(       self  :	Optional[int]							,				snake_case  :	Dict    )		->							Node | None:
          if self.empty():
               raise IndexError('''Warning: Tree is empty! please use another.'''    )
          else:
               __UpperCAmelCase			:				List[Any]													=    self.root
               # use lazy evaluation here to avoid NoneType Attribute error
               while node is not None and node.value is not value:
                    __UpperCAmelCase			:				Union[str, Any]													=    node.left if value < node.value else node.right
               return node

     def 				lowerCamelCase__				(       self  :	str							,				snake_case  :	Node | None = None    )		->							Node | None:
          if node is None:
               if self.root is None:
                    return None
               __UpperCAmelCase			:				Optional[Any]													=    self.root

          if not self.empty():
               while node.right is not None:
                    __UpperCAmelCase			:				str													=    node.right
          return node

     def 				lowerCamelCase__				(       self  :	int							,				snake_case  :	Node | None = None    )		->							Node | None:
          if node is None:
               __UpperCAmelCase			:				str													=    self.root
          if self.root is None:
               return None
          if not self.empty():
               __UpperCAmelCase			:				List[str]													=    self.root
               while node.left is not None:
                    __UpperCAmelCase			:				str													=    node.left
          return node

     def 				lowerCamelCase__				(       self  :	Union[str, Any]							,				snake_case  :	int    )		->							None:
          __UpperCAmelCase			:				List[str]													=    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:
                    __UpperCAmelCase			:				Optional[int]													=    self.get_max(
                        node.left    )  # Gets the max value of the left branch
                    self.remove(tmp_node.value    )  # type: ignore
                    __UpperCAmelCase			:				List[str]													=    (
                        tmp_node.value  # type: ignore
                    )  # Assigns the value to the node to delete and keep tree structure

     def 				lowerCamelCase__				(       self  :	List[str]							,				snake_case  :	Node | None    )		->							Iterable:
          if node is not None:
               yield node  # Preorder Traversal
               yield from self.preorder_traverse(node.left    )
               yield from self.preorder_traverse(node.right    )

     def 				lowerCamelCase__				(       self  :	Union[str, Any]							,				snake_case  :	int=None    )		->							Any:
          if traversal_function is None:
               return self.preorder_traverse(self.root    )
          else:
               return traversal_function(self.root    )

     def 				lowerCamelCase__				(       self  :	str							,				snake_case  :	list							,				snake_case  :	Node | None    )		->							None:
          if node:
               self.inorder(snake_case							,				node.left    )
               arr.append(node.value    )
               self.inorder(snake_case							,				node.right    )






     def 				lowerCamelCase__				(       self  :	Optional[int]							,				snake_case  :	int							,				snake_case  :	Node    )		->							int:
          __UpperCAmelCase			:				list[int]													=    []
          self.inorder(snake_case							,				snake_case    )  # append all values to list using inorder traversal
          return arr[k - 1]




def 			_a			(		_lowercase      :			Node | None						):





     '''simple docstring'''






     __UpperCAmelCase			:				List[str]													=    []
     if curr_node is not None:
          __UpperCAmelCase			:				Union[str, Any]													=    postorder(curr_node.left						) + postorder(curr_node.right						) + [curr_node]
     return node_list




def 			_a			(		):





     '''simple docstring'''






     __UpperCAmelCase			:				Optional[Any]													=    (8, 3, 6, 1, 10, 14, 13, 4, 7)
     __UpperCAmelCase			:				Union[str, Any]													=    BinarySearchTree()
     for i in testlist:
          t.insert(_lowercase						)

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

     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(_lowercase						)
          print(_lowercase						)


if __name__ == "__main__":
      import doctest

      doctest.testmod(verbose=True)