


'''simple docstring'''







import inspect
from typing import List, Optional, Union

import torch
from torch import nn
from torch.nn import functional as F
from torchvision import transforms
from transformers import CLIPImageProcessor, CLIPModel, CLIPTextModel, CLIPTokenizer

from diffusers import (
    AutoencoderKL,
    DDIMScheduler,
    DiffusionPipeline,
    DPMSolverMultistepScheduler,
    LMSDiscreteScheduler,
    PNDMScheduler,
    UNetaDConditionModel,
)
from diffusers.pipelines.stable_diffusion.pipeline_stable_diffusion import StableDiffusionPipelineOutput
class    lowercase_	(       nn.Module  ):


    def __init__(	self    ,   a    ,   a=1.0       ):
          super().__init__()

          UpperCamelCase__      =							cut_size
          UpperCamelCase__      =							cut_power


    def   __a				(	self    ,   a    ,   a       ):
          UpperCamelCase__      =							pixel_values.shape[2:4]
          UpperCamelCase__      =							min(_a    ,   _a       )
          UpperCamelCase__      =							min(_a    ,   _a    ,   self.cut_size       )
          UpperCamelCase__      =							[]
          for _ in range(_a       ):
                UpperCamelCase__      =							int(torch.rand([]       ) ** self.cut_power * (max_size - min_size) + min_size       )
                UpperCamelCase__      =							torch.randint(0    ,   sideX - size + 1    ,   ()       )
                UpperCamelCase__      =							torch.randint(0    ,   sideY - size + 1    ,   ()       )
                UpperCamelCase__      =							pixel_values[:, :, offsety : offsety + size, offsetx : offsetx + size]
                cutouts.append(F.adaptive_avg_poolad(_a    ,   self.cut_size       )       )
          return torch.cat(_a       )







def _UpperCamelCase			(	__A ,     __A       )				->						Optional[Any]:


      '''simple docstring'''



      UpperCamelCase__      =							F.normalize(SCREAMING_SNAKE_CASE_ ,     dim=-1       )
      UpperCamelCase__      =							F.normalize(SCREAMING_SNAKE_CASE_ ,     dim=-1       )
      return (x - y).norm(dim=-1       ).div(2       ).arcsin().pow(2       ).mul(2       )







def _UpperCamelCase			(	__A ,     __A       )				->						Union[str, Any]:


      '''simple docstring'''



      for param in model.parameters():
            UpperCamelCase__      =							value



