






import unittest

from transformers import is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
		import torch

		from transformers import (
		    RemBertConfig,
		    RemBertForCausalLM,
		    RemBertForMaskedLM,
		    RemBertForMultipleChoice,
		    RemBertForQuestionAnswering,
		    RemBertForSequenceClassification,
		    RemBertForTokenClassification,
		    RemBertModel,
		)
		from transformers.models.rembert.modeling_rembert import REMBERT_PRETRAINED_MODEL_ARCHIVE_LIST





class  snake_case__      :
	def __init__(       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__=13    ,     lowerCAmelCase__=7    ,     lowerCAmelCase__=True    ,     lowerCAmelCase__=True    ,     lowerCAmelCase__=True    ,     lowerCAmelCase__=True    ,     lowerCAmelCase__=99    ,     lowerCAmelCase__=32    ,     lowerCAmelCase__=18    ,     lowerCAmelCase__=43    ,     lowerCAmelCase__=5    ,     lowerCAmelCase__=4    ,     lowerCAmelCase__=37    ,     lowerCAmelCase__="gelu"    ,     lowerCAmelCase__=0.1    ,     lowerCAmelCase__=0.1    ,     lowerCAmelCase__=5_12    ,     lowerCAmelCase__=16    ,     lowerCAmelCase__=2    ,     lowerCAmelCase__=0.0_2    ,     lowerCAmelCase__=3    ,     lowerCAmelCase__=4    ,     lowerCAmelCase__=None    ,     )							->   Union[str, Any]:
							__magic_name__    :     str     		=      parent
							__magic_name__    :     Any     		=      batch_size
							__magic_name__    :     str     		=      seq_length
							__magic_name__    :     Union[str, Any]     		=      is_training
							__magic_name__    :     Any     		=      use_input_mask
							__magic_name__    :     Tuple     		=      use_token_type_ids
							__magic_name__    :     List[Any]     		=      use_labels
							__magic_name__    :     Dict     		=      vocab_size
							__magic_name__    :     Tuple     		=      hidden_size
							__magic_name__    :     Dict     		=      input_embedding_size
							__magic_name__    :     Tuple     		=      output_embedding_size
							__magic_name__    :     List[str]     		=      num_hidden_layers
							__magic_name__    :     Union[str, Any]     		=      num_attention_heads
							__magic_name__    :     Optional[int]     		=      intermediate_size
							__magic_name__    :     Any     		=      hidden_act
							__magic_name__    :     List[Any]     		=      hidden_dropout_prob
							__magic_name__    :     Dict     		=      attention_probs_dropout_prob
							__magic_name__    :     Optional[int]     		=      max_position_embeddings
							__magic_name__    :     Optional[int]     		=      type_vocab_size
							__magic_name__    :     Union[str, Any]     		=      type_sequence_label_size
							__magic_name__    :     str     		=      initializer_range
							__magic_name__    :     Any     		=      num_labels
							__magic_name__    :     Dict     		=      num_choices
							__magic_name__    :     Dict     		=      scope
	def     __magic_name__       (       self				)							->   List[Any]:
							__magic_name__    :     Dict     		=      ids_tensor([self.batch_size, self.seq_length]    ,     self.vocab_size				)

							__magic_name__    :     List[Any]     		=      None
							if self.use_input_mask:
													__magic_name__    :     List[str]     		=      random_attention_mask([self.batch_size, self.seq_length]				)

							__magic_name__    :     List[str]     		=      None
							if self.use_token_type_ids:
													__magic_name__    :     Dict     		=      ids_tensor([self.batch_size, self.seq_length]    ,     self.type_vocab_size				)

							__magic_name__    :     List[Any]     		=      None
							__magic_name__    :     Tuple     		=      None
							__magic_name__    :     List[Any]     		=      None
							if self.use_labels:
													__magic_name__    :     int     		=      ids_tensor([self.batch_size]    ,     self.type_sequence_label_size				)
													__magic_name__    :     Optional[Any]     		=      ids_tensor([self.batch_size, self.seq_length]    ,     self.num_labels				)
													__magic_name__    :     List[str]     		=      ids_tensor([self.batch_size]    ,     self.num_choices				)

							__magic_name__    :     List[str]     		=      RemBertConfig(
							    vocab_size=self.vocab_size    ,     hidden_size=self.hidden_size    ,     input_embedding_size=self.input_embedding_size    ,     output_embedding_size=self.output_embedding_size    ,     num_hidden_layers=self.num_hidden_layers    ,     num_attention_heads=self.num_attention_heads    ,     intermediate_size=self.intermediate_size    ,     hidden_act=self.hidden_act    ,     hidden_dropout_prob=self.hidden_dropout_prob    ,     attention_probs_dropout_prob=self.attention_probs_dropout_prob    ,     max_position_embeddings=self.max_position_embeddings    ,     type_vocab_size=self.type_vocab_size    ,     is_decoder=lowerCAmelCase__    ,     initializer_range=self.initializer_range    ,     )

							return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels
	def     __magic_name__       (       self				)							->   List[Any]:
							(
							    __magic_name__
							)    :     Dict     		=      self.prepare_config_and_inputs()

							__magic_name__    :     List[Any]     		=      True
							__magic_name__    :     Union[str, Any]     		=      floats_tensor([self.batch_size, self.seq_length, self.hidden_size]				)
							__magic_name__    :     int     		=      ids_tensor([self.batch_size, self.seq_length]    ,     vocab_size=2				)

							return (
							    config,
							    input_ids,
							    token_type_ids,
							    input_mask,
							    sequence_labels,
							    token_labels,
							    choice_labels,
							    encoder_hidden_states,
							    encoder_attention_mask,
							)
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__				)							->   List[Any]:
							__magic_name__    :     Optional[Any]     		=      RemBertModel(config=lowerCAmelCase__				)
							model.to(lowerCAmelCase__				)
							model.eval()
							__magic_name__    :     Optional[Any]     		=      model(lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__				)
							__magic_name__    :     Optional[Any]     		=      model(lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__				)
							__magic_name__    :     List[str]     		=      model(lowerCAmelCase__				)
							self.parent.assertEqual(result.last_hidden_state.shape    ,     (self.batch_size, self.seq_length, self.hidden_size)				)
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     )							->   Any:
							__magic_name__    :     Optional[int]     		=      True
							__magic_name__    :     Dict     		=      RemBertModel(lowerCAmelCase__				)
							model.to(lowerCAmelCase__				)
							model.eval()
							__magic_name__    :     Tuple     		=      model(
							    lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__    ,     encoder_hidden_states=lowerCAmelCase__    ,     encoder_attention_mask=lowerCAmelCase__    ,     )
							__magic_name__    :     int     		=      model(
							    lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__    ,     encoder_hidden_states=lowerCAmelCase__    ,     )
							__magic_name__    :     str     		=      model(lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__				)
							self.parent.assertEqual(result.last_hidden_state.shape    ,     (self.batch_size, self.seq_length, self.hidden_size)				)
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     )							->   Any:
							__magic_name__    :     List[Any]     		=      RemBertForCausalLM(config=lowerCAmelCase__				)
							model.to(lowerCAmelCase__				)
							model.eval()
							__magic_name__    :     List[str]     		=      model(lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__    ,     labels=lowerCAmelCase__				)
							self.parent.assertEqual(result.logits.shape    ,     (self.batch_size, self.seq_length, self.vocab_size)				)
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__				)							->   Optional[int]:
							__magic_name__    :     Optional[Any]     		=      RemBertForMaskedLM(config=lowerCAmelCase__				)
							model.to(lowerCAmelCase__				)
							model.eval()
							__magic_name__    :     Tuple     		=      model(lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__    ,     labels=lowerCAmelCase__				)
							self.parent.assertEqual(result.logits.shape    ,     (self.batch_size, self.seq_length, self.vocab_size)				)
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     )							->   Tuple:
							__magic_name__    :     Dict     		=      True
							__magic_name__    :     Optional[Any]     		=      True
							__magic_name__    :     List[Any]     		=      RemBertForCausalLM(config=lowerCAmelCase__				)
							model.to(lowerCAmelCase__				)
							model.eval()

							# first forward pass
							__magic_name__    :     Any     		=      model(
							    lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     encoder_hidden_states=lowerCAmelCase__    ,     encoder_attention_mask=lowerCAmelCase__    ,     use_cache=lowerCAmelCase__    ,     )
							__magic_name__    :     Optional[int]     		=      outputs.past_key_values

							# create hypothetical multiple next token and extent to next_input_ids
							__magic_name__    :     Union[str, Any]     		=      ids_tensor((self.batch_size, 3)    ,     config.vocab_size				)
							__magic_name__    :     Optional[Any]     		=      ids_tensor((self.batch_size, 3)    ,     vocab_size=2				)

							# append to next input_ids and
							__magic_name__    :     str     		=      torch.cat([input_ids, next_tokens]    ,     dim=-1				)
							__magic_name__    :     Dict     		=      torch.cat([input_mask, next_mask]    ,     dim=-1				)

							__magic_name__    :     str     		=      model(
							    lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     encoder_hidden_states=lowerCAmelCase__    ,     encoder_attention_mask=lowerCAmelCase__    ,     output_hidden_states=lowerCAmelCase__    ,     )["""hidden_states"""][0]
							__magic_name__    :     Dict     		=      model(
							    lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     encoder_hidden_states=lowerCAmelCase__    ,     encoder_attention_mask=lowerCAmelCase__    ,     past_key_values=lowerCAmelCase__    ,     output_hidden_states=lowerCAmelCase__    ,     )["""hidden_states"""][0]

							# select random slice
							__magic_name__    :     List[Any]     		=      ids_tensor((1,)    ,     output_from_past.shape[-1]				).item()
							__magic_name__    :     str     		=      output_from_no_past[:, -3:, random_slice_idx].detach()
							__magic_name__    :     Dict     		=      output_from_past[:, :, random_slice_idx].detach()

							self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]				)

							# test that outputs are equal for slice
							self.parent.assertTrue(torch.allclose(lowerCAmelCase__    ,     lowerCAmelCase__    ,     atol=1e-3				)				)
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__				)							->   List[Any]:
							__magic_name__    :     Tuple     		=      RemBertForQuestionAnswering(config=lowerCAmelCase__				)
							model.to(lowerCAmelCase__				)
							model.eval()
							__magic_name__    :     str     		=      model(
							    lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__    ,     start_positions=lowerCAmelCase__    ,     end_positions=lowerCAmelCase__    ,     )
							self.parent.assertEqual(result.start_logits.shape    ,     (self.batch_size, self.seq_length)				)
							self.parent.assertEqual(result.end_logits.shape    ,     (self.batch_size, self.seq_length)				)
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__				)							->   List[Any]:
							__magic_name__    :     Optional[Any]     		=      self.num_labels
							__magic_name__    :     Any     		=      RemBertForSequenceClassification(lowerCAmelCase__				)
							model.to(lowerCAmelCase__				)
							model.eval()
							__magic_name__    :     List[str]     		=      model(lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__    ,     labels=lowerCAmelCase__				)
							self.parent.assertEqual(result.logits.shape    ,     (self.batch_size, self.num_labels)				)
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__				)							->   int:
							__magic_name__    :     int     		=      self.num_labels
							__magic_name__    :     List[str]     		=      RemBertForTokenClassification(config=lowerCAmelCase__				)
							model.to(lowerCAmelCase__				)
							model.eval()
							__magic_name__    :     Tuple     		=      model(lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__    ,     labels=lowerCAmelCase__				)
							self.parent.assertEqual(result.logits.shape    ,     (self.batch_size, self.seq_length, self.num_labels)				)
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__				)							->   Dict:
							__magic_name__    :     List[str]     		=      self.num_choices
							__magic_name__    :     int     		=      RemBertForMultipleChoice(config=lowerCAmelCase__				)
							model.to(lowerCAmelCase__				)
							model.eval()
							__magic_name__    :     Optional[int]     		=      input_ids.unsqueeze(1				).expand(-1    ,     self.num_choices    ,     -1				).contiguous()
							__magic_name__    :     int     		=      token_type_ids.unsqueeze(1				).expand(-1    ,     self.num_choices    ,     -1				).contiguous()
							__magic_name__    :     Optional[int]     		=      input_mask.unsqueeze(1				).expand(-1    ,     self.num_choices    ,     -1				).contiguous()
							__magic_name__    :     List[Any]     		=      model(
							    lowerCAmelCase__    ,     attention_mask=lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__    ,     labels=lowerCAmelCase__    ,     )
							self.parent.assertEqual(result.logits.shape    ,     (self.batch_size, self.num_choices)				)







	def     __magic_name__       (       self				)							->   List[str]:
							__magic_name__    :     Optional[int]     		=      self.prepare_config_and_inputs()
							(
							    __magic_name__
							)    :     Optional[Any]     		=      config_and_inputs
							__magic_name__    :     Union[str, Any]     		=      {"""input_ids""": input_ids, """token_type_ids""": token_type_ids, """attention_mask""": input_mask}
							return config, inputs_dict





