





"""simple docstring"""





from __future__ import annotations

from queue import Queue






def 	__UpperCAmelCase					(       snake_case_  :  int   ,	snake_case_  :  int   )							->	tuple[int, int]:






   """simple docstring"""


   a ^= b
   b ^= a
   a ^= b
   return a, b






def 	__UpperCAmelCase					(       snake_case_  :  int   ,	snake_case_  :  list[list[int]]   )							->	list[list[int]]:






   """simple docstring"""


   _lowerCAmelCase					     =		1
   while (1 << j) < max_node:
      for i in range(1   ,	max_node + 1   ):
         _lowerCAmelCase					     =		parent[j - 1][parent[j - 1][i]]
      j += 1
   return parent






def 	__UpperCAmelCase					(       snake_case_  :  int   ,	snake_case_  :  int   ,	snake_case_  :  list[int]   ,	snake_case_  :  list[list[int]]   )							->	int:






   """simple docstring"""


   if level[u] < level[v]:
      _lowerCAmelCase					     =		swap(snake_case__   ,	snake_case__   )
   # making depth of u same as depth of v
   for i in range(18   ,	-1   ,	-1   ):
      if level[u] - (1 << i) >= level[v]:
         _lowerCAmelCase					     =		parent[i][u]
    # at the same depth if u==v that mean lca is found
   if u == v:
      return u
   # moving both nodes upwards till lca in found
   for i in range(18   ,	-1   ,	-1   ):
      if parent[i][u] not in [0, parent[i][v]]:
         _lowerCAmelCase					     =		parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
   return parent[0][u]






def 	__UpperCAmelCase					(       snake_case_  :  list[int]   ,	snake_case_  :  list[list[int]]   ,	snake_case_  :  int   ,	snake_case_  :  dict[int, list[int]]   ,	snake_case_  :  int = 1   ,	)							->	tuple[list[int], list[list[int]]]:






   """simple docstring"""


   _lowerCAmelCase					     =		0
   _lowerCAmelCase					     =		Queue(maxsize=snake_case__   )
   q.put(snake_case__   )
   while q.qsize() != 0:
      _lowerCAmelCase					     =		q.get()
      for v in graph[u]:
         if level[v] == -1:
            _lowerCAmelCase					     =		level[u] + 1
            q.put(snake_case__   )
            _lowerCAmelCase					     =		u
   return level, parent






def 	__UpperCAmelCase					(       )							->	None:






   """simple docstring"""


   _lowerCAmelCase					     =		13
   # initializing with 0
   _lowerCAmelCase					     =		[[0 for _ in range(max_node + 10   )] for _ in range(20   )]
   # initializing with -1 which means every node is unvisited
   _lowerCAmelCase					     =		[-1 for _ in range(max_node + 10   )]
   _lowerCAmelCase					     =		{
       1: [2, 3, 4],
       2: [5],
       3: [6, 7],
       4: [8],
       5: [9, 10],
       6: [11],
       7: [],
       8: [12, 13],
       9: [],
       10: [],
       11: [],
       12: [],
       13: [],
   }
   _lowerCAmelCase					     =		breadth_first_search(snake_case__   ,	snake_case__   ,	snake_case__   ,	snake_case__   ,	1   )
   _lowerCAmelCase					     =		create_sparse(snake_case__   ,	snake_case__   )
   print("""LCA of node 1 and 3 is: """   ,	lowest_common_ancestor(1   ,	3   ,	snake_case__   ,	snake_case__   )   )
   print("""LCA of node 5 and 6 is: """   ,	lowest_common_ancestor(5   ,	6   ,	snake_case__   ,	snake_case__   )   )
   print("""LCA of node 7 and 11 is: """   ,	lowest_common_ancestor(7   ,	11   ,	snake_case__   ,	snake_case__   )   )
   print("""LCA of node 6 and 7 is: """   ,	lowest_common_ancestor(6   ,	7   ,	snake_case__   ,	snake_case__   )   )
   print("""LCA of node 4 and 12 is: """   ,	lowest_common_ancestor(4   ,	12   ,	snake_case__   ,	snake_case__   )   )
   print("""LCA of node 8 and 8 is: """   ,	lowest_common_ancestor(8   ,	8   ,	snake_case__   ,	snake_case__   )   )


