


def a_		(       UpperCamelCase_   :							Optional[Any]   ,					UpperCamelCase_   :							Any   ,					UpperCamelCase_   :							Tuple   ,					UpperCamelCase_   :							int  )							->   Dict:







 """simple docstring"""

 if start == end:
  return start if lst[start] > item else start + 1
 if start > end:
  return start

 lowerCamelCase      						=    (start + end) // 2
 if lst[mid] < item:
  return binary_search(UpperCamelCase_   ,					UpperCamelCase_   ,					mid + 1   ,					UpperCamelCase_  )
 elif lst[mid] > item:
  return binary_search(UpperCamelCase_   ,					UpperCamelCase_   ,					UpperCamelCase_   ,					mid - 1  )
 else:
  return mid







def a_		(       UpperCamelCase_   :							int  )							->   Dict:







 """simple docstring"""

 lowerCamelCase      						=    len(UpperCamelCase_  )

 for index in range(1   ,					UpperCamelCase_  ):
  lowerCamelCase      						=    lst[index]
  lowerCamelCase      						=    binary_search(UpperCamelCase_   ,					UpperCamelCase_   ,					0   ,					index - 1  )
  lowerCamelCase      						=    lst[:pos] + [value] + lst[pos:index] + lst[index + 1 :]

 return lst







def a_		(       UpperCamelCase_   :							Optional[int]   ,					UpperCamelCase_   :							Optional[Any]  )							->   Any:







 """simple docstring"""

 if not left:
  return right

 if not right:
  return left

 if left[0] < right[0]:
  return [left[0], *merge(left[1:]   ,					UpperCamelCase_  )]

 return [right[0], *merge(UpperCamelCase_   ,					right[1:]  )]







def a_		(       UpperCamelCase_   :							Union[str, Any]  )							->   int:







 """simple docstring"""

 lowerCamelCase      						=    len(UpperCamelCase_  )
 lowerCamelCase						,	lowerCamelCase      						=    [], []
 lowerCamelCase      						=    [lst[0]]
 lowerCamelCase      						=    []
 lowerCamelCase      						=    1
 while i < length:
  if lst[i] < lst[i - 1]:
   runs.append(UpperCamelCase_  )
   lowerCamelCase      						=    [lst[i]]
  else:
   new_run.append(lst[i]  )
  i += 1
 runs.append(UpperCamelCase_  )

 for run in runs:
  sorted_runs.append(insertion_sort(UpperCamelCase_  )  )
 for run in sorted_runs:
  lowerCamelCase      						=    merge(UpperCamelCase_   ,					UpperCamelCase_  )

 return sorted_array







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







 """simple docstring"""

 lowerCamelCase      						=    [5, 9, 1_0, 3, -4, 5, 1_7_8, 9_2, 4_6, -1_8, 0, 7]
 lowerCamelCase      						=    tim_sort(UpperCamelCase_  )
 print(UpperCamelCase_  )


if __name__ == "__main__":
     main()







import inspect
import unittest

from transformers import SwinaSRConfig
from transformers.testing_utils import require_torch, require_vision, slow, torch_device
from transformers.utils import is_torch_available, is_vision_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 SwinaSRForImageSuperResolution, SwinaSRModel
     from transformers.models.swinasr.modeling_swinasr import SWIN2SR_PRETRAINED_MODEL_ARCHIVE_LIST

if is_vision_available():
     from PIL import Image

     from transformers import SwinaSRImageProcessor


