
"""simple docstring"""



from __future__ import annotations

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

a       :						Any       		=		TypeVar('''T''')
a       :						Tuple       		=		TypeVar('''U''')




class 		a_    (			Generic[T, U]						):







    def __init__(      self      :							Optional[int]  ,       __UpperCamelCase      :							T | None  ,       __UpperCamelCase      :							U | None  )		->Tuple:






        '''simple docstring'''






        _UpperCAmelCase        = key
        _UpperCAmelCase        = val
        _UpperCAmelCase        = None
        _UpperCAmelCase        = None







    def __repr__(      self      :							Any  )		->str:






        '''simple docstring'''






        return (
            f"""Node: key: {self.key}, val: {self.val}, """
            f"""has next: {bool(self.next  )}, has prev: {bool(self.prev  )}"""
        )







class 		a_    (			Generic[T, U]						):







    def __init__(      self      :							Union[str, Any]  )		->None:






        '''simple docstring'''






        _UpperCAmelCase        = DoubleLinkedListNode(__UpperCamelCase  ,       __UpperCamelCase  )
        _UpperCAmelCase        = DoubleLinkedListNode(__UpperCamelCase  ,       __UpperCamelCase  )
        _UpperCAmelCase     ,_UpperCAmelCase        = self.rear, self.head







    def __repr__(      self      :							List[Any]  )		->str:






        '''simple docstring'''






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







    def   _snake_case       (      self      :							List[str]  ,       __UpperCamelCase      :							DoubleLinkedListNode[T, U]  )		->None:






        '''simple docstring'''






        _UpperCAmelCase        = self.rear.prev

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

        _UpperCAmelCase        = node
        _UpperCAmelCase        = previous
        _UpperCAmelCase        = node
        _UpperCAmelCase        = self.rear







    def   _snake_case       (      self      :							Tuple  ,       __UpperCamelCase      :							DoubleLinkedListNode[T, U]  )		->DoubleLinkedListNode[T, U] | None:






        '''simple docstring'''






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

        _UpperCAmelCase        = node.next
        _UpperCAmelCase        = node.prev
        _UpperCAmelCase        = None
        _UpperCAmelCase        = None
        return node