@require_torch
class  snake_case__      (       _lowerCAmelCase		,						_lowerCAmelCase		,						unittest.TestCase   ):
	lowercase__		:  Optional[Any]							   =					(
	    (
	        RemBertModel,
	        RemBertForMaskedLM,
	        RemBertForCausalLM,
	        RemBertForMultipleChoice,
	        RemBertForQuestionAnswering,
	        RemBertForSequenceClassification,
	        RemBertForTokenClassification,
	    )
	    if is_torch_available()
	    else ()
	)
	lowercase__		:  Optional[int]							   =					(RemBertForCausalLM,) if is_torch_available() else ()
	lowercase__		:  Tuple							   =					(
	    {
	        '''feature-extraction''': RemBertModel,
	        '''fill-mask''': RemBertForMaskedLM,
	        '''question-answering''': RemBertForQuestionAnswering,
	        '''text-classification''': RemBertForSequenceClassification,
	        '''text-generation''': RemBertForCausalLM,
	        '''token-classification''': RemBertForTokenClassification,
	        '''zero-shot''': RemBertForSequenceClassification,
	    }
	    if is_torch_available()
	    else {}
	)
	def     __magic_name__       (       self				)							->   Optional[Any]:
							__magic_name__    :     Union[str, Any]     		=      RemBertModelTester(self				)
							__magic_name__    :     str     		=      ConfigTester(self    ,     config_class=lowerCAmelCase__    ,     hidden_size=37				)
	def     __magic_name__       (       self				)							->   Dict:
							self.config_tester.run_common_tests()
	def     __magic_name__       (       self				)							->   List[Any]:
							__magic_name__    :     Optional[Any]     		=      self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_model(*lowerCAmelCase__				)
	def     __magic_name__       (       self				)							->   Union[str, Any]:
							__magic_name__    :     Any     		=      self.model_tester.prepare_config_and_inputs()
							for type in ["absolute", "relative_key", "relative_key_query"]:
													__magic_name__    :     Union[str, Any]     		=      type
													self.model_tester.create_and_check_model(*lowerCAmelCase__				)
	def     __magic_name__       (       self				)							->   List[Any]:
							__magic_name__    :     int     		=      self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_masked_lm(*lowerCAmelCase__				)
	def     __magic_name__       (       self				)							->   List[str]:
							__magic_name__    :     str     		=      self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_multiple_choice(*lowerCAmelCase__				)
	def     __magic_name__       (       self				)							->   Dict:
							__magic_name__    :     str     		=      self.model_tester.prepare_config_and_inputs_for_decoder()
							self.model_tester.create_and_check_decoder_model_past_large_inputs(*lowerCAmelCase__				)
	def     __magic_name__       (       self				)							->   int:
							__magic_name__    :     int     		=      self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_question_answering(*lowerCAmelCase__				)
	def     __magic_name__       (       self				)							->   Tuple:
							__magic_name__    :     int     		=      self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_sequence_classification(*lowerCAmelCase__				)
	def     __magic_name__       (       self				)							->   Optional[Any]:
							__magic_name__    :     Tuple     		=      self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_for_token_classification(*lowerCAmelCase__				)
	def     __magic_name__       (       self				)							->   Any:
							__magic_name__    :     List[str]     		=      self.model_tester.prepare_config_and_inputs_for_decoder()
							self.model_tester.create_and_check_model_as_decoder(*lowerCAmelCase__				)
	def     __magic_name__       (       self				)							->   List[str]:
							# This regression test was failing with PyTorch < 1.3
							(
							    __magic_name__
							)    :     Dict     		=      self.model_tester.prepare_config_and_inputs_for_decoder()

							__magic_name__    :     Union[str, Any]     		=      None

							self.model_tester.create_and_check_model_as_decoder(
							    lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     lowerCAmelCase__    ,     )







	@slow
	def     __magic_name__       (       self				)							->   Union[str, Any]:
							for model_name in REMBERT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
													__magic_name__    :     int     		=      RemBertModel.from_pretrained(lowerCAmelCase__				)
													self.assertIsNotNone(lowerCAmelCase__				)





