





'''simple docstring'''

from sklearn.metrics import mean_absolute_error

import datasets


lowerCAmelCase__      :   Dict      	=			"\\n@article{scikit-learn,\n title={Scikit-learn: Machine Learning in {P}ython},\n author={Pedregosa, F. and Varoquaux, G. and Gramfort, A. and Michel, V.\n         and Thirion, B. and Grisel, O. and Blondel, M. and Prettenhofer, P.\n         and Weiss, R. and Dubourg, V. and Vanderplas, J. and Passos, A. and\n         Cournapeau, D. and Brucher, M. and Perrot, M. and Duchesnay, E.},\n journal={Journal of Machine Learning Research},\n volume={12},\n pages={2825--2830},\n year={2011}\n}\n"

lowerCAmelCase__      :   Optional[Any]      	=			"\\nMean Absolute Error (MAE) is the mean of the magnitude of difference between the predicted and actual\nvalues.\n"


lowerCAmelCase__      :   Optional[Any]      	=			"\nArgs:\n    predictions: array-like of shape (n_samples,) or (n_samples, n_outputs)\n        Estimated target values.\n    references: array-like of shape (n_samples,) or (n_samples, n_outputs)\n        Ground truth (correct) target values.\n    sample_weight: array-like of shape (n_samples,), default=None\n        Sample weights.\n    multioutput: {\"raw_values\", \"uniform_average\"} or array-like of shape (n_outputs,), default=\"uniform_average\"\n        Defines aggregating of multiple output values. Array-like value defines weights used to average errors.\n\n                 \"raw_values\" : Returns a full set of errors in case of multioutput input.\n\n                 \"uniform_average\" : Errors of all outputs are averaged with uniform weight.\n\nReturns:\n    mae : mean absolute error.\n        If multioutput is \"raw_values\", then mean absolute error is returned for each output separately. If multioutput is \"uniform_average\" or an ndarray of weights, then the weighted average of all output errors is returned.\n        MAE output is non-negative floating point. The best value is 0.0.\nExamples:\n\n    >>> mae_metric = datasets.load_metric(\"mae\")\n    >>> predictions = [2.5, 0.0, 2, 8]\n    >>> references = [3, -0.5, 2, 7]\n    >>> results = mae_metric.compute(predictions=predictions, references=references)\n    >>> print(results)\n    {'mae': 0.5}\n\n    If you're using multi-dimensional lists, then set the config as follows :\n\n    >>> mae_metric = datasets.load_metric(\"mae\", \"multilist\")\n    >>> predictions = [[0.5, 1], [-1, 1], [7, -6]]\n    >>> references = [[0, 2], [-1, 2], [8, -5]]\n    >>> results = mae_metric.compute(predictions=predictions, references=references)\n    >>> print(results)\n    {'mae': 0.75}\n    >>> results = mae_metric.compute(predictions=predictions, references=references, multioutput='raw_values')\n    >>> print(results)\n    {'mae': array([0.5, 1. ])}\n"


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







					"""simple docstring"""






					def 		lowerCamelCase_   (   self       :      Tuple		):







							"""simple docstring"""
							return datasets.MetricInfo(
							    description=_DESCRIPTION		,	citation=_CITATION		,	inputs_description=_KWARGS_DESCRIPTION		,	features=datasets.Features(self._get_feature_types()		)		,	reference_urls=[
							        "https://scikit-learn.org/stable/modules/generated/sklearn.metrics.mean_absolute_error.html"
							    ]		,	)
					def 		lowerCamelCase_   (   self       :      List[str]		):







							"""simple docstring"""
							if self.config_name == "multilist":
									return {
									    "predictions": datasets.Sequence(datasets.Value("float"		)		),
									    "references": datasets.Sequence(datasets.Value("float"		)		),
									}
							else:
									return {
									    "predictions": datasets.Value("float"		),
									    "references": datasets.Value("float"		),
									}






					def 		lowerCamelCase_   (   self       :      Union[str, Any]		,	UpperCAmelCase_       :      str		,	UpperCAmelCase_       :      int		,	UpperCAmelCase_       :      Optional[Any]=None		,	UpperCAmelCase_       :      Optional[Any]="uniform_average"		):







							"""simple docstring"""
							__UpperCAmelCase	:							List[Any]     =     mean_absolute_error(UpperCAmelCase_		,	UpperCAmelCase_		,	sample_weight=UpperCAmelCase_		,	multioutput=UpperCAmelCase_		)

							return {"mae": mae_score}











