





'''simple docstring'''






from __future__ import annotations

import math
import random
from typing import Any




class  _A :

		def __init__(   self					:   Tuple			)					->    None:


					"""simple docstring"""

					__snake_case					:      list[Any]							      =     []
					__snake_case					:      int							      =     0
					__snake_case					:      int							      =     0

		def 	lowercase__     (   self					:   List[str]			)					->    bool:


					"""simple docstring"""

					return self.head == self.tail

		def 	lowercase__     (   self					:   int  ,      __magic_name__					:   Any			)					->    None:


					"""simple docstring"""

					self.data.append(__magic_name__			)
					__snake_case					:      Dict							      =     self.tail + 1

		def 	lowercase__     (   self					:   int			)					->    Any:


					"""simple docstring"""

					__snake_case					:      Optional[int]							      =     self.data[self.head]
					__snake_case					:      Optional[Any]							      =     self.head + 1
					return ret

		def 	lowercase__     (   self					:   str			)					->    int:


					"""simple docstring"""

					return self.tail - self.head

		def 	lowercase__     (   self					:   int			)					->    None:


					"""simple docstring"""

					print(self.data			)
					print("""**************"""			)
					print(self.data[self.head : self.tail]			)





class  _A :

		def __init__(   self					:   str  ,      __magic_name__					:   Any			)					->    None:


					"""simple docstring"""

					__snake_case					:      List[Any]							      =     data
					__snake_case					:      MyNode | None							      =     None
					__snake_case					:      MyNode | None							      =     None
					__snake_case					:      int							      =     1

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


					"""simple docstring"""

					return self.data

		def 	lowercase__     (   self					:   Dict			)					->    MyNode | None:


					"""simple docstring"""

					return self.left

		def 	lowercase__     (   self					:   Optional[int]			)					->    MyNode | None:


					"""simple docstring"""

					return self.right

		def 	lowercase__     (   self					:   List[Any]			)					->    int:


					"""simple docstring"""

					return self.height

		def 	lowercase__     (   self					:   Any  ,      __magic_name__					:   Any			)					->    None:


					"""simple docstring"""

					__snake_case					:      Any							      =     data

		def 	lowercase__     (   self					:   Optional[int]  ,      __magic_name__					:   MyNode | None			)					->    None:


					"""simple docstring"""

					__snake_case					:      List[str]							      =     node

		def 	lowercase__     (   self					:   List[Any]  ,      __magic_name__					:   MyNode | None			)					->    None:


					"""simple docstring"""

					__snake_case					:      List[Any]							      =     node

		def 	lowercase__     (   self					:   Optional[Any]  ,      __magic_name__					:   int			)					->    None:


					"""simple docstring"""

					__snake_case					:      Tuple							      =     height







def 					_a						(       _lowerCamelCase ) ->				int:



			"""simple docstring"""


			if node is None:
						return 0
			return node.get_height()







def 					_a						(       _lowerCamelCase    ,	_lowerCamelCase ) ->				int:



			"""simple docstring"""


			if a > b:
						return a
			return b







def 					_a						(       _lowerCamelCase ) ->				MyNode:



			"""simple docstring"""


			print("""left rotation node:"""    ,	node.get_data() )
			__snake_case					:      Optional[Any]							      =     node.get_left()
			assert ret is not None
			node.set_left(ret.get_right() )
			ret.set_right(_lowerCamelCase )
			__snake_case					:      str							      =     my_max(get_height(node.get_right() )    ,	get_height(node.get_left() ) ) + 1
			node.set_height(_lowerCamelCase )
			__snake_case					:      List[Any]							      =     my_max(get_height(ret.get_right() )    ,	get_height(ret.get_left() ) ) + 1
			ret.set_height(_lowerCamelCase )
			return ret







def 					_a						(       _lowerCamelCase ) ->				MyNode:



			"""simple docstring"""


			print("""right rotation node:"""    ,	node.get_data() )
			__snake_case					:      Optional[Any]							      =     node.get_right()
			assert ret is not None
			node.set_right(ret.get_left() )
			ret.set_left(_lowerCamelCase )
			__snake_case					:      Tuple							      =     my_max(get_height(node.get_right() )    ,	get_height(node.get_left() ) ) + 1
			node.set_height(_lowerCamelCase )
			__snake_case					:      Any							      =     my_max(get_height(ret.get_right() )    ,	get_height(ret.get_left() ) ) + 1
			ret.set_height(_lowerCamelCase )
			return ret







def 					_a						(       _lowerCamelCase ) ->				MyNode:



			"""simple docstring"""


			__snake_case					:      str							      =     node.get_left()
			assert left_child is not None
			node.set_left(left_rotation(_lowerCamelCase ) )
			return right_rotation(_lowerCamelCase )







