
from __future__ import annotations

import unittest
from collections.abc import Iterator






class     SCREAMING_SNAKE_CASE__      :

							"""simple docstring"""






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





													'''simple docstring'''






													__UpperCamelCase       					=     label
													__UpperCamelCase       					=     parent
													__UpperCamelCase       					=     None
													__UpperCamelCase       					=     None






class     SCREAMING_SNAKE_CASE__      :

							"""simple docstring"""






							def __init__(					self     )->				None:





													'''simple docstring'''






													__UpperCamelCase       					=     None



							def       A__						(					self     )->				None:





													'''simple docstring'''






													__UpperCamelCase       					=     None



							def       A__						(					self     )->				bool:





													'''simple docstring'''






													return self.root is None



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_     )->				None:





													'''simple docstring'''






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



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_ = None     )->				Node:





													'''simple docstring'''






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

													return node



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_     )->				Node:





													'''simple docstring'''






													return self._search(self.root       ,		SCREAMING_SNAKE_CASE_     )



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_     )->				Node:





													'''simple docstring'''






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

													return node



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_     )->				None:





													'''simple docstring'''






													__UpperCamelCase       					=     self.search(SCREAMING_SNAKE_CASE_     )
													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(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       A__						(					self       ,		SCREAMING_SNAKE_CASE_       ,		SCREAMING_SNAKE_CASE_     )->				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       A__						(					self       ,		SCREAMING_SNAKE_CASE_     )->				Node:





													'''simple docstring'''






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

													return lowest_node



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_     )->				bool:





													'''simple docstring'''






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



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





													'''simple docstring'''






													return self._inorder_traversal(self.root     )



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





													'''simple docstring'''






													return self._preorder_traversal(self.root     )



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_     )->				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     SCREAMING_SNAKE_CASE__      (							unittest.TestCase      ):

							"""simple docstring"""






							@staticmethod
							def       A__						(					)->				BinarySearchTree:





													'''simple docstring'''






													__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     )

													return t



							def       A__						(					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(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       A__						(					self     )->				None:





													'''simple docstring'''






													__UpperCamelCase       					=     self._get_binary_search_tree()

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

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

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



							def       A__						(					self     )->				None:





													'''simple docstring'''






													__UpperCamelCase       					=     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       A__						(					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       A__						(					self     )->				None:





													'''simple docstring'''






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



							def       A__						(					self     )->				None:





													'''simple docstring'''






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

													t.empty()
													assert t.is_empty()



							def       A__						(					self     )->				None:





													'''simple docstring'''






													__UpperCamelCase       					=     self._get_binary_search_tree()

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



							def       A__						(					self     )->				None:





													'''simple docstring'''






													__UpperCamelCase       					=     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       A__						(					self     )->				None:





													'''simple docstring'''






													__UpperCamelCase       					=     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       A__						(					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, 10, 13, 14]



							def       A__						(					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, 10, 14, 13]





def 		A_	(							) ->      None:



						'''simple docstring'''

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

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

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

						# 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:'''	, snake_case	)

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


if __name__ == "__main__":
							binary_search_tree_example()






import torch

from transformers import PreTrainedModel

from .custom_configuration import CustomConfig, NoSuperInitConfig






class     SCREAMING_SNAKE_CASE__      (							SCREAMING_SNAKE_CASE_      ):

							"""simple docstring"""






							_snake_case       						=					CustomConfig



							def __init__(					self       ,		SCREAMING_SNAKE_CASE_     )->				Tuple:





													'''simple docstring'''






													super().__init__(SCREAMING_SNAKE_CASE_     )
													__UpperCamelCase       					=     torch.nn.Linear(config.hidden_size       ,		config.hidden_size     )



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_     )->				List[str]:





													'''simple docstring'''






													return self.linear(SCREAMING_SNAKE_CASE_     )



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_     )->				Any:





													'''simple docstring'''






													pass






class     SCREAMING_SNAKE_CASE__      (							SCREAMING_SNAKE_CASE_      ):

							"""simple docstring"""






							_snake_case       						=					NoSuperInitConfig



							def __init__(					self       ,		SCREAMING_SNAKE_CASE_     )->				Tuple:





													'''simple docstring'''






													super().__init__(SCREAMING_SNAKE_CASE_     )
													__UpperCamelCase       					=     torch.nn.Linear(config.attribute       ,		config.attribute     )



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_     )->				List[str]:





													'''simple docstring'''






													return self.linear(SCREAMING_SNAKE_CASE_     )



							def       A__						(					self       ,		SCREAMING_SNAKE_CASE_     )->				Union[str, Any]:





													'''simple docstring'''






													pass




