



import inspect
import unittest
import warnings

from transformers import DeiTConfig
from transformers.models.auto import get_values
from transformers.testing_utils import (
    require_accelerate,
    require_torch,
    require_torch_gpu,
    require_vision,
    slow,
    torch_device,
)
from transformers.utils import cached_property, is_torch_available, is_vision_available

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 torch import nn

							from transformers import (
							    MODEL_FOR_IMAGE_CLASSIFICATION_MAPPING,
							    MODEL_FOR_SEQUENCE_CLASSIFICATION_MAPPING,
							    MODEL_MAPPING,
							    DeiTForImageClassification,
							    DeiTForImageClassificationWithTeacher,
							    DeiTForMaskedImageModeling,
							    DeiTModel,
							)
							from transformers.models.deit.modeling_deit import DEIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
							from PIL import Image

							from transformers import DeiTImageProcessor







class     __lowerCAmelCase					:



			def __init__(		self     :						Union[str, Any]				,	A     :						Union[str, Any]				,	A     :						Optional[int]=13				,	A     :						int=30				,	A     :						Union[str, Any]=2				,	A     :						Dict=3				,	A     :						Optional[int]=True				,	A     :						Optional[int]=True				,	A     :						Dict=32				,	A     :						List[str]=5				,	A     :						str=4				,	A     :						List[str]=37				,	A     :						Union[str, Any]="gelu"				,	A     :						Tuple=0.1				,	A     :						Optional[int]=0.1				,	A     :						List[str]=10				,	A     :						List[str]=0.0_2				,	A     :						Any=3				,	A     :						Any=None				,	A     :						int=2				,	)     ->					List[str]:



						"""simple docstring"""






						_UpperCAmelCase	 =     parent
						_UpperCAmelCase	 =     batch_size
						_UpperCAmelCase	 =     image_size
						_UpperCAmelCase	 =     patch_size
						_UpperCAmelCase	 =     num_channels
						_UpperCAmelCase	 =     is_training
						_UpperCAmelCase	 =     use_labels
						_UpperCAmelCase	 =     hidden_size
						_UpperCAmelCase	 =     num_hidden_layers
						_UpperCAmelCase	 =     num_attention_heads
						_UpperCAmelCase	 =     intermediate_size
						_UpperCAmelCase	 =     hidden_act
						_UpperCAmelCase	 =     hidden_dropout_prob
						_UpperCAmelCase	 =     attention_probs_dropout_prob
						_UpperCAmelCase	 =     type_sequence_label_size
						_UpperCAmelCase	 =     initializer_range
						_UpperCAmelCase	 =     scope
						_UpperCAmelCase	 =     encoder_stride

						# in DeiT, the seq length equals the number of patches + 2 (we add 2 for the [CLS] and distilation tokens)
						_UpperCAmelCase	 =     (image_size // patch_size) ** 2
						_UpperCAmelCase	 =     num_patches + 2



			def 					_lowerCamelCase (		self     :						Union[str, Any])     ->					Dict:



						"""simple docstring"""






						_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.type_sequence_label_size)

						_UpperCAmelCase	 =     self.get_config()

						return config, pixel_values, labels



			def 					_lowerCamelCase (		self     :						List[str])     ->					Dict:



						"""simple docstring"""






						return DeiTConfig(
						    image_size=self.image_size				,	patch_size=self.patch_size				,	num_channels=self.num_channels				,	hidden_size=self.hidden_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				,	is_decoder=A				,	initializer_range=self.initializer_range				,	encoder_stride=self.encoder_stride				,	)



			def 					_lowerCamelCase (		self     :						Optional[Any]				,	A     :						List[Any]				,	A     :						Optional[int]				,	A     :						Union[str, Any])     ->					Optional[Any]:



						"""simple docstring"""






						_UpperCAmelCase	 =     DeiTModel(config=A)
						model.to(A)
						model.eval()
						_UpperCAmelCase	 =     model(A)
						self.parent.assertEqual(result.last_hidden_state.shape				,	(self.batch_size, self.seq_length, self.hidden_size))



			def 					_lowerCamelCase (		self     :						int				,	A     :						Union[str, Any]				,	A     :						Tuple				,	A     :						str)     ->					Optional[int]:



						"""simple docstring"""






						_UpperCAmelCase	 =     DeiTForMaskedImageModeling(config=A)
						model.to(A)
						model.eval()
						_UpperCAmelCase	 =     model(A)
						self.parent.assertEqual(
						    result.reconstruction.shape				,	(self.batch_size, self.num_channels, self.image_size, self.image_size))

						# test greyscale images
						_UpperCAmelCase	 =     1
						_UpperCAmelCase	 =     DeiTForMaskedImageModeling(A)
						model.to(A)
						model.eval()

						_UpperCAmelCase	 =     floats_tensor([self.batch_size, 1, self.image_size, self.image_size])
						_UpperCAmelCase	 =     model(A)
						self.parent.assertEqual(result.reconstruction.shape				,	(self.batch_size, 1, self.image_size, self.image_size))



			def 					_lowerCamelCase (		self     :						Optional[int]				,	A     :						Union[str, Any]				,	A     :						Union[str, Any]				,	A     :						str)     ->					List[Any]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.type_sequence_label_size
						_UpperCAmelCase	 =     DeiTForImageClassification(A)
						model.to(A)
						model.eval()
						_UpperCAmelCase	 =     model(A				,	labels=A)
						self.parent.assertEqual(result.logits.shape				,	(self.batch_size, self.type_sequence_label_size))

						# test greyscale images
						_UpperCAmelCase	 =     1
						_UpperCAmelCase	 =     DeiTForImageClassification(A)
						model.to(A)
						model.eval()

						_UpperCAmelCase	 =     floats_tensor([self.batch_size, 1, self.image_size, self.image_size])
						_UpperCAmelCase	 =     model(A				,	labels=A)
						self.parent.assertEqual(result.logits.shape				,	(self.batch_size, self.type_sequence_label_size))



			def 					_lowerCamelCase (		self     :						Optional[int])     ->					Union[str, Any]:



						"""simple docstring"""






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







