






"""simple docstring"""





import os
import pickle
import unittest

from transformers import AutoTokenizer
from transformers.models.bert.tokenization_bert import BertTokenizer
from transformers.models.bert_japanese.tokenization_bert_japanese import (
    VOCAB_FILES_NAMES,
    BertJapaneseTokenizer,
    CharacterTokenizer,
    JumanppTokenizer,
    MecabTokenizer,
    SudachiTokenizer,
    WordpieceTokenizer,
)
from transformers.testing_utils import custom_tokenizers, require_jumanpp, require_sudachi

from ...test_tokenization_common import TokenizerTesterMixin
@custom_tokenizers
class    __lowerCamelCase    (  __lowercase							,	unittest.TestCase  ):
   a      :				str 						=BertJapaneseTokenizer
   a      :				List[Any] 						=False
   a      :				Optional[Any] 						=True

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Union[str, Any]:
       super().setUp()

       UpperCamelCase__         =    [
           "[UNK]",
           "[CLS]",
           "[SEP]",
           "こんにちは",
           "こん",
           "にちは",
           "ばんは",
           "##こん",
           "##にちは",
           "##ばんは",
           "世界",
           "##世界",
           "、",
           "##、",
           "。",
           "##。",
       ]

       UpperCamelCase__         =    os.path.join(self.tmpdirname ,				VOCAB_FILES_NAMES['vocab_file']      )
       with open(self.vocab_file ,				'w' ,				encoding='utf-8'      ) as vocab_writer:
           vocab_writer.write(''.join([x + '\n' for x in vocab_tokens]      )      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       Union[str, Any]:
       UpperCamelCase__         =    "こんにちは、世界。 \nこんばんは、世界。"
       UpperCamelCase__         =    "こんにちは 、 世界 。 こんばんは 、 世界 。"
       return input_text, output_text

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       Dict:
       UpperCamelCase__         =    self.get_input_output_texts(snake_case_      )
       UpperCamelCase__         =    tokenizer.encode(snake_case_ ,				add_special_tokens=snake_case_      )
       UpperCamelCase__         =    tokenizer.decode(snake_case_ ,				clean_up_tokenization_spaces=snake_case_      )
       return text, ids

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[Any]:
       pass  # TODO add if relevant

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Union[str, Any]:
       pass  # TODO add if relevant

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Tuple:
       pass  # TODO add if relevant

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       UpperCamelCase__         =    self.tokenizer_class(self.vocab_file      )

       UpperCamelCase__         =    tokenizer.tokenize('こんにちは、世界。\nこんばんは、世界。'      )
       self.assertListEqual(snake_case_ ,				['こんにちは', '、', '世界', '。', 'こん', '##ばんは', '、', '世界', '。']      )
       self.assertListEqual(tokenizer.convert_tokens_to_ids(snake_case_      ) ,				[3, 12, 10, 14, 4, 9, 12, 10, 14]      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Dict:
       UpperCamelCase__         =    self.tokenizer_class(self.vocab_file ,				word_tokenizer_type='mecab'      )
       self.assertIsNotNone(snake_case_      )

       UpperCamelCase__         =    "こんにちは、世界。\nこんばんは、世界。"
       UpperCamelCase__         =    tokenizer.tokenize(snake_case_      )
       self.assertListEqual(snake_case_ ,				['こんにちは', '、', '世界', '。', 'こん', '##ばんは', '、', '世界', '。']      )
       self.assertListEqual(tokenizer.convert_tokens_to_ids(snake_case_      ) ,				[3, 12, 10, 14, 4, 9, 12, 10, 14]      )

       UpperCamelCase__         =    os.path.join(self.tmpdirname ,				'tokenizer.bin'      )
       with open(snake_case_ ,				'wb'      ) as handle:
           pickle.dump(snake_case_ ,				snake_case_      )

       with open(snake_case_ ,				'rb'      ) as handle:
           UpperCamelCase__         =    pickle.load(snake_case_      )

       UpperCamelCase__         =    tokenizer_new.tokenize(snake_case_      )

       self.assertListEqual(snake_case_ ,				snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[Any]:
       UpperCamelCase__         =    MecabTokenizer(mecab_dic='ipadic'      )

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['アップルストア', 'で', 'iPhone', '8', 'が', '発売', 'さ', 'れ', 'た', '。'] ,				)

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       try:
           UpperCamelCase__         =    MecabTokenizer(mecab_dic='unidic_lite'      )
       except ModuleNotFoundError:
           return

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['アップル', 'ストア', 'で', 'iPhone', '8', 'が', '発売', 'さ', 'れ', 'た', '。'] ,				)

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Union[str, Any]:
       try:
           UpperCamelCase__         =    MecabTokenizer(mecab_dic='unidic'      )
       except ModuleNotFoundError:
           return

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['アップル', 'ストア', 'で', 'iPhone', '8', 'が', '発売', 'さ', 'れ', 'た', '。'] ,				)

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       UpperCamelCase__         =    MecabTokenizer(do_lower_case=snake_case_ ,				mecab_dic='ipadic'      )

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['アップルストア', 'で', 'iphone', '8', 'が', '発売', 'さ', 'れ', 'た', '。'] ,				)

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[Any]:
       try:
           UpperCamelCase__         =    MecabTokenizer(
               do_lower_case=snake_case_ ,				normalize_text=snake_case_ ,				mecab_option='-d /usr/local/lib/mecab/dic/jumandic'      )
       except RuntimeError:
           # if dict doesn't exist in the system, previous code raises this error.
           return

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['ｱｯﾌﾟﾙストア', 'で', 'iPhone', '８', 'が', '発売', 'さ', 'れた', '\u3000', '。'] ,				)

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[int]:
       UpperCamelCase__         =    MecabTokenizer(normalize_text=snake_case_ ,				mecab_dic='ipadic'      )

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['ｱｯﾌﾟﾙストア', 'で', 'iPhone', '８', 'が', '発売', 'さ', 'れ', 'た', '　', '。'] ,				)

   @require_sudachi
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[Any]:
       UpperCamelCase__         =    self.tokenizer_class(self.vocab_file ,				word_tokenizer_type='sudachi'      )
       self.assertIsNotNone(snake_case_      )

       UpperCamelCase__         =    "こんにちは、世界。\nこんばんは、世界。"
       UpperCamelCase__         =    tokenizer.tokenize(snake_case_      )
       self.assertListEqual(snake_case_ ,				['こんにちは', '、', '世界', '。', 'こん', '##ばんは', '、', '世界', '。']      )
       self.assertListEqual(tokenizer.convert_tokens_to_ids(snake_case_      ) ,				[3, 12, 10, 14, 4, 9, 12, 10, 14]      )

       UpperCamelCase__         =    os.path.join(self.tmpdirname ,				'tokenizer.bin'      )
       with open(snake_case_ ,				'wb'      ) as handle:
           pickle.dump(snake_case_ ,				snake_case_      )

       with open(snake_case_ ,				'rb'      ) as handle:
           UpperCamelCase__         =    pickle.load(snake_case_      )

       UpperCamelCase__         =    tokenizer_new.tokenize(snake_case_      )

       self.assertListEqual(snake_case_ ,				snake_case_      )

   @require_sudachi
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Tuple:
       UpperCamelCase__         =    SudachiTokenizer(sudachi_dict_type='core'      )

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				[' ', '\t', 'アップル', 'ストア', 'で', 'iPhone', '8', ' ', 'が', ' ', ' ', '\n ', '発売', 'さ', 'れ', 'た', ' ', '。', ' ', ' '] ,				)

   @require_sudachi
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       UpperCamelCase__         =    SudachiTokenizer(sudachi_dict_type='core' ,				sudachi_split_mode='A'      )

       self.assertListEqual(tokenizer.tokenize('外国人参政権'      ) ,				['外国', '人', '参政', '権']      )

   @require_sudachi
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Tuple:
       UpperCamelCase__         =    SudachiTokenizer(sudachi_dict_type='core' ,				sudachi_split_mode='B'      )

       self.assertListEqual(tokenizer.tokenize('外国人参政権'      ) ,				['外国人', '参政権']      )

   @require_sudachi
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       UpperCamelCase__         =    SudachiTokenizer(sudachi_dict_type='core' ,				sudachi_split_mode='C'      )

       self.assertListEqual(tokenizer.tokenize('外国人参政権'      ) ,				['外国人参政権']      )

   @require_sudachi
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Union[str, Any]:
       UpperCamelCase__         =    SudachiTokenizer(do_lower_case=snake_case_ ,				sudachi_dict_type='core'      )

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				[' ', '\t', 'アップル', 'ストア', 'で', 'iphone', '8', ' ', 'が', ' ', ' ', '\n ', '発売', 'さ', 'れ', 'た', ' ', '。', ' ', ' '] ,				)

   @require_sudachi
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       UpperCamelCase__         =    SudachiTokenizer(normalize_text=snake_case_ ,				sudachi_dict_type='core'      )

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				[' ', '\t', 'ｱｯﾌﾟﾙ', 'ストア', 'で', 'iPhone', '８', ' ', 'が', ' ', ' ', '\n ', '発売', 'さ', 'れ', 'た', '\u3000', '。', ' ', ' '] ,				)

   @require_sudachi
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       UpperCamelCase__         =    SudachiTokenizer(trim_whitespace=snake_case_ ,				sudachi_dict_type='core'      )

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['アップル', 'ストア', 'で', 'iPhone', '8', 'が', '発売', 'さ', 'れ', 'た', '。'] ,				)

   @require_jumanpp
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[Any]:
       UpperCamelCase__         =    self.tokenizer_class(self.vocab_file ,				word_tokenizer_type='jumanpp'      )
       self.assertIsNotNone(snake_case_      )

       UpperCamelCase__         =    "こんにちは、世界。\nこんばんは、世界。"
       UpperCamelCase__         =    tokenizer.tokenize(snake_case_      )
       self.assertListEqual(snake_case_ ,				['こんにちは', '、', '世界', '。', 'こん', '##ばんは', '、', '世界', '。']      )
       self.assertListEqual(tokenizer.convert_tokens_to_ids(snake_case_      ) ,				[3, 12, 10, 14, 4, 9, 12, 10, 14]      )

       UpperCamelCase__         =    os.path.join(self.tmpdirname ,				'tokenizer.bin'      )
       with open(snake_case_ ,				'wb'      ) as handle:
           pickle.dump(snake_case_ ,				snake_case_      )

       with open(snake_case_ ,				'rb'      ) as handle:
           UpperCamelCase__         =    pickle.load(snake_case_      )

       UpperCamelCase__         =    tokenizer_new.tokenize(snake_case_      )

       self.assertListEqual(snake_case_ ,				snake_case_      )

   @require_jumanpp
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       str:
       UpperCamelCase__         =    JumanppTokenizer()

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['アップル', 'ストア', 'で', 'iPhone', '8', '\u3000', 'が', '\u3000', '\u3000', '\u3000', '発売', 'さ', 'れた', '\u3000', '。'] ,				)

   @require_jumanpp
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[Any]:
       UpperCamelCase__         =    JumanppTokenizer(do_lower_case=snake_case_      )

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['アップル', 'ストア', 'で', 'iphone', '8', '\u3000', 'が', '\u3000', '\u3000', '\u3000', '発売', 'さ', 'れた', '\u3000', '。'] ,				)

   @require_jumanpp
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       str:
       UpperCamelCase__         =    JumanppTokenizer(normalize_text=snake_case_      )

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['ｱ', 'ｯ', 'ﾌ', 'ﾟ', 'ﾙ', 'ストア', 'で', 'iPhone', '８', '\u3000', 'が', '\u3000', '\u3000', '\u3000', '発売', 'さ', 'れた', '\u3000', '。'] ,				)

   @require_jumanpp
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[Any]:
       UpperCamelCase__         =    JumanppTokenizer(trim_whitespace=snake_case_      )

       self.assertListEqual(
           tokenizer.tokenize(' \tｱｯﾌﾟﾙストアでiPhone８ が  \n 発売された　。  '      ) ,				['アップル', 'ストア', 'で', 'iPhone', '8', 'が', '発売', 'さ', 'れた', '。'] ,				)

   @require_jumanpp
   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[Any]:
       UpperCamelCase__         =    JumanppTokenizer()

       self.assertListEqual(
           tokenizer.tokenize('ありがとうございますm(_ _)ｍ見つけるのが大変です。'      ) ,				['ありがとう', 'ございます', 'm(_ _)m', '見つける', 'の', 'が', '大変です', '。'] ,				)

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       UpperCamelCase__         =    ["[UNK]", "[CLS]", "[SEP]", "こんにちは", "こん", "にちは", "ばんは", "##こん", "##にちは", "##ばんは"]

       UpperCamelCase__         =    {}
       for i, token in enumerate(snake_case_      ):
           UpperCamelCase__         =    i
       UpperCamelCase__         =    WordpieceTokenizer(vocab=snake_case_ ,				unk_token='[UNK]'      )

       self.assertListEqual(tokenizer.tokenize(''      ) ,				[]      )

       self.assertListEqual(tokenizer.tokenize('こんにちは'      ) ,				['こんにちは']      )

       self.assertListEqual(tokenizer.tokenize('こんばんは'      ) ,				['こん', '##ばんは']      )

       self.assertListEqual(tokenizer.tokenize('こんばんは こんばんにちは こんにちは'      ) ,				['こん', '##ばんは', '[UNK]', 'こんにちは']      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Tuple:
       UpperCamelCase__         =    BertJapaneseTokenizer.from_pretrained('nlp-waseda/roberta-base-japanese-with-auto-jumanpp'      )
       UpperCamelCase__         =    tokenizer.subword_tokenizer

       UpperCamelCase__         =    subword_tokenizer.tokenize('国境 の 長い トンネル を 抜ける と 雪国 であった 。'      )
       self.assertListEqual(snake_case_ ,				['▁国境', '▁の', '▁長い', '▁トンネル', '▁を', '▁抜ける', '▁と', '▁雪', '国', '▁であった', '▁。']      )

       UpperCamelCase__         =    subword_tokenizer.tokenize('こんばんは こんばん にち は こんにちは'      )
       self.assertListEqual(snake_case_ ,				['▁こん', 'ばん', 'は', '▁こん', 'ばん', '▁に', 'ち', '▁は', '▁こんにちは']      )







   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       UpperCamelCase__         =    self.tokenizer_class.from_pretrained('cl-tohoku/bert-base-japanese'      )

       UpperCamelCase__         =    tokenizer.encode('ありがとう。' ,				add_special_tokens=snake_case_      )
       UpperCamelCase__         =    tokenizer.encode('どういたしまして。' ,				add_special_tokens=snake_case_      )

       UpperCamelCase__         =    tokenizer.build_inputs_with_special_tokens(snake_case_      )
       UpperCamelCase__         =    tokenizer.build_inputs_with_special_tokens(snake_case_ ,				snake_case_      )

       # 2 is for "[CLS]", 3 is for "[SEP]"
       assert encoded_sentence == [2] + text + [3]
       assert encoded_pair == [2] + text + [3] + text_a + [3]







@custom_tokenizers
class    __lowerCamelCase    (  __lowercase							,	unittest.TestCase  ):
   a      :				str 						=BertJapaneseTokenizer
   a      :				Union[str, Any] 						=False

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[Any]:
       super().setUp()

       UpperCamelCase__         =    ["[UNK]", "[CLS]", "[SEP]", "こ", "ん", "に", "ち", "は", "ば", "世", "界", "、", "。"]

       UpperCamelCase__         =    os.path.join(self.tmpdirname ,				VOCAB_FILES_NAMES['vocab_file']      )
       with open(self.vocab_file ,				'w' ,				encoding='utf-8'      ) as vocab_writer:
           vocab_writer.write(''.join([x + '\n' for x in vocab_tokens]      )      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				**snake_case_      )		->       List[Any]:
       return BertJapaneseTokenizer.from_pretrained(self.tmpdirname ,				subword_tokenizer_type='character' ,				**snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       List[Any]:
       UpperCamelCase__         =    "こんにちは、世界。 \nこんばんは、世界。"
       UpperCamelCase__         =    "こ ん に ち は 、 世 界 。 こ ん ば ん は 、 世 界 。"
       return input_text, output_text

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       pass  # TODO add if relevant

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[Any]:
       pass  # TODO add if relevant

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       pass  # TODO add if relevant

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Optional[Any]:
       UpperCamelCase__         =    self.tokenizer_class(self.vocab_file ,				subword_tokenizer_type='character'      )

       UpperCamelCase__         =    tokenizer.tokenize('こんにちは、世界。 \nこんばんは、世界。'      )
       self.assertListEqual(
           snake_case_ ,				['こ', 'ん', 'に', 'ち', 'は', '、', '世', '界', '。', 'こ', 'ん', 'ば', 'ん', 'は', '、', '世', '界', '。']      )
       self.assertListEqual(
           tokenizer.convert_tokens_to_ids(snake_case_      ) ,				[3, 4, 5, 6, 7, 11, 9, 10, 12, 3, 4, 8, 4, 7, 11, 9, 10, 12]      )

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       UpperCamelCase__         =    ["[UNK]", "[CLS]", "[SEP]", "こ", "ん", "に", "ち", "は", "ば", "世", "界", "、", "。"]

       UpperCamelCase__         =    {}
       for i, token in enumerate(snake_case_      ):
           UpperCamelCase__         =    i
       UpperCamelCase__         =    CharacterTokenizer(vocab=snake_case_ ,				unk_token='[UNK]'      )

       self.assertListEqual(tokenizer.tokenize(''      ) ,				[]      )

       self.assertListEqual(tokenizer.tokenize('こんにちは'      ) ,				['こ', 'ん', 'に', 'ち', 'は']      )

       self.assertListEqual(tokenizer.tokenize('こんにちほ'      ) ,				['こ', 'ん', 'に', 'ち', '[UNK]']      )







   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       int:
       UpperCamelCase__         =    self.tokenizer_class.from_pretrained('cl-tohoku/bert-base-japanese-char'      )

       UpperCamelCase__         =    tokenizer.encode('ありがとう。' ,				add_special_tokens=snake_case_      )
       UpperCamelCase__         =    tokenizer.encode('どういたしまして。' ,				add_special_tokens=snake_case_      )

       UpperCamelCase__         =    tokenizer.build_inputs_with_special_tokens(snake_case_      )
       UpperCamelCase__         =    tokenizer.build_inputs_with_special_tokens(snake_case_ ,				snake_case_      )

       # 2 is for "[CLS]", 3 is for "[SEP]"
       assert encoded_sentence == [2] + text + [3]
       assert encoded_pair == [2] + text + [3] + text_a + [3]







@custom_tokenizers
class    __lowerCamelCase    (  unittest.TestCase  ):

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       List[str]:
       UpperCamelCase__         =    "cl-tohoku/bert-base-japanese"
       UpperCamelCase__         =    AutoTokenizer.from_pretrained(snake_case_      )
       self.assertIsInstance(snake_case_ ,				snake_case_      )







class    __lowerCamelCase    (  unittest.TestCase  ):

   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       Any:
       UpperCamelCase__         =    "cl-tohoku/bert-base-japanese"
       with self.assertLogs('transformers' ,				level='WARNING'      ) as cm:
           BertTokenizer.from_pretrained(snake_case_      )
           self.assertTrue(
               cm.records[0].message.startswith(
                   'The tokenizer class you load from this checkpoint is not the same type as the class this function'
                   ' is called from.'      )      )
       UpperCamelCase__         =    "bert-base-cased"
       with self.assertLogs('transformers' ,				level='WARNING'      ) as cm:
           BertJapaneseTokenizer.from_pretrained(snake_case_      )
           self.assertTrue(
               cm.records[0].message.startswith(
                   'The tokenizer class you load from this checkpoint is not the same type as the class this function'
                   ' is called from.'      )      )












"""simple docstring"""





from __future__ import annotations

from typing import Generic, TypeVar

A__					: Any=	TypeVar("""T""")
class    __lowerCamelCase    (  Generic[T]  ):

   def __init__(					self ,				snake_case_      )		->       None:
       UpperCamelCase__         =    data
       UpperCamelCase__         =    self
       UpperCamelCase__         =    0







class    __lowerCamelCase    (  Generic[T]  ):

   def __init__(					self      )		->       None:
       # map from node name to the node object
       UpperCamelCase__         =    {}

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       None:
       # create a new set with x as its member
       UpperCamelCase__         =    DisjointSetTreeNode(snake_case_      )

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       DisjointSetTreeNode[T]:
       # find the set x belongs to (with path-compression)
       UpperCamelCase__         =    self.map[data]
       if elem_ref != elem_ref.parent:
           UpperCamelCase__         =    self.find_set(elem_ref.parent.data      )
       return elem_ref.parent

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       None:
       # helper function for union operation
       if nodea.rank > nodea.rank:
           UpperCamelCase__         =    nodea
       else:
           UpperCamelCase__         =    nodea
           if nodea.rank == nodea.rank:
               nodea.rank += 1







   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_      )		->       None:
       # merge 2 disjoint sets
       self.link(self.find_set(snake_case_      ) ,				self.find_set(snake_case_      )      )







class    __lowerCamelCase    (  Generic[T]  ):

   def __init__(					self      )		->       None:
       # connections: map from the node to the neighbouring nodes (with weights)
       UpperCamelCase__         =    {}

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_      )		->       None:
       # add a node ONLY if its not present in the graph
       if node not in self.connections:
           UpperCamelCase__         =    {}

   def 						SCREAMING_SNAKE_CASE__ (					self ,				snake_case_ ,				snake_case_ ,				snake_case_      )		->       None:
       # add an edge with the given weight
       self.add_node(snake_case_      )
       self.add_node(snake_case_      )
       UpperCamelCase__         =    weight
       UpperCamelCase__         =    weight







   def 						SCREAMING_SNAKE_CASE__ (					self      )		->       GraphUndirectedWeighted[T]:
       UpperCamelCase__         =    []
       UpperCamelCase__         =    set()
       for start in self.connections:
           for end in self.connections[start]:
               if (start, end) not in seen:
                   seen.add((end, start)      )
                   edges.append((start, end, self.connections[start][end])      )
       edges.sort(key=lambda snake_case_      : x[2]      )

       # creating the disjoint set
       UpperCamelCase__         =    DisjointSetTree[T]()
       for node in self.connections:
           disjoint_set.make_set(snake_case_      )

       # MST generation
       UpperCamelCase__         =    0
       UpperCamelCase__         =    0
       UpperCamelCase__         =    GraphUndirectedWeighted[T]()
       while num_edges < len(self.connections      ) - 1:
           UpperCamelCase__       ,						UpperCamelCase__       ,						UpperCamelCase__         =    edges[index]
           index += 1
           UpperCamelCase__         =    disjoint_set.find_set(snake_case_      )
           UpperCamelCase__         =    disjoint_set.find_set(snake_case_      )
           if parent_u != parent_v:
               num_edges += 1
               graph.add_edge(snake_case_ ,				snake_case_ ,				snake_case_      )
               disjoint_set.union(snake_case_ ,				snake_case_      )
       return graph