class     lowerCAmelCase				:


       '''simple docstring'''







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







        '''simple docstring'''

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

        # here we set some attributes to make tests pass
        lowerCamelCase      						=    len(__snake_case     )
        lowerCamelCase      						=    embed_dim
        lowerCamelCase      						=    (image_size // patch_size) ** 2

       def   lowerCamelCase__						(	self					:  List[Any]     )   -> Optional[Any]:







        '''simple docstring'''

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

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

        lowerCamelCase      						=    self.get_config()

        return config, pixel_values, labels

       def   lowerCamelCase__						(	self					:  Optional[Any]     )   -> str:







        '''simple docstring'''

        return SwinaSRConfig(
            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						,	upscale=self.upscale						,	)

       def   lowerCamelCase__						(	self					:  List[Any]						,	__snake_case					:  Any						,	__snake_case					:  Union[str, Any]						,	__snake_case					:  Optional[Any]     )   -> str:







        '''simple docstring'''

        lowerCamelCase      						=    SwinaSRModel(config=__snake_case     )
        model.to(__snake_case     )
        model.eval()
        lowerCamelCase      						=    model(__snake_case     )

        self.parent.assertEqual(
            result.last_hidden_state.shape						,	(self.batch_size, self.embed_dim, self.image_size, self.image_size)     )

       def   lowerCamelCase__						(	self					:  Tuple						,	__snake_case					:  str						,	__snake_case					:  Optional[int]						,	__snake_case					:  Dict     )   -> str:







        '''simple docstring'''

        lowerCamelCase      						=    SwinaSRForImageSuperResolution(__snake_case     )
        model.to(__snake_case     )
        model.eval()
        lowerCamelCase      						=    model(__snake_case     )

        lowerCamelCase      						=    self.image_size * self.upscale
        self.parent.assertEqual(
            result.reconstruction.shape						,	(self.batch_size, self.num_channels, expected_image_size, expected_image_size)     )





       def   lowerCamelCase__						(	self					:  str     )   -> Any:







        '''simple docstring'''

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


@require_torch
class     lowerCAmelCase				(    __UpperCamelCase   ,				__UpperCamelCase   ,				unittest.TestCase				):


       '''simple docstring'''







       snake_case    							=	(SwinaSRModel, SwinaSRForImageSuperResolution) if is_torch_available() else ()
       snake_case    							=	{'feature-extraction': SwinaSRModel} if is_torch_available() else {}

       snake_case    							=	False
       snake_case    							=	False
       snake_case    							=	False
       snake_case    							=	False
       snake_case    							=	False

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







        '''simple docstring'''

        lowerCamelCase      						=    SwinaSRModelTester(self     )
        lowerCamelCase      						=    ConfigTester(self						,	config_class=__snake_case						,	embed_dim=37     )

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







        '''simple docstring'''

        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   lowerCamelCase__						(	self					:  Optional[int]     )   -> List[Any]:







        '''simple docstring'''

        lowerCamelCase      						=    self.model_tester.prepare_config_and_inputs()
        self.model_tester.create_and_check_model(*__snake_case     )

       def   lowerCamelCase__						(	self					:  int     )   -> Tuple:







        '''simple docstring'''

        lowerCamelCase      						=    self.model_tester.prepare_config_and_inputs()
        self.model_tester.create_and_check_for_image_super_resolution(*__snake_case     )

       @unittest.skip(reason='Got `CUDA error: misaligned address` with PyTorch 2.0.0.'     )
       def   lowerCamelCase__						(	self					:  List[Any]     )   -> Optional[Any]:







        '''simple docstring'''

        pass

       @unittest.skip(reason='Swin2SR does not use inputs_embeds'     )
       def   lowerCamelCase__						(	self					:  str     )   -> Optional[int]:







        '''simple docstring'''

        pass

       @unittest.skip(reason='Swin2SR does not support training yet'     )
       def   lowerCamelCase__						(	self					:  Dict     )   -> Dict:







        '''simple docstring'''

        pass

       @unittest.skip(reason='Swin2SR does not support training yet'     )
       def   lowerCamelCase__						(	self					:  List[Any]     )   -> int:







        '''simple docstring'''

        pass

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







        '''simple docstring'''

        lowerCamelCase						,	lowerCamelCase      						=    self.model_tester.prepare_config_and_inputs_for_common()

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

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







        '''simple docstring'''

        lowerCamelCase						,	lowerCamelCase      						=    self.model_tester.prepare_config_and_inputs_for_common()

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

         lowerCamelCase      						=    ['pixel_values']
         self.assertListEqual(arg_names[:1]						,	__snake_case     )

       @slow
       def   lowerCamelCase__						(	self					:  Dict     )   -> List[str]:







        '''simple docstring'''

        for model_name in SWIN2SR_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
         lowerCamelCase      						=    SwinaSRModel.from_pretrained(__snake_case     )
         self.assertIsNotNone(__snake_case     )

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







        '''simple docstring'''

        lowerCamelCase						,	lowerCamelCase      						=    self.model_tester.prepare_config_and_inputs_for_common()

        lowerCamelCase      						=    _config_zero_init(__snake_case     )
        for model_class in self.all_model_classes:
         lowerCamelCase      						=    model_class(config=__snake_case     )
         for name, param in model.named_parameters():
          if "logit_scale" in name:
           continue
          if 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'''						,	)





       def   lowerCamelCase__						(	self					:  int     )   -> Tuple:







        '''simple docstring'''

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

        for model_class in self.all_model_classes:
         lowerCamelCase      						=    True
         lowerCamelCase      						=    False
         lowerCamelCase      						=    True
         lowerCamelCase      						=    model_class(__snake_case     )
         model.to(__snake_case     )
         model.eval()
         with torch.no_grad():
          lowerCamelCase      						=    model(**self._prepare_for_class(__snake_case						,	__snake_case     )     )
         lowerCamelCase      						=    outputs.attentions
         lowerCamelCase      						=    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"]
         lowerCamelCase      						=    True
         lowerCamelCase      						=    config.window_size**2
         lowerCamelCase      						=    model_class(__snake_case     )
         model.to(__snake_case     )
         model.eval()
         with torch.no_grad():
          lowerCamelCase      						=    model(**self._prepare_for_class(__snake_case						,	__snake_case     )     )
         lowerCamelCase      						=    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]						,	)
         lowerCamelCase      						=    len(__snake_case     )

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

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

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


@require_vision
@require_torch
@slow
class     lowerCAmelCase				(    unittest.TestCase				):


       '''simple docstring'''







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







        '''simple docstring'''

        lowerCamelCase      						=    SwinaSRImageProcessor()
        lowerCamelCase      						=    SwinaSRForImageSuperResolution.from_pretrained('caidas/swin2SR-classical-sr-x2-64'     ).to(__snake_case     )

        lowerCamelCase      						=    Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'     )
        lowerCamelCase      						=    processor(images=__snake_case						,	return_tensors='pt'     ).to(__snake_case     )

        # forward pass
        with torch.no_grad():
         lowerCamelCase      						=    model(**__snake_case     )

        # verify the logits
        lowerCamelCase      						=    torch.Size([1, 3, 976, 1296]     )
        self.assertEqual(outputs.reconstruction.shape						,	__snake_case     )
        lowerCamelCase      						=    torch.tensor(
            [[0.5458, 0.5546, 0.5638], [0.5526, 0.5565, 0.5651], [0.5396, 0.5426, 0.5621]]     ).to(__snake_case     )
        self.assertTrue(torch.allclose(outputs.reconstruction[0, 0, :3, :3]						,	__snake_case						,	atol=1e-4     )     )




