

"""simple docstring"""






import numpy as np

import datasets


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

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

__lowerCamelCase										=		"\nArgs:\n    X: List of datapoints to be compared with the `reference_distribution`.\n    reference_distribution: List of datapoints from the reference distribution we want to compare to.\nReturns:\n    mahalanobis: The Mahalonobis distance for each datapoint in `X`.\nExamples:\n\n    >>> mahalanobis_metric = datasets.load_metric(\"mahalanobis\")\n    >>> results = mahalanobis_metric.compute(reference_distribution=[[0, 1], [1, 0]], X=[[0, 1]])\n    >>> print(results)\n    {'mahalanobis': array([0.5])}\n"
@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION   , _KWARGS_DESCRIPTION     )
class        _lowercase					(     datasets.Metric     ):







     def 	lowerCAmelCase__    (      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 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      __magic_name__     =      np.array(UpperCAmelCase__       )
      __magic_name__     =      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
      __magic_name__     =      X - np.mean(UpperCAmelCase__       )
      __magic_name__     =      np.cov(reference_distribution.T       )
      try:
       __magic_name__     =      np.linalg.inv(UpperCAmelCase__       )
      except np.linalg.LinAlgError:
       __magic_name__     =      np.linalg.pinv(UpperCAmelCase__       )
      __magic_name__     =      np.dot(UpperCAmelCase__ ,						UpperCAmelCase__       )
      __magic_name__     =      np.dot(UpperCAmelCase__ ,						X_minus_mu.T       ).diagonal()

      return {"mahalanobis": mahal_dist}




"""simple docstring"""






from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

__lowerCamelCase										=		TypeVar("T")





def 	lowercase      (   __UpperCamelCase						) ->      int:
 return (position - 1) // 2





def 	lowercase      (   __UpperCamelCase						) ->      int:
 return (2 * position) + 1





def 	lowercase      (   __UpperCamelCase						) ->      int:
 return (2 * position) + 2
class        _lowercase					(     Generic[T]     ):







     def __init__(      self       ):
      __magic_name__     =      []
      __magic_name__     =      {}
      __magic_name__     =      0







     def __len__(      self       ):
      return self.elements







     def __repr__(      self       ):
      return str(self.heap       )







     def 	lowerCAmelCase__    (      self       ):
      # Check if the priority queue is empty
      return self.elements == 0







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      # Add an element with given priority to the queue
      self.heap.append((elem, weight)       )
      __magic_name__     =      self.elements
      self.elements += 1
      self._bubble_up(UpperCamelCase_       )







     def 	lowerCAmelCase__    (      self       ):
      # Remove and return the element with lowest weight (highest priority)
      if self.elements > 1:
       self._swap_nodes(0 ,						self.elements - 1       )
      __magic_name__   ,						__magic_name__     =      self.heap.pop()
      del self.position_map[elem]
      self.elements -= 1
      if self.elements > 0:
       __magic_name__   ,						__magic_name__     =      self.heap[0]
       self._bubble_down(UpperCamelCase_       )
      return elem







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      # Update the weight of the given key
      __magic_name__     =      self.position_map[elem]
      __magic_name__     =      (elem, weight)
      if position > 0:
       __magic_name__     =      get_parent_position(UpperCamelCase_       )
       __magic_name__   ,						__magic_name__     =      self.heap[parent_position]
       if parent_weight > weight:
        self._bubble_up(UpperCamelCase_       )
       else:
        self._bubble_down(UpperCamelCase_       )
      else:
       self._bubble_down(UpperCamelCase_       )







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_       ):
      # Place a node at the proper position (upward movement) [to be used internally
      # only]
      __magic_name__     =      self.position_map[elem]
      if curr_pos == 0:
       return None
      __magic_name__     =      get_parent_position(UpperCamelCase_       )
      __magic_name__   ,						__magic_name__     =      self.heap[curr_pos]
      __magic_name__   ,						__magic_name__     =      self.heap[parent_position]
      if parent_weight > weight:
       self._swap_nodes(UpperCamelCase_ ,						UpperCamelCase_       )
       return self._bubble_up(UpperCamelCase_       )
      return None







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_       ):
      # Place a node at the proper position (downward movement) [to be used
      # internally only]
      __magic_name__     =      self.position_map[elem]
      __magic_name__   ,						__magic_name__     =      self.heap[curr_pos]
      __magic_name__     =      get_child_left_position(UpperCamelCase_       )
      __magic_name__     =      get_child_right_position(UpperCamelCase_       )
      if child_left_position < self.elements and child_right_position < self.elements:
       __magic_name__   ,						__magic_name__     =      self.heap[child_left_position]
       __magic_name__   ,						__magic_name__     =      self.heap[child_right_position]
       if child_right_weight < child_left_weight and child_right_weight < weight:
        self._swap_nodes(UpperCamelCase_ ,						UpperCamelCase_       )
        return self._bubble_down(UpperCamelCase_       )
      if child_left_position < self.elements:
       __magic_name__   ,						__magic_name__     =      self.heap[child_left_position]
       if child_left_weight < weight:
        self._swap_nodes(UpperCamelCase_ ,						UpperCamelCase_       )
        return self._bubble_down(UpperCamelCase_       )
      else:
       return None
      if child_right_position < self.elements:
       __magic_name__   ,						__magic_name__     =      self.heap[child_right_position]
       if child_right_weight < weight:
        self._swap_nodes(UpperCamelCase_ ,						UpperCamelCase_       )
        return self._bubble_down(UpperCamelCase_       )
      return None







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      # Swap the nodes at the given positions
      __magic_name__     =      self.heap[nodea_pos][0]
      __magic_name__     =      self.heap[nodea_pos][0]
      __magic_name__   ,						__magic_name__     =      (
          self.heap[nodea_pos],
          self.heap[nodea_pos],
      )
      __magic_name__     =      nodea_pos
      __magic_name__     =      nodea_pos


