




import inspect
import unittest

from transformers import SegformerConfig, is_torch_available, is_vision_available
from transformers.models.auto import get_values
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
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
				import torch

				from transformers import (
				    MODEL_MAPPING,
				    SegformerForImageClassification,
				    SegformerForSemanticSegmentation,
				    SegformerModel,
				)
				from transformers.models.segformer.modeling_segformer import SEGFORMER_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
				from PIL import Image

				from transformers import SegformerImageProcessor




class       _A				(		__lowercase     ):






		def 				UpperCAmelCase (    self			):
								_UpperCAmelCase      =			self.config_class(**self.inputs_dict			)
								self.parent.assertTrue(hasattr(_SCREAMING_SNAKE_CASE						,		"""hidden_sizes"""			)			)
								self.parent.assertTrue(hasattr(_SCREAMING_SNAKE_CASE						,		"""num_attention_heads"""			)			)
								self.parent.assertTrue(hasattr(_SCREAMING_SNAKE_CASE						,		"""num_encoder_blocks"""			)			)




class       _A				:






		def __init__(    self						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE=13						,		_SCREAMING_SNAKE_CASE=64						,		_SCREAMING_SNAKE_CASE=3						,		_SCREAMING_SNAKE_CASE=4						,		_SCREAMING_SNAKE_CASE=[2, 2, 2, 2]						,		_SCREAMING_SNAKE_CASE=[8, 4, 2, 1]						,		_SCREAMING_SNAKE_CASE=[16, 32, 64, 128]						,		_SCREAMING_SNAKE_CASE=[1, 4, 8, 16]						,		_SCREAMING_SNAKE_CASE=[1, 2, 4, 8]						,		_SCREAMING_SNAKE_CASE=True						,		_SCREAMING_SNAKE_CASE=True						,		_SCREAMING_SNAKE_CASE="gelu"						,		_SCREAMING_SNAKE_CASE=0.1						,		_SCREAMING_SNAKE_CASE=0.1						,		_SCREAMING_SNAKE_CASE=0.02						,		_SCREAMING_SNAKE_CASE=3						,		_SCREAMING_SNAKE_CASE=None						,		):
								_UpperCAmelCase      =			parent
								_UpperCAmelCase      =			batch_size
								_UpperCAmelCase      =			image_size
								_UpperCAmelCase      =			num_channels
								_UpperCAmelCase      =			num_encoder_blocks
								_UpperCAmelCase      =			sr_ratios
								_UpperCAmelCase      =			depths
								_UpperCAmelCase      =			hidden_sizes
								_UpperCAmelCase      =			downsampling_rates
								_UpperCAmelCase      =			num_attention_heads
								_UpperCAmelCase      =			is_training
								_UpperCAmelCase      =			use_labels
								_UpperCAmelCase      =			hidden_act
								_UpperCAmelCase      =			hidden_dropout_prob
								_UpperCAmelCase      =			attention_probs_dropout_prob
								_UpperCAmelCase      =			initializer_range
								_UpperCAmelCase      =			num_labels
								_UpperCAmelCase      =			scope






		def 				UpperCAmelCase (    self			):
								_UpperCAmelCase      =			floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]			)

								_UpperCAmelCase      =			None
								if self.use_labels:
														_UpperCAmelCase      =			ids_tensor([self.batch_size, self.image_size, self.image_size]						,		self.num_labels			)

								_UpperCAmelCase      =			self.get_config()
								return config, pixel_values, labels






		def 				UpperCAmelCase (    self			):
								return SegformerConfig(
								    image_size=self.image_size						,		num_channels=self.num_channels						,		num_encoder_blocks=self.num_encoder_blocks						,		depths=self.depths						,		hidden_sizes=self.hidden_sizes						,		num_attention_heads=self.num_attention_heads						,		hidden_act=self.hidden_act						,		hidden_dropout_prob=self.hidden_dropout_prob						,		attention_probs_dropout_prob=self.attention_probs_dropout_prob						,		initializer_range=self.initializer_range						,		)






		def 				UpperCAmelCase (    self						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			):
								_UpperCAmelCase      =			SegformerModel(config=_SCREAMING_SNAKE_CASE			)
								model.to(_SCREAMING_SNAKE_CASE			)
								model.eval()
								_UpperCAmelCase      =			model(_SCREAMING_SNAKE_CASE			)
								_UpperCAmelCase      =			_UpperCAmelCase      =			self.image_size // (self.downsampling_rates[-1] * 2)
								self.parent.assertEqual(
								    result.last_hidden_state.shape						,		(self.batch_size, self.hidden_sizes[-1], expected_height, expected_width)			)






		def 				UpperCAmelCase (    self						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			):
								_UpperCAmelCase      =			self.num_labels
								_UpperCAmelCase      =			SegformerForSemanticSegmentation(_SCREAMING_SNAKE_CASE			)
								model.to(_SCREAMING_SNAKE_CASE			)
								model.eval()
								_UpperCAmelCase      =			model(_SCREAMING_SNAKE_CASE			)
								self.parent.assertEqual(
								    result.logits.shape						,		(self.batch_size, self.num_labels, self.image_size // 4, self.image_size // 4)			)
								_UpperCAmelCase      =			model(_SCREAMING_SNAKE_CASE						,		labels=_SCREAMING_SNAKE_CASE			)
								self.parent.assertEqual(
								    result.logits.shape						,		(self.batch_size, self.num_labels, self.image_size // 4, self.image_size // 4)			)
								self.parent.assertGreater(result.loss						,		0.0			)






		def 				UpperCAmelCase (    self						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			):
								_UpperCAmelCase      =			1
								_UpperCAmelCase      =			SegformerForSemanticSegmentation(config=_SCREAMING_SNAKE_CASE			)
								model.to(_SCREAMING_SNAKE_CASE			)
								model.eval()
								_UpperCAmelCase      =			torch.randint(0						,		1						,		(self.batch_size, self.image_size, self.image_size)			).to(_SCREAMING_SNAKE_CASE			)
								_UpperCAmelCase      =			model(_SCREAMING_SNAKE_CASE						,		labels=_SCREAMING_SNAKE_CASE			)
								self.parent.assertGreater(result.loss						,		0.0			)






		def 				UpperCAmelCase (    self			):
								_UpperCAmelCase      =			self.prepare_config_and_inputs()
								_UpperCAmelCase    ,					_UpperCAmelCase    ,					_UpperCAmelCase      =			config_and_inputs
								_UpperCAmelCase      =			{"""pixel_values""": pixel_values}
								return config, inputs_dict




@require_torch
class       _A				(		__lowercase       ,     __lowercase       ,     unittest.TestCase     ):
		__a					    =       (
		    (
		        SegformerModel,
		        SegformerForSemanticSegmentation,
		        SegformerForImageClassification,
		    )
		    if is_torch_available()
		    else ()
		)
		__a					    =       (
		    {
		        """feature-extraction""": SegformerModel,
		        """image-classification""": SegformerForImageClassification,
		        """image-segmentation""": SegformerForSemanticSegmentation,
		    }
		    if is_torch_available()
		    else {}
		)

		__a					    =       True
		__a					    =       False
		__a					    =       False
		__a					    =       False






		def 				UpperCAmelCase (    self			):
								_UpperCAmelCase      =			SegformerModelTester(self			)
								_UpperCAmelCase      =			SegformerConfigTester(self						,		config_class=_SCREAMING_SNAKE_CASE			)






		def 				UpperCAmelCase (    self			):
								self.config_tester.run_common_tests()






		def 				UpperCAmelCase (    self			):
								_UpperCAmelCase      =			self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_model(*_SCREAMING_SNAKE_CASE			)






		def 				UpperCAmelCase (    self			):
								_UpperCAmelCase      =			self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_for_binary_image_segmentation(*_SCREAMING_SNAKE_CASE			)






		def 				UpperCAmelCase (    self			):
								_UpperCAmelCase      =			self.model_tester.prepare_config_and_inputs()
								self.model_tester.create_and_check_for_image_segmentation(*_SCREAMING_SNAKE_CASE			)






		@unittest.skip("""SegFormer does not use inputs_embeds"""			)
		def 				UpperCAmelCase (    self			):
								pass






		@unittest.skip("""SegFormer does not have get_input_embeddings method and get_output_embeddings methods"""			)
		def 				UpperCAmelCase (    self			):
								pass






		def 				UpperCAmelCase (    self			):
								_UpperCAmelCase    ,					_UpperCAmelCase      =			self.model_tester.prepare_config_and_inputs_for_common()

								for model_class in self.all_model_classes:
														_UpperCAmelCase      =			model_class(_SCREAMING_SNAKE_CASE			)
														_UpperCAmelCase      =			inspect.signature(model.forward			)
														# signature.parameters is an OrderedDict => so arg_names order is deterministic
														_UpperCAmelCase      =			[*signature.parameters.keys()]

														_UpperCAmelCase      =			["""pixel_values"""]
														self.assertListEqual(arg_names[:1]						,		_SCREAMING_SNAKE_CASE			)






		def 				UpperCAmelCase (    self			):
								_UpperCAmelCase    ,					_UpperCAmelCase      =			self.model_tester.prepare_config_and_inputs_for_common()
								_UpperCAmelCase      =			True

								for model_class in self.all_model_classes:
														_UpperCAmelCase      =			True
														_UpperCAmelCase      =			False
														_UpperCAmelCase      =			True
														_UpperCAmelCase      =			model_class(_SCREAMING_SNAKE_CASE			)
														model.to(_SCREAMING_SNAKE_CASE			)
														model.eval()
														with torch.no_grad():
																				_UpperCAmelCase      =			model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			)			)
														_UpperCAmelCase      =			outputs.attentions

														_UpperCAmelCase      =			sum(self.model_tester.depths			)
														self.assertEqual(len(_SCREAMING_SNAKE_CASE			)						,		_SCREAMING_SNAKE_CASE			)

														# check that output_attentions also work using config
														del inputs_dict["output_attentions"]
														_UpperCAmelCase      =			True
														_UpperCAmelCase      =			model_class(_SCREAMING_SNAKE_CASE			)
														model.to(_SCREAMING_SNAKE_CASE			)
														model.eval()
														with torch.no_grad():
																				_UpperCAmelCase      =			model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			)			)
														_UpperCAmelCase      =			outputs.attentions

														self.assertEqual(len(_SCREAMING_SNAKE_CASE			)						,		_SCREAMING_SNAKE_CASE			)

														# verify the first attentions (first block, first layer)
														_UpperCAmelCase      =			(self.model_tester.image_size // 4) ** 2
														_UpperCAmelCase      =			(self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
														self.assertListEqual(
														    list(attentions[0].shape[-3:]			)						,		[self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]						,		)

														# verify the last attentions (last block, last layer)
														_UpperCAmelCase      =			(self.model_tester.image_size // 32) ** 2
														_UpperCAmelCase      =			(self.model_tester.image_size // (32 * self.model_tester.sr_ratios[-1])) ** 2
														self.assertListEqual(
														    list(attentions[-1].shape[-3:]			)						,		[self.model_tester.num_attention_heads[-1], expected_seq_len, expected_reduced_seq_len]						,		)
														_UpperCAmelCase      =			len(_SCREAMING_SNAKE_CASE			)

														# Check attention is always last and order is fine
														_UpperCAmelCase      =			True
														_UpperCAmelCase      =			True
														_UpperCAmelCase      =			model_class(_SCREAMING_SNAKE_CASE			)
														model.to(_SCREAMING_SNAKE_CASE			)
														model.eval()
														with torch.no_grad():
																				_UpperCAmelCase      =			model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			)			)

														self.assertEqual(out_len + 1						,		len(_SCREAMING_SNAKE_CASE			)			)

														_UpperCAmelCase      =			outputs.attentions

														self.assertEqual(len(_SCREAMING_SNAKE_CASE			)						,		_SCREAMING_SNAKE_CASE			)
														# verify the first attentions (first block, first layer)
														_UpperCAmelCase      =			(self.model_tester.image_size // 4) ** 2
														_UpperCAmelCase      =			(self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
														self.assertListEqual(
														    list(self_attentions[0].shape[-3:]			)						,		[self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len]						,		)






		def 				UpperCAmelCase (    self			):
								def check_hidden_states_output(_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			):
														_UpperCAmelCase      =			model_class(_SCREAMING_SNAKE_CASE			)
														model.to(_SCREAMING_SNAKE_CASE			)
														model.eval()

														with torch.no_grad():
																				_UpperCAmelCase      =			model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			)			)

														_UpperCAmelCase      =			outputs.hidden_states

														_UpperCAmelCase      =			self.model_tester.num_encoder_blocks
														self.assertEqual(len(_SCREAMING_SNAKE_CASE			)						,		_SCREAMING_SNAKE_CASE			)

														# verify the first hidden states (first block)
														self.assertListEqual(
														    list(hidden_states[0].shape[-3:]			)						,		[
														        self.model_tester.hidden_sizes[0],
														        self.model_tester.image_size // 4,
														        self.model_tester.image_size // 4,
														    ]						,		)

								_UpperCAmelCase    ,					_UpperCAmelCase      =			self.model_tester.prepare_config_and_inputs_for_common()

								for model_class in self.all_model_classes:
														_UpperCAmelCase      =			True
														check_hidden_states_output(_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			)

														# check that output_hidden_states also work using config
														del inputs_dict["output_hidden_states"]
														_UpperCAmelCase      =			True

														check_hidden_states_output(_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE			)






		def 				UpperCAmelCase (    self			):
								if not self.model_tester.is_training:
														return

								_UpperCAmelCase    ,					_UpperCAmelCase      =			self.model_tester.prepare_config_and_inputs_for_common()
								_UpperCAmelCase      =			True

								for model_class in self.all_model_classes:
														if model_class in get_values(_SCREAMING_SNAKE_CASE			):
																				continue

														_UpperCAmelCase      =			model_class(_SCREAMING_SNAKE_CASE			)
														model.to(_SCREAMING_SNAKE_CASE			)
														model.train()
														_UpperCAmelCase      =			self._prepare_for_class(_SCREAMING_SNAKE_CASE						,		_SCREAMING_SNAKE_CASE						,		return_labels=_SCREAMING_SNAKE_CASE			)
														_UpperCAmelCase      =			model(**_SCREAMING_SNAKE_CASE			).loss
														loss.backward()






		@unittest.skip("""Will be fixed soon by reducing the size of the model used for common tests."""			)
		def 				UpperCAmelCase (    self			):
								pass






		@slow
		def 				UpperCAmelCase (    self			):
								for model_name in SEGFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
														_UpperCAmelCase      =			SegformerModel.from_pretrained(_SCREAMING_SNAKE_CASE			)
														self.assertIsNotNone(_SCREAMING_SNAKE_CASE			)




def        _SCREAMING_SNAKE_CASE      (		)						->				int:
						_UpperCAmelCase      =			Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""       )
						return image




@require_torch
class       _A				(		unittest.TestCase     ):






		@slow
		def 				UpperCAmelCase (    self			):
								# only resize + normalize
								_UpperCAmelCase      =			SegformerImageProcessor(
								    image_scale=(512, 512)						,		keep_ratio=_SCREAMING_SNAKE_CASE						,		align=_SCREAMING_SNAKE_CASE						,		do_random_crop=_SCREAMING_SNAKE_CASE			)
								_UpperCAmelCase      =			SegformerForSemanticSegmentation.from_pretrained("""nvidia/segformer-b0-finetuned-ade-512-512"""			).to(
								    _SCREAMING_SNAKE_CASE			)

								_UpperCAmelCase      =			prepare_img()
								_UpperCAmelCase      =			image_processor(images=_SCREAMING_SNAKE_CASE						,		return_tensors="""pt"""			)
								_UpperCAmelCase      =			encoded_inputs.pixel_values.to(_SCREAMING_SNAKE_CASE			)

								with torch.no_grad():
														_UpperCAmelCase      =			model(_SCREAMING_SNAKE_CASE			)

								_UpperCAmelCase      =			torch.Size((1, model.config.num_labels, 128, 128)			)
								self.assertEqual(outputs.logits.shape						,		_SCREAMING_SNAKE_CASE			)

								_UpperCAmelCase      =			torch.tensor(
								    [
								        [[-4.6310, -5.5232, -6.2356], [-5.1921, -6.1444, -6.5996], [-5.4424, -6.2790, -6.7574]],
								        [[-12.1391, -13.3122, -13.9554], [-12.8732, -13.9352, -14.3563], [-12.9438, -13.8226, -14.2513]],
								        [[-12.5134, -13.4686, -14.4915], [-12.8669, -14.4343, -14.7758], [-13.2523, -14.5819, -15.0694]],
								    ]			).to(_SCREAMING_SNAKE_CASE			)
								self.assertTrue(torch.allclose(outputs.logits[0, :3, :3, :3]						,		_SCREAMING_SNAKE_CASE						,		atol=1e-4			)			)






		@slow
		def 				UpperCAmelCase (    self			):
								# only resize + normalize
								_UpperCAmelCase      =			SegformerImageProcessor(
								    image_scale=(512, 512)						,		keep_ratio=_SCREAMING_SNAKE_CASE						,		align=_SCREAMING_SNAKE_CASE						,		do_random_crop=_SCREAMING_SNAKE_CASE			)
								_UpperCAmelCase      =			SegformerForSemanticSegmentation.from_pretrained(
								    """nvidia/segformer-b1-finetuned-cityscapes-1024-1024"""			).to(_SCREAMING_SNAKE_CASE			)

								_UpperCAmelCase      =			prepare_img()
								_UpperCAmelCase      =			image_processor(images=_SCREAMING_SNAKE_CASE						,		return_tensors="""pt"""			)
								_UpperCAmelCase      =			encoded_inputs.pixel_values.to(_SCREAMING_SNAKE_CASE			)

								with torch.no_grad():
														_UpperCAmelCase      =			model(_SCREAMING_SNAKE_CASE			)

								_UpperCAmelCase      =			torch.Size((1, model.config.num_labels, 128, 128)			)
								self.assertEqual(outputs.logits.shape						,		_SCREAMING_SNAKE_CASE			)

								_UpperCAmelCase      =			torch.tensor(
								    [
								        [[-13.5748, -13.9111, -12.6500], [-14.3500, -15.3683, -14.2328], [-14.7532, -16.0424, -15.6087]],
								        [[-17.1651, -15.8725, -12.9653], [-17.2580, -17.3718, -14.8223], [-16.6058, -16.8783, -16.7452]],
								        [[-3.6456, -3.0209, -1.4203], [-3.0797, -3.1959, -2.0000], [-1.8757, -1.9217, -1.6997]],
								    ]			).to(_SCREAMING_SNAKE_CASE			)
								self.assertTrue(torch.allclose(outputs.logits[0, :3, :3, :3]						,		_SCREAMING_SNAKE_CASE						,		atol=1e-1			)			)






		@slow
		def 				UpperCAmelCase (    self			):
								# only resize + normalize
								_UpperCAmelCase      =			SegformerImageProcessor(
								    image_scale=(512, 512)						,		keep_ratio=_SCREAMING_SNAKE_CASE						,		align=_SCREAMING_SNAKE_CASE						,		do_random_crop=_SCREAMING_SNAKE_CASE			)
								_UpperCAmelCase      =			SegformerForSemanticSegmentation.from_pretrained("""nvidia/segformer-b0-finetuned-ade-512-512"""			).to(
								    _SCREAMING_SNAKE_CASE			)

								_UpperCAmelCase      =			prepare_img()
								_UpperCAmelCase      =			image_processor(images=_SCREAMING_SNAKE_CASE						,		return_tensors="""pt"""			)
								_UpperCAmelCase      =			encoded_inputs.pixel_values.to(_SCREAMING_SNAKE_CASE			)

								with torch.no_grad():
														_UpperCAmelCase      =			model(_SCREAMING_SNAKE_CASE			)

								_UpperCAmelCase      =			outputs.logits.detach().cpu()

								_UpperCAmelCase      =			image_processor.post_process_semantic_segmentation(outputs=_SCREAMING_SNAKE_CASE						,		target_sizes=[(500, 300)]			)
								_UpperCAmelCase      =			torch.Size((500, 300)			)
								self.assertEqual(segmentation[0].shape						,		_SCREAMING_SNAKE_CASE			)

								_UpperCAmelCase      =			image_processor.post_process_semantic_segmentation(outputs=_SCREAMING_SNAKE_CASE			)
								_UpperCAmelCase      =			torch.Size((128, 128)			)
								self.assertEqual(segmentation[0].shape						,		_SCREAMING_SNAKE_CASE			)





from __future__ import annotations




def        _SCREAMING_SNAKE_CASE      (		snake_case       )						->				list[int]:
						if len(snake_case       ) == 0:
												return array

						_UpperCAmelCase    ,					_UpperCAmelCase      =			min(snake_case       ), max(snake_case       )

						# Compute the variables
						_UpperCAmelCase      =			_max - _min + 1
						_UpperCAmelCase    ,					_UpperCAmelCase      =			[0] * holes_range, [0] * holes_range

						# Make the sorting.
						for i in array:
												_UpperCAmelCase      =			i - _min
												_UpperCAmelCase      =			i
												holes_repeat[index] += 1

						# Makes the array back by replacing the numbers.
						_UpperCAmelCase      =			0
						for i in range(snake_case       ):
												while holes_repeat[i] > 0:
																		_UpperCAmelCase      =			holes[i]
																		index += 1
																		holes_repeat[i] -= 1

    # Returns the sorted array.
						return array


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				a													=			input("Enter numbers separated by comma:\n")
				a													=			[int(x) for x in user_input.split(",")]
				print(pigeon_sort(unsorted))