


"""simple docstring"""
from __future__ import annotations

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

UpperCAmelCase				=						TypeVar("""T""")
UpperCAmelCase				=						TypeVar("""U""")




class 	lowercase__				(					Generic[T, U]				):





   def __init__(							self      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)  ->  Union[str, Any]:
      _lowerCamelCase	:					Any   =		key
      _lowerCamelCase	:					Any   =		val
      _lowerCamelCase	:					DoubleLinkedListNode[T, U] | None   =		None
      _lowerCamelCase	:					DoubleLinkedListNode[T, U] | None   =		None





   def __repr__(							self)  ->  str:
      return (
          F'Node: key: {self.key}, val: {self.val}, '
          F'has next: {bool(self.next)}, has prev: {bool(self.prev)}'
      )







class 	lowercase__				(					Generic[T, U]				):





   def __init__(							self)  ->  None:
      _lowerCamelCase	:					DoubleLinkedListNode[T, U]   =		DoubleLinkedListNode(SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)
      _lowerCamelCase	:					DoubleLinkedListNode[T, U]   =		DoubleLinkedListNode(SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)
      _lowerCamelCase   ,    _lowerCamelCase	:					Optional[int]   =		self.rear, self.head





   def __repr__(							self)  ->  str:
      _lowerCamelCase	:					Union[str, Any]   =		["""DoubleLinkedList"""]
      _lowerCamelCase	:					List[Any]   =		self.head
      while node.next is not None:
         rep.append(str(SCREAMING_SNAKE_CASE))
         _lowerCamelCase	:					Optional[Any]   =		node.next
      rep.append(str(self.rear))
      return ",\n    ".join(SCREAMING_SNAKE_CASE)





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE)  ->  None:
      _lowerCamelCase	:					Dict   =		self.rear.prev

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

      _lowerCamelCase	:					Optional[int]   =		node
      _lowerCamelCase	:					List[str]   =		previous
      _lowerCamelCase	:					Dict   =		node
      _lowerCamelCase	:					str   =		self.rear





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE)  ->  DoubleLinkedListNode[T, U] | None:

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

      _lowerCamelCase	:					Dict   =		node.next
      _lowerCamelCase	:					int   =		node.prev
      _lowerCamelCase	:					Union[str, Any]   =		None
      _lowerCamelCase	:					Any   =		None
      return node







class 	lowercase__				(					Generic[T, U]				):
   __UpperCAmelCase							       =					{}





   def __init__(							self      ,   SCREAMING_SNAKE_CASE)  ->  str:
      _lowerCamelCase	:					DoubleLinkedList[T, U]   =		DoubleLinkedList()
      _lowerCamelCase	:					Optional[int]   =		capacity
      _lowerCamelCase	:					int   =		0
      _lowerCamelCase	:					Union[str, Any]   =		0
      _lowerCamelCase	:					Optional[Any]   =		0
      _lowerCamelCase	:					dict[T, DoubleLinkedListNode[T, U]]   =		{}





   def __repr__(							self)  ->  str:
      return (
          F'CacheInfo(hits={self.hits}, misses={self.miss}, '
          F'capacity={self.capacity}, current size={self.num_keys})'
      )





   def __contains__(							self      ,   SCREAMING_SNAKE_CASE)  ->  bool:
      return key in self.cache





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE)  ->  U | None:
      # Note: pythonic interface would throw KeyError rather than return None

      if key in self.cache:
         self.hits += 1
         _lowerCamelCase	:					DoubleLinkedListNode[T, U]   =		self.cache[key]
         _lowerCamelCase	:					Dict   =		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(SCREAMING_SNAKE_CASE)
         return node.val
      self.miss += 1
      return None





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)  ->  None:

      if key not in self.cache:
         if self.num_keys >= self.capacity:
            # delete first node (oldest) when over capacity
            _lowerCamelCase	:					int   =		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(SCREAMING_SNAKE_CASE) is not None
            )  # node guaranteed to be in list assert node.key is not None

            del self.cache[first_node.key]
            self.num_keys -= 1
         _lowerCamelCase	:					str   =		DoubleLinkedListNode(SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE)
         self.list.add(self.cache[key])
         self.num_keys += 1

      else:
         # bump node to the end of the list, update value
         _lowerCamelCase	:					List[str]   =		self.list.remove(self.cache[key])
         assert node is not None  # node guaranteed to be in list
         _lowerCamelCase	:					Union[str, Any]   =		value
         self.list.add(SCREAMING_SNAKE_CASE)





   @classmethod
   def 		UpperCamelCase_  (							cls      ,   SCREAMING_SNAKE_CASE = 128)  ->  Callable[[Callable[[T], U]], Callable[..., U]]:

      def cache_decorator_inner(SCREAMING_SNAKE_CASE) -> Callable[..., U]:
         def cache_decorator_wrapper(*SCREAMING_SNAKE_CASE) -> U:
            if func not in cls.decorator_function_to_instance_map:
               _lowerCamelCase	:					Union[str, Any]   =		LRUCache(SCREAMING_SNAKE_CASE)

            _lowerCamelCase	:					Union[str, Any]   =		cls.decorator_function_to_instance_map[func].get(args[0])
            if result is None:
               _lowerCamelCase	:					Any   =		func(*SCREAMING_SNAKE_CASE)
               cls.decorator_function_to_instance_map[func].put(args[0]      ,   SCREAMING_SNAKE_CASE)
            return result

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

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

         return cache_decorator_wrapper

      return cache_decorator_inner