@require_torch
class     __lowerCAmelCase					(    A       ,		A       ,		unittest.TestCase		):
			UpperCamelCase           =  (
			    (
			        DeiTModel,
			        DeiTForImageClassification,
			        DeiTForImageClassificationWithTeacher,
			        DeiTForMaskedImageModeling,
			    )
			    if is_torch_available()
			    else ()
			)
			UpperCamelCase           =  (
			    {
			        '''feature-extraction''': DeiTModel,
			        '''image-classification''': (DeiTForImageClassification, DeiTForImageClassificationWithTeacher),
			    }
			    if is_torch_available()
			    else {}
			)

			UpperCamelCase           =  False
			UpperCamelCase           =  False
			UpperCamelCase           =  False



			def 					_lowerCamelCase (		self     :						str)     ->					Tuple:



						"""simple docstring"""






						_UpperCAmelCase	 =     DeiTModelTester(self)
						_UpperCAmelCase	 =     ConfigTester(self				,	config_class=A				,	has_text_modality=A				,	hidden_size=37)



			def 					_lowerCamelCase (		self     :						List[Any])     ->					List[str]:



						"""simple docstring"""






						self.config_tester.run_common_tests()



			@unittest.skip(reason='DeiT does not use inputs_embeds')
			def 					_lowerCamelCase (		self     :						List[str])     ->					Dict:



						"""simple docstring"""






						pass



			def 					_lowerCamelCase (		self     :						Union[str, Any])     ->					Union[str, Any]:



						"""simple docstring"""






						_UpperCAmelCase ,  _UpperCAmelCase	 =     self.model_tester.prepare_config_and_inputs_for_common()

						for model_class in self.all_model_classes:
									_UpperCAmelCase	 =     model_class(A)
									self.assertIsInstance(model.get_input_embeddings()				,	(nn.Module))
									_UpperCAmelCase	 =     model.get_output_embeddings()
									self.assertTrue(x is None or isinstance(A				,	nn.Linear))



			def 					_lowerCamelCase (		self     :						List[str])     ->					Tuple:



						"""simple docstring"""






						_UpperCAmelCase ,  _UpperCAmelCase	 =     self.model_tester.prepare_config_and_inputs_for_common()

						for model_class in self.all_model_classes:
									_UpperCAmelCase	 =     model_class(A)
									_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]				,	A)



			def 					_lowerCamelCase (		self     :						Tuple)     ->					Tuple:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_model(*A)



			def 					_lowerCamelCase (		self     :						Optional[Any])     ->					Union[str, Any]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_for_masked_image_modeling(*A)



			def 					_lowerCamelCase (		self     :						Optional[Any])     ->					Union[str, Any]:



						"""simple docstring"""






						_UpperCAmelCase	 =     self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_for_image_classification(*A)



			def 					_lowerCamelCase (		self     :						Union[str, Any]				,	A     :						Optional[Any]				,	A     :						List[str]				,	A     :						str=False)     ->					Dict:



						"""simple docstring"""






						_UpperCAmelCase	 =     super()._prepare_for_class(A				,	A				,	return_labels=A)

						if return_labels:
									if model_class.__name__ == "DeiTForImageClassificationWithTeacher":
												del inputs_dict["labels"]

						return inputs_dict



			def 					_lowerCamelCase (		self     :						Union[str, Any])     ->					Optional[int]:



						"""simple docstring"""






						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:
									# DeiTForImageClassificationWithTeacher supports inference-only
									if (
									    model_class in get_values(A)
									    or model_class.__name__ == "DeiTForImageClassificationWithTeacher"
									):
												continue
									_UpperCAmelCase	 =     model_class(A)
									model.to(A)
									model.train()
									_UpperCAmelCase	 =     self._prepare_for_class(A				,	A				,	return_labels=A)
									_UpperCAmelCase	 =     model(**A).loss
									loss.backward()



			def 					_lowerCamelCase (		self     :						List[Any])     ->					Tuple:



						"""simple docstring"""






						_UpperCAmelCase ,  _UpperCAmelCase	 =     self.model_tester.prepare_config_and_inputs_for_common()
						if not self.model_tester.is_training:
									return

						_UpperCAmelCase	 =     False
						_UpperCAmelCase	 =     True

						for model_class in self.all_model_classes:
									if model_class in get_values(A) or not model_class.supports_gradient_checkpointing:
												continue
									# DeiTForImageClassificationWithTeacher supports inference-only
									if model_class.__name__ == "DeiTForImageClassificationWithTeacher":
												continue
									_UpperCAmelCase	 =     model_class(A)
									model.gradient_checkpointing_enable()
									model.to(A)
									model.train()
									_UpperCAmelCase	 =     self._prepare_for_class(A				,	A				,	return_labels=A)
									_UpperCAmelCase	 =     model(**A).loss
									loss.backward()



			def 					_lowerCamelCase (		self     :						Optional[Any])     ->					Optional[int]:



						"""simple docstring"""






						_UpperCAmelCase ,  _UpperCAmelCase	 =     self.model_tester.prepare_config_and_inputs_for_common()

						_UpperCAmelCase	 =     [
						    {'title': 'multi_label_classification', 'num_labels': 2, 'dtype': torch.float},
						    {'title': 'single_label_classification', 'num_labels': 1, 'dtype': torch.long},
						    {'title': 'regression', 'num_labels': 1, 'dtype': torch.float},
						]

						for model_class in self.all_model_classes:
									if (
									    model_class
									    not in [
									        *get_values(A),
									        *get_values(A),
									    ]
									    or model_class.__name__ == "DeiTForImageClassificationWithTeacher"
									):
												continue

									for problem_type in problem_types:
												with self.subTest(msg=F"Testing {model_class} with {problem_type['title']}"):
															_UpperCAmelCase	 =     problem_type['title']
															_UpperCAmelCase	 =     problem_type['num_labels']

															_UpperCAmelCase	 =     model_class(A)
															model.to(A)
															model.train()

															_UpperCAmelCase	 =     self._prepare_for_class(A				,	A				,	return_labels=A)

															if problem_type["num_labels"] > 1:
																		_UpperCAmelCase	 =     inputs['labels'].unsqueeze(1).repeat(1				,	problem_type['num_labels'])

															_UpperCAmelCase	 =     inputs['labels'].to(problem_type['dtype'])

															# This tests that we do not trigger the warning form PyTorch "Using a target size that is different
															# to the input size. This will likely lead to incorrect results due to broadcasting. Please ensure
															# they have the same size." which is a symptom something in wrong for the regression problem.
															# See https://github.com/huggingface/transformers/issues/11780
															with warnings.catch_warnings(record=A) as warning_list:
																		_UpperCAmelCase	 =     model(**A).loss
															for w in warning_list:
																		if "Using a target size that is different to the input size" in str(w.message):
																					raise ValueError(
																					    F"Something is going wrong in the regression problem: intercepted {w.message}")

															loss.backward()



			@slow
			def 					_lowerCamelCase (		self     :						int)     ->					Optional[int]:



						"""simple docstring"""






						for model_name in DEIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
									_UpperCAmelCase	 =     DeiTModel.from_pretrained(A)
									self.assertIsNotNone(A)





