



'''simple docstring'''



from __future__ import annotations

import collections
import tempfile
import unittest

import numpy as np

from transformers.testing_utils import require_tf, require_vision, slow
from transformers.utils import is_tf_available, is_vision_available

from ...test_modeling_tf_common import floats_tensor, ids_tensor, random_attention_mask
from ..bert.test_modeling_tf_bert import TFBertModelTester
from ..clip.test_modeling_tf_clip import TFCLIPVisionModelTester
from ..deit.test_modeling_tf_deit import TFDeiTModelTester
from ..roberta.test_modeling_tf_roberta import TFRobertaModelTester
from ..vit.test_modeling_tf_vit import TFViTModelTester


if is_tf_available():
		from transformers import (
		    TFBertModel,
		    TFCLIPVisionModel,
		    TFDeiTModel,
		    TFRobertaModel,
		    TFVisionTextDualEncoderModel,
		    TFViTModel,
		    VisionTextDualEncoderConfig,
		)

if is_vision_available():
		from PIL import Image

		from transformers import VisionTextDualEncoderProcessor



def      _A				(      _lowerCAmelCase    ):



							"""simple docstring"""



							if isinstance(_UpperCAmelCase     ,      collections.abc.Iterable    ):
														return x
							return (x, x)





@require_tf
class _UpperCamelCase						:





				'''simple docstring'''





				def  __lowerCamelCase   (							self     :     Any     ,				_lowerCAmelCase     :     str     ,				_lowerCAmelCase     :     int):







											'''simple docstring'''

											pass

				def  __lowerCamelCase   (							self     :     str):







											'''simple docstring'''

											pass

				def  __lowerCamelCase   (							self     :     Dict):







											'''simple docstring'''

											pass

				def  __lowerCamelCase   (							self     :     int     ,				_lowerCAmelCase     :     List[Any]     ,				_lowerCAmelCase     :     List[str]     ,				_lowerCAmelCase     :     Dict     ,				_lowerCAmelCase     :     Union[str, Any]     ,				_lowerCAmelCase     :     Dict=None     ,				**_lowerCAmelCase     :     Tuple):







											'''simple docstring'''

											__lowercase						=VisionTextDualEncoderConfig.from_vision_text_configs(lowerCAmelCase__     ,				lowerCAmelCase__)

											__lowercase						=TFVisionTextDualEncoderModel(lowerCAmelCase__)

											__lowercase						=model(input_ids=lowerCAmelCase__     ,				pixel_values=lowerCAmelCase__     ,				attention_mask=lowerCAmelCase__)

											self.assertEqual(output['text_embeds'].shape     ,				(input_ids.shape[0], config.projection_dim))
											self.assertEqual(output['image_embeds'].shape     ,				(pixel_values.shape[0], config.projection_dim))

				def  __lowerCamelCase   (							self     :     Optional[Any]     ,				_lowerCAmelCase     :     Any     ,				_lowerCAmelCase     :     int     ,				_lowerCAmelCase     :     str     ,				_lowerCAmelCase     :     Dict     ,				_lowerCAmelCase     :     Any=None     ,				**_lowerCAmelCase     :     List[str]):







											'''simple docstring'''

											__lowercase						=self.get_vision_text_model(lowerCAmelCase__     ,				lowerCAmelCase__)
											__lowercase						=TFVisionTextDualEncoderModel(vision_model=lowerCAmelCase__     ,				text_model=lowerCAmelCase__)

											__lowercase						=model(input_ids=lowerCAmelCase__     ,				pixel_values=lowerCAmelCase__     ,				attention_mask=lowerCAmelCase__)

											self.assertEqual(output['text_embeds'].shape     ,				(input_ids.shape[0], model.config.projection_dim))
											self.assertEqual(output['image_embeds'].shape     ,				(pixel_values.shape[0], model.config.projection_dim))

				def  __lowerCamelCase   (							self     :     Dict     ,				_lowerCAmelCase     :     Dict     ,				_lowerCAmelCase     :     Union[str, Any]     ,				_lowerCAmelCase     :     Any     ,				_lowerCAmelCase     :     Any     ,				_lowerCAmelCase     :     Optional[int]=None     ,				**_lowerCAmelCase     :     str):







											'''simple docstring'''

											__lowercase						=self.get_vision_text_model(lowerCAmelCase__     ,				lowerCAmelCase__)
											__lowercase						={"vision_model": vision_model, "text_model": text_model}
											__lowercase						=TFVisionTextDualEncoderModel.from_vision_text_pretrained(**lowerCAmelCase__)

											__lowercase						=model(input_ids=lowerCAmelCase__     ,				pixel_values=lowerCAmelCase__     ,				attention_mask=lowerCAmelCase__)

											self.assertEqual(output['text_embeds'].shape     ,				(input_ids.shape[0], model.config.projection_dim))
											self.assertEqual(output['image_embeds'].shape     ,				(pixel_values.shape[0], model.config.projection_dim))

				def  __lowerCamelCase   (							self     :     Dict     ,				_lowerCAmelCase     :     Any     ,				_lowerCAmelCase     :     int     ,				_lowerCAmelCase     :     Any     ,				_lowerCAmelCase     :     Tuple     ,				_lowerCAmelCase     :     Union[str, Any]=None     ,				**_lowerCAmelCase     :     Dict):







											'''simple docstring'''

											__lowercase						=self.get_vision_text_model(lowerCAmelCase__     ,				lowerCAmelCase__)
											__lowercase						=TFVisionTextDualEncoderModel(vision_model=lowerCAmelCase__     ,				text_model=lowerCAmelCase__)

											__lowercase						=model(input_ids=lowerCAmelCase__     ,				pixel_values=lowerCAmelCase__     ,				attention_mask=lowerCAmelCase__)
											__lowercase						=output[0].numpy()

											with tempfile.TemporaryDirectory() as tmpdirname:
																		model.save_pretrained(lowerCAmelCase__)
																		__lowercase						=TFVisionTextDualEncoderModel.from_pretrained(lowerCAmelCase__)

																		__lowercase						=model(input_ids=lowerCAmelCase__     ,				pixel_values=lowerCAmelCase__     ,				attention_mask=lowerCAmelCase__)
																		__lowercase						=after_output[0].numpy()
																		__lowercase						=np.amax(np.abs(out_a - out_a))
																		self.assertLessEqual(lowerCAmelCase__     ,				1e-5)

				def  __lowerCamelCase   (							self     :     Union[str, Any]     ,				_lowerCAmelCase     :     List[str]     ,				_lowerCAmelCase     :     int     ,				_lowerCAmelCase     :     List[Any]     ,				_lowerCAmelCase     :     Tuple     ,				_lowerCAmelCase     :     List[Any]=None     ,				**_lowerCAmelCase     :     List[Any]):







											'''simple docstring'''

											__lowercase						=self.get_vision_text_model(lowerCAmelCase__     ,				lowerCAmelCase__)
											__lowercase						=TFVisionTextDualEncoderModel(vision_model=lowerCAmelCase__     ,				text_model=lowerCAmelCase__)

											__lowercase						=model(
											    input_ids=lowerCAmelCase__     ,				pixel_values=lowerCAmelCase__     ,				attention_mask=lowerCAmelCase__     ,				output_attentions=lowerCAmelCase__)

											__lowercase						=output.vision_model_output.attentions
											self.assertEqual(len(lowerCAmelCase__)     ,				vision_config.num_hidden_layers)

											# in ViT, the seq_len equals the number of patches + 1 (we add 1 for the [CLS] token)
											__lowercase						=to_atuple(vision_model.config.image_size)
											__lowercase						=to_atuple(vision_model.config.patch_size)
											__lowercase						=(image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])
											__lowercase						=num_patches + 1
											self.assertEqual(vision_attentions[0].shape[-3:]     ,				(vision_config.num_attention_heads, seq_len, seq_len))

											__lowercase						=output.text_model_output.attentions
											self.assertEqual(len(lowerCAmelCase__)     ,				text_config.num_hidden_layers)

											self.assertEqual(
											    text_attentions[0].shape[-3:]     ,				(text_config.num_attention_heads, input_ids.shape[-1], input_ids.shape[-1])     ,				)

				def  __lowerCamelCase   (							self     :     str     ,				_lowerCAmelCase     :     np.ndarray     ,				_lowerCAmelCase     :     np.ndarray     ,				_lowerCAmelCase     :     float):







											'''simple docstring'''

											__lowercase						=np.abs((a - b)).max()
											self.assertLessEqual(lowerCAmelCase__     ,				lowerCAmelCase__     ,				f"""Difference between torch and flax is {diff} (>= {tol}).""")

				def  __lowerCamelCase   (							self     :     Dict):







											'''simple docstring'''

											__lowercase						=self.prepare_config_and_inputs()
											self.check_vision_text_dual_encoder_model(**lowerCAmelCase__)

				def  __lowerCamelCase   (							self     :     str):







											'''simple docstring'''

											__lowercase						=self.prepare_config_and_inputs()
											self.check_model_from_pretrained_configs(**lowerCAmelCase__)

				def  __lowerCamelCase   (							self     :     Dict):







											'''simple docstring'''

											__lowercase						=self.prepare_config_and_inputs()
											self.check_vision_text_dual_encoder_from_pretrained(**lowerCAmelCase__)

				def  __lowerCamelCase   (							self     :     str):







											'''simple docstring'''

											__lowercase						=self.prepare_config_and_inputs()
											self.check_save_load(**lowerCAmelCase__)

				def  __lowerCamelCase   (							self     :     Optional[int]):







											'''simple docstring'''

											__lowercase						=self.prepare_config_and_inputs()
											self.check_vision_text_output_attention(**lowerCAmelCase__)

				@slow
				def  __lowerCamelCase   (							self     :     Optional[int]):







											'''simple docstring'''

											__lowercase						=self.get_pretrained_model_and_inputs()

											__lowercase						=model_a(**lowerCAmelCase__)
											__lowercase						=outputs[0].numpy()

											with tempfile.TemporaryDirectory() as tmp_dirname:
																		model_a.save_pretrained(lowerCAmelCase__)
																		__lowercase						=TFVisionTextDualEncoderModel.from_pretrained(lowerCAmelCase__)

																		__lowercase						=model_a(**lowerCAmelCase__)
																		__lowercase						=after_outputs[0].numpy()
																		__lowercase						=np.amax(np.abs(out_a - out_a))
																		self.assertLessEqual(lowerCAmelCase__     ,				1e-5)