if __name__ == "__main__":
  main()




"""simple docstring"""





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

import sentencepiece as spm

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


if TYPE_CHECKING:
  from transformers.pipelines.conversational import Conversation

SCREAMING_SNAKE_CASE				:     Optional[int]          =	logging.get_logger(__name__)

SCREAMING_SNAKE_CASE				:     List[str]          =	{'''vocab_file''': '''tokenizer.model'''}

SCREAMING_SNAKE_CASE				:     str          =	{
    '''vocab_file''': {
        '''hf-internal-testing/llama-tokenizer''': '''https://huggingface.co/hf-internal-testing/llama-tokenizer/resolve/main/tokenizer.model''',
    },
    '''tokenizer_file''': {
        '''hf-internal-testing/llama-tokenizer''': '''https://huggingface.co/hf-internal-testing/llama-tokenizer/resolve/main/tokenizer_config.json''',
    },
}
SCREAMING_SNAKE_CASE				:     Tuple          =	{
    '''hf-internal-testing/llama-tokenizer''': 2_0_4_8,
}
SCREAMING_SNAKE_CASE				:     Tuple          =	'''▁'''

SCREAMING_SNAKE_CASE    ,					SCREAMING_SNAKE_CASE				:     Optional[int]          =	'''[INST]''', '''[/INST]'''
SCREAMING_SNAKE_CASE    ,					SCREAMING_SNAKE_CASE				:     Union[str, Any]          =	'''<<SYS>>\n''', '''\n<</SYS>>\n\n'''

# fmt: off
SCREAMING_SNAKE_CASE				:     Optional[Any]          =	'''You are a helpful, respectful and honest assistant. Always answer as helpfully as possible, while being safe. Your\
answers should not include any harmful, unethical, racist, sexist, toxic, dangerous, or illegal content. Please ensure\
that your responses are socially unbiased and positive in nature.

If a question does not make any sense, or is not factually coherent, explain why instead of answering something not\
correct. If you don\'t know the answer to a question, please don\'t share false information.'''


