




import unittest

import numpy as np

from transformers.testing_utils import require_torch, require_vision
from transformers.utils import is_torch_available, is_vision_available

from ...test_image_processing_common import ImageProcessingSavingTestMixin, prepare_video_inputs


if is_torch_available():
		import torch

if is_vision_available():
		from PIL import Image

		from transformers import VivitImageProcessor
class 		UpperCAmelCase   (				unittest.TestCase			):







						'''simple docstring'''





						def __init__(						self							:     Any       ,	__lowercase							:     List[Any]       ,	__lowercase							:     List[str]=7       ,	__lowercase							:     Any=3       ,	__lowercase							:     int=10       ,	__lowercase							:     Union[str, Any]=18       ,	__lowercase							:     Any=30       ,	__lowercase							:     List[Any]=4_00       ,	__lowercase							:     Tuple=True       ,	__lowercase							:     Optional[Any]=None       ,	__lowercase							:     Dict=True       ,	__lowercase							:     List[Any]=[0.5, 0.5, 0.5]       ,	__lowercase							:     Any=[0.5, 0.5, 0.5]       ,	__lowercase							:     Optional[int]=None       ,	):






							"""simple docstring"""






							snake_case_		    =     size if size is not None else {'''shortest_edge''': 18}
							snake_case_		    =     crop_size if crop_size is not None else {'''height''': 18, '''width''': 18}

							snake_case_		    =     parent
							snake_case_		    =     batch_size
							snake_case_		    =     num_channels
							snake_case_		    =     num_frames
							snake_case_		    =     image_size
							snake_case_		    =     min_resolution
							snake_case_		    =     max_resolution
							snake_case_		    =     do_resize
							snake_case_		    =     size
							snake_case_		    =     do_normalize
							snake_case_		    =     image_mean
							snake_case_		    =     image_std
							snake_case_		    =     crop_size






						def        snake_case__						(						self							:     Optional[Any]						):






							"""simple docstring"""






							return {
							    "image_mean": self.image_mean,
							    "image_std": self.image_std,
							    "do_normalize": self.do_normalize,
							    "do_resize": self.do_resize,
							    "size": self.size,
							    "crop_size": self.crop_size,
							}







