


from __future__ import annotations

import math
import random
from typing import Any







class lowerCAmelCase_		:

 '''simple docstring'''

 def __init__(			self      ):
       snake_case_ =   []
       snake_case_ =   0
       snake_case_ =   0



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



 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase      ):
       self.data.append(_UpperCAmelCase      )
       snake_case_ =   self.tail + 1



 def 		UpperCamelCase__  (			self      ):
       snake_case_ =   self.data[self.head]
       snake_case_ =   self.head + 1
       return ret



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





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







class lowerCAmelCase_		:

 '''simple docstring'''

 def __init__(			self	,   _UpperCAmelCase      ):
       snake_case_ =   data
       snake_case_ =   None
       snake_case_ =   None
       snake_case_ =   1



 def 		UpperCamelCase__  (			self      ):
       return self.data



 def 		UpperCamelCase__  (			self      ):
       return self.left



 def 		UpperCamelCase__  (			self      ):
       return self.right



 def 		UpperCamelCase__  (			self      ):
       return self.height



 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase      ):
       snake_case_ =   data



 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase      ):
       snake_case_ =   node



 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase      ):
       snake_case_ =   node





 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase      ):
       snake_case_ =   height






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						int:




      """simple docstring"""

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






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )->						int:




      """simple docstring"""

      if a > b:
            return a
      return b






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						MyNode:




      """simple docstring"""

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






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						MyNode:




      """simple docstring"""

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






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						MyNode:




      """simple docstring"""

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






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						MyNode:




      """simple docstring"""

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






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )->						MyNode | None:




      """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
                  snake_case_ =   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_ =   right_rotation(SCREAMING_SNAKE_CASE      )
                  else:
                        snake_case_ =   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:
                  snake_case_ =   node.get_right()
                  assert right_child is not None
                  if data < right_child.get_data():
                        snake_case_ =   rl_rotation(SCREAMING_SNAKE_CASE      )
                  else:
                        snake_case_ =   left_rotation(SCREAMING_SNAKE_CASE      )
      snake_case_ =   my_max(get_height(node.get_right()      )      ,      get_height(node.get_left()      )      ) + 1
      node.set_height(SCREAMING_SNAKE_CASE      )
      return node






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						Any:




      """simple docstring"""

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






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      )->						Any:




      """simple docstring"""

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






def  __lowerCAmelCase					(SCREAMING_SNAKE_CASE      ,      SCREAMING_SNAKE_CASE      )->						MyNode | None:




      """simple docstring"""

      snake_case_ =   root.get_left()
      snake_case_ =   root.get_right()
      if root.get_data() == data:
            if left_child is not None and right_child is not None:
                  snake_case_ =   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:
                  snake_case_ =   left_child
            elif right_child is not None:
                  snake_case_ =   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()      ):
                  snake_case_ =   left_rotation(SCREAMING_SNAKE_CASE      )
            else:
                  snake_case_ =   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()      ):
                  snake_case_ =   right_rotation(SCREAMING_SNAKE_CASE      )
            else:
                  snake_case_ =   lr_rotation(SCREAMING_SNAKE_CASE      )
      snake_case_ =   my_max(get_height(root.get_right()      )      ,      get_height(root.get_left()      )      ) + 1
      root.set_height(SCREAMING_SNAKE_CASE      )
      return root







class lowerCAmelCase_		:

 '''simple docstring'''

 def __init__(			self      ):
       snake_case_ =   None



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



 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase      ):
       print('''insert:''' + str(_UpperCAmelCase      )      )
       snake_case_ =   insert_node(self.root	,   _UpperCAmelCase      )



 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase      ):
       print('''delete:''' + str(_UpperCAmelCase      )      )
       if self.root is None:
             print('''Tree is empty!'''      )
             return
       snake_case_ =   del_node(self.root	,   _UpperCAmelCase      )





 def __str__(			self	,   ):  # a level traversale, gives a more intuitive look on the tree
       snake_case_ =   ''''''
       snake_case_ =   MyQueue()
       q.push(self.root      )
       snake_case_ =   self.get_height()
       if layer == 0:
             return output
       snake_case_ =   0
       while not q.is_empty():
             snake_case_ =   q.pop()
             snake_case_ =   ''' ''' * 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
             snake_case_ =   cnt + 1
             for i in range(1_00      ):
                   if cnt == math.pow(2	,   _UpperCAmelCase      ) - 1:
                         snake_case_ =   layer - 1
                         if layer == 0:
                               output += "\n*************************************"
                               return output
                         output += "\n"
                         break
       output += "\n*************************************"
       return output






def  __lowerCAmelCase					()->						None:




      """simple docstring"""

      import doctest

      doctest.testmod()


if __name__ == "__main__":
   _test()
   UpperCAmelCase    =					AVLtree()
   UpperCAmelCase    =					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 numpy as np

import datasets


UpperCAmelCase    =					"""
Compute the Mahalanobis Distance