@require_tf
class _UpperCamelCase						(   UpperCAmelCase_					,				unittest.TestCase						):





				'''simple docstring'''





				def  __lowerCamelCase   (							self     :     Dict):







											'''simple docstring'''

											__lowercase						=TFVisionTextDualEncoderModel.from_vision_text_pretrained(
											    'hf-internal-testing/tiny-random-vit'     ,				'hf-internal-testing/tiny-random-bert')
											__lowercase						=1_3
											__lowercase						=floats_tensor(
											    [
											        batch_size,
											        model.vision_model.config.num_channels,
											        model.vision_model.config.image_size,
											        model.vision_model.config.image_size,
											    ])
											__lowercase						=ids_tensor([batch_size, 4]     ,				model.text_model.config.vocab_size)
											__lowercase						=random_attention_mask([batch_size, 4])
											__lowercase						={"pixel_values": pixel_values, "input_ids": input_ids, "attention_mask": attention_mask}

											return model, inputs

				def  __lowerCamelCase   (							self     :     Optional[int]     ,				_lowerCAmelCase     :     Dict     ,				_lowerCAmelCase     :     Union[str, Any]):







											'''simple docstring'''

											__lowercase						=TFViTModel(lowerCAmelCase__     ,				name='vision_model')
											__lowercase						=TFBertModel(lowerCAmelCase__     ,				name='text_model')
											return vision_model, text_model

				def  __lowerCamelCase   (							self     :     Dict):







											'''simple docstring'''

											__lowercase						=TFViTModelTester(self)
											__lowercase						=TFBertModelTester(self)
											__lowercase						=vit_model_tester.prepare_config_and_inputs()
											__lowercase						=bert_model_tester.prepare_config_and_inputs()

											__lowercase						=vision_config_and_inputs

											(
											    __lowercase    
											)						=text_config_and_inputs

											return {
											    "text_config": text_config,
											    "vision_config": vision_config,
											    "pixel_values": pixel_values,
											    "attention_mask": input_mask,
											    "input_ids": input_ids,
											    "text_token_type_ids": token_type_ids,
											    "text_sequence_labels": sequence_labels,
											    "text_token_labels": token_labels,
											    "text_choice_labels": choice_labels,
											}





