
"""simple docstring"""






from typing import TYPE_CHECKING

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


UpperCAmelCase          =							{
    """configuration_splinter""": ["""SPLINTER_PRETRAINED_CONFIG_ARCHIVE_MAP""", """SplinterConfig"""],
    """tokenization_splinter""": ["""SplinterTokenizer"""],
}

try:
					if not is_tokenizers_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					UpperCAmelCase          =							["""SplinterTokenizerFast"""]

try:
					if not is_torch_available():
										raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
					pass
else:
					UpperCAmelCase          =							[
					    """SPLINTER_PRETRAINED_MODEL_ARCHIVE_LIST""",
					    """SplinterForQuestionAnswering""",
					    """SplinterForPreTraining""",
					    """SplinterLayer""",
					    """SplinterModel""",
					    """SplinterPreTrainedModel""",
					]


if TYPE_CHECKING:
					from .configuration_splinter import SPLINTER_PRETRAINED_CONFIG_ARCHIVE_MAP, SplinterConfig
					from .tokenization_splinter import SplinterTokenizer

					try:
										if not is_tokenizers_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .tokenization_splinter_fast import SplinterTokenizerFast

					try:
										if not is_torch_available():
															raise OptionalDependencyNotAvailable()
					except OptionalDependencyNotAvailable:
										pass
					else:
										from .modeling_splinter import (
										    SPLINTER_PRETRAINED_MODEL_ARCHIVE_LIST,
										    SplinterForPreTraining,
										    SplinterForQuestionAnswering,
										    SplinterLayer,
										    SplinterModel,
										    SplinterPreTrainedModel,
										)


else:
					import sys

					UpperCAmelCase          =							_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)




"""simple docstring"""






from __future__ import annotations

import unittest
from collections.abc import Iterator



class  lowercase				:






			def __init__(self     :  Optional[int]			,SCREAMING_SNAKE_CASE_     :  int			,SCREAMING_SNAKE_CASE_     :  Node | None )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     label
				lowerCAmelCase				       =     parent
				lowerCAmelCase				       =     None
				lowerCAmelCase				       =     None





class  lowercase				:






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





				"""simple docstring"""


				lowerCAmelCase				       =     None






			def 				UpperCAmelCase       (self     :  Optional[int] )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     None






			def 				UpperCAmelCase       (self     :  Tuple )					->  bool:





				"""simple docstring"""


				return self.root is None






			def 				UpperCAmelCase       (self     :  Union[str, Any]			,SCREAMING_SNAKE_CASE_     :  int )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     self._put(self.root			,SCREAMING_SNAKE_CASE_ )






			def 				UpperCAmelCase       (self     :  str			,SCREAMING_SNAKE_CASE_     :  Node | None			,SCREAMING_SNAKE_CASE_     :  int			,SCREAMING_SNAKE_CASE_     :  Node | None = None )					->  Node:





				"""simple docstring"""


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

				return node






			def 				UpperCAmelCase       (self     :  str			,SCREAMING_SNAKE_CASE_     :  int )					->  Node:





				"""simple docstring"""


				return self._search(self.root			,SCREAMING_SNAKE_CASE_ )






			def 				UpperCAmelCase       (self     :  Optional[Any]			,SCREAMING_SNAKE_CASE_     :  Node | None			,SCREAMING_SNAKE_CASE_     :  int )					->  Node:





				"""simple docstring"""


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

				return node






			def 				UpperCAmelCase       (self     :  Tuple			,SCREAMING_SNAKE_CASE_     :  int )					->  None:





				"""simple docstring"""


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






			def 				UpperCAmelCase       (self     :  int			,SCREAMING_SNAKE_CASE_     :  Node			,SCREAMING_SNAKE_CASE_     :  Node | None )					->  None:





				"""simple docstring"""


				if new_children:
					lowerCAmelCase				       =     node.parent

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






			def 				UpperCAmelCase       (self     :  Dict			,SCREAMING_SNAKE_CASE_     :  Node )					->  Node:





				"""simple docstring"""


				if node.left:
					lowerCAmelCase				       =     self._get_lowest_node(node.left )
				else:
					lowerCAmelCase				       =     node
					self._reassign_nodes(SCREAMING_SNAKE_CASE_			,node.right )

				return lowest_node






			def 				UpperCAmelCase       (self     :  Union[str, Any]			,SCREAMING_SNAKE_CASE_     :  int )					->  bool:





				"""simple docstring"""


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






			def 				UpperCAmelCase       (self     :  str )					->  int:





				"""simple docstring"""


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

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

				return node.label






			def 				UpperCAmelCase       (self     :  Any )					->  int:





				"""simple docstring"""


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

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

				return node.label






			def 				UpperCAmelCase       (self     :  str )					->  Iterator[Node]:





				"""simple docstring"""


				return self._inorder_traversal(self.root )






			def 				UpperCAmelCase       (self     :  Optional[Any]			,SCREAMING_SNAKE_CASE_     :  Node | None )					->  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 				UpperCAmelCase       (self     :  Any )					->  Iterator[Node]:





				"""simple docstring"""


				return self._preorder_traversal(self.root )






			def 				UpperCAmelCase       (self     :  Any			,SCREAMING_SNAKE_CASE_     :  Node | None )					->  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 				UpperCAmelCase       ()					->  BinarySearchTree:





				"""simple docstring"""


				lowerCAmelCase				       =     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 				UpperCAmelCase       (self     :  Any )					->  None:





				"""simple docstring"""


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






			def 				UpperCAmelCase       (self     :  Any )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     self._get_binary_search_tree()

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

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

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






			def 				UpperCAmelCase       (self     :  int )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     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 				UpperCAmelCase       (self     :  List[str] )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     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 				UpperCAmelCase       (self     :  int )					->  None:





				"""simple docstring"""


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






			def 				UpperCAmelCase       (self     :  str )					->  None:





				"""simple docstring"""


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

				t.empty()
				assert t.is_empty()






			def 				UpperCAmelCase       (self     :  Optional[int] )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     self._get_binary_search_tree()

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






			def 				UpperCAmelCase       (self     :  Any )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     self._get_binary_search_tree()

				assert t.get_max_label() == 14

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






			def 				UpperCAmelCase       (self     :  Tuple )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     self._get_binary_search_tree()

				assert t.get_min_label() == 1

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






			def 				UpperCAmelCase       (self     :  Optional[int] )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     self._get_binary_search_tree()

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






			def 				UpperCAmelCase       (self     :  Optional[Any] )					->  None:





				"""simple docstring"""


				lowerCAmelCase				       =     self._get_binary_search_tree()

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





def __magic_name__  (							)				->	None:

	'''simple docstring'''




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

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

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

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

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


if __name__ == "__main__":
					binary_search_tree_example()