def 							A			(  )       ->				List[str]:







			'''simple docstring'''
			_UpperCAmelCase	 =     Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'					)
			return image







@require_torch
@require_vision
class     __lowerCAmelCase					(    unittest.TestCase		):



			@cached_property
			def 					_lowerCamelCase (		self     :						Union[str, Any])     ->					Any:



						"""simple docstring"""






						return (
						    DeiTImageProcessor.from_pretrained('facebook/deit-base-distilled-patch16-224')
						    if is_vision_available()
						    else None
						)



			@slow
			def 					_lowerCamelCase (		self     :						Any)     ->					int:



						"""simple docstring"""






						_UpperCAmelCase	 =     DeiTForImageClassificationWithTeacher.from_pretrained('facebook/deit-base-distilled-patch16-224').to(
						    A)

						_UpperCAmelCase	 =     self.default_image_processor
						_UpperCAmelCase	 =     prepare_img()
						_UpperCAmelCase	 =     image_processor(images=A				,	return_tensors='pt').to(A)

						# forward pass
						with torch.no_grad():
									_UpperCAmelCase	 =     model(**A)

						# verify the logits
						_UpperCAmelCase	 =     torch.Size((1, 10_00))
						self.assertEqual(outputs.logits.shape				,	A)

						_UpperCAmelCase	 =     torch.tensor([-1.0_2_6_6, 0.1_9_1_2, -1.2_8_6_1]).to(A)

						self.assertTrue(torch.allclose(outputs.logits[0, :3]				,	A				,	atol=1E-4))



			@slow
			@require_accelerate
			@require_torch_gpu
			def 					_lowerCamelCase (		self     :						int)     ->					Union[str, Any]:



						"""simple docstring"""






						_UpperCAmelCase	 =     DeiTModel.from_pretrained(
						    'facebook/deit-base-distilled-patch16-224'				,	torch_dtype=torch.floataa				,	device_map='auto')
						_UpperCAmelCase	 =     self.default_image_processor

						_UpperCAmelCase	 =     prepare_img()
						_UpperCAmelCase	 =     image_processor(images=A				,	return_tensors='pt')
						_UpperCAmelCase	 =     inputs.pixel_values.to(A)

						# forward pass to make sure inference works in fp16
						with torch.no_grad():
									_UpperCAmelCase	 =     model(A)





def 							A			(  _UpperCAmelCase       :     list					)       ->				list:







			'''simple docstring'''
			if len(_UpperCAmelCase					) <= 1:
						return lst

			_UpperCAmelCase	 =     1

			while i < len(_UpperCAmelCase					):
						if lst[i - 1] <= lst[i]:
									i += 1
						else:
									_UpperCAmelCase ,  _UpperCAmelCase	 =     lst[i], lst[i - 1]
									i -= 1
									if i == 0:
												_UpperCAmelCase	 =     1

			return lst


if __name__ == "__main__":
							UpperCAmelCase__     = input("Enter numbers separated by a comma:\n").strip()
							UpperCAmelCase__     = [int(item) for item in user_input.split(",")]
							print(gnome_sort(unsorted))