class 		a_    (			Generic[T, U]						):
    a   :					dict[Callable[[T], U], LRUCache[T, U]]			     =					{}







    def __init__(      self      :							Dict  ,       __UpperCamelCase      :							int  )		->Dict:






        '''simple docstring'''






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







    def __repr__(      self      :							int  )		->str:






        '''simple docstring'''






        return (
            f"""CacheInfo(hits={self.hits}, misses={self.miss}, """
            f"""capacity={self.capacity}, current size={self.num_keys})"""
        )







    def __contains__(      self      :							Optional[int]  ,       __UpperCamelCase      :							T  )		->bool:






        '''simple docstring'''






        return key in self.cache







    def   _snake_case       (      self      :							int  ,       __UpperCamelCase      :							T  )		->U | None:






        '''simple docstring'''






        if key in self.cache:
            self.hits += 1
            _UpperCAmelCase        = self.cache[key]
            _UpperCAmelCase        = 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   _snake_case       (      self      :							Union[str, Any]  ,       __UpperCamelCase      :							T  ,       __UpperCamelCase      :							U  )		->None:






        '''simple docstring'''






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

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

        else:
            # bump node to the end of the list, update value
            _UpperCAmelCase        = self.list.remove(self.cache[key]  )
            assert node is not None  # node guaranteed to be in list
            _UpperCAmelCase        = value
            self.list.add(__UpperCamelCase  )







    @classmethod
    def   _snake_case       (      cls      :							Tuple  ,       __UpperCamelCase      :							int = 1_28  )		->Callable[[Callable[[T], U]], Callable[..., U]]:






        '''simple docstring'''






        def cache_decorator_inner(__UpperCamelCase      :							Callable[[T], U]  ) -> Callable[..., U]:
            def cache_decorator_wrapper(*__UpperCamelCase      :							T  ) -> U:
                if func not in cls.decorator_function_to_instance_map:
                    _UpperCAmelCase        = LRUCache(__UpperCamelCase  )

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

            def cache_info() -> LRUCache[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()

"""simple docstring"""



import unittest

from transformers import is_torch_available
from transformers.testing_utils import require_torch


if is_torch_available():
 import torch

 from transformers.generation import DisjunctiveConstraint




@require_torch
class 		a_    (			unittest.TestCase						):







    def   _snake_case       (      self      :							Union[str, Any]  )		->Any:






        '''simple docstring'''






        _UpperCAmelCase        = [[1, 2, 4], [1, 2, 3, 4]]
        _UpperCAmelCase        = DisjunctiveConstraint(__UpperCamelCase  )
        self.assertTrue(isinstance(dc.token_ids  ,       __UpperCamelCase  )  )

        with self.assertRaises(__UpperCamelCase  ):
            DisjunctiveConstraint(torch.LongTensor([[1, 2, 4], [1, 2, 3]]  )  )

        with self.assertRaises(__UpperCamelCase  ):
            DisjunctiveConstraint([torch.LongTensor([1, 2, 4]  ), torch.LongTensor([1, 2, 3, 4, 5]  )]  )







    def   _snake_case       (      self      :							Optional[int]  )		->Dict:






        '''simple docstring'''






        _UpperCAmelCase        = [[1, 2], [1, 2, 3, 4]]

        with self.assertRaises(__UpperCamelCase  ):
            DisjunctiveConstraint(__UpperCamelCase  )  # fails here







    def   _snake_case       (      self      :							Optional[int]  )		->Dict:






        '''simple docstring'''






        _UpperCAmelCase        = [[1, 2, 3], [1, 2, 4]]

        _UpperCAmelCase        = DisjunctiveConstraint(__UpperCamelCase  )

        _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = dc.update(1  )
        _UpperCAmelCase        = stepped is True and completed is False and reset is False
        self.assertTrue(__UpperCamelCase  )
        self.assertTrue(not dc.completed  )
        self.assertTrue(dc.current_seq == [1]  )

        _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = dc.update(2  )
        _UpperCAmelCase        = stepped is True and completed is False and reset is False
        self.assertTrue(__UpperCamelCase  )
        self.assertTrue(not dc.completed  )
        self.assertTrue(dc.current_seq == [1, 2]  )

        _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = dc.update(3  )
        _UpperCAmelCase        = stepped is True and completed is True and reset is False
        self.assertTrue(__UpperCamelCase  )
        self.assertTrue(dc.completed  )  # Completed!
        self.assertTrue(dc.current_seq == [1, 2, 3]  )







    def   _snake_case       (      self      :							List[Any]  )		->Any:






        '''simple docstring'''






        _UpperCAmelCase        = [[1, 2, 3], [1, 2, 4, 5], [1, 2, 5]]

        _UpperCAmelCase        = DisjunctiveConstraint(__UpperCamelCase  )

        _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = dc.update(1  )
        self.assertTrue(not dc.completed  )
        self.assertTrue(dc.current_seq == [1]  )

        _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = dc.update(2  )
        self.assertTrue(not dc.completed  )
        self.assertTrue(dc.current_seq == [1, 2]  )

        _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = dc.update(4  )
        self.assertTrue(not dc.completed  )
        self.assertTrue(dc.current_seq == [1, 2, 4]  )

        _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = dc.update(5  )
        self.assertTrue(dc.completed  )  # Completed!
        self.assertTrue(dc.current_seq == [1, 2, 4, 5]  )

        dc.reset()

        _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = dc.update(1  )
        self.assertTrue(not dc.completed  )
        self.assertTrue(dc.remaining() == 3  )
        self.assertTrue(dc.current_seq == [1]  )

        _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = dc.update(2  )
        self.assertTrue(not dc.completed  )
        self.assertTrue(dc.remaining() == 2  )
        self.assertTrue(dc.current_seq == [1, 2]  )

        _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = dc.update(5  )
        self.assertTrue(dc.completed  )  # Completed!
        self.assertTrue(dc.remaining() == 0  )
        self.assertTrue(dc.current_seq == [1, 2, 5]  )