






from __future__ import annotations

import unittest
from collections.abc import Iterator


class  __lowercase :







     '''simple docstring'''




     def __init__(			self    :     int	,		UpperCamelCase_    :     int	,		UpperCamelCase_    :     Node | None			):


         """simple docstring"""



         __A             =		label
         __A             =		parent
         __A             =		None
         __A             =		None


class  __lowercase :







     '''simple docstring'''




     def __init__(			self    :     Optional[Any]			):


         """simple docstring"""



         __A             =		None




     def 						lowerCAmelCase_       (			self    :     Optional[Any]			):


         """simple docstring"""



         __A             =		None




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


         """simple docstring"""



         return self.root is None




     def 						lowerCAmelCase_       (			self    :     Optional[int]	,		UpperCamelCase_    :     int			):


         """simple docstring"""



         __A             =		self._put(self.root	,		UpperCamelCase_			)




     def 						lowerCAmelCase_       (			self    :     int	,		UpperCamelCase_    :     Node | None	,		UpperCamelCase_    :     int	,		UpperCamelCase_    :     Node | None = None			):


         """simple docstring"""



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

         return node




     def 						lowerCAmelCase_       (			self    :     int	,		UpperCamelCase_    :     int			):


         """simple docstring"""



         return self._search(self.root	,		UpperCamelCase_			)




     def 						lowerCAmelCase_       (			self    :     Union[str, Any]	,		UpperCamelCase_    :     Node | None	,		UpperCamelCase_    :     int			):


         """simple docstring"""



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

         return node




     def 						lowerCAmelCase_       (			self    :     Dict	,		UpperCamelCase_    :     int			):


         """simple docstring"""



         __A             =		self.search(UpperCamelCase_			)
         if node.right and node.left:
             __A             =		self._get_lowest_node(node.right			)
             __A             =		node.left
             __A             =		node.right
             __A             =		lowest_node
             if node.right:
                 __A             =		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 						lowerCAmelCase_       (			self    :     Optional[Any]	,		UpperCamelCase_    :     Node	,		UpperCamelCase_    :     Node | None			):


         """simple docstring"""



         if new_children:
             __A             =		node.parent

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




     def 						lowerCAmelCase_       (			self    :     str	,		UpperCamelCase_    :     Node			):


         """simple docstring"""



         if node.left:
             __A             =		self._get_lowest_node(node.left			)
         else:
             __A             =		node
             self._reassign_nodes(UpperCamelCase_	,		node.right			)

         return lowest_node




     def 						lowerCAmelCase_       (			self    :     Union[str, Any]	,		UpperCamelCase_    :     int			):


         """simple docstring"""



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




     def 						lowerCAmelCase_       (			self    :     int			):


         """simple docstring"""



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

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

         return node.label




     def 						lowerCAmelCase_       (			self    :     Any			):


         """simple docstring"""



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

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

         return node.label




     def 						lowerCAmelCase_       (			self    :     Tuple			):


         """simple docstring"""



         return self._inorder_traversal(self.root			)




     def 						lowerCAmelCase_       (			self    :     List[Any]	,		UpperCamelCase_    :     Node | None			):


         """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    :     List[Any]			):


         """simple docstring"""



         return self._preorder_traversal(self.root			)





     def 						lowerCAmelCase_       (			self    :     int	,		UpperCamelCase_    :     Node | None			):


         """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					):







     '''simple docstring'''




     @staticmethod
     def 						lowerCAmelCase_       (			):


         """simple docstring"""



         __A             =		BinarySearchTree()
         t.put(8			)
         t.put(3			)
         t.put(6			)
         t.put(1			)
         t.put(10			)
         t.put(14			)
         t.put(13			)
         t.put(4			)
         t.put(7			)
         t.put(5			)

         return t




     def 						lowerCAmelCase_       (			self    :     List[Any]			):


         """simple docstring"""



         __A             =		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 						lowerCAmelCase_       (			self    :     Optional[Any]			):


         """simple docstring"""



         __A             =		self._get_binary_search_tree()

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

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

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




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


         """simple docstring"""



         __A             =		self._get_binary_search_tree()

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

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

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

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

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




     def 						lowerCAmelCase_       (			self    :     Tuple			):


         """simple docstring"""



         __A             =		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    :     int			):


         """simple docstring"""



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




     def 						lowerCAmelCase_       (			self    :     str			):


         """simple docstring"""



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

         t.empty()
         assert t.is_empty()




     def 						lowerCAmelCase_       (			self    :     Tuple			):


         """simple docstring"""



         __A             =		self._get_binary_search_tree()

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




     def 						lowerCAmelCase_       (			self    :     Optional[int]			):


         """simple docstring"""



         __A             =		self._get_binary_search_tree()

         assert t.get_max_label() == 14

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




     def 						lowerCAmelCase_       (			self    :     int			):


         """simple docstring"""



         __A             =		self._get_binary_search_tree()

         assert t.get_min_label() == 1

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




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


         """simple docstring"""



         __A             =		self._get_binary_search_tree()

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





     def 						lowerCAmelCase_       (			self    :     str			):


         """simple docstring"""



         __A             =		self._get_binary_search_tree()

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