@require_torch
class  snake_case__      (       unittest.TestCase   ):
	@slow
	def     __magic_name__       (       self				)							->   Tuple:
							# Test exact values at the last hidden layer
							__magic_name__    :     Optional[int]     		=      RemBertModel.from_pretrained("""google/rembert"""				)
							__magic_name__    :     Dict     		=      torch.tensor([[3_12, 5_64_98, 3_13, 21_25, 3_13]]				)
							__magic_name__    :     List[Any]     		=      torch.tensor([[0, 0, 0, 1, 1]]				)
							with torch.no_grad():
													__magic_name__    :     int     		=      model(lowerCAmelCase__    ,     token_type_ids=lowerCAmelCase__    ,     output_hidden_states=lowerCAmelCase__				)

							__magic_name__    :     List[Any]     		=      11_52

							__magic_name__    :     List[Any]     		=      torch.Size((1, 5, hidden_size)				)
							self.assertEqual(output["""last_hidden_state"""].shape    ,     lowerCAmelCase__				)

							__magic_name__    :     List[Any]     		=      torch.tensor(
							    [
							        [
							            [0.0_7_5_4, -0.2_0_2_2, 0.1_9_0_4],
							            [-0.3_3_5_4, -0.3_6_9_2, -0.4_7_9_1],
							            [-0.2_3_1_4, -0.6_7_2_9, -0.0_7_4_9],
							            [-0.0_3_9_6, -0.3_1_0_5, -0.4_2_3_4],
							            [-0.1_5_7_1, -0.0_5_2_5, 0.5_3_5_3],
							        ]
							    ]				)

							# Running on the original tf implementation gives slightly different results here.
							# Not clear why this variations is present
							# TODO: Find reason for discrepancy
							# expected_original_implementation = [[
							#     [0.07630594074726105, -0.20146065950393677, 0.19107051193714142],
							#     [-0.3405614495277405, -0.36971670389175415, -0.4808273911476135],
							#     [-0.22587086260318756, -0.6656315922737122, -0.07844287157058716],
							#     [-0.04145475849509239, -0.3077218234539032, -0.42316967248916626],
							#     [-0.15887849032878876, -0.054529931396245956, 0.5356100797653198]
							# ]]

							self.assertTrue(torch.allclose(output["""last_hidden_state"""][:, :, :3]    ,     lowerCAmelCase__    ,     atol=1e-4				)				)








