


"""simple docstring"""




from typing import List

from packaging import version
from sklearn.metrics import fa_score

import datasets
from datasets.config import PY_VERSION


if PY_VERSION < version.parse('3.8'):
 import importlib_metadata
else:
 import importlib.metadata as importlib_metadata


# TODO(Patrick/Anton)
lowerCamelCase						 =	'\\n'

lowerCamelCase						 =	'\\n    XTREME-S is a benchmark to evaluate universal cross-lingual speech representations in many languages.\n    XTREME-S covers four task families: speech recognition, classification, speech-to-text translation and retrieval.\n'

lowerCamelCase						 =	'\nCompute XTREME-S evaluation metric associated to each XTREME-S dataset.\nArgs:\n    predictions: list of predictions to score.\n        Each translation should be tokenized into a list of tokens.\n    references: list of lists of references for each translation.\n        Each reference should be tokenized into a list of tokens.\n    bleu_kwargs: optional dict of keywords to be passed when computing \'bleu\'.\n        Keywords include Dict can be one of \'smooth_method\', \'smooth_value\', \'force\', \'lowercase\',\n        \'tokenize\', \'use_effective_order\'.\n    wer_kwargs: optional dict of keywords to be passed when computing \'wer\' and \'cer\'.\n        Keywords include \'concatenate_texts\'.\nReturns: depending on the XTREME-S task, one or several of:\n    "accuracy": Accuracy - for \'fleurs-lang_id\', \'minds14\'\n    "f1": F1 score - for \'minds14\'\n    "wer": Word error rate - for \'mls\', \'fleurs-asr\', \'voxpopuli\', \'babel\'\n    "cer": Character error rate - for \'mls\', \'fleurs-asr\', \'voxpopuli\', \'babel\'\n    "bleu": BLEU score according to the `sacrebleu` metric - for \'covost2\'\nExamples:\n\n    >>> xtreme_s_metric = datasets.load_metric(\'xtreme_s\', \'mls\')  # \'mls\', \'voxpopuli\', \'fleurs-asr\' or \'babel\'\n    >>> references = ["it is sunny here", "paper and pen are essentials"]\n    >>> predictions = ["it\'s sunny", "paper pen are essential"]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {\'wer\': 0.56, \'cer\': 0.27}\n\n    >>> xtreme_s_metric = datasets.load_metric(\'xtreme_s\', \'covost2\')\n    >>> references = ["bonjour paris", "il est necessaire de faire du sport de temps en temp"]\n    >>> predictions = ["bonjour paris", "il est important de faire du sport souvent"]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {\'bleu\': 31.65}\n\n    >>> xtreme_s_metric = datasets.load_metric(\'xtreme_s\', \'fleurs-lang_id\')\n    >>> references = [0, 1, 0, 0, 1]\n    >>> predictions = [0, 1, 1, 0, 0]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {\'accuracy\': 0.6}\n\n    >>> xtreme_s_metric = datasets.load_metric(\'xtreme_s\', \'minds14\')\n    >>> references = [0, 1, 0, 0, 1]\n    >>> predictions = [0, 1, 1, 0, 0]\n    >>> results = xtreme_s_metric.compute(predictions=predictions, references=references)\n    >>> print({k: round(v, 2) for k, v in results.items()})\n    {\'f1\': 0.58, \'accuracy\': 0.6}\n'

lowerCamelCase						 =	['fleurs-asr', 'mls', 'voxpopuli', 'babel', 'covost2', 'fleurs-lang_id', 'minds14']
lowerCamelCase						 =	''

try:
 from jiwer import transforms as tr

 lowerCamelCase						 =	True
except ImportError:
 lowerCamelCase						 =	False

