


import argparse

import gdown
import numpy as np
import torch
from huggingface_hub import hf_hub_download

from transformers import (
    CLIPTokenizer,
    CLIPTokenizerFast,
    VideoMAEImageProcessor,
    XCLIPConfig,
    XCLIPModel,
    XCLIPProcessor,
    XCLIPTextConfig,
    XCLIPVisionConfig,
)




def       a_ (       SCREAMING_SNAKE_CASE__   : int						,     SCREAMING_SNAKE_CASE__   : Optional[Any]	):
       '''simple docstring'''





       _lowerCamelCase			:						Any            =XCLIPTextConfig()

       # derive patch size from model name
       _lowerCamelCase			:						Union[str, Any]            =model_name.find('patch'	)
       _lowerCamelCase			:						str            =int(model_name[start_idx + len('patch'	) : start_idx + len('patch'	) + 2]	)
       _lowerCamelCase			:						Optional[int]            =XCLIPVisionConfig(patch_size=SCREAMING_SNAKE_CASE__						,     num_frames=SCREAMING_SNAKE_CASE__	)

       if "large" in model_name:
              _lowerCamelCase			:						str            =768
              _lowerCamelCase			:						Tuple            =3_072
              _lowerCamelCase			:						List[Any]            =12

              _lowerCamelCase			:						int            =1_024
              _lowerCamelCase			:						Any            =4_096
              _lowerCamelCase			:						int            =16
              _lowerCamelCase			:						Any            =24
              _lowerCamelCase			:						Union[str, Any]            =768
              _lowerCamelCase			:						Tuple            =3_072

       if model_name == "xclip-large-patch14-16-frames":
              _lowerCamelCase			:						int            =336

       _lowerCamelCase			:						int            =XCLIPConfig.from_text_vision_configs(SCREAMING_SNAKE_CASE__						,     SCREAMING_SNAKE_CASE__	)

       if "large" in model_name:
              _lowerCamelCase			:						Optional[int]            =768

       return config




def       a_ (       SCREAMING_SNAKE_CASE__   : Union[str, Any]	):
       '''simple docstring'''





       if name == "token_embedding.weight":
              _lowerCamelCase			:						Optional[Any]            =name.replace('token_embedding.weight'						,     'text_model.embeddings.token_embedding.weight'	)
       if name == "positional_embedding":
              _lowerCamelCase			:						int            =name.replace('positional_embedding'						,     'text_model.embeddings.position_embedding.weight'	)
       if "ln_1" in name:
              _lowerCamelCase			:						int            =name.replace('ln_1'						,     'layer_norm1'	)
       if "ln_2" in name:
              _lowerCamelCase			:						Tuple            =name.replace('ln_2'						,     'layer_norm2'	)
       if "c_fc" in name:
              _lowerCamelCase			:						str            =name.replace('c_fc'						,     'fc1'	)
       if "c_proj" in name:
              _lowerCamelCase			:						List[str]            =name.replace('c_proj'						,     'fc2'	)
       if name.startswith('transformer.resblocks'	):
              _lowerCamelCase			:						Union[str, Any]            =name.replace('transformer.resblocks'						,     'text_model.encoder.layers'	)
       if "attn.out_proj" in name and "message" not in name:
              _lowerCamelCase			:						Optional[int]            =name.replace('attn.out_proj'						,     'self_attn.out_proj'	)
       if "ln_final" in name:
              _lowerCamelCase			:						Tuple            =name.replace('ln_final'						,     'text_model.final_layer_norm'	)
       # visual encoder
       if name == "visual.class_embedding":
              _lowerCamelCase			:						List[Any]            =name.replace('visual.class_embedding'						,     'vision_model.embeddings.class_embedding'	)
       if name == "visual.positional_embedding":
              _lowerCamelCase			:						Dict            =name.replace('visual.positional_embedding'						,     'vision_model.embeddings.position_embedding.weight'	)
       if name.startswith('visual.transformer.resblocks'	):
              _lowerCamelCase			:						List[str]            =name.replace('visual.transformer.resblocks'						,     'vision_model.encoder.layers'	)
       if "visual.conv1" in name:
              _lowerCamelCase			:						Union[str, Any]            =name.replace('visual.conv1'						,     'vision_model.embeddings.patch_embedding'	)
       if "visual.ln_pre" in name:
              _lowerCamelCase			:						Any            =name.replace('visual.ln_pre'						,     'vision_model.pre_layernorm'	)
       if "visual.ln_post" in name:
              _lowerCamelCase			:						Optional[int]            =name.replace('visual.ln_post'						,     'vision_model.post_layernorm'	)
       if "visual.proj" in name:
              _lowerCamelCase			:						Tuple            =name.replace('visual.proj'						,     'visual_projection.weight'	)
       if "text_projection" in name:
              _lowerCamelCase			:						List[str]            =name.replace('text_projection'						,     'text_projection.weight'	)
       # things on top
       if "prompts_visual_proj" in name:
              _lowerCamelCase			:						List[Any]            =name.replace('prompts_visual_proj'						,     'prompts_visual_projection'	)
       if "prompts_visual_ln" in name:
              _lowerCamelCase			:						List[str]            =name.replace('prompts_visual_ln'						,     'prompts_visual_layernorm'	)
       # mit
       if name == "mit.positional_embedding":
              _lowerCamelCase			:						int            =name.replace('positional'						,     'position'	)
       if name.startswith('mit.resblocks'	):
              _lowerCamelCase			:						List[Any]            =name.replace('mit.resblocks'						,     'mit.encoder.layers'	)
       # prompts generator
       if name.startswith('prompts_generator.norm'	):
              _lowerCamelCase			:						Tuple            =name.replace('prompts_generator.norm'						,     'prompts_generator.layernorm'	)

       return name




