'''simple docstring'''




import collections
import inspect
import unittest

from transformers import FocalNetConfig
from transformers.testing_utils import 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 (
						    FocalNetBackbone,
						    FocalNetForImageClassification,
						    FocalNetForMaskedImageModeling,
						    FocalNetModel,
						)
						from transformers.models.focalnet.modeling_focalnet import FOCALNET_PRETRAINED_MODEL_ARCHIVE_LIST

if is_vision_available():
						from PIL import Image

						from transformers import AutoImageProcessor





class     __magic_name__						:







			def __init__(	self				:  Optional[Any]				,			lowercase_				:  Tuple				,			lowercase_				:  List[Any]=13				,			lowercase_				:  Tuple=32				,			lowercase_				:  Dict=2				,			lowercase_				:  Optional[int]=3				,			lowercase_				:  Tuple=16				,			lowercase_				:  Tuple=[32, 64, 128]				,			lowercase_				:  List[Any]=[1, 2, 1]				,			lowercase_				:  int=[2, 2, 4]				,			lowercase_				:  Optional[int]=2				,			lowercase_				:  Dict=2.0				,			lowercase_				:  Union[str, Any]=True				,			lowercase_				:  List[Any]=0.0				,			lowercase_				:  Union[str, Any]=0.0				,			lowercase_				:  Any=0.1				,			lowercase_				:  int="gelu"				,			lowercase_				:  Union[str, Any]=False				,			lowercase_				:  Optional[int]=True				,			lowercase_				:  List[str]=0.02				,			lowercase_				:  List[str]=1E-5				,			lowercase_				:  List[Any]=True				,			lowercase_				:  Tuple=None				,			lowercase_				:  Union[str, Any]=True				,			lowercase_				:  Dict=10				,			lowercase_				:  str=8				,			lowercase_				:  List[Any]=["stage1", "stage2"]				,			lowercase_				:  Tuple=[1, 2]				,			):
										lowercase_					:			Dict										=       parent
										lowercase_					:			Optional[Any]										=       batch_size
										lowercase_					:			Any										=       image_size
										lowercase_					:			Dict										=       patch_size
										lowercase_					:			List[str]										=       num_channels
										lowercase_					:			List[Any]										=       embed_dim
										lowercase_					:			Optional[Any]										=       hidden_sizes
										lowercase_					:			Tuple										=       depths
										lowercase_					:			Union[str, Any]										=       num_heads
										lowercase_					:			Optional[int]										=       window_size
										lowercase_					:			Tuple										=       mlp_ratio
										lowercase_					:			Tuple										=       qkv_bias
										lowercase_					:			Tuple										=       hidden_dropout_prob
										lowercase_					:			List[Any]										=       attention_probs_dropout_prob
										lowercase_					:			List[Any]										=       drop_path_rate
										lowercase_					:			Tuple										=       hidden_act
										lowercase_					:			int										=       use_absolute_embeddings
										lowercase_					:			Union[str, Any]										=       patch_norm
										lowercase_					:			Any										=       layer_norm_eps
										lowercase_					:			Any										=       initializer_range
										lowercase_					:			Optional[int]										=       is_training
										lowercase_					:			str										=       scope
										lowercase_					:			List[Any]										=       use_labels
										lowercase_					:			Optional[int]										=       type_sequence_label_size
										lowercase_					:			Optional[int]										=       encoder_stride
										lowercase_					:			List[str]										=       out_features
										lowercase_					:			str										=       out_indices







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Tuple    ):
										lowercase_					:			Optional[Any]										=       floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]    )

										lowercase_					:			Union[str, Any]										=       None
										if self.use_labels:
																	lowercase_					:			Optional[Any]										=       ids_tensor([self.batch_size]				,			self.type_sequence_label_size    )

										lowercase_					:			Any										=       self.get_config()

										return config, pixel_values, labels







			def 	SCREAMING_SNAKE_CASE_     (	self				:  List[Any]    ):
										return FocalNetConfig(
										    image_size=self.image_size				,			patch_size=self.patch_size				,			num_channels=self.num_channels				,			embed_dim=self.embed_dim				,			hidden_sizes=self.hidden_sizes				,			depths=self.depths				,			num_heads=self.num_heads				,			window_size=self.window_size				,			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				,			use_absolute_embeddings=self.use_absolute_embeddings				,			path_norm=self.patch_norm				,			layer_norm_eps=self.layer_norm_eps				,			initializer_range=self.initializer_range				,			encoder_stride=self.encoder_stride				,			out_features=self.out_features				,			out_indices=self.out_indices				,			)







			def 	SCREAMING_SNAKE_CASE_     (	self				:  int				,			lowercase_				:  str				,			lowercase_				:  Optional[int]				,			lowercase_				:  int    ):
										lowercase_					:			List[Any]										=       FocalNetModel(config=lowercase_    )
										model.to(lowercase_    )
										model.eval()
										lowercase_					:			Optional[int]										=       model(lowercase_    )

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

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







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Union[str, Any]				,			lowercase_				:  List[str]				,			lowercase_				:  Optional[Any]				,			lowercase_				:  int    ):
										lowercase_					:			Union[str, Any]										=       FocalNetBackbone(config=lowercase_    )
										model.to(lowercase_    )
										model.eval()
										lowercase_					:			Any										=       model(lowercase_    )

										# verify feature maps
										self.parent.assertEqual(len(result.feature_maps    )				,			len(config.out_features    )    )
										self.parent.assertListEqual(list(result.feature_maps[0].shape    )				,			[self.batch_size, self.image_size, 8, 8]    )

										# verify channels
										self.parent.assertEqual(len(model.channels    )				,			len(config.out_features    )    )
										self.parent.assertListEqual(model.channels				,			config.hidden_sizes[:-1]    )

										# verify backbone works with out_features=None
										lowercase_					:			int										=       None
										lowercase_					:			Optional[int]										=       FocalNetBackbone(config=lowercase_    )
										model.to(lowercase_    )
										model.eval()
										lowercase_					:			List[str]										=       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, self.image_size * 2, 4, 4]    )

										# verify channels
										self.parent.assertEqual(len(model.channels    )				,			1    )
										self.parent.assertListEqual(model.channels				,			[config.hidden_sizes[-1]]    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  str				,			lowercase_				:  List[Any]				,			lowercase_				:  List[str]				,			lowercase_				:  Any    ):
										lowercase_					:			str										=       FocalNetForMaskedImageModeling(config=lowercase_    )
										model.to(lowercase_    )
										model.eval()
										lowercase_					:			Union[str, Any]										=       model(lowercase_    )
										self.parent.assertEqual(
										    result.reconstruction.shape				,			(self.batch_size, self.num_channels, self.image_size, self.image_size)    )

										# test greyscale images
										lowercase_					:			str										=       1
										lowercase_					:			str										=       FocalNetForMaskedImageModeling(lowercase_    )
										model.to(lowercase_    )
										model.eval()

										lowercase_					:			Dict										=       floats_tensor([self.batch_size, 1, self.image_size, self.image_size]    )
										lowercase_					:			str										=       model(lowercase_    )
										self.parent.assertEqual(result.reconstruction.shape				,			(self.batch_size, 1, self.image_size, self.image_size)    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  int				,			lowercase_				:  List[Any]				,			lowercase_				:  Optional[int]				,			lowercase_				:  Union[str, Any]    ):
										lowercase_					:			Any										=       self.type_sequence_label_size
										lowercase_					:			int										=       FocalNetForImageClassification(lowercase_    )
										model.to(lowercase_    )
										model.eval()
										lowercase_					:			str										=       model(lowercase_				,			labels=lowercase_    )
										self.parent.assertEqual(result.logits.shape				,			(self.batch_size, self.type_sequence_label_size)    )

										# test greyscale images
										lowercase_					:			Optional[Any]										=       1
										lowercase_					:			Any										=       FocalNetForImageClassification(lowercase_    )
										model.to(lowercase_    )
										model.eval()

										lowercase_					:			Dict										=       floats_tensor([self.batch_size, 1, self.image_size, self.image_size]    )
										lowercase_					:			List[str]										=       model(lowercase_    )
										self.parent.assertEqual(result.logits.shape				,			(self.batch_size, self.type_sequence_label_size)    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Any    ):
										lowercase_					:			List[Any]										=       self.prepare_config_and_inputs()

										lowercase_						,						lowercase_						,						lowercase_					:			Union[str, Any]										=       config_and_inputs
										lowercase_					:			List[str]										=       {"""pixel_values""": pixel_values}
										return config, inputs_dict





