






import unittest

from transformers import DebertaVaTokenizer, DebertaVaTokenizerFast
from transformers.testing_utils import get_tests_dir, require_sentencepiece, require_tokenizers, slow

from ...test_tokenization_common import TokenizerTesterMixin


__UpperCamelCase      :      str     						=						get_tests_dir("""fixtures/spiece.model""")


@require_sentencepiece
@require_tokenizers
class        __UpperCamelCase    (     _lowerCAmelCase   ,			unittest.TestCase   ):
	__snake_case	:Any   =       DebertaVaTokenizer
	__snake_case	:Optional[Any]   =       DebertaVaTokenizerFast
	__snake_case	:int   =       True
	__snake_case	:str   =       True







	def  _a   (  self      :							Any			)		-> Union[str, Any]:
		"""simple docstring"""







		super().setUp()

		# We have a SentencePiece fixture for testing
		__lowercase             =  DebertaVaTokenizer(_lowerCAmelCase       ,				unk_token="""<unk>"""			)
		tokenizer.save_pretrained(self.tmpdirname			)







	def  _a   (  self      :							str       ,				_lowerCAmelCase      :							List[str]			)		-> Tuple:
		"""simple docstring"""







		__lowercase             =  """this is a test"""
		__lowercase             =  """this is a test"""
		return input_text, output_text







	def  _a   (  self      :							Tuple			)		-> List[Any]:
		"""simple docstring"""







		__lowercase             =  """<pad>"""
		__lowercase             =  0

		self.assertEqual(self.get_tokenizer()._convert_token_to_id(_lowerCAmelCase			)       ,				_lowerCAmelCase			)
		self.assertEqual(self.get_tokenizer()._convert_id_to_token(_lowerCAmelCase			)       ,				_lowerCAmelCase			)







	def  _a   (  self      :							Union[str, Any]			)		-> Tuple:
		"""simple docstring"""







		__lowercase             =  list(self.get_tokenizer().get_vocab().keys()			)
		self.assertEqual(vocab_keys[0]       ,				"""<pad>"""			)
		self.assertEqual(vocab_keys[1]       ,				"""<unk>"""			)
		self.assertEqual(vocab_keys[-1]       ,				"""[PAD]"""			)
		self.assertEqual(len(_lowerCAmelCase			)       ,				3_0001			)







	def  _a   (  self      :							Union[str, Any]			)		-> List[Any]:
		"""simple docstring"""







		self.assertEqual(self.get_tokenizer().vocab_size       ,				3_0000			)







	def  _a   (  self      :							int			)		-> str:
		"""simple docstring"""







		__lowercase             =  """ \tHeLLo!how  \n Are yoU?  """
		__lowercase             =  ["""▁hello""", """!""", """how""", """▁are""", """▁you""", """?"""]
		# fmt: on

		__lowercase             =  DebertaVaTokenizer(_lowerCAmelCase       ,				do_lower_case=_lowerCAmelCase			)
		__lowercase             =  tokenizer.convert_ids_to_tokens(tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)

		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		__lowercase             =  DebertaVaTokenizerFast(_lowerCAmelCase       ,				do_lower_case=_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)

		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)







	@unittest.skip("""There is an inconsistency between slow and fast tokenizer due to a bug in the fast one."""			)
	def  _a   (  self      :							Union[str, Any]			)		-> Tuple:
		"""simple docstring"""







		pass







	@unittest.skip("""There is an inconsistency between slow and fast tokenizer due to a bug in the fast one."""			)
	def  _a   (  self      :							int			)		-> Optional[Any]:
		"""simple docstring"""







		pass







	def  _a   (  self      :							str			)		-> Optional[Any]:
		"""simple docstring"""







		__lowercase             =  """I was born in 92000, and this is falsé."""
		__lowercase             =  ["""▁""", """<unk>""", """▁was""", """▁born""", """▁in""", """▁9""", """2000""", """▁""", """,""", """▁and""", """▁this""", """▁is""", """▁fal""", """s""", """<unk>""", """▁""", """.""", ]
		# fmt: on

		__lowercase             =  DebertaVaTokenizer(_lowerCAmelCase       ,				split_by_punct=_lowerCAmelCase			)
		__lowercase             =  tokenizer.convert_ids_to_tokens(tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)

		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		__lowercase             =  DebertaVaTokenizerFast(_lowerCAmelCase       ,				split_by_punct=_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)

		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)







	def  _a   (  self      :							List[str]			)		-> List[Any]:
		"""simple docstring"""







		__lowercase             =  """I was born in 92000, and this is falsé."""
		__lowercase             =  ["""▁i""", """▁was""", """▁born""", """▁in""", """▁9""", """2000""", """▁""", """,""", """▁and""", """▁this""", """▁is""", """▁fal""", """s""", """<unk>""", """▁""", """.""", ]
		# fmt: on

		__lowercase             =  DebertaVaTokenizer(_lowerCAmelCase       ,				do_lower_case=_lowerCAmelCase       ,				split_by_punct=_lowerCAmelCase			)
		__lowercase             =  tokenizer.convert_ids_to_tokens(tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		__lowercase             =  DebertaVaTokenizerFast(_lowerCAmelCase       ,				do_lower_case=_lowerCAmelCase       ,				split_by_punct=_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)







	def  _a   (  self      :							int			)		-> Optional[Any]:
		"""simple docstring"""







		__lowercase             =  """I was born in 92000, and this is falsé."""
		__lowercase             =  ["""▁i""", """▁was""", """▁born""", """▁in""", """▁9""", """2000""", """,""", """▁and""", """▁this""", """▁is""", """▁fal""", """s""", """<unk>""", """.""", ]
		# fmt: on

		__lowercase             =  DebertaVaTokenizer(_lowerCAmelCase       ,				do_lower_case=_lowerCAmelCase       ,				split_by_punct=_lowerCAmelCase			)
		__lowercase             =  tokenizer.convert_ids_to_tokens(tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)

		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		__lowercase             =  DebertaVaTokenizerFast(_lowerCAmelCase       ,				do_lower_case=_lowerCAmelCase       ,				split_by_punct=_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)

		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)







	def  _a   (  self      :							Tuple			)		-> Union[str, Any]:
		"""simple docstring"""







		__lowercase             =  """I was born in 92000, and this is falsé."""
		__lowercase             =  ["""▁""", """<unk>""", """▁was""", """▁born""", """▁in""", """▁9""", """2000""", """▁""", """,""", """▁and""", """▁this""", """▁is""", """▁fal""", """s""", """<unk>""", """▁""", """.""", ]
		# fmt: on

		__lowercase             =  DebertaVaTokenizer(_lowerCAmelCase       ,				do_lower_case=_lowerCAmelCase       ,				split_by_punct=_lowerCAmelCase			)
		__lowercase             =  tokenizer.convert_ids_to_tokens(tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)

		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		__lowercase             =  DebertaVaTokenizerFast(_lowerCAmelCase       ,				do_lower_case=_lowerCAmelCase       ,				split_by_punct=_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)

		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)







	def  _a   (  self      :							Tuple			)		-> Tuple:
		"""simple docstring"""







		__lowercase             =  """ \tHeLLo!how  \n Are yoU?  """
		__lowercase             =  ["""▁""", """<unk>""", """e""", """<unk>""", """o""", """!""", """how""", """▁""", """<unk>""", """re""", """▁yo""", """<unk>""", """?"""]
		# fmt: on

		__lowercase             =  DebertaVaTokenizer(_lowerCAmelCase       ,				do_lower_case=_lowerCAmelCase       ,				split_by_punct=_lowerCAmelCase			)
		__lowercase             =  tokenizer.convert_ids_to_tokens(tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)

		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		__lowercase             =  DebertaVaTokenizerFast(_lowerCAmelCase       ,				do_lower_case=_lowerCAmelCase       ,				split_by_punct=_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)

		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)







	def  _a   (  self      :							Optional[int]			)		-> Union[str, Any]:
		"""simple docstring"""







		__lowercase             =  self.get_tokenizer()
		__lowercase             =  self.get_rust_tokenizer()

		__lowercase             =  """I was born in 92000, and this is falsé."""

		__lowercase             =  tokenizer.convert_ids_to_tokens(tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)
		__lowercase             =  rust_tokenizer.convert_ids_to_tokens(rust_tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		__lowercase             =  tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		__lowercase             =  self.get_rust_tokenizer()
		__lowercase             =  tokenizer.encode(_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.encode(_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)







	def  _a   (  self      :							Dict			)		-> List[str]:
		"""simple docstring"""







		__lowercase             =  """This is a test"""
		__lowercase             =  [13, 1, 4398, 25, 21, 1289]
		__lowercase             =  ["""▁""", """T""", """his""", """▁is""", """▁a""", """▁test"""]
		__lowercase             =  ["""▁""", """<unk>""", """his""", """▁is""", """▁a""", """▁test"""]

		__lowercase             =  DebertaVaTokenizer(_lowerCAmelCase       ,				keep_accents=_lowerCAmelCase			)
		__lowercase             =  DebertaVaTokenizerFast(_lowerCAmelCase       ,				keep_accents=_lowerCAmelCase			)

		__lowercase             =  tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)
		__lowercase             =  tokenizer.tokenize(_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)
		__lowercase             =  tokenizer.convert_ids_to_tokens(_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		__lowercase             =  rust_tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.tokenize(_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.convert_ids_to_tokens(_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		# fmt: off
		__lowercase             =  """I was born in 92000, and this is falsé."""
		__lowercase             =  [13, 1, 23, 386, 19, 561, 3050, 15, 17, 48, 25, 8256, 18, 1, 9]
		__lowercase             =  ["""▁""", """I""", """▁was""", """▁born""", """▁in""", """▁9""", """2000""", """,""", """▁and""", """▁this""", """▁is""", """▁fal""", """s""", """é""", """.""", ]
		__lowercase             =  ["""▁""", """<unk>""", """▁was""", """▁born""", """▁in""", """▁9""", """2000""", """,""", """▁and""", """▁this""", """▁is""", """▁fal""", """s""", """<unk>""", """.""", ]
		# fmt: on

		__lowercase             =  tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)
		__lowercase             =  tokenizer.tokenize(_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)
		__lowercase             =  tokenizer.convert_ids_to_tokens(_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)

		__lowercase             =  rust_tokenizer.encode(_lowerCAmelCase       ,				add_special_tokens=_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.tokenize(_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)
		__lowercase             =  rust_tokenizer.convert_ids_to_tokens(_lowerCAmelCase			)
		self.assertListEqual(_lowerCAmelCase       ,				_lowerCAmelCase			)







	def  _a   (  self      :							Union[str, Any]			)		-> List[Any]:
		"""simple docstring"""







		__lowercase             =  DebertaVaTokenizer(_lowerCAmelCase			)

		__lowercase             =  tokenizer.encode("""sequence builders"""			)
		__lowercase             =  tokenizer.encode("""multi-sequence build"""			)

		__lowercase             =  tokenizer.build_inputs_with_special_tokens(_lowerCAmelCase			)
		__lowercase             =  tokenizer.build_inputs_with_special_tokens(_lowerCAmelCase       ,				_lowerCAmelCase			)

		self.assertEqual([tokenizer.cls_token_id] + text + [tokenizer.sep_token_id]       ,				_lowerCAmelCase			)
		self.assertEqual(
		    [tokenizer.cls_token_id] + text + [tokenizer.sep_token_id] + text_a + [tokenizer.sep_token_id]       ,				_lowerCAmelCase       ,				)







	@slow
	def  _a   (  self      :							Optional[Any]			)		-> Tuple:
		"""simple docstring"""







		__lowercase             =  {"""input_ids""": [[1, 3_9867, 36, 1_9390, 486, 27, 3_5052, 8_1436, 18, 6_0685, 1225, 7, 3_5052, 8_1436, 18, 9367, 1_6899, 18, 1_5937, 53, 594, 773, 18, 1_6287, 3_0465, 36, 1_5937, 6, 4_1139, 38, 3_6979, 6_0763, 191, 6, 3_4132, 99, 6, 5_0538, 390, 4_3230, 6, 3_4132, 2779, 2_0850, 14, 699, 1072, 1194, 36, 382, 1_0901, 53, 7, 699, 1072, 2084, 36, 2_0422, 630, 53, 19, 105, 3049, 1896, 1053, 1_6899, 1506, 11, 3_7978, 4243, 7, 1237, 3_1869, 200, 1_6566, 654, 6, 3_5052, 8_1436, 7, 5_5630, 1_3593, 4, 2], [1, 26, 1_5011, 13, 667, 8, 1053, 18, 2_3611, 1237, 7_2356, 1_2820, 34, 10_4134, 1209, 35, 1_3313, 6627, 21, 202, 347, 7, 164, 2399, 11, 46, 4485, 4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 5, 1232, 2864, 1_5785, 1_4951, 105, 5, 8581, 1250, 4, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], """token_type_ids""": [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], """attention_mask""": [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]}  # noqa: E501
		# fmt: on

		self.tokenizer_integration_test_util(
		    expected_encoding=_lowerCAmelCase       ,				model_name="""microsoft/deberta-v2-xlarge"""       ,				revision="""ad6e42c1532ddf3a15c39246b63f5559d558b670"""       ,				)









import heapq
import sys

import numpy as np

__UpperCamelCase      :      List[str]     						=						tuple[int, int]


class        __UpperCamelCase    :







	def __init__(  self      :							Optional[int]			)		-> Dict:
		"""simple docstring"""







		__lowercase             =  []
		__lowercase             =  set()







	def  _a   (  self      :							int			)		-> List[Any]:
		"""simple docstring"""







		if not self.empty():
			return self.elements[0][0]
		else:
			return float("""inf"""			)







	def  _a   (  self      :							Dict			)		-> Optional[Any]:
		"""simple docstring"""







		return len(self.elements			) == 0







	def  _a   (  self      :							str       ,				_lowerCAmelCase      :							Union[str, Any]       ,				_lowerCAmelCase      :							Optional[Any]			)		-> Dict:
		"""simple docstring"""







		if item not in self.set:
			heapq.heappush(self.elements       ,				(priority, item)			)
			self.set.add(_lowerCAmelCase			)
		else:
			# update
			# print("update", item)
			__lowercase             =  []
			((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			while x != item:
				temp.append((pri, x)			)
				((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			temp.append((priority, item)			)
			for pro, xxx in temp:
				heapq.heappush(self.elements       ,				(pro, xxx)			)







	def  _a   (  self      :							List[str]       ,				_lowerCAmelCase      :							Optional[Any]			)		-> Dict:
		"""simple docstring"""







		if item in self.set:
			self.set.remove(_lowerCAmelCase			)
			__lowercase             =  []
			((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			while x != item:
				temp.append((pro, x)			)
				((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
			for prito, yyy in temp:
				heapq.heappush(self.elements       ,				(prito, yyy)			)







	def  _a   (  self      :							Any			)		-> List[Any]:
		"""simple docstring"""







		return self.elements[0][1]







	def  _a   (  self      :							Optional[int]			)		-> List[Any]:
		"""simple docstring"""







		((__lowercase)       ,						(__lowercase))             =  heapq.heappop(self.elements			)
		self.set.remove(_lowerCAmelCase			)
		return (priority, item)





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  np.array(lowerCamelCase					)
	__lowercase             =  np.array(lowerCamelCase					)
	return np.linalg.norm(a - b					)





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	return consistent_heuristic(lowerCamelCase				,  lowerCamelCase					) // t





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	return abs(p[0] - goal[0]					) + abs(p[1] - goal[1]					)





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  g_function[start] + Wa * heuristics[i](lowerCamelCase				,  lowerCamelCase					)
	return ans





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  np.chararray((n, n)					)
	for i in range(lowerCamelCase					):
		for j in range(lowerCamelCase					):
			__lowercase             =  """*"""

	for i in range(lowerCamelCase					):
		for j in range(lowerCamelCase					):
			if (j, (n - 1) - i) in blocks:
				__lowercase             =  """#"""

	__lowercase             =  """-"""
	__lowercase             =  back_pointer[goal]
	while x != start:
		((__lowercase)       ,						(__lowercase))             =  x
		# print(x)
		__lowercase             =  """-"""
		__lowercase             =  back_pointer[x]
	__lowercase             =  """-"""

	for i in range(lowerCamelCase					):
		for j in range(lowerCamelCase					):
			if (i, j) == (0, n - 1):
				print(grid[i][j]				,  end=""" """					)
				print("""<-- End position"""				,  end=""" """					)
			else:
				print(grid[i][j]				,  end=""" """					)
		print()
	print("""^"""					)
	print("""Start position"""					)
	print()
	print("""# is an obstacle"""					)
	print("""- is the path taken by algorithm"""					)
	print("""PATH TAKEN BY THE ALGORITHM IS:-"""					)
	__lowercase             =  back_pointer[goal]
	while x != start:
		print(lowerCamelCase				,  end=""" """					)
		__lowercase             =  back_pointer[x]
	print(lowerCamelCase					)
	sys.exit()





def 				snake_case  (     lowerCamelCase					):




	'''simple docstring'''







	if p[0] < 0 or p[0] > n - 1:
		return False
	if p[1] < 0 or p[1] > n - 1:
		return False
	return True





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  ):




	'''simple docstring'''







	for itera in range(lowerCamelCase					):
		open_list[itera].remove_element(lowerCamelCase					)
	# print("s", s)
	# print("j", j)
	((__lowercase)       ,						(__lowercase))             =  s
	__lowercase             =  (x - 1, y)
	__lowercase             =  (x + 1, y)
	__lowercase             =  (x, y + 1)
	__lowercase             =  (x, y - 1)

	for neighbours in [left, right, up, down]:
		if neighbours not in blocks:
			if valid(lowerCamelCase					) and neighbours not in visited:
				# print("neighbour", neighbours)
				visited.add(lowerCamelCase					)
				__lowercase             =  -1
				__lowercase             =  float("""inf"""					)

			if valid(lowerCamelCase					) and g_function[neighbours] > g_function[s] + 1:
				__lowercase             =  g_function[s] + 1
				__lowercase             =  s
				if neighbours not in close_list_anchor:
					open_list[0].put(lowerCamelCase				,  key(lowerCamelCase				,  0				,  lowerCamelCase				,  lowerCamelCase					)					)
					if neighbours not in close_list_inad:
						for var in range(1				,  lowerCamelCase					):
							if key(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					) <= Wa * key(
							    lowerCamelCase				,  0				,  lowerCamelCase				,  lowerCamelCase					):
								open_list[j].put(
								    lowerCamelCase				,  key(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					)					)





def 				snake_case  (     ):




	'''simple docstring'''







	__lowercase             =  []
	for x in range(1				,  5					):
		for y in range(1				,  6					):
			some_list.append((x, y)					)

	for x in range(15				,  20					):
		some_list.append((x, 17)					)

	for x in range(10				,  19					):
		for y in range(1				,  15					):
			some_list.append((x, y)					)

    # L block
	for x in range(1				,  4					):
		for y in range(12				,  19					):
			some_list.append((x, y)					)
	for x in range(3				,  13					):
		for y in range(16				,  19					):
			some_list.append((x, y)					)
	return some_list


__UpperCamelCase      :      Optional[int]     						=						{0: consistent_heuristic, 1: heuristic_a, 2: heuristic_a}

__UpperCamelCase      :      Optional[Any]     						=						[
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (4, 1),
    (5, 1),
    (6, 1),
    (7, 1),
    (8, 1),
    (9, 1),
    (10, 1),
    (11, 1),
    (12, 1),
    (13, 1),
    (14, 1),
    (15, 1),
    (16, 1),
    (17, 1),
    (18, 1),
    (19, 1),
]
__UpperCamelCase      :      Optional[Any]     						=						make_common_ground()


__UpperCamelCase      :      Dict     						=						blocks_blk
# hyper parameters
__UpperCamelCase      :      Union[str, Any]     						=						1
__UpperCamelCase      :      Union[str, Any]     						=						1
__UpperCamelCase      :      Optional[int]     						=						20
__UpperCamelCase      :      List[str]     						=						3  # one consistent and two other inconsistent

# start and end destination
__UpperCamelCase      :      str     						=						(0, 0)
__UpperCamelCase      :      str     						=						(n - 1, n - 1)

__UpperCamelCase      :      Optional[Any]     						=						1





def 				snake_case  (     lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					):




	'''simple docstring'''







	__lowercase             =  {start: 0, goal: float("""inf"""					)}
	__lowercase             =  {start: -1, goal: -1}
	__lowercase             =  []
	__lowercase             =  set()

	for i in range(lowerCamelCase					):
		open_list.append(PriorityQueue()					)
		open_list[i].put(lowerCamelCase				,  key(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					)					)

	__lowercase             =  []
	__lowercase             =  []
	while open_list[0].minkey() < float("""inf"""					):
		for i in range(1				,  lowerCamelCase					):
			# print(open_list[0].minkey(), open_list[i].minkey())
			if open_list[i].minkey() <= Wa * open_list[0].minkey():
				global t
				t += 1
				if g_function[goal] <= open_list[i].minkey():
					if g_function[goal] < float("""inf"""					):
						do_something(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					)
				else:
					__lowercase       ,						__lowercase             =  open_list[i].top_show()
					visited.add(lowerCamelCase					)
					expand_state(
					    lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  )
					close_list_inad.append(lowerCamelCase					)
			else:
				if g_function[goal] <= open_list[0].minkey():
					if g_function[goal] < float("""inf"""					):
						do_something(lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase					)
				else:
					__lowercase             =  open_list[0].top_show()
					visited.add(lowerCamelCase					)
					expand_state(
					    lowerCamelCase				,  0				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  lowerCamelCase				,  )
					close_list_anchor.append(lowerCamelCase					)
	print("""No path found to goal"""					)
	print()
	for i in range(n - 1				,  -1				,  -1					):
		for j in range(lowerCamelCase					):
			if (j, i) in blocks:
				print("""#"""				,  end=""" """					)
			elif (j, i) in back_pointer:
				if (j, i) == (n - 1, n - 1):
					print("""*"""				,  end=""" """					)
				else:
					print("""-"""				,  end=""" """					)
			else:
				print("""*"""				,  end=""" """					)
			if (j, i) == (n - 1, n - 1):
				print("""<-- End position"""				,  end=""" """					)
		print()
	print("""^"""					)
	print("""Start position"""					)
	print()
	print("""# is an obstacle"""					)
	print("""- is the path taken by algorithm"""					)


if __name__ == "__main__":
						multi_a_star(start, goal, n_heuristic)

