






"""simple docstring"""



from __future__ import annotations

from queue import Queue
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    int						,   __snake_case     :    int       ):





  '''simple docstring'''





  a ^= b
  b ^= a
  a ^= b
  return a, b
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    int						,   __snake_case     :    list[list[int]]       ):





  '''simple docstring'''





  lowercase				       =			1
  while (1 << j) < max_node:
    for i in range(1						,   max_node + 1       ):
      lowercase				       =			parent[j - 1][parent[j - 1][i]]
    j += 1
  return parent
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    int						,   __snake_case     :    int						,   __snake_case     :    list[int]						,   __snake_case     :    list[list[int]]       ):





  '''simple docstring'''





  if level[u] < level[v]:
    lowercase       ,	lowercase				       =			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]:
      lowercase				       =			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]]:
      lowercase       ,	lowercase				       =			parent[i][u], parent[i][v]
    # returning longest common ancestor of u,v
  return parent[0][u]
def 		_SCREAMING_SNAKE_CASE					(       __snake_case     :    list[int]						,   __snake_case     :    list[list[int]]						,   __snake_case     :    int						,   __snake_case     :    dict[int, list[int]]						,   __snake_case     :    int = 1						,   ):





  '''simple docstring'''





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





  '''simple docstring'''





  lowercase				       =			13
  # initializing with 0
  lowercase				       =			[[0 for _ in range(max_node + 10       )] for _ in range(20       )]
  # initializing with -1 which means every node is unvisited
  lowercase				       =			[-1 for _ in range(max_node + 10       )]
  lowercase				       =			{
      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: [],
  }
  lowercase       ,	lowercase				       =			breadth_first_search(__snake_case						,   __snake_case						,   __snake_case						,   __snake_case						,   1       )
  lowercase				       =			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 shutil
import tempfile
import unittest
from pathlib import Path
from shutil import copyfile

from transformers import SpeechaTextTokenizer, is_speech_available
from transformers.models.speech_to_text.tokenization_speech_to_text import VOCAB_FILES_NAMES, save_json
from transformers.testing_utils import get_tests_dir, require_sentencepiece, require_torch, require_torchaudio
from transformers.utils import FEATURE_EXTRACTOR_NAME

from .test_feature_extraction_speech_to_text import floats_list


if is_speech_available():
     from transformers import SpeechaTextFeatureExtractor, SpeechaTextProcessor


A							     = get_tests_dir("fixtures/test_sentencepiece.model")



