





from __future__ import annotations

import math
import random
from typing import Any


class 			lowercase				:



						"""simple docstring"""

						def __init__(    self			:		List[Any]					):





										'''simple docstring'''







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







						def 		__UpperCAmelCase       (    self			:		Tuple					):





										'''simple docstring'''







										return self.head == self.tail







						def 		__UpperCAmelCase       (    self			:		List[str] ,				lowerCamelCase_			:		Any					):





										'''simple docstring'''







										self.data.append(lowerCamelCase_					)
										_snake_case :			Union[str, Any]  						=   self.tail + 1







						def 		__UpperCAmelCase       (    self			:		str					):





										'''simple docstring'''







										_snake_case :			List[str]  						=   self.data[self.head]
										_snake_case :			Union[str, Any]  						=   self.head + 1
										return ret







						def 		__UpperCAmelCase       (    self			:		List[str]					):





										'''simple docstring'''







										return self.tail - self.head







						def 		__UpperCAmelCase       (    self			:		List[str]					):





										'''simple docstring'''







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



class 			lowercase				:



						"""simple docstring"""

						def __init__(    self			:		Optional[Any] ,				lowerCamelCase_			:		Any					):





										'''simple docstring'''







										_snake_case :			Tuple  						=   data
										_snake_case :			MyNode | None  						=   None
										_snake_case :			MyNode | None  						=   None
										_snake_case :			int  						=   1







						def 		__UpperCAmelCase       (    self			:		Optional[Any]					):





										'''simple docstring'''







										return self.data







						def 		__UpperCAmelCase       (    self			:		str					):





										'''simple docstring'''







										return self.left







						def 		__UpperCAmelCase       (    self			:		Optional[int]					):





										'''simple docstring'''







										return self.right







						def 		__UpperCAmelCase       (    self			:		Optional[int]					):





										'''simple docstring'''







										return self.height







						def 		__UpperCAmelCase       (    self			:		List[str] ,				lowerCamelCase_			:		Any					):





										'''simple docstring'''







										_snake_case :			int  						=   data







						def 		__UpperCAmelCase       (    self			:		List[str] ,				lowerCamelCase_			:		MyNode | None					):





										'''simple docstring'''







										_snake_case :			int  						=   node







						def 		__UpperCAmelCase       (    self			:		Any ,				lowerCamelCase_			:		MyNode | None					):





										'''simple docstring'''







										_snake_case :			Dict  						=   node







						def 		__UpperCAmelCase       (    self			:		str ,				lowerCamelCase_			:		int					):





										'''simple docstring'''







										_snake_case :			int  						=   height



def       A__(		__lowerCAmelCase ):
				if node is None:
								return 0
				return node.get_height()

def       A__(		__lowerCAmelCase	,			__lowerCAmelCase ):
				if a > b:
								return a
				return b

def       A__(		__lowerCAmelCase ):
				print('left rotation node:'	,			node.get_data() )
				_snake_case :			str  						=   node.get_left()
				assert ret is not None
				node.set_left(ret.get_right() )
				ret.set_right(__lowerCAmelCase )
				_snake_case :			List[Any]  						=   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 ):
				print('right rotation node:'	,			node.get_data() )
				_snake_case :			str  						=   node.get_right()
				assert ret is not None
				node.set_right(ret.get_left() )
				ret.set_left(__lowerCAmelCase )
				_snake_case :			Optional[int]  						=   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 ):
				_snake_case :			Union[str, Any]  						=   node.get_left()
				assert left_child is not None
				node.set_left(left_rotation(__lowerCAmelCase ) )
				return right_rotation(__lowerCAmelCase )

def       A__(		__lowerCAmelCase ):
				_snake_case :			Union[str, Any]  						=   node.get_right()
				assert right_child is not None
				node.set_right(right_rotation(__lowerCAmelCase ) )
				return left_rotation(__lowerCAmelCase )

def       A__(		__lowerCAmelCase	,			__lowerCAmelCase ):
				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 :			int  						=   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 :			Union[str, Any]  						=   right_rotation(__lowerCAmelCase )
												else:
																_snake_case :			str  						=   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 :			List[str]  						=   node.get_right()
												assert right_child is not None
												if data < right_child.get_data():
																_snake_case :			Any  						=   rl_rotation(__lowerCAmelCase )
												else:
																_snake_case :			Any  						=   left_rotation(__lowerCAmelCase )
				_snake_case :			str  						=   my_max(get_height(node.get_right() )	,			get_height(node.get_left() ) ) + 1
				node.set_height(__lowerCAmelCase )
				return node

def       A__(		__lowerCAmelCase ):
				while True:
								_snake_case :			List[str]  						=   root.get_right()
								if right_child is None:
												break
								_snake_case :			Union[str, Any]  						=   right_child
				return root.get_data()