def 					_a						(       _lowerCamelCase ) ->				MyNode:



			"""simple docstring"""


			__snake_case					:      Optional[int]							      =     node.get_right()
			assert right_child is not None
			node.set_right(right_rotation(_lowerCamelCase ) )
			return left_rotation(_lowerCamelCase )







def 					_a						(       _lowerCamelCase    ,	_lowerCamelCase ) ->				MyNode | None:



			"""simple docstring"""


			if node is None:
						return MyNode(_lowerCamelCase )
			if data < node.get_data():
						node.set_left(insert_node(node.get_left()    ,	_lowerCamelCase ) )
						if (
						    get_height(node.get_left() ) - get_height(node.get_right() ) == 2
						):  # an unbalance detected
									__snake_case					:      Union[str, Any]							      =     node.get_left()
									assert left_child is not None
									if (
									    data < left_child.get_data()
									):  # new node is the left child of the left child
												__snake_case					:      Any							      =     right_rotation(_lowerCamelCase )
									else:
												__snake_case					:      Tuple							      =     lr_rotation(_lowerCamelCase )
			else:
						node.set_right(insert_node(node.get_right()    ,	_lowerCamelCase ) )
						if get_height(node.get_right() ) - get_height(node.get_left() ) == 2:
									__snake_case					:      Optional[int]							      =     node.get_right()
									assert right_child is not None
									if data < right_child.get_data():
												__snake_case					:      Optional[int]							      =     rl_rotation(_lowerCamelCase )
									else:
												__snake_case					:      Tuple							      =     left_rotation(_lowerCamelCase )
			__snake_case					:      Optional[Any]							      =     my_max(get_height(node.get_right() )    ,	get_height(node.get_left() ) ) + 1
			node.set_height(_lowerCamelCase )
			return node







def 					_a						(       _lowerCamelCase ) ->				Any:



			"""simple docstring"""


			while True:
						__snake_case					:      Dict							      =     root.get_right()
						if right_child is None:
									break
						__snake_case					:      List[Any]							      =     right_child
			return root.get_data()







def 					_a						(       _lowerCamelCase ) ->				Any:



			"""simple docstring"""


			while True:
						__snake_case					:      Optional[Any]							      =     root.get_left()
						if left_child is None:
									break
						__snake_case					:      int							      =     left_child
			return root.get_data()







def 					_a						(       _lowerCamelCase    ,	_lowerCamelCase ) ->				MyNode | None:



			"""simple docstring"""


			__snake_case					:      int							      =     root.get_left()
			__snake_case					:      int							      =     root.get_right()
			if root.get_data() == data:
						if left_child is not None and right_child is not None:
									__snake_case					:      Tuple							      =     get_left_most(_lowerCamelCase )
									root.set_data(_lowerCamelCase )
									root.set_right(del_node(_lowerCamelCase    ,	_lowerCamelCase ) )
						elif left_child is not None:
									__snake_case					:      Optional[int]							      =     left_child
						elif right_child is not None:
									__snake_case					:      str							      =     right_child
						else:
									return None
			elif root.get_data() > data:
						if left_child is None:
									print("""No such data""" )
									return root
						else:
									root.set_left(del_node(_lowerCamelCase    ,	_lowerCamelCase ) )
			else:  # root.get_data() < data
						if right_child is None:
									return root
						else:
									root.set_right(del_node(_lowerCamelCase    ,	_lowerCamelCase ) )

			if get_height(_lowerCamelCase ) - get_height(_lowerCamelCase ) == 2:
						assert right_child is not None
						if get_height(right_child.get_right() ) > get_height(right_child.get_left() ):
									__snake_case					:      Optional[Any]							      =     left_rotation(_lowerCamelCase )
						else:
									__snake_case					:      str							      =     rl_rotation(_lowerCamelCase )
			elif get_height(_lowerCamelCase ) - get_height(_lowerCamelCase ) == -2:
						assert left_child is not None
						if get_height(left_child.get_left() ) > get_height(left_child.get_right() ):
									__snake_case					:      List[Any]							      =     right_rotation(_lowerCamelCase )
						else:
									__snake_case					:      List[str]							      =     lr_rotation(_lowerCamelCase )
			__snake_case					:      List[Any]							      =     my_max(get_height(root.get_right() )    ,	get_height(root.get_left() ) ) + 1
			root.set_height(_lowerCamelCase )
			return root




