
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     _SCREAMING_SNAKE_CASE     (      snake_case_			,       unittest.TestCase						):
	lowerCAmelCase__         = BertJapaneseTokenizer
	lowerCAmelCase__         = False
	lowerCAmelCase__         = True



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

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

					lowerCamelCase_						=			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						,  lowercase )				->       Union[str, Any]:
					lowerCamelCase_						=			"こんにちは、世界。 \nこんばんは、世界。"
					lowerCamelCase_						=			"こんにちは 、 世界 。 こんばんは 、 世界 。"
					return input_text, output_text



	def     SCREAMING_SNAKE_CASE_(    self						,  lowercase )				->       Any:
					lowerCamelCase_	,    lowerCamelCase_						=			self.get_input_output_texts(lowercase )
					lowerCamelCase_						=			tokenizer.encode(lowercase						,  add_special_tokens=lowercase )
					lowerCamelCase_						=			tokenizer.decode(lowercase						,  clean_up_tokenization_spaces=lowercase )
					return text, ids



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



	def     SCREAMING_SNAKE_CASE_(    self )				->       int:
					pass  # TODO add if relevant



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



	def     SCREAMING_SNAKE_CASE_(    self )				->       Tuple:
					lowerCamelCase_						=			self.tokenizer_class(self.vocab_file )

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



	def     SCREAMING_SNAKE_CASE_(    self )				->       Optional[int]:
					lowerCamelCase_						=			self.tokenizer_class(self.vocab_file						,  word_tokenizer_type="mecab" )
					self.assertIsNotNone(lowercase )

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

					lowerCamelCase_						=			os.path.join(self.tmpdirname						,  "tokenizer.bin" )
					with open(lowercase						,  "wb" ) as handle:
									pickle.dump(lowercase						,  lowercase )

					with open(lowercase						,  "rb" ) as handle:
									lowerCamelCase_						=			pickle.load(lowercase )

					lowerCamelCase_						=			tokenizer_new.tokenize(lowercase )

					self.assertListEqual(lowercase						,  lowercase )



	def     SCREAMING_SNAKE_CASE_(    self )				->       Dict:
					lowerCamelCase_						=			MecabTokenizer(mecab_dic="ipadic" )

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



	def     SCREAMING_SNAKE_CASE_(    self )				->       List[str]:
					try:
									lowerCamelCase_						=			MecabTokenizer(mecab_dic="unidic_lite" )
					except ModuleNotFoundError:
									return

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



	def     SCREAMING_SNAKE_CASE_(    self )				->       List[Any]:
					try:
									lowerCamelCase_						=			MecabTokenizer(mecab_dic="unidic" )
					except ModuleNotFoundError:
									return

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



	def     SCREAMING_SNAKE_CASE_(    self )				->       Any:
					lowerCamelCase_						=			MecabTokenizer(do_lower_case=lowercase						,  mecab_dic="ipadic" )

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



	def     SCREAMING_SNAKE_CASE_(    self )				->       int:
					try:
									lowerCamelCase_						=			MecabTokenizer(
									    do_lower_case=lowercase						,  normalize_text=lowercase						,  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]:
					lowerCamelCase_						=			MecabTokenizer(normalize_text=lowercase						,  mecab_dic="ipadic" )

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



	@require_sudachi
	def     SCREAMING_SNAKE_CASE_(    self )				->       Any:
					lowerCamelCase_						=			self.tokenizer_class(self.vocab_file						,  word_tokenizer_type="sudachi" )
					self.assertIsNotNone(lowercase )

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

					lowerCamelCase_						=			os.path.join(self.tmpdirname						,  "tokenizer.bin" )
					with open(lowercase						,  "wb" ) as handle:
									pickle.dump(lowercase						,  lowercase )

					with open(lowercase						,  "rb" ) as handle:
									lowerCamelCase_						=			pickle.load(lowercase )

					lowerCamelCase_						=			tokenizer_new.tokenize(lowercase )

					self.assertListEqual(lowercase						,  lowercase )



	@require_sudachi
	def     SCREAMING_SNAKE_CASE_(    self )				->       Union[str, Any]:
					lowerCamelCase_						=			SudachiTokenizer(sudachi_dict_type="core" )

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



	@require_sudachi
	def     SCREAMING_SNAKE_CASE_(    self )				->       str:
					lowerCamelCase_						=			SudachiTokenizer(sudachi_dict_type="core"						,  sudachi_split_mode="A" )

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



	@require_sudachi
	def     SCREAMING_SNAKE_CASE_(    self )				->       int:
					lowerCamelCase_						=			SudachiTokenizer(sudachi_dict_type="core"						,  sudachi_split_mode="B" )

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



	@require_sudachi
	def     SCREAMING_SNAKE_CASE_(    self )				->       List[str]:
					lowerCamelCase_						=			SudachiTokenizer(sudachi_dict_type="core"						,  sudachi_split_mode="C" )

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



	@require_sudachi
	def     SCREAMING_SNAKE_CASE_(    self )				->       List[Any]:
					lowerCamelCase_						=			SudachiTokenizer(do_lower_case=lowercase						,  sudachi_dict_type="core" )

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



	@require_sudachi
	def     SCREAMING_SNAKE_CASE_(    self )				->       Optional[int]:
					lowerCamelCase_						=			SudachiTokenizer(normalize_text=lowercase						,  sudachi_dict_type="core" )

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



	@require_sudachi
	def     SCREAMING_SNAKE_CASE_(    self )				->       Any:
					lowerCamelCase_						=			SudachiTokenizer(trim_whitespace=lowercase						,  sudachi_dict_type="core" )

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



	@require_jumanpp
	def     SCREAMING_SNAKE_CASE_(    self )				->       Optional[Any]:
					lowerCamelCase_						=			self.tokenizer_class(self.vocab_file						,  word_tokenizer_type="jumanpp" )
					self.assertIsNotNone(lowercase )

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

					lowerCamelCase_						=			os.path.join(self.tmpdirname						,  "tokenizer.bin" )
					with open(lowercase						,  "wb" ) as handle:
									pickle.dump(lowercase						,  lowercase )

					with open(lowercase						,  "rb" ) as handle:
									lowerCamelCase_						=			pickle.load(lowercase )

					lowerCamelCase_						=			tokenizer_new.tokenize(lowercase )

					self.assertListEqual(lowercase						,  lowercase )



	@require_jumanpp
	def     SCREAMING_SNAKE_CASE_(    self )				->       List[str]:
					lowerCamelCase_						=			JumanppTokenizer()

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



	@require_jumanpp
	def     SCREAMING_SNAKE_CASE_(    self )				->       Optional[int]:
					lowerCamelCase_						=			JumanppTokenizer(do_lower_case=lowercase )

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



	@require_jumanpp
	def     SCREAMING_SNAKE_CASE_(    self )				->       Optional[int]:
					lowerCamelCase_						=			JumanppTokenizer(normalize_text=lowercase )

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



	@require_jumanpp
	def     SCREAMING_SNAKE_CASE_(    self )				->       Union[str, Any]:
					lowerCamelCase_						=			JumanppTokenizer(trim_whitespace=lowercase )

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



	@require_jumanpp
	def     SCREAMING_SNAKE_CASE_(    self )				->       Union[str, Any]:
					lowerCamelCase_						=			JumanppTokenizer()

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



	def     SCREAMING_SNAKE_CASE_(    self )				->       Tuple:
					lowerCamelCase_						=			["[UNK]", "[CLS]", "[SEP]", "こんにちは", "こん", "にちは", "ばんは", "##こん", "##にちは", "##ばんは"]

					lowerCamelCase_						=			{}
					for i, token in enumerate(lowercase ):
									lowerCamelCase_						=			i
					lowerCamelCase_						=			WordpieceTokenizer(vocab=lowercase						,  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 )				->       Optional[int]:
					lowerCamelCase_						=			BertJapaneseTokenizer.from_pretrained("nlp-waseda/roberta-base-japanese-with-auto-jumanpp" )
					lowerCamelCase_						=			tokenizer.subword_tokenizer

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

					lowerCamelCase_						=			subword_tokenizer.tokenize("こんばんは こんばん にち は こんにちは" )
					self.assertListEqual(lowercase						,  ["▁こん", "ばん", "は", "▁こん", "ばん", "▁に", "ち", "▁は", "▁こんにちは"] )



	def     SCREAMING_SNAKE_CASE_(    self )				->       int:
					lowerCamelCase_						=			self.tokenizer_class.from_pretrained("cl-tohoku/bert-base-japanese" )

					lowerCamelCase_						=			tokenizer.encode("ありがとう。"						,  add_special_tokens=lowercase )
					lowerCamelCase_						=			tokenizer.encode("どういたしまして。"						,  add_special_tokens=lowercase )

					lowerCamelCase_						=			tokenizer.build_inputs_with_special_tokens(lowercase )
					lowerCamelCase_						=			tokenizer.build_inputs_with_special_tokens(lowercase						,  lowercase )

					# 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     _SCREAMING_SNAKE_CASE     (      snake_case_			,       unittest.TestCase						):
	lowerCAmelCase__         = BertJapaneseTokenizer
	lowerCAmelCase__         = False



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

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

					lowerCamelCase_						=			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						,  **lowercase )				->       Any:
					return BertJapaneseTokenizer.from_pretrained(self.tmpdirname						,  subword_tokenizer_type="character"						,  **lowercase )



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



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



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



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



	def     SCREAMING_SNAKE_CASE_(    self )				->       List[str]:
					lowerCamelCase_						=			self.tokenizer_class(self.vocab_file						,  subword_tokenizer_type="character" )

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



	def     SCREAMING_SNAKE_CASE_(    self )				->       List[str]:
					lowerCamelCase_						=			["[UNK]", "[CLS]", "[SEP]", "こ", "ん", "に", "ち", "は", "ば", "世", "界", "、", "。"]

					lowerCamelCase_						=			{}
					for i, token in enumerate(lowercase ):
									lowerCamelCase_						=			i
					lowerCamelCase_						=			CharacterTokenizer(vocab=lowercase						,  unk_token="[UNK]" )

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

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

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



	def     SCREAMING_SNAKE_CASE_(    self )				->       List[Any]:
					lowerCamelCase_						=			self.tokenizer_class.from_pretrained("cl-tohoku/bert-base-japanese-char" )

					lowerCamelCase_						=			tokenizer.encode("ありがとう。"						,  add_special_tokens=lowercase )
					lowerCamelCase_						=			tokenizer.encode("どういたしまして。"						,  add_special_tokens=lowercase )

					lowerCamelCase_						=			tokenizer.build_inputs_with_special_tokens(lowercase )
					lowerCamelCase_						=			tokenizer.build_inputs_with_special_tokens(lowercase						,  lowercase )

					# 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     _SCREAMING_SNAKE_CASE     (      unittest.TestCase						):



	def     SCREAMING_SNAKE_CASE_(    self )				->       Union[str, Any]:
					lowerCamelCase_						=			"cl-tohoku/bert-base-japanese"
					lowerCamelCase_						=			AutoTokenizer.from_pretrained(lowercase )
					self.assertIsInstance(lowercase						,  lowercase )




