


from __future__ import annotations

import math
import random
from typing import Any







class 						_snake_case    :




 def __init__(						self       ):
       a		:list[Any]									=			[]
       a		:int									=			0
       a		:int									=			0




 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       return self.head == self.tail




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase       ):
       self.data.append(_lowerCamelCase       )
       a		:Optional[Any]									=			self.tail + 1




 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       a		:int									=			self.data[self.head]
       a		:Any									=			self.head + 1
       return ret




 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       return self.tail - self.head




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







class 						_snake_case    :




 def __init__(						self   ,    _lowerCamelCase       ):
       a		:Any									=			data
       a		:MyNode | None									=			None
       a		:MyNode | None									=			None
       a		:int									=			1




 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       return self.data




 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       return self.left




 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       return self.right




 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       return self.height




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase       ):
       a		:Optional[int]									=			data




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase       ):
       a		:Dict									=			node




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase       ):
       a		:Optional[Any]									=			node




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase       ):
       a		:Optional[Any]									=			height







def 							__lowerCamelCase		(					UpperCAmelCase_		:						MyNode | None		):




      """simple docstring"""





      if node is None:
            return 0
      return node.get_height()
def 							__lowerCamelCase		(					UpperCAmelCase_		:						int					,    UpperCAmelCase_		:						int		):




      """simple docstring"""





      if a > b:
            return a
      return b
def 							__lowerCamelCase		(					UpperCAmelCase_		:						MyNode		):




      """simple docstring"""





      print('''left rotation node:'''					,    node.get_data()		)
      a		:str									=			node.get_left()
      assert ret is not None
      node.set_left(ret.get_right()		)
      ret.set_right(UpperCAmelCase_		)
      a		:Optional[Any]									=			my_max(get_height(node.get_right()		)					,    get_height(node.get_left()		)		) + 1
      node.set_height(UpperCAmelCase_		)
      a		:str									=			my_max(get_height(ret.get_right()		)					,    get_height(ret.get_left()		)		) + 1
      ret.set_height(UpperCAmelCase_		)
      return ret
def 							__lowerCamelCase		(					UpperCAmelCase_		:						MyNode		):




      """simple docstring"""





      print('''right rotation node:'''					,    node.get_data()		)
      a		:str									=			node.get_right()
      assert ret is not None
      node.set_right(ret.get_left()		)
      ret.set_left(UpperCAmelCase_		)
      a		:Tuple									=			my_max(get_height(node.get_right()		)					,    get_height(node.get_left()		)		) + 1
      node.set_height(UpperCAmelCase_		)
      a		:Dict									=			my_max(get_height(ret.get_right()		)					,    get_height(ret.get_left()		)		) + 1
      ret.set_height(UpperCAmelCase_		)
      return ret
def 							__lowerCamelCase		(					UpperCAmelCase_		:						MyNode		):




      """simple docstring"""





      a		:Dict									=			node.get_left()
      assert left_child is not None
      node.set_left(left_rotation(UpperCAmelCase_		)		)
      return right_rotation(UpperCAmelCase_		)
def 							__lowerCamelCase		(					UpperCAmelCase_		:						MyNode		):




      """simple docstring"""





      a		:List[Any]									=			node.get_right()
      assert right_child is not None
      node.set_right(right_rotation(UpperCAmelCase_		)		)
      return left_rotation(UpperCAmelCase_		)
def 							__lowerCamelCase		(					UpperCAmelCase_		:						MyNode | None					,    UpperCAmelCase_		:						Any		):




      """simple docstring"""





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




      """simple docstring"""





      while True:
            a		:Any									=			root.get_right()
            if right_child is None:
                  break
            a		:Dict									=			right_child
      return root.get_data()
def 							__lowerCamelCase		(					UpperCAmelCase_		:						MyNode		):




      """simple docstring"""





      while True:
            a		:Optional[Any]									=			root.get_left()
            if left_child is None:
                  break
            a		:str									=			left_child
      return root.get_data()
def 							__lowerCamelCase		(					UpperCAmelCase_		:						MyNode					,    UpperCAmelCase_		:						Any		):




      """simple docstring"""





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

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







