from __future__ import annotations

import unittest
from collections.abc import Iterator
class 							lowercase_    :







    def __init__(	self       ,     UpperCamelCase__       ,     UpperCamelCase__				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					label
     UpperCAmelCase_				       =					parent
     UpperCAmelCase_				       =					None
     UpperCAmelCase_				       =					None


class 							lowercase_    :







    def __init__(	self				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					None







    def   lowerCamelCase_    (	self				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					None







    def   lowerCamelCase_    (	self				)				->       bool:





     """simple docstring"""

     return self.root is None







    def   lowerCamelCase_    (	self       ,     UpperCamelCase__				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					self._put(self.root       ,     lowerCAmelCase__				)







    def   lowerCamelCase_    (	self       ,     UpperCamelCase__       ,     UpperCamelCase__       ,     UpperCamelCase__ = None				)				->       Node:





     """simple docstring"""

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

     return node







    def   lowerCamelCase_    (	self       ,     UpperCamelCase__				)				->       Node:





     """simple docstring"""

     return self._search(self.root       ,     lowerCAmelCase__				)







    def   lowerCamelCase_    (	self       ,     UpperCamelCase__       ,     UpperCamelCase__				)				->       Node:





     """simple docstring"""

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

     return node







    def   lowerCamelCase_    (	self       ,     UpperCamelCase__				)				->       None:





     """simple docstring"""

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







    def   lowerCamelCase_    (	self       ,     UpperCamelCase__       ,     UpperCamelCase__				)				->       None:





     """simple docstring"""

     if new_children:
      UpperCAmelCase_				       =					node.parent

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







    def   lowerCamelCase_    (	self       ,     UpperCamelCase__				)				->       Node:





     """simple docstring"""

     if node.left:
      UpperCAmelCase_				       =					self._get_lowest_node(node.left				)
     else:
      UpperCAmelCase_				       =					node
      self._reassign_nodes(lowerCAmelCase__       ,     node.right				)

     return lowest_node







    def   lowerCamelCase_    (	self       ,     UpperCamelCase__				)				->       bool:





     """simple docstring"""

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







    def   lowerCamelCase_    (	self				)				->       int:





     """simple docstring"""

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

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

     return node.label







    def   lowerCamelCase_    (	self				)				->       int:





     """simple docstring"""

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

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

     return node.label







    def   lowerCamelCase_    (	self				)				->       Iterator[Node]:





     """simple docstring"""

     return self._inorder_traversal(self.root				)







    def   lowerCamelCase_    (	self       ,     UpperCamelCase__				)				->       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   lowerCamelCase_    (	self				)				->       Iterator[Node]:





     """simple docstring"""

     return self._preorder_traversal(self.root				)







    def   lowerCamelCase_    (	self       ,     UpperCamelCase__				)				->       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 							lowercase_    (     unittest.TestCase						):







    @staticmethod
    def   lowerCamelCase_    (	)				->       BinarySearchTree:





     """simple docstring"""

     UpperCAmelCase_				       =					BinarySearchTree()
     t.put(8				)
     t.put(3				)
     t.put(6				)
     t.put(1				)
     t.put(1_0				)
     t.put(1_4				)
     t.put(1_3				)
     t.put(4				)
     t.put(7				)
     t.put(5				)

     return t







    def   lowerCamelCase_    (	self				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					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(1_0				)
     assert t.root.right is not None
     assert t.root.right.parent == t.root
     assert t.root.right.label == 1_0

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







    def   lowerCamelCase_    (	self				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					self._get_binary_search_tree()

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

     UpperCAmelCase_				       =					t.search(1_3				)
     assert node.label == 1_3

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







    def   lowerCamelCase_    (	self				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					self._get_binary_search_tree()

     t.remove(1_3				)
     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:





     """simple docstring"""

     UpperCAmelCase_				       =					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:





     """simple docstring"""

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







    def   lowerCamelCase_    (	self				)				->       None:





     """simple docstring"""

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

     t.empty()
     assert t.is_empty()







    def   lowerCamelCase_    (	self				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					self._get_binary_search_tree()

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







    def   lowerCamelCase_    (	self				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					self._get_binary_search_tree()

     assert t.get_max_label() == 1_4

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







    def   lowerCamelCase_    (	self				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					self._get_binary_search_tree()

     assert t.get_min_label() == 1

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







    def   lowerCamelCase_    (	self				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					self._get_binary_search_tree()

     UpperCAmelCase_				       =					[i.label for i in t.inorder_traversal()]
     assert inorder_traversal_nodes == [1, 3, 4, 5, 6, 7, 8, 1_0, 1_3, 1_4]







    def   lowerCamelCase_    (	self				)				->       None:





     """simple docstring"""

     UpperCAmelCase_				       =					self._get_binary_search_tree()

     UpperCAmelCase_				       =					[i.label for i in t.preorder_traversal()]
     assert preorder_traversal_nodes == [8, 3, 1, 6, 4, 5, 7, 1_0, 1_4, 1_3]



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

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

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

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

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


if __name__ == "__main__":
      binary_search_tree_example()

'''simple docstring'''

from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available, is_vision_available


__snake_case       :   int  		=    {
    '''configuration_videomae''': ['''VIDEOMAE_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''VideoMAEConfig'''],
}

try:
      if not is_torch_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __snake_case       :   Optional[Any]  		=    [
          '''VIDEOMAE_PRETRAINED_MODEL_ARCHIVE_LIST''',
          '''VideoMAEForPreTraining''',
          '''VideoMAEModel''',
          '''VideoMAEPreTrainedModel''',
          '''VideoMAEForVideoClassification''',
      ]

try:
      if not is_vision_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __snake_case       :   str  		=    ['''VideoMAEFeatureExtractor''']
      __snake_case       :   Any  		=    ['''VideoMAEImageProcessor''']

if TYPE_CHECKING:
      from .configuration_videomae import VIDEOMAE_PRETRAINED_CONFIG_ARCHIVE_MAP, VideoMAEConfig

      try:
            if not is_torch_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_videomae import (
                VIDEOMAE_PRETRAINED_MODEL_ARCHIVE_LIST,
                VideoMAEForPreTraining,
                VideoMAEForVideoClassification,
                VideoMAEModel,
                VideoMAEPreTrainedModel,
            )

      try:
            if not is_vision_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .feature_extraction_videomae import VideoMAEFeatureExtractor
            from .image_processing_videomae import VideoMAEImageProcessor

else:
      import sys

      __snake_case       :   List[str]  		=    _LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)
