


'''simple docstring'''







from __future__ import annotations

import math
import random
from typing import Any
class 	UpperCamelCase__					:



     """simple docstring"""






     def __init__( self   ):

            '''simple docstring'''

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







     def a	( self   ):

            '''simple docstring'''

            return self.head == self.tail







     def a	( self      ,	snake_case__   ):

            '''simple docstring'''

            self.data.append(snake_case__   )
            _lowerCAmelCase    :							List[str]   			=       self.tail + 1







     def a	( self   ):

            '''simple docstring'''

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







     def a	( self   ):

            '''simple docstring'''

            return self.tail - self.head







     def a	( self   ):

            '''simple docstring'''

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



     """simple docstring"""






     def __init__( self      ,	snake_case__   ):

            '''simple docstring'''

            _lowerCAmelCase    :							str   			=       data
            _lowerCAmelCase    :							MyNode | None   			=       None
            _lowerCAmelCase    :							MyNode | None   			=       None
            _lowerCAmelCase    :							int   			=       1







     def a	( self   ):

            '''simple docstring'''

            return self.data







     def a	( self   ):

            '''simple docstring'''

            return self.left







     def a	( self   ):

            '''simple docstring'''

            return self.right







     def a	( self   ):

            '''simple docstring'''

            return self.height







     def a	( self      ,	snake_case__   ):

            '''simple docstring'''

            _lowerCAmelCase    :							Tuple   			=       data







     def a	( self      ,	snake_case__   ):

            '''simple docstring'''

            _lowerCAmelCase    :							Optional[Any]   			=       node







     def a	( self      ,	snake_case__   ):

            '''simple docstring'''

            _lowerCAmelCase    :							Dict   			=       node







     def a	( self      ,	snake_case__   ):

            '''simple docstring'''

            _lowerCAmelCase    :							Tuple   			=       height






def 			lowercase				(_A					):







       """simple docstring"""







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






def 			lowercase				(_A   ,						_A					):







       """simple docstring"""







       if a > b:
              return a
       return b






def 			lowercase				(_A					):







       """simple docstring"""







       print('left rotation node:'   ,						node.get_data()					)
       _lowerCAmelCase    :							Tuple   			=       node.get_left()
       assert ret is not None
       node.set_left(ret.get_right()					)
       ret.set_right(_A					)
       _lowerCAmelCase    :							Union[str, Any]   			=       my_max(get_height(node.get_right()					)   ,						get_height(node.get_left()					)					) + 1
       node.set_height(_A					)
       _lowerCAmelCase    :							List[str]   			=       my_max(get_height(ret.get_right()					)   ,						get_height(ret.get_left()					)					) + 1
       ret.set_height(_A					)
       return ret






def 			lowercase				(_A					):







       """simple docstring"""







       print('right rotation node:'   ,						node.get_data()					)
       _lowerCAmelCase    :							int   			=       node.get_right()
       assert ret is not None
       node.set_right(ret.get_left()					)
       ret.set_left(_A					)
       _lowerCAmelCase    :							List[str]   			=       my_max(get_height(node.get_right()					)   ,						get_height(node.get_left()					)					) + 1
       node.set_height(_A					)
       _lowerCAmelCase    :							Optional[Any]   			=       my_max(get_height(ret.get_right()					)   ,						get_height(ret.get_left()					)					) + 1
       ret.set_height(_A					)
       return ret






def 			lowercase				(_A					):







       """simple docstring"""







       _lowerCAmelCase    :							List[Any]   			=       node.get_left()
       assert left_child is not None
       node.set_left(left_rotation(_A					)					)
       return right_rotation(_A					)






def 			lowercase				(_A					):







       """simple docstring"""







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






def 			lowercase				(_A   ,						_A					):







       """simple docstring"""







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






def 			lowercase				(_A					):







       """simple docstring"""







       while True:
              _lowerCAmelCase    :							Any   			=       root.get_right()
              if right_child is None:
                     break
              _lowerCAmelCase    :							Union[str, Any]   			=       right_child
       return root.get_data()






def 			lowercase				(_A					):







       """simple docstring"""







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






