from __future__ import annotations

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

lowerCAmelCase__      		=					TypeVar('T')
lowerCAmelCase__      		=					TypeVar('U')
class 							a_					(		Generic[T, U]		):






 '''simple docstring'''






 def __init__(     self   :    Optional[Any]     ,       lowercase__   :    T | None     ,       lowercase__   :    U | None):







        '''simple docstring'''



        lowerCAmelCase__	      =   key
        lowerCAmelCase__	      =   val
        lowerCAmelCase__	      =   0
        lowerCAmelCase__	      =   None
        lowerCAmelCase__	      =   None




 def __repr__(     self   :    Optional[int]):







        '''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 							a_					(		Generic[T, U]		):






 '''simple docstring'''






 def __init__(     self   :    List[Any]):







        '''simple docstring'''



        lowerCAmelCase__	      =   DoubleLinkedListNode(lowercase__     ,       lowercase__)
        lowerCAmelCase__	      =   DoubleLinkedListNode(lowercase__     ,       lowercase__)
        lowerCAmelCase__      ,   lowerCAmelCase__	      =   self.rear, self.head




 def __repr__(     self   :    Any):







        '''simple docstring'''



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




 def 						__snake_case		(     self   :    Any     ,       lowercase__   :    DoubleLinkedListNode[T, U]):







        '''simple docstring'''



        lowerCAmelCase__	      =   self.rear.prev

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

        lowerCAmelCase__	      =   node
        lowerCAmelCase__	      =   previous
        lowerCAmelCase__	      =   node
        lowerCAmelCase__	      =   self.rear
        node.freq += 1
        self._position_node(lowercase__)




 def 						__snake_case		(     self   :    Any     ,       lowercase__   :    DoubleLinkedListNode[T, U]):







        '''simple docstring'''



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

               lowerCAmelCase__	      =   previous_node.prev
               lowerCAmelCase__	      =   node.prev
               lowerCAmelCase__	      =   previous_node
               lowerCAmelCase__	      =   node




 def 						__snake_case		(     self   :    Any     ,       lowercase__   :    DoubleLinkedListNode[T, U]):







        '''simple docstring'''



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

        lowerCAmelCase__	      =   node.next
        lowerCAmelCase__	      =   node.prev
        lowerCAmelCase__	      =   None
        lowerCAmelCase__	      =   None
        return node






class 							a_					(		Generic[T, U]		):






 '''simple docstring'''






 UpperCAmelCase_      					=   {}




 def __init__(     self   :    str     ,       lowercase__   :    int):







        '''simple docstring'''



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




 def __repr__(     self   :    Dict):







        '''simple docstring'''



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




 def __contains__(     self   :    Tuple     ,       lowercase__   :    T):







        '''simple docstring'''



        return key in self.cache




 def 						__snake_case		(     self   :    List[str]     ,       lowercase__   :    T):







        '''simple docstring'''



        if key in self.cache:
               self.hits += 1
               lowerCAmelCase__	      =   self.cache[key]
               lowerCAmelCase__	      =   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(lowercase__)
               return node.val
        self.miss += 1
        return None




 def 						__snake_case		(     self   :    Dict     ,       lowercase__   :    T     ,       lowercase__   :    U):







        '''simple docstring'''



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

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

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




 @classmethod
 def 						__snake_case		(     cls   :    type[LFUCache[T, U]]     ,       lowercase__   :    int = 128):







        '''simple docstring'''



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

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

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

               setattr(lowercase__     ,       'cache_info'     ,       lowercase__)  # noqa: B010

               return cache_decorator_wrapper

        return cache_decorator_inner


if __name__ == "__main__":
    import doctest

    doctest.testmod()

import unittest

from cer import CER


lowerCAmelCase__      		=					CER()
class 							a_					(		unittest.TestCase		):






 '''simple docstring'''






 def 						__snake_case		(     self   :    Any):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['White House']
        lowerCAmelCase__	      =   ['white house']
        # S = 2, D = 0, I = 0, N = 11, CER = 2 / 11
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.1_818_181_818) < 1e-6)




 def 						__snake_case		(     self   :    List[Any]):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['were wolf']
        lowerCAmelCase__	      =   ['werewolf']
        # S = 0, D = 0, I = 1, N = 9, CER = 1 / 9
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.1_111_111) < 1e-6)

        lowerCAmelCase__	      =   ['werewolf']
        lowerCAmelCase__	      =   ['weae     wolf']
        # S = 1, D = 1, I = 0, N = 8, CER = 0.25
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.25) < 1e-6)

        # consecutive whitespaces case 1
        lowerCAmelCase__	      =   ['were wolf']
        lowerCAmelCase__	      =   ['were               wolf']
        # S = 0, D = 0, I = 0, N = 9, CER = 0
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.0) < 1e-6)

        # consecutive whitespaces case 2
        lowerCAmelCase__	      =   ['were   wolf']
        lowerCAmelCase__	      =   ['were               wolf']
        # S = 0, D = 0, I = 0, N = 9, CER = 0
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.0) < 1e-6)




 def 						__snake_case		(     self   :    Optional[Any]):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['werewolf']
        lowerCAmelCase__	      =   ['weaewolf']
        # S = 1, D = 0, I = 0, N = 8, CER = 0.125
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.125) < 1e-6)




 def 						__snake_case		(     self   :    Tuple):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['werewolf']
        lowerCAmelCase__	      =   ['wereawolf']
        # S = 0, D = 1, I = 0, N = 8, CER = 0.125
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.125) < 1e-6)




 def 						__snake_case		(     self   :    Optional[int]):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['werewolf']
        lowerCAmelCase__	      =   ['wereolf']
        # S = 0, D = 0, I = 1, N = 8, CER = 0.125
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.125) < 1e-6)




 def 						__snake_case		(     self   :    str):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['werewolf']
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertEqual(lowercase__     ,       0.0)




 def 						__snake_case		(     self   :    Tuple):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['werewolf', 'I am your father']
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertEqual(lowercase__     ,       0.0)

        lowerCAmelCase__	      =   ['werewolf', 'I am your father', 'doge']
        lowerCAmelCase__	      =   ['werxwolf', 'I       am your father', 'doge']
        # S = 1, D = 0, I = 0, N = 28, CER = 1 / 28
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.03_571_428) < 1e-6)




 def 						__snake_case		(     self   :    Tuple):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['My hovercraft', 'is full of eels']
        lowerCAmelCase__	      =   ['My hovercraft is full', ' of eels']
        # S = 0, D = 0, I = 2, N = 28, CER = 2 / 28
        # whitespace at the front of " of eels" will be strip during preporcessing
        # so need to insert 2 whitespaces
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__     ,       concatenate_texts=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.071_428) < 1e-6)




 def 						__snake_case		(     self   :    Dict):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['我能吞下玻璃而不伤身体']
        lowerCAmelCase__	      =   [' 能吞虾玻璃而 不霜身体啦']
        # S = 3, D = 2, I = 0, N = 11, CER = 5 / 11
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.4_545_454_545) < 1e-6)

        lowerCAmelCase__	      =   ['我能吞下玻璃', '而不伤身体']
        lowerCAmelCase__	      =   ['我    能 吞 下 玻 璃', '而不伤身体']
        # S = 0, D = 5, I = 0, N = 11, CER = 5 / 11
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertTrue(abs(char_error_rate - 0.454_545_454_545) < 1e-6)

        lowerCAmelCase__	      =   ['我能吞下玻璃而不伤身体']
        lowerCAmelCase__	      =   cer.compute(predictions=lowercase__     ,       references=lowercase__)
        self.assertFalse(lowercase__     ,       0.0)




 def 						__snake_case		(     self   :    Dict):







        '''simple docstring'''



        lowerCAmelCase__	      =   ['']
        lowerCAmelCase__	      =   ['Hypothesis']
        with self.assertRaises(lowercase__):
               cer.compute(predictions=lowercase__     ,       references=lowercase__)


if __name__ == "__main__":
    unittest.main()
