


'''simple docstring'''






from functools import lru_cache






@lru_cache
def 						_A					(lowerCAmelCase__	:int		) ->	int:




     '''simple docstring'''



     if not isinstance(lowerCAmelCase__					,    lowerCAmelCase__		):
          raise TypeError('k must be an integer.'		)
     if k < 0:
          raise ValueError('k integer must be greater or equal to zero.'		)
     if k == 0:
          return 0
     elif k == 1:
          return 1
     else:
          return fibonacci(k - 1		) + fibonacci(k - 2		)






def 						_A					(lowerCAmelCase__	:list					,    lowerCAmelCase__	:int		) ->	int:




     '''simple docstring'''



     _a         =				len(lowerCAmelCase__		)
     # Find m such that F_m >= n where F_i is the i_th fibonacci number.
     _a         =				0
     while True:
          if fibonacci(lowerCAmelCase__		) >= len_list:
               _a         =				i
               break
          i += 1
     _a         =				0
     while fibb_k > 0:
          _a         =				min(
              offset + fibonacci(fibb_k - 1		)					,    len_list - 1		)  # Prevent out of range
          _a         =				arr[index_k]
          if item_k_1 == val:
               return index_k
          elif val < item_k_1:
               fibb_k -= 1
          elif val > item_k_1:
               offset += fibonacci(fibb_k - 1		)
               fibb_k -= 2
     else:
          return -1


if __name__ == "__main__":
 import doctest

 doctest.testmod()





'''simple docstring'''






import json
import os
import re
import unicodedata
from typing import Optional, Tuple

from ...tokenization_utils import PreTrainedTokenizer, _is_control, _is_punctuation, _is_whitespace
from ...utils import logging


a_       :     Tuple 							=     logging.get_logger(__name__)

a_       :     Optional[Any] 							=     {
    "vocab_file": "vocab.json",
    "merges_file": "merges.txt",
}

a_       :     str 							=     {
    "vocab_file": {"openai-gpt": "https://huggingface.co/openai-gpt/resolve/main/vocab.json"},
    "merges_file": {"openai-gpt": "https://huggingface.co/openai-gpt/resolve/main/merges.txt"},
}

a_       :     Union[str, Any] 							=     {
    "openai-gpt": 5_1_2,
}






def 						_A					(lowerCAmelCase__	:Any		) ->	int:




     '''simple docstring'''



     _a         =				text.strip()
     if not text:
          return []
     _a         =				text.split()
     return tokens




