




import copy
import inspect
import unittest

import numpy as np
from huggingface_hub import hf_hub_download

from transformers import TimesformerConfig
from transformers.models.auto import get_values
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_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 (
           MODEL_FOR_VIDEO_CLASSIFICATION_MAPPING,
           TimesformerForVideoClassification,
           TimesformerModel,
       )
       from transformers.models.timesformer.modeling_timesformer import TIMESFORMER_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
       from transformers import VideoMAEImageProcessor




class 		UpperCamelCase__	:

    '''simple docstring'''



    def __init__(    self     ,  UpperCamelCase__     ,  UpperCamelCase__=13     ,  UpperCamelCase__=10     ,  UpperCamelCase__=3     ,  UpperCamelCase__=2     ,  UpperCamelCase__=2     ,  UpperCamelCase__=True     ,  UpperCamelCase__=True     ,  UpperCamelCase__=32     ,  UpperCamelCase__=5     ,  UpperCamelCase__=4     ,  UpperCamelCase__=37     ,  UpperCamelCase__="gelu"     ,  UpperCamelCase__=0.1     ,  UpperCamelCase__=0.1     ,  UpperCamelCase__=10     ,  UpperCamelCase__=0.02     ,  UpperCamelCase__="divided_space_time"     ,  UpperCamelCase__=None     ,  )     ->      Dict:
           lowerCamelCase   :      Optional[int]			 =					parent
           lowerCamelCase   :      List[Any]			 =					batch_size
           lowerCamelCase   :      Tuple			 =					image_size
           lowerCamelCase   :      Any			 =					num_channels
           lowerCamelCase   :      int			 =					patch_size
           lowerCamelCase   :      List[Any]			 =					num_frames
           lowerCamelCase   :      Dict			 =					is_training
           lowerCamelCase   :      Tuple			 =					use_labels
           lowerCamelCase   :      Optional[Any]			 =					hidden_size
           lowerCamelCase   :      int			 =					num_hidden_layers
           lowerCamelCase   :      List[Any]			 =					num_attention_heads
           lowerCamelCase   :      str			 =					intermediate_size
           lowerCamelCase   :      Optional[int]			 =					hidden_act
           lowerCamelCase   :      int			 =					hidden_dropout_prob
           lowerCamelCase   :      Optional[int]			 =					attention_probs_dropout_prob
           lowerCamelCase   :      str			 =					attention_type
           lowerCamelCase   :      Union[str, Any]			 =					initializer_range
           lowerCamelCase   :      List[str]			 =					scope
           lowerCamelCase   :      List[Any]			 =					num_labels

           # in TimeSformer, the number of spatial tokens equals num_frames * num_patches per frame + 1 CLS token
           lowerCamelCase   :      List[str]			 =					(image_size // patch_size) ** 2
           lowerCamelCase   :      Optional[Any]			 =					(num_frames) * self.num_patches_per_frame + 1







    def     _lowercase     (    self     )     ->      List[str]:
           lowerCamelCase   :      str			 =					floats_tensor(
               [self.batch_size, self.num_frames, self.num_channels, self.image_size, self.image_size]     )

           lowerCamelCase   :      Optional[int]			 =					None
           if self.use_labels:
                  lowerCamelCase   :      Dict			 =					ids_tensor([self.batch_size]     ,  self.num_labels     )

           lowerCamelCase   :      Optional[int]			 =					self.get_config()

           return config, pixel_values, labels







    def     _lowercase     (    self     )     ->      int:
           lowerCamelCase   :      int			 =					TimesformerConfig(
               image_size=self.image_size     ,  patch_size=self.patch_size     ,  num_channels=self.num_channels     ,  num_frames=self.num_frames     ,  hidden_size=self.hidden_size     ,  num_hidden_layers=self.num_hidden_layers     ,  num_attention_heads=self.num_attention_heads     ,  intermediate_size=self.intermediate_size     ,  hidden_act=self.hidden_act     ,  hidden_dropout_prob=self.hidden_dropout_prob     ,  attention_probs_dropout_prob=self.attention_probs_dropout_prob     ,  initializer_range=self.initializer_range     ,  attention_type=self.attention_type     ,  )
           lowerCamelCase   :      Optional[int]			 =					self.num_labels
           return config







    def     _lowercase     (    self     ,  UpperCamelCase__     ,  UpperCamelCase__     ,  UpperCamelCase__     )     ->      Optional[Any]:
           lowerCamelCase   :      int			 =					TimesformerModel(config=UpperCamelCase__     )
           model.to(UpperCamelCase__     )
           model.eval()
           lowerCamelCase   :      List[str]			 =					model(UpperCamelCase__     )
           self.parent.assertEqual(result.last_hidden_state.shape     ,  (self.batch_size, self.seq_length, self.hidden_size)     )







    def     _lowercase     (    self     ,  UpperCamelCase__     ,  UpperCamelCase__     ,  UpperCamelCase__     )     ->      Union[str, Any]:
           lowerCamelCase   :      Any			 =					TimesformerForVideoClassification(UpperCamelCase__     )
           model.to(UpperCamelCase__     )
           model.eval()

           lowerCamelCase   :      List[str]			 =					model(UpperCamelCase__     )

           # verify the logits shape
           lowerCamelCase   :      List[Any]			 =					torch.Size((self.batch_size, self.num_labels)     )
           self.parent.assertEqual(result.logits.shape     ,  UpperCamelCase__     )







    def     _lowercase     (    self     )     ->      Union[str, Any]:
           lowerCamelCase   :      Any			 =					self.prepare_config_and_inputs()
           lowerCamelCase ,      lowerCamelCase ,      lowerCamelCase   :      List[Any]			 =					config_and_inputs
           lowerCamelCase   :      List[Any]			 =					{"pixel_values": pixel_values}
           return config, inputs_dict




@require_torch
class 		UpperCamelCase__	(lowerCAmelCase__    ,				lowerCAmelCase__    ,				unittest.TestCase     ):

    '''simple docstring'''



    lowerCamelCase_      :	Tuple	     =      (TimesformerModel, TimesformerForVideoClassification) if is_torch_available() else ()
    lowerCamelCase_      :	int	     =      (
        {"""feature-extraction""": TimesformerModel, """video-classification""": TimesformerForVideoClassification}
        if is_torch_available()
        else {}
    )

    lowerCamelCase_      :	Union[str, Any]	     =      False
    lowerCamelCase_      :	List[str]	     =      False
    lowerCamelCase_      :	str	     =      False
    lowerCamelCase_      :	str	     =      False







    def     _lowercase     (    self     )     ->      str:
           lowerCamelCase   :      Union[str, Any]			 =					TimesformerModelTester(self     )
           lowerCamelCase   :      Tuple			 =					ConfigTester(
               self     ,  config_class=UpperCamelCase__     ,  has_text_modality=UpperCamelCase__     ,  hidden_size=37     )







    def     _lowercase     (    self     ,  UpperCamelCase__     ,  UpperCamelCase__     ,  UpperCamelCase__=False     )     ->      List[str]:
           lowerCamelCase   :      Tuple			 =					copy.deepcopy(UpperCamelCase__     )

           if return_labels:
                  if model_class in get_values(UpperCamelCase__     ):
                         lowerCamelCase   :      Union[str, Any]			 =					torch.zeros(
                             self.model_tester.batch_size     ,  dtype=torch.long     ,  device=UpperCamelCase__     )

           return inputs_dict







    def     _lowercase     (    self     )     ->      List[Any]:
           self.config_tester.run_common_tests()







    @unittest.skip(reason="TimeSformer does not use inputs_embeds"     )
    def     _lowercase     (    self     )     ->      Dict:
           pass







    def     _lowercase     (    self     )     ->      Union[str, Any]:
           lowerCamelCase ,      lowerCamelCase   :      Any			 =					self.model_tester.prepare_config_and_inputs_for_common()

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







    def     _lowercase     (    self     )     ->      Optional[Any]:
           lowerCamelCase ,      lowerCamelCase   :      int			 =					self.model_tester.prepare_config_and_inputs_for_common()

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

                  lowerCamelCase   :      Union[str, Any]			 =					["pixel_values"]
                  self.assertListEqual(arg_names[:1]     ,  UpperCamelCase__     )







    def     _lowercase     (    self     )     ->      Dict:
           lowerCamelCase   :      Tuple			 =					self.model_tester.prepare_config_and_inputs()
           self.model_tester.create_and_check_model(*UpperCamelCase__     )







    def     _lowercase     (    self     )     ->      Tuple:
           lowerCamelCase   :      Union[str, Any]			 =					self.model_tester.prepare_config_and_inputs()
           self.model_tester.create_and_check_for_video_classification(*UpperCamelCase__     )







    @slow
    def     _lowercase     (    self     )     ->      List[Any]:
           for model_name in TIMESFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
                  lowerCamelCase   :      Optional[Any]			 =					TimesformerModel.from_pretrained(UpperCamelCase__     )
                  self.assertIsNotNone(UpperCamelCase__     )







    def     _lowercase     (    self     )     ->      Dict:
           if not self.has_attentions:
                  pass

           else:
                  lowerCamelCase ,      lowerCamelCase   :      Optional[Any]			 =					self.model_tester.prepare_config_and_inputs_for_common()
                  lowerCamelCase   :      List[str]			 =					True

                  for model_class in self.all_model_classes:
                         lowerCamelCase   :      List[str]			 =					self.model_tester.seq_length
                         lowerCamelCase   :      List[str]			 =					self.model_tester.num_frames

                         lowerCamelCase   :      Union[str, Any]			 =					True
                         lowerCamelCase   :      Tuple			 =					False
                         lowerCamelCase   :      Dict			 =					True
                         lowerCamelCase   :      Optional[Any]			 =					model_class(UpperCamelCase__     )
                         model.to(UpperCamelCase__     )
                         model.eval()
                         with torch.no_grad():
                                lowerCamelCase   :      List[Any]			 =					model(**self._prepare_for_class(UpperCamelCase__     ,  UpperCamelCase__     )     )
                         lowerCamelCase   :      Optional[int]			 =					outputs.attentions
                         self.assertEqual(len(UpperCamelCase__     )     ,  self.model_tester.num_hidden_layers     )

                         # check that output_attentions also work using config
                         del inputs_dict["output_attentions"]
                         lowerCamelCase   :      int			 =					True
                         lowerCamelCase   :      Dict			 =					model_class(UpperCamelCase__     )
                         model.to(UpperCamelCase__     )
                         model.eval()
                         with torch.no_grad():
                                lowerCamelCase   :      Optional[int]			 =					model(**self._prepare_for_class(UpperCamelCase__     ,  UpperCamelCase__     )     )
                         lowerCamelCase   :      List[str]			 =					outputs.attentions
                         self.assertEqual(len(UpperCamelCase__     )     ,  self.model_tester.num_hidden_layers     )

                         # attentions has shape (batch_size x num_frames) x num_heads x (num_patches per frame + 1) x (num_patches per frame + 1)
                         self.assertListEqual(
                             list(attentions[0].shape[-3:]     )     ,  [self.model_tester.num_attention_heads, seq_len // num_frames + 1, seq_len // num_frames + 1]     ,  )
                         lowerCamelCase   :      Union[str, Any]			 =					len(UpperCamelCase__     )

                         # Check attention is always last and order is fine
                         lowerCamelCase   :      List[str]			 =					True
                         lowerCamelCase   :      List[Any]			 =					True
                         lowerCamelCase   :      Dict			 =					model_class(UpperCamelCase__     )
                         model.to(UpperCamelCase__     )
                         model.eval()
                         with torch.no_grad():
                                lowerCamelCase   :      int			 =					model(**self._prepare_for_class(UpperCamelCase__     ,  UpperCamelCase__     )     )

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

                         lowerCamelCase   :      Tuple			 =					outputs.attentions

                         self.assertEqual(len(UpperCamelCase__     )     ,  self.model_tester.num_hidden_layers     )

                         # attentions has shape (batch_size x num_frames) x num_heads x (num_patches per frame + 1) x (num_patches per frame + 1)
                         self.assertListEqual(
                             list(self_attentions[0].shape[-3:]     )     ,  [self.model_tester.num_attention_heads, seq_len // num_frames + 1, seq_len // num_frames + 1]     ,  )







    def     _lowercase     (    self     )     ->      List[str]:
           def check_hidden_states_output(UpperCamelCase__     ,  UpperCamelCase__     ,  UpperCamelCase__     ):
                  lowerCamelCase   :      str			 =					model_class(UpperCamelCase__     )
                  model.to(UpperCamelCase__     )
                  model.eval()

                  with torch.no_grad():
                         lowerCamelCase   :      Any			 =					model(**self._prepare_for_class(UpperCamelCase__     ,  UpperCamelCase__     )     )

                  lowerCamelCase   :      Tuple			 =					outputs.hidden_states
                  lowerCamelCase   :      Optional[int]			 =					self.model_tester.num_hidden_layers + 1
                  self.assertEqual(len(UpperCamelCase__     )     ,  UpperCamelCase__     )

                  lowerCamelCase   :      Optional[Any]			 =					self.model_tester.seq_length

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

           lowerCamelCase ,      lowerCamelCase   :      Optional[int]			 =					self.model_tester.prepare_config_and_inputs_for_common()

           for model_class in self.all_model_classes:
                  lowerCamelCase   :      Dict			 =					True
                  check_hidden_states_output(UpperCamelCase__     ,  UpperCamelCase__     ,  UpperCamelCase__     )

                  # check that output_hidden_states also work using config
                  del inputs_dict["output_hidden_states"]
                  lowerCamelCase   :      int			 =					True

                  check_hidden_states_output(UpperCamelCase__     ,  UpperCamelCase__     ,  UpperCamelCase__     )




def      A      (      )	-> Dict:
       lowerCamelCase   :      Dict			 =					hf_hub_download(
           repo_id="hf-internal-testing/spaghetti-video" ,filename="eating_spaghetti.npy" ,repo_type="dataset"    )
       lowerCamelCase   :      Union[str, Any]			 =					np.load(_SCREAMING_SNAKE_CASE    )
       return list(_SCREAMING_SNAKE_CASE    )




@require_torch
@require_vision
class 		UpperCamelCase__	(unittest.TestCase     ):

    '''simple docstring'''



    @cached_property
    def     _lowercase     (    self     )     ->      List[str]:
           # logits were tested with a different mean and std, so we use the same here
           return (
               VideoMAEImageProcessor(image_mean=[0.5, 0.5, 0.5]     ,  image_std=[0.5, 0.5, 0.5]     )
               if is_vision_available()
               else None
           )







    @slow
    def     _lowercase     (    self     )     ->      int:
           lowerCamelCase   :      Tuple			 =					TimesformerForVideoClassification.from_pretrained("facebook/timesformer-base-finetuned-k400"     ).to(
               UpperCamelCase__     )

           lowerCamelCase   :      Any			 =					self.default_image_processor
           lowerCamelCase   :      Union[str, Any]			 =					prepare_video()
           lowerCamelCase   :      List[Any]			 =					image_processor(video[:8]     ,  return_tensors="pt"     ).to(UpperCamelCase__     )

           # forward pass
           with torch.no_grad():
                  lowerCamelCase   :      List[Any]			 =					model(**UpperCamelCase__     )

           # verify the logits
           lowerCamelCase   :      Tuple			 =					torch.Size((1, 400)     )
           self.assertEqual(outputs.logits.shape     ,  UpperCamelCase__     )

           lowerCamelCase   :      Dict			 =					torch.tensor([-0.3016, -0.7713, -0.4205]     ).to(UpperCamelCase__     )

           self.assertTrue(torch.allclose(outputs.logits[0, :3]     ,  UpperCamelCase__     ,  atol=1e-4     )     )








def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


					def update_area_of_max_square(UpperCamelCase_	,	UpperCamelCase_		) -> int:
										# BASE CASE
										if row >= rows or col >= cols:
															return 0

										SCREAMING_SNAKE_CASE__													= update_area_of_max_square(UpperCamelCase_	,	col + 1		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square(row + 1	,	col + 1		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square(row + 1	,	UpperCamelCase_		)

										if mat[row][col]:
															SCREAMING_SNAKE_CASE__													= 1 + min([right, diagonal, down]		)
															SCREAMING_SNAKE_CASE__													= max(largest_square_area[0]	,	UpperCamelCase_		)
															return sub_problem_sol
										else:
															return 0

					SCREAMING_SNAKE_CASE__													= [0]
					update_area_of_max_square(0	,	0		)
					return largest_square_area[0]






def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


					def update_area_of_max_square_using_dp_array(
					    UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		) -> int:
										if row >= rows or col >= cols:
															return 0
										if dp_array[row][col] != -1:
															return dp_array[row][col]

										SCREAMING_SNAKE_CASE__													= update_area_of_max_square_using_dp_array(UpperCamelCase_	,	col + 1	,	UpperCamelCase_		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square_using_dp_array(row + 1	,	col + 1	,	UpperCamelCase_		)
										SCREAMING_SNAKE_CASE__													= update_area_of_max_square_using_dp_array(row + 1	,	UpperCamelCase_	,	UpperCamelCase_		)

										if mat[row][col]:
															SCREAMING_SNAKE_CASE__													= 1 + min([right, diagonal, down]		)
															SCREAMING_SNAKE_CASE__													= max(largest_square_area[0]	,	UpperCamelCase_		)
															SCREAMING_SNAKE_CASE__													= sub_problem_sol
															return sub_problem_sol
										else:
															return 0

					SCREAMING_SNAKE_CASE__													= [0]
					SCREAMING_SNAKE_CASE__													= [[-1] * cols for _ in range(UpperCamelCase_		)]
					update_area_of_max_square_using_dp_array(0	,	0	,	UpperCamelCase_		)

					return largest_square_area[0]






def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


					SCREAMING_SNAKE_CASE__													= [[0] * (cols + 1) for _ in range(rows + 1		)]
					SCREAMING_SNAKE_CASE__													= 0
					for row in range(rows - 1	,	-1	,	-1		):
										for col in range(cols - 1	,	-1	,	-1		):
															SCREAMING_SNAKE_CASE__													= dp_array[row][col + 1]
															SCREAMING_SNAKE_CASE__													= dp_array[row + 1][col + 1]
															SCREAMING_SNAKE_CASE__													= dp_array[row + 1][col]

															if mat[row][col] == 1:
																				SCREAMING_SNAKE_CASE__													= 1 + min(UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)
																				SCREAMING_SNAKE_CASE__													= max(dp_array[row][col]	,	UpperCamelCase_		)
															else:
																				SCREAMING_SNAKE_CASE__													= 0

					return largest_square_area






def 							_lowercase							(     UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)		->		int:
					'''simple docstring'''


					SCREAMING_SNAKE_CASE__													= [0] * (cols + 1)
					SCREAMING_SNAKE_CASE__													= [0] * (cols + 1)
					SCREAMING_SNAKE_CASE__													= 0
					for row in range(rows - 1	,	-1	,	-1		):
										for col in range(cols - 1	,	-1	,	-1		):
															SCREAMING_SNAKE_CASE__													= current_row[col + 1]
															SCREAMING_SNAKE_CASE__													= next_row[col + 1]
															SCREAMING_SNAKE_CASE__													= next_row[col]

															if mat[row][col] == 1:
																				SCREAMING_SNAKE_CASE__													= 1 + min(UpperCamelCase_	,	UpperCamelCase_	,	UpperCamelCase_		)
																				SCREAMING_SNAKE_CASE__													= max(current_row[col]	,	UpperCamelCase_		)
															else:
																				SCREAMING_SNAKE_CASE__													= 0
										SCREAMING_SNAKE_CASE__													= current_row

					return largest_square_area


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				print(largest_square_area_in_matrix_bottom_up(2, 2, [[1, 1], [1, 1]]))





