




import collections
import inspect
import unittest

from transformers import DinatConfig
from transformers.testing_utils import require_natten, require_torch, require_vision, slow, torch_device
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_backbone_common import BackboneTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, _config_zero_init, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
							import torch
							from torch import nn

							from transformers import DinatBackbone, DinatForImageClassification, DinatModel
							from transformers.models.dinat.modeling_dinat import DINAT_PRETRAINED_MODEL_ARCHIVE_LIST

if is_vision_available():
							from PIL import Image

							from transformers import AutoImageProcessor


class     __SCREAMING_SNAKE_CASE							:

					def __init__(    self			,	__lowercase			,	__lowercase=13			,	__lowercase=64			,	__lowercase=4			,	__lowercase=3			,	__lowercase=16			,	__lowercase=[1, 2, 1]			,	__lowercase=[2, 4, 8]			,	__lowercase=3			,	__lowercase=[[3], [1, 2], [1]]			,	__lowercase=2.0			,	__lowercase=True			,	__lowercase=0.0			,	__lowercase=0.0			,	__lowercase=0.1			,	__lowercase="gelu"			,	__lowercase=True			,	__lowercase=0.02			,	__lowercase=1E-5			,	__lowercase=True			,	__lowercase=None			,	__lowercase=True			,	__lowercase=10			,	__lowercase=["stage1", "stage2"]			,	__lowercase=[1, 2]			,	):







						'''simple docstring'''




						lowerCamelCase_							:		Tuple							       =							parent
						lowerCamelCase_							:		str							       =							batch_size
						lowerCamelCase_							:		Optional[Any]							       =							image_size
						lowerCamelCase_							:		Any							       =							patch_size
						lowerCamelCase_							:		Optional[Any]							       =							num_channels
						lowerCamelCase_							:		Optional[int]							       =							embed_dim
						lowerCamelCase_							:		Any							       =							depths
						lowerCamelCase_							:		Tuple							       =							num_heads
						lowerCamelCase_							:		str							       =							kernel_size
						lowerCamelCase_							:		Optional[Any]							       =							dilations
						lowerCamelCase_							:		Optional[int]							       =							mlp_ratio
						lowerCamelCase_							:		Dict							       =							qkv_bias
						lowerCamelCase_							:		Union[str, Any]							       =							hidden_dropout_prob
						lowerCamelCase_							:		Optional[int]							       =							attention_probs_dropout_prob
						lowerCamelCase_							:		Optional[int]							       =							drop_path_rate
						lowerCamelCase_							:		Union[str, Any]							       =							hidden_act
						lowerCamelCase_							:		str							       =							patch_norm
						lowerCamelCase_							:		int							       =							layer_norm_eps
						lowerCamelCase_							:		List[Any]							       =							initializer_range
						lowerCamelCase_							:		Dict							       =							is_training
						lowerCamelCase_							:		List[str]							       =							scope
						lowerCamelCase_							:		List[Any]							       =							use_labels
						lowerCamelCase_							:		List[str]							       =							num_labels
						lowerCamelCase_							:		Any							       =							out_features
						lowerCamelCase_							:		int							       =							out_indices

					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_							:		str							       =							floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size] )

						lowerCamelCase_							:		Any							       =							None
						if self.use_labels:
							lowerCamelCase_							:		Union[str, Any]							       =							ids_tensor([self.batch_size]			,	self.num_labels )

						lowerCamelCase_							:		Union[str, Any]							       =							self.get_config()

						return config, pixel_values, labels

					def      lowercase_							(    self ):







						'''simple docstring'''




						return DinatConfig(
						    num_labels=self.num_labels			,	image_size=self.image_size			,	patch_size=self.patch_size			,	num_channels=self.num_channels			,	embed_dim=self.embed_dim			,	depths=self.depths			,	num_heads=self.num_heads			,	kernel_size=self.kernel_size			,	dilations=self.dilations			,	mlp_ratio=self.mlp_ratio			,	qkv_bias=self.qkv_bias			,	hidden_dropout_prob=self.hidden_dropout_prob			,	attention_probs_dropout_prob=self.attention_probs_dropout_prob			,	drop_path_rate=self.drop_path_rate			,	hidden_act=self.hidden_act			,	patch_norm=self.patch_norm			,	layer_norm_eps=self.layer_norm_eps			,	initializer_range=self.initializer_range			,	out_features=self.out_features			,	out_indices=self.out_indices			,	)

					def      lowercase_							(    self			,	__lowercase			,	__lowercase			,	__lowercase ):







						'''simple docstring'''




						lowerCamelCase_							:		str							       =							DinatModel(config=__lowercase )
						model.to(__lowercase )
						model.eval()
						lowerCamelCase_							:		Optional[Any]							       =							model(__lowercase )

						lowerCamelCase_							:		Union[str, Any]							       =							(config.image_size // config.patch_size) // (2 ** (len(config.depths ) - 1))
						lowerCamelCase_							:		Any							       =							int(config.embed_dim * 2 ** (len(config.depths ) - 1) )

						self.parent.assertEqual(
						    result.last_hidden_state.shape			,	(self.batch_size, expected_height, expected_width, expected_dim) )

					def      lowercase_							(    self			,	__lowercase			,	__lowercase			,	__lowercase ):







						'''simple docstring'''




						lowerCamelCase_							:		Optional[Any]							       =							DinatForImageClassification(__lowercase )
						model.to(__lowercase )
						model.eval()
						lowerCamelCase_							:		int							       =							model(__lowercase			,	labels=__lowercase )
						self.parent.assertEqual(result.logits.shape			,	(self.batch_size, self.num_labels) )

						# test greyscale images
						lowerCamelCase_							:		Dict							       =							1
						lowerCamelCase_							:		Tuple							       =							DinatForImageClassification(__lowercase )
						model.to(__lowercase )
						model.eval()

						lowerCamelCase_							:		str							       =							floats_tensor([self.batch_size, 1, self.image_size, self.image_size] )
						lowerCamelCase_							:		Optional[int]							       =							model(__lowercase )
						self.parent.assertEqual(result.logits.shape			,	(self.batch_size, self.num_labels) )

					def      lowercase_							(    self			,	__lowercase			,	__lowercase			,	__lowercase ):







						'''simple docstring'''




						lowerCamelCase_							:		Optional[Any]							       =							DinatBackbone(config=__lowercase )
						model.to(__lowercase )
						model.eval()
						lowerCamelCase_							:		List[str]							       =							model(__lowercase )

						# verify hidden states
						self.parent.assertEqual(len(result.feature_maps )			,	len(config.out_features ) )
						self.parent.assertListEqual(list(result.feature_maps[0].shape )			,	[self.batch_size, model.channels[0], 16, 16] )

						# verify channels
						self.parent.assertEqual(len(model.channels )			,	len(config.out_features ) )

						# verify backbone works with out_features=None
						lowerCamelCase_							:		List[Any]							       =							None
						lowerCamelCase_							:		Any							       =							DinatBackbone(config=__lowercase )
						model.to(__lowercase )
						model.eval()
						lowerCamelCase_							:		Dict							       =							model(__lowercase )

						# verify feature maps
						self.parent.assertEqual(len(result.feature_maps )			,	1 )
						self.parent.assertListEqual(list(result.feature_maps[0].shape )			,	[self.batch_size, model.channels[-1], 4, 4] )

						# verify channels
						self.parent.assertEqual(len(model.channels )			,	1 )





					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_							:		Optional[Any]							       =							self.prepare_config_and_inputs()
						lowerCamelCase_       ,      lowerCamelCase_       ,      lowerCamelCase_							:		List[str]							       =							config_and_inputs
						lowerCamelCase_							:		int							       =							{'pixel_values': pixel_values}
						return config, inputs_dict


@require_natten
@require_torch
class     __SCREAMING_SNAKE_CASE							(		lowerCamelCase       ,					lowerCamelCase       ,					unittest.TestCase  ):
					_lowerCamelCase		  =			(
					    (
					        DinatModel,
					        DinatForImageClassification,
					        DinatBackbone,
					    )
					    if is_torch_available()
					    else ()
					)
					_lowerCamelCase		  =			(
					    {"""feature-extraction""": DinatModel, """image-classification""": DinatForImageClassification}
					    if is_torch_available()
					    else {}
					)
					_lowerCamelCase		  =			False

					_lowerCamelCase		  =			False
					_lowerCamelCase		  =			False
					_lowerCamelCase		  =			False
					_lowerCamelCase		  =			False

					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_							:		Tuple							       =							DinatModelTester(self )
						lowerCamelCase_							:		List[Any]							       =							ConfigTester(self			,	config_class=__lowercase			,	embed_dim=37 )

					def      lowercase_							(    self ):







						'''simple docstring'''




						self.create_and_test_config_common_properties()
						self.config_tester.create_and_test_config_to_json_string()
						self.config_tester.create_and_test_config_to_json_file()
						self.config_tester.create_and_test_config_from_and_save_pretrained()
						self.config_tester.create_and_test_config_with_num_labels()
						self.config_tester.check_config_can_be_init_without_params()
						self.config_tester.check_config_arguments_init()

					def      lowercase_							(    self ):







						'''simple docstring'''




						return

					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_							:		Tuple							       =							self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_model(*__lowercase )

					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_							:		Optional[Any]							       =							self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_for_image_classification(*__lowercase )

					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_							:		Optional[int]							       =							self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_backbone(*__lowercase )

					@unittest.skip(reason='Dinat does not use inputs_embeds' )
					def      lowercase_							(    self ):







						'''simple docstring'''




						pass

					@unittest.skip(reason='Dinat does not use feedforward chunking' )
					def      lowercase_							(    self ):







						'''simple docstring'''




						pass

					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_       ,      lowerCamelCase_							:		Union[str, Any]							       =							self.model_tester.prepare_config_and_inputs_for_common()

						for model_class in self.all_model_classes:
							lowerCamelCase_							:		Optional[int]							       =							model_class(__lowercase )
							self.assertIsInstance(model.get_input_embeddings()			,	(nn.Module) )
							lowerCamelCase_							:		Optional[Any]							       =							model.get_output_embeddings()
							self.assertTrue(x is None or isinstance(__lowercase			,	nn.Linear ) )

					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_       ,      lowerCamelCase_							:		str							       =							self.model_tester.prepare_config_and_inputs_for_common()

						for model_class in self.all_model_classes:
							lowerCamelCase_							:		Union[str, Any]							       =							model_class(__lowercase )
							lowerCamelCase_							:		List[Any]							       =							inspect.signature(model.forward )
							# signature.parameters is an OrderedDict => so arg_names order is deterministic
							lowerCamelCase_							:		Optional[int]							       =							[*signature.parameters.keys()]

							lowerCamelCase_							:		List[str]							       =							['pixel_values']
							self.assertListEqual(arg_names[:1]			,	__lowercase )

					def      lowercase_							(    self ):







						'''simple docstring'''




						self.skipTest('Dinat\'s attention operation is handled entirely by NATTEN.' )

					def      lowercase_							(    self			,	__lowercase			,	__lowercase			,	__lowercase			,	__lowercase ):







						'''simple docstring'''




						lowerCamelCase_							:		Optional[Any]							       =							model_class(__lowercase )
						model.to(__lowercase )
						model.eval()

						with torch.no_grad():
							lowerCamelCase_							:		Optional[Any]							       =							model(**self._prepare_for_class(__lowercase			,	__lowercase ) )

						lowerCamelCase_							:		Optional[Any]							       =							outputs.hidden_states

						lowerCamelCase_							:		Tuple							       =							getattr(
						    self.model_tester			,	'expected_num_hidden_layers'			,	len(self.model_tester.depths ) + 1 )
						self.assertEqual(len(__lowercase )			,	__lowercase )

						# Dinat has a different seq_length
						lowerCamelCase_							:		List[str]							       =							(
						    config.patch_size
						    if isinstance(config.patch_size			,	collections.abc.Iterable )
						    else (config.patch_size, config.patch_size)
						)

						lowerCamelCase_							:		Tuple							       =							image_size[0] // patch_size[0]
						lowerCamelCase_							:		str							       =							image_size[1] // patch_size[1]

						self.assertListEqual(
						    list(hidden_states[0].shape[-3:] )			,	[height, width, self.model_tester.embed_dim]			,	)

						if model_class.__name__ != "DinatBackbone":
							lowerCamelCase_							:		Optional[int]							       =							outputs.reshaped_hidden_states
							self.assertEqual(len(__lowercase )			,	__lowercase )

							lowerCamelCase_       ,      lowerCamelCase_       ,      lowerCamelCase_       ,      lowerCamelCase_							:		List[Any]							       =							reshaped_hidden_states[0].shape
							lowerCamelCase_							:		Optional[int]							       =							(
							    reshaped_hidden_states[0].view(__lowercase			,	__lowercase			,	__lowercase			,	__lowercase ).permute(0			,	2			,	3			,	1 )
							)
							self.assertListEqual(
							    list(reshaped_hidden_states.shape[-3:] )			,	[height, width, self.model_tester.embed_dim]			,	)

					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_       ,      lowerCamelCase_							:		Optional[Any]							       =							self.model_tester.prepare_config_and_inputs_for_common()

						lowerCamelCase_							:		List[Any]							       =							(
						    self.model_tester.image_size
						    if isinstance(self.model_tester.image_size			,	collections.abc.Iterable )
						    else (self.model_tester.image_size, self.model_tester.image_size)
						)

						for model_class in self.all_model_classes:
							lowerCamelCase_							:		Optional[Any]							       =							True
							self.check_hidden_states_output(__lowercase			,	__lowercase			,	__lowercase			,	__lowercase )

							# check that output_hidden_states also work using config
							del inputs_dict["output_hidden_states"]
							lowerCamelCase_							:		int							       =							True

							self.check_hidden_states_output(__lowercase			,	__lowercase			,	__lowercase			,	__lowercase )

					@slow
					def      lowercase_							(    self ):







						'''simple docstring'''




						for model_name in DINAT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
							lowerCamelCase_							:		Optional[int]							       =							DinatModel.from_pretrained(__lowercase )
							self.assertIsNotNone(__lowercase )





					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_       ,      lowerCamelCase_							:		Dict							       =							self.model_tester.prepare_config_and_inputs_for_common()

						lowerCamelCase_							:		int							       =							_config_zero_init(__lowercase )
						for model_class in self.all_model_classes:
							lowerCamelCase_							:		Union[str, Any]							       =							model_class(config=__lowercase )
							for name, param in model.named_parameters():
								if "embeddings" not in name and param.requires_grad:
									self.assertIn(
									    ((param.data.mean() * 1E9).round() / 1E9).item()			,	[0.0, 1.0]			,	msg=f"Parameter {name} of model {model_class} seems not properly initialized"			,	)


@require_natten
@require_vision
@require_torch
class     __SCREAMING_SNAKE_CASE							(		unittest.TestCase  ):

					@cached_property
					def      lowercase_							(    self ):







						'''simple docstring'''




						return AutoImageProcessor.from_pretrained('shi-labs/dinat-mini-in1k-224' ) if is_vision_available() else None





					@slow
					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_							:		Tuple							       =							DinatForImageClassification.from_pretrained('shi-labs/dinat-mini-in1k-224' ).to(__lowercase )
						lowerCamelCase_							:		Union[str, Any]							       =							self.default_image_processor

						lowerCamelCase_							:		int							       =							Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png' )
						lowerCamelCase_							:		Any							       =							image_processor(images=__lowercase			,	return_tensors='pt' ).to(__lowercase )

						# forward pass
						with torch.no_grad():
							lowerCamelCase_							:		str							       =							model(**__lowercase )

						# verify the logits
						lowerCamelCase_							:		str							       =							torch.Size((1, 1_000) )
						self.assertEqual(outputs.logits.shape			,	__lowercase )
						lowerCamelCase_							:		Tuple							       =							torch.tensor([-0.15_45, -0.76_67, 0.46_42] ).to(__lowercase )
						self.assertTrue(torch.allclose(outputs.logits[0, :3]			,	__lowercase			,	atol=1E-4 ) )


@require_torch
@require_natten
class     __SCREAMING_SNAKE_CASE							(		unittest.TestCase       ,					lowerCamelCase  ):
					_lowerCamelCase		  =			(DinatBackbone,) if is_torch_available() else ()
					_lowerCamelCase		  =			DinatConfig

					def      lowercase_							(    self ):







						'''simple docstring'''




						lowerCamelCase_							:		List[Any]							       =							DinatModelTester(self )






from __future__ import annotations






def  snake_case (							A						,       A      )							->							Union[str, Any]:




	'''simple docstring'''


	lowerCamelCase_							:		Tuple							       =							0
	lowerCamelCase_							:		str							       =							len(A      ) - 1
	while left <= right:
		lowerCamelCase_							:		str							       =							(left + right) // 2
		if left == right:
			if sorted_list[middle] < item:
				lowerCamelCase_							:		List[Any]							       =							middle + 1
			break
		elif sorted_list[middle] < item:
			lowerCamelCase_							:		Any							       =							middle + 1
		else:
			lowerCamelCase_							:		Optional[int]							       =							middle - 1
	sorted_list.insert(A						,       A      )
	return sorted_list






def  snake_case (							A						,       A      )							->							Union[str, Any]:




	'''simple docstring'''


	lowerCamelCase_							:		List[Any]							       =							[]
	while left and right:
		if left[0][0] < right[0][0]:
			result.append(left.pop(0      )      )
		else:
			result.append(right.pop(0      )      )
	return result + left + right






def  snake_case (							A      )							->							Any:




	'''simple docstring'''


	lowerCamelCase_							:		List[Any]							       =							len(A      )
	if length <= 1:
		return list_ad
	lowerCamelCase_							:		Any							       =							length // 2
	return merge(sortlist_ad(list_ad[:middle]      )						,       sortlist_ad(list_ad[middle:]      )      )






def  snake_case (							A      )							->							list[int]:




	'''simple docstring'''


	if len(A      ) <= 1:
		return collection
	lowerCamelCase_							:		Tuple							       =							[]
	lowerCamelCase_							:		int							       =							False
	for i in range(0						,       len(A      )						,       2      ):
		if i == len(A      ) - 1:
			lowerCamelCase_							:		Any							       =							True
		else:
			if collection[i] < collection[i + 1]:
				two_paired_list.append([collection[i], collection[i + 1]]      )
			else:
				two_paired_list.append([collection[i + 1], collection[i]]      )
	lowerCamelCase_							:		Union[str, Any]							       =							sortlist_ad(A      )
	lowerCamelCase_							:		int							       =							[i[0] for i in sorted_list_ad]
	result.append(sorted_list_ad[-1][1]      )
	if has_last_odd_item:
		lowerCamelCase_							:		List[str]							       =							collection[-1]
		lowerCamelCase_							:		Optional[Any]							       =							binary_search_insertion(A						,       A      )
	lowerCamelCase_							:		Optional[Any]							       =							False
	for i in range(len(A      ) - 1      ):
		if result[i] == collection[-1] and has_last_odd_item:
			lowerCamelCase_							:		Optional[Any]							       =							True
		lowerCamelCase_							:		Dict							       =							sorted_list_ad[i][1]
		# If last_odd_item is inserted before the item's index,
		# you should forward index one more.
		if is_last_odd_item_inserted_before_this_index:
			lowerCamelCase_							:		Dict							       =							result[: i + 2] + binary_search_insertion(result[i + 2 :]						,       A      )
		else:
			lowerCamelCase_							:		str							       =							result[: i + 1] + binary_search_insertion(result[i + 1 :]						,       A      )

	return result


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