class    lowercase_	(       _snake_case  ):


    def __init__(	self    ,   a    ,   a    ,   a    ,   a    ,   a    ,   a    ,   a    ,   ):
          super().__init__()
          self.register_modules(
              vae=_a    ,   text_encoder=_a    ,   clip_model=_a    ,   tokenizer=_a    ,   unet=_a    ,   scheduler=_a    ,   feature_extractor=_a    ,   )

          UpperCamelCase__      =							transforms.Normalize(mean=feature_extractor.image_mean    ,   std=feature_extractor.image_std       )
          UpperCamelCase__      =							(
              feature_extractor.size
              if isinstance(feature_extractor.size    ,   _a       )
              else feature_extractor.size['shortest_edge']
          )
          UpperCamelCase__      =							MakeCutouts(self.cut_out_size       )

          set_requires_grad(self.text_encoder    ,   _a       )
          set_requires_grad(self.clip_model    ,   _a       )


    def   __a				(	self    ,   a = "auto"       ):
          if slice_size == "auto":
                # half the attention head size is usually a good trade-off between
                # speed and memory
                UpperCamelCase__      =							self.unet.config.attention_head_dim // 2
          self.unet.set_attention_slice(_a       )


    def   __a				(	self       ):
          self.enable_attention_slicing(_a       )


    def   __a				(	self       ):
          set_requires_grad(self.vae    ,   _a       )


    def   __a				(	self       ):
          set_requires_grad(self.vae    ,   _a       )


    def   __a				(	self       ):
          set_requires_grad(self.unet    ,   _a       )


    def   __a				(	self       ):
          set_requires_grad(self.unet    ,   _a       )


    @torch.enable_grad()
    def   __a				(	self    ,   a    ,   a    ,   a    ,   a    ,   a    ,   a    ,   a    ,   a    ,   a=True    ,   ):
          UpperCamelCase__      =							latents.detach().requires_grad_()

          UpperCamelCase__      =							self.scheduler.scale_model_input(_a    ,   _a       )

          # predict the noise residual
          UpperCamelCase__      =							self.unet(_a    ,   _a    ,   encoder_hidden_states=_a       ).sample

          if isinstance(self.scheduler    ,   (PNDMScheduler, DDIMScheduler, DPMSolverMultistepScheduler)       ):
                UpperCamelCase__      =							self.scheduler.alphas_cumprod[timestep]
                UpperCamelCase__      =							1 - alpha_prod_t
                # compute predicted original sample from predicted noise also called
                # "predicted x_0" of formula (12) from https://arxiv.org/pdf/2010.02502.pdf
                UpperCamelCase__      =							(latents - beta_prod_t ** 0.5 * noise_pred) / alpha_prod_t ** 0.5

                UpperCamelCase__      =							torch.sqrt(_a       )
                UpperCamelCase__      =							pred_original_sample * (fac) + latents * (1 - fac)
          elif isinstance(self.scheduler    ,   _a       ):
                UpperCamelCase__      =							self.scheduler.sigmas[index]
                UpperCamelCase__      =							latents - sigma * noise_pred
          else:
                raise ValueError(f'''scheduler type {type(self.scheduler       )} not supported'''       )

          UpperCamelCase__      =							1 / self.vae.config.scaling_factor * sample
          UpperCamelCase__      =							self.vae.decode(_a       ).sample
          UpperCamelCase__      =							(image / 2 + 0.5).clamp(0    ,   1       )

          if use_cutouts:
                UpperCamelCase__      =							self.make_cutouts(_a    ,   _a       )
          else:
                UpperCamelCase__      =							transforms.Resize(self.cut_out_size       )(_a       )
          UpperCamelCase__      =							self.normalize(_a       ).to(latents.dtype       )

          UpperCamelCase__      =							self.clip_model.get_image_features(_a       )
          UpperCamelCase__      =							image_embeddings_clip / image_embeddings_clip.norm(p=2    ,   dim=-1    ,   keepdim=_a       )

          if use_cutouts:
                UpperCamelCase__      =							spherical_dist_loss(_a    ,   _a       )
                UpperCamelCase__      =							dists.view([num_cutouts, sample.shape[0], -1]       )
                UpperCamelCase__      =							dists.sum(2       ).mean(0       ).sum() * clip_guidance_scale
          else:
                UpperCamelCase__      =							spherical_dist_loss(_a    ,   _a       ).mean() * clip_guidance_scale

          UpperCamelCase__      =							-torch.autograd.grad(_a    ,   _a       )[0]

          if isinstance(self.scheduler    ,   _a       ):
                UpperCamelCase__      =							latents.detach() + grads * (sigma**2)
                UpperCamelCase__      =							noise_pred_original
          else:
                UpperCamelCase__      =							noise_pred_original - torch.sqrt(_a       ) * grads
          return noise_pred, latents


    @torch.no_grad()
    def __call__(	self    ,   a    ,   a = 5_12    ,   a = 5_12    ,   a = 50    ,   a = 7.5    ,   a = 1    ,   a = 0.0    ,   a = 1_00    ,   a = None    ,   a = 4    ,   a = True    ,   a = None    ,   a = None    ,   a = "pil"    ,   a = True    ,   ):
          if isinstance(_a    ,   _a       ):
                UpperCamelCase__      =							1
          elif isinstance(_a    ,   _a       ):
                UpperCamelCase__      =							len(_a       )
          else:
                raise ValueError(f'''`prompt` has to be of type `str` or `list` but is {type(_a       )}'''       )

          if height % 8 != 0 or width % 8 != 0:
                raise ValueError(f'''`height` and `width` have to be divisible by 8 but are {height} and {width}.'''       )

          # get prompt text embeddings
          UpperCamelCase__      =							self.tokenizer(
              _a    ,   padding="max_length"    ,   max_length=self.tokenizer.model_max_length    ,   truncation=_a    ,   return_tensors="pt"    ,   )
          UpperCamelCase__      =							self.text_encoder(text_input.input_ids.to(self.device       )       )[0]
          # duplicate text embeddings for each generation per prompt
          UpperCamelCase__      =							text_embeddings.repeat_interleave(_a    ,   dim=0       )

          if clip_guidance_scale > 0:
                if clip_prompt is not None:
                      UpperCamelCase__      =							self.tokenizer(
                          _a    ,   padding="max_length"    ,   max_length=self.tokenizer.model_max_length    ,   truncation=_a    ,   return_tensors="pt"    ,   ).input_ids.to(self.device       )
                else:
                      UpperCamelCase__      =							text_input.input_ids.to(self.device       )
                UpperCamelCase__      =							self.clip_model.get_text_features(_a       )
                UpperCamelCase__      =							text_embeddings_clip / text_embeddings_clip.norm(p=2    ,   dim=-1    ,   keepdim=_a       )
                # duplicate text embeddings clip for each generation per prompt
                UpperCamelCase__      =							text_embeddings_clip.repeat_interleave(_a    ,   dim=0       )

          # here `guidance_scale` is defined analog to the guidance weight `w` of equation (2)
          # of the Imagen paper: https://arxiv.org/pdf/2205.11487.pdf . `guidance_scale = 1`
          # corresponds to doing no classifier free guidance.
          UpperCamelCase__      =							guidance_scale > 1.0
          # get unconditional embeddings for classifier free guidance
          if do_classifier_free_guidance:
                UpperCamelCase__      =							text_input.input_ids.shape[-1]
                UpperCamelCase__      =							self.tokenizer([""]    ,   padding="max_length"    ,   max_length=_a    ,   return_tensors="pt"       )
                UpperCamelCase__      =							self.text_encoder(uncond_input.input_ids.to(self.device       )       )[0]
                # duplicate unconditional embeddings for each generation per prompt
                UpperCamelCase__      =							uncond_embeddings.repeat_interleave(_a    ,   dim=0       )

                # For classifier free guidance, we need to do two forward passes.
                # Here we concatenate the unconditional and text embeddings into a single batch
                # to avoid doing two forward passes
                UpperCamelCase__      =							torch.cat([uncond_embeddings, text_embeddings]       )

          # get the initial random noise unless the user supplied it

          # Unlike in other pipelines, latents need to be generated in the target device
          # for 1-to-1 results reproducibility with the CompVis implementation.
          # However this currently doesn't work in `mps`.
          UpperCamelCase__      =							(batch_size * num_images_per_prompt, self.unet.config.in_channels, height // 8, width // 8)
          UpperCamelCase__      =							text_embeddings.dtype
          if latents is None:
                if self.device.type == "mps":
                      # randn does not work reproducibly on mps
                      UpperCamelCase__      =							torch.randn(_a    ,   generator=_a    ,   device="cpu"    ,   dtype=_a       ).to(
                          self.device       )
                else:
                      UpperCamelCase__      =							torch.randn(_a    ,   generator=_a    ,   device=self.device    ,   dtype=_a       )
          else:
                if latents.shape != latents_shape:
                      raise ValueError(f'''Unexpected latents shape, got {latents.shape}, expected {latents_shape}'''       )
                UpperCamelCase__      =							latents.to(self.device       )

          # set timesteps
          UpperCamelCase__      =							'offset' in set(inspect.signature(self.scheduler.set_timesteps       ).parameters.keys()       )
          UpperCamelCase__      =							{}
          if accepts_offset:
                UpperCamelCase__      =							1

          self.scheduler.set_timesteps(_a    ,   **_a       )

          # Some schedulers like PNDM have timesteps as arrays
          # It's more optimized to move all timesteps to correct device beforehand
          UpperCamelCase__      =							self.scheduler.timesteps.to(self.device       )

          # scale the initial noise by the standard deviation required by the scheduler
          UpperCamelCase__      =							latents * self.scheduler.init_noise_sigma

          # prepare extra kwargs for the scheduler step, since not all schedulers have the same signature
          # eta (η) is only used with the DDIMScheduler, it will be ignored for other schedulers.
          # eta corresponds to η in DDIM paper: https://arxiv.org/abs/2010.02502
          # and should be between [0, 1]
          UpperCamelCase__      =							'eta' in set(inspect.signature(self.scheduler.step       ).parameters.keys()       )
          UpperCamelCase__      =							{}
          if accepts_eta:
                UpperCamelCase__      =							eta

          # check if the scheduler accepts generator
          UpperCamelCase__      =							'generator' in set(inspect.signature(self.scheduler.step       ).parameters.keys()       )
          if accepts_generator:
                UpperCamelCase__      =							generator

          for i, t in enumerate(self.progress_bar(_a       )       ):
                # expand the latents if we are doing classifier free guidance
                UpperCamelCase__      =							torch.cat([latents] * 2       ) if do_classifier_free_guidance else latents
                UpperCamelCase__      =							self.scheduler.scale_model_input(_a    ,   _a       )

                # predict the noise residual
                UpperCamelCase__      =							self.unet(_a    ,   _a    ,   encoder_hidden_states=_a       ).sample

                # perform classifier free guidance
                if do_classifier_free_guidance:
                      UpperCamelCase__      =							noise_pred.chunk(2       )
                      UpperCamelCase__      =							noise_pred_uncond + guidance_scale * (noise_pred_text - noise_pred_uncond)

                # perform clip guidance
                if clip_guidance_scale > 0:
                      UpperCamelCase__      =							(
                          text_embeddings.chunk(2       )[1] if do_classifier_free_guidance else text_embeddings
                      )
                      UpperCamelCase__      =							self.cond_fn(
                          _a    ,   _a    ,   _a    ,   _a    ,   _a    ,   _a    ,   _a    ,   _a    ,   _a    ,   )

                # compute the previous noisy sample x_t -> x_t-1
                UpperCamelCase__      =							self.scheduler.step(_a    ,   _a    ,   _a    ,   **_a       ).prev_sample

          # scale and decode the image latents with vae
          UpperCamelCase__      =							1 / self.vae.config.scaling_factor * latents
          UpperCamelCase__      =							self.vae.decode(_a       ).sample

          UpperCamelCase__      =							(image / 2 + 0.5).clamp(0    ,   1       )
          UpperCamelCase__      =							image.cpu().permute(0    ,   2    ,   3    ,   1       ).numpy()

          if output_type == "pil":
                UpperCamelCase__      =							self.numpy_to_pil(_a       )

          if not return_dict:
                return (image, None)

          return StableDiffusionPipelineOutput(images=_a    ,   nsfw_content_detected=_a       )






'''simple docstring'''




from __future__ import annotations

import unittest
from collections.abc import Iterator


class    UpperCAmelCase__	:






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



class    UpperCAmelCase__	:






   """simple docstring"""
   def __init__(self					)     ->  None:
        lowercase_       :							Node | None  					=       None
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							int  					=       None
   def 		_lowerCamelCase			(self					)     ->  bool:
        return self.root is None
   def 		_lowerCamelCase			(self							,					_a					)     ->  None:
        lowercase_       :							Any  					=       self._put(self.root							,					_a					)
   def 		_lowerCamelCase			(self							,					_a							,					_a							,					_a = None					)     ->  Node:
        if node is None:
             lowercase_       :							Union[str, Any]  					=       Node(_a							,					_a					)
        else:
             if label < node.label:
                  lowercase_       :							Optional[int]  					=       self._put(node.left							,					_a							,					_a					)
             elif label > node.label:
                  lowercase_       :							List[str]  					=       self._put(node.right							,					_a							,					_a					)
             else:
                  lowercase_       :							Optional[int]  					=       f'''Node with label {label} already exists'''
                  raise Exception(_a					)

        return node
   def 		_lowerCamelCase			(self							,					_a					)     ->  Node:
        return self._search(self.root							,					_a					)
   def 		_lowerCamelCase			(self							,					_a							,					_a					)     ->  Node:
        if node is None:
             lowercase_       :							Optional[int]  					=       f'''Node with label {label} does not exist'''
             raise Exception(_a					)
        else:
             if label < node.label:
                  lowercase_       :							int  					=       self._search(node.left							,					_a					)
             elif label > node.label:
                  lowercase_       :							str  					=       self._search(node.right							,					_a					)

        return node
   def 		_lowerCamelCase			(self							,					_a					)     ->  None:
        lowercase_       :							List[str]  					=       self.search(_a					)
        if node.right and node.left:
             lowercase_       :							int  					=       self._get_lowest_node(node.right					)
             lowercase_       :							Any  					=       node.left
             lowercase_       :							str  					=       node.right
             lowercase_       :							Any  					=       lowest_node
             if node.right:
                  lowercase_       :							Any  					=       lowest_node
             self._reassign_nodes(_a							,					_a					)
        elif not node.right and node.left:
             self._reassign_nodes(_a							,					node.left					)
        elif node.right and not node.left:
             self._reassign_nodes(_a							,					node.right					)
        else:
             self._reassign_nodes(_a							,					_a					)
   def 		_lowerCamelCase			(self							,					_a							,					_a					)     ->  None:
        if new_children:
             lowercase_       :							List[str]  					=       node.parent

        if node.parent:
             if node.parent.right == node:
                  lowercase_       :							str  					=       new_children
             else:
                  lowercase_       :							Tuple  					=       new_children
        else:
             lowercase_       :							Union[str, Any]  					=       new_children
   def 		_lowerCamelCase			(self							,					_a					)     ->  Node:
        if node.left:
             lowercase_       :							Optional[int]  					=       self._get_lowest_node(node.left					)
        else:
             lowercase_       :							str  					=       node
             self._reassign_nodes(_a							,					node.right					)

        return lowest_node
   def 		_lowerCamelCase			(self							,					_a					)     ->  bool:
        try:
             self.search(_a					)
             return True
        except Exception:
             return False
   def 		_lowerCamelCase			(self					)     ->  int:
        if self.root is None:
             raise Exception('Binary search tree is empty'					)

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

        return node.label
   def 		_lowerCamelCase			(self					)     ->  int:
        if self.root is None:
             raise Exception('Binary search tree is empty'					)

        lowercase_       :							Optional[Any]  					=       self.root
        while node.left is not None:
             lowercase_       :							Optional[int]  					=       node.left

        return node.label
   def 		_lowerCamelCase			(self					)     ->  Iterator[Node]:
        return self._inorder_traversal(self.root					)
   def 		_lowerCamelCase			(self							,					_a					)     ->  Iterator[Node]:
        if node is not None:
             yield from self._inorder_traversal(node.left					)
             yield node
             yield from self._inorder_traversal(node.right					)
   def 		_lowerCamelCase			(self					)     ->  Iterator[Node]:
        return self._preorder_traversal(self.root					)





   def 		_lowerCamelCase			(self							,					_a					)     ->  Iterator[Node]:
        if node is not None:
             yield node
             yield from self._preorder_traversal(node.left					)
             yield from self._preorder_traversal(node.right					)



class    UpperCAmelCase__	(							unittest.TestCase      ):






   """simple docstring"""
   @staticmethod
   def 		_lowerCamelCase			()     ->  BinarySearchTree:
        lowercase_       :							int  					=       BinarySearchTree()
        t.put(8					)
        t.put(3					)
        t.put(6					)
        t.put(1					)
        t.put(10					)
        t.put(14					)
        t.put(13					)
        t.put(4					)
        t.put(7					)
        t.put(5					)

        return t
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							List[Any]  					=       BinarySearchTree()
        assert t.is_empty()

        t.put(8					)
        assert t.root is not None
        assert t.root.parent is None
        assert t.root.label == 8

        t.put(10					)
        assert t.root.right is not None
        assert t.root.right.parent == t.root
        assert t.root.right.label == 10

        t.put(3					)
        assert t.root.left is not None
        assert t.root.left.parent == t.root
        assert t.root.left.label == 3

        t.put(6					)
        assert t.root.left.right is not None
        assert t.root.left.right.parent == t.root.left
        assert t.root.left.right.label == 6

        t.put(1					)
        assert t.root.left.left is not None
        assert t.root.left.left.parent == t.root.left
        assert t.root.left.left.label == 1

        with self.assertRaises(_a					):  # noqa: B017
             t.put(1					)
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							List[Any]  					=       self._get_binary_search_tree()

        lowercase_       :							int  					=       t.search(6					)
        assert node.label == 6

        lowercase_       :							str  					=       t.search(13					)
        assert node.label == 13

        with self.assertRaises(_a					):  # noqa: B017
             t.search(2					)
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							Any  					=       self._get_binary_search_tree()

        t.remove(13					)
        assert t.root is not None
        assert t.root.right is not None
        assert t.root.right.right is not None
        assert t.root.right.right.right is None
        assert t.root.right.right.left is None

        t.remove(7					)
        assert t.root.left is not None
        assert t.root.left.right is not None
        assert t.root.left.right.left is not None
        assert t.root.left.right.right is None
        assert t.root.left.right.left.label == 4

        t.remove(6					)
        assert t.root.left.left is not None
        assert t.root.left.right.right is not None
        assert t.root.left.left.label == 1
        assert t.root.left.right.label == 4
        assert t.root.left.right.right.label == 5
        assert t.root.left.right.left is None
        assert t.root.left.left.parent == t.root.left
        assert t.root.left.right.parent == t.root.left

        t.remove(3					)
        assert t.root is not None
        assert t.root.left.label == 4
        assert t.root.left.right.label == 5
        assert t.root.left.left.label == 1
        assert t.root.left.parent == t.root
        assert t.root.left.left.parent == t.root.left
        assert t.root.left.right.parent == t.root.left

        t.remove(4					)
        assert t.root.left is not None
        assert t.root.left.left is not None
        assert t.root.left.label == 5
        assert t.root.left.right is None
        assert t.root.left.left.label == 1
        assert t.root.left.parent == t.root
        assert t.root.left.left.parent == t.root.left
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							Union[str, Any]  					=       self._get_binary_search_tree()

        t.remove(3					)
        assert t.root is not None
        assert t.root.left is not None
        assert t.root.left.left is not None
        assert t.root.left.right is not None
        assert t.root.left.right.left is not None
        assert t.root.left.right.right is not None
        assert t.root.left.label == 4
        assert t.root.left.right.label == 6
        assert t.root.left.left.label == 1
        assert t.root.left.right.right.label == 7
        assert t.root.left.right.left.label == 5
        assert t.root.left.parent == t.root
        assert t.root.left.right.parent == t.root.left
        assert t.root.left.left.parent == t.root.left
        assert t.root.left.right.left.parent == t.root.left.right
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							Union[str, Any]  					=       self._get_binary_search_tree()
        t.empty()
        assert t.root is None
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							str  					=       self._get_binary_search_tree()
        assert not t.is_empty()

        t.empty()
        assert t.is_empty()
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							List[Any]  					=       self._get_binary_search_tree()

        assert t.exists(6					)
        assert not t.exists(-1					)
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							Dict  					=       self._get_binary_search_tree()

        assert t.get_max_label() == 14

        t.empty()
        with self.assertRaises(_a					):  # noqa: B017
             t.get_max_label()
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							Tuple  					=       self._get_binary_search_tree()

        assert t.get_min_label() == 1

        t.empty()
        with self.assertRaises(_a					):  # noqa: B017
             t.get_min_label()
   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							Tuple  					=       self._get_binary_search_tree()

        lowercase_       :							List[str]  					=       [i.label for i in t.inorder_traversal()]
        assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 10, 13, 14]





   def 		_lowerCamelCase			(self					)     ->  None:
        lowercase_       :							Tuple  					=       self._get_binary_search_tree()

        lowercase_       :							List[Any]  					=       [i.label for i in t.preorder_traversal()]
        assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 10, 14, 13]