'''simple docstring'''

class      SCREAMING_SNAKE_CASE__      :







					"""simple docstring"""






					def __init__(   self       :      Tuple		,	UpperCAmelCase_       :      Dict		):







							"""simple docstring"""
							__UpperCAmelCase	:							Any     =     val
							# Number of nodes in left subtree
							__UpperCAmelCase	:							Dict     =     0
							__UpperCAmelCase	:							int     =     None
							__UpperCAmelCase	:							Optional[int]     =     None
							__UpperCAmelCase	:							List[str]     =     None






					def 		lowerCamelCase_   (   self       :      int		,	UpperCAmelCase_       :      Optional[Any]		):







							"""simple docstring"""
							assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

							if self.val < other.val:
									__UpperCAmelCase	:							str     =     self.right
									__UpperCAmelCase	:							Tuple     =     None
									if self.right:
											__UpperCAmelCase	:							int     =     other
									__UpperCAmelCase	:							List[str]     =     other
									__UpperCAmelCase	:							Any     =     self.left_tree_size * 2 + 1
									return self
							else:
									__UpperCAmelCase	:							List[Any]     =     other.right
									__UpperCAmelCase	:							Union[str, Any]     =     None
									if other.right:
											__UpperCAmelCase	:							List[str]     =     self
									__UpperCAmelCase	:							Optional[Any]     =     self
									__UpperCAmelCase	:							Any     =     other.left_tree_size * 2 + 1
									return other






