
"""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      __a      :







       def __init__(       self				,lowerCamelCase_				,lowerCamelCase_=13				,lowerCamelCase_=32				,lowerCamelCase_=2				,lowerCamelCase_=3				,lowerCamelCase_=16				,lowerCamelCase_=[1, 2, 1]				,lowerCamelCase_=[2, 2, 4]				,lowerCamelCase_=2				,lowerCamelCase_=2.0				,lowerCamelCase_=True				,lowerCamelCase_=0.0				,lowerCamelCase_=0.0				,lowerCamelCase_=0.1				,lowerCamelCase_="gelu"				,lowerCamelCase_=False				,lowerCamelCase_=True				,lowerCamelCase_=0.0_2				,lowerCamelCase_=1e-5				,lowerCamelCase_=True				,lowerCamelCase_=None				,lowerCamelCase_=True				,lowerCamelCase_=10				,lowerCamelCase_=8				,):



          '''simple docstring'''

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







       def  _snake_case      (       self		):



          '''simple docstring'''

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

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

          _UpperCAmelCase 						=       self.get_config()

          return config, pixel_values, labels







       def  _snake_case      (       self		):



          '''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  _snake_case      (       self				,lowerCamelCase_				,lowerCamelCase_				,lowerCamelCase_		):



          '''simple docstring'''

          _UpperCAmelCase 						=       DonutSwinModel(config=SCREAMING_SNAKE_CASE__		)
          model.to(SCREAMING_SNAKE_CASE__		)
          model.eval()
          _UpperCAmelCase 						=       model(SCREAMING_SNAKE_CASE__		)

          _UpperCAmelCase 						=       ((config.image_size // config.patch_size) ** 2) // (4 ** (len(config.depths		) - 1))
          _UpperCAmelCase 						=       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  _snake_case      (       self		):



          '''simple docstring'''

          _UpperCAmelCase 						=       self.prepare_config_and_inputs()
          (
              (
              _UpperCAmelCase							
          )						,				(
              _UpperCAmelCase							
          )						,				(
              _UpperCAmelCase							
          )						,											
          ) 						=       config_and_inputs
          _UpperCAmelCase 						=       {"pixel_values": pixel_values}
          return config, inputs_dict






@require_torch
class      __a      (       __a					,						__a					,						unittest.TestCase      ):
       _lowerCamelCase				:				Any   			=      (DonutSwinModel,) if is_torch_available() else ()
       _lowerCamelCase				:				Optional[int]   			=      {'feature-extraction': DonutSwinModel} if is_torch_available() else {}
       _lowerCamelCase				:				Dict   			=      True

       _lowerCamelCase				:				Union[str, Any]   			=      False
       _lowerCamelCase				:				Optional[Any]   			=      False
       _lowerCamelCase				:				int   			=      False







       def  _snake_case      (       self		):



          '''simple docstring'''

          _UpperCAmelCase 						=       DonutSwinModelTester(self		)
          _UpperCAmelCase 						=       ConfigTester(self				,config_class=SCREAMING_SNAKE_CASE__				,embed_dim=37		)







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



          '''simple docstring'''

          return







       def  _snake_case      (       self		):



          '''simple docstring'''

          _UpperCAmelCase 						=       self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_model(*SCREAMING_SNAKE_CASE__		)







       def  _snake_case      (       self		):



          '''simple docstring'''

          pass







       def  _snake_case      (       self		):



          '''simple docstring'''

          _UpperCAmelCase						,				_UpperCAmelCase 						=       self.model_tester.prepare_config_and_inputs_for_common()

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







       def  _snake_case      (       self		):



          '''simple docstring'''

          _UpperCAmelCase						,				_UpperCAmelCase 						=       self.model_tester.prepare_config_and_inputs_for_common()

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

             _UpperCAmelCase 						=       ["pixel_values"]
             self.assertListEqual(arg_names[:1]				,SCREAMING_SNAKE_CASE__		)







       def  _snake_case      (       self		):



          '''simple docstring'''

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

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

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

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

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

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

             _UpperCAmelCase 						=       outputs.attentions

             self.assertEqual(len(SCREAMING_SNAKE_CASE__		)				,SCREAMING_SNAKE_CASE__		)

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







       def  _snake_case      (       self				,lowerCamelCase_				,lowerCamelCase_				,lowerCamelCase_				,lowerCamelCase_		):



          '''simple docstring'''

          _UpperCAmelCase 						=       model_class(SCREAMING_SNAKE_CASE__		)
          model.to(SCREAMING_SNAKE_CASE__		)
          model.eval()

          with torch.no_grad():
             _UpperCAmelCase 						=       model(**self._prepare_for_class(SCREAMING_SNAKE_CASE__				,SCREAMING_SNAKE_CASE__		)		)

          _UpperCAmelCase 						=       outputs.hidden_states

          _UpperCAmelCase 						=       getattr(
              self.model_tester				,"expected_num_hidden_layers"				,len(self.model_tester.depths		) + 1		)
          self.assertEqual(len(SCREAMING_SNAKE_CASE__		)				,SCREAMING_SNAKE_CASE__		)

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

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

          _UpperCAmelCase 						=       outputs.reshaped_hidden_states
          self.assertEqual(len(SCREAMING_SNAKE_CASE__		)				,SCREAMING_SNAKE_CASE__		)

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







       def  _snake_case      (       self		):



          '''simple docstring'''

          _UpperCAmelCase						,				_UpperCAmelCase 						=       self.model_tester.prepare_config_and_inputs_for_common()

          _UpperCAmelCase 						=       (
              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 						=       True
             self.check_hidden_states_output(SCREAMING_SNAKE_CASE__				,SCREAMING_SNAKE_CASE__				,SCREAMING_SNAKE_CASE__				,SCREAMING_SNAKE_CASE__		)

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

             self.check_hidden_states_output(SCREAMING_SNAKE_CASE__				,SCREAMING_SNAKE_CASE__				,SCREAMING_SNAKE_CASE__				,SCREAMING_SNAKE_CASE__		)







       def  _snake_case      (       self		):



          '''simple docstring'''

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

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

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

          for model_class in self.all_model_classes:
             _UpperCAmelCase 						=       True
             self.check_hidden_states_output(SCREAMING_SNAKE_CASE__				,SCREAMING_SNAKE_CASE__				,SCREAMING_SNAKE_CASE__				,(padded_height, padded_width)		)

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







       @slow
       def  _snake_case      (       self		):



          '''simple docstring'''

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







       def  _snake_case      (       self		):



          '''simple docstring'''

          _UpperCAmelCase						,				_UpperCAmelCase 						=       self.model_tester.prepare_config_and_inputs_for_common()

          _UpperCAmelCase 						=       _config_zero_init(SCREAMING_SNAKE_CASE__		)
          for model_class in self.all_model_classes:
             _UpperCAmelCase 						=       model_class(config=SCREAMING_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"""




from __future__ import annotations



def 						UpperCAmelCase__ (					A__						,     A__						,     A__						,     A__ )   ->   None:




   """simple docstring"""
   lowerCamelCase__       ,							lowerCamelCase__						       =      m - 1, 0
   while i >= 0 and j < n:
      if key == mat[i][j]:
         print(f'Key {key} found at row- {i + 1} column- {j + 1}' )
         return
      if key < mat[i][j]:
         i -= 1
      else:
         j += 1
   print(f'Key {key} not found' )



def 						UpperCAmelCase__ (					)   ->   None:




   """simple docstring"""
   lowerCamelCase__						       =      [[2, 5, 7], [4, 8, 13], [9, 11, 15], [12, 17, 20]]
   lowerCamelCase__						       =      int(input("Enter the element to be searched:" ) )
   print(A__ )
   search_in_a_sorted_matrix(A__						,     len(A__ )						,     len(mat[0] )						,     A__ )


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     main()