if __name__ == "__main__":
 import doctest

 doctest.testmod()





"""simple docstring"""
from typing import Dict, List

from nltk.translate import gleu_score

import datasets
from datasets import MetricInfo


UpperCAmelCase				=						"""\
@misc{wu2016googles,
      title={Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation},
      author={Yonghui Wu and Mike Schuster and Zhifeng Chen and Quoc V. Le and Mohammad Norouzi and Wolfgang Macherey
              and Maxim Krikun and Yuan Cao and Qin Gao and Klaus Macherey and Jeff Klingner and Apurva Shah and Melvin
              Johnson and Xiaobing Liu and Łukasz Kaiser and Stephan Gouws and Yoshikiyo Kato and Taku Kudo and Hideto
              Kazawa and Keith Stevens and George Kurian and Nishant Patil and Wei Wang and Cliff Young and
              Jason Smith and Jason Riesa and Alex Rudnick and Oriol Vinyals and Greg Corrado and Macduff Hughes
              and Jeffrey Dean},
      year={2016},
      eprint={1609.08144},
      archivePrefix={arXiv},
      primaryClass={cs.CL}
}
"""

UpperCAmelCase				=						"""\
The BLEU score has some undesirable properties when used for single
sentences, as it was designed to be a corpus measure. We therefore
use a slightly different score for our RL experiments which we call
the 'GLEU score'. For the GLEU score, we record all sub-sequences of
1, 2, 3 or 4 tokens in output and target sequence (n-grams). We then
compute a recall, which is the ratio of the number of matching n-grams
to the number of total n-grams in the target (ground truth) sequence,
and a precision, which is the ratio of the number of matching n-grams
to the number of total n-grams in the generated output sequence. Then
GLEU score is simply the minimum of recall and precision. This GLEU
score's range is always between 0 (no matches) and 1 (all match) and
it is symmetrical when switching output and target. According to
our experiments, GLEU score correlates quite well with the BLEU
metric on a corpus level but does not have its drawbacks for our per
sentence reward objective.
"""

