

'''simple docstring'''







import io
import os
import unicodedata
from typing import Any, Dict, List, Optional, Tuple

import sentencepiece as spm

from ...tokenization_utils import PreTrainedTokenizer
from ...utils import logging


__lowerCamelCase		       =    logging.get_logger(__name__)

__lowerCamelCase		       =    '''▁'''

__lowerCamelCase		       =    {'''vocab_file''': '''vocab.txt''', '''sentencepiece_model_ckpt''': '''sentencepiece.bpe.model'''}

__lowerCamelCase		       =    {
    '''sentencepiece_model_file''': '''sentencepiece.bpe.model''',
    '''vocab_file''': '''vocab.txt''',
}

__lowerCamelCase		       =    {
    '''vocab_file''': {
        '''ernie-m-base''': '''https://huggingface.co/susnato/ernie-m-base_pytorch/blob/main/vocab.txt''',
        '''ernie-m-large''': '''https://huggingface.co/susnato/ernie-m-base_pytorch/blob/main/vocab.txt''',
    },
    '''sentencepiece_model_file''': {
        '''ernie-m-base''': '''https://huggingface.co/susnato/ernie-m-base_pytorch/blob/main/sentencepiece.bpe.model''',
        '''ernie-m-large''': '''https://huggingface.co/susnato/ernie-m-base_pytorch/blob/main/sentencepiece.bpe.model''',
    },
}

__lowerCamelCase		       =    {
    '''ernie-m-base''': 514,
    '''ernie-m-large''': 514,
}

__lowerCamelCase		       =    {
    '''ernie-m-base''': {'''do_lower_case''': False},
    '''ernie-m-large''': {'''do_lower_case''': False},
}