if _jiwer_available and version.parse(importlib_metadata.version('jiwer')) < version.parse('2.3.0'):




 class A  (       tr.AbstractTransform					):






       def __init__( self						:					Optional[Any]      ,       lowercase_						:					str = " "			) ->						Dict:
              """simple docstring"""




              _lowerCamelCase	:		List[str]          =sentence_delimiter






       def 	lowerCamelCase	( self						:					List[Any]      ,       lowercase_						:					str			) ->						List[str]:
              """simple docstring"""




              return list(lowercase_			)






       def 	lowerCamelCase	( self						:					Any      ,       lowercase_						:					List[str]			) ->						Dict:
              """simple docstring"""




              _lowerCamelCase	:		Tuple          =[]
              for sent_idx, sentence in enumerate(lowercase_			):
                     chars.extend(self.process_string(lowercase_			)			)
                     if self.sentence_delimiter is not None and self.sentence_delimiter != "" and sent_idx < len(lowercase_			) - 1:
                            chars.append(self.sentence_delimiter			)
              return chars




 lowerCamelCase						 =	tr.Compose(
     [tr.RemoveMultipleSpaces(), tr.Strip(), SentencesToListOfCharacters(SENTENCE_DELIMITER)]
 )
elif _jiwer_available:
 lowerCamelCase						 =	tr.Compose(
     [
         tr.RemoveMultipleSpaces(),
         tr.Strip(),
         tr.ReduceToSingleSentence(SENTENCE_DELIMITER),
         tr.ReduceToListOfListOfChars(),
     ]
 )
else:
 lowerCamelCase						 =	None




def      a_				(   SCREAMING_SNAKE_CASE__ :				Optional[Any]		,      SCREAMING_SNAKE_CASE__ :				Union[str, Any]					):
       '''simple docstring'''





       return float((preds == labels).mean()					)




def      a_				(   SCREAMING_SNAKE_CASE__ :				List[Any]		,      SCREAMING_SNAKE_CASE__ :				List[Any]					):
       '''simple docstring'''





       return {
           "f1": float(fa_score(y_true=SCREAMING_SNAKE_CASE__		,      y_pred=SCREAMING_SNAKE_CASE__		,      average='macro'					)					),
           "accuracy": simple_accuracy(SCREAMING_SNAKE_CASE__		,      SCREAMING_SNAKE_CASE__					),
       }




def      a_				(   SCREAMING_SNAKE_CASE__ :				List[Any]		,      SCREAMING_SNAKE_CASE__ :				List[str]		,      SCREAMING_SNAKE_CASE__ :				Any="exp"		,      SCREAMING_SNAKE_CASE__ :				int=None		,      SCREAMING_SNAKE_CASE__ :				List[Any]=False		,      SCREAMING_SNAKE_CASE__ :				Dict=False		,      SCREAMING_SNAKE_CASE__ :				List[str]=None		,      SCREAMING_SNAKE_CASE__ :				int=False		,      ):
       '''simple docstring'''





       _lowerCamelCase	:		Optional[Any]          =[[label] for label in labels]
       _lowerCamelCase	:		int          =list(SCREAMING_SNAKE_CASE__					)
       try:
              import sacrebleu as scb
       except ImportError:
              raise ValueError(
                  'sacrebleu has to be installed in order to apply the bleu metric for covost2.'
                  'You can install it via `pip install sacrebleu`.'					)

       if version.parse(scb.__version__					) < version.parse('1.4.12'					):
              raise ImportWarning(
                  'To use `sacrebleu`, the module `sacrebleu>=1.4.12` is required, and the current version of `sacrebleu` doesn\'t match this condition.\n'
                  'You can install it with `pip install "sacrebleu>=1.4.12"`.'					)

       _lowerCamelCase	:		Optional[int]          =len(labels[0]					)
       if any(len(SCREAMING_SNAKE_CASE__					) != references_per_prediction for refs in labels					):
              raise ValueError('Sacrebleu requires the same number of references for each prediction'					)
       _lowerCamelCase	:		Dict          =[[refs[i] for refs in labels] for i in range(SCREAMING_SNAKE_CASE__					)]
       _lowerCamelCase	:		Optional[Any]          =scb.corpus_bleu(
           SCREAMING_SNAKE_CASE__		,      SCREAMING_SNAKE_CASE__		,      smooth_method=SCREAMING_SNAKE_CASE__		,      smooth_value=SCREAMING_SNAKE_CASE__		,      force=SCREAMING_SNAKE_CASE__		,      lowercase=SCREAMING_SNAKE_CASE__		,      use_effective_order=SCREAMING_SNAKE_CASE__		,      **({'tokenize': tokenize} if tokenize else {})		,      )
       return {"bleu": output.score}