def       a_ (       SCREAMING_SNAKE_CASE__   : Union[str, Any]						,     SCREAMING_SNAKE_CASE__   : int	):
       '''simple docstring'''





       for key in orig_state_dict.copy().keys():
              _lowerCamelCase			:						Dict            =orig_state_dict.pop(SCREAMING_SNAKE_CASE__	)

              if "attn.in_proj" in key:
                     _lowerCamelCase			:						Tuple            =key.split('.'	)
                     if key.startswith('visual'	):
                            _lowerCamelCase			:						List[Any]            =key_split[3]
                            _lowerCamelCase			:						Any            =config.vision_config.hidden_size
                            if "message_attn" in key:
                                   if "weight" in key:
                                          _lowerCamelCase			:						str            =val[
                                              :dim, :
                                          ]
                                          _lowerCamelCase			:						List[Any]            =val[
                                              dim : dim * 2, :
                                          ]
                                          _lowerCamelCase			:						Union[str, Any]            =val[
                                              -dim:, :
                                          ]
                                   else:
                                          _lowerCamelCase			:						str            =val[
                                              :dim
                                          ]
                                          _lowerCamelCase			:						Union[str, Any]            =val[
                                              dim : dim * 2
                                          ]
                                          _lowerCamelCase			:						Any            =val[
                                              -dim:
                                          ]
                            else:
                                   if "weight" in key:
                                          _lowerCamelCase			:						Dict            =val[
                                              :dim, :
                                          ]
                                          _lowerCamelCase			:						str            =val[
                                              dim : dim * 2, :
                                          ]
                                          _lowerCamelCase			:						int            =val[
                                              -dim:, :
                                          ]
                                   else:
                                          _lowerCamelCase			:						List[str]            =val[:dim]
                                          _lowerCamelCase			:						Tuple            =val[
                                              dim : dim * 2
                                          ]
                                          _lowerCamelCase			:						Any            =val[-dim:]
                     elif key.startswith('mit'	):
                            _lowerCamelCase			:						Optional[Any]            =key_split[2]
                            _lowerCamelCase			:						Optional[int]            =config.vision_config.mit_hidden_size
                            if "weight" in key:
                                   _lowerCamelCase			:						Any            =val[:dim, :]
                                   _lowerCamelCase			:						List[str]            =val[dim : dim * 2, :]
                                   _lowerCamelCase			:						Tuple            =val[-dim:, :]
                            else:
                                   _lowerCamelCase			:						Any            =val[:dim]
                                   _lowerCamelCase			:						Optional[Any]            =val[dim : dim * 2]
                                   _lowerCamelCase			:						Optional[int]            =val[-dim:]
                     else:
                            _lowerCamelCase			:						int            =key_split[2]
                            _lowerCamelCase			:						List[Any]            =config.text_config.hidden_size
                            if "weight" in key:
                                   _lowerCamelCase			:						Any            =val[:dim, :]
                                   _lowerCamelCase			:						List[Any]            =val[
                                       dim : dim * 2, :
                                   ]
                                   _lowerCamelCase			:						Union[str, Any]            =val[-dim:, :]
                            else:
                                   _lowerCamelCase			:						Optional[Any]            =val[:dim]
                                   _lowerCamelCase			:						Dict            =val[
                                       dim : dim * 2
                                   ]
                                   _lowerCamelCase			:						Union[str, Any]            =val[-dim:]
              else:
                     _lowerCamelCase			:						Optional[int]            =rename_key(SCREAMING_SNAKE_CASE__	)
                     if new_key_name in ["visual_projection.weight", "text_projection.weight"]:
                            _lowerCamelCase			:						Any            =val.T
                     _lowerCamelCase			:						str            =val

       return orig_state_dict