@require_torch
@require_vision
class 		UpperCAmelCase   (				__lowercase       ,   unittest.TestCase			):







						'''simple docstring'''





						lowerCAmelCase_     		=   VivitImageProcessor if is_vision_available() else None






						def        snake_case__						(						self							:     int						):






							"""simple docstring"""






							snake_case_		    =     VivitImageProcessingTester(self						)






						@property
						def        snake_case__						(						self							:     Tuple						):






							"""simple docstring"""






							return self.image_processor_tester.prepare_image_processor_dict()






						def        snake_case__						(						self							:     List[str]						):






							"""simple docstring"""






							snake_case_		    =     self.image_processing_class(**self.image_processor_dict						)
							self.assertTrue(hasattr(snake_case_       ,	"image_mean"						)						)
							self.assertTrue(hasattr(snake_case_       ,	"image_std"						)						)
							self.assertTrue(hasattr(snake_case_       ,	"do_normalize"						)						)
							self.assertTrue(hasattr(snake_case_       ,	"do_resize"						)						)
							self.assertTrue(hasattr(snake_case_       ,	"do_center_crop"						)						)
							self.assertTrue(hasattr(snake_case_       ,	"size"						)						)






						def        snake_case__						(						self							:     List[Any]						):






							"""simple docstring"""






							snake_case_		    =     self.image_processing_class.from_dict(self.image_processor_dict						)
							self.assertEqual(image_processor.size       ,	{"shortest_edge": 18}						)
							self.assertEqual(image_processor.crop_size       ,	{"height": 18, "width": 18}						)

							snake_case_		    =     self.image_processing_class.from_dict(self.image_processor_dict       ,	size=42       ,	crop_size=84						)
							self.assertEqual(image_processor.size       ,	{"shortest_edge": 42}						)
							self.assertEqual(image_processor.crop_size       ,	{"height": 84, "width": 84}						)






						def        snake_case__						(						self							:     Optional[int]						):






							"""simple docstring"""






							snake_case_		    =     self.image_processing_class(**self.image_processor_dict						)
							# create random PIL videos
							snake_case_		    =     prepare_video_inputs(self.image_processor_tester       ,	equal_resolution=snake_case_						)
							for video in video_inputs:
								self.assertIsInstance(snake_case_       ,	snake_case_						)
								self.assertIsInstance(video[0]       ,	Image.Image						)

							# Test not batched input
							snake_case_		    =     image_processing(video_inputs[0]       ,	return_tensors="pt"						).pixel_values
							self.assertEqual(
							    encoded_videos.shape       ,	(
							        1,
							        self.image_processor_tester.num_frames,
							        self.image_processor_tester.num_channels,
							        self.image_processor_tester.crop_size["height"],
							        self.image_processor_tester.crop_size["width"],
							    )       ,	)

							# Test batched
							snake_case_		    =     image_processing(snake_case_       ,	return_tensors="pt"						).pixel_values
							self.assertEqual(
							    encoded_videos.shape       ,	(
							        self.image_processor_tester.batch_size,
							        self.image_processor_tester.num_frames,
							        self.image_processor_tester.num_channels,
							        self.image_processor_tester.crop_size["height"],
							        self.image_processor_tester.crop_size["width"],
							    )       ,	)






						def        snake_case__						(						self							:     str						):






							"""simple docstring"""






							snake_case_		    =     self.image_processing_class(**self.image_processor_dict						)
							# create random numpy tensors
							snake_case_		    =     prepare_video_inputs(self.image_processor_tester       ,	equal_resolution=snake_case_       ,	numpify=snake_case_						)
							for video in video_inputs:
								self.assertIsInstance(snake_case_       ,	snake_case_						)
								self.assertIsInstance(video[0]       ,	np.ndarray						)

							# Test not batched input
							snake_case_		    =     image_processing(video_inputs[0]       ,	return_tensors="pt"						).pixel_values
							self.assertEqual(
							    encoded_videos.shape       ,	(
							        1,
							        self.image_processor_tester.num_frames,
							        self.image_processor_tester.num_channels,
							        self.image_processor_tester.crop_size["height"],
							        self.image_processor_tester.crop_size["width"],
							    )       ,	)

							# Test batched
							snake_case_		    =     image_processing(snake_case_       ,	return_tensors="pt"						).pixel_values
							self.assertEqual(
							    encoded_videos.shape       ,	(
							        self.image_processor_tester.batch_size,
							        self.image_processor_tester.num_frames,
							        self.image_processor_tester.num_channels,
							        self.image_processor_tester.crop_size["height"],
							        self.image_processor_tester.crop_size["width"],
							    )       ,	)






						def        snake_case__						(						self							:     str						):






							"""simple docstring"""






							snake_case_		    =     self.image_processing_class(**self.image_processor_dict						)
							# create random PyTorch tensors
							snake_case_		    =     prepare_video_inputs(self.image_processor_tester       ,	equal_resolution=snake_case_       ,	torchify=snake_case_						)
							for video in video_inputs:
								self.assertIsInstance(snake_case_       ,	snake_case_						)
								self.assertIsInstance(video[0]       ,	torch.Tensor						)

							# Test not batched input
							snake_case_		    =     image_processing(video_inputs[0]       ,	return_tensors="pt"						).pixel_values
							self.assertEqual(
							    encoded_videos.shape       ,	(
							        1,
							        self.image_processor_tester.num_frames,
							        self.image_processor_tester.num_channels,
							        self.image_processor_tester.crop_size["height"],
							        self.image_processor_tester.crop_size["width"],
							    )       ,	)

							# Test batched
							snake_case_		    =     image_processing(snake_case_       ,	return_tensors="pt"						).pixel_values
							self.assertEqual(
							    encoded_videos.shape       ,	(
							        self.image_processor_tester.batch_size,
							        self.image_processor_tester.num_frames,
							        self.image_processor_tester.num_channels,
							        self.image_processor_tester.crop_size["height"],
							        self.image_processor_tester.crop_size["width"],
							    )       ,	)


from __future__ import annotations

import math
import random
from typing import Any