@require_tf
class _UpperCamelCase						(   UpperCAmelCase_					,				unittest.TestCase						):





				'''simple docstring'''





				def  __lowerCamelCase   (							self     :     Tuple):







											'''simple docstring'''

											__lowercase						=TFVisionTextDualEncoderModel.from_vision_text_pretrained(
											    'Rocketknight1/tiny-random-deit-tf'     ,				'hf-internal-testing/tiny-random-roberta')
											__lowercase						=1_3
											__lowercase						=floats_tensor(
											    [
											        batch_size,
											        model.vision_model.config.num_channels,
											        model.vision_model.config.image_size,
											        model.vision_model.config.image_size,
											    ])
											__lowercase						=ids_tensor([batch_size, 4]     ,				model.text_model.config.vocab_size)
											__lowercase						=random_attention_mask([batch_size, 4])
											__lowercase						={"pixel_values": pixel_values, "input_ids": input_ids, "attention_mask": attention_mask}

											return model, inputs

				def  __lowerCamelCase   (							self     :     Dict     ,				_lowerCAmelCase     :     Tuple     ,				_lowerCAmelCase     :     Dict     ,				_lowerCAmelCase     :     List[Any]     ,				_lowerCAmelCase     :     int     ,				_lowerCAmelCase     :     Optional[Any]=None     ,				**_lowerCAmelCase     :     str):







											'''simple docstring'''

											__lowercase						=self.get_vision_text_model(lowerCAmelCase__     ,				lowerCAmelCase__)
											__lowercase						=TFVisionTextDualEncoderModel(vision_model=lowerCAmelCase__     ,				text_model=lowerCAmelCase__)

											__lowercase						=model(
											    input_ids=lowerCAmelCase__     ,				pixel_values=lowerCAmelCase__     ,				attention_mask=lowerCAmelCase__     ,				output_attentions=lowerCAmelCase__)

											__lowercase						=output.vision_model_output.attentions
											self.assertEqual(len(lowerCAmelCase__)     ,				vision_config.num_hidden_layers)

											# in DEiT, the seq_len equals the number of patches + 2 (we add 2 for the [CLS] and distillation tokens)
											__lowercase						=to_atuple(vision_model.config.image_size)
											__lowercase						=to_atuple(vision_model.config.patch_size)
											__lowercase						=(image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])
											__lowercase						=num_patches + 2
											self.assertEqual(vision_attentions[0].shape[-3:]     ,				(vision_config.num_attention_heads, seq_len, seq_len))

											__lowercase						=output.text_model_output.attentions
											self.assertEqual(len(lowerCAmelCase__)     ,				text_config.num_hidden_layers)

											self.assertEqual(
											    text_attentions[0].shape[-3:]     ,				(text_config.num_attention_heads, input_ids.shape[-1], input_ids.shape[-1])     ,				)

				def  __lowerCamelCase   (							self     :     int     ,				_lowerCAmelCase     :     int     ,				_lowerCAmelCase     :     str):







											'''simple docstring'''

											__lowercase						=TFDeiTModel(lowerCAmelCase__     ,				name='vision_model')
											__lowercase						=TFRobertaModel(lowerCAmelCase__     ,				name='text_model')
											return vision_model, text_model

				def  __lowerCamelCase   (							self     :     Any):







											'''simple docstring'''

											__lowercase						=TFDeiTModelTester(self)
											__lowercase						=TFRobertaModelTester(self)
											__lowercase						=vit_model_tester.prepare_config_and_inputs()
											__lowercase						=bert_model_tester.prepare_config_and_inputs()

											__lowercase						=vision_config_and_inputs

											(
											    __lowercase    
											)						=text_config_and_inputs

											return {
											    "text_config": text_config,
											    "vision_config": vision_config,
											    "pixel_values": pixel_values,
											    "attention_mask": input_mask,
											    "input_ids": input_ids,
											    "text_token_type_ids": token_type_ids,
											    "text_sequence_labels": sequence_labels,
											    "text_token_labels": token_labels,
											    "text_choice_labels": choice_labels,
											}





