



"""simple docstring"""







import collections
import inspect
import unittest

from transformers import DonutSwinConfig
from transformers.testing_utils import require_torch, slow, torch_device
from transformers.utils import is_torch_available

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 DonutSwinModel
							from transformers.models.donut.modeling_donut_swin import DONUT_SWIN_PRETRAINED_MODEL_ARCHIVE_LIST






class   UpperCAmelCase__		:



		def __init__(			self	:     List[Any]   ,				snake_case	:     Optional[Any]   ,				snake_case	:     int=13   ,				snake_case	:     Any=32   ,				snake_case	:     Union[str, Any]=2   ,				snake_case	:     List[Any]=3   ,				snake_case	:     Optional[int]=16   ,				snake_case	:     List[Any]=[1, 2, 1]   ,				snake_case	:     Dict=[2, 2, 4]   ,				snake_case	:     Dict=2   ,				snake_case	:     int=2.0   ,				snake_case	:     str=True   ,				snake_case	:     Optional[Any]=0.0   ,				snake_case	:     str=0.0   ,				snake_case	:     List[str]=0.1   ,				snake_case	:     int="gelu"   ,				snake_case	:     List[Any]=False   ,				snake_case	:     Optional[int]=True   ,				snake_case	:     Optional[Any]=0.02   ,				snake_case	:     Tuple=1E-5   ,				snake_case	:     Union[str, Any]=True   ,				snake_case	:     Optional[Any]=None   ,				snake_case	:     Optional[Any]=True   ,				snake_case	:     Tuple=10   ,				snake_case	:     Optional[Any]=8   ,				)      ->    Any:






									'''simple docstring'''

									A    =       parent
									A    =       batch_size
									A    =       image_size
									A    =       patch_size
									A    =       num_channels
									A    =       embed_dim
									A    =       depths
									A    =       num_heads
									A    =       window_size
									A    =       mlp_ratio
									A    =       qkv_bias
									A    =       hidden_dropout_prob
									A    =       attention_probs_dropout_prob
									A    =       drop_path_rate
									A    =       hidden_act
									A    =       use_absolute_embeddings
									A    =       patch_norm
									A    =       layer_norm_eps
									A    =       initializer_range
									A    =       is_training
									A    =       scope
									A    =       use_labels
									A    =       type_sequence_label_size
									A    =       encoder_stride



		def        A_		(			self	:     Optional[Any]					)      ->    Dict:






									'''simple docstring'''

									A    =       floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]					)

									A    =       None
									if self.use_labels:
																A    =       ids_tensor([self.batch_size]   ,				self.type_sequence_label_size					)

									A    =       self.get_config()

									return config, pixel_values, labels



		def        A_		(			self	:     Any					)      ->    Any:






									'''simple docstring'''

									return DonutSwinConfig(
									    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   ,				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   ,				)



		def        A_		(			self	:     int   ,				snake_case	:     Union[str, Any]   ,				snake_case	:     Union[str, Any]   ,				snake_case	:     Union[str, Any]					)      ->    List[str]:






									'''simple docstring'''

									A    =       DonutSwinModel(config=snake_case					)
									model.to(snake_case					)
									model.eval()
									A    =       model(snake_case					)

									A    =       ((config.image_size // config.patch_size) ** 2) // (4 ** (len(config.depths					) - 1))
									A    =       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        A_		(			self	:     Optional[int]					)      ->    Union[str, Any]:






									'''simple docstring'''

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






@require_torch
class   UpperCAmelCase__		(   UpperCamelCase ,UpperCamelCase ,unittest.TestCase  ):
		lowerCAmelCase_							:						Any							=  (DonutSwinModel,) if is_torch_available() else ()
		lowerCAmelCase_							:						Dict							=  {"""feature-extraction""": DonutSwinModel} if is_torch_available() else {}
		lowerCAmelCase_							:						List[Any]							=  True

		lowerCAmelCase_							:						Dict							=  False
		lowerCAmelCase_							:						str							=  False
		lowerCAmelCase_							:						Any							=  False



		def        A_		(			self	:     Optional[int]					)      ->    Tuple:






									'''simple docstring'''

									A    =       DonutSwinModelTester(self					)
									A    =       ConfigTester(self   ,				config_class=snake_case   ,				embed_dim=37					)



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






									'''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        A_		(			self	:     int					)      ->    int:






									'''simple docstring'''

									return



		def        A_		(			self	:     int					)      ->    str:






									'''simple docstring'''

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



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






									'''simple docstring'''

									pass



		def        A_		(			self	:     Dict					)      ->    int:






									'''simple docstring'''

									A   ,	A    =       self.model_tester.prepare_config_and_inputs_for_common()

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



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






									'''simple docstring'''

									A   ,	A    =       self.model_tester.prepare_config_and_inputs_for_common()

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

																A    =       ['pixel_values']
																self.assertListEqual(arg_names[:1]   ,				snake_case					)



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






									'''simple docstring'''

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

									for model_class in self.all_model_classes:
																A    =       True
																A    =       False
																A    =       True
																A    =       model_class(snake_case					)
																model.to(snake_case					)
																model.eval()
																with torch.no_grad():
																							A    =       model(**self._prepare_for_class(snake_case   ,				snake_case					)					)
																A    =       outputs.attentions
																A    =       len(self.model_tester.depths					)
																self.assertEqual(len(snake_case					)   ,				snake_case					)

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

																self.assertListEqual(
																    list(attentions[0].shape[-3:]					)   ,				[self.model_tester.num_heads[0], window_size_squared, window_size_squared]   ,				)
																A    =       len(snake_case					)

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

																if hasattr(self.model_tester   ,				'num_hidden_states_types'					):
																							A    =       self.model_tester.num_hidden_states_types
																else:
																							# also another +1 for reshaped_hidden_states
																							A    =       2
																self.assertEqual(out_len + added_hidden_states   ,				len(snake_case					)					)

																A    =       outputs.attentions

																self.assertEqual(len(snake_case					)   ,				snake_case					)

																self.assertListEqual(
																    list(self_attentions[0].shape[-3:]					)   ,				[self.model_tester.num_heads[0], window_size_squared, window_size_squared]   ,				)



		def        A_		(			self	:     Tuple   ,				snake_case	:     str   ,				snake_case	:     List[str]   ,				snake_case	:     List[Any]   ,				snake_case	:     List[Any]					)      ->    int:






									'''simple docstring'''

									A    =       model_class(snake_case					)
									model.to(snake_case					)
									model.eval()

									with torch.no_grad():
																A    =       model(**self._prepare_for_class(snake_case   ,				snake_case					)					)

									A    =       outputs.hidden_states

									A    =       getattr(
									    self.model_tester   ,				'expected_num_hidden_layers'   ,				len(self.model_tester.depths					) + 1					)
									self.assertEqual(len(snake_case					)   ,				snake_case					)

									# DonutSwin has a different seq_length
									A    =       (
									    config.patch_size
									    if isinstance(config.patch_size   ,				collections.abc.Iterable					)
									    else (config.patch_size, config.patch_size)
									)

									A    =       (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]   ,				)

									A    =       outputs.reshaped_hidden_states
									self.assertEqual(len(snake_case					)   ,				snake_case					)

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



		def        A_		(			self	:     List[str]					)      ->    Optional[int]:






									'''simple docstring'''

									A   ,	A    =       self.model_tester.prepare_config_and_inputs_for_common()

									A    =       (
									    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:
																A    =       True
																self.check_hidden_states_output(snake_case   ,				snake_case   ,				snake_case   ,				snake_case					)

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

																self.check_hidden_states_output(snake_case   ,				snake_case   ,				snake_case   ,				snake_case					)



		def        A_		(			self	:     Dict					)      ->    Any:






									'''simple docstring'''

									A   ,	A    =       self.model_tester.prepare_config_and_inputs_for_common()
									A    =       3

									A    =       (
									    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)
									)
									A    =       (
									    config.patch_size
									    if isinstance(config.patch_size   ,				collections.abc.Iterable					)
									    else (config.patch_size, config.patch_size)
									)

									A    =       image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
									A    =       image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

									for model_class in self.all_model_classes:
																A    =       True
																self.check_hidden_states_output(snake_case   ,				snake_case   ,				snake_case   ,				(padded_height, padded_width)					)

																# check that output_hidden_states also work using config
																del inputs_dict["output_hidden_states"]
																A    =       True
																self.check_hidden_states_output(snake_case   ,				snake_case   ,				snake_case   ,				(padded_height, padded_width)					)



		@slow
		def        A_		(			self	:     List[Any]					)      ->    List[Any]:






									'''simple docstring'''

									for model_name in DONUT_SWIN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																A    =       DonutSwinModel.from_pretrained(snake_case					)
																self.assertIsNotNone(snake_case					)



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






									'''simple docstring'''

									A   ,	A    =       self.model_tester.prepare_config_and_inputs_for_common()

									A    =       _config_zero_init(snake_case					)
									for model_class in self.all_model_classes:
																A    =       model_class(config=snake_case					)
																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"""   ,				)








"""simple docstring"""







def 	lowerCAmelCase__      (  lowerCamelCase__      )			->				List[str]:
							A    =       [701, 301, 132, 57, 23, 10, 4, 1]
							for gap in gaps:
														for i in range(lowerCamelCase__					,   len(lowerCamelCase__      )      ):
																					A    =       collection[i]
																					A    =       i
																					while j >= gap and collection[j - gap] > insert_value:
																												A    =       collection[j - gap]
																												j -= gap
																					if j != i:
																												A    =       insert_value
							return collection


if __name__ == "__main__":
							from doctest import testmod

							testmod()
							A     =      input('Enter numbers separated by a comma:\n').strip()
							A     =      [int(item) for item in user_input.split(',')]
							print(shell_sort(unsorted))