class 		UpperCamelCase__  :
   def __init__(self :					Optional[Any]   ):
    __a :  list[Any]						=  []
    __a :  int						=  0
    __a :  int						=  0
   def       lowerCAmelCase			(self :					Optional[int]   ):
    return self.head == self.tail
   def       lowerCAmelCase			(self :					List[Any]					,				snake_case_ :					Any   ):
    self.data.append(snake_case_   )
    __a :  str						=  self.tail + 1
   def       lowerCAmelCase			(self :					Optional[int]   ):
    __a :  int						=  self.data[self.head]
    __a :  Union[str, Any]						=  self.head + 1
    return ret
   def       lowerCAmelCase			(self :					Union[str, Any]   ):
    return self.tail - self.head







   def       lowerCAmelCase			(self :					Union[str, Any]   ):
    print(self.data   )
    print('''**************'''   )
    print(self.data[self.head : self.tail]   )





class 		UpperCamelCase__  :
   def __init__(self :					List[str]					,				snake_case_ :					Any   ):
    __a :  List[str]						=  data
    __a :  MyNode | None						=  None
    __a :  MyNode | None						=  None
    __a :  int						=  1
   def       lowerCAmelCase			(self :					int   ):
    return self.data
   def       lowerCAmelCase			(self :					Dict   ):
    return self.left
   def       lowerCAmelCase			(self :					int   ):
    return self.right
   def       lowerCAmelCase			(self :					int   ):
    return self.height
   def       lowerCAmelCase			(self :					Optional[Any]					,				snake_case_ :					Any   ):
    __a :  Tuple						=  data
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					MyNode | None   ):
    __a :  Any						=  node
   def       lowerCAmelCase			(self :					Union[str, Any]					,				snake_case_ :					MyNode | None   ):
    __a :  List[str]						=  node







   def       lowerCAmelCase			(self :					Optional[int]					,				snake_case_ :					int   ):
    __a :  Union[str, Any]						=  height





def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode | None  ):
 if node is None:
  return 0
 return node.get_height()




def    __UpperCamelCase     (				lowerCAmelCase__							:				int  ,   lowerCAmelCase__							:				int  ):
 if a > b:
  return a
 return b




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 print('''left rotation node:'''  ,   node.get_data()  )
 __a :  str						=  node.get_left()
 assert ret is not None
 node.set_left(ret.get_right()  )
 ret.set_right(lowerCAmelCase__  )
 __a :  List[Any]						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 __a :  Union[str, Any]						=  my_max(get_height(ret.get_right()  )  ,   get_height(ret.get_left()  )  ) + 1
 ret.set_height(lowerCAmelCase__  )
 return ret




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 print('''right rotation node:'''  ,   node.get_data()  )
 __a :  List[Any]						=  node.get_right()
 assert ret is not None
 node.set_right(ret.get_left()  )
 ret.set_left(lowerCAmelCase__  )
 __a :  Union[str, Any]						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 __a :  List[str]						=  my_max(get_height(ret.get_right()  )  ,   get_height(ret.get_left()  )  ) + 1
 ret.set_height(lowerCAmelCase__  )
 return ret




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 __a :  Union[str, Any]						=  node.get_left()
 assert left_child is not None
 node.set_left(left_rotation(lowerCAmelCase__  )  )
 return right_rotation(lowerCAmelCase__  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 __a :  Optional[int]						=  node.get_right()
 assert right_child is not None
 node.set_right(right_rotation(lowerCAmelCase__  )  )
 return left_rotation(lowerCAmelCase__  )




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode | None  ,   lowerCAmelCase__							:				Any  ):
 if node is None:
  return MyNode(lowerCAmelCase__  )
 if data < node.get_data():
  node.set_left(insert_node(node.get_left()  ,   lowerCAmelCase__  )  )
  if (
      get_height(node.get_left()  ) - get_height(node.get_right()  ) == 2
  ):  # an unbalance detected
   __a :  Tuple						=  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 :  str						=  right_rotation(lowerCAmelCase__  )
   else:
    __a :  Dict						=  lr_rotation(lowerCAmelCase__  )
 else:
  node.set_right(insert_node(node.get_right()  ,   lowerCAmelCase__  )  )
  if get_height(node.get_right()  ) - get_height(node.get_left()  ) == 2:
   __a :  Dict						=  node.get_right()
   assert right_child is not None
   if data < right_child.get_data():
    __a :  str						=  rl_rotation(lowerCAmelCase__  )
   else:
    __a :  Tuple						=  left_rotation(lowerCAmelCase__  )
 __a :  Any						=  my_max(get_height(node.get_right()  )  ,   get_height(node.get_left()  )  ) + 1
 node.set_height(lowerCAmelCase__  )
 return node




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 while True:
  __a :  Union[str, Any]						=  root.get_right()
  if right_child is None:
   break
  __a :  str						=  right_child
 return root.get_data()




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ):
 while True:
  __a :  Optional[int]						=  root.get_left()
  if left_child is None:
   break
  __a :  int						=  left_child
 return root.get_data()




