
"""simple docstring"""



from __future__ import annotations

import math
import random
from typing import Any
class        _SCREAMING_SNAKE_CASE  :






				'''simple docstring'''



				def __init__(					self	:			int  )		->  None:







											"""simple docstring"""




											_lowerCAmelCase  	=			[]
											_lowerCAmelCase  	=			0
											_lowerCAmelCase  	=			0


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







											"""simple docstring"""




											return self.head == self.tail


				def 				__lowerCamelCase	(					self	:			Tuple				,     UpperCAmelCase_	:			Any  )		->  None:







											"""simple docstring"""




											self.data.append(UpperCAmelCase_  )
											_lowerCAmelCase  	=			self.tail + 1


				def 				__lowerCamelCase	(					self	:			Optional[int]  )		->  Any:







											"""simple docstring"""




											_lowerCAmelCase  	=			self.data[self.head]
											_lowerCAmelCase  	=			self.head + 1
											return ret


				def 				__lowerCamelCase	(					self	:			Tuple  )		->  int:







											"""simple docstring"""




											return self.tail - self.head







				def 				__lowerCamelCase	(					self	:			int  )		->  None:







											"""simple docstring"""




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






class        _SCREAMING_SNAKE_CASE  :






				'''simple docstring'''



				def __init__(					self	:			Dict				,     UpperCAmelCase_	:			Any  )		->  None:







											"""simple docstring"""




											_lowerCAmelCase  	=			data
											_lowerCAmelCase  	=			None
											_lowerCAmelCase  	=			None
											_lowerCAmelCase  	=			1


				def 				__lowerCamelCase	(					self	:			Dict  )		->  Any:







											"""simple docstring"""




											return self.data


				def 				__lowerCamelCase	(					self	:			Any  )		->  MyNode | None:







											"""simple docstring"""




											return self.left


				def 				__lowerCamelCase	(					self	:			List[str]  )		->  MyNode | None:







											"""simple docstring"""




											return self.right


				def 				__lowerCamelCase	(					self	:			Dict  )		->  int:







											"""simple docstring"""




											return self.height


				def 				__lowerCamelCase	(					self	:			List[str]				,     UpperCAmelCase_	:			Any  )		->  None:







											"""simple docstring"""




											_lowerCAmelCase  	=			data


				def 				__lowerCamelCase	(					self	:			Dict				,     UpperCAmelCase_	:			MyNode | None  )		->  None:







											"""simple docstring"""




											_lowerCAmelCase  	=			node


				def 				__lowerCamelCase	(					self	:			int				,     UpperCAmelCase_	:			MyNode | None  )		->  None:







											"""simple docstring"""




											_lowerCAmelCase  	=			node







				def 				__lowerCamelCase	(					self	:			Dict				,     UpperCAmelCase_	:			int  )		->  None:







											"""simple docstring"""




											_lowerCAmelCase  	=			height






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					MyNode | None						):






							"""simple docstring"""



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






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					int     ,  SCREAMING_SNAKE_CASE:					int						):






							"""simple docstring"""



							if a > b:
														return a
							return b






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					MyNode						):






							"""simple docstring"""



							print('left rotation node:'     ,  node.get_data()						)
							_lowerCAmelCase  	=			node.get_left()
							assert ret is not None
							node.set_left(ret.get_right()						)
							ret.set_right(SCREAMING_SNAKE_CASE						)
							_lowerCAmelCase  	=			my_max(get_height(node.get_right()						)     ,  get_height(node.get_left()						)						) + 1
							node.set_height(SCREAMING_SNAKE_CASE						)
							_lowerCAmelCase  	=			my_max(get_height(ret.get_right()						)     ,  get_height(ret.get_left()						)						) + 1
							ret.set_height(SCREAMING_SNAKE_CASE						)
							return ret






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					MyNode						):






							"""simple docstring"""



							print('right rotation node:'     ,  node.get_data()						)
							_lowerCAmelCase  	=			node.get_right()
							assert ret is not None
							node.set_right(ret.get_left()						)
							ret.set_left(SCREAMING_SNAKE_CASE						)
							_lowerCAmelCase  	=			my_max(get_height(node.get_right()						)     ,  get_height(node.get_left()						)						) + 1
							node.set_height(SCREAMING_SNAKE_CASE						)
							_lowerCAmelCase  	=			my_max(get_height(ret.get_right()						)     ,  get_height(ret.get_left()						)						) + 1
							ret.set_height(SCREAMING_SNAKE_CASE						)
							return ret






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					MyNode						):






							"""simple docstring"""



							_lowerCAmelCase  	=			node.get_left()
							assert left_child is not None
							node.set_left(left_rotation(SCREAMING_SNAKE_CASE						)						)
							return right_rotation(SCREAMING_SNAKE_CASE						)






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					MyNode						):






							"""simple docstring"""



							_lowerCAmelCase  	=			node.get_right()
							assert right_child is not None
							node.set_right(right_rotation(SCREAMING_SNAKE_CASE						)						)
							return left_rotation(SCREAMING_SNAKE_CASE						)






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					MyNode | None     ,  SCREAMING_SNAKE_CASE:					Any						):






							"""simple docstring"""



							if node is None:
														return MyNode(SCREAMING_SNAKE_CASE						)
							if data < node.get_data():
														node.set_left(insert_node(node.get_left()     ,  SCREAMING_SNAKE_CASE						)						)
														if (
														    get_height(node.get_left()						) - get_height(node.get_right()						) == 2
														):  # an unbalance detected
																					_lowerCAmelCase  	=			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
																												_lowerCAmelCase  	=			right_rotation(SCREAMING_SNAKE_CASE						)
																					else:
																												_lowerCAmelCase  	=			lr_rotation(SCREAMING_SNAKE_CASE						)
							else:
														node.set_right(insert_node(node.get_right()     ,  SCREAMING_SNAKE_CASE						)						)
														if get_height(node.get_right()						) - get_height(node.get_left()						) == 2:
																					_lowerCAmelCase  	=			node.get_right()
																					assert right_child is not None
																					if data < right_child.get_data():
																												_lowerCAmelCase  	=			rl_rotation(SCREAMING_SNAKE_CASE						)
																					else:
																												_lowerCAmelCase  	=			left_rotation(SCREAMING_SNAKE_CASE						)
							_lowerCAmelCase  	=			my_max(get_height(node.get_right()						)     ,  get_height(node.get_left()						)						) + 1
							node.set_height(SCREAMING_SNAKE_CASE						)
							return node






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					MyNode						):






							"""simple docstring"""



							while True:
														_lowerCAmelCase  	=			root.get_right()
														if right_child is None:
																					break
														_lowerCAmelCase  	=			right_child
							return root.get_data()






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					MyNode						):






							"""simple docstring"""



							while True:
														_lowerCAmelCase  	=			root.get_left()
														if left_child is None:
																					break
														_lowerCAmelCase  	=			left_child
							return root.get_data()