@require_tf
class _UpperCamelCase						(   UpperCAmelCase_					,				unittest.TestCase						):





				'''simple docstring'''





				def  __lowerCamelCase   (							self     :     Tuple):







											'''simple docstring'''

											__lowercase						=TFVisionTextDualEncoderModel.from_vision_text_pretrained(
											    'Rocketknight1/tiny-random-clip-tf'     ,				'hf-internal-testing/tiny-random-bert')
											__lowercase						=1_3
											__lowercase						=floats_tensor(
											    [
											        batch_size,
											        model.vision_model.config.num_channels,
											        model.vision_model.config.image_size,
											        model.vision_model.config.image_size,
											    ])
											__lowercase						=ids_tensor([batch_size, 4]     ,				model.text_model.config.vocab_size)
											__lowercase						=random_attention_mask([batch_size, 4])
											__lowercase						={"pixel_values": pixel_values, "input_ids": input_ids, "attention_mask": attention_mask}

											return model, inputs

				def  __lowerCamelCase   (							self     :     List[str]     ,				_lowerCAmelCase     :     Any     ,				_lowerCAmelCase     :     Any):







											'''simple docstring'''

											__lowercase						=TFCLIPVisionModel(lowerCAmelCase__     ,				name='vision_model')
											__lowercase						=TFBertModel(lowerCAmelCase__     ,				name='text_model')
											return vision_model, text_model

				def  __lowerCamelCase   (							self     :     List[str]):







											'''simple docstring'''

											__lowercase						=TFCLIPVisionModelTester(self)
											__lowercase						=TFBertModelTester(self)
											__lowercase						=clip_model_tester.prepare_config_and_inputs()
											__lowercase						=bert_model_tester.prepare_config_and_inputs()

											__lowercase						=vision_config_and_inputs

											(
											    __lowercase    
											)						=text_config_and_inputs

											return {
											    "text_config": text_config,
											    "vision_config": vision_config,
											    "pixel_values": pixel_values,
											    "attention_mask": input_mask,
											    "input_ids": input_ids,
											    "text_token_type_ids": token_type_ids,
											    "text_sequence_labels": sequence_labels,
											    "text_token_labels": token_labels,
											    "text_choice_labels": choice_labels,
											}