@require_torch
@require_torchaudio
@require_sentencepiece
class 			lowerCAmelCase__ (							unittest.TestCase							):



  '''simple docstring'''






  def 		_lowerCamelCase						(self	:			List[str]     ) ->							List[str]:
        snake_case_    							=				tempfile.mkdtemp()

        snake_case_    							=				["<s>", "<pad>", "</s>", "<unk>", "▁This", "▁is", "▁a", "▁t", "est"]
        snake_case_    							=				dict(zip(lowerCAmelCase_						,			range(len(lowerCAmelCase_     )     )     )     )
        snake_case_    							=				Path(self.tmpdirname     )
        save_json(lowerCAmelCase_						,			save_dir / VOCAB_FILES_NAMES["vocab_file"]     )
        if not (save_dir / VOCAB_FILES_NAMES["spm_file"]).exists():
              copyfile(lowerCAmelCase_						,			save_dir / VOCAB_FILES_NAMES["spm_file"]     )

        snake_case_    							=				SpeechaTextTokenizer.from_pretrained(self.tmpdirname     )
        tokenizer.save_pretrained(self.tmpdirname     )

        snake_case_    							=				{
            "feature_size": 24,
            "num_mel_bins": 24,
            "padding_value": 0.0,
            "sampling_rate": 1_60_00,
            "return_attention_mask": False,
            "do_normalize": True,
        }
        save_json(lowerCAmelCase_						,			save_dir / FEATURE_EXTRACTOR_NAME     )

  def 		_lowerCamelCase						(self	:			Dict						,			**lowerCAmelCase_	:			Any     ) ->							Union[str, Any]:
        return SpeechaTextTokenizer.from_pretrained(self.tmpdirname						,			**lowerCAmelCase_     )

  def 		_lowerCamelCase						(self	:			List[str]						,			**lowerCAmelCase_	:			List[str]     ) ->							Any:
        return SpeechaTextFeatureExtractor.from_pretrained(self.tmpdirname						,			**lowerCAmelCase_     )

  def 		_lowerCamelCase						(self	:			int     ) ->							str:
        shutil.rmtree(self.tmpdirname     )

  def 		_lowerCamelCase						(self	:			List[Any]     ) ->							Optional[Any]:
        snake_case_    							=				self.get_tokenizer()
        snake_case_    							=				self.get_feature_extractor()

        snake_case_    							=				SpeechaTextProcessor(tokenizer=lowerCAmelCase_						,			feature_extractor=lowerCAmelCase_     )

        processor.save_pretrained(self.tmpdirname     )
        snake_case_    							=				SpeechaTextProcessor.from_pretrained(self.tmpdirname     )

        self.assertEqual(processor.tokenizer.get_vocab()						,			tokenizer.get_vocab()     )
        self.assertIsInstance(processor.tokenizer						,			lowerCAmelCase_     )

        self.assertEqual(processor.feature_extractor.to_json_string()						,			feature_extractor.to_json_string()     )
        self.assertIsInstance(processor.feature_extractor						,			lowerCAmelCase_     )

  def 		_lowerCamelCase						(self	:			str     ) ->							int:
        snake_case_    							=				SpeechaTextProcessor(
            tokenizer=self.get_tokenizer()						,			feature_extractor=self.get_feature_extractor()     )
        processor.save_pretrained(self.tmpdirname     )

        snake_case_    							=				self.get_tokenizer(bos_token="(BOS)"						,			eos_token="(EOS)"     )
        snake_case_    							=				self.get_feature_extractor(do_normalize=lowerCAmelCase_						,			padding_value=1.0     )

        snake_case_    							=				SpeechaTextProcessor.from_pretrained(
            self.tmpdirname						,			bos_token="(BOS)"						,			eos_token="(EOS)"						,			do_normalize=lowerCAmelCase_						,			padding_value=1.0     )

        self.assertEqual(processor.tokenizer.get_vocab()						,			tokenizer_add_kwargs.get_vocab()     )
        self.assertIsInstance(processor.tokenizer						,			lowerCAmelCase_     )

        self.assertEqual(processor.feature_extractor.to_json_string()						,			feature_extractor_add_kwargs.to_json_string()     )
        self.assertIsInstance(processor.feature_extractor						,			lowerCAmelCase_     )

  def 		_lowerCamelCase						(self	:			Tuple     ) ->							Optional[Any]:
        snake_case_    							=				self.get_feature_extractor()
        snake_case_    							=				self.get_tokenizer()

        snake_case_    							=				SpeechaTextProcessor(tokenizer=lowerCAmelCase_						,			feature_extractor=lowerCAmelCase_     )

        snake_case_    							=				floats_list((3, 10_00)     )

        snake_case_    							=				feature_extractor(lowerCAmelCase_						,			return_tensors="np"     )
        snake_case_    							=				processor(lowerCAmelCase_						,			return_tensors="np"     )

        for key in input_feat_extract.keys():
              self.assertAlmostEqual(input_feat_extract[key].sum()						,			input_processor[key].sum()						,			delta=1E-2     )

  def 		_lowerCamelCase						(self	:			Union[str, Any]     ) ->							int:
        snake_case_    							=				self.get_feature_extractor()
        snake_case_    							=				self.get_tokenizer()

        snake_case_    							=				SpeechaTextProcessor(tokenizer=lowerCAmelCase_						,			feature_extractor=lowerCAmelCase_     )

        snake_case_    							=				"This is a test string"

        snake_case_    							=				processor(text=lowerCAmelCase_     )

        snake_case_    							=				tokenizer(lowerCAmelCase_     )

        for key in encoded_tok.keys():
              self.assertListEqual(encoded_tok[key]						,			encoded_processor[key]     )

  def 		_lowerCamelCase						(self	:			Union[str, Any]     ) ->							int:
        snake_case_    							=				self.get_feature_extractor()
        snake_case_    							=				self.get_tokenizer()

        snake_case_    							=				SpeechaTextProcessor(tokenizer=lowerCAmelCase_						,			feature_extractor=lowerCAmelCase_     )

        snake_case_    							=				[[1, 4, 5, 8, 1, 0, 8], [3, 4, 3, 1, 1, 8, 9]]

        snake_case_    							=				processor.batch_decode(lowerCAmelCase_     )
        snake_case_    							=				tokenizer.batch_decode(lowerCAmelCase_     )

        self.assertListEqual(lowerCAmelCase_						,			lowerCAmelCase_     )


  def 		_lowerCamelCase						(self	:			int     ) ->							int:
        snake_case_    							=				self.get_feature_extractor()
        snake_case_    							=				self.get_tokenizer()

        snake_case_    							=				SpeechaTextProcessor(tokenizer=lowerCAmelCase_						,			feature_extractor=lowerCAmelCase_     )

        self.assertListEqual(
            processor.model_input_names						,			feature_extractor.model_input_names						,			msg="`processor` and `feature_extractor` model input names do not match"						,			)