def 	__snake_case  (    SCREAMING_SNAKE_CASE:					MyNode     ,  SCREAMING_SNAKE_CASE:					Any						):






							"""simple docstring"""



							_lowerCAmelCase  	=			root.get_left()
							_lowerCAmelCase  	=			root.get_right()
							if root.get_data() == data:
														if left_child is not None and right_child is not None:
																					_lowerCAmelCase  	=			get_left_most(SCREAMING_SNAKE_CASE						)
																					root.set_data(SCREAMING_SNAKE_CASE						)
																					root.set_right(del_node(SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE						)						)
														elif left_child is not None:
																					_lowerCAmelCase  	=			left_child
														elif right_child is not None:
																					_lowerCAmelCase  	=			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(SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE						)						)
							else:  # root.get_data() < data
														if right_child is None:
																					return root
														else:
																					root.set_right(del_node(SCREAMING_SNAKE_CASE     ,  SCREAMING_SNAKE_CASE						)						)

							if get_height(SCREAMING_SNAKE_CASE						) - get_height(SCREAMING_SNAKE_CASE						) == 2:
														assert right_child is not None
														if get_height(right_child.get_right()						) > get_height(right_child.get_left()						):
																					_lowerCAmelCase  	=			left_rotation(SCREAMING_SNAKE_CASE						)
														else:
																					_lowerCAmelCase  	=			rl_rotation(SCREAMING_SNAKE_CASE						)
							elif get_height(SCREAMING_SNAKE_CASE						) - get_height(SCREAMING_SNAKE_CASE						) == -2:
														assert left_child is not None
														if get_height(left_child.get_left()						) > get_height(left_child.get_right()						):
																					_lowerCAmelCase  	=			right_rotation(SCREAMING_SNAKE_CASE						)
														else:
																					_lowerCAmelCase  	=			lr_rotation(SCREAMING_SNAKE_CASE						)
							_lowerCAmelCase  	=			my_max(get_height(root.get_right()						)     ,  get_height(root.get_left()						)						) + 1
							root.set_height(SCREAMING_SNAKE_CASE						)
							return root
