



import collections
import inspect
import unittest
from typing import Dict, List, Tuple

from transformers import MaskFormerSwinConfig
from transformers.testing_utils import require_torch, require_torch_multi_gpu, torch_device
from transformers.utils import is_torch_available

from ...test_backbone_common import BackboneTesterMixin
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 MaskFormerSwinBackbone
   from transformers.models.maskformer import MaskFormerSwinModel


class   snake_case_ :




       """simple docstring"""






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

             """simple docstring"""





             UpperCAmelCase_  :	int				      =		parent
             UpperCAmelCase_  :	List[str]				      =		batch_size
             UpperCAmelCase_  :	List[str]				      =		image_size
             UpperCAmelCase_  :	Optional[int]				      =		patch_size
             UpperCAmelCase_  :	int				      =		num_channels
             UpperCAmelCase_  :	Union[str, Any]				      =		embed_dim
             UpperCAmelCase_  :	Tuple				      =		depths
             UpperCAmelCase_  :	List[Any]				      =		num_heads
             UpperCAmelCase_  :	int				      =		window_size
             UpperCAmelCase_  :	int				      =		mlp_ratio
             UpperCAmelCase_  :	Optional[Any]				      =		qkv_bias
             UpperCAmelCase_  :	List[Any]				      =		hidden_dropout_prob
             UpperCAmelCase_  :	Optional[int]				      =		attention_probs_dropout_prob
             UpperCAmelCase_  :	Any				      =		drop_path_rate
             UpperCAmelCase_  :	Optional[int]				      =		hidden_act
             UpperCAmelCase_  :	Tuple				      =		use_absolute_embeddings
             UpperCAmelCase_  :	Union[str, Any]				      =		patch_norm
             UpperCAmelCase_  :	str				      =		layer_norm_eps
             UpperCAmelCase_  :	List[str]				      =		initializer_range
             UpperCAmelCase_  :	Optional[int]				      =		is_training
             UpperCAmelCase_  :	str				      =		scope
             UpperCAmelCase_  :	Tuple				      =		use_labels
             UpperCAmelCase_  :	List[str]				      =		type_sequence_label_size
             UpperCAmelCase_  :	Optional[int]				      =		encoder_stride
             UpperCAmelCase_  :	str				      =		out_features
             UpperCAmelCase_  :	Optional[Any]				      =		out_indices



       def  A_   (     self):

             """simple docstring"""





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

             UpperCAmelCase_  :	str				      =		None
             if self.use_labels:
                   UpperCAmelCase_  :	List[str]				      =		ids_tensor([self.batch_size]     ,self.type_sequence_label_size)

             UpperCAmelCase_  :	List[str]				      =		self.get_config()

             return config, pixel_values, labels



       def  A_   (     self):

             """simple docstring"""





             return MaskFormerSwinConfig(
                 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     ,out_features=self.out_features     ,out_indices=self.out_indices     ,)



       def  A_   (     self     ,lowercase     ,lowercase     ,lowercase):

             """simple docstring"""





             UpperCAmelCase_  :	Any				      =		MaskFormerSwinModel(config=lowercase)
             model.to(lowercase)
             model.eval()
             UpperCAmelCase_  :	Dict				      =		model(lowercase)

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

             """simple docstring"""





             UpperCAmelCase_  :	Any				      =		MaskFormerSwinBackbone(config=lowercase)
             model.to(lowercase)
             model.eval()
             UpperCAmelCase_  :	str				      =		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)     ,[13, 16, 16, 16])

             # verify channels
             self.parent.assertEqual(len(model.channels)     ,len(config.out_features))
             self.parent.assertListEqual(model.channels     ,[16, 32, 64])

             # verify ValueError
             with self.parent.assertRaises(lowercase):
                   UpperCAmelCase_  :	Dict				      =		['''stem''']
                   UpperCAmelCase_  :	str				      =		MaskFormerSwinBackbone(config=lowercase)



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	Tuple				      =		self.prepare_config_and_inputs()
             UpperCAmelCase_  :	List[Any]				      =		config_and_inputs
             UpperCAmelCase_  :	Any				      =		{'''pixel_values''': pixel_values}
             return config, inputs_dict