class       __lowerCamelCase	(   __lowercase    ):
   __UpperCamelCase									=   VOCAB_FILES_NAMES
   __UpperCamelCase									=   PRETRAINED_VOCAB_FILES_MAP
   __UpperCamelCase									=   PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
   __UpperCamelCase									=   ['input_ids', 'attention_mask']







   def __init__(self       ,	lowerCamelCase       ,	lowerCamelCase="<unk>"       ,	lowerCamelCase="<s>"       ,	lowerCamelCase="</s>"       ,	lowerCamelCase=None       ,	lowerCamelCase = None       ,	lowerCamelCase=True       ,	lowerCamelCase=False       ,	lowerCamelCase=False       ,	lowerCamelCase=True       ,	**lowerCamelCase       ,	):




      '''simple docstring'''




      _lowerCAmelCase					     =		{} if sp_model_kwargs is None else sp_model_kwargs
      _lowerCAmelCase					     =		AddedToken(lowerCamelCase       ,	lstrip=lowerCamelCase       ,	rstrip=lowerCamelCase				) if isinstance(lowerCamelCase       ,	lowerCamelCase				) else bos_token
      _lowerCAmelCase					     =		AddedToken(lowerCamelCase       ,	lstrip=lowerCamelCase       ,	rstrip=lowerCamelCase				) if isinstance(lowerCamelCase       ,	lowerCamelCase				) else eos_token
      _lowerCAmelCase					     =		AddedToken(lowerCamelCase       ,	lstrip=lowerCamelCase       ,	rstrip=lowerCamelCase				) if isinstance(lowerCamelCase       ,	lowerCamelCase				) else unk_token
      _lowerCAmelCase					     =		AddedToken(lowerCamelCase       ,	lstrip=lowerCamelCase       ,	rstrip=lowerCamelCase				) if isinstance(lowerCamelCase       ,	lowerCamelCase				) else pad_token
      super().__init__(
          bos_token=lowerCamelCase       ,	eos_token=lowerCamelCase       ,	unk_token=lowerCamelCase       ,	pad_token=lowerCamelCase       ,	add_bos_token=lowerCamelCase       ,	add_eos_token=lowerCamelCase       ,	sp_model_kwargs=self.sp_model_kwargs       ,	clean_up_tokenization_spaces=lowerCamelCase       ,	legacy=lowerCamelCase       ,	**lowerCamelCase       ,	)
      if legacy:
         logger.warning_once(
             f"""You are using the legacy behaviour of the {self.__class__}. This means that tokens that come after special tokens will not be properly handled. We recommend you to"""
             """ read the related pull request available at https://github.com/huggingface/transformers/pull/24565"""				)
      _lowerCAmelCase					     =		legacy
      _lowerCAmelCase					     =		vocab_file
      _lowerCAmelCase					     =		add_bos_token
      _lowerCAmelCase					     =		add_eos_token
      _lowerCAmelCase					     =		spm.SentencePieceProcessor(**self.sp_model_kwargs				)
      self.sp_model.Load(lowerCamelCase				)







   def __getstate__(self				):




      '''simple docstring'''




      _lowerCAmelCase					     =		self.__dict__.copy()
      _lowerCAmelCase					     =		None
      _lowerCAmelCase					     =		self.sp_model.serialized_model_proto()
      return state







   def __setstate__(self       ,	lowerCamelCase				):




      '''simple docstring'''




      _lowerCAmelCase					     =		d
      _lowerCAmelCase					     =		spm.SentencePieceProcessor(**self.sp_model_kwargs				)
      self.sp_model.LoadFromSerializedProto(self.sp_model_proto				)







   @property
   def 							A__						(self				):




      '''simple docstring'''




      return self.sp_model.get_piece_size()







   def 							A__						(self				):




      '''simple docstring'''




      _lowerCAmelCase					     =		{self.convert_ids_to_tokens(lowerCamelCase				): i for i in range(self.vocab_size				)}
      vocab.update(self.added_tokens_encoder				)
      return vocab







   def 							A__						(self       ,	lowerCamelCase       ,	**lowerCamelCase				):




      '''simple docstring'''




      if not self.legacy:
         _lowerCAmelCase					     =		SPIECE_UNDERLINE + text.replace(lowerCamelCase       ,	""" """				)
      return super().tokenize(lowerCamelCase       ,	**lowerCamelCase				)







   def 							A__						(self       ,	lowerCamelCase				):




      '''simple docstring'''




      if not self.legacy:
         _lowerCAmelCase					     =		text.startswith(lowerCamelCase				)
         if is_first:
            _lowerCAmelCase					     =		text[1:]

      _lowerCAmelCase					     =		self.sp_model.encode(lowerCamelCase       ,	out_type=lowerCamelCase				)

      if not self.legacy and not is_first and not text.startswith(""" """				) and tokens[0].startswith(lowerCamelCase				):
         _lowerCAmelCase					     =		([tokens[0][1:]] if len(tokens[0]				) > 1 else []) + tokens[1:]
      return tokens







   def 							A__						(self       ,	lowerCamelCase				):




      '''simple docstring'''




      return self.sp_model.piece_to_id(lowerCamelCase				)







   def 							A__						(self       ,	lowerCamelCase				):




      '''simple docstring'''




      _lowerCAmelCase					     =		self.sp_model.IdToPiece(lowerCamelCase				)
      return token







   def 							A__						(self       ,	lowerCamelCase				):




      '''simple docstring'''




      _lowerCAmelCase					     =		[]
      _lowerCAmelCase					     =		""""""
      _lowerCAmelCase					     =		False
      for i, token in enumerate(lowerCamelCase				):
         # make sure that special tokens are not decoded using sentencepiece model
         if token in self.all_special_tokens:
            if not prev_is_special and i != 0:
               out_string += " "
            out_string += self.sp_model.decode(lowerCamelCase				) + token
            _lowerCAmelCase					     =		True
            _lowerCAmelCase					     =		[]
         else:
            current_sub_tokens.append(lowerCamelCase				)
            _lowerCAmelCase					     =		False
      out_string += self.sp_model.decode(lowerCamelCase				)
      return out_string







   def 							A__						(self       ,	lowerCamelCase       ,	lowerCamelCase = None				):




      '''simple docstring'''




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

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

      return (out_vocab_file,)







   def 							A__						(self       ,	lowerCamelCase       ,	lowerCamelCase=None				):




      '''simple docstring'''




      _lowerCAmelCase					     =		[self.bos_token_id] if self.add_bos_token else []
      _lowerCAmelCase					     =		[self.eos_token_id] if self.add_eos_token else []

      _lowerCAmelCase					     =		bos_token_id + token_ids_a + eos_token_id

      if token_ids_a is not None:
         _lowerCAmelCase					     =		output + bos_token_id + token_ids_a + eos_token_id

      return output







   def 							A__						(self       ,	lowerCamelCase       ,	lowerCamelCase = None       ,	lowerCamelCase = False				):




      '''simple docstring'''




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

      _lowerCAmelCase					     =		[1] if self.add_bos_token else []
      _lowerCAmelCase					     =		[1] if self.add_eos_token else []

      if token_ids_a is None:
         return bos_token_id + ([0] * len(lowerCamelCase				)) + eos_token_id
      return (
          bos_token_id
          + ([0] * len(lowerCamelCase				))
          + eos_token_id
          + bos_token_id
          + ([0] * len(lowerCamelCase				))
          + eos_token_id
      )







   def 							A__						(self       ,	lowerCamelCase       ,	lowerCamelCase = None				):




      '''simple docstring'''




      _lowerCAmelCase					     =		[self.bos_token_id] if self.add_bos_token else []
      _lowerCAmelCase					     =		[self.eos_token_id] if self.add_eos_token else []

      _lowerCAmelCase					     =		[0] * len(bos_token_id + token_ids_a + eos_token_id				)

      if token_ids_a is not None:
         output += [1] * len(bos_token_id + token_ids_a + eos_token_id				)

      return output







   def 							A__						(self       ,	lowerCamelCase				):




      '''simple docstring'''




      _lowerCAmelCase					     =		list(conversation.iter_texts()				)
      if not all([is_user for is_user, msg in dialogue[::2]]				) or not all(
          [not is_user for is_user, msg in dialogue[1::2]]				):
         raise ValueError(
             """The model only supports 'user' and 'assistant' roles, starting with user and alternating (u/a/u/a/u...)"""				)

      _lowerCAmelCase					     =		[]
      if len(conversation.past_user_inputs				) > 0:
         if not conversation.past_user_inputs[0].startswith(lowerCamelCase				) or E_SYS not in conversation.past_user_inputs[0]:
            _lowerCAmelCase					     =		(
                B_SYS + DEFAULT_SYSTEM_PROMPT + E_SYS + conversation.past_user_inputs[0]
            )
      elif not dialogue[0][1].startswith(lowerCamelCase				) or E_SYS not in dialogue[0][1]:
         _lowerCAmelCase					     =		(dialogue[0][0], B_SYS + DEFAULT_SYSTEM_PROMPT + E_SYS + dialogue[0][1])

      dialog_tokens += sum(
          [
              [self.bos_token_id]
              + self.encode(
                  f"""{B_INST} {(prompt[1]).strip()} {E_INST} {(answer[1]).strip()} """       ,	add_special_tokens=lowerCamelCase				)
              + [self.eos_token_id]
              for prompt, answer in zip(dialogue[::2]       ,	dialogue[1::2]				)
          ]       ,	[]       ,	)
      if not (dialogue[-1][0]):
         raise ValueError(f"""Last message must be from user, got {dialogue[-1]["role"]}"""				)
      dialog_tokens += [self.bos_token_id] + self.encode(
          f"""{B_INST} {(dialogue[-1][1]).strip()} {E_INST}"""       ,	add_special_tokens=lowerCamelCase				)
      return dialog_tokens