

from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

UpperCamelCase__		   =    TypeVar('''T''')
UpperCamelCase__		   =    TypeVar('''U''')

class 						__snake_case						(							Generic[T, U]     ):
       """simple docstring"""







       def __init__(		self			,   _UpperCamelCase			,   _UpperCamelCase      )			->       Dict:






              """simple docstring"""


              __snake_case					  =       key
              __snake_case					  =       val
              __snake_case					  =       0
              __snake_case					  =       None
              __snake_case					  =       None






       def __repr__(		self      )			->       str:






              """simple docstring"""


              return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
                  self.key			,   self.val			,   self.freq			,   self.next is not None			,   self.prev is not None      )






class 						__snake_case						(							Generic[T, U]     ):
       """simple docstring"""







       def __init__(		self      )			->       None:






              """simple docstring"""


              __snake_case					  =       DoubleLinkedListNode(_UpperCamelCase			,   _UpperCamelCase      )
              __snake_case					  =       DoubleLinkedListNode(_UpperCamelCase			,   _UpperCamelCase      )
              __snake_case  ,						__snake_case					  =       self.rear, self.head


       def __repr__(		self      )			->       str:






              """simple docstring"""


              __snake_case					  =       ["""DoubleLinkedList"""]
              __snake_case					  =       self.head
              while node.next is not None:
                     rep.append(str(_UpperCamelCase      )      )
                     __snake_case					  =       node.next
              rep.append(str(self.rear      )      )
              return ",\n    ".join(_UpperCamelCase      )


       def  a		(		self			,   _UpperCamelCase      )			->       None:






              """simple docstring"""


              __snake_case					  =       self.rear.prev

              # All nodes other than self.head are guaranteed to have non-None previous
              assert previous is not None

              __snake_case					  =       node
              __snake_case					  =       previous
              __snake_case					  =       node
              __snake_case					  =       self.rear
              node.freq += 1
              self._position_node(_UpperCamelCase      )


       def  a		(		self			,   _UpperCamelCase      )			->       None:






              """simple docstring"""


              while node.prev is not None and node.prev.freq > node.freq:
                     # swap node with previous node
                     __snake_case					  =       node.prev

                     __snake_case					  =       previous_node.prev
                     __snake_case					  =       node.prev
                     __snake_case					  =       previous_node
                     __snake_case					  =       node






       def  a		(		self			,   _UpperCamelCase      )			->       DoubleLinkedListNode[T, U] | None:






              """simple docstring"""


              if node.prev is None or node.next is None:
                     return None

              __snake_case					  =       node.next
              __snake_case					  =       node.prev
              __snake_case					  =       None
              __snake_case					  =       None
              return node






class 						__snake_case						(							Generic[T, U]     ):
       """simple docstring"""







       __SCREAMING_SNAKE_CASE													=       {}


       def __init__(		self			,   _UpperCamelCase      )			->       List[str]:






              """simple docstring"""


              __snake_case					  =       DoubleLinkedList()
              __snake_case					  =       capacity
              __snake_case					  =       0
              __snake_case					  =       0
              __snake_case					  =       0
              __snake_case					  =       {}


       def __repr__(		self      )			->       str:






              """simple docstring"""


              return (
                  F'CacheInfo(hits={self.hits}, misses={self.miss}, '
                  F'capacity={self.capacity}, current_size={self.num_keys})'
              )


       def __contains__(		self			,   _UpperCamelCase      )			->       bool:






              """simple docstring"""


              return key in self.cache


       def  a		(		self			,   _UpperCamelCase      )			->       U | None:






              """simple docstring"""


              if key in self.cache:
                     self.hits += 1
                     __snake_case					  =       self.cache[key]
                     __snake_case					  =       self.list.remove(self.cache[key]      )
                     assert node == value_node

                     # node is guaranteed not None because it is in self.cache
                     assert node is not None
                     self.list.add(_UpperCamelCase      )
                     return node.val
              self.miss += 1
              return None


       def  a		(		self			,   _UpperCamelCase			,   _UpperCamelCase      )			->       None:






              """simple docstring"""


              if key not in self.cache:
                     if self.num_keys >= self.capacity:
                            # delete first node when over capacity
                            __snake_case					  =       self.list.head.next

                            # guaranteed to have a non-None first node when num_keys > 0
                            # explain to type checker via assertions
                            assert first_node is not None
                            assert first_node.key is not None
                            assert self.list.remove(_UpperCamelCase      ) is not None
                            # first_node guaranteed to be in list

                            del self.cache[first_node.key]
                            self.num_keys -= 1
                     __snake_case					  =       DoubleLinkedListNode(_UpperCamelCase			,   _UpperCamelCase      )
                     self.list.add(self.cache[key]      )
                     self.num_keys += 1

              else:
                     __snake_case					  =       self.list.remove(self.cache[key]      )
                     assert node is not None  # node guaranteed to be in list
                     __snake_case					  =       value
                     self.list.add(_UpperCamelCase      )






       @classmethod
       def  a		(		cls			,   _UpperCamelCase = 1_28      )			->       Callable[[Callable[[T], U]], Callable[..., U]]:






              """simple docstring"""


              def cache_decorator_inner(_UpperCamelCase      ) -> Callable[..., U]:
                     def cache_decorator_wrapper(*_UpperCamelCase      ) -> U:
                            if func not in cls.decorator_function_to_instance_map:
                                   __snake_case					  =       LFUCache(_UpperCamelCase      )

                            __snake_case					  =       cls.decorator_function_to_instance_map[func].get(args[0]      )
                            if result is None:
                                   __snake_case					  =       func(*_UpperCamelCase      )
                                   cls.decorator_function_to_instance_map[func].put(args[0]			,   _UpperCamelCase      )
                            return result

                     def cache_info() -> LFUCache[T, U]:
                            return cls.decorator_function_to_instance_map[func]

                     setattr(_UpperCamelCase			,   """cache_info"""			,   _UpperCamelCase      )  # noqa: B010

                     return cache_decorator_wrapper

              return cache_decorator_inner


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      )