@require_torch
class   snake_case_ (__A , __A , unittest.TestCase  ):




       """simple docstring"""






       _lowerCamelCase			    =				(
           (
               MaskFormerSwinModel,
               MaskFormerSwinBackbone,
           )
           if is_torch_available()
           else ()
       )
       _lowerCamelCase			    =				{"""feature-extraction""": MaskFormerSwinModel} if is_torch_available() else {}
       _lowerCamelCase			    =				False
       _lowerCamelCase			    =				False
       _lowerCamelCase			    =				False
       _lowerCamelCase			    =				False
       _lowerCamelCase			    =				False



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	Optional[Any]				      =		MaskFormerSwinModelTester(self)
             UpperCAmelCase_  :	List[str]				      =		ConfigTester(self     ,config_class=lowercase     ,embed_dim=37)



       @require_torch_multi_gpu
       @unittest.skip(
           reason=(
               "`MaskFormerSwinModel` outputs `hidden_states_spatial_dimensions` which doesn\'t work well with"
               " `nn.DataParallel`"
           ))
       def  A_   (     self):

             """simple docstring"""





             pass



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

             """simple docstring"""





             return



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	Optional[int]				      =		self.model_tester.prepare_config_and_inputs()
             self.model_tester.create_and_check_model(*lowercase)



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	List[Any]				      =		self.model_tester.prepare_config_and_inputs()
             self.model_tester.create_and_check_backbone(*lowercase)



       @unittest.skip("Swin does not use inputs_embeds")
       def  A_   (     self):

             """simple docstring"""





             pass



       @unittest.skip("Swin does not support feedforward chunking")
       def  A_   (     self):

             """simple docstring"""





             pass



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	int				      =		self.model_tester.prepare_config_and_inputs_for_common()

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



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	Any				      =		self.model_tester.prepare_config_and_inputs_for_common()

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

                   UpperCAmelCase_  :	Optional[Any]				      =		['''pixel_values''']
                   self.assertListEqual(arg_names[:1]     ,lowercase)



       @unittest.skip(reason="MaskFormerSwin is only used as backbone and doesn\'t support output_attentions")
       def  A_   (     self):

             """simple docstring"""





             pass



       @unittest.skip(reason="MaskFormerSwin is only used as an internal backbone")
       def  A_   (     self):

             """simple docstring"""





             pass



       def  A_   (     self     ,lowercase     ,lowercase     ,lowercase     ,lowercase):

             """simple docstring"""





             UpperCAmelCase_  :	Tuple				      =		model_class(lowercase)
             model.to(lowercase)
             model.eval()

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

             UpperCAmelCase_  :	Tuple				      =		outputs.hidden_states

             UpperCAmelCase_  :	Union[str, Any]				      =		getattr(
                 self.model_tester     ,"expected_num_hidden_layers"     ,len(self.model_tester.depths) + 1)
             self.assertEqual(len(lowercase)     ,lowercase)

             # Swin has a different seq_length
             UpperCAmelCase_  :	int				      =		(
                 config.patch_size
                 if isinstance(config.patch_size     ,collections.abc.Iterable)
                 else (config.patch_size, config.patch_size)
             )

             UpperCAmelCase_  :	Dict				      =		(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]     ,)



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	List[str]				      =		self.model_tester.prepare_config_and_inputs_for_common()

             UpperCAmelCase_  :	Dict				      =		(
                 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:
                   UpperCAmelCase_  :	List[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"]
                   UpperCAmelCase_  :	Union[str, Any]				      =		True

                   self.check_hidden_states_output(lowercase     ,lowercase     ,lowercase     ,lowercase)



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	int				      =		self.model_tester.prepare_config_and_inputs_for_common()
             UpperCAmelCase_  :	List[str]				      =		3

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

             UpperCAmelCase_  :	Optional[Any]				      =		image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
             UpperCAmelCase_  :	Optional[int]				      =		image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

             for model_class in self.all_model_classes:
                   UpperCAmelCase_  :	Union[str, Any]				      =		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"]
                   UpperCAmelCase_  :	Any				      =		True
                   self.check_hidden_states_output(lowercase     ,lowercase     ,lowercase     ,(padded_height, padded_width))



       @unittest.skip(reason="MaskFormerSwin doesn\'t have pretrained checkpoints")
       def  A_   (     self):

             """simple docstring"""





             pass



       @unittest.skip(reason="This will be fixed once MaskFormerSwin is replaced by native Swin")
       def  A_   (     self):

             """simple docstring"""





             pass



       @unittest.skip(reason="This will be fixed once MaskFormerSwin is replaced by native Swin")
       def  A_   (     self):

             """simple docstring"""





             pass



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	int				      =		self.model_tester.prepare_config_and_inputs_for_common()

             def set_nan_tensor_to_zero(lowercase):
                   UpperCAmelCase_  :	Optional[int]				      =		0
                   return t

             def check_equivalence(lowercase     ,lowercase     ,lowercase     ,lowercase={}):
                   with torch.no_grad():
                         UpperCAmelCase_  :	int				      =		model(**lowercase     ,return_dict=lowercase     ,**lowercase)
                         UpperCAmelCase_  :	Tuple				      =		model(**lowercase     ,return_dict=lowercase     ,**lowercase).to_tuple()

                         def recursive_check(lowercase     ,lowercase):
                               if isinstance(lowercase     ,(List, Tuple)):
                                     for tuple_iterable_value, dict_iterable_value in zip(lowercase     ,lowercase):
                                           recursive_check(lowercase     ,lowercase)
                               elif isinstance(lowercase     ,lowercase):
                                     for tuple_iterable_value, dict_iterable_value in zip(
                                         tuple_object.values()     ,dict_object.values()):
                                           recursive_check(lowercase     ,lowercase)
                               elif tuple_object is None:
                                     return
                               else:
                                     self.assertTrue(
                                         torch.allclose(
                                             set_nan_tensor_to_zero(lowercase)     ,set_nan_tensor_to_zero(lowercase)     ,atol=1E-5)     ,msg=(
                                             "Tuple and dict output are not equal. Difference:"
                                             F""" {torch.max(torch.abs(tuple_object - dict_object))}. Tuple has `nan`:"""
                                             F""" {torch.isnan(lowercase).any()} and `inf`: {torch.isinf(lowercase)}. Dict has"""
                                             F""" `nan`: {torch.isnan(lowercase).any()} and `inf`: {torch.isinf(lowercase)}."""
                                         )     ,)

                         recursive_check(lowercase     ,lowercase)

             for model_class in self.all_model_classes:
                   UpperCAmelCase_  :	Any				      =		model_class(lowercase)
                   model.to(lowercase)
                   model.eval()

                   UpperCAmelCase_  :	List[Any]				      =		self._prepare_for_class(lowercase     ,lowercase)
                   UpperCAmelCase_  :	Union[str, Any]				      =		self._prepare_for_class(lowercase     ,lowercase)
                   check_equivalence(lowercase     ,lowercase     ,lowercase)

                   UpperCAmelCase_  :	Optional[int]				      =		self._prepare_for_class(lowercase     ,lowercase     ,return_labels=lowercase)
                   UpperCAmelCase_  :	List[str]				      =		self._prepare_for_class(lowercase     ,lowercase     ,return_labels=lowercase)
                   check_equivalence(lowercase     ,lowercase     ,lowercase)

                   UpperCAmelCase_  :	Union[str, Any]				      =		self._prepare_for_class(lowercase     ,lowercase)
                   UpperCAmelCase_  :	List[str]				      =		self._prepare_for_class(lowercase     ,lowercase)
                   check_equivalence(lowercase     ,lowercase     ,lowercase     ,{"output_hidden_states": True})

                   UpperCAmelCase_  :	int				      =		self._prepare_for_class(lowercase     ,lowercase     ,return_labels=lowercase)
                   UpperCAmelCase_  :	List[Any]				      =		self._prepare_for_class(lowercase     ,lowercase     ,return_labels=lowercase)
                   check_equivalence(lowercase     ,lowercase     ,lowercase     ,{"output_hidden_states": True})


@require_torch
class   snake_case_ (unittest.TestCase , __A  ):




       """simple docstring"""






       _lowerCamelCase			    =				(MaskFormerSwinBackbone,) if is_torch_available() else ()
       _lowerCamelCase			    =				MaskFormerSwinConfig



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	Optional[Any]				      =		MaskFormerSwinModelTester(self)



       def  A_   (     self):

             """simple docstring"""





             UpperCAmelCase_  :	Any				      =		self.model_tester.prepare_config_and_inputs_for_common()
             UpperCAmelCase_  :	Tuple				      =		inputs_dict['''pixel_values'''].shape[0]

             for backbone_class in self.all_model_classes:
                   UpperCAmelCase_  :	str				      =		backbone_class(lowercase)
                   backbone.to(lowercase)
                   backbone.eval()

                   UpperCAmelCase_  :	Optional[int]				      =		backbone(**lowercase)

                   # Test default outputs and verify feature maps
                   self.assertIsInstance(outputs.feature_maps     ,lowercase)
                   self.assertTrue(len(outputs.feature_maps) == len(backbone.channels))
                   for feature_map, n_channels in zip(outputs.feature_maps     ,backbone.channels):
                         self.assertTrue(feature_map.shape[:2]     ,(batch_size, n_channels))
                   self.assertIsNone(outputs.hidden_states)
                   self.assertIsNone(outputs.attentions)

                   # Test output_hidden_states=True
                   UpperCAmelCase_  :	List[Any]				      =		backbone(**lowercase     ,output_hidden_states=lowercase)
                   self.assertIsNotNone(outputs.hidden_states)
                   self.assertTrue(len(outputs.hidden_states)     ,len(backbone.stage_names))
                   # We skip the stem layer
                   for hidden_states, n_channels in zip(outputs.hidden_states[1:]     ,backbone.channels):
                         for hidden_state in hidden_states:
                               # Hidden states are in the format (batch_size, (height * width), n_channels)
                               UpperCAmelCase_  :	str				      =		hidden_state.shape
                               self.assertTrue((h_batch_size, h_n_channels)     ,(batch_size, n_channels))

                                 # Test output_attentions=True
                   if self.has_attentions:
                         UpperCAmelCase_  :	str				      =		backbone(**lowercase     ,output_attentions=lowercase)
                         self.assertIsNotNone(outputs.attentions)





import operator







def    _snake_case (       __snake_case					,  __snake_case = False					,  __snake_case = None    )     ->     list:






      '''simple docstring'''







      UpperCAmelCase_  :	Optional[int]				      =		operator.lt if reverse else operator.gt
      UpperCAmelCase_  :	int				      =		solution or []

      if not arr:
            return solution

      UpperCAmelCase_  :	Union[str, Any]				      =		[arr.pop(0    )]
      for i, item in enumerate(__snake_case    ):
            if _operator(__snake_case					,  sublist[-1]    ):
                  sublist.append(__snake_case    )
                  arr.pop(__snake_case    )

    #  merging sublist into solution list
      if not solution:
            solution.extend(__snake_case    )
      else:
            while sublist:
                  UpperCAmelCase_  :	Optional[int]				      =		sublist.pop(0    )
                  for i, xx in enumerate(__snake_case    ):
                        if not _operator(__snake_case					,  __snake_case    ):
                              solution.insert(__snake_case					,  __snake_case    )
                              break
                  else:
                        solution.append(__snake_case    )

      strand_sort(__snake_case					,  __snake_case					,  __snake_case    )
      return solution


if __name__ == "__main__":
   assert strand_sort([4, 3, 5, 1, 2]) == [1, 2, 3, 4, 5]
   assert strand_sort([4, 3, 5, 1, 2], reverse=True) == [5, 4, 3, 2, 1]