class        _SCREAMING_SNAKE_CASE  :






				'''simple docstring'''



				def __init__(					self	:			Any  )		->  None:







											"""simple docstring"""




											_lowerCAmelCase  	=			None


				def 				__lowerCamelCase	(					self	:			Dict  )		->  int:







											"""simple docstring"""




											return get_height(self.root  )


				def 				__lowerCamelCase	(					self	:			List[Any]				,     UpperCAmelCase_	:			Any  )		->  None:







											"""simple docstring"""




											print('insert:' + str(UpperCAmelCase_  )  )
											_lowerCAmelCase  	=			insert_node(self.root				,     UpperCAmelCase_  )


				def 				__lowerCamelCase	(					self	:			Dict				,     UpperCAmelCase_	:			Any  )		->  None:







											"""simple docstring"""




											print('delete:' + str(UpperCAmelCase_  )  )
											if self.root is None:
																		print('Tree is empty!'  )
																		return
											_lowerCAmelCase  	=			del_node(self.root				,     UpperCAmelCase_  )







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







											"""simple docstring"""




											_lowerCAmelCase  	=			''
											_lowerCAmelCase  	=			MyQueue()
											q.push(self.root  )
											_lowerCAmelCase  	=			self.get_height()
											if layer == 0:
																		return output
											_lowerCAmelCase  	=			0
											while not q.is_empty():
																		_lowerCAmelCase  	=			q.pop()
																		_lowerCAmelCase  	=			' ' * int(math.pow(2				,     layer - 1  )  )
																		output += space
																		if node is None:
																									output += "*"
																									q.push(UpperCAmelCase_  )
																									q.push(UpperCAmelCase_  )
																		else:
																									output += str(node.get_data()  )
																									q.push(node.get_left()  )
																									q.push(node.get_right()  )
																		output += space
																		_lowerCAmelCase  	=			cnt + 1
																		for i in range(100  ):
																									if cnt == math.pow(2				,     UpperCAmelCase_  ) - 1:
																																_lowerCAmelCase  	=			layer - 1
																																if layer == 0:
																																							output += "\n*************************************"
																																							return output
																																output += "\n"
																																break
											output += "\n*************************************"
											return output






def 	__snake_case  (    ):






							"""simple docstring"""



							import doctest

							doctest.testmod()


if __name__ == "__main__":
	_test()
	_snake_case          =						AVLtree()
	_snake_case          =						list(range(1_0))
	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))








"""simple docstring"""



import pytest


_snake_case          =						'''__dummy_dataset1__'''

_snake_case          =						'''
import json
import os

import datasets


REPO_URL = "https://huggingface.co/datasets/albertvillanova/tests-raw-jsonl/resolve/main/"
URLS = {"train": REPO_URL + "wikiann-bn-train.jsonl", "validation": REPO_URL + "wikiann-bn-validation.jsonl"}


class __DummyDataset1__(datasets.GeneratorBasedBuilder):

    def _info(self):
        features = datasets.Features(
            {
                "tokens": datasets.Sequence(datasets.Value("string")),
                "ner_tags": datasets.Sequence(
                    datasets.features.ClassLabel(
                        names=[
                            "O",
                            "B-PER",
                            "I-PER",
                            "B-ORG",
                            "I-ORG",
                            "B-LOC",
                            "I-LOC",
                        ]
                    )
                ),
                "langs": datasets.Sequence(datasets.Value("string")),
                "spans": datasets.Sequence(datasets.Value("string")),
            }
        )
        return datasets.DatasetInfo(features=features)

    def _split_generators(self, dl_manager):
        dl_path = dl_manager.download(URLS)
        return [
            datasets.SplitGenerator(datasets.Split.TRAIN, gen_kwargs={"filepath": dl_path["train"]}),
            datasets.SplitGenerator(datasets.Split.VALIDATION, gen_kwargs={"filepath": dl_path["validation"]}),
        ]

    def _generate_examples(self, filepath):
        with open(filepath, "r", encoding="utf-8") as f:
            for i, line in enumerate(f):
                yield i, json.loads(line)
'''






@pytest.fixture
def 	__snake_case  (    ):






							"""simple docstring"""



							return DATASET_LOADING_SCRIPT_NAME






@pytest.fixture
def 	__snake_case  (    ):






							"""simple docstring"""



							return DATASET_LOADING_SCRIPT_CODE






@pytest.fixture
def 	__snake_case  (    SCREAMING_SNAKE_CASE:					List[str]     ,  SCREAMING_SNAKE_CASE:					Optional[int]     ,  SCREAMING_SNAKE_CASE:					List[str]						):






							"""simple docstring"""



							_lowerCAmelCase  	=			dataset_loading_script_name
							_lowerCAmelCase  	=			tmp_path / 'datasets' / script_name
							script_dir.mkdir(parents=SCREAMING_SNAKE_CASE						)
							_lowerCAmelCase  	=			script_dir / f"""{script_name}.py"""
							with open(SCREAMING_SNAKE_CASE     ,  'w'						) as f:
														f.write(SCREAMING_SNAKE_CASE						)
							return str(SCREAMING_SNAKE_CASE						)






