



from __future__ import annotations

import unittest
from collections.abc import Iterator
class       _lowerCAmelCase :






			"""simple docstring"""





			def __init__(					self						:							Optional[Any]      ,  lowercase						:							Tuple      ,  lowercase						:							Tuple )    ->       None:
									"""simple docstring"""







									__lowercase											=					label
									__lowercase											=					parent
									__lowercase											=					None
									__lowercase											=					None





class       _lowerCAmelCase :






			"""simple docstring"""





			def __init__(					self						:							Optional[Any] )    ->       None:
									"""simple docstring"""







									__lowercase											=					None





			def 		snake_case__      (					self						:							List[str] )    ->       None:
									"""simple docstring"""







									__lowercase											=					None





			def 		snake_case__      (					self						:							Optional[int] )    ->       bool:
									"""simple docstring"""







									return self.root is None





			def 		snake_case__      (					self						:							int      ,  lowercase						:							Optional[Any] )    ->       None:
									"""simple docstring"""







									__lowercase											=					self._put(self.root      ,  _UpperCAmelCase )





			def 		snake_case__      (					self						:							str      ,  lowercase						:							int      ,  lowercase						:							int      ,  lowercase						:							int = None )    ->       Node:
									"""simple docstring"""







									if node is None:
															__lowercase											=					Node(_UpperCAmelCase      ,  _UpperCAmelCase )
									else:
															if label < node.label:
																					__lowercase											=					self._put(node.left      ,  _UpperCAmelCase      ,  _UpperCAmelCase )
															elif label > node.label:
																					__lowercase											=					self._put(node.right      ,  _UpperCAmelCase      ,  _UpperCAmelCase )
															else:
																					__lowercase											=					F"Node with label {label} already exists"
																					raise Exception(_UpperCAmelCase )

									return node





			def 		snake_case__      (					self						:							Any      ,  lowercase						:							Tuple )    ->       Node:
									"""simple docstring"""







									return self._search(self.root      ,  _UpperCAmelCase )





			def 		snake_case__      (					self						:							str      ,  lowercase						:							str      ,  lowercase						:							Any )    ->       Node:
									"""simple docstring"""







									if node is None:
															__lowercase											=					F"Node with label {label} does not exist"
															raise Exception(_UpperCAmelCase )
									else:
															if label < node.label:
																					__lowercase											=					self._search(node.left      ,  _UpperCAmelCase )
															elif label > node.label:
																					__lowercase											=					self._search(node.right      ,  _UpperCAmelCase )

									return node





			def 		snake_case__      (					self						:							Optional[int]      ,  lowercase						:							Optional[Any] )    ->       None:
									"""simple docstring"""







									__lowercase											=					self.search(_UpperCAmelCase )
									if node.right and node.left:
															__lowercase											=					self._get_lowest_node(node.right )
															__lowercase											=					node.left
															__lowercase											=					node.right
															__lowercase											=					lowest_node
															if node.right:
																					__lowercase											=					lowest_node
															self._reassign_nodes(_UpperCAmelCase      ,  _UpperCAmelCase )
									elif not node.right and node.left:
															self._reassign_nodes(_UpperCAmelCase      ,  node.left )
									elif node.right and not node.left:
															self._reassign_nodes(_UpperCAmelCase      ,  node.right )
									else:
															self._reassign_nodes(_UpperCAmelCase      ,  _UpperCAmelCase )





			def 		snake_case__      (					self						:							List[str]      ,  lowercase						:							Optional[Any]      ,  lowercase						:							Tuple )    ->       None:
									"""simple docstring"""







									if new_children:
															__lowercase											=					node.parent

									if node.parent:
															if node.parent.right == node:
																					__lowercase											=					new_children
															else:
																					__lowercase											=					new_children
									else:
															__lowercase											=					new_children





			def 		snake_case__      (					self						:							Any      ,  lowercase						:							Optional[Any] )    ->       Node:
									"""simple docstring"""







									if node.left:
															__lowercase											=					self._get_lowest_node(node.left )
									else:
															__lowercase											=					node
															self._reassign_nodes(_UpperCAmelCase      ,  node.right )

									return lowest_node





			def 		snake_case__      (					self						:							str      ,  lowercase						:							List[str] )    ->       bool:
									"""simple docstring"""







									try:
															self.search(_UpperCAmelCase )
															return True
									except Exception:
															return False





			def 		snake_case__      (					self						:							Any )    ->       int:
									"""simple docstring"""







									if self.root is None:
															raise Exception("""Binary search tree is empty""" )

									__lowercase											=					self.root
									while node.right is not None:
															__lowercase											=					node.right

									return node.label





			def 		snake_case__      (					self						:							Dict )    ->       int:
									"""simple docstring"""







									if self.root is None:
															raise Exception("""Binary search tree is empty""" )

									__lowercase											=					self.root
									while node.left is not None:
															__lowercase											=					node.left

									return node.label





			def 		snake_case__      (					self						:							int )    ->       Iterator[Node]:
									"""simple docstring"""







									return self._inorder_traversal(self.root )





			def 		snake_case__      (					self						:							List[Any]      ,  lowercase						:							int )    ->       Iterator[Node]:
									"""simple docstring"""







									if node is not None:
															yield from self._inorder_traversal(node.left )
															yield node
															yield from self._inorder_traversal(node.right )





			def 		snake_case__      (					self						:							Any )    ->       Iterator[Node]:
									"""simple docstring"""







									return self._preorder_traversal(self.root )







			def 		snake_case__      (					self						:							str      ,  lowercase						:							Dict )    ->       Iterator[Node]:
									"""simple docstring"""







									if node is not None:
															yield node
															yield from self._preorder_traversal(node.left )
															yield from self._preorder_traversal(node.right )