def      _SCREAMING_SNAKE_CASE  (	)  -> None:





    """simple docstring"""

    __A             =		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      )

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

    print("""Label 6 exists:"""     ,			t.exists(6      )      )
    print("""Label 13 exists:"""     ,			t.exists(1_3      )      )
    print("""Label -1 exists:"""     ,			t.exists(-1      )      )
    print("""Label 12 exists:"""     ,			t.exists(1_2      )      )

    # Prints all the elements of the list in inorder traversal
    __A             =		[i.label for i in t.inorder_traversal()]
    print("""Inorder traversal:"""     ,			__lowercase      )

    # Prints all the elements of the list in preorder traversal
    __A             =		[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(1_3      )
    t.remove(1_0      )
    t.remove(8      )
    t.remove(3      )
    t.remove(6      )
    t.remove(1_4      )

    # Prints all the elements of the list in inorder traversal after delete
    __A             =		[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
    __A             =		[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 importlib
import inspect
from functools import wraps
from typing import TYPE_CHECKING, Optional, Union

from .download.streaming_download_manager import (
    xbasename,
    xdirname,
    xet_parse,
    xexists,
    xgetsize,
    xglob,
    xgzip_open,
    xisdir,
    xisfile,
    xjoin,
    xlistdir,
    xnumpy_load,
    xopen,
    xpandas_read_csv,
    xpandas_read_excel,
    xPath,
    xrelpath,
    xsio_loadmat,
    xsplit,
    xsplitext,
    xwalk,
    xxml_dom_minidom_parse,
)
from .utils.logging import get_logger
from .utils.patching import patch_submodule
from .utils.py_utils import get_imports


__a :    List[str]								=				get_logger(__name__)


if TYPE_CHECKING:
  from .builder import DatasetBuilder



def      _SCREAMING_SNAKE_CASE  (	__lowercase				:     Dict     ,			__lowercase				:     Optional[Union[str, bool]] = None      )  -> List[str]:





    """simple docstring"""

    __A             =		importlib.import_module(__lowercase      )

    # TODO(QL): always update the module to add subsequent new authentication
    if hasattr(__lowercase     ,			"""_patched_for_streaming"""      ) and module._patched_for_streaming:
        return

    def wrap_auth(__lowercase				:     int      ):
        @wraps(__lowercase      )
        def wrapper(*__lowercase				:     Tuple     ,			**__lowercase				:     List[str]      ):
            return function(*__lowercase     ,			use_auth_token=__lowercase     ,			**__lowercase      )

        __A             =		"""wrap_auth"""
        return wrapper

    # open files in a streaming fashion
    patch_submodule(__lowercase     ,			"""open"""     ,			wrap_auth(__lowercase      )      ).start()
    patch_submodule(__lowercase     ,			"""os.listdir"""     ,			wrap_auth(__lowercase      )      ).start()
    patch_submodule(__lowercase     ,			"""os.walk"""     ,			wrap_auth(__lowercase      )      ).start()
    patch_submodule(__lowercase     ,			"""glob.glob"""     ,			wrap_auth(__lowercase      )      ).start()
    # allow to navigate in remote zip files
    patch_submodule(__lowercase     ,			"""os.path.join"""     ,			__lowercase      ).start()
    patch_submodule(__lowercase     ,			"""os.path.dirname"""     ,			__lowercase      ).start()
    patch_submodule(__lowercase     ,			"""os.path.basename"""     ,			__lowercase      ).start()
    patch_submodule(__lowercase     ,			"""os.path.relpath"""     ,			__lowercase      ).start()
    patch_submodule(__lowercase     ,			"""os.path.split"""     ,			__lowercase      ).start()
    patch_submodule(__lowercase     ,			"""os.path.splitext"""     ,			__lowercase      ).start()
    # allow checks on paths
    patch_submodule(__lowercase     ,			"""os.path.exists"""     ,			wrap_auth(__lowercase      )      ).start()
    patch_submodule(__lowercase     ,			"""os.path.isdir"""     ,			wrap_auth(__lowercase      )      ).start()
    patch_submodule(__lowercase     ,			"""os.path.isfile"""     ,			wrap_auth(__lowercase      )      ).start()
    patch_submodule(__lowercase     ,			"""os.path.getsize"""     ,			wrap_auth(__lowercase      )      ).start()
    patch_submodule(__lowercase     ,			"""pathlib.Path"""     ,			__lowercase      ).start()
    # file readers
    patch_submodule(__lowercase     ,			"""gzip.open"""     ,			wrap_auth(__lowercase      )      ).start()
    patch_submodule(__lowercase     ,			"""numpy.load"""     ,			wrap_auth(__lowercase      )      ).start()
    patch_submodule(__lowercase     ,			"""pandas.read_csv"""     ,			wrap_auth(__lowercase      )     ,			attrs=["""__version__"""]      ).start()
    patch_submodule(__lowercase     ,			"""pandas.read_excel"""     ,			wrap_auth(__lowercase      )     ,			attrs=["""__version__"""]      ).start()
    patch_submodule(__lowercase     ,			"""scipy.io.loadmat"""     ,			wrap_auth(__lowercase      )     ,			attrs=["""__version__"""]      ).start()
    patch_submodule(__lowercase     ,			"""xml.etree.ElementTree.parse"""     ,			wrap_auth(__lowercase      )      ).start()
    patch_submodule(__lowercase     ,			"""xml.dom.minidom.parse"""     ,			wrap_auth(__lowercase      )      ).start()
    __A             =		True






def      _SCREAMING_SNAKE_CASE  (	__lowercase				:     "DatasetBuilder"      )  -> Union[str, Any]:





    """simple docstring"""

    extend_module_for_streaming(builder.__module__     ,			use_auth_token=builder.use_auth_token      )
    # if needed, we also have to extend additional internal imports (like wmt14 -> wmt_utils)
    if not builder.__module__.startswith("""datasets."""      ):  # check that it's not a packaged builder like csv
        for imports in get_imports(inspect.getfile(builder.__class__      )      ):
            if imports[0] == "internal":
                __A             =		imports[1]
                __A             =		""".""".join(builder.__module__.split("""."""      )[:-1] + [internal_import_name]      )
                extend_module_for_streaming(__lowercase     ,			use_auth_token=builder.use_auth_token      )

    # builders can inherit from other builders that might use streaming functionality
    # (for example, ImageFolder and AudioFolder inherit from FolderBuilder which implements examples generation)
    # but these parents builders are not patched automatically as they are not instantiated, so we patch them here
    from .builder import DatasetBuilder

    __A             =		[
        cls.__module__
        for cls in type(__lowercase      ).__mro__[1:]  # make sure it's not the same module we've already patched
        if issubclass(cls     ,			__lowercase      ) and cls.__module__ != DatasetBuilder.__module__
    ]  # check it's not a standard builder from datasets.builder
    for module in parent_builder_modules:
        extend_module_for_streaming(__lowercase     ,			use_auth_token=builder.use_auth_token      )