class     _SCREAMING_SNAKE_CASE     (      unittest.TestCase						):



	def     SCREAMING_SNAKE_CASE_(    self )				->       Tuple:
					lowerCamelCase_						=			"cl-tohoku/bert-base-japanese"
					with self.assertLogs("transformers"						,  level="WARNING" ) as cm:
									BertTokenizer.from_pretrained(lowercase )
									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." ) )
					lowerCamelCase_						=			"bert-base-cased"
					with self.assertLogs("transformers"						,  level="WARNING" ) as cm:
									BertJapaneseTokenizer.from_pretrained(lowercase )
									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." ) )




import math





def 			lowerCamelCase_ (				lowerCamelCase__	, lowerCamelCase__ = 0	, lowerCamelCase__ = 0    ):
				lowerCamelCase_						=			end or len(lowerCamelCase__    )
				for i in range(lowerCamelCase__	, lowerCamelCase__    ):
								lowerCamelCase_						=			i
								lowerCamelCase_						=			array[i]
								while temp_index != start and temp_index_value < array[temp_index - 1]:
												lowerCamelCase_						=			array[temp_index - 1]
												temp_index -= 1
								lowerCamelCase_						=			temp_index_value
				return array





def 			lowerCamelCase_ (				lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    ):  # Max Heap
				lowerCamelCase_						=			index
				lowerCamelCase_						=			2 * index + 1  # Left Node
				lowerCamelCase_						=			2 * index + 2  # Right Node

				if left_index < heap_size and array[largest] < array[left_index]:
								lowerCamelCase_						=			left_index

				if right_index < heap_size and array[largest] < array[right_index]:
								lowerCamelCase_						=			right_index

				if largest != index:
								lowerCamelCase_	,    lowerCamelCase_						=			array[largest], array[index]
								heapify(lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    )