class       _lowerCAmelCase (			unittest.TestCase      ):






			"""simple docstring"""





			@staticmethod
			def 		snake_case__      (					)    ->       BinarySearchTree:
									"""simple docstring"""







									__lowercase											=					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 		snake_case__      (					self						:							Union[str, Any] )    ->       None:
									"""simple docstring"""







									__lowercase											=					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(_UpperCAmelCase ):  # noqa: B017
															t.put(1 )





			def 		snake_case__      (					self						:							str )    ->       None:
									"""simple docstring"""







									__lowercase											=					self._get_binary_search_tree()

									__lowercase											=					t.search(6 )
									assert node.label == 6

									__lowercase											=					t.search(13 )
									assert node.label == 13

									with self.assertRaises(_UpperCAmelCase ):  # noqa: B017
															t.search(2 )





			def 		snake_case__      (					self						:							List[str] )    ->       None:
									"""simple docstring"""







									__lowercase											=					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 		snake_case__      (					self						:							int )    ->       None:
									"""simple docstring"""







									__lowercase											=					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 		snake_case__      (					self						:							Dict )    ->       None:
									"""simple docstring"""







									__lowercase											=					self._get_binary_search_tree()
									t.empty()
									assert t.root is None





			def 		snake_case__      (					self						:							str )    ->       None:
									"""simple docstring"""







									__lowercase											=					self._get_binary_search_tree()
									assert not t.is_empty()

									t.empty()
									assert t.is_empty()





			def 		snake_case__      (					self						:							str )    ->       None:
									"""simple docstring"""







									__lowercase											=					self._get_binary_search_tree()

									assert t.exists(6 )
									assert not t.exists(-1 )





			def 		snake_case__      (					self						:							str )    ->       None:
									"""simple docstring"""







									__lowercase											=					self._get_binary_search_tree()

									assert t.get_max_label() == 14

									t.empty()
									with self.assertRaises(_UpperCAmelCase ):  # noqa: B017
															t.get_max_label()





			def 		snake_case__      (					self						:							str )    ->       None:
									"""simple docstring"""







									__lowercase											=					self._get_binary_search_tree()

									assert t.get_min_label() == 1

									t.empty()
									with self.assertRaises(_UpperCAmelCase ):  # noqa: B017
															t.get_min_label()





			def 		snake_case__      (					self						:							Dict )    ->       None:
									"""simple docstring"""







									__lowercase											=					self._get_binary_search_tree()

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







			def 		snake_case__      (					self						:							List[Any] )    ->       None:
									"""simple docstring"""







									__lowercase											=					self._get_binary_search_tree()

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






def 			UpperCAmelCase__     (     )			->   str:
						__lowercase											=					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(
						    """
            8
           / \\
          3   10
         / \\    \\
        1   6    14
           / \\   /
          4   7 13
           \\
            5
        """ )

						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											=					[i.label for i in t.inorder_traversal()]
						print("""Inorder traversal:"""    ,							lowercase__ )

						# Prints all the elements of the list in preorder traversal
						__lowercase											=					[i.label for i in t.preorder_traversal()]
						print("""Preorder traversal:"""    ,							lowercase__ )

						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(
						    """
          4
         / \\
        1   7
             \\
              5
        """ )
						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											=					[i.label for i in t.inorder_traversal()]
						print("""Inorder traversal after delete:"""    ,							lowercase__ )

						# Prints all the elements of the list in preorder traversal after delete
						__lowercase											=					[i.label for i in t.preorder_traversal()]
						print("""Preorder traversal after delete:"""    ,							lowercase__ )

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


if __name__ == "__main__":
			binary_search_tree_example()













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


