

from __future__ import annotations

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

UpperCAmelCase				: Optional[Any]         =  TypeVar('T')
UpperCAmelCase				: Tuple         =  TypeVar('U')







class 		lowerCAmelCase__     (   Generic[T, U]      ):



 """simple docstring"""



 def __init__(	self      : Any      ,							__SCREAMING_SNAKE_CASE      : Union[str, Any]      ,							__SCREAMING_SNAKE_CASE      : List[str]    )						->				Dict:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   key
      __SCREAMING_SNAKE_CASE						     =   val
      __SCREAMING_SNAKE_CASE						     =   0
      __SCREAMING_SNAKE_CASE						     =   None
      __SCREAMING_SNAKE_CASE						     =   None


 def __repr__(	self      : Dict    )						->				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 		lowerCAmelCase__     (   Generic[T, U]      ):



 """simple docstring"""



 def __init__(	self      : Tuple    )						->				None:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   DoubleLinkedListNode(__SCREAMING_SNAKE_CASE      ,							__SCREAMING_SNAKE_CASE    )
      __SCREAMING_SNAKE_CASE						     =   DoubleLinkedListNode(__SCREAMING_SNAKE_CASE      ,							__SCREAMING_SNAKE_CASE    )
      __SCREAMING_SNAKE_CASE						     =   self.rear, self.head
 def __repr__(	self      : Optional[int]    )						->				str:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   ["DoubleLinkedList"]
      __SCREAMING_SNAKE_CASE						     =   self.head
      while node.next is not None:
           rep.append(str(__SCREAMING_SNAKE_CASE    )    )
           __SCREAMING_SNAKE_CASE						     =   node.next
      rep.append(str(self.rear    )    )
      return ",\n    ".join(__SCREAMING_SNAKE_CASE    )
 def    UpperCAmelCase__	(	self      : Optional[int]      ,							__SCREAMING_SNAKE_CASE      : str    )						->				None:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   self.rear.prev

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

      __SCREAMING_SNAKE_CASE						     =   node
      __SCREAMING_SNAKE_CASE						     =   previous
      __SCREAMING_SNAKE_CASE						     =   node
      __SCREAMING_SNAKE_CASE						     =   self.rear
      node.freq += 1
      self._position_node(__SCREAMING_SNAKE_CASE    )
 def    UpperCAmelCase__	(	self      : Union[str, Any]      ,							__SCREAMING_SNAKE_CASE      : Optional[Any]    )						->				None:


      """simple docstring"""




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

           __SCREAMING_SNAKE_CASE						     =   previous_node.prev
           __SCREAMING_SNAKE_CASE						     =   node.prev
           __SCREAMING_SNAKE_CASE						     =   previous_node
           __SCREAMING_SNAKE_CASE						     =   node


 def    UpperCAmelCase__	(	self      : Union[str, Any]      ,							__SCREAMING_SNAKE_CASE      : str    )						->				DoubleLinkedListNode[T, U] | None:


      """simple docstring"""




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

      __SCREAMING_SNAKE_CASE						     =   node.next
      __SCREAMING_SNAKE_CASE						     =   node.prev
      __SCREAMING_SNAKE_CASE						     =   None
      __SCREAMING_SNAKE_CASE						     =   None
      return node