class 						_snake_case    :




 def __init__(						self       ):
       a		:MyNode | None									=			None




 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       return get_height(self.root       )




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase       ):
       print('''insert:''' + str(_lowerCamelCase       )       )
       a		:Dict									=			insert_node(self.root   ,    _lowerCamelCase       )




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase       ):
       print('''delete:''' + str(_lowerCamelCase       )       )
       if self.root is None:
             print('''Tree is empty!'''       )
             return
       a		:Dict									=			del_node(self.root   ,    _lowerCamelCase       )




 def __str__(						self   ,    ):  # a level traversale, gives a more intuitive look on the tree
       a		:List[str]									=			''''''
       a		:Union[str, Any]									=			MyQueue()
       q.push(self.root       )
       a		:Optional[Any]									=			self.get_height()
       if layer == 0:
             return output
       a		:int									=			0
       while not q.is_empty():
             a		:Tuple									=			q.pop()
             a		:Optional[int]									=			''' ''' * int(math.pow(2   ,    layer - 1       )       )
             output += space
             if node is None:
                   output += "*"
                   q.push(_lowerCamelCase       )
                   q.push(_lowerCamelCase       )
             else:
                   output += str(node.get_data()       )
                   q.push(node.get_left()       )
                   q.push(node.get_right()       )
             output += space
             a		:Dict									=			cnt + 1
             for i in range(100       ):
                   if cnt == math.pow(2   ,    _lowerCamelCase       ) - 1:
                         a		:Tuple									=			layer - 1
                         if layer == 0:
                               output += "\n*************************************"
                               return output
                         output += "\n"
                         break
       output += "\n*************************************"
       return output







def 							__lowerCamelCase		(					):




      """simple docstring"""





      import doctest

      doctest.testmod()


if __name__ == "__main__":
     _test()
     snake_case							:       Tuple										=	AVLtree()
     snake_case							:       str										=	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 os
import tempfile
from functools import partial
from unittest import TestCase
from unittest.mock import patch

import datasets
import datasets.config

from .utils import require_beam







class 						_snake_case    ( datasets.BeamBasedBuilder				):




 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       return datasets.DatasetInfo(
           features=datasets.Features({'''content''': datasets.Value('''string'''       )}       )   ,    supervised_keys=_lowerCamelCase   ,    )




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase   ,    _lowerCamelCase       ):
       return [datasets.SplitGenerator(name=datasets.Split.TRAIN   ,    gen_kwargs={'''examples''': get_test_dummy_examples()}       )]




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase   ,    _lowerCamelCase       ):
       import apache_beam as beam

       return pipeline | "Load Examples" >> beam.Create(_lowerCamelCase       )







class 						_snake_case    ( datasets.BeamBasedBuilder				):




 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       return datasets.DatasetInfo(
           features=datasets.Features({'''a''': datasets.Sequence({'''b''': datasets.Value('''string'''       )}       )}       )   ,    supervised_keys=_lowerCamelCase   ,    )




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase   ,    _lowerCamelCase       ):
       return [
           datasets.SplitGenerator(name=datasets.Split.TRAIN   ,    gen_kwargs={'''examples''': get_test_nested_examples()}       )
       ]




 def 			SCREAMING_SNAKE_CASE__							(						self   ,    _lowerCamelCase   ,    _lowerCamelCase       ):
       import apache_beam as beam

       return pipeline | "Load Examples" >> beam.Create(_lowerCamelCase       )







def 							__lowerCamelCase		(					):




      """simple docstring"""





      return [(i, {"content": content}) for i, content in enumerate(['''foo''', '''bar''', '''foobar''']		)]
def 							__lowerCamelCase		(					):




      """simple docstring"""





      return [(i, {"a": {"b": [content]}}) for i, content in enumerate(['''foo''', '''bar''', '''foobar''']		)]