class 					A__      (      _snake_case			):
    lowercase						=		["input_ids"]

    lowercase						=		VOCAB_FILES_NAMES
    lowercase						=		PRETRAINED_INIT_CONFIGURATION
    lowercase						=		PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
    lowercase						=		PRETRAINED_VOCAB_FILES_MAP
    lowercase						=		RESOURCE_FILES_NAMES



    def __init__(					self		,				UpperCamelCase__		,				UpperCamelCase__=None		,				UpperCamelCase__=False		,				UpperCamelCase__="utf8"		,				UpperCamelCase__="[UNK]"		,				UpperCamelCase__="[SEP]"		,				UpperCamelCase__="[PAD]"		,				UpperCamelCase__="[CLS]"		,				UpperCamelCase__="[MASK]"		,				UpperCamelCase__ = None		,				**UpperCamelCase__		,				)						->      None:





           '''simple docstring'''
           A_						=      {} if sp_model_kwargs is None else sp_model_kwargs
           super().__init__(
               do_lower_case=UpperCamelCase__		,				unk_token=UpperCamelCase__		,				sep_token=UpperCamelCase__		,				pad_token=UpperCamelCase__		,				cls_token=UpperCamelCase__		,				mask_token=UpperCamelCase__		,				vocab_file=UpperCamelCase__		,				encoding=UpperCamelCase__		,				sp_model_kwargs=self.sp_model_kwargs		,				**UpperCamelCase__		,				)
           A_						=      do_lower_case
           A_						=      sentencepiece_model_ckpt
           A_						=      spm.SentencePieceProcessor(**self.sp_model_kwargs       )
           self.sp_model.Load(UpperCamelCase__       )

           # to mimic paddlenlp.transformers.ernie_m.tokenizer.ErnieMTokenizer functioning
           if vocab_file is not None:
                  A_						=      self.load_vocab(filepath=UpperCamelCase__       )
           else:
                  A_						=      {self.sp_model.id_to_piece(UpperCamelCase__       ): id for id in range(self.sp_model.get_piece_size()       )}
           A_						=      {v: k for k, v in self.vocab.items()}



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





           '''simple docstring'''
           if text is None:
                  return None

           A_						=      self.tokenize(UpperCamelCase__       )
           A_					,			A_						=      """""", []

           for i, ch in enumerate(UpperCamelCase__       ):
                  if ch in self.SP_CHAR_MAPPING:
                         A_						=      self.SP_CHAR_MAPPING.get(UpperCamelCase__       )
                  else:
                         A_						=      unicodedata.normalize("""NFKC"""		,				UpperCamelCase__       )
                  if self.is_whitespace(UpperCamelCase__       ):
                         continue
                  normalized_text += ch
                  char_mapping.extend([i] * len(UpperCamelCase__       )       )

           A_					,			A_					,			A_						=      normalized_text, [], 0

           if self.do_lower_case:
                  A_						=      text.lower()

           for token in split_tokens:
                  if token[:1] == "▁":
                         A_						=      token[1:]
                  A_						=      text[offset:].index(UpperCamelCase__       ) + offset
                  A_						=      start + len(UpperCamelCase__       )

                  token_mapping.append((char_mapping[start], char_mapping[end - 1] + 1)       )
                  A_						=      end
           return token_mapping



    @property
    def 					snake_case_			(					self       )						->      Optional[int]:





           '''simple docstring'''
           return len(self.vocab       )



    def 					snake_case_			(					self       )						->      int:





           '''simple docstring'''
           return dict(self.vocab		,				**self.added_tokens_encoder       )



    def __getstate__(					self       )						->      List[str]:





           '''simple docstring'''
           A_						=      self.__dict__.copy()
           A_						=      None
           return state



    def __setstate__(					self		,				UpperCamelCase__       )						->      Any:





           '''simple docstring'''
           A_						=      d

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

           A_						=      spm.SentencePieceProcessor(**self.sp_model_kwargs       )
           self.sp_model.Load(self.sentencepiece_model_ckpt       )



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





           '''simple docstring'''
           return "".join((self.SP_CHAR_MAPPING.get(UpperCamelCase__		,				UpperCamelCase__       ) for c in text)       )



    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__=False		,				UpperCamelCase__=64		,				UpperCamelCase__=0.1       )						->      List[Any]:





           '''simple docstring'''

           if self.sp_model_kwargs.get("""enable_sampling"""       ) is True:
                  A_						=      True
           if self.sp_model_kwargs.get("""alpha"""       ) is not None:
                  A_						=      self.sp_model_kwargs.get("""alpha"""       )
           if self.sp_model_kwargs.get("""nbest_size"""       ) is not None:
                  A_						=      self.sp_model_kwargs.get("""nbest_size"""       )

           if not enable_sampling:
                  A_						=      self.sp_model.EncodeAsPieces(UpperCamelCase__       )
           else:
                  A_						=      self.sp_model.SampleEncodeAsPieces(UpperCamelCase__		,				UpperCamelCase__		,				UpperCamelCase__       )
           A_						=      []
           for pi, piece in enumerate(UpperCamelCase__       ):
                  if piece == SPIECE_UNDERLINE:
                         if not pieces[pi + 1].startswith(UpperCamelCase__       ) and pi != 0:
                                new_pieces.append(UpperCamelCase__       )
                                continue
                         else:
                                continue
                  A_						=      0
                  for i, chunk in enumerate(UpperCamelCase__       ):
                         if chunk == SPIECE_UNDERLINE:
                                continue
                         if self.is_ch_char(UpperCamelCase__       ) or self.is_punct(UpperCamelCase__       ):
                                if i > lst_i and piece[lst_i:i] != SPIECE_UNDERLINE:
                                       new_pieces.append(piece[lst_i:i]       )
                                new_pieces.append(UpperCamelCase__       )
                                A_						=      i + 1
                         elif chunk.isdigit() and i > 0 and not piece[i - 1].isdigit():
                                if i > lst_i and piece[lst_i:i] != SPIECE_UNDERLINE:
                                       new_pieces.append(piece[lst_i:i]       )
                                A_						=      i
                         elif not chunk.isdigit() and i > 0 and piece[i - 1].isdigit():
                                if i > lst_i and piece[lst_i:i] != SPIECE_UNDERLINE:
                                       new_pieces.append(piece[lst_i:i]       )
                                A_						=      i
                  if len(UpperCamelCase__       ) > lst_i:
                         new_pieces.append(piece[lst_i:]       )
           return new_pieces



    def 					snake_case_			(					self		,				UpperCamelCase__       )						->      Optional[Any]:





           '''simple docstring'''
           A_						=      """""".join(UpperCamelCase__       ).replace(UpperCamelCase__		,				""" """       ).strip()
           return out_string



    def 					snake_case_			(					self		,				UpperCamelCase__       )						->      List[str]:





           '''simple docstring'''
           A_						=      self.convert_ids_to_tokens(UpperCamelCase__       )
           A_						=      """""".join(UpperCamelCase__       ).replace(UpperCamelCase__		,				""" """       ).strip()
           return out_string



    def 					snake_case_			(					self		,				UpperCamelCase__       )						->      Tuple:





           '''simple docstring'''
           return self.vocab.get(UpperCamelCase__		,				self.vocab.get(self.unk_token       )       )



    def 					snake_case_			(					self		,				UpperCamelCase__       )						->      Optional[Any]:





           '''simple docstring'''
           return self.reverse_vocab.get(UpperCamelCase__		,				self.unk_token       )



    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__=None       )						->      Optional[Any]:





           '''simple docstring'''
           if token_ids_a is None:
                  return [self.cls_token_id] + token_ids_a + [self.sep_token_id]
           A_						=      [self.cls_token_id]
           A_						=      [self.sep_token_id]
           return _cls + token_ids_a + _sep + _sep + token_ids_a + _sep



    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__=None       )						->      Optional[Any]:





           '''simple docstring'''
           if offset_mapping_a is None:
                  return [(0, 0)] + offset_mapping_a + [(0, 0)]

           return [(0, 0)] + offset_mapping_a + [(0, 0), (0, 0)] + offset_mapping_a + [(0, 0)]



    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__=None		,				UpperCamelCase__=False       )						->      Optional[int]:





           '''simple docstring'''

           if already_has_special_tokens:
                  if token_ids_a is not None:
                         raise ValueError(
                             """You should not supply a second sequence if the provided sequence of """
                             """ids is already formatted with special tokens for the model."""       )
                  return [1 if x in [self.sep_token_id, self.cls_token_id] else 0 for x in token_ids_a]

           if token_ids_a is not None:
                  return [1] + ([0] * len(UpperCamelCase__       )) + [1, 1] + ([0] * len(UpperCamelCase__       )) + [1]
           return [1] + ([0] * len(UpperCamelCase__       )) + [1]



    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__ = None       )						->      List[int]:





           '''simple docstring'''
           # called when `add_special_tokens` is True, so align with `build_inputs_with_special_tokens` method
           if token_ids_a is None:
                  # [CLS] X [SEP]
                  return (len(UpperCamelCase__       ) + 2) * [0]

           # [CLS] A [SEP] [SEP] B [SEP]
           return [0] * (len(UpperCamelCase__       ) + 1) + [1] * (len(UpperCamelCase__       ) + 3)



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





           '''simple docstring'''
           if "\u4e00" <= char <= "\u9fff":
                  return True
           return False



    def 					snake_case_			(					self		,				UpperCamelCase__       )						->      Dict:





           '''simple docstring'''
           if ("a" <= char <= "z") or ("A" <= char <= "Z"):
                  return True
           return False



    def 					snake_case_			(					self		,				UpperCamelCase__       )						->      Any:





           '''simple docstring'''
           if char in ",;:.?!~，；：。？！《》【】":
                  return True
           return False



    def 					snake_case_			(					self		,				UpperCamelCase__       )						->      Any:





           '''simple docstring'''
           if char == " " or char == "\t" or char == "\n" or char == "\r":
                  return True
           if len(UpperCamelCase__       ) == 1:
                  A_						=      unicodedata.category(UpperCamelCase__       )
                  if cat == "Zs":
                         return True
           return False



    def 					snake_case_			(					self		,				UpperCamelCase__       )						->      Any:





           '''simple docstring'''
           A_						=      {}
           with io.open(UpperCamelCase__		,				"""r"""		,				encoding="""utf-8"""       ) as f:
                  for index, line in enumerate(UpperCamelCase__       ):
                         A_						=      line.rstrip("""\n"""       )
                         A_						=      int(UpperCamelCase__       )

           return token_to_idx







    def 					snake_case_			(					self		,				UpperCamelCase__		,				UpperCamelCase__ = None       )						->      Tuple[str]:





           '''simple docstring'''
           A_						=      0
           if os.path.isdir(UpperCamelCase__       ):
                  A_						=      os.path.join(
                      UpperCamelCase__		,				(filename_prefix + """-""" if filename_prefix else """""") + VOCAB_FILES_NAMES["""vocab_file"""]       )
           else:
                  A_						=      (filename_prefix + """-""" if filename_prefix else """""") + save_directory
           with open(UpperCamelCase__		,				"""w"""		,				encoding="""utf-8"""       ) as writer:
                  for token, token_index in sorted(self.vocab.items()		,				key=lambda UpperCamelCase__       : kv[1]       ):
                         if index != token_index:
                                logger.warning(
                                    f'''Saving vocabulary to {vocab_file}: vocabulary indices are not consecutive.'''
                                    """ Please check that the vocabulary is not corrupted!"""       )
                                A_						=      token_index
                         writer.write(token + """\n"""       )
                         index += 1

           A_						=      os.path.join(UpperCamelCase__		,				"""sentencepiece.bpe.model"""       )
           with open(UpperCamelCase__		,				"""wb"""       ) as fi:
                  A_						=      self.sp_model.serialized_model_proto()
                  fi.write(UpperCamelCase__       )

           return (vocab_file,)