class 		lowerCAmelCase__     (   Generic[T, U]      ):



 """simple docstring"""



 lowerCAmelCase__						      =   {}
 def __init__(	self      : List[str]      ,							__SCREAMING_SNAKE_CASE      : int    )						->				Tuple:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   DoubleLinkedList()
      __SCREAMING_SNAKE_CASE						     =   capacity
      __SCREAMING_SNAKE_CASE						     =   0
      __SCREAMING_SNAKE_CASE						     =   0
      __SCREAMING_SNAKE_CASE						     =   0
      __SCREAMING_SNAKE_CASE						     =   {}
 def __repr__(	self      : Any    )						->				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[Any]      ,							__SCREAMING_SNAKE_CASE      : int    )						->				bool:


      """simple docstring"""




      return key in self.cache
 def    UpperCAmelCase__	(	self      : List[Any]      ,							__SCREAMING_SNAKE_CASE      : Tuple    )						->				U | None:


      """simple docstring"""




      if key in self.cache:
           self.hits += 1
           __SCREAMING_SNAKE_CASE						     =   self.cache[key]
           __SCREAMING_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(__SCREAMING_SNAKE_CASE    )
           return node.val
      self.miss += 1
      return None
 def    UpperCAmelCase__	(	self      : Optional[Any]      ,							__SCREAMING_SNAKE_CASE      : List[Any]      ,							__SCREAMING_SNAKE_CASE      : List[Any]    )						->				None:


      """simple docstring"""




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

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

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


 @classmethod
 def    UpperCAmelCase__	(	cls      : Optional[int]      ,							__SCREAMING_SNAKE_CASE      : Optional[int] = 128    )						->				Callable[[Callable[[T], U]], Callable[..., U]]:


      """simple docstring"""




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

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

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



import os
import re
import unicodedata
from shutil import copyfile
from typing import Any, Dict, List, Optional, Tuple

import sentencepiece as spm

from ...tokenization_utils import AddedToken, PreTrainedTokenizer
from ...utils import logging


UpperCAmelCase				: Union[str, Any]         =  logging.get_logger(__name__)
UpperCAmelCase				: List[Any]         =  {'vocab_file': 'spiece.model'}

UpperCAmelCase				: Any         =  {
    'vocab_file': {
        'google/fnet-base': 'https://huggingface.co/google/fnet-base/resolve/main/spiece.model',
        'google/fnet-large': 'https://huggingface.co/google/fnet-large/resolve/main/spiece.model',
    },
}

UpperCAmelCase				: Tuple         =  {
    'google/fnet-base': 5_1_2,
    'google/fnet-large': 5_1_2,
}

UpperCAmelCase				: Union[str, Any]         =  '▁'