def _UpperCamelCase (							):
     lowercase_       :							int  					=       BinarySearchTree()
     t.put(8				)
     t.put(3				)
     t.put(6				)
     t.put(1				)
     t.put(10				)
     t.put(14				)
     t.put(13				)
     t.put(4				)
     t.put(7				)
     t.put(5				)

     print(
         '\n            8\n           / \\\n          3   10\n         / \\    \\\n        1   6    14\n           / \\   /\n          4   7 13\n           \\\n            5\n        '				)

     print('Label 6 exists:'	,							t.exists(6				)				)
     print('Label 13 exists:'	,							t.exists(13				)				)
     print('Label -1 exists:'	,							t.exists(-1				)				)
     print('Label 12 exists:'	,							t.exists(12				)				)

     # Prints all the elements of the list in inorder traversal
     lowercase_       :							Optional[int]  					=       [i.label for i in t.inorder_traversal()]
     print('Inorder traversal:'	,							SCREAMING_SNAKE_CASE_				)

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

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

     # Delete elements
     print('\nDeleting elements 13, 10, 8, 3, 6, 14'				)
     print(
         '\n          4\n         / \\\n        1   7\n             \\\n              5\n        '				)
     t.remove(13				)
     t.remove(10				)
     t.remove(8				)
     t.remove(3				)
     t.remove(6				)
     t.remove(14				)

     # Prints all the elements of the list in inorder traversal after delete
     lowercase_       :							Dict  					=       [i.label for i in t.inorder_traversal()]
     print('Inorder traversal after delete:'	,							SCREAMING_SNAKE_CASE_				)

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

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


if __name__ == "__main__":
 binary_search_tree_example()