if is_torch_available():
   import torch

if is_vision_available():
   from PIL import Image

   from transformers import BlipImageProcessor


class 		lowerCAmelCase_				(  unittest.TestCase ):





     def __init__(	self							, _UpperCAmelCase							, _UpperCAmelCase=7							, _UpperCAmelCase=3							, _UpperCAmelCase=18							, _UpperCAmelCase=30							, _UpperCAmelCase=400							, _UpperCAmelCase=True							, _UpperCAmelCase=None							, _UpperCAmelCase=True							, _UpperCAmelCase=False							, _UpperCAmelCase=[0.48145466, 0.4578275, 0.40821073]							, _UpperCAmelCase=[0.26862954, 0.26130258, 0.27577711]							, _UpperCAmelCase=True							, )		->				List[str]:
        lowerCamelCase									=size if size is not None else {"""height""": 20, """width""": 20}
        lowerCamelCase									=parent
        lowerCamelCase									=batch_size
        lowerCamelCase									=num_channels
        lowerCamelCase									=image_size
        lowerCamelCase									=min_resolution
        lowerCamelCase									=max_resolution
        lowerCamelCase									=do_resize
        lowerCamelCase									=size
        lowerCamelCase									=do_normalize
        lowerCamelCase									=image_mean
        lowerCamelCase									=image_std
        lowerCamelCase									=do_pad
        lowerCamelCase									=do_convert_rgb





     def 						lowerCamelCase							(	self  )		->				str:
        return {
            "do_resize": self.do_resize,
            "size": self.size,
            "do_normalize": self.do_normalize,
            "image_mean": self.image_mean,
            "image_std": self.image_std,
            "do_convert_rgb": self.do_convert_rgb,
            "do_pad": self.do_pad,
        }





     def 						lowerCamelCase							(	self							, _UpperCAmelCase=False							, _UpperCAmelCase=False							, _UpperCAmelCase=False  )		->				Optional[int]:
        assert not (numpify and torchify), "You cannot specify both numpy and PyTorch tensors at the same time"

        if equal_resolution:
           lowerCamelCase									=[]
           for i in range(self.batch_size  ):
              image_inputs.append(
                  np.random.randint(
                      255							, size=(self.num_channels, self.max_resolution, self.max_resolution)							, dtype=np.uinta  )  )
        else:
           lowerCamelCase									=[]
           for i in range(self.batch_size  ):
              lowerCamelCase				,       lowerCamelCase									=np.random.choice(np.arange(self.min_resolution							, self.max_resolution  )							, 2  )
              image_inputs.append(np.random.randint(255							, size=(self.num_channels, width, height)							, dtype=np.uinta  )  )

        if not numpify and not torchify:
           # PIL expects the channel dimension as last dimension
           lowerCamelCase									=[Image.fromarray(np.moveaxis(_UpperCAmelCase							, 0							, -1  )  ) for x in image_inputs]

        if torchify:
           lowerCamelCase									=[torch.from_numpy(_UpperCAmelCase  ) for x in image_inputs]

        return image_inputs