class 			a  (  _SCREAMING_SNAKE_CASE							):
 def __init__(			self   ,					__magic_name__=True   ,					__magic_name__=None   ,					__magic_name__=True   ,					__magic_name__=None   ,					__magic_name__=True   ,					)       ->				Optional[Any]:
      if never_split is None:
           _a         =				[]
      _a         =				do_lower_case
      _a         =				set(__magic_name__    )
      _a         =				tokenize_chinese_chars
      _a         =				strip_accents
      _a         =				do_split_on_punc
 def 				__UpperCAmelCase		(			self   ,					__magic_name__   ,					__magic_name__=None    )       ->				List[str]:
      _a         =				self.never_split.union(set(__magic_name__    )    ) if never_split else self.never_split
      _a         =				self._clean_text(__magic_name__    )

      # This was added on November 1st, 2018 for the multilingual and Chinese
      # models. This is also applied to the English models now, but it doesn't
      # matter since the English models were not trained on any Chinese data
      # and generally don't have any Chinese data in them (there are Chinese
      # characters in the vocabulary because Wikipedia does have some Chinese
      # words in the English Wikipedia.).
      if self.tokenize_chinese_chars:
           _a         =				self._tokenize_chinese_chars(__magic_name__    )
      # prevents treating the same character with different unicode codepoints as different characters
      _a         =				unicodedata.normalize('NFC'   ,					__magic_name__    )
      _a         =				whitespace_tokenize(__magic_name__    )
      _a         =				[]
      for token in orig_tokens:
           if token not in never_split:
                if self.do_lower_case:
                     _a         =				token.lower()
                     if self.strip_accents is not False:
                          _a         =				self._run_strip_accents(__magic_name__    )
                elif self.strip_accents:
                     _a         =				self._run_strip_accents(__magic_name__    )
           split_tokens.extend(self._run_split_on_punc(__magic_name__   ,					__magic_name__    )    )

      _a         =				whitespace_tokenize(' '.join(__magic_name__    )    )
      return output_tokens
 def 				__UpperCAmelCase		(			self   ,					__magic_name__    )       ->				List[str]:
      _a         =				unicodedata.normalize('NFD'   ,					__magic_name__    )
      _a         =				[]
      for char in text:
           _a         =				unicodedata.category(__magic_name__    )
           if cat == "Mn":
                continue
           output.append(__magic_name__    )
      return "".join(__magic_name__    )
 def 				__UpperCAmelCase		(			self   ,					__magic_name__   ,					__magic_name__=None    )       ->				Dict:
      if not self.do_split_on_punc or (never_split is not None and text in never_split):
           return [text]
      _a         =				list(__magic_name__    )
      _a         =				0
      _a         =				True
      _a         =				[]
      while i < len(__magic_name__    ):
           _a         =				chars[i]
           if _is_punctuation(__magic_name__    ):
                output.append([char]    )
                _a         =				True
           else:
                if start_new_word:
                     output.append([]    )
                _a         =				False
                output[-1].append(__magic_name__    )
           i += 1

      return ["".join(__magic_name__    ) for x in output]
 def 				__UpperCAmelCase		(			self   ,					__magic_name__    )       ->				Tuple:
      _a         =				[]
      for char in text:
           _a         =				ord(__magic_name__    )
           if self._is_chinese_char(__magic_name__    ):
                output.append(' '    )
                output.append(__magic_name__    )
                output.append(' '    )
           else:
                output.append(__magic_name__    )
      return "".join(__magic_name__    )
 def 				__UpperCAmelCase		(			self   ,					__magic_name__    )       ->				Union[str, Any]:
      # This defines a "chinese character" as anything in the CJK Unicode block:
      #   https://en.wikipedia.org/wiki/CJK_Unified_Ideographs_(Unicode_block)
      #
      # Note that the CJK Unicode block is NOT all Japanese and Korean characters,
      # despite its name. The modern Korean Hangul alphabet is a different block,
      # as is Japanese Hiragana and Katakana. Those alphabets are used to write
      # space-separated words, so they are not treated specially and handled
      # like the all of the other languages.
      if (
          (cp >= 0x4E00 and cp <= 0x9FFF)
          or (cp >= 0x3400 and cp <= 0x4DBF)  #
          or (cp >= 0x2_0000 and cp <= 0x2_A6DF)  #
          or (cp >= 0x2_A700 and cp <= 0x2_B73F)  #
          or (cp >= 0x2_B740 and cp <= 0x2_B81F)  #
          or (cp >= 0x2_B820 and cp <= 0x2_CEAF)  #
          or (cp >= 0xF900 and cp <= 0xFAFF)
          or (cp >= 0x2_F800 and cp <= 0x2_FA1F)  #
      ):  #
           return True

      return False




 def 				__UpperCAmelCase		(			self   ,					__magic_name__    )       ->				Any:
      _a         =				[]
      for char in text:
           _a         =				ord(__magic_name__    )
           if cp == 0 or cp == 0xFFFD or _is_control(__magic_name__    ):
                continue
           if _is_whitespace(__magic_name__    ):
                output.append(' '    )
           else:
                output.append(__magic_name__    )
      return "".join(__magic_name__    )






def 						_A					(lowerCAmelCase__	:str		) ->	Tuple:




     '''simple docstring'''



     _a         =				set()
     _a         =				word[0]
     for char in word[1:]:
          pairs.add((prev_char, char)		)
          _a         =				char
     return pairs






def 						_A					(lowerCAmelCase__	:Tuple		) ->	Union[str, Any]:




     '''simple docstring'''



     _a         =				text.replace('—'					,    '-'		)
     _a         =				text.replace('–'					,    '-'		)
     _a         =				text.replace('―'					,    '-'		)
     _a         =				text.replace('…'					,    '...'		)
     _a         =				text.replace('´'					,    '\''		)
     _a         =				re.sub(r'(-+|~+|!+|"+|;+|\?+|\++|,+|\)+|\(+|\\+|\/+|\*+|\[+|\]+|}+|{+|\|+|_+)'					,    r' \1 '					,    lowerCAmelCase__		)
     _a         =				re.sub(r'\s*\n\s*'					,    ' \n '					,    lowerCAmelCase__		)
     _a         =				re.sub(r'[^\S\n]+'					,    ' '					,    lowerCAmelCase__		)
     return text.strip()






