

from __future__ import annotations







def 	lowerCamelCase__			(   __A						:list[int]		):


       """simple docstring"""




       if not list_of_ints:
              return []

       if min(__A		) < 0:
              raise ValueError("""All numbers must be positive"""		)

       __snake_case					  =       max(len(bin(__A		)[2:]		) for x in list_of_ints		)
       return _msd_radix_sort(__A  ,__A		)







def 	lowerCamelCase__			(   __A						:list[int]  ,__A						:int		):


       """simple docstring"""




       if bit_position == 0 or len(__A		) in [0, 1]:
              return list_of_ints

       __snake_case					  =       []
       __snake_case					  =       []
       # Split numbers based on bit at bit_position from the right
       for number in list_of_ints:
              if (number >> (bit_position - 1)) & 1:
                     # number has a one at bit bit_position
                     ones.append(__A		)
              else:
                     # number has a zero at bit bit_position
                     zeros.append(__A		)

    # recursively split both lists further
       __snake_case					  =       _msd_radix_sort(__A  ,bit_position - 1		)
       __snake_case					  =       _msd_radix_sort(__A  ,bit_position - 1		)

       # recombine lists
       __snake_case					  =       zeros
       res.extend(__A		)

       return res







def 	lowerCamelCase__			(   __A						:list[int]		):


       """simple docstring"""




       __snake_case					  =       len(__A		)
       if not list_of_ints or length == 1:
              return

       if min(__A		) < 0:
              raise ValueError("""All numbers must be positive"""		)

       __snake_case					  =       max(len(bin(__A		)[2:]		) for x in list_of_ints		)
       _msd_radix_sort_inplace(__A  ,__A  ,0  ,__A		)







def 	lowerCamelCase__			(   __A						:list[int]  ,__A						:int  ,__A						:int  ,__A						:int		):


       """simple docstring"""




       if bit_position == 0 or end_index - begin_index <= 1:
              return

       bit_position -= 1

       __snake_case					  =       begin_index
       __snake_case					  =       end_index - 1
       while i <= j:
              __snake_case					  =       False
              if not (list_of_ints[i] >> bit_position) & 1:
                     # found zero at the beginning
                     i += 1
                     __snake_case					  =       True
              if (list_of_ints[j] >> bit_position) & 1:
                     # found one at the end
                     j -= 1
                     __snake_case					  =       True

              if changed:
                     continue

              __snake_case  ,						__snake_case					  =       list_of_ints[j], list_of_ints[i]
              j -= 1
              if j != i:
                     i += 1

       _msd_radix_sort_inplace(__A  ,__A  ,__A  ,__A		)
       _msd_radix_sort_inplace(__A  ,__A  ,__A  ,__A		)


if __name__ == "__main__":
      import doctest

      doctest.testmod()




import datasets

from .evaluate import (
    apply_no_ans_threshold,
    find_all_best_thresh,
    get_raw_scores,
    make_eval_dict,
    make_qid_to_has_ans,
    merge_eval,
)


UpperCamelCase__		   =    '''\
@inproceedings{Rajpurkar2016SQuAD10,
  title={SQuAD: 100, 000+ Questions for Machine Comprehension of Text},
  author={Pranav Rajpurkar and Jian Zhang and Konstantin Lopyrev and Percy Liang},
  booktitle={EMNLP},
  year={2016}
}
'''

UpperCamelCase__		   =    '''
This metric wrap the official scoring script for version 2 of the Stanford Question
Answering Dataset (SQuAD).

Stanford Question Answering Dataset (SQuAD) is a reading comprehension dataset, consisting of questions posed by
crowdworkers on a set of Wikipedia articles, where the answer to every question is a segment of text, or span,
from the corresponding reading passage, or the question might be unanswerable.

SQuAD2.0 combines the 100,000 questions in SQuAD1.1 with over 50,000 unanswerable questions
written adversarially by crowdworkers to look similar to answerable ones.
To do well on SQuAD2.0, systems must not only answer questions when possible, but also
determine when no answer is supported by the paragraph and abstain from answering.
'''