class      SCREAMING_SNAKE_CASE__      :







					"""simple docstring"""






					def __init__(   self       :      Optional[int]		,	UpperCAmelCase_       :      Optional[int]=None		,	UpperCAmelCase_       :      Optional[int]=None		,	UpperCAmelCase_       :      Optional[int]=0		):







							"""simple docstring"""
							__UpperCAmelCase	:							Any     =     heap_size
							__UpperCAmelCase	:							Any     =     bottom_root
							__UpperCAmelCase	:							List[str]     =     min_node
					def 		lowerCamelCase_   (   self       :      List[str]		,	UpperCAmelCase_       :      Dict		):







							"""simple docstring"""

							# Empty heaps corner cases
							if other.size == 0:
									return None
							if self.size == 0:
									__UpperCAmelCase	:							Dict     =     other.size
									__UpperCAmelCase	:							Optional[Any]     =     other.bottom_root
									__UpperCAmelCase	:							str     =     other.min_node
									return None
							# Update size
							__UpperCAmelCase	:							str     =     self.size + other.size

							# Update min.node
							if self.min_node.val > other.min_node.val:
									__UpperCAmelCase	:							Tuple     =     other.min_node
							# Merge

							# Order roots by left_subtree_size
							__UpperCAmelCase	:							int     =     []
							__UpperCAmelCase  ,			__UpperCAmelCase	:							List[str]     =     self.bottom_root, other.bottom_root
							while i or j:
									if i and ((not j) or i.left_tree_size < j.left_tree_size):
											combined_roots_list.append((i, True)		)
											__UpperCAmelCase	:							Optional[Any]     =     i.parent
									else:
											combined_roots_list.append((j, False)		)
											__UpperCAmelCase	:							Tuple     =     j.parent
        # Insert links between them
							for i in range(len(UpperCAmelCase_		) - 1		):
									if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
											__UpperCAmelCase	:							Optional[Any]     =     combined_roots_list[i + 1][0]
											__UpperCAmelCase	:							Any     =     combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
							__UpperCAmelCase	:							List[str]     =     combined_roots_list[0][0]
							while i.parent:
									if (
									    (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
									) or (
									    i.left_tree_size == i.parent.left_tree_size
									    and i.left_tree_size != i.parent.parent.left_tree_size
									):
											# Neighbouring Nodes
											__UpperCAmelCase	:							List[str]     =     i.left
											__UpperCAmelCase	:							Dict     =     i.parent.parent

											# Merging trees
											__UpperCAmelCase	:							Optional[int]     =     i.merge_trees(i.parent		)

											# Updating links
											__UpperCAmelCase	:							Dict     =     previous_node
											__UpperCAmelCase	:							Union[str, Any]     =     next_node
											if previous_node:
													__UpperCAmelCase	:							List[str]     =     i
											if next_node:
													__UpperCAmelCase	:							Dict     =     i
									else:
											__UpperCAmelCase	:							Optional[int]     =     i.parent
        # Updating self.bottom_root
							while i.left:
									__UpperCAmelCase	:							str     =     i.left
							__UpperCAmelCase	:							List[Any]     =     i

							# Update other
							__UpperCAmelCase	:							int     =     self.size
							__UpperCAmelCase	:							Dict     =     self.bottom_root
							__UpperCAmelCase	:							Union[str, Any]     =     self.min_node

							# Return the merged heap
							return self
					def 		lowerCamelCase_   (   self       :      Tuple		,	UpperCAmelCase_       :      Optional[int]		):







							"""simple docstring"""
							if self.size == 0:
									__UpperCAmelCase	:							Optional[Any]     =     Node(UpperCAmelCase_		)
									__UpperCAmelCase	:							Optional[Any]     =     1
									__UpperCAmelCase	:							Optional[Any]     =     self.bottom_root
							else:
									# Create new node
									__UpperCAmelCase	:							Optional[Any]     =     Node(UpperCAmelCase_		)

									# Update size
									self.size += 1

									# update min_node
									if val < self.min_node.val:
											__UpperCAmelCase	:							Optional[int]     =     new_node
									# Put new_node as a bottom_root in heap
									__UpperCAmelCase	:							Union[str, Any]     =     new_node
									__UpperCAmelCase	:							Optional[Any]     =     self.bottom_root
									__UpperCAmelCase	:							List[str]     =     new_node

									# Consecutively merge roots with same left_tree_size
									while (
									    self.bottom_root.parent
									    and self.bottom_root.left_tree_size
									    == self.bottom_root.parent.left_tree_size
									):
											# Next node
											__UpperCAmelCase	:							Optional[Any]     =     self.bottom_root.parent.parent

											# Merge
											__UpperCAmelCase	:							str     =     self.bottom_root.merge_trees(self.bottom_root.parent		)

											# Update Links
											__UpperCAmelCase	:							int     =     next_node
											__UpperCAmelCase	:							Any     =     None
											if next_node:
													__UpperCAmelCase	:							Any     =     self.bottom_root
					def 		lowerCamelCase_   (   self       :      Any		):







							"""simple docstring"""
							return self.min_node.val
					def 		lowerCamelCase_   (   self       :      str		):







							"""simple docstring"""
							return self.size == 0
					def 		lowerCamelCase_   (   self       :      int		):







							"""simple docstring"""
							__UpperCAmelCase	:							str     =     self.min_node.val

							# Last element in heap corner case
							if self.size == 1:
									# Update size
									__UpperCAmelCase	:							Optional[int]     =     0

									# Update bottom root
									__UpperCAmelCase	:							List[str]     =     None

									# Update min_node
									__UpperCAmelCase	:							int     =     None

									return min_value
							# No right subtree corner case
							# The structure of the tree implies that this should be the bottom root
							# and there is at least one other root
							if self.min_node.right is None:
									# Update size
									self.size -= 1

									# Update bottom root
									__UpperCAmelCase	:							Union[str, Any]     =     self.bottom_root.parent
									__UpperCAmelCase	:							str     =     None

									# Update min_node
									__UpperCAmelCase	:							int     =     self.bottom_root
									__UpperCAmelCase	:							int     =     self.bottom_root.parent
									while i:
											if i.val < self.min_node.val:
													__UpperCAmelCase	:							Union[str, Any]     =     i
											__UpperCAmelCase	:							Optional[int]     =     i.parent
									return min_value
							# General case
							# Find the BinomialHeap of the right subtree of min_node
							__UpperCAmelCase	:							Optional[int]     =     self.min_node.right
							__UpperCAmelCase	:							List[Any]     =     None
							__UpperCAmelCase	:							Optional[int]     =     bottom_of_new
							__UpperCAmelCase	:							Union[str, Any]     =     1

							# Size, min_node and bottom_root
							while bottom_of_new.left:
									__UpperCAmelCase	:							str     =     size_of_new * 2 + 1
									__UpperCAmelCase	:							List[str]     =     bottom_of_new.left
									if bottom_of_new.val < min_of_new.val:
											__UpperCAmelCase	:							Union[str, Any]     =     bottom_of_new
        # Corner case of single root on top left path
							if (not self.min_node.left) and (not self.min_node.parent):
									__UpperCAmelCase	:							Optional[Any]     =     size_of_new
									__UpperCAmelCase	:							List[str]     =     bottom_of_new
									__UpperCAmelCase	:							List[Any]     =     min_of_new
									# print("Single root, multiple nodes case")
									return min_value
							# Remaining cases
							# Construct heap of right subtree
							__UpperCAmelCase	:							Union[str, Any]     =     BinomialHeap(
							    bottom_root=UpperCAmelCase_		,	min_node=UpperCAmelCase_		,	heap_size=UpperCAmelCase_		)

							# Update size
							__UpperCAmelCase	:							Any     =     self.size - 1 - size_of_new

							# Neighbour nodes
							__UpperCAmelCase	:							Union[str, Any]     =     self.min_node.left
							__UpperCAmelCase	:							List[str]     =     self.min_node.parent

							# Initialize new bottom_root and min_node
							__UpperCAmelCase	:							Optional[Any]     =     previous_node or next_node
							__UpperCAmelCase	:							Optional[Any]     =     next_node

							# Update links of previous_node and search below for new min_node and
							# bottom_root
							if previous_node:
									__UpperCAmelCase	:							List[str]     =     next_node

									# Update bottom_root and search for min_node below
									__UpperCAmelCase	:							List[str]     =     previous_node
									__UpperCAmelCase	:							int     =     previous_node
									while self.bottom_root.left:
											__UpperCAmelCase	:							Dict     =     self.bottom_root.left
											if self.bottom_root.val < self.min_node.val:
													__UpperCAmelCase	:							Union[str, Any]     =     self.bottom_root
							if next_node:
									__UpperCAmelCase	:							Tuple     =     previous_node

									# Search for new min_node above min_node
									__UpperCAmelCase	:							Optional[int]     =     next_node
									while i:
											if i.val < self.min_node.val:
													__UpperCAmelCase	:							List[Any]     =     i
											__UpperCAmelCase	:							List[Any]     =     i.parent
        # Merge heaps
							self.merge_heaps(UpperCAmelCase_		)

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







							"""simple docstring"""
							__UpperCAmelCase	:							Tuple     =     self.bottom_root
							while top_root.parent:
									__UpperCAmelCase	:							Optional[int]     =     top_root.parent
							# preorder
							__UpperCAmelCase	:							Union[str, Any]     =     []
							self.__traversal(UpperCAmelCase_		,	UpperCAmelCase_		)
							return heap_pre_order
					def 		lowerCamelCase_   (   self       :      Optional[int]		,	UpperCAmelCase_       :      Optional[Any]		,	UpperCAmelCase_       :      int		,	UpperCAmelCase_       :      Dict=0		):







							"""simple docstring"""
							if curr_node:
									preorder.append((curr_node.val, level)		)
									self.__traversal(curr_node.left		,	UpperCAmelCase_		,	level + 1		)
									self.__traversal(curr_node.right		,	UpperCAmelCase_		,	level + 1		)
							else:
									preorder.append(("#", level)		)






					def __str__(   self       :      Optional[int]		):







							"""simple docstring"""
							if self.is_empty():
									return ""
							__UpperCAmelCase	:							Optional[Any]     =     self.pre_order()

							return "\n".join(("-" * level + str(UpperCAmelCase_		)) for value, level in preorder_heap		)


# Unit Tests
if __name__ == "__main__":
			import doctest

			doctest.testmod()