@require_torch
@require_vision
class 		lowerCAmelCase_				(  UpperCamelCase				,     unittest.TestCase ):
     __lowerCamelCase       :    str 	=     BlipImageProcessor if is_vision_available() else None





     def 						lowerCamelCase							(	self  )		->				Dict:
        lowerCamelCase									=BlipImageProcessingTester(self  )





     @property
     def 						lowerCamelCase							(	self  )		->				Optional[int]:
        return self.image_processor_tester.prepare_image_processor_dict()





     def 						lowerCamelCase							(	self  )		->				Union[str, Any]:
        lowerCamelCase									=self.image_processing_class(**self.image_processor_dict  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """do_resize"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """size"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """do_normalize"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """image_mean"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """image_std"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """do_convert_rgb"""  )  )





     def 						lowerCamelCase							(	self  )		->				Union[str, Any]:
        pass





     def 						lowerCamelCase							(	self  )		->				int:
        # Initialize image_processor
        lowerCamelCase									=self.image_processing_class(**self.image_processor_dict  )
        # create random PIL images
        lowerCamelCase									=self.image_processor_tester.prepare_inputs(equal_resolution=_UpperCAmelCase  )
        for image in image_inputs:
           self.assertIsInstance(_UpperCAmelCase							, Image.Image  )

        # Test not batched input
        lowerCamelCase									=image_processor(image_inputs[0]							, return_tensors="""pt"""  ).pixel_values
        self.assertEqual(
            encoded_images.shape							, (
                1,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.size["""height"""],
                self.image_processor_tester.size["""width"""],
            )							, )

        # Test batched
        lowerCamelCase									=image_processor(_UpperCAmelCase							, return_tensors="""pt"""  ).pixel_values
        self.assertEqual(
            encoded_images.shape							, (
                self.image_processor_tester.batch_size,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.size["""height"""],
                self.image_processor_tester.size["""width"""],
            )							, )





     def 						lowerCamelCase							(	self  )		->				Union[str, Any]:
        # Initialize image_processor
        lowerCamelCase									=self.image_processing_class(**self.image_processor_dict  )
        # create random numpy tensors
        lowerCamelCase									=self.image_processor_tester.prepare_inputs(equal_resolution=_UpperCAmelCase							, numpify=_UpperCAmelCase  )
        for image in image_inputs:
           self.assertIsInstance(_UpperCAmelCase							, np.ndarray  )

        # Test not batched input
        lowerCamelCase									=image_processor(image_inputs[0]							, return_tensors="""pt"""  ).pixel_values
        self.assertEqual(
            encoded_images.shape							, (
                1,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.size["""height"""],
                self.image_processor_tester.size["""width"""],
            )							, )

        # Test batched
        lowerCamelCase									=image_processor(_UpperCAmelCase							, return_tensors="""pt"""  ).pixel_values
        self.assertEqual(
            encoded_images.shape							, (
                self.image_processor_tester.batch_size,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.size["""height"""],
                self.image_processor_tester.size["""width"""],
            )							, )





     def 						lowerCamelCase							(	self  )		->				Optional[Any]:
        # Initialize image_processor
        lowerCamelCase									=self.image_processing_class(**self.image_processor_dict  )
        # create random PyTorch tensors
        lowerCamelCase									=self.image_processor_tester.prepare_inputs(equal_resolution=_UpperCAmelCase							, torchify=_UpperCAmelCase  )
        for image in image_inputs:
           self.assertIsInstance(_UpperCAmelCase							, torch.Tensor  )

        # Test not batched input
        lowerCamelCase									=image_processor(image_inputs[0]							, return_tensors="""pt"""  ).pixel_values
        self.assertEqual(
            encoded_images.shape							, (
                1,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.size["""height"""],
                self.image_processor_tester.size["""width"""],
            )							, )

        # Test batched
        lowerCamelCase									=image_processor(_UpperCAmelCase							, return_tensors="""pt"""  ).pixel_values
        self.assertEqual(
            encoded_images.shape							, (
                self.image_processor_tester.batch_size,
                self.image_processor_tester.num_channels,
                self.image_processor_tester.size["""height"""],
                self.image_processor_tester.size["""width"""],
            )							, )




@require_torch
@require_vision
class 		lowerCAmelCase_				(  UpperCamelCase				,     unittest.TestCase ):
     __lowerCamelCase       :    Any 	=     BlipImageProcessor if is_vision_available() else None





     def 						lowerCamelCase							(	self  )		->				Optional[int]:
        lowerCamelCase									=BlipImageProcessingTester(self							, num_channels=4  )
        lowerCamelCase									=3





     @property
     def 						lowerCamelCase							(	self  )		->				Any:
        return self.image_processor_tester.prepare_image_processor_dict()





     def 						lowerCamelCase							(	self  )		->				List[str]:
        lowerCamelCase									=self.image_processing_class(**self.image_processor_dict  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """do_resize"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """size"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """do_normalize"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """image_mean"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """image_std"""  )  )
        self.assertTrue(hasattr(_UpperCAmelCase							, """do_convert_rgb"""  )  )





     def 						lowerCamelCase							(	self  )		->				Optional[int]:
        pass





     def 						lowerCamelCase							(	self  )		->				List[Any]:
        # Initialize image_processor
        lowerCamelCase									=self.image_processing_class(**self.image_processor_dict  )
        # create random PIL images
        lowerCamelCase									=self.image_processor_tester.prepare_inputs(equal_resolution=_UpperCAmelCase  )
        for image in image_inputs:
           self.assertIsInstance(_UpperCAmelCase							, Image.Image  )

        # Test not batched input
        lowerCamelCase									=image_processor(image_inputs[0]							, return_tensors="""pt"""  ).pixel_values
        self.assertEqual(
            encoded_images.shape							, (
                1,
                self.expected_encoded_image_num_channels,
                self.image_processor_tester.size["""height"""],
                self.image_processor_tester.size["""width"""],
            )							, )

        # Test batched
        lowerCamelCase									=image_processor(_UpperCAmelCase							, return_tensors="""pt"""  ).pixel_values
        self.assertEqual(
            encoded_images.shape							, (
                self.image_processor_tester.batch_size,
                self.expected_encoded_image_num_channels,
                self.image_processor_tester.size["""height"""],
                self.image_processor_tester.size["""width"""],
            )							, )