class 						_snake_case    ( _snake_case				):




 @require_beam
 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       a		:Dict									=			len(get_test_dummy_examples()       )
       with tempfile.TemporaryDirectory() as tmp_cache_dir:
             a		:Optional[Any]									=			DummyBeamDataset(cache_dir=_lowerCamelCase   ,    beam_runner='''DirectRunner'''       )
             builder.download_and_prepare()
             self.assertTrue(
                 os.path.exists(
                     os.path.join(_lowerCamelCase   ,    builder.name   ,    '''default'''   ,    '''0.0.0'''   ,    F'''{builder.name}-train.arrow'''       )       )       )
             self.assertDictEqual(builder.info.features   ,    datasets.Features({'''content''': datasets.Value('''string'''       )}       )       )
             a		:str									=			builder.as_dataset()
             self.assertEqual(dset['''train'''].num_rows   ,    _lowerCamelCase       )
             self.assertEqual(dset['''train'''].info.splits['''train'''].num_examples   ,    _lowerCamelCase       )
             self.assertDictEqual(dset['''train'''][0]   ,    get_test_dummy_examples()[0][1]       )
             self.assertDictEqual(
                 dset['''train'''][expected_num_examples - 1]   ,    get_test_dummy_examples()[expected_num_examples - 1][1]       )
             self.assertTrue(
                 os.path.exists(os.path.join(_lowerCamelCase   ,    builder.name   ,    '''default'''   ,    '''0.0.0'''   ,    '''dataset_info.json'''       )       )       )
             del dset




 @require_beam
 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       import apache_beam as beam

       a		:Any									=			beam.io.parquetio.WriteToParquet

       a		:Any									=			len(get_test_dummy_examples()       )
       with tempfile.TemporaryDirectory() as tmp_cache_dir:
             a		:Union[str, Any]									=			DummyBeamDataset(cache_dir=_lowerCamelCase   ,    beam_runner='''DirectRunner'''       )
             with patch('''apache_beam.io.parquetio.WriteToParquet'''       ) as write_parquet_mock:
                   a		:str									=			partial(_lowerCamelCase   ,    num_shards=2       )
                   builder.download_and_prepare()
             self.assertTrue(
                 os.path.exists(
                     os.path.join(
                         _lowerCamelCase   ,    builder.name   ,    '''default'''   ,    '''0.0.0'''   ,    F'''{builder.name}-train-00000-of-00002.arrow'''       )       )       )
             self.assertTrue(
                 os.path.exists(
                     os.path.join(
                         _lowerCamelCase   ,    builder.name   ,    '''default'''   ,    '''0.0.0'''   ,    F'''{builder.name}-train-00000-of-00002.arrow'''       )       )       )
             self.assertDictEqual(builder.info.features   ,    datasets.Features({'''content''': datasets.Value('''string'''       )}       )       )
             a		:List[str]									=			builder.as_dataset()
             self.assertEqual(dset['''train'''].num_rows   ,    _lowerCamelCase       )
             self.assertEqual(dset['''train'''].info.splits['''train'''].num_examples   ,    _lowerCamelCase       )
             # Order is not preserved when sharding, so we just check that all the elements are there
             self.assertListEqual(sorted(dset['''train''']['''content''']       )   ,    sorted(['''foo''', '''bar''', '''foobar''']       )       )
             self.assertTrue(
                 os.path.exists(os.path.join(_lowerCamelCase   ,    builder.name   ,    '''default'''   ,    '''0.0.0'''   ,    '''dataset_info.json'''       )       )       )
             del dset




 @require_beam
 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       with tempfile.TemporaryDirectory() as tmp_cache_dir:
             a		:Dict									=			DummyBeamDataset(cache_dir=_lowerCamelCase       )
             self.assertRaises(datasets.builder.MissingBeamOptions   ,    builder.download_and_prepare       )




 @require_beam
 def 			SCREAMING_SNAKE_CASE__							(						self       ):
       a		:str									=			len(get_test_nested_examples()       )
       with tempfile.TemporaryDirectory() as tmp_cache_dir:
             a		:List[Any]									=			NestedBeamDataset(cache_dir=_lowerCamelCase   ,    beam_runner='''DirectRunner'''       )
             builder.download_and_prepare()
             self.assertTrue(
                 os.path.exists(
                     os.path.join(_lowerCamelCase   ,    builder.name   ,    '''default'''   ,    '''0.0.0'''   ,    F'''{builder.name}-train.arrow'''       )       )       )
             self.assertDictEqual(
                 builder.info.features   ,    datasets.Features({'''a''': datasets.Sequence({'''b''': datasets.Value('''string'''       )}       )}       )       )
             a		:Any									=			builder.as_dataset()
             self.assertEqual(dset['''train'''].num_rows   ,    _lowerCamelCase       )
             self.assertEqual(dset['''train'''].info.splits['''train'''].num_examples   ,    _lowerCamelCase       )
             self.assertDictEqual(dset['''train'''][0]   ,    get_test_nested_examples()[0][1]       )
             self.assertDictEqual(
                 dset['''train'''][expected_num_examples - 1]   ,    get_test_nested_examples()[expected_num_examples - 1][1]       )
             self.assertTrue(
                 os.path.exists(os.path.join(_lowerCamelCase   ,    builder.name   ,    '''default'''   ,    '''0.0.0'''   ,    '''dataset_info.json'''       )       )       )
             del dset