@require_torch
class     __magic_name__						(    _UpperCAmelCase,     _UpperCAmelCase,     unittest.TestCase):
			UpperCamelCase__				=       (
			    (
			        FocalNetModel,
			        FocalNetForImageClassification,
			        FocalNetForMaskedImageModeling,
			        FocalNetBackbone,
			    )
			    if is_torch_available()
			    else ()
			)
			UpperCamelCase__				=       (
			    {'''feature-extraction''': FocalNetModel, '''image-classification''': FocalNetForImageClassification}
			    if is_torch_available()
			    else {}
			)
			UpperCamelCase__				=       False

			UpperCamelCase__				=       False
			UpperCamelCase__				=       False
			UpperCamelCase__				=       False
			UpperCamelCase__				=       False







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Dict    ):
										lowercase_					:			Optional[Any]										=       FocalNetModelTester(self    )
										lowercase_					:			Dict										=       ConfigTester(self				,			config_class=lowercase_				,			embed_dim=37				,			has_text_modality=lowercase_    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Any    ):
										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 	SCREAMING_SNAKE_CASE_     (	self				:  List[str]    ):
										return







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Dict    ):
										lowercase_					:			List[Any]										=       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_model(*lowercase_    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Any    ):
										lowercase_					:			Tuple										=       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_backbone(*lowercase_    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Dict    ):
										lowercase_					:			str										=       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_for_masked_image_modeling(*lowercase_    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Any    ):
										lowercase_					:			Tuple										=       self.model_tester.prepare_config_and_inputs()
										self.model_tester.create_and_check_for_image_classification(*lowercase_    )







			@unittest.skip(reason="""FocalNet does not use inputs_embeds"""    )
			def 	SCREAMING_SNAKE_CASE_     (	self				:  Any    ):
										pass







			@unittest.skip(reason="""FocalNet does not use feedforward chunking"""    )
			def 	SCREAMING_SNAKE_CASE_     (	self				:  Any    ):
										pass







			def 	SCREAMING_SNAKE_CASE_     (	self				:  List[Any]    ):
										lowercase_						,						lowercase_					:			List[str]										=       self.model_tester.prepare_config_and_inputs_for_common()

										for model_class in self.all_model_classes[:-1]:
																	lowercase_					:			List[Any]										=       model_class(lowercase_    )
																	self.assertIsInstance(model.get_input_embeddings()				,			(nn.Module)    )
																	lowercase_					:			Union[str, Any]										=       model.get_output_embeddings()
																	self.assertTrue(x is None or isinstance(lowercase_				,			nn.Linear    )    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Optional[Any]    ):
										lowercase_						,						lowercase_					:			Dict										=       self.model_tester.prepare_config_and_inputs_for_common()

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

																	lowercase_					:			Any										=       ["""pixel_values"""]
																	self.assertListEqual(arg_names[:1]				,			lowercase_    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Dict				,			lowercase_				:  Any				,			lowercase_				:  Union[str, Any]				,			lowercase_				:  str				,			lowercase_				:  List[str]    ):
										lowercase_					:			Optional[Any]										=       model_class(lowercase_    )
										model.to(lowercase_    )
										model.eval()

										with torch.no_grad():
																	lowercase_					:			Union[str, Any]										=       model(**self._prepare_for_class(lowercase_				,			lowercase_    )    )

										lowercase_					:			int										=       outputs.hidden_states

										lowercase_					:			Optional[int]										=       getattr(
										    self.model_tester				,			"""expected_num_hidden_layers"""				,			len(self.model_tester.depths    ) + 1    )
										self.assertEqual(len(lowercase_    )				,			lowercase_    )

										# FocalNet has a different seq_length
										lowercase_					:			Any										=       (
										    config.patch_size
										    if isinstance(config.patch_size				,			collections.abc.Iterable    )
										    else (config.patch_size, config.patch_size)
										)

										lowercase_					:			int										=       (image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])

										self.assertListEqual(
										    list(hidden_states[0].shape[-2:]    )				,			[num_patches, self.model_tester.embed_dim]				,			)

										lowercase_					:			Optional[Any]										=       outputs.reshaped_hidden_states
										self.assertEqual(len(lowercase_    )				,			lowercase_    )

										lowercase_						,						lowercase_						,						lowercase_						,						lowercase_					:			Any										=       reshaped_hidden_states[0].shape
										lowercase_					:			Union[str, Any]										=       (
										    reshaped_hidden_states[0].view(lowercase_				,			lowercase_				,			height * width    ).permute(0				,			2				,			1    )
										)
										self.assertListEqual(
										    list(reshaped_hidden_states.shape[-2:]    )				,			[num_patches, self.model_tester.embed_dim]				,			)







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Optional[int]    ):
										lowercase_						,						lowercase_					:			Optional[Any]										=       self.model_tester.prepare_config_and_inputs_for_common()

										lowercase_					:			Optional[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[:-1]:
																	lowercase_					:			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"]
																	lowercase_					:			Any										=       True

																	self.check_hidden_states_output(lowercase_				,			lowercase_				,			lowercase_				,			lowercase_    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Optional[Any]    ):
										lowercase_						,						lowercase_					:			Dict										=       self.model_tester.prepare_config_and_inputs_for_common()
										lowercase_					:			Any										=       3

										lowercase_					:			List[str]										=       (
										    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)
										)
										lowercase_					:			List[str]										=       (
										    config.patch_size
										    if isinstance(config.patch_size				,			collections.abc.Iterable    )
										    else (config.patch_size, config.patch_size)
										)

										lowercase_					:			Tuple										=       image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
										lowercase_					:			Optional[int]										=       image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

										for model_class in self.all_model_classes[:-1]:
																	lowercase_					:			Dict										=       True
																	self.check_hidden_states_output(lowercase_				,			lowercase_				,			lowercase_				,			(padded_height, padded_width)    )

																	# check that output_hidden_states also work using config
																	del inputs_dict["output_hidden_states"]
																	lowercase_					:			Optional[Any]										=       True
																	self.check_hidden_states_output(lowercase_				,			lowercase_				,			lowercase_				,			(padded_height, padded_width)    )







			@slow
			def 	SCREAMING_SNAKE_CASE_     (	self				:  int    ):
										for model_name in FOCALNET_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																	lowercase_					:			Dict										=       FocalNetModel.from_pretrained(lowercase_    )
																	self.assertIsNotNone(lowercase_    )







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Union[str, Any]    ):
										lowercase_						,						lowercase_					:			Tuple										=       self.model_tester.prepare_config_and_inputs_for_common()

										lowercase_					:			Optional[int]										=       _config_zero_init(lowercase_    )
										for model_class in self.all_model_classes:
																	lowercase_					:			Optional[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_vision
@require_torch
class     __magic_name__						(    unittest.TestCase):







			@cached_property
			def 	SCREAMING_SNAKE_CASE_     (	self				:  List[str]    ):
										# TODO update organization
										return AutoImageProcessor.from_pretrained("""microsoft/focalnet-tiny"""    ) if is_vision_available() else None







			@slow
			def 	SCREAMING_SNAKE_CASE_     (	self				:  List[str]    ):
										lowercase_					:			Union[str, Any]										=       FocalNetForImageClassification.from_pretrained("""microsoft/focalnet-tiny"""    ).to(lowercase_    )
										lowercase_					:			Union[str, Any]										=       self.default_image_processor

										lowercase_					:			List[str]										=       Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""    )
										lowercase_					:			Any										=       image_processor(images=lowercase_				,			return_tensors="""pt"""    ).to(lowercase_    )

										# forward pass
										with torch.no_grad():
																	lowercase_					:			int										=       model(**lowercase_    )

										# verify the logits
										lowercase_					:			str										=       torch.Size((1, 1000)    )
										self.assertEqual(outputs.logits.shape				,			lowercase_    )
										lowercase_					:			Union[str, Any]										=       torch.tensor([0.21_66, -0.43_68, 0.21_91]    ).to(lowercase_    )
										self.assertTrue(torch.allclose(outputs.logits[0, :3]				,			lowercase_				,			atol=1E-4    )    )
										self.assertTrue(outputs.logits.argmax(dim=-1    ).item()				,			281    )





@require_torch
class     __magic_name__						(    _UpperCAmelCase,     unittest.TestCase):
			UpperCamelCase__				=       (FocalNetBackbone,) if is_torch_available() else ()
			UpperCamelCase__				=       FocalNetConfig

			UpperCamelCase__				=       False







			def 	SCREAMING_SNAKE_CASE_     (	self				:  Optional[int]    ):
										lowercase_					:			Tuple										=       FocalNetModelTester(self    )






'''simple docstring'''




def 							lowerCamelCase	(      UpperCAmelCase__       :					list )			->      list:
							if any(not isinstance(UpperCAmelCase__      ,      UpperCAmelCase__ ) or x < 0 for x in sequence ):
														raise TypeError("""Sequence must be list of non-negative integers""" )
							for _ in range(len(UpperCAmelCase__ ) ):
														for i, (rod_upper, rod_lower) in enumerate(zip(UpperCAmelCase__      ,      sequence[1:] ) ):
																					if rod_upper > rod_lower:
																												sequence[i] -= rod_upper - rod_lower
																												sequence[i + 1] += rod_upper - rod_lower
							return sequence


if __name__ == "__main__":
						assert bead_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
						assert bead_sort([7, 9, 4, 3, 5]) == [3, 4, 5, 7, 9]