def       a_ (       SCREAMING_SNAKE_CASE__   : Optional[int]	):
       '''simple docstring'''





       if num_frames == 8:
              _lowerCamelCase			:						Tuple            ='eating_spaghetti_8_frames.npy'
       elif num_frames == 16:
              _lowerCamelCase			:						Tuple            ='eating_spaghetti.npy'
       elif num_frames == 32:
              _lowerCamelCase			:						Optional[int]            ='eating_spaghetti_32_frames.npy'
       _lowerCamelCase			:						Dict            =hf_hub_download(
           repo_id='hf-internal-testing/spaghetti-video'						,     filename=SCREAMING_SNAKE_CASE__						,     repo_type='dataset'						,     )
       _lowerCamelCase			:						str            =np.load(SCREAMING_SNAKE_CASE__	)
       return list(SCREAMING_SNAKE_CASE__	)




def       a_ (       SCREAMING_SNAKE_CASE__   : List[str]						,     SCREAMING_SNAKE_CASE__   : Tuple=None						,     SCREAMING_SNAKE_CASE__   : str=False	):
       '''simple docstring'''





       _lowerCamelCase			:						List[Any]            ={
           # fully supervised kinetics-400 checkpoints
           'xclip-base-patch32': 'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/k400_32_8.pth',
           'xclip-base-patch32-16-frames': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/k400_32_16.pth'
           ),
           'xclip-base-patch16': 'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/k400_16_8.pth',
           'xclip-base-patch16-16-frames': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/k400_16_16.pth'
           ),
           'xclip-large-patch14': 'https://drive.google.com/u/0/uc?id=1NUOImq0o5DlQTST17iIP3vG7DgmHQuCx&amp;export=download&amp;confirm=t&amp;uuid=b26caedc-88e2-473e-830a-9d158b653cdb',
           'xclip-large-patch14-16-frames': 'https://drive.google.com/u/0/uc?id=1FOYgnJc097OJ4lGwtRCCydQyVPJEOH7d&amp;export=download&amp;confirm=t&amp;uuid=538fa810-e671-4050-b385-9a623f89804f',
           # fully supervised kinetics-600 checkpoints
           'xclip-base-patch16-kinetics-600': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/k600_16_8.pth'
           ),
           'xclip-base-patch16-kinetics-600-16-frames': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/k600_16_16.pth'
           ),
           'xclip-large-patch14-kinetics-600': 'https://drive.google.com/u/0/uc?id=1FV8C1INuM91sLAN4ImjzePLIlpMSihwV&amp;export=download&amp;confirm=t&amp;uuid=141d4977-4a65-44ae-864f-4b0c19f838be',
           # few shot
           'xclip-base-patch16-hmdb-2-shot': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/few_hmdb_2.pth'
           ),
           'xclip-base-patch16-hmdb-4-shot': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/few_hmdb_4.pth'
           ),
           'xclip-base-patch16-hmdb-8-shot': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/few_hmdb_8.pth'
           ),
           'xclip-base-patch16-hmdb-16-shot': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/few_hmdb_16.pth'
           ),
           'xclip-base-patch16-ucf-2-shot': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/few_ucf_2.pth'
           ),
           'xclip-base-patch16-ucf-4-shot': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/few_ucf_4.pth'
           ),
           'xclip-base-patch16-ucf-8-shot': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/few_ucf_8.pth'
           ),
           'xclip-base-patch16-ucf-16-shot': (
               'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/few_ucf_16.pth'
           ),
           # zero shot
           'xclip-base-patch16-zero-shot': 'https://github.com/nbl97/X-CLIP_Model_Zoo/releases/download/v1.0/zero.pth',
       }

       _lowerCamelCase			:						Dict            =model_to_url[model_name]
       _lowerCamelCase			:						Optional[int]            =8
       if "16-frames" in model_name:
              _lowerCamelCase			:						List[Any]            =16
       elif "shot" in model_name:
              _lowerCamelCase			:						Optional[Any]            =32

       _lowerCamelCase			:						Any            =get_xclip_config(SCREAMING_SNAKE_CASE__						,     SCREAMING_SNAKE_CASE__	)
       _lowerCamelCase			:						Optional[int]            =XCLIPModel(SCREAMING_SNAKE_CASE__	)
       model.eval()

       if "drive" in checkpoint_url:
              _lowerCamelCase			:						Any            ='pytorch_model.bin'
              gdown.cached_download(SCREAMING_SNAKE_CASE__						,     SCREAMING_SNAKE_CASE__						,     quiet=SCREAMING_SNAKE_CASE__	)
              _lowerCamelCase			:						Any            =torch.load(SCREAMING_SNAKE_CASE__						,     map_location='cpu'	)['model']
       else:
              _lowerCamelCase			:						Any            =torch.hub.load_state_dict_from_url(SCREAMING_SNAKE_CASE__	)['model']

       _lowerCamelCase			:						str            =convert_state_dict(SCREAMING_SNAKE_CASE__						,     SCREAMING_SNAKE_CASE__	)

       _lowerCamelCase			:						int            =XCLIPModel(SCREAMING_SNAKE_CASE__	)
       _lowerCamelCase      ,	_lowerCamelCase			:						Union[str, Any]            =model.load_state_dict(SCREAMING_SNAKE_CASE__						,     strict=SCREAMING_SNAKE_CASE__	)
       assert missing_keys == ["text_model.embeddings.position_ids", "vision_model.embeddings.position_ids"]
       model.eval()

       _lowerCamelCase			:						Any            =336 if model_name == 'xclip-large-patch14-16-frames' else 224
       _lowerCamelCase			:						Any            =VideoMAEImageProcessor(size=SCREAMING_SNAKE_CASE__	)
       _lowerCamelCase			:						Optional[int]            =CLIPTokenizer.from_pretrained('openai/clip-vit-base-patch32'	)
       _lowerCamelCase			:						List[Any]            =CLIPTokenizerFast.from_pretrained('openai/clip-vit-base-patch32'	)
       _lowerCamelCase			:						int            =XCLIPProcessor(image_processor=SCREAMING_SNAKE_CASE__						,     tokenizer=SCREAMING_SNAKE_CASE__	)

       _lowerCamelCase			:						Dict            =prepare_video(SCREAMING_SNAKE_CASE__	)
       _lowerCamelCase			:						Dict            =processor(
           text=['playing sports', 'eating spaghetti', 'go shopping']						,     videos=SCREAMING_SNAKE_CASE__						,     return_tensors='pt'						,     padding=SCREAMING_SNAKE_CASE__	)

       print('Shape of pixel values:'						,     inputs.pixel_values.shape	)

       with torch.no_grad():
              _lowerCamelCase			:						Union[str, Any]            =model(**SCREAMING_SNAKE_CASE__	)

       # Verify outputs
       _lowerCamelCase			:						Any            =outputs.logits_per_video
       _lowerCamelCase			:						Optional[Any]            =logits_per_video.softmax(dim=1	)
       print('Probs:'						,     SCREAMING_SNAKE_CASE__	)
       # kinetics-400
       if model_name == "xclip-base-patch32":
              _lowerCamelCase			:						Any            =torch.tensor([[0.00_19, 0.99_51, 0.00_30]]	)
       elif model_name == "xclip-base-patch32-16-frames":
              _lowerCamelCase			:						int            =torch.tensor([[7.0999e-04, 9.9883e-01, 4.5580e-04]]	)
       elif model_name == "xclip-base-patch16":
              _lowerCamelCase			:						int            =torch.tensor([[0.00_83, 0.96_81, 0.02_36]]	)
       elif model_name == "xclip-base-patch16-16-frames":
              _lowerCamelCase			:						int            =torch.tensor([[7.6937e-04, 9.9728e-01, 1.9473e-03]]	)
       elif model_name == "xclip-large-patch14":
              _lowerCamelCase			:						Union[str, Any]            =torch.tensor([[0.00_62, 0.98_64, 0.00_75]]	)
       elif model_name == "xclip-large-patch14-16-frames":
              _lowerCamelCase			:						int            =torch.tensor([[3.3877e-04, 9.9937e-01, 2.8888e-04]]	)
       # kinetics-600
       elif model_name == "xclip-base-patch16-kinetics-600":
              _lowerCamelCase			:						Union[str, Any]            =torch.tensor([[0.05_55, 0.89_14, 0.05_31]]	)
       elif model_name == "xclip-base-patch16-kinetics-600-16-frames":
              _lowerCamelCase			:						Optional[int]            =torch.tensor([[3.8554e-04, 9.9929e-01, 3.2754e-04]]	)
       elif model_name == "xclip-large-patch14-kinetics-600":
              _lowerCamelCase			:						Dict            =torch.tensor([[0.00_36, 0.99_20, 0.00_45]]	)
       # few shot
       elif model_name == "xclip-base-patch16-hmdb-2-shot":
              _lowerCamelCase			:						str            =torch.tensor([[7.1890e-06, 9.9994e-01, 5.6559e-05]]	)
       elif model_name == "xclip-base-patch16-hmdb-4-shot":
              _lowerCamelCase			:						Any            =torch.tensor([[1.0320e-05, 9.9993e-01, 6.2435e-05]]	)
       elif model_name == "xclip-base-patch16-hmdb-8-shot":
              _lowerCamelCase			:						List[Any]            =torch.tensor([[4.1377e-06, 9.9990e-01, 9.8386e-05]]	)
       elif model_name == "xclip-base-patch16-hmdb-16-shot":
              _lowerCamelCase			:						List[Any]            =torch.tensor([[4.1347e-05, 9.9962e-01, 3.3411e-04]]	)
       elif model_name == "xclip-base-patch16-ucf-2-shot":
              _lowerCamelCase			:						List[str]            =torch.tensor([[8.5857e-05, 9.9928e-01, 6.3291e-04]]	)
       elif model_name == "xclip-base-patch16-ucf-4-shot":
              _lowerCamelCase			:						Any            =torch.tensor([[8.5857e-05, 9.9928e-01, 6.3291e-04]]	)
       elif model_name == "xclip-base-patch16-ucf-8-shot":
              _lowerCamelCase			:						int            =torch.tensor([[0.00_27, 0.99_04, 0.00_70]]	)
       elif model_name == "xclip-base-patch16-ucf-16-shot":
              _lowerCamelCase			:						Optional[Any]            =torch.tensor([[9.8219e-04, 9.9593e-01, 3.0863e-03]]	)
       # zero shot
       elif model_name == "xclip-base-patch16-zero-shot":
              _lowerCamelCase			:						Optional[int]            =torch.tensor([[3.5082e-04, 9.9785e-01, 1.7966e-03]]	)
       else:
              raise ValueError(F'''Model name {model_name} not supported'''	)
       assert torch.allclose(SCREAMING_SNAKE_CASE__						,     SCREAMING_SNAKE_CASE__						,     atol=1e-3	)
       print('Looks ok!'	)

       if pytorch_dump_folder_path is not None:
              print(F'''Saving model {model_name} to {pytorch_dump_folder_path}'''	)
              model.save_pretrained(SCREAMING_SNAKE_CASE__	)

       if push_to_hub:
              print('Pushing model, processor and slow tokenizer files to the hub...'	)
              model.push_to_hub(SCREAMING_SNAKE_CASE__						,     organization='nielsr'	)
              processor.push_to_hub(SCREAMING_SNAKE_CASE__						,     organization='nielsr'	)
              slow_tokenizer.push_to_hub(SCREAMING_SNAKE_CASE__						,     organization='nielsr'	)