class 			a  (  _SCREAMING_SNAKE_CASE							):
 _lowerCAmelCase			       =						VOCAB_FILES_NAMES
 _lowerCAmelCase			       =						PRETRAINED_VOCAB_FILES_MAP
 _lowerCAmelCase			       =						PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
 _lowerCAmelCase			       =						["""input_ids""", """attention_mask"""]
 def __init__(			self   ,					__magic_name__   ,					__magic_name__   ,					__magic_name__="<unk>"   ,					**__magic_name__    )       ->				Any:
      super().__init__(unk_token=__magic_name__   ,					**__magic_name__    )

      try:
           import ftfy
           from spacy.lang.en import English

           _a         =				English()
           _a         =				_nlp.tokenizer
           _a         =				ftfy.fix_text
      except ImportError:
           logger.warning('ftfy or spacy is not installed using BERT BasicTokenizer instead of SpaCy & ftfy.'    )
           _a         =				BasicTokenizer(do_lower_case=__magic_name__    )
           _a         =				None

      with open(__magic_name__   ,					encoding='utf-8'    ) as vocab_handle:
           _a         =				json.load(__magic_name__    )
      _a         =				{v: k for k, v in self.encoder.items()}
      with open(__magic_name__   ,					encoding='utf-8'    ) as merges_handle:
           _a         =				merges_handle.read().split('\n'    )[1:-1]
      _a         =				[tuple(merge.split()    ) for merge in merges]
      _a         =				dict(zip(__magic_name__   ,					range(len(__magic_name__    )    )    )    )
      _a         =				{}
 @property
 def 				__UpperCAmelCase		(			self    )       ->				Optional[int]:
      return True
 @property
 def 				__UpperCAmelCase		(			self    )       ->				int:
      return len(self.encoder    )
 def 				__UpperCAmelCase		(			self    )       ->				List[str]:
      return dict(self.encoder   ,					**self.added_tokens_encoder    )
 def 				__UpperCAmelCase		(			self   ,					__magic_name__    )       ->				Any:
      _a         =				tuple(token[:-1]    ) + (token[-1] + '</w>',)
      if token in self.cache:
           return self.cache[token]
      _a         =				get_pairs(__magic_name__    )

      if not pairs:
           return token + "</w>"

      while True:
           _a         =				min(__magic_name__   ,					key=lambda __magic_name__    : self.bpe_ranks.get(__magic_name__   ,					float('inf'    )    )    )
           if bigram not in self.bpe_ranks:
                break
           _a   , _a         =				bigram
           _a         =				[]
           _a         =				0
           while i < len(__magic_name__    ):
                try:
                     _a         =				word.index(__magic_name__   ,					__magic_name__    )
                except ValueError:
                     new_word.extend(word[i:]    )
                     break
                else:
                     new_word.extend(word[i:j]    )
                     _a         =				j

                if word[i] == first and i < len(__magic_name__    ) - 1 and word[i + 1] == second:
                     new_word.append(first + second    )
                     i += 2
                else:
                     new_word.append(word[i]    )
                     i += 1
           _a         =				tuple(__magic_name__    )
           _a         =				new_word
           if len(__magic_name__    ) == 1:
                break
           else:
                _a         =				get_pairs(__magic_name__    )
      _a         =				' '.join(__magic_name__    )
      if word == "\n  </w>":
           _a         =				'\n</w>'
      _a         =				word
      return word
 def 				__UpperCAmelCase		(			self   ,					__magic_name__    )       ->				Union[str, Any]:
      _a         =				[]
      if self.fix_text is None:
           # Using BERT's BasicTokenizer
           _a         =				self.nlp.tokenize(__magic_name__    )
           for token in text:
                split_tokens.extend(list(self.bpe(__magic_name__    ).split(' '    )    )    )
      else:
           # Using SpaCy & ftfy (original tokenization process of OpenAI GPT)
           _a         =				self.nlp(text_standardize(self.fix_text(__magic_name__    )    )    )
           for token in text:
                split_tokens.extend(list(self.bpe(token.text.lower()    ).split(' '    )    )    )
      return split_tokens
 def 				__UpperCAmelCase		(			self   ,					__magic_name__    )       ->				Any:
      return self.encoder.get(__magic_name__   ,					self.encoder.get(self.unk_token    )    )
 def 				__UpperCAmelCase		(			self   ,					__magic_name__    )       ->				Any:
      return self.decoder.get(__magic_name__   ,					self.unk_token    )
 def 				__UpperCAmelCase		(			self   ,					__magic_name__    )       ->				Dict:
      _a         =				''.join(__magic_name__    ).replace('</w>'   ,					' '    ).strip()
      return out_string




 def 				__UpperCAmelCase		(			self   ,					__magic_name__   ,					__magic_name__ = None    )       ->				Tuple[str]:
      if not os.path.isdir(__magic_name__    ):
           logger.error(f'Vocabulary path ({save_directory}) should be a directory'    )
           return
      _a         =				os.path.join(
          __magic_name__   ,					(filename_prefix + '-' if filename_prefix else '') + VOCAB_FILES_NAMES['vocab_file']    )
      _a         =				os.path.join(
          __magic_name__   ,					(filename_prefix + '-' if filename_prefix else '') + VOCAB_FILES_NAMES['merges_file']    )

      with open(__magic_name__   ,					'w'   ,					encoding='utf-8'    ) as f:
           f.write(json.dumps(self.encoder   ,					indent=2   ,					sort_keys=__magic_name__   ,					ensure_ascii=__magic_name__    ) + '\n'    )

      _a         =				0
      with open(__magic_name__   ,					'w'   ,					encoding='utf-8'    ) as writer:
           writer.write('#version: 0.2\n'    )
           for bpe_tokens, token_index in sorted(self.bpe_ranks.items()   ,					key=lambda __magic_name__    : kv[1]    ):
                if index != token_index:
                     logger.warning(
                         f'Saving vocabulary to {merge_file}: BPE merge indices are not consecutive.'
                         ' Please check that the tokenizer is not corrupted!'    )
                     _a         =				token_index
                writer.write(' '.join(__magic_name__    ) + '\n'    )
                index += 1

      return vocab_file, merge_file