class  _A :

		def __init__(   self					:   int			)					->    None:


					"""simple docstring"""

					__snake_case					:      MyNode | None							      =     None

		def 	lowercase__     (   self					:   Dict			)					->    int:


					"""simple docstring"""

					return get_height(self.root			)

		def 	lowercase__     (   self					:   Tuple  ,      __magic_name__					:   Any			)					->    None:


					"""simple docstring"""

					print("""insert:""" + str(__magic_name__			)			)
					__snake_case					:      Optional[Any]							      =     insert_node(self.root  ,      __magic_name__			)

		def 	lowercase__     (   self					:   Dict  ,      __magic_name__					:   Any			)					->    None:


					"""simple docstring"""

					print("""delete:""" + str(__magic_name__			)			)
					if self.root is None:
								print("""Tree is empty!"""			)
								return
					__snake_case					:      str							      =     del_node(self.root  ,      __magic_name__			)

		def __str__(   self					:   Dict  ,      )					->    str:  # a level traversale, gives a more intuitive look on the tree


					"""simple docstring"""

					__snake_case					:      List[Any]							      =     """"""
					__snake_case					:      int							      =     MyQueue()
					q.push(self.root			)
					__snake_case					:      int							      =     self.get_height()
					if layer == 0:
								return output
					__snake_case					:      Any							      =     0
					while not q.is_empty():
								__snake_case					:      Optional[int]							      =     q.pop()
								__snake_case					:      Optional[int]							      =     """ """ * int(math.pow(2  ,      layer - 1			)			)
								output += space
								if node is None:
											output += "*"
											q.push(__magic_name__			)
											q.push(__magic_name__			)
								else:
											output += str(node.get_data()			)
											q.push(node.get_left()			)
											q.push(node.get_right()			)
								output += space
								__snake_case					:      Tuple							      =     cnt + 1
								for i in range(1_00			):
											if cnt == math.pow(2  ,      __magic_name__			) - 1:
														__snake_case					:      Tuple							      =     layer - 1
														if layer == 0:
																	output += "\n*************************************"
																	return output
														output += "\n"
														break
					output += "\n*************************************"
					return output







def 					_a						(       ) ->				None:



			"""simple docstring"""


			import doctest

			doctest.testmod()


if __name__ == "__main__":
	_test()
	__UpperCamelCase					    =	AVLtree()
	__UpperCamelCase					    =	list(range(10))
	random.shuffle(lst)
	for i in lst:
		t.insert(i)
		print(str(t))
	random.shuffle(lst)
	for i in lst:
		t.del_node(i)
		print(str(t))







import pytest

from datasets import Dataset, DatasetDict, Features, NamedSplit, Value
from datasets.io.text import TextDatasetReader

from ..utils import assert_arrow_memory_doesnt_increase, assert_arrow_memory_increases






def        __lowerCAmelCase		(	__lowerCamelCase						:     List[Any]					, __lowerCamelCase						:     Any						)	->    Dict:
					assert isinstance(__lowerCamelCase					, __lowerCamelCase						)
					assert dataset.num_rows == 4
					assert dataset.num_columns == 1
					assert dataset.column_names == ["text"]
					for feature, expected_dtype in expected_features.items():
										assert dataset.features[feature].dtype == expected_dtype






@pytest.mark.parametrize("""keep_in_memory"""					, [False, True]						)
def        __lowerCAmelCase		(	__lowerCamelCase						:     Tuple					, __lowerCamelCase						:     str					, __lowerCamelCase						:     Optional[Any]						)	->    List[Any]:
					__lowerCAmelCase						 =tmp_path / """cache"""
					__lowerCAmelCase						 ={"""text""": """string"""}
					with assert_arrow_memory_increases() if keep_in_memory else assert_arrow_memory_doesnt_increase():
										__lowerCAmelCase						 =TextDatasetReader(__lowerCamelCase					, cache_dir=__lowerCamelCase					, keep_in_memory=__lowerCamelCase						).read()
					_check_text_dataset(__lowerCamelCase					, __lowerCamelCase						)






@pytest.mark.parametrize(
    """features"""					, [
        None,
        {"""text""": """string"""},
        {"""text""": """int32"""},
        {"""text""": """float32"""},
    ]					, )
def        __lowerCAmelCase		(	__lowerCamelCase						:     Tuple					, __lowerCamelCase						:     Any					, __lowerCamelCase						:     Tuple						)	->    List[Any]:
					__lowerCAmelCase						 =tmp_path / """cache"""
					__lowerCAmelCase						 ={"""text""": """string"""}
					__lowerCAmelCase						 =features.copy() if features else default_expected_features
					__lowerCAmelCase						 =(
					    Features({feature: Value(__lowerCamelCase						) for feature, dtype in features.items()}						) if features is not None else None
					)
					__lowerCAmelCase						 =TextDatasetReader(__lowerCamelCase					, features=__lowerCamelCase					, cache_dir=__lowerCamelCase						).read()
					_check_text_dataset(__lowerCamelCase					, __lowerCamelCase						)