def       A__(		__lowerCAmelCase ):
				while True:
								_snake_case :			Union[str, Any]  						=   root.get_left()
								if left_child is None:
												break
								_snake_case :			Tuple  						=   left_child
				return root.get_data()

def       A__(		__lowerCAmelCase	,			__lowerCAmelCase ):
				_snake_case :			List[Any]  						=   root.get_left()
				_snake_case :			Any  						=   root.get_right()
				if root.get_data() == data:
								if left_child is not None and right_child is not None:
												_snake_case :			List[Any]  						=   get_left_most(__lowerCAmelCase )
												root.set_data(__lowerCAmelCase )
												root.set_right(del_node(__lowerCAmelCase	,			__lowerCAmelCase ) )
								elif left_child is not None:
												_snake_case :			List[str]  						=   left_child
								elif right_child is not None:
												_snake_case :			Optional[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(__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 :			List[Any]  						=   left_rotation(__lowerCAmelCase )
								else:
												_snake_case :			Optional[Any]  						=   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 :			Optional[int]  						=   right_rotation(__lowerCAmelCase )
								else:
												_snake_case :			str  						=   lr_rotation(__lowerCAmelCase )
				_snake_case :			Tuple  						=   my_max(get_height(root.get_right() )	,			get_height(root.get_left() ) ) + 1
				root.set_height(__lowerCAmelCase )
				return root


class 			lowercase				:



						"""simple docstring"""

						def __init__(    self			:		Dict					):





										'''simple docstring'''







										_snake_case :			MyNode | None  						=   None







						def 		__UpperCAmelCase       (    self			:		Any					):





										'''simple docstring'''







										return get_height(self.root					)







						def 		__UpperCAmelCase       (    self			:		Union[str, Any] ,				lowerCamelCase_			:		Any					):





										'''simple docstring'''







										print('insert:' + str(lowerCamelCase_					)					)
										_snake_case :			Any  						=   insert_node(self.root ,				lowerCamelCase_					)







						def 		__UpperCAmelCase       (    self			:		Any ,				lowerCamelCase_			:		Any					):





										'''simple docstring'''







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







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





										'''simple docstring'''







										_snake_case :			Tuple  						=   ''
										_snake_case :			str  						=   MyQueue()
										q.push(self.root					)
										_snake_case :			int  						=   self.get_height()
										if layer == 0:
														return output
										_snake_case :			Union[str, Any]  						=   0
										while not q.is_empty():
														_snake_case :			List[Any]  						=   q.pop()
														_snake_case :			str  						=   ' ' * 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
														_snake_case :			List[str]  						=   cnt + 1
														for i in range(1_00					):
																		if cnt == math.pow(2 ,				lowerCamelCase_					) - 1:
																						_snake_case :			List[str]  						=   layer - 1
																						if layer == 0:
																										output += "\n*************************************"
																										return output
																						output += "\n"
																						break
										output += "\n*************************************"
										return output



def       A__(		):
				import doctest

				doctest.testmod()


if __name__ == "__main__":
		_test()
		lowercase_		:				int				=						AVLtree()
		lowercase_		:				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))













from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_torch_available,
)


lowercase_		:				Optional[int]				=						{
    '''configuration_mega''': ['''MEGA_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''MegaConfig''', '''MegaOnnxConfig'''],
}

try:
		if not is_torch_available():
				raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
		pass
else:
		lowercase_		:				Any				=						[
		    '''MEGA_PRETRAINED_MODEL_ARCHIVE_LIST''',
		    '''MegaForCausalLM''',
		    '''MegaForMaskedLM''',
		    '''MegaForMultipleChoice''',
		    '''MegaForQuestionAnswering''',
		    '''MegaForSequenceClassification''',
		    '''MegaForTokenClassification''',
		    '''MegaModel''',
		    '''MegaPreTrainedModel''',
		]

if TYPE_CHECKING:
		from .configuration_mega import MEGA_PRETRAINED_CONFIG_ARCHIVE_MAP, MegaConfig, MegaOnnxConfig

		try:
				if not is_torch_available():
						raise OptionalDependencyNotAvailable()
		except OptionalDependencyNotAvailable:
				pass
		else:
				from .modeling_mega import (
				    MEGA_PRETRAINED_MODEL_ARCHIVE_LIST,
				    MegaForCausalLM,
				    MegaForMaskedLM,
				    MegaForMultipleChoice,
				    MegaForQuestionAnswering,
				    MegaForSequenceClassification,
				    MegaForTokenClassification,
				    MegaModel,
				    MegaPreTrainedModel,
				)

else:
		import sys

		lowercase_		:				str				=						_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)