class  snake_case__      :
	def __init__(       self				)							->   None:
							# numbermap keys are the number and its values are lists of indexes sorted
							# in ascending order
							__magic_name__    :     dict[int, list[int]]     		=      {}
							# indexmap keys are an index and it's values are the number at that index
							__magic_name__    :     dict[int, int]     		=      {}
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__				)							->   list[int]:
							if isinstance(lowerCAmelCase__    ,     (range, str)				):
													__magic_name__    :     int     		=      list(lowerCAmelCase__				)
							elif not isinstance(lowerCAmelCase__    ,     lowerCAmelCase__				):
													raise TypeError(
													    """binary_search_delete() only accepts either a list, range or str"""				)

							__magic_name__    :     str     		=      0
							__magic_name__    :     int     		=      len(lowerCAmelCase__				) - 1

							while low <= high:
													__magic_name__    :     List[str]     		=      (low + high) // 2
													if array[mid] == item:
																			array.pop(lowerCAmelCase__				)
																			return array
													elif array[mid] < item:
																			__magic_name__    :     Tuple     		=      mid + 1
													else:
																			__magic_name__    :     Dict     		=      mid - 1
							raise ValueError(
							    """Either the item is not in the array or the array was unsorted"""				)
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__				)							->   list[int]:
							if isinstance(lowerCAmelCase__    ,     (range, str)				):
													__magic_name__    :     Tuple     		=      list(lowerCAmelCase__				)
							elif not isinstance(lowerCAmelCase__    ,     lowerCAmelCase__				):
													raise TypeError(
													    """binary_search_insert() only accepts either a list, range or str"""				)

							__magic_name__    :     List[str]     		=      0
							__magic_name__    :     Tuple     		=      len(lowerCAmelCase__				) - 1

							while low <= high:
													__magic_name__    :     Dict     		=      (low + high) // 2
													if array[mid] == index:
																			# If the item already exists in the array,
																			# insert it after the existing item
																			array.insert(mid + 1    ,     lowerCAmelCase__				)
																			return array
													elif array[mid] < index:
																			__magic_name__    :     int     		=      mid + 1
													else:
																			__magic_name__    :     Tuple     		=      mid - 1

        # If the item doesn't exist in the array, insert it at the appropriate position
							array.insert(lowerCAmelCase__    ,     lowerCAmelCase__				)
							return array
	def     __magic_name__       (       self    ,     lowerCAmelCase__    ,     lowerCAmelCase__				)							->   None:
							# Remove previous index
							if index in self.indexmap:
													__magic_name__    :     int     		=      self.indexmap[index]
													if len(self.numbermap[n]				) == 1:
																			del self.numbermap[n]
													else:
																			__magic_name__    :     Union[str, Any]     		=      self.binary_search_delete(self.numbermap[n]    ,     lowerCAmelCase__				)

        # Set new index
							__magic_name__    :     List[Any]     		=      number

							# Number not seen before or empty so insert number value
							if number not in self.numbermap:
													__magic_name__    :     Any     		=      [index]

							# Here we need to perform a binary search insertion in order to insert
							# The item in the correct place
							else:
													__magic_name__    :     Optional[Any]     		=      self.binary_search_insert(
													    self.numbermap[number]    ,     lowerCAmelCase__				)







	def     __magic_name__       (       self    ,     lowerCAmelCase__				)							->   int:
							return self.numbermap.get(lowerCAmelCase__    ,     [-1]				)[0]


if __name__ == "__main__":
		import doctest

		doctest.testmod()