class 		lowerCAmelCase__     (   a      ):



 """simple docstring"""



 lowerCAmelCase__						      =   VOCAB_FILES_NAMES
 lowerCAmelCase__						      =   PRETRAINED_VOCAB_FILES_MAP
 lowerCAmelCase__						      =   PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
 lowerCAmelCase__						      =   ["input_ids", "token_type_ids"]
 def __init__(	self      : List[str]      ,							__SCREAMING_SNAKE_CASE      : Optional[Any]      ,							__SCREAMING_SNAKE_CASE      : str=False      ,							__SCREAMING_SNAKE_CASE      : Optional[int]=True      ,							__SCREAMING_SNAKE_CASE      : List[Any]=True      ,							__SCREAMING_SNAKE_CASE      : int="<unk>"      ,							__SCREAMING_SNAKE_CASE      : List[str]="[SEP]"      ,							__SCREAMING_SNAKE_CASE      : List[str]="<pad>"      ,							__SCREAMING_SNAKE_CASE      : List[Any]="[CLS]"      ,							__SCREAMING_SNAKE_CASE      : Dict="[MASK]"      ,							__SCREAMING_SNAKE_CASE      : Optional[Dict[str, Any]] = None      ,							**__SCREAMING_SNAKE_CASE      : Dict      ,							)						->				None:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   (
          AddedToken(__SCREAMING_SNAKE_CASE      ,							lstrip=__SCREAMING_SNAKE_CASE      ,							rstrip=__SCREAMING_SNAKE_CASE      ,							normalized=__SCREAMING_SNAKE_CASE    )
          if isinstance(__SCREAMING_SNAKE_CASE      ,							__SCREAMING_SNAKE_CASE    )
          else mask_token
      )

      __SCREAMING_SNAKE_CASE						     =   {} if sp_model_kwargs is None else sp_model_kwargs

      super().__init__(
          do_lower_case=__SCREAMING_SNAKE_CASE      ,							remove_space=__SCREAMING_SNAKE_CASE      ,							keep_accents=__SCREAMING_SNAKE_CASE      ,							unk_token=__SCREAMING_SNAKE_CASE      ,							sep_token=__SCREAMING_SNAKE_CASE      ,							pad_token=__SCREAMING_SNAKE_CASE      ,							cls_token=__SCREAMING_SNAKE_CASE      ,							mask_token=__SCREAMING_SNAKE_CASE      ,							sp_model_kwargs=self.sp_model_kwargs      ,							**__SCREAMING_SNAKE_CASE      ,							)

      __SCREAMING_SNAKE_CASE						     =   do_lower_case
      __SCREAMING_SNAKE_CASE						     =   remove_space
      __SCREAMING_SNAKE_CASE						     =   keep_accents
      __SCREAMING_SNAKE_CASE						     =   vocab_file

      __SCREAMING_SNAKE_CASE						     =   spm.SentencePieceProcessor(**self.sp_model_kwargs    )
      self.sp_model.Load(__SCREAMING_SNAKE_CASE    )
 @property
 def    UpperCAmelCase__	(	self      : int    )						->				Optional[Any]:


      """simple docstring"""




      return len(self.sp_model    )
 def    UpperCAmelCase__	(	self      : Dict    )						->				Tuple:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   {self.convert_ids_to_tokens(__SCREAMING_SNAKE_CASE    ): i for i in range(self.vocab_size    )}
      vocab.update(self.added_tokens_encoder    )
      return vocab
 def __getstate__(	self      : Any    )						->				str:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   self.__dict__.copy()
      __SCREAMING_SNAKE_CASE						     =   None
      return state
 def __setstate__(	self      : List[str]      ,							__SCREAMING_SNAKE_CASE      : Dict    )						->				Union[str, Any]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   d

      # for backward compatibility
      if not hasattr(self      ,							"""sp_model_kwargs"""    ):
           __SCREAMING_SNAKE_CASE						     =   {}

      __SCREAMING_SNAKE_CASE						     =   spm.SentencePieceProcessor(**self.sp_model_kwargs    )
      self.sp_model.Load(self.vocab_file    )
 def    UpperCAmelCase__	(	self      : Tuple      ,							__SCREAMING_SNAKE_CASE      : Optional[int]    )						->				Optional[int]:


      """simple docstring"""




      if self.remove_space:
           __SCREAMING_SNAKE_CASE						     =   """ """.join(inputs.strip().split()    )
      else:
           __SCREAMING_SNAKE_CASE						     =   inputs
      __SCREAMING_SNAKE_CASE						     =   outputs.replace("""``"""      ,							"""\""""    ).replace("""''"""      ,							"""\""""    )

      if not self.keep_accents:
           __SCREAMING_SNAKE_CASE						     =   unicodedata.normalize("""NFKD"""      ,							__SCREAMING_SNAKE_CASE    )
           __SCREAMING_SNAKE_CASE						     =   """""".join([c for c in outputs if not unicodedata.combining(__SCREAMING_SNAKE_CASE    )]    )
      if self.do_lower_case:
           __SCREAMING_SNAKE_CASE						     =   outputs.lower()

      return outputs
 def    UpperCAmelCase__	(	self      : str      ,							__SCREAMING_SNAKE_CASE      : str    )						->				List[str]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   self.preprocess_text(__SCREAMING_SNAKE_CASE    )
      __SCREAMING_SNAKE_CASE						     =   self.sp_model.encode(__SCREAMING_SNAKE_CASE      ,							out_type=__SCREAMING_SNAKE_CASE    )
      __SCREAMING_SNAKE_CASE						     =   []
      for piece in pieces:
           if len(__SCREAMING_SNAKE_CASE    ) > 1 and piece[-1] == str(""","""    ) and piece[-2].isdigit():
                __SCREAMING_SNAKE_CASE						     =   self.sp_model.EncodeAsPieces(piece[:-1].replace(__SCREAMING_SNAKE_CASE      ,							""""""    )    )
                if piece[0] != SPIECE_UNDERLINE and cur_pieces[0][0] == SPIECE_UNDERLINE:
                     if len(cur_pieces[0]    ) == 1:
                          __SCREAMING_SNAKE_CASE						     =   cur_pieces[1:]
                     else:
                          __SCREAMING_SNAKE_CASE						     =   cur_pieces[0][1:]
                cur_pieces.append(piece[-1]    )
                new_pieces.extend(__SCREAMING_SNAKE_CASE    )
           else:
                new_pieces.append(__SCREAMING_SNAKE_CASE    )

      return new_pieces
 def    UpperCAmelCase__	(	self      : Any      ,							__SCREAMING_SNAKE_CASE      : str    )						->				Optional[Any]:


      """simple docstring"""




      return self.sp_model.PieceToId(__SCREAMING_SNAKE_CASE    )
 def    UpperCAmelCase__	(	self      : Optional[Any]      ,							__SCREAMING_SNAKE_CASE      : Union[str, Any]    )						->				Optional[Any]:


      """simple docstring"""




      return self.sp_model.IdToPiece(__SCREAMING_SNAKE_CASE    )
 def    UpperCAmelCase__	(	self      : Dict      ,							__SCREAMING_SNAKE_CASE      : List[str]    )						->				Optional[int]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   []
      __SCREAMING_SNAKE_CASE						     =   """"""
      __SCREAMING_SNAKE_CASE						     =   False
      for token in tokens:
           # make sure that special tokens are not decoded using sentencepiece model
           if token in self.all_special_tokens:
                if not prev_is_special:
                     out_string += " "
                out_string += self.sp_model.decode(__SCREAMING_SNAKE_CASE    ) + token
                __SCREAMING_SNAKE_CASE						     =   True
                __SCREAMING_SNAKE_CASE						     =   []
           else:
                current_sub_tokens.append(__SCREAMING_SNAKE_CASE    )
                __SCREAMING_SNAKE_CASE						     =   False
      out_string += self.sp_model.decode(__SCREAMING_SNAKE_CASE    )
      return out_string.strip()
 def    UpperCAmelCase__	(	self      : List[Any]      ,							__SCREAMING_SNAKE_CASE      : List[int]      ,							__SCREAMING_SNAKE_CASE      : bool = False      ,							__SCREAMING_SNAKE_CASE      : bool = None      ,							__SCREAMING_SNAKE_CASE      : bool = True      ,							**__SCREAMING_SNAKE_CASE      : List[str]      ,							)						->				str:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   kwargs.pop("""use_source_tokenizer"""      ,							__SCREAMING_SNAKE_CASE    )

      __SCREAMING_SNAKE_CASE						     =   self.convert_ids_to_tokens(__SCREAMING_SNAKE_CASE      ,							skip_special_tokens=__SCREAMING_SNAKE_CASE    )

      # To avoid mixing byte-level and unicode for byte-level BPT
      # we need to build string separately for added tokens and byte-level tokens
      # cf. https://github.com/huggingface/transformers/issues/1133
      __SCREAMING_SNAKE_CASE						     =   []
      __SCREAMING_SNAKE_CASE						     =   []
      for token in filtered_tokens:
           if skip_special_tokens and token in self.all_special_ids:
                continue
           if token in self.added_tokens_encoder:
                if current_sub_text:
                     sub_texts.append(self.convert_tokens_to_string(__SCREAMING_SNAKE_CASE    )    )
                     __SCREAMING_SNAKE_CASE						     =   []
                sub_texts.append(__SCREAMING_SNAKE_CASE    )
           else:
                current_sub_text.append(__SCREAMING_SNAKE_CASE    )
      if current_sub_text:
           sub_texts.append(self.convert_tokens_to_string(__SCREAMING_SNAKE_CASE    )    )

      # Mimic the behavior of the Rust tokenizer:
      # No space after <unk>
      if spaces_between_special_tokens:
           __SCREAMING_SNAKE_CASE						     =   re.sub(r"""(<unk>) """      ,							r"""\1"""      ,							""" """.join(__SCREAMING_SNAKE_CASE    )    )
      else:
           __SCREAMING_SNAKE_CASE						     =   """""".join(__SCREAMING_SNAKE_CASE    )

      __SCREAMING_SNAKE_CASE						     =   (
          clean_up_tokenization_spaces
          if clean_up_tokenization_spaces is not None
          else self.clean_up_tokenization_spaces
      )
      if clean_up_tokenization_spaces:
           __SCREAMING_SNAKE_CASE						     =   self.clean_up_tokenization(__SCREAMING_SNAKE_CASE    )
           return clean_text
      else:
           return text
 def    UpperCAmelCase__	(	self      : str      ,							__SCREAMING_SNAKE_CASE      : List[int]      ,							__SCREAMING_SNAKE_CASE      : Optional[List[int]] = None    )						->				List[int]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   [self.sep_token_id]
      __SCREAMING_SNAKE_CASE						     =   [self.cls_token_id]
      if token_ids_a is None:
           return cls + token_ids_a + sep
      return cls + token_ids_a + sep + token_ids_a + sep
 def    UpperCAmelCase__	(	self      : Dict      ,							__SCREAMING_SNAKE_CASE      : List[int]      ,							__SCREAMING_SNAKE_CASE      : Optional[List[int]] = None      ,							__SCREAMING_SNAKE_CASE      : bool = False    )						->				List[int]:


      """simple docstring"""




      if already_has_special_tokens:
           return super().get_special_tokens_mask(
               token_ids_a=__SCREAMING_SNAKE_CASE      ,							token_ids_a=__SCREAMING_SNAKE_CASE      ,							already_has_special_tokens=__SCREAMING_SNAKE_CASE    )

      if token_ids_a is not None:
           return [1] + ([0] * len(__SCREAMING_SNAKE_CASE    )) + [1] + ([0] * len(__SCREAMING_SNAKE_CASE    )) + [1]
      return [1] + ([0] * len(__SCREAMING_SNAKE_CASE    )) + [1]
 def    UpperCAmelCase__	(	self      : List[Any]      ,							__SCREAMING_SNAKE_CASE      : List[int]      ,							__SCREAMING_SNAKE_CASE      : Optional[List[int]] = None    )						->				List[int]:


      """simple docstring"""




      __SCREAMING_SNAKE_CASE						     =   [self.sep_token_id]
      __SCREAMING_SNAKE_CASE						     =   [self.cls_token_id]

      if token_ids_a is None:
           return len(cls + token_ids_a + sep    ) * [0]
      return len(cls + token_ids_a + sep    ) * [0] + len(token_ids_a + sep    ) * [1]


 def    UpperCAmelCase__	(	self      : List[str]      ,							__SCREAMING_SNAKE_CASE      : str      ,							__SCREAMING_SNAKE_CASE      : Optional[str] = None    )						->				Tuple[str]:


      """simple docstring"""




      if not os.path.isdir(__SCREAMING_SNAKE_CASE    ):
           logger.error(f'Vocabulary path ({save_directory}) should be a directory'    )
           return
      __SCREAMING_SNAKE_CASE						     =   os.path.join(
          __SCREAMING_SNAKE_CASE      ,							(filename_prefix + """-""" if filename_prefix else """""") + VOCAB_FILES_NAMES["""vocab_file"""]    )

      if os.path.abspath(self.vocab_file    ) != os.path.abspath(__SCREAMING_SNAKE_CASE    ) and os.path.isfile(self.vocab_file    ):
           copyfile(self.vocab_file      ,							__SCREAMING_SNAKE_CASE    )
      elif not os.path.isfile(self.vocab_file    ):
           with open(__SCREAMING_SNAKE_CASE      ,							"""wb"""    ) as fi:
                __SCREAMING_SNAKE_CASE						     =   self.sp_model.serialized_model_proto()
                fi.write(__SCREAMING_SNAKE_CASE    )

      return (out_vocab_file,)