def    __UpperCamelCase     (				lowerCAmelCase__							:				MyNode  ,   lowerCAmelCase__							:				Any  ):
 __a :  Optional[Any]						=  root.get_left()
 __a :  List[str]						=  root.get_right()
 if root.get_data() == data:
  if left_child is not None and right_child is not None:
   __a :  str						=  get_left_most(lowerCAmelCase__  )
   root.set_data(lowerCAmelCase__  )
   root.set_right(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )
  elif left_child is not None:
   __a :  int						=  left_child
  elif right_child is not None:
   __a :  List[Any]						=  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(lowerCAmelCase__  ,   lowerCAmelCase__  )  )
 else:  # root.get_data() < data
  if right_child is None:
   return root
  else:
   root.set_right(del_node(lowerCAmelCase__  ,   lowerCAmelCase__  )  )

 if get_height(lowerCAmelCase__  ) - get_height(lowerCAmelCase__  ) == 2:
  assert right_child is not None
  if get_height(right_child.get_right()  ) > get_height(right_child.get_left()  ):
   __a :  List[Any]						=  left_rotation(lowerCAmelCase__  )
  else:
   __a :  Union[str, Any]						=  rl_rotation(lowerCAmelCase__  )
 elif get_height(lowerCAmelCase__  ) - get_height(lowerCAmelCase__  ) == -2:
  assert left_child is not None
  if get_height(left_child.get_left()  ) > get_height(left_child.get_right()  ):
   __a :  int						=  right_rotation(lowerCAmelCase__  )
  else:
   __a :  Tuple						=  lr_rotation(lowerCAmelCase__  )
 __a :  str						=  my_max(get_height(root.get_right()  )  ,   get_height(root.get_left()  )  ) + 1
 root.set_height(lowerCAmelCase__  )
 return root



class 		UpperCamelCase__  :
   def __init__(self :					Optional[Any]   ):
    __a :  MyNode | None						=  None
   def       lowerCAmelCase			(self :					List[Any]   ):
    return get_height(self.root   )
   def       lowerCAmelCase			(self :					Any					,				snake_case_ :					Any   ):
    print('''insert:''' + str(snake_case_   )   )
    __a :  List[Any]						=  insert_node(self.root					,				snake_case_   )
   def       lowerCAmelCase			(self :					Dict					,				snake_case_ :					Any   ):
    print('''delete:''' + str(snake_case_   )   )
    if self.root is None:
     print('''Tree is empty!'''   )
     return
    __a :  Union[str, Any]						=  del_node(self.root					,				snake_case_   )







   def __str__(self :					List[str]					,				):  # a level traversale, gives a more intuitive look on the tree
    __a :  Union[str, Any]						=  ''''''
    __a :  int						=  MyQueue()
    q.push(self.root   )
    __a :  List[str]						=  self.get_height()
    if layer == 0:
     return output
    __a :  List[Any]						=  0
    while not q.is_empty():
     __a :  List[str]						=  q.pop()
     __a :  Optional[int]						=  ''' ''' * int(math.pow(2					,				layer - 1   )   )
     output += space
     if node is None:
      output += "*"
      q.push(snake_case_   )
      q.push(snake_case_   )
     else:
      output += str(node.get_data()   )
      q.push(node.get_left()   )
      q.push(node.get_right()   )
     output += space
     __a :  int						=  cnt + 1
     for i in range(1_0_0   ):
      if cnt == math.pow(2					,				snake_case_   ) - 1:
       __a :  str						=  layer - 1
       if layer == 0:
        output += "\n*************************************"
        return output
       output += "\n"
       break
    output += "\n*************************************"
    return output





def    __UpperCamelCase     (				):
 import doctest

 doctest.testmod()


if __name__ == "__main__":
      _test()
      lowercase__       =AVLtree()
      lowercase__       =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))