@pytest.mark.parametrize("""split"""					, [None, NamedSplit("""train"""						), """train""", """test"""]						)
def        __lowerCAmelCase		(	__lowerCamelCase						:     Union[str, Any]					, __lowerCamelCase						:     List[str]					, __lowerCamelCase						:     Union[str, Any]						)	->    Any:
					__lowerCAmelCase						 =tmp_path / """cache"""
					__lowerCAmelCase						 ={"""text""": """string"""}
					__lowerCAmelCase						 =TextDatasetReader(__lowerCamelCase					, cache_dir=__lowerCamelCase					, split=__lowerCamelCase						).read()
					_check_text_dataset(__lowerCamelCase					, __lowerCamelCase						)
					assert dataset.split == split if split else "train"






@pytest.mark.parametrize("""path_type"""					, [str, list]						)
def        __lowerCAmelCase		(	__lowerCamelCase						:     List[Any]					, __lowerCamelCase						:     int					, __lowerCamelCase						:     List[str]						)	->    Any:
					if issubclass(__lowerCamelCase					, __lowerCamelCase						):
										__lowerCAmelCase						 =text_path
					elif issubclass(__lowerCamelCase					, __lowerCamelCase						):
										__lowerCAmelCase						 =[text_path]
					__lowerCAmelCase						 =tmp_path / """cache"""
					__lowerCAmelCase						 ={"""text""": """string"""}
					__lowerCAmelCase						 =TextDatasetReader(__lowerCamelCase					, cache_dir=__lowerCamelCase						).read()
					_check_text_dataset(__lowerCamelCase					, __lowerCamelCase						)






def        __lowerCAmelCase		(	__lowerCamelCase						:     Tuple					, __lowerCamelCase						:     List[str]					, __lowerCamelCase						:     str=("train",)						)	->    Dict:
					assert isinstance(__lowerCamelCase					, __lowerCamelCase						)
					for split in splits:
										__lowerCAmelCase						 =dataset_dict[split]
										assert dataset.num_rows == 4
										assert dataset.num_columns == 1
										assert dataset.column_names == ["text"]
										for feature, expected_dtype in expected_features.items():
															assert dataset.features[feature].dtype == expected_dtype






@pytest.mark.parametrize("""keep_in_memory"""					, [False, True]						)
def        __lowerCAmelCase		(	__lowerCamelCase						:     Optional[int]					, __lowerCamelCase						:     List[Any]					, __lowerCamelCase						:     List[Any]						)	->    Dict:
					__lowerCAmelCase						 =tmp_path / """cache"""
					__lowerCAmelCase						 ={"""text""": """string"""}
					with assert_arrow_memory_increases() if keep_in_memory else assert_arrow_memory_doesnt_increase():
										__lowerCAmelCase						 =TextDatasetReader({"""train""": text_path}					, cache_dir=__lowerCamelCase					, keep_in_memory=__lowerCamelCase						).read()
					_check_text_datasetdict(__lowerCamelCase					, __lowerCamelCase						)






@pytest.mark.parametrize(
    """features"""					, [
        None,
        {"""text""": """string"""},
        {"""text""": """int32"""},
        {"""text""": """float32"""},
    ]					, )
def        __lowerCAmelCase		(	__lowerCamelCase						:     Any					, __lowerCamelCase						:     Optional[int]					, __lowerCamelCase						:     Union[str, Any]						)	->    Tuple:
					__lowerCAmelCase						 =tmp_path / """cache"""
					# CSV file loses col_1 string dtype information: default now is "int64" instead of "string"
					__lowerCAmelCase						 ={"""text""": """string"""}
					__lowerCAmelCase						 =features.copy() if features else default_expected_features
					__lowerCAmelCase						 =(
					    Features({feature: Value(__lowerCamelCase						) for feature, dtype in features.items()}						) if features is not None else None
					)
					__lowerCAmelCase						 =TextDatasetReader({"""train""": text_path}					, features=__lowerCamelCase					, cache_dir=__lowerCamelCase						).read()
					_check_text_datasetdict(__lowerCamelCase					, __lowerCamelCase						)






@pytest.mark.parametrize("""split"""					, [None, NamedSplit("""train"""						), """train""", """test"""]						)
def        __lowerCAmelCase		(	__lowerCamelCase						:     int					, __lowerCamelCase						:     List[str]					, __lowerCamelCase						:     Any						)	->    int:
					if split:
										__lowerCAmelCase						 ={split: text_path}
					else:
										__lowerCAmelCase						 ="""train"""
										__lowerCAmelCase						 ={"""train""": text_path, """test""": text_path}
					__lowerCAmelCase						 =tmp_path / """cache"""
					__lowerCAmelCase						 ={"""text""": """string"""}
					__lowerCAmelCase						 =TextDatasetReader(__lowerCamelCase					, cache_dir=__lowerCamelCase						).read()
					_check_text_datasetdict(__lowerCamelCase					, __lowerCamelCase					, splits=list(path.keys()						)						)
					assert all(dataset[split].split == split for split in path.keys()						)