if __name__ == "__main__":
 lowerCamelCase		   =			argparse.ArgumentParser()
 # Required parameters
 parser.add_argument(
     '--model_name',
     default='xclip-base-patch32',
     type=str,
     help='Name of the model.',
 )
 parser.add_argument(
     '--pytorch_dump_folder_path', default=None, type=str, help='Path to the output PyTorch model directory.'
 )
 parser.add_argument(
     '--push_to_hub', action='store_true', help='Whether or not to push the converted model to the 🤗 hub.'
 )

 lowerCamelCase		   =			parser.parse_args()
 convert_xclip_checkpoint(args.model_name, args.pytorch_dump_folder_path, args.push_to_hub)






from collections.abc import Iterable
from typing import Any




class A    :






      def __init__(   self		:	Dict     ,  lowercase_		:	int | None = None					)   ->		int:
             """simple docstring"""




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






      def __repr__(   self		:	Dict					)   ->		str:
             """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 A    :






      def __init__(   self		:	Union[str, Any]     ,  lowercase_		:	Node | None = None					)   ->		int:
             """simple docstring"""




             _lowerCamelCase			:						Optional[int]            =root






      def __str__(   self		:	Tuple					)   ->		str:
             """simple docstring"""




             return str(self.root					)






      def 			lowerCamelCase			(   self		:	Optional[Any]     ,  lowercase_		:	Node     ,  lowercase_		:	Node | None					)   ->		None:
             """simple docstring"""




             if new_children is not None:  # reset its kids
                    _lowerCamelCase			:						Optional[int]            =node.parent
             if node.parent is not None:  # reset its parent
                    if self.is_right(lowercase_					):  # If it is the right children
                           _lowerCamelCase			:						int            =new_children
                    else:
                           _lowerCamelCase			:						Dict            =new_children
             else:
                    _lowerCamelCase			:						Tuple            =new_children






      def 			lowerCamelCase			(   self		:	Optional[Any]     ,  lowercase_		:	Node					)   ->		bool:
             """simple docstring"""




             if node.parent and node.parent.right:
                    return node == node.parent.right
             return False






      def 			lowerCamelCase			(   self		:	int					)   ->		bool:
             """simple docstring"""




             return self.root is None






      def 			lowerCamelCase			(   self		:	List[Any]     ,  lowercase_		:	Union[str, Any]					)   ->		None:
             """simple docstring"""




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






      def 			lowerCamelCase			(   self		:	Any     ,  *lowercase_		:	Union[str, Any]					)   ->		None:
             """simple docstring"""




             for value in values:
                    self.__insert(lowercase_					)






      def 			lowerCamelCase			(   self		:	Optional[int]     ,  lowercase_		:	List[Any]					)   ->		Node | None:
             """simple docstring"""




             if self.empty():
                    raise IndexError('Warning: Tree is empty! please use another.'					)
             else:
                    _lowerCamelCase			:						int            =self.root
                    # use lazy evaluation here to avoid NoneType Attribute error
                    while node is not None and node.value is not value:
                           _lowerCamelCase			:						Dict            =node.left if value < node.value else node.right
                    return node






      def 			lowerCamelCase			(   self		:	Tuple     ,  lowercase_		:	Node | None = None					)   ->		Node | None:
             """simple docstring"""




             if node is None:
                    if self.root is None:
                           return None
                    _lowerCamelCase			:						Union[str, Any]            =self.root

             if not self.empty():
                    while node.right is not None:
                           _lowerCamelCase			:						Optional[int]            =node.right
             return node






      def 			lowerCamelCase			(   self		:	Optional[Any]     ,  lowercase_		:	Node | None = None					)   ->		Node | None:
             """simple docstring"""




             if node is None:
                    _lowerCamelCase			:						Union[str, Any]            =self.root
             if self.root is None:
                    return None
             if not self.empty():
                    _lowerCamelCase			:						Optional[int]            =self.root
                    while node.left is not None:
                           _lowerCamelCase			:						List[Any]            =node.left
             return node






      def 			lowerCamelCase			(   self		:	Tuple     ,  lowercase_		:	int					)   ->		None:
             """simple docstring"""




             _lowerCamelCase			:						List[str]            =self.search(lowercase_					)  # 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(lowercase_     ,  lowercase_					)
                    elif node.left is None:  # Has only right children
                           self.__reassign_nodes(lowercase_     ,  node.right					)
                    elif node.right is None:  # Has only left children
                           self.__reassign_nodes(lowercase_     ,  node.left					)
                    else:
                           _lowerCamelCase			:						List[str]            =self.get_max(
                               node.left					)  # Gets the max value of the left branch
                           self.remove(tmp_node.value					)  # type: ignore
                           _lowerCamelCase			:						Union[str, Any]            =(
                               tmp_node.value  # type: ignore
                           )  # Assigns the value to the node to delete and keep tree structure






      def 			lowerCamelCase			(   self		:	str     ,  lowercase_		:	Node | None					)   ->		Iterable:
             """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 			lowerCamelCase			(   self		:	str     ,  lowercase_		:	Dict=None					)   ->		Any:
             """simple docstring"""




             if traversal_function is None:
                    return self.preorder_traverse(self.root					)
             else:
                    return traversal_function(self.root					)






      def 			lowerCamelCase			(   self		:	Union[str, Any]     ,  lowercase_		:	list     ,  lowercase_		:	Node | None					)   ->		None:
             """simple docstring"""




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






      def 			lowerCamelCase			(   self		:	Union[str, Any]     ,  lowercase_		:	int     ,  lowercase_		:	Node					)   ->		int:
             """simple docstring"""




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




def       a_ (       SCREAMING_SNAKE_CASE__   : Node | None	):
       '''simple docstring'''





       _lowerCamelCase			:						int            =[]
       if curr_node is not None:
              _lowerCamelCase			:						List[Any]            =postorder(curr_node.left	) + postorder(curr_node.right	) + [curr_node]
       return node_list




def       a_ (       ):
       '''simple docstring'''





       _lowerCamelCase			:						Optional[int]            =(8, 3, 6, 1, 10, 14, 13, 4, 7)
       _lowerCamelCase			:						int            =BinarySearchTree()
       for i in testlist:
              t.insert(SCREAMING_SNAKE_CASE__	)

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

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


if __name__ == "__main__":
 import doctest

 doctest.testmod(verbose=True)