def 			lowercase				(_A   ,						_A					):







       """simple docstring"""







       _lowerCAmelCase    :							List[Any]   			=       root.get_left()
       _lowerCAmelCase    :							List[str]   			=       root.get_right()
       if root.get_data() == data:
              if left_child is not None and right_child is not None:
                     _lowerCAmelCase    :							Optional[int]   			=       get_left_most(_A					)
                     root.set_data(_A					)
                     root.set_right(del_node(_A   ,						_A					)					)
              elif left_child is not None:
                     _lowerCAmelCase    :							str   			=       left_child
              elif right_child is not None:
                     _lowerCAmelCase    :							Tuple   			=       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(_A   ,						_A					)					)
       else:  # root.get_data() < data
              if right_child is None:
                     return root
              else:
                     root.set_right(del_node(_A   ,						_A					)					)

       if get_height(_A					) - get_height(_A					) == 2:
              assert right_child is not None
              if get_height(right_child.get_right()					) > get_height(right_child.get_left()					):
                     _lowerCAmelCase    :							Tuple   			=       left_rotation(_A					)
              else:
                     _lowerCAmelCase    :							Dict   			=       rl_rotation(_A					)
       elif get_height(_A					) - get_height(_A					) == -2:
              assert left_child is not None
              if get_height(left_child.get_left()					) > get_height(left_child.get_right()					):
                     _lowerCAmelCase    :							Optional[int]   			=       right_rotation(_A					)
              else:
                     _lowerCAmelCase    :							Any   			=       lr_rotation(_A					)
       _lowerCAmelCase    :							Optional[Any]   			=       my_max(get_height(root.get_right()					)   ,						get_height(root.get_left()					)					) + 1
       root.set_height(_A					)
       return root
class 	UpperCamelCase__					:



     """simple docstring"""






     def __init__( self   ):

            '''simple docstring'''

            _lowerCAmelCase    :							MyNode | None   			=       None







     def a	( self   ):

            '''simple docstring'''

            return get_height(self.root   )







     def a	( self      ,	snake_case__   ):

            '''simple docstring'''

            print('insert:' + str(snake_case__   )   )
            _lowerCAmelCase    :							List[str]   			=       insert_node(self.root      ,	snake_case__   )







     def a	( self      ,	snake_case__   ):

            '''simple docstring'''

            print('delete:' + str(snake_case__   )   )
            if self.root is None:
                   print('Tree is empty!'   )
                   return
            _lowerCAmelCase    :							Union[str, Any]   			=       del_node(self.root      ,	snake_case__   )







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

            '''simple docstring'''

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






def 			lowercase				():







       """simple docstring"""







       import doctest

       doctest.testmod()


if __name__ == "__main__":
       _test()
       lowerCAmelCase    :     Tuple					=						AVLtree()
       lowerCAmelCase    :     Any					=						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))





'''simple docstring'''







import pytest

import datasets


# Import fixture modules as plugins
lowerCAmelCase    :     List[str]					=						["""tests.fixtures.files""", """tests.fixtures.hub""", """tests.fixtures.fsspec"""]






def 			lowercase				(_A   ,						_A					):







       """simple docstring"""







       for item in items:
              if any(marker in item.keywords for marker in ['integration', 'unit']					):
                     continue
              item.add_marker(pytest.mark.unit					)






def 			lowercase				(_A					):







       """simple docstring"""







       config.addinivalue_line('markers'   ,						'torchaudio_latest: mark test to run with torchaudio>=0.12'					)






@pytest.fixture(autouse=_A					)
def 			lowercase				(_A   ,						_A					):







       """simple docstring"""







       _lowerCAmelCase    :							str   			=       tmp_path_factory.getbasetemp() / 'cache'
       _lowerCAmelCase    :							Dict   			=       test_hf_cache_home / 'datasets'
       _lowerCAmelCase    :							List[Any]   			=       test_hf_cache_home / 'metrics'
       _lowerCAmelCase    :							List[Any]   			=       test_hf_cache_home / 'modules'
       monkeypatch.setattr('datasets.config.HF_DATASETS_CACHE'   ,						str(_A					)					)
       monkeypatch.setattr('datasets.config.HF_METRICS_CACHE'   ,						str(_A					)					)
       monkeypatch.setattr('datasets.config.HF_MODULES_CACHE'   ,						str(_A					)					)
       _lowerCAmelCase    :							Dict   			=       test_hf_datasets_cache / 'downloads'
       monkeypatch.setattr('datasets.config.DOWNLOADED_DATASETS_PATH'   ,						str(_A					)					)
       _lowerCAmelCase    :							Union[str, Any]   			=       test_hf_datasets_cache / 'downloads' / 'extracted'
       monkeypatch.setattr('datasets.config.EXTRACTED_DATASETS_PATH'   ,						str(_A					)					)






@pytest.fixture(autouse=_A   ,						scope='session'					)
def 			lowercase				():







       """simple docstring"""







       datasets.disable_progress_bar()






@pytest.fixture(autouse=_A					)
def 			lowercase				(_A					):







       """simple docstring"""







       monkeypatch.setattr('datasets.config.HF_UPDATE_DOWNLOAD_COUNTS'   ,						_A					)






@pytest.fixture
def 			lowercase				(_A					):







       """simple docstring"""







       monkeypatch.setattr('sqlalchemy.util.deprecations.SILENCE_UBER_WARNING'   ,						_A					)