def 			lowerCamelCase_ (				lowerCamelCase__    ):
				lowerCamelCase_						=			len(lowerCamelCase__    )

				for i in range(n // 2	, -1	, -1    ):
								heapify(lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    )

				for i in range(n - 1	, 0	, -1    ):
								lowerCamelCase_	,    lowerCamelCase_						=			array[0], array[i]
								heapify(lowerCamelCase__	, 0	, lowerCamelCase__    )

				return array





def 			lowerCamelCase_ (				lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    ):
				if (array[first_index] > array[middle_index]) != (
				    array[first_index] > array[last_index]
				):
								return array[first_index]
				elif (array[middle_index] > array[first_index]) != (
				    array[middle_index] > array[last_index]
				):
								return array[middle_index]
				else:
								return array[last_index]





def 			lowerCamelCase_ (				lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    ):
				lowerCamelCase_						=			low
				lowerCamelCase_						=			high
				while True:
								while array[i] < pivot:
												i += 1
								j -= 1
								while pivot < array[j]:
												j -= 1
								if i >= j:
												return i
								lowerCamelCase_	,    lowerCamelCase_						=			array[j], array[i]
								i += 1





def 			lowerCamelCase_ (				lowerCamelCase__    ):
				if len(lowerCamelCase__    ) == 0:
								return array
				lowerCamelCase_						=			2 * math.ceil(math.loga(len(lowerCamelCase__    )    )    )
				lowerCamelCase_						=			1_6
				return intro_sort(lowerCamelCase__	, 0	, len(lowerCamelCase__    )	, lowerCamelCase__	, lowerCamelCase__    )





def 			lowerCamelCase_ (				lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    ):
				while end - start > size_threshold:
								if max_depth == 0:
												return heap_sort(lowerCamelCase__    )
								max_depth -= 1
								lowerCamelCase_						=			median_of_a(lowerCamelCase__	, lowerCamelCase__	, start + ((end - start) // 2) + 1	, end - 1    )
								lowerCamelCase_						=			partition(lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    )
								intro_sort(lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    )
								lowerCamelCase_						=			p
				return insertion_sort(lowerCamelCase__	, lowerCamelCase__	, lowerCamelCase__    )


if __name__ == "__main__":
			import doctest

			doctest.testmod()

			__A				=input('''Enter numbers separated by a comma : ''').strip()
			__A				=[float(item) for item in user_input.split(''',''')]
			print(sort(unsorted))