@require_vision
@require_tf
class _UpperCamelCase						(   unittest.TestCase						):





				'''simple docstring'''





				@slow
				def  __lowerCamelCase   (							self     :     List[Any]):







											'''simple docstring'''

											__lowercase						=TFVisionTextDualEncoderModel.from_pretrained(
											    'clip-italian/clip-italian'     ,				logit_scale_init_value=1.0     ,				from_pt=lowerCAmelCase__)
											__lowercase						=VisionTextDualEncoderProcessor.from_pretrained('clip-italian/clip-italian')

											__lowercase						=Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png')
											__lowercase						=processor(
											    text=['una foto di un gatto', 'una foto di un cane']     ,				images=lowerCAmelCase__     ,				padding=lowerCAmelCase__     ,				return_tensors='np')

											__lowercase						=model(**lowerCAmelCase__)

											# verify the logits
											self.assertEqual(outputs.logits_per_image.shape     ,				(inputs.pixel_values.shape[0], inputs.input_ids.shape[0]))
											self.assertEqual(
											    outputs.logits_per_text.shape     ,				(inputs.input_ids.shape[0], inputs.pixel_values.shape[0])     ,				)

											__lowercase						=np.array([[1.228_4727, 0.310_4122]])

											self.assertTrue(np.allclose(outputs.logits_per_image.numpy()     ,				lowerCAmelCase__     ,				atol=1e-3))






from collections.abc import Callable