'''simple docstring'''







from queue import PriorityQueue
from typing import Any

import numpy as np
def       UpperCAmelCase__    (      UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       )			->			float | int:
       for nxt, d in graph[v]:
              if nxt in visited_forward:
                     continue
              A_						=      cst_fwd.get(UpperCAmelCase__,       np.inf				)
              A_						=      cst_fwd[v] + d
              if new_cost_f < old_cost_f:
                     queue.put((new_cost_f, nxt)				)
                     A_						=      new_cost_f
                     A_						=      v
              if nxt in visited_backward:
                     if cst_fwd[v] + d + cst_bwd[nxt] < shortest_distance:
                            A_						=      cst_fwd[v] + d + cst_bwd[nxt]
       return shortest_distance
def       UpperCAmelCase__    (      UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__				)			->			int:
       A_						=      -1

       A_						=      set()
       A_						=      set()
       A_						=      {source: 0}
       A_						=      {destination: 0}
       A_						=      {source: None}
       A_						=      {destination: None}
       A_						=      PriorityQueue()
       A_						=      PriorityQueue()

       A_						=      np.inf

       queue_forward.put((0, source)				)
       queue_backward.put((0, destination)				)

       if source == destination:
              return 0

       while not queue_forward.empty() and not queue_backward.empty():
              A_					,			A_						=      queue_forward.get()
              visited_forward.add(UpperCAmelCase__				)

              A_					,			A_						=      queue_backward.get()
              visited_backward.add(UpperCAmelCase__				)

              A_						=      pass_and_relaxation(
                  UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       )

              A_						=      pass_and_relaxation(
                  UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       UpperCAmelCase__,       )

              if cst_fwd[v_fwd] + cst_bwd[v_bwd] >= shortest_distance:
                     break

       if shortest_distance != np.inf:
              A_						=      shortest_distance
       return shortest_path_distance


__lowerCamelCase		       =    {
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''G''', 2]],
    '''F''': [],
    '''G''': [['''F''', 1]],
}
__lowerCamelCase		       =    {
    '''B''': [['''E''', 1]],
    '''C''': [['''B''', 1]],
    '''D''': [['''C''', 1]],
    '''F''': [['''D''', 1], ['''G''', 1]],
    '''E''': [[None, np.inf]],
    '''G''': [['''E''', 2]],
}

if __name__ == "__main__":
      import doctest

      doctest.testmod()