Mahalonobis distance is the distance between a point and a distribution.
And not between two distinct points. It is effectively a multivariate equivalent of the Euclidean distance.
It was introduced by Prof. P. C. Mahalanobis in 1936
and has been used in various statistical applications ever since
[source: https://www.machinelearningplus.com/statistics/mahalanobis-distance/]
"""

UpperCAmelCase    =					"""\
@article{de2000mahalanobis,
  title={The mahalanobis distance},
  author={De Maesschalck, Roy and Jouan-Rimbaud, Delphine and Massart, D{\'e}sir{\'e} L},
  journal={Chemometrics and intelligent laboratory systems},
  volume={50},
  number={1},
  pages={1--18},
  year={2000},
  publisher={Elsevier}
}
"""

UpperCAmelCase    =					"""
Args:
    X: List of datapoints to be compared with the `reference_distribution`.
    reference_distribution: List of datapoints from the reference distribution we want to compare to.
Returns:
    mahalanobis: The Mahalonobis distance for each datapoint in `X`.
Examples:

    >>> mahalanobis_metric = datasets.load_metric(\"mahalanobis\")
    >>> results = mahalanobis_metric.compute(reference_distribution=[[0, 1], [1, 0]], X=[[0, 1]])
    >>> print(results)
    {'mahalanobis': array([0.5])}
"""







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

 '''simple docstring'''

 def 		UpperCamelCase__  (			self      ):
       return datasets.MetricInfo(
           description=_DESCRIPTION	,   citation=_CITATION	,   inputs_description=_KWARGS_DESCRIPTION	,   features=datasets.Features(
               {
                   '''X''': datasets.Sequence(datasets.Value('''float'''	,   id='''sequence'''      )	,   id='''X'''      ),
               }      )	,   )





 def 		UpperCamelCase__  (			self	,   _UpperCAmelCase	,   _UpperCAmelCase      ):
       # convert to numpy arrays
       snake_case_ =   np.array(_UpperCAmelCase      )
       snake_case_ =   np.array(_UpperCAmelCase      )

       # Assert that arrays are 2D
       if len(X.shape      ) != 2:
             raise ValueError('''Expected `X` to be a 2D vector'''      )
       if len(reference_distribution.shape      ) != 2:
             raise ValueError('''Expected `reference_distribution` to be a 2D vector'''      )
       if reference_distribution.shape[0] < 2:
             raise ValueError(
                 '''Expected `reference_distribution` to be a 2D vector with more than one element in the first dimension'''      )

       # Get mahalanobis distance for each prediction
       snake_case_ =   X - np.mean(_UpperCAmelCase      )
       snake_case_ =   np.cov(reference_distribution.T      )
       try:
             snake_case_ =   np.linalg.inv(_UpperCAmelCase      )
       except np.linalg.LinAlgError:
             snake_case_ =   np.linalg.pinv(_UpperCAmelCase      )
       snake_case_ =   np.dot(_UpperCAmelCase	,   _UpperCAmelCase      )
       snake_case_ =   np.dot(_UpperCAmelCase	,   X_minus_mu.T      ).diagonal()

       return {"mahalanobis": mahal_dist}