

from scipy.stats import pearsonr

import datasets


__A     :					str     = "\nPearson correlation coefficient and p-value for testing non-correlation.\nThe Pearson correlation coefficient measures the linear relationship between two datasets. The calculation of the p-value relies on the assumption that each dataset is normally distributed. Like other correlation coefficients, this one varies between -1 and +1 with 0 implying no correlation. Correlations of -1 or +1 imply an exact linear relationship. Positive correlations imply that as x increases, so does y. Negative correlations imply that as x increases, y decreases.\nThe p-value roughly indicates the probability of an uncorrelated system producing datasets that have a Pearson correlation at least as extreme as the one computed from these datasets.\n"


__A     :					int     = "\nArgs:\n    predictions (`list` of `int`): Predicted class labels, as returned by a model.\n    references (`list` of `int`): Ground truth labels.\n    return_pvalue (`boolean`): If `True`, returns the p-value, along with the correlation coefficient. If `False`, returns only the correlation coefficient. Defaults to `False`.\n\nReturns:\n    pearsonr (`float`): Pearson correlation coefficient. Minimum possible value is -1. Maximum possible value is 1. Values of 1 and -1 indicate exact linear positive and negative relationships, respectively. A value of 0 implies no correlation.\n    p-value (`float`): P-value, which roughly indicates the probability of an The p-value roughly indicates the probability of an uncorrelated system producing datasets that have a Pearson correlation at least as extreme as the one computed from these datasets. Minimum possible value is 0. Maximum possible value is 1. Higher values indicate higher probabilities.\n\nExamples:\n\n    Example 1-A simple example using only predictions and references.\n        >>> pearsonr_metric = datasets.load_metric(\"pearsonr\")\n        >>> results = pearsonr_metric.compute(predictions=[10, 9, 2.5, 6, 4], references=[1, 2, 3, 4, 5])\n        >>> print(round(results['pearsonr'], 2))\n        -0.74\n\n    Example 2-The same as Example 1, but that also returns the `p-value`.\n        >>> pearsonr_metric = datasets.load_metric(\"pearsonr\")\n        >>> results = pearsonr_metric.compute(predictions=[10, 9, 2.5, 6, 4], references=[1, 2, 3, 4, 5], return_pvalue=True)\n        >>> print(sorted(list(results.keys())))\n        ['p-value', 'pearsonr']\n        >>> print(round(results['pearsonr'], 2))\n        -0.74\n        >>> print(round(results['p-value'], 2))\n        0.15\n"


__A     :					List[Any]     = "\n@article{2020SciPy-NMeth,\nauthor  = {Virtanen, Pauli and Gommers, Ralf and Oliphant, Travis E. and\n      Haberland, Matt and Reddy, Tyler and Cournapeau, David and\n      Burovski, Evgeni and Peterson, Pearu and Weckesser, Warren and\n      Bright, Jonathan and {van der Walt}, St{\'e}fan J. and\n      Brett, Matthew and Wilson, Joshua and Millman, K. Jarrod and\n      Mayorov, Nikolay and Nelson, Andrew R. J. and Jones, Eric and\n      Kern, Robert and Larson, Eric and Carey, C J and\n      Polat, Ilhan and Feng, Yu and Moore, Eric W. and\n      {VanderPlas}, Jake and Laxalde, Denis and Perktold, Josef and\n      Cimrman, Robert and Henriksen, Ian and Quintero, E. A. and\n      Harris, Charles R. and Archibald, Anne M. and\n      Ribeiro, Antonio H. and Pedregosa, Fabian and\n      {van Mulbregt}, Paul and {SciPy 1.0 Contributors}},\ntitle   = {{{SciPy} 1.0: Fundamental Algorithms for Scientific\n      Computing in Python}},\njournal = {Nature Methods},\nyear    = {2020},\nvolume  = {17},\npages   = {261--272},\nadsurl  = {https://rdcu.be/b08Wh},\ndoi = {10.1038/s41592-019-0686-2},\n}\n"


@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION      ,  _KWARGS_DESCRIPTION)
class        _SCREAMING_SNAKE_CASE	(   datasets.Metric):







						def     _snake_case							(       self				)->				Union[str, Any]:
													return datasets.MetricInfo(
													    description=_DESCRIPTION			,		citation=_CITATION			,		inputs_description=_KWARGS_DESCRIPTION			,		features=datasets.Features(
													        {
													            """predictions""": datasets.Value("""float"""				),
													            """references""": datasets.Value("""float"""				),
													        }				)			,		reference_urls=["""https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.pearsonr.html"""]			,		)







						def     _snake_case							(       self			,		_SCREAMING_SNAKE_CASE			,		_SCREAMING_SNAKE_CASE			,		_SCREAMING_SNAKE_CASE=False				)->				Tuple:
													if return_pvalue:
																				lowerCamelCase_				     =pearsonr(lowercase_			,		lowercase_				)
																				return {"pearsonr": results[0], "p-value": results[1]}
													else:
																				return {"pearsonr": float(pearsonr(lowercase_			,		lowercase_				)[0]				)}

'''simple docstring'''




from __future__ import annotations

