


'''simple docstring'''
import inspect
import unittest

from transformers import MobileViTConfig
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
  import torch

  from transformers import MobileViTForImageClassification, MobileViTForSemanticSegmentation, MobileViTModel
  from transformers.models.mobilevit.modeling_mobilevit import MOBILEVIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
  from PIL import Image

  from transformers import MobileViTImageProcessor




class      lowerCamelCase_  (      __a ):






      def lowercase_				(   self							:       Union[str, Any]					):


          '''simple docstring'''


          UpperCAmelCase__     :						List[Any]						=							self.config_class(**self.inputs_dict					)
          self.parent.assertTrue(hasattr(_A		,		'''hidden_sizes'''					)					)
          self.parent.assertTrue(hasattr(_A		,		'''neck_hidden_sizes'''					)					)
          self.parent.assertTrue(hasattr(_A		,		'''num_attention_heads'''					)					)




class      lowerCamelCase_  :






      def __init__(   self							:       Optional[Any]		,		_A							:       Tuple		,		_A							:       List[Any]=13		,		_A							:       Union[str, Any]=32		,		_A							:       int=2		,		_A							:       int=3		,		_A							:       List[Any]=640		,		_A							:       Optional[int]=4		,		_A							:       List[str]="silu"		,		_A							:       Optional[int]=3		,		_A							:       Optional[Any]=32		,		_A							:       str=0.1		,		_A							:       List[str]=0.1		,		_A							:       List[Any]=0.1		,		_A							:       Optional[int]=0.0_2		,		_A							:       Optional[int]=True		,		_A							:       str=True		,		_A							:       Dict=10		,		_A							:       Tuple=None		,		):


          '''simple docstring'''


          UpperCAmelCase__     :						Optional[Any]						=							parent
          UpperCAmelCase__     :						Dict						=							batch_size
          UpperCAmelCase__     :						Any						=							image_size
          UpperCAmelCase__     :						str						=							patch_size
          UpperCAmelCase__     :						List[str]						=							num_channels
          UpperCAmelCase__     :						Any						=							last_hidden_size
          UpperCAmelCase__     :						Dict						=							num_attention_heads
          UpperCAmelCase__     :						List[Any]						=							hidden_act
          UpperCAmelCase__     :						Any						=							conv_kernel_size
          UpperCAmelCase__     :						Optional[Any]						=							output_stride
          UpperCAmelCase__     :						Dict						=							hidden_dropout_prob
          UpperCAmelCase__     :						Dict						=							attention_probs_dropout_prob
          UpperCAmelCase__     :						Optional[int]						=							classifier_dropout_prob
          UpperCAmelCase__     :						int						=							use_labels
          UpperCAmelCase__     :						Any						=							is_training
          UpperCAmelCase__     :						Union[str, Any]						=							num_labels
          UpperCAmelCase__     :						Optional[Any]						=							initializer_range
          UpperCAmelCase__     :						Tuple						=							scope






      def lowercase_				(   self							:       Dict					):


          '''simple docstring'''


          UpperCAmelCase__     :						Tuple						=							floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]					)

          UpperCAmelCase__     :						List[Any]						=							None
          UpperCAmelCase__     :						Optional[Any]						=							None
          if self.use_labels:
              UpperCAmelCase__     :						List[str]						=							ids_tensor([self.batch_size]		,		self.num_labels					)
              UpperCAmelCase__     :						List[str]						=							ids_tensor([self.batch_size, self.image_size, self.image_size]		,		self.num_labels					)

          UpperCAmelCase__     :						Tuple						=							self.get_config()

          return config, pixel_values, labels, pixel_labels






      def lowercase_				(   self							:       int					):


          '''simple docstring'''


          return MobileViTConfig(
              image_size=self.image_size		,		patch_size=self.patch_size		,		num_channels=self.num_channels		,		num_attention_heads=self.num_attention_heads		,		hidden_act=self.hidden_act		,		conv_kernel_size=self.conv_kernel_size		,		output_stride=self.output_stride		,		hidden_dropout_prob=self.hidden_dropout_prob		,		attention_probs_dropout_prob=self.attention_probs_dropout_prob		,		classifier_dropout_prob=self.classifier_dropout_prob		,		initializer_range=self.initializer_range		,		)






      def lowercase_				(   self							:       List[str]		,		_A							:       int		,		_A							:       List[str]		,		_A							:       Optional[int]		,		_A							:       Union[str, Any]					):


          '''simple docstring'''


          UpperCAmelCase__     :						Optional[Any]						=							MobileViTModel(config=_A					)
          model.to(_A					)
          model.eval()
          UpperCAmelCase__     :						int						=							model(_A					)
          self.parent.assertEqual(
              result.last_hidden_state.shape		,		(
                  self.batch_size,
                  self.last_hidden_size,
                  self.image_size // self.output_stride,
                  self.image_size // self.output_stride,
              )		,		)






      def lowercase_				(   self							:       List[Any]		,		_A							:       List[str]		,		_A							:       List[str]		,		_A							:       Dict		,		_A							:       str					):


          '''simple docstring'''


          UpperCAmelCase__     :						str						=							self.num_labels
          UpperCAmelCase__     :						Optional[int]						=							MobileViTForImageClassification(_A					)
          model.to(_A					)
          model.eval()
          UpperCAmelCase__     :						List[Any]						=							model(_A		,		labels=_A					)
          self.parent.assertEqual(result.logits.shape		,		(self.batch_size, self.num_labels)					)






      def lowercase_				(   self							:       Dict		,		_A							:       Union[str, Any]		,		_A							:       Any		,		_A							:       Optional[int]		,		_A							:       Dict					):


          '''simple docstring'''


          UpperCAmelCase__     :						int						=							self.num_labels
          UpperCAmelCase__     :						Any						=							MobileViTForSemanticSegmentation(_A					)
          model.to(_A					)
          model.eval()
          UpperCAmelCase__     :						List[str]						=							model(_A					)
          self.parent.assertEqual(
              result.logits.shape		,		(
                  self.batch_size,
                  self.num_labels,
                  self.image_size // self.output_stride,
                  self.image_size // self.output_stride,
              )		,		)
          UpperCAmelCase__     :						Optional[Any]						=							model(_A		,		labels=_A					)
          self.parent.assertEqual(
              result.logits.shape		,		(
                  self.batch_size,
                  self.num_labels,
                  self.image_size // self.output_stride,
                  self.image_size // self.output_stride,
              )		,		)






      def lowercase_				(   self							:       List[Any]					):


          '''simple docstring'''


          UpperCAmelCase__     :						int						=							self.prepare_config_and_inputs()
          UpperCAmelCase__		,		UpperCAmelCase__		,		UpperCAmelCase__		,		UpperCAmelCase__     :						Any						=							config_and_inputs
          UpperCAmelCase__     :						int						=							{'''pixel_values''': pixel_values}
          return config, inputs_dict