def      a_				(   SCREAMING_SNAKE_CASE__ :				List[str]		,      SCREAMING_SNAKE_CASE__ :				Union[str, Any]		,      SCREAMING_SNAKE_CASE__ :				str		,      SCREAMING_SNAKE_CASE__ :				Union[str, Any]					):
       '''simple docstring'''





       try:
              from jiwer import compute_measures
       except ImportError:
              raise ValueError(
                  F'''jiwer has to be installed in order to apply the wer metric for {config_name}.'''
                  'You can install it via `pip install jiwer`.'					)

       if concatenate_texts:
              _lowerCamelCase	:		Any          =compute_measures(SCREAMING_SNAKE_CASE__		,      SCREAMING_SNAKE_CASE__					)['wer']

              _lowerCamelCase	:		List[Any]          =compute_measures(SCREAMING_SNAKE_CASE__		,      SCREAMING_SNAKE_CASE__		,      truth_transform=SCREAMING_SNAKE_CASE__		,      hypothesis_transform=SCREAMING_SNAKE_CASE__					)['wer']
              return {"wer": wer, "cer": cer}
       else:

              def compute_score(SCREAMING_SNAKE_CASE__ :				List[str]		,      SCREAMING_SNAKE_CASE__ :				Optional[Any]		,      SCREAMING_SNAKE_CASE__ :				List[Any]="wer"					):
                     _lowerCamelCase	:		Optional[int]          =0
                     _lowerCamelCase	:		Dict          =0
                     for prediction, reference in zip(SCREAMING_SNAKE_CASE__		,      SCREAMING_SNAKE_CASE__					):
                            if score_type == "wer":
                                   _lowerCamelCase	:		Tuple          =compute_measures(SCREAMING_SNAKE_CASE__		,      SCREAMING_SNAKE_CASE__					)
                            elif score_type == "cer":
                                   _lowerCamelCase	:		Any          =compute_measures(
                                       SCREAMING_SNAKE_CASE__		,      SCREAMING_SNAKE_CASE__		,      truth_transform=SCREAMING_SNAKE_CASE__		,      hypothesis_transform=SCREAMING_SNAKE_CASE__					)
                            incorrect += measures["substitutions"] + measures["deletions"] + measures["insertions"]
                            total += measures["substitutions"] + measures["deletions"] + measures["hits"]
                     return incorrect / total

              return {"wer": compute_score(SCREAMING_SNAKE_CASE__		,      SCREAMING_SNAKE_CASE__		,      'wer'					), "cer": compute_score(SCREAMING_SNAKE_CASE__		,      SCREAMING_SNAKE_CASE__		,      'cer'					)}




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






      def 	lowerCamelCase	( self						:					str			) ->						Optional[Any]:
             """simple docstring"""




             if self.config_name not in _CONFIG_NAMES:
                    raise KeyError(F'''You should supply a configuration name selected in {_CONFIG_NAMES}'''			)

             _lowerCamelCase	:		Any          ='int64' if self.config_name in ['fleurs-lang_id', 'minds14'] else 'string'

             return datasets.MetricInfo(
                 description=_DESCRIPTION      ,       citation=_CITATION      ,       inputs_description=_KWARGS_DESCRIPTION      ,       features=datasets.Features(
                     {'predictions': datasets.Value(lowercase_			), 'references': datasets.Value(lowercase_			)}			)      ,       codebase_urls=[]      ,       reference_urls=[]      ,       format='numpy'      ,       )






      def 	lowerCamelCase	( self						:					Optional[Any]      ,       lowercase_						:					Optional[int]      ,       lowercase_						:					List[str]      ,       lowercase_						:					Optional[Any]=None      ,       lowercase_						:					List[Any]=None			) ->						Dict:
             """simple docstring"""




             _lowerCamelCase	:		Optional[Any]          =bleu_kwargs if bleu_kwargs is not None else {}
             _lowerCamelCase	:		Dict          =wer_kwargs if wer_kwargs is not None else {}

             if self.config_name == "fleurs-lang_id":
                    return {"accuracy": simple_accuracy(lowercase_      ,       lowercase_			)}
             elif self.config_name == "minds14":
                    return fa_and_simple_accuracy(lowercase_      ,       lowercase_			)
             elif self.config_name == "covost2":
                    _lowerCamelCase	:		List[str]          =bleu_kwargs.pop('smooth_method'      ,       'exp'			)
                    _lowerCamelCase	:		int          =bleu_kwargs.pop('smooth_value'      ,       lowercase_			)
                    _lowerCamelCase	:		int          =bleu_kwargs.pop('force'      ,       lowercase_			)
                    _lowerCamelCase	:		str          =bleu_kwargs.pop('lowercase'      ,       lowercase_			)
                    _lowerCamelCase	:		int          =bleu_kwargs.pop('tokenize'      ,       lowercase_			)
                    _lowerCamelCase	:		int          =bleu_kwargs.pop('use_effective_order'      ,       lowercase_			)
                    return bleu(
                        preds=lowercase_      ,       labels=lowercase_      ,       smooth_method=lowercase_      ,       smooth_value=lowercase_      ,       force=lowercase_      ,       lowercase=lowercase_      ,       tokenize=lowercase_      ,       use_effective_order=lowercase_      ,       )
             elif self.config_name in ["fleurs-asr", "mls", "voxpopuli", "babel"]:
                    _lowerCamelCase	:		Optional[Any]          =wer_kwargs.pop('concatenate_texts'      ,       lowercase_			)
                    return wer_and_cer(lowercase_      ,       lowercase_      ,       lowercase_      ,       self.config_name			)
             else:
                    raise KeyError(F'''You should supply a configuration name selected in {_CONFIG_NAMES}'''			)