import math
import random
from typing import Any





class     __magic_name__						:







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







			def 	SCREAMING_SNAKE_CASE_     (	self				:  int    ):
										return self.head == self.tail







			def 	SCREAMING_SNAKE_CASE_     (	self				:  List[str]				,			lowercase_				:  Any    ):
										self.data.append(lowercase_    )
										lowercase_					:			Optional[Any]										=       self.tail + 1







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Optional[Any]    ):
										lowercase_					:			List[Any]										=       self.data[self.head]
										lowercase_					:			Optional[int]										=       self.head + 1
										return ret







			def 	SCREAMING_SNAKE_CASE_     (	self				:  List[str]    ):
										return self.tail - self.head







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





class     __magic_name__						:







			def __init__(	self				:  Any				,			lowercase_				:  Any    ):
										lowercase_					:			Optional[Any]										=       data
										lowercase_					:			MyNode | None										=       None
										lowercase_					:			MyNode | None										=       None
										lowercase_					:			int										=       1







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Tuple    ):
										return self.data







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Union[str, Any]    ):
										return self.left







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Dict    ):
										return self.right







			def 	SCREAMING_SNAKE_CASE_     (	self				:  str    ):
										return self.height







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Any				,			lowercase_				:  Any    ):
										lowercase_					:			Dict										=       data







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Union[str, Any]				,			lowercase_				:  MyNode | None    ):
										lowercase_					:			Optional[Any]										=       node







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Tuple				,			lowercase_				:  MyNode | None    ):
										lowercase_					:			str										=       node







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Any				,			lowercase_				:  int    ):
										lowercase_					:			Tuple										=       height




def 							lowerCamelCase	(      UpperCAmelCase__       :					MyNode | None )			->      int:
							if node is None:
														return 0
							return node.get_height()




def 							lowerCamelCase	(      UpperCAmelCase__       :					int      ,      UpperCAmelCase__       :					int )			->      int:
							if a > b:
														return a
							return b




def 							lowerCamelCase	(      UpperCAmelCase__       :					MyNode )			->      MyNode:
							print("""left rotation node:"""      ,      node.get_data() )
							lowercase_					:			Union[str, Any]										=       node.get_left()
							assert ret is not None
							node.set_left(ret.get_right() )
							ret.set_right(UpperCAmelCase__ )
							lowercase_					:			Any										=       my_max(get_height(node.get_right() )      ,      get_height(node.get_left() ) ) + 1
							node.set_height(UpperCAmelCase__ )
							lowercase_					:			Optional[int]										=       my_max(get_height(ret.get_right() )      ,      get_height(ret.get_left() ) ) + 1
							ret.set_height(UpperCAmelCase__ )
							return ret




def 							lowerCamelCase	(      UpperCAmelCase__       :					MyNode )			->      MyNode:
							print("""right rotation node:"""      ,      node.get_data() )
							lowercase_					:			Dict										=       node.get_right()
							assert ret is not None
							node.set_right(ret.get_left() )
							ret.set_left(UpperCAmelCase__ )
							lowercase_					:			Tuple										=       my_max(get_height(node.get_right() )      ,      get_height(node.get_left() ) ) + 1
							node.set_height(UpperCAmelCase__ )
							lowercase_					:			str										=       my_max(get_height(ret.get_right() )      ,      get_height(ret.get_left() ) ) + 1
							ret.set_height(UpperCAmelCase__ )
							return ret




def 							lowerCamelCase	(      UpperCAmelCase__       :					MyNode )			->      MyNode:
							lowercase_					:			Optional[Any]										=       node.get_left()
							assert left_child is not None
							node.set_left(left_rotation(UpperCAmelCase__ ) )
							return right_rotation(UpperCAmelCase__ )




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




def 							lowerCamelCase	(      UpperCAmelCase__       :					MyNode )			->      Any:
							while True:
														lowercase_					:			Any										=       root.get_right()
														if right_child is None:
																					break
														lowercase_					:			List[str]										=       right_child
							return root.get_data()




def 							lowerCamelCase	(      UpperCAmelCase__       :					MyNode )			->      Any:
							while True:
														lowercase_					:			List[Any]										=       root.get_left()
														if left_child is None:
																					break
														lowercase_					:			str										=       left_child
							return root.get_data()




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





class     __magic_name__						:







			def __init__(	self				:  List[str]    ):
										lowercase_					:			MyNode | None										=       None







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Optional[int]    ):
										return get_height(self.root    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Any				,			lowercase_				:  Any    ):
										print("""insert:""" + str(lowercase_    )    )
										lowercase_					:			Dict										=       insert_node(self.root				,			lowercase_    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Any				,			lowercase_				:  Any    ):
										print("""delete:""" + str(lowercase_    )    )
										if self.root is None:
																	print("""Tree is empty!"""    )
																	return
										lowercase_					:			int										=       del_node(self.root				,			lowercase_    )







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




def 							lowerCamelCase	(      )			->      None:
							import doctest

							doctest.testmod()


if __name__ == "__main__":
						_test()
						_lowercase						: Optional[Any]						=						AVLtree()
						_lowercase						: Optional[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))