class   __lowercase				:




			"""simple docstring"""







			def __init__( self  :     Tuple   ,						lowerCAmelCase__  :     Callable | None = None):
									# Stores actual heap items.
									SCREAMING_SNAKE_CASE_: list  		=       []
									# Stores indexes of each item for supporting updates and deletion.
									SCREAMING_SNAKE_CASE_: dict  		=       {}
									# Stores current size of heap.
									SCREAMING_SNAKE_CASE_: Optional[Any]  		=       0
									# Stores function used to evaluate the score of an item on which basis ordering
									# will be done.
									SCREAMING_SNAKE_CASE_: Any  		=       key or (lambda lowerCAmelCase__: x)



			def        _SCREAMING_SNAKE_CASE			( self  :     Dict   ,						lowerCAmelCase__  :     int):
									return int((i - 1) / 2) if i > 0 else None



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[Any]   ,						lowerCAmelCase__  :     int):
									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       int(2 * i + 1)
									return left if 0 < left < self.size else None



			def        _SCREAMING_SNAKE_CASE			( self  :     Union[str, Any]   ,						lowerCAmelCase__  :     int):
									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       int(2 * i + 2)
									return right if 0 < right < self.size else None



			def        _SCREAMING_SNAKE_CASE			( self  :     str   ,						lowerCAmelCase__  :     int   ,						lowerCAmelCase__  :     int):
									SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: str  		=       (
									    self.pos_map[self.arr[j][0]],
									    self.pos_map[self.arr[i][0]],
									)
									# Then swap the items in the list.
									SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: List[str]  		=       self.arr[j], self.arr[i]



			def        _SCREAMING_SNAKE_CASE			( self  :     str   ,						lowerCAmelCase__  :     int   ,						lowerCAmelCase__  :     int):
									return self.arr[i][1] < self.arr[j][1]



			def        _SCREAMING_SNAKE_CASE			( self  :     str   ,						lowerCAmelCase__  :     int):
									SCREAMING_SNAKE_CASE_: Any  		=       self._left(lowerCAmelCase__)
									SCREAMING_SNAKE_CASE_: List[Any]  		=       self._right(lowerCAmelCase__)
									SCREAMING_SNAKE_CASE_: List[Any]  		=       i

									if left is not None and not self._cmp(lowerCAmelCase__   ,						lowerCAmelCase__):
															SCREAMING_SNAKE_CASE_: Optional[int]  		=       left
									if right is not None and not self._cmp(lowerCAmelCase__   ,						lowerCAmelCase__):
															SCREAMING_SNAKE_CASE_: Tuple  		=       right

									return valid_parent



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[int]   ,						lowerCAmelCase__  :     int):
									SCREAMING_SNAKE_CASE_: List[Any]  		=       self._parent(lowerCAmelCase__)
									while parent is not None and not self._cmp(lowerCAmelCase__   ,						lowerCAmelCase__):
															self._swap(lowerCAmelCase__   ,						lowerCAmelCase__)
															SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: List[str]  		=       parent, self._parent(lowerCAmelCase__)



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[Any]   ,						lowerCAmelCase__  :     int):
									SCREAMING_SNAKE_CASE_: Optional[int]  		=       self._get_valid_parent(lowerCAmelCase__)
									while valid_parent != index:
															self._swap(lowerCAmelCase__   ,						lowerCAmelCase__)
															SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: Dict  		=       valid_parent, self._get_valid_parent(lowerCAmelCase__)



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[int]   ,						lowerCAmelCase__  :     int   ,						lowerCAmelCase__  :     int):
									if item not in self.pos_map:
															return
									SCREAMING_SNAKE_CASE_: Any  		=       self.pos_map[item]
									SCREAMING_SNAKE_CASE_: int  		=       [item, self.key(lowerCAmelCase__)]
									# Make sure heap is right in both up and down direction.
									# Ideally only one of them will make any change.
									self._heapify_up(lowerCAmelCase__)
									self._heapify_down(lowerCAmelCase__)



			def        _SCREAMING_SNAKE_CASE			( self  :     List[str]   ,						lowerCAmelCase__  :     int):
									if item not in self.pos_map:
															return
									SCREAMING_SNAKE_CASE_: Optional[Any]  		=       self.pos_map[item]
									del self.pos_map[item]
									SCREAMING_SNAKE_CASE_: List[str]  		=       self.arr[self.size - 1]
									SCREAMING_SNAKE_CASE_: Tuple  		=       index
									self.size -= 1
									# Make sure heap is right in both up and down direction. Ideally only one
									# of them will make any change- so no performance loss in calling both.
									if self.size > index:
															self._heapify_up(lowerCAmelCase__)
															self._heapify_down(lowerCAmelCase__)



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[Any]   ,						lowerCAmelCase__  :     int   ,						lowerCAmelCase__  :     int):
									SCREAMING_SNAKE_CASE_: Optional[int]  		=       len(self.arr)
									if arr_len == self.size:
															self.arr.append([item, self.key(lowerCAmelCase__)])
									else:
															SCREAMING_SNAKE_CASE_: str  		=       [item, self.key(lowerCAmelCase__)]
									SCREAMING_SNAKE_CASE_: List[Any]  		=       self.size
									self.size += 1
									self._heapify_up(self.size - 1)



			def        _SCREAMING_SNAKE_CASE			( self  :     List[Any]):
									return self.arr[0] if self.size else None




			def        _SCREAMING_SNAKE_CASE			( self  :     Dict):
									SCREAMING_SNAKE_CASE_: Dict  		=       self.get_top()
									if top_item_tuple:
															self.delete_item(top_item_tuple[0])
									return top_item_tuple







def 			A_      (    ):
						pass


if __name__ == "__main__":
						import doctest

						doctest.testmod()