@require_torch
class      lowerCamelCase_  (      __a	,			__a	,			unittest.TestCase ):
      lowerCAmelCase__							=	(
          (MobileViTModel, MobileViTForImageClassification, MobileViTForSemanticSegmentation)
          if is_torch_available()
          else ()
      )
      lowerCAmelCase__							=	(
          {
              'feature-extraction': MobileViTModel,
              'image-classification': MobileViTForImageClassification,
              'image-segmentation': MobileViTForSemanticSegmentation,
          }
          if is_torch_available()
          else {}
      )

      lowerCAmelCase__							=	False
      lowerCAmelCase__							=	False
      lowerCAmelCase__							=	False
      lowerCAmelCase__							=	False






      def lowercase_				(   self							:       List[Any]					):


          '''simple docstring'''


          UpperCAmelCase__     :						Optional[Any]						=							MobileViTModelTester(self					)
          UpperCAmelCase__     :						Optional[int]						=							MobileViTConfigTester(self		,		config_class=_A		,		has_text_modality=_A					)






      def lowercase_				(   self							:       Union[str, Any]					):


          '''simple docstring'''


          self.config_tester.run_common_tests()






      @unittest.skip(reason='''MobileViT does not use inputs_embeds'''					)
      def lowercase_				(   self							:       str					):


          '''simple docstring'''


          pass






      @unittest.skip(reason='''MobileViT does not support input and output embeddings'''					)
      def lowercase_				(   self							:       List[Any]					):


          '''simple docstring'''


          pass






      @unittest.skip(reason='''MobileViT does not output attentions'''					)
      def lowercase_				(   self							:       Optional[Any]					):


          '''simple docstring'''


          pass






      def lowercase_				(   self							:       int					):


          '''simple docstring'''


          UpperCAmelCase__		,		UpperCAmelCase__     :						Dict						=							self.model_tester.prepare_config_and_inputs_for_common()

          for model_class in self.all_model_classes:
              UpperCAmelCase__     :						Optional[Any]						=							model_class(_A					)
              UpperCAmelCase__     :						int						=							inspect.signature(model.forward					)
              # signature.parameters is an OrderedDict => so arg_names order is deterministic
              UpperCAmelCase__     :						Union[str, Any]						=							[*signature.parameters.keys()]

              UpperCAmelCase__     :						List[str]						=							['''pixel_values''']
              self.assertListEqual(arg_names[:1]		,		_A					)






      @unittest.skip('''Will be fixed soon by reducing the size of the model used for common tests.'''					)
      def lowercase_				(   self							:       List[Any]					):


          '''simple docstring'''


          pass






      def lowercase_				(   self							:       Any					):


          '''simple docstring'''


          UpperCAmelCase__     :						str						=							self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_model(*_A					)






      def lowercase_				(   self							:       str					):


          '''simple docstring'''


          def check_hidden_states_output(_A							:       Tuple		,		_A							:       Any		,		_A							:       List[Any]					):
              UpperCAmelCase__     :						Optional[int]						=							model_class(_A					)
              model.to(_A					)
              model.eval()

              with torch.no_grad():
                  UpperCAmelCase__     :						Any						=							model(**self._prepare_for_class(_A		,		_A					)					)

              UpperCAmelCase__     :						List[Any]						=							outputs.hidden_states

              UpperCAmelCase__     :						Tuple						=							5
              self.assertEqual(len(_A					)		,		_A					)

              # MobileViT's feature maps are of shape (batch_size, num_channels, height, width)
              # with the width and height being successively divided by 2.
              UpperCAmelCase__     :						Any						=							2
              for i in range(len(_A					)					):
                  self.assertListEqual(
                      list(hidden_states[i].shape[-2:]					)		,		[self.model_tester.image_size // divisor, self.model_tester.image_size // divisor]		,		)
                  divisor *= 2

              self.assertEqual(self.model_tester.output_stride		,		divisor // 2					)

          UpperCAmelCase__		,		UpperCAmelCase__     :						str						=							self.model_tester.prepare_config_and_inputs_for_common()

          for model_class in self.all_model_classes:
              UpperCAmelCase__     :						Union[str, Any]						=							True
              check_hidden_states_output(_A		,		_A		,		_A					)

              # check that output_hidden_states also work using config
              del inputs_dict["output_hidden_states"]
              UpperCAmelCase__     :						Dict						=							True

              check_hidden_states_output(_A		,		_A		,		_A					)






      def lowercase_				(   self							:       List[Any]					):


          '''simple docstring'''


          UpperCAmelCase__     :						List[Any]						=							self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_for_image_classification(*_A					)






      def lowercase_				(   self							:       int					):


          '''simple docstring'''


          UpperCAmelCase__     :						Union[str, Any]						=							self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_for_semantic_segmentation(*_A					)






      @slow
      def lowercase_				(   self							:       List[Any]					):


          '''simple docstring'''


          for model_name in MOBILEVIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
              UpperCAmelCase__     :						str						=							MobileViTModel.from_pretrained(_A					)
              self.assertIsNotNone(_A					)





def    a__			(   )       ->      int:
    UpperCAmelCase__     :						Optional[Any]						=							Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''		)
    return image







@require_torch
@require_vision
class      lowerCamelCase_  (      unittest.TestCase ):






      @cached_property
      def lowercase_				(   self							:       Optional[Any]					):


          '''simple docstring'''


          return MobileViTImageProcessor.from_pretrained('''apple/mobilevit-xx-small'''					) if is_vision_available() else None






      @slow
      def lowercase_				(   self							:       Optional[int]					):


          '''simple docstring'''


          UpperCAmelCase__     :						Tuple						=							MobileViTForImageClassification.from_pretrained('''apple/mobilevit-xx-small'''					).to(_A					)

          UpperCAmelCase__     :						int						=							self.default_image_processor
          UpperCAmelCase__     :						Dict						=							prepare_img()
          UpperCAmelCase__     :						Optional[Any]						=							image_processor(images=_A		,		return_tensors='''pt'''					).to(_A					)

          # forward pass
          with torch.no_grad():
              UpperCAmelCase__     :						Optional[Any]						=							model(**_A					)

          # verify the logits
          UpperCAmelCase__     :						Any						=							torch.Size((1, 1_000)					)
          self.assertEqual(outputs.logits.shape		,		_A					)

          UpperCAmelCase__     :						Optional[int]						=							torch.tensor([-1.9_3_6_4, -1.2_3_2_7, -0.4_6_5_3]					).to(_A					)

          self.assertTrue(torch.allclose(outputs.logits[0, :3]		,		_A		,		atol=1e-4					)					)






      @slow
      def lowercase_				(   self							:       Optional[int]					):


          '''simple docstring'''


          UpperCAmelCase__     :						int						=							MobileViTForSemanticSegmentation.from_pretrained('''apple/deeplabv3-mobilevit-xx-small'''					)
          UpperCAmelCase__     :						Optional[Any]						=							model.to(_A					)

          UpperCAmelCase__     :						Optional[int]						=							MobileViTImageProcessor.from_pretrained('''apple/deeplabv3-mobilevit-xx-small'''					)

          UpperCAmelCase__     :						int						=							prepare_img()
          UpperCAmelCase__     :						Dict						=							image_processor(images=_A		,		return_tensors='''pt'''					).to(_A					)

          # forward pass
          with torch.no_grad():
              UpperCAmelCase__     :						Any						=							model(**_A					)
          UpperCAmelCase__     :						List[Any]						=							outputs.logits

          # verify the logits
          UpperCAmelCase__     :						Optional[int]						=							torch.Size((1, 21, 32, 32)					)
          self.assertEqual(logits.shape		,		_A					)

          UpperCAmelCase__     :						List[Any]						=							torch.tensor(
              [
                  [[6.9_7_1_3, 6.9_7_8_6, 7.2_4_2_2], [7.2_8_9_3, 7.2_8_2_5, 7.4_4_4_6], [7.6_5_8_0, 7.8_7_9_7, 7.9_4_2_0]],
                  [[-1_0.6_8_6_9, -1_0.3_2_5_0, -1_0.3_4_7_1], [-1_0.4_2_2_8, -9.9_8_6_8, -9.7_1_3_2], [-1_1.0_4_0_5, -1_1.0_2_2_1, -1_0.7_3_1_8]],
                  [[-3.3_0_8_9, -2.8_5_3_9, -2.6_7_4_0], [-3.2_7_0_6, -2.5_6_2_1, -2.5_1_0_8], [-3.2_5_3_4, -2.6_6_1_5, -2.6_6_5_1]],
              ]		,		device=_A		,		)

          self.assertTrue(torch.allclose(logits[0, :3, :3, :3]		,		_A		,		atol=1e-4					)					)






      @slow
      def lowercase_				(   self							:       Tuple					):


          '''simple docstring'''


          UpperCAmelCase__     :						Tuple						=							MobileViTForSemanticSegmentation.from_pretrained('''apple/deeplabv3-mobilevit-xx-small'''					)
          UpperCAmelCase__     :						str						=							model.to(_A					)

          UpperCAmelCase__     :						Tuple						=							MobileViTImageProcessor.from_pretrained('''apple/deeplabv3-mobilevit-xx-small'''					)

          UpperCAmelCase__     :						str						=							prepare_img()
          UpperCAmelCase__     :						Tuple						=							image_processor(images=_A		,		return_tensors='''pt'''					).to(_A					)

          # forward pass
          with torch.no_grad():
              UpperCAmelCase__     :						Any						=							model(**_A					)

          UpperCAmelCase__     :						Tuple						=							outputs.logits.detach().cpu()

          UpperCAmelCase__     :						Dict						=							image_processor.post_process_semantic_segmentation(outputs=_A		,		target_sizes=[(50, 60)]					)
          UpperCAmelCase__     :						str						=							torch.Size((50, 60)					)
          self.assertEqual(segmentation[0].shape		,		_A					)

          UpperCAmelCase__     :						int						=							image_processor.post_process_semantic_segmentation(outputs=_A					)
          UpperCAmelCase__     :						str						=							torch.Size((32, 32)					)
          self.assertEqual(segmentation[0].shape		,		_A					)



'''simple docstring'''







from __future__ import annotations

import math
import random
from typing import Any


class        A__   :



    def __init__(       self							)    ->   None:





           '''simple docstring'''
           A_						       =   []
           A_						       =   0
           A_						       =   0



    def        snake_case_      (       self							)    ->   bool:





           '''simple docstring'''
           return self.head == self.tail



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           self.data.append(UpperCamelCase__							)
           A_						       =   self.tail + 1



    def        snake_case_      (       self							)    ->   Any:





           '''simple docstring'''
           A_						       =   self.data[self.head]
           A_						       =   self.head + 1
           return ret



    def        snake_case_      (       self							)    ->   int:





           '''simple docstring'''
           return self.tail - self.head







    def        snake_case_      (       self							)    ->   None:





           '''simple docstring'''
           print(self.data							)
           print("""**************"""							)
           print(self.data[self.head : self.tail]							)


class        A__   :



    def __init__(       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           A_						       =   data
           A_						       =   None
           A_						       =   None
           A_						       =   1



    def        snake_case_      (       self							)    ->   Any:





           '''simple docstring'''
           return self.data



    def        snake_case_      (       self							)    ->   MyNode | None:





           '''simple docstring'''
           return self.left



    def        snake_case_      (       self							)    ->   MyNode | None:





           '''simple docstring'''
           return self.right



    def        snake_case_      (       self							)    ->   int:





           '''simple docstring'''
           return self.height



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           A_						       =   data



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           A_						       =   node



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           A_						       =   node







    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           A_						       =   height

def    UpperCAmelCase__     (   UpperCAmelCase__					)      ->      int:
       if node is None:
              return 0
       return node.get_height()
def    UpperCAmelCase__     (   UpperCAmelCase__,							UpperCAmelCase__					)      ->      int:
       if a > b:
              return a
       return b
def    UpperCAmelCase__     (   UpperCAmelCase__					)      ->      MyNode:
       print("""left rotation node:""",							node.get_data()					)
       A_						       =   node.get_left()
       assert ret is not None
       node.set_left(ret.get_right()					)
       ret.set_right(UpperCAmelCase__					)
       A_						       =   my_max(get_height(node.get_right()					),							get_height(node.get_left()					)					) + 1
       node.set_height(UpperCAmelCase__					)
       A_						       =   my_max(get_height(ret.get_right()					),							get_height(ret.get_left()					)					) + 1
       ret.set_height(UpperCAmelCase__					)
       return ret
def    UpperCAmelCase__     (   UpperCAmelCase__					)      ->      MyNode:
       print("""right rotation node:""",							node.get_data()					)
       A_						       =   node.get_right()
       assert ret is not None
       node.set_right(ret.get_left()					)
       ret.set_left(UpperCAmelCase__					)
       A_						       =   my_max(get_height(node.get_right()					),							get_height(node.get_left()					)					) + 1
       node.set_height(UpperCAmelCase__					)
       A_						       =   my_max(get_height(ret.get_right()					),							get_height(ret.get_left()					)					) + 1
       ret.set_height(UpperCAmelCase__					)
       return ret
def    UpperCAmelCase__     (   UpperCAmelCase__					)      ->      MyNode:
       A_						       =   node.get_left()
       assert left_child is not None
       node.set_left(left_rotation(UpperCAmelCase__					)					)
       return right_rotation(UpperCAmelCase__					)
def    UpperCAmelCase__     (   UpperCAmelCase__					)      ->      MyNode:
       A_						       =   node.get_right()
       assert right_child is not None
       node.set_right(right_rotation(UpperCAmelCase__					)					)
       return left_rotation(UpperCAmelCase__					)
def    UpperCAmelCase__     (   UpperCAmelCase__,							UpperCAmelCase__					)      ->      MyNode | None:
       if node is None:
              return MyNode(UpperCAmelCase__					)
       if data < node.get_data():
              node.set_left(insert_node(node.get_left(),							UpperCAmelCase__					)					)
              if (
                  get_height(node.get_left()					) - get_height(node.get_right()					) == 2
              ):  # an unbalance detected
                     A_						       =   node.get_left()
                     assert left_child is not None
                     if (
                         data < left_child.get_data()
                     ):  # new node is the left child of the left child
                            A_						       =   right_rotation(UpperCAmelCase__					)
                     else:
                            A_						       =   lr_rotation(UpperCAmelCase__					)
       else:
              node.set_right(insert_node(node.get_right(),							UpperCAmelCase__					)					)
              if get_height(node.get_right()					) - get_height(node.get_left()					) == 2:
                     A_						       =   node.get_right()
                     assert right_child is not None
                     if data < right_child.get_data():
                            A_						       =   rl_rotation(UpperCAmelCase__					)
                     else:
                            A_						       =   left_rotation(UpperCAmelCase__					)
       A_						       =   my_max(get_height(node.get_right()					),							get_height(node.get_left()					)					) + 1
       node.set_height(UpperCAmelCase__					)
       return node
def    UpperCAmelCase__     (   UpperCAmelCase__					)      ->      Any:
       while True:
              A_						       =   root.get_right()
              if right_child is None:
                     break
              A_						       =   right_child
       return root.get_data()
def    UpperCAmelCase__     (   UpperCAmelCase__					)      ->      Any:
       while True:
              A_						       =   root.get_left()
              if left_child is None:
                     break
              A_						       =   left_child
       return root.get_data()
def    UpperCAmelCase__     (   UpperCAmelCase__,							UpperCAmelCase__					)      ->      MyNode | None:
       A_						       =   root.get_left()
       A_						       =   root.get_right()
       if root.get_data() == data:
              if left_child is not None and right_child is not None:
                     A_						       =   get_left_most(UpperCAmelCase__					)
                     root.set_data(UpperCAmelCase__					)
                     root.set_right(del_node(UpperCAmelCase__,							UpperCAmelCase__					)					)
              elif left_child is not None:
                     A_						       =   left_child
              elif right_child is not None:
                     A_						       =   right_child
              else:
                     return None
       elif root.get_data() > data:
              if left_child is None:
                     print("""No such data"""					)
                     return root
              else:
                     root.set_left(del_node(UpperCAmelCase__,							UpperCAmelCase__					)					)
       else:  # root.get_data() < data
              if right_child is None:
                     return root
              else:
                     root.set_right(del_node(UpperCAmelCase__,							UpperCAmelCase__					)					)

       if get_height(UpperCAmelCase__					) - get_height(UpperCAmelCase__					) == 2:
              assert right_child is not None
              if get_height(right_child.get_right()					) > get_height(right_child.get_left()					):
                     A_						       =   left_rotation(UpperCAmelCase__					)
              else:
                     A_						       =   rl_rotation(UpperCAmelCase__					)
       elif get_height(UpperCAmelCase__					) - get_height(UpperCAmelCase__					) == -2:
              assert left_child is not None
              if get_height(left_child.get_left()					) > get_height(left_child.get_right()					):
                     A_						       =   right_rotation(UpperCAmelCase__					)
              else:
                     A_						       =   lr_rotation(UpperCAmelCase__					)
       A_						       =   my_max(get_height(root.get_right()					),							get_height(root.get_left()					)					) + 1
       root.set_height(UpperCAmelCase__					)
       return root


class        A__   :



    def __init__(       self							)    ->   None:





           '''simple docstring'''
           A_						       =   None



    def        snake_case_      (       self							)    ->   int:





           '''simple docstring'''
           return get_height(self.root							)



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           print("""insert:""" + str(UpperCamelCase__							)							)
           A_						       =   insert_node(self.root		,					UpperCamelCase__							)



    def        snake_case_      (       self		,					UpperCamelCase__							)    ->   None:





           '''simple docstring'''
           print("""delete:""" + str(UpperCamelCase__							)							)
           if self.root is None:
                  print("""Tree is empty!"""							)
                  return
           A_						       =   del_node(self.root		,					UpperCamelCase__							)







    def __str__(       self		,					)    ->   str:  # a level traversale, gives a more intuitive look on the tree





           '''simple docstring'''
           A_						       =   """"""
           A_						       =   MyQueue()
           q.push(self.root							)
           A_						       =   self.get_height()
           if layer == 0:
                  return output
           A_						       =   0
           while not q.is_empty():
                  A_						       =   q.pop()
                  A_						       =   """ """ * int(math.pow(2		,					layer - 1							)							)
                  output += space
                  if node is None:
                         output += "*"
                         q.push(UpperCamelCase__							)
                         q.push(UpperCamelCase__							)
                  else:
                         output += str(node.get_data()							)
                         q.push(node.get_left()							)
                         q.push(node.get_right()							)
                  output += space
                  A_						       =   cnt + 1
                  for i in range(100							):
                         if cnt == math.pow(2		,					UpperCamelCase__							) - 1:
                                A_						       =   layer - 1
                                if layer == 0:
                                       output += "\n*************************************"
                                       return output
                                output += "\n"
                                break
           output += "\n*************************************"
           return output

def    UpperCAmelCase__     (   )      ->      None:
       import doctest

       doctest.testmod()


if __name__ == "__main__":
      _test()
      __lowerCamelCase									=     AVLtree()
      __lowerCamelCase									=     list(range(10))
      random.shuffle(lst)
      for i in lst:
            t.insert(i)
            print(str(t))
      random.shuffle(lst)
      for i in lst:
            t.del_node(i)
            print(str(t))