class        _lowercase					(     Generic[T]     ):







     def __init__(      self       ):
      __magic_name__     =      {}
      __magic_name__     =      0







     def __repr__(      self       ):
      return str(self.connections       )







     def __len__(      self       ):
      return self.nodes







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_       ):
      # Add a node in the graph if it is not in the graph
      if node not in self.connections:
       __magic_name__     =      {}
       self.nodes += 1







     def 	lowerCAmelCase__    (      self ,						UpperCamelCase_ ,						UpperCamelCase_ ,						UpperCamelCase_       ):
      # Add an edge between 2 nodes in the graph
      self.add_node(UpperCamelCase_       )
      self.add_node(UpperCamelCase_       )
      __magic_name__     =      weight
      __magic_name__     =      weight





def 	lowercase      (   __UpperCamelCase      ,   ) ->      tuple[dict[T, int], dict[T, T | None]]:
 __magic_name__     =      {node: maxsize for node in graph.connections}
 __magic_name__     =      {node: None for node in graph.connections}

 __magic_name__     =      MinPriorityQueue()
 for node, weight in dist.items():
  priority_queue.push(__UpperCamelCase      ,   __UpperCamelCase						)

 if priority_queue.is_empty():
  return dist, parent

 # initialization
 __magic_name__     =      priority_queue.extract_min()
 __magic_name__     =      0
 for neighbour in graph.connections[node]:
  if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
   __magic_name__     =      dist[node] + graph.connections[node][neighbour]
   priority_queue.update_key(__UpperCamelCase      ,   dist[neighbour]						)
   __magic_name__     =      node

    # running prim's algorithm
 while not priority_queue.is_empty():
  __magic_name__     =      priority_queue.extract_min()
  for neighbour in graph.connections[node]:
   if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
    __magic_name__     =      dist[node] + graph.connections[node][neighbour]
    priority_queue.update_key(__UpperCamelCase      ,   dist[neighbour]						)
    __magic_name__     =      node
 return dist, parent