from __future__ import annotations

from abc import abstractmethod
from collections.abc import Iterable
from typing import Generic, Protocol, TypeVar




class A  (       UpperCamelCase_					):






      @abstractmethod
      def __lt__( self						:					T      ,       lowercase_						:					T			) ->						bool:
             """simple docstring"""




             pass






      @abstractmethod
      def __gt__( self						:					T      ,       lowercase_						:					T			) ->						bool:
             """simple docstring"""




             pass






      @abstractmethod
      def __eq__( self						:					T      ,       lowercase_						:					object			) ->						bool:
             """simple docstring"""




             pass




lowerCamelCase						 =	TypeVar('T', bound=Comparable)




class A  (       Generic[T]					):






      def __init__( self						:					Optional[Any]			) ->						None:
             """simple docstring"""




             _lowerCamelCase	:		list[T]          =[]
             _lowerCamelCase	:		int          =0






      def __repr__( self						:					int			) ->						str:
             """simple docstring"""




             return str(self.h			)






      def 	lowerCamelCase	( self						:					str      ,       lowercase_						:					int			) ->						int | None:
             """simple docstring"""




             if child_idx > 0:
                    return (child_idx - 1) // 2
             return None






      def 	lowerCamelCase	( self						:					Union[str, Any]      ,       lowercase_						:					int			) ->						int | None:
             """simple docstring"""




             _lowerCamelCase	:		Dict          =2 * parent_idx + 1
             if left_child_index < self.heap_size:
                    return left_child_index
             return None






      def 	lowerCamelCase	( self						:					List[str]      ,       lowercase_						:					int			) ->						int | None:
             """simple docstring"""




             _lowerCamelCase	:		Optional[int]          =2 * parent_idx + 2
             if right_child_index < self.heap_size:
                    return right_child_index
             return None






      def 	lowerCamelCase	( self						:					Any      ,       lowercase_						:					int			) ->						None:
             """simple docstring"""




             if index < self.heap_size:
                    _lowerCamelCase	:		int          =index
                    _lowerCamelCase	:		Any          =self.left_child_idx(lowercase_			)
                    _lowerCamelCase	:		int          =self.right_child_idx(lowercase_			)
                    # check which child is larger than its parent
                    if left_child is not None and self.h[left_child] > self.h[violation]:
                           _lowerCamelCase	:		str          =left_child
                    if right_child is not None and self.h[right_child] > self.h[violation]:
                           _lowerCamelCase	:		str          =right_child
                    # if violation indeed exists
                    if violation != index:
                           # swap to fix the violation
                           _lowerCamelCase     ,					_lowerCamelCase	:		List[str]          =self.h[index], self.h[violation]
                           # fix the subsequent violation recursively if any
                           self.max_heapify(lowercase_			)






      def 	lowerCamelCase	( self						:					int      ,       lowercase_						:					Iterable[T]			) ->						None:
             """simple docstring"""




             _lowerCamelCase	:		List[Any]          =list(lowercase_			)
             _lowerCamelCase	:		Dict          =len(self.h			)
             if self.heap_size > 1:
                    # max_heapify from right to left but exclude leaves (last level)
                    for i in range(self.heap_size // 2 - 1      ,       -1      ,       -1			):
                           self.max_heapify(lowercase_			)






      def 	lowerCamelCase	( self						:					Dict			) ->						T:
             """simple docstring"""




             if self.heap_size >= 2:
                    _lowerCamelCase	:		Optional[int]          =self.h[0]
                    _lowerCamelCase	:		Optional[int]          =self.h.pop(-1			)
                    self.heap_size -= 1
                    self.max_heapify(0			)
                    return me
             elif self.heap_size == 1:
                    self.heap_size -= 1
                    return self.h.pop(-1			)
             else:
                    raise Exception('Empty heap'			)






      def 	lowerCamelCase	( self						:					Tuple      ,       lowercase_						:					T			) ->						None:
             """simple docstring"""




             self.h.append(lowercase_			)
             _lowerCamelCase	:		List[Any]          =(self.heap_size - 1) // 2
             self.heap_size += 1
             while idx >= 0:
                    self.max_heapify(lowercase_			)
                    _lowerCamelCase	:		Tuple          =(idx - 1) // 2






      def 	lowerCamelCase	( self						:					Optional[Any]			) ->						None:
             """simple docstring"""




             _lowerCamelCase	:		Union[str, Any]          =self.heap_size
             for j in range(size - 1      ,       0      ,       -1			):
                    _lowerCamelCase     ,					_lowerCamelCase	:		Optional[Any]          =self.h[j], self.h[0]
                    self.heap_size -= 1
                    self.max_heapify(0			)
             _lowerCamelCase	:		Union[str, Any]          =size


if __name__ == "__main__":
 import doctest

 # run doc test
 doctest.testmod()

 # demo
 for unsorted in [
     [0],
     [2],
     [3, 5],
     [5, 3],
     [5, 5],
     [0, 0, 0, 0],
     [1, 1, 1, 1],
     [2, 2, 3, 5],
     [0, 2, 2, 3, 5],
     [2, 5, 3, 0, 2, 3, 0, 3],
     [6, 1, 2, 7, 9, 3, 4, 5, 10, 8],
     [1_03, 9, 1, 7, 11, 15, 25, 2_01, 2_09, 1_07, 5],
     [-45, -2, -5],
 ]:
  print(F"""unsorted array: {unsorted}""")

  lowerCamelCase						 =	Heap()
  heap.build_max_heap(unsorted)
  print(F"""after build heap: {heap}""")

  print(F"""max value: {heap.extract_max()}""")
  print(F"""after max value removed: {heap}""")

  heap.insert(1_00)
  print(F"""after new value 100 inserted: {heap}""")

  heap.heap_sort()
  print(F"""heap-sorted array: {heap}\n""")