UpperCAmelCase				=						"""\
Computes corpus-level Google BLEU (GLEU) score of translated segments against one or more references.
Instead of averaging the sentence level GLEU scores (i.e. macro-average precision), Wu et al. (2016) sum up the matching
tokens and the max of hypothesis and reference tokens for each sentence, then compute using the aggregate values.

Args:
    predictions (list of str): list of translations to score.
        Each translation should be tokenized into a list of tokens.
    references (list of list of str): list of lists of references for each translation.
        Each reference should be tokenized into a list of tokens.
    min_len (int): The minimum order of n-gram this function should extract. Defaults to 1.
    max_len (int): The maximum order of n-gram this function should extract. Defaults to 4.

Returns:
    'google_bleu': google_bleu score

Examples:
    Example 1:
        >>> hyp1 = ['It', 'is', 'a', 'guide', 'to', 'action', 'which',
        ...         'ensures', 'that', 'the', 'rubber', 'duck', 'always',
        ...         'disobeys', 'the', 'commands', 'of', 'the', 'cat']
        >>> ref1a = ['It', 'is', 'the', 'guiding', 'principle', 'which',
        ...          'guarantees', 'the', 'rubber', 'duck', 'forces', 'never',
        ...          'being', 'under', 'the', 'command', 'of', 'the', 'cat']

        >>> hyp2 = ['he', 'read', 'the', 'book', 'because', 'he', 'was',
        ...         'interested', 'in', 'world', 'history']
        >>> ref2a = ['he', 'was', 'interested', 'in', 'world', 'history',
        ...          'because', 'he', 'read', 'the', 'book']

        >>> list_of_references = [[ref1a], [ref2a]]
        >>> hypotheses = [hyp1, hyp2]
        >>> google_bleu = datasets.load_metric(\"google_bleu\")
        >>> results = google_bleu.compute(predictions=hypotheses, references=list_of_references)
        >>> print(round(results[\"google_bleu\"], 2))
        0.44

    Example 2:
        >>> hyp1 = ['It', 'is', 'a', 'guide', 'to', 'action', 'which',
        ...         'ensures', 'that', 'the', 'rubber', 'duck', 'always',
        ...         'disobeys', 'the', 'commands', 'of', 'the', 'cat']
        >>> ref1a = ['It', 'is', 'the', 'guiding', 'principle', 'which',
        ...          'guarantees', 'the', 'rubber', 'duck', 'forces', 'never',
        ...          'being', 'under', 'the', 'command', 'of', 'the', 'cat']
        >>> ref1b = ['It', 'is', 'a', 'guide', 'to', 'action', 'that',
        ...          'ensures', 'that', 'the', 'rubber', 'duck', 'will', 'never',
        ...          'heed', 'the', 'cat', 'commands']
        >>> ref1c = ['It', 'is', 'the', 'practical', 'guide', 'for', 'the',
        ...          'rubber', 'duck', 'army', 'never', 'to', 'heed', 'the', 'directions',
        ...          'of', 'the', 'cat']

        >>> hyp2 = ['he', 'read', 'the', 'book', 'because', 'he', 'was',
        ...         'interested', 'in', 'world', 'history']
        >>> ref2a = ['he', 'was', 'interested', 'in', 'world', 'history',
        ...          'because', 'he', 'read', 'the', 'book']

        >>> list_of_references = [[ref1a, ref1b, ref1c], [ref2a]]
        >>> hypotheses = [hyp1, hyp2]
        >>> google_bleu = datasets.load_metric(\"google_bleu\")
        >>> results = google_bleu.compute(predictions=hypotheses, references=list_of_references)
        >>> print(round(results[\"google_bleu\"], 2))
        0.61

    Example 3:
        >>> hyp1 = ['It', 'is', 'a', 'guide', 'to', 'action', 'which',
        ...         'ensures', 'that', 'the', 'rubber', 'duck', 'always',
        ...         'disobeys', 'the', 'commands', 'of', 'the', 'cat']
        >>> ref1a = ['It', 'is', 'the', 'guiding', 'principle', 'which',
        ...          'guarantees', 'the', 'rubber', 'duck', 'forces', 'never',
        ...          'being', 'under', 'the', 'command', 'of', 'the', 'cat']
        >>> ref1b = ['It', 'is', 'a', 'guide', 'to', 'action', 'that',
        ...          'ensures', 'that', 'the', 'rubber', 'duck', 'will', 'never',
        ...          'heed', 'the', 'cat', 'commands']
        >>> ref1c = ['It', 'is', 'the', 'practical', 'guide', 'for', 'the',
        ...          'rubber', 'duck', 'army', 'never', 'to', 'heed', 'the', 'directions',
        ...          'of', 'the', 'cat']

        >>> hyp2 = ['he', 'read', 'the', 'book', 'because', 'he', 'was',
        ...         'interested', 'in', 'world', 'history']
        >>> ref2a = ['he', 'was', 'interested', 'in', 'world', 'history',
        ...          'because', 'he', 'read', 'the', 'book']

        >>> list_of_references = [[ref1a, ref1b, ref1c], [ref2a]]
        >>> hypotheses = [hyp1, hyp2]
        >>> google_bleu = datasets.load_metric(\"google_bleu\")
        >>> results = google_bleu.compute(predictions=hypotheses, references=list_of_references, min_len=2)
        >>> print(round(results[\"google_bleu\"], 2))
        0.53

    Example 4:
        >>> hyp1 = ['It', 'is', 'a', 'guide', 'to', 'action', 'which',
        ...         'ensures', 'that', 'the', 'rubber', 'duck', 'always',
        ...         'disobeys', 'the', 'commands', 'of', 'the', 'cat']
        >>> ref1a = ['It', 'is', 'the', 'guiding', 'principle', 'which',
        ...          'guarantees', 'the', 'rubber', 'duck', 'forces', 'never',
        ...          'being', 'under', 'the', 'command', 'of', 'the', 'cat']
        >>> ref1b = ['It', 'is', 'a', 'guide', 'to', 'action', 'that',
        ...          'ensures', 'that', 'the', 'rubber', 'duck', 'will', 'never',
        ...          'heed', 'the', 'cat', 'commands']
        >>> ref1c = ['It', 'is', 'the', 'practical', 'guide', 'for', 'the',
        ...          'rubber', 'duck', 'army', 'never', 'to', 'heed', 'the', 'directions',
        ...          'of', 'the', 'cat']

        >>> hyp2 = ['he', 'read', 'the', 'book', 'because', 'he', 'was',
        ...         'interested', 'in', 'world', 'history']
        >>> ref2a = ['he', 'was', 'interested', 'in', 'world', 'history',
        ...          'because', 'he', 'read', 'the', 'book']

        >>> list_of_references = [[ref1a, ref1b, ref1c], [ref2a]]
        >>> hypotheses = [hyp1, hyp2]
        >>> google_bleu = datasets.load_metric(\"google_bleu\")
        >>> results = google_bleu.compute(predictions=hypotheses,references=list_of_references, min_len=2, max_len=6)
        >>> print(round(results[\"google_bleu\"], 2))
        0.4
"""




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





   def 		UpperCamelCase_  (							self)  ->  MetricInfo:
      return datasets.MetricInfo(
          description=_DESCRIPTION      ,   citation=_CITATION      ,   inputs_description=_KWARGS_DESCRIPTION      ,   features=datasets.Features(
              {
                  """predictions""": datasets.Sequence(datasets.Value("""string"""      ,   id="""token""")      ,   id="""sequence"""),
                  """references""": datasets.Sequence(
                      datasets.Sequence(datasets.Value("""string"""      ,   id="""token""")      ,   id="""sequence""")      ,   id="""references"""),
              })      ,   )





   def 		UpperCamelCase_  (							self      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE      ,   SCREAMING_SNAKE_CASE = 1      ,   SCREAMING_SNAKE_CASE = 4      ,   )  ->  Dict[str, float]:
      return {
          "google_bleu": gleu_score.corpus_gleu(
              list_of_references=SCREAMING_SNAKE_CASE      ,   hypotheses=SCREAMING_SNAKE_CASE      ,   min_len=SCREAMING_SNAKE_CASE      ,   max_len=SCREAMING_SNAKE_CASE)
      }