UpperCamelCase__		   =    '''
Computes SQuAD v2 scores (F1 and EM).
Args:
    predictions: List of triple for question-answers to score with the following elements:
        - the question-answer \'id\' field as given in the references (see below)
        - the text of the answer
        - the probability that the question has no answer
    references: List of question-answers dictionaries with the following key-values:
            - \'id\': id of the question-answer pair (see above),
            - \'answers\': a list of Dict {\'text\': text of the answer as a string}
    no_answer_threshold: float
        Probability threshold to decide that a question has no answer.
Returns:
    \'exact\': Exact match (the normalized answer exactly match the gold answer)
    \'f1\': The F-score of predicted tokens versus the gold answer
    \'total\': Number of score considered
    \'HasAns_exact\': Exact match (the normalized answer exactly match the gold answer)
    \'HasAns_f1\': The F-score of predicted tokens versus the gold answer
    \'HasAns_total\': Number of score considered
    \'NoAns_exact\': Exact match (the normalized answer exactly match the gold answer)
    \'NoAns_f1\': The F-score of predicted tokens versus the gold answer
    \'NoAns_total\': Number of score considered
    \'best_exact\': Best exact match (with varying threshold)
    \'best_exact_thresh\': No-answer probability threshold associated to the best exact match
    \'best_f1\': Best F1 (with varying threshold)
    \'best_f1_thresh\': No-answer probability threshold associated to the best F1
Examples:

    >>> predictions = [{\'prediction_text\': \'1976\', \'id\': \'56e10a3be3433e1400422b22\', \'no_answer_probability\': 0.}]
    >>> references = [{\'answers\': {\'answer_start\': [97], \'text\': [\'1976\']}, \'id\': \'56e10a3be3433e1400422b22\'}]
    >>> squad_v2_metric = datasets.load_metric("squad_v2")
    >>> results = squad_v2_metric.compute(predictions=predictions, references=references)
    >>> print(results)
    {\'exact\': 100.0, \'f1\': 100.0, \'total\': 1, \'HasAns_exact\': 100.0, \'HasAns_f1\': 100.0, \'HasAns_total\': 1, \'best_exact\': 100.0, \'best_exact_thresh\': 0.0, \'best_f1\': 100.0, \'best_f1_thresh\': 0.0}
'''

@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION ,  _KWARGS_DESCRIPTION     )
class 						__snake_case						(							datasets.Metric     ):
       """simple docstring"""







       def  a		(		self      )			->       Tuple:






              """simple docstring"""


              return datasets.MetricInfo(
                  description=_DESCRIPTION			,   citation=_CITATION			,   inputs_description=_KWARGS_DESCRIPTION			,   features=datasets.Features(
                      {
                          """predictions""": {
                              """id""": datasets.Value("""string"""      ),
                              """prediction_text""": datasets.Value("""string"""      ),
                              """no_answer_probability""": datasets.Value("""float32"""      ),
                          },
                          """references""": {
                              """id""": datasets.Value("""string"""      ),
                              """answers""": datasets.features.Sequence(
                                  {"""text""": datasets.Value("""string"""      ), """answer_start""": datasets.Value("""int32"""      )}      ),
                          },
                      }      )			,   codebase_urls=["""https://rajpurkar.github.io/SQuAD-explorer/"""]			,   reference_urls=["""https://rajpurkar.github.io/SQuAD-explorer/"""]			,   )






       def  a		(		self			,   _UpperCamelCase			,   _UpperCamelCase			,   _UpperCamelCase=1.0      )			->       Dict:






              """simple docstring"""


              __snake_case					  =       {p["""id"""]: p["""no_answer_probability"""] for p in predictions}
              __snake_case					  =       [{"""paragraphs""": [{"""qas""": references}]}]
              __snake_case					  =       {p["""id"""]: p["""prediction_text"""] for p in predictions}

              __snake_case					  =       make_qid_to_has_ans(_UpperCamelCase      )  # maps qid to True/False
              __snake_case					  =       [k for k, v in qid_to_has_ans.items() if v]
              __snake_case					  =       [k for k, v in qid_to_has_ans.items() if not v]

              __snake_case  ,						__snake_case					  =       get_raw_scores(_UpperCamelCase			,   _UpperCamelCase      )
              __snake_case					  =       apply_no_ans_threshold(_UpperCamelCase			,   _UpperCamelCase			,   _UpperCamelCase			,   _UpperCamelCase      )
              __snake_case					  =       apply_no_ans_threshold(_UpperCamelCase			,   _UpperCamelCase			,   _UpperCamelCase			,   _UpperCamelCase      )
              __snake_case					  =       make_eval_dict(_UpperCamelCase			,   _UpperCamelCase      )

              if has_ans_qids:
                     __snake_case					  =       make_eval_dict(_UpperCamelCase			,   _UpperCamelCase			,   qid_list=_UpperCamelCase      )
                     merge_eval(_UpperCamelCase			,   _UpperCamelCase			,   """HasAns"""      )
              if no_ans_qids:
                     __snake_case					  =       make_eval_dict(_UpperCamelCase			,   _UpperCamelCase			,   qid_list=_UpperCamelCase      )
                     merge_eval(_UpperCamelCase			,   _UpperCamelCase			,   """NoAns"""      )
              find_all_best_thresh(_UpperCamelCase			,   _UpperCamelCase			,   _UpperCamelCase			,   _UpperCamelCase			,   _UpperCamelCase			,   _UpperCamelCase      )
              return dict(_UpperCamelCase      )

