


'''simple docstring'''






import copy
import inspect
import unittest

import numpy as np
from huggingface_hub import hf_hub_download

from transformers import VideoMAEConfig
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,
		    VideoMAEForPreTraining,
		    VideoMAEForVideoClassification,
		    VideoMAEModel,
		)
		from transformers.models.videomae.modeling_videomae import VIDEOMAE_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
		from transformers import VideoMAEImageProcessor




class 						a__							:





							'''simple docstring'''






							def __init__(						self   ,       lowerCamelCase_   ,       lowerCamelCase_=13   ,       lowerCamelCase_=10   ,       lowerCamelCase_=3   ,       lowerCamelCase_=2   ,       lowerCamelCase_=2   ,       lowerCamelCase_=2   ,       lowerCamelCase_=True   ,       lowerCamelCase_=True   ,       lowerCamelCase_=32   ,       lowerCamelCase_=5   ,       lowerCamelCase_=4   ,       lowerCamelCase_=37   ,       lowerCamelCase_="gelu"   ,       lowerCamelCase_=0.1   ,       lowerCamelCase_=0.1   ,       lowerCamelCase_=10   ,       lowerCamelCase_=0.02   ,       lowerCamelCase_=0.9   ,       lowerCamelCase_=None   ,       )			->				Tuple:
														lowerCAmelCase__			  =      parent
														lowerCAmelCase__			  =      batch_size
														lowerCAmelCase__			  =      image_size
														lowerCAmelCase__			  =      num_channels
														lowerCAmelCase__			  =      patch_size
														lowerCAmelCase__			  =      tubelet_size
														lowerCAmelCase__			  =      num_frames
														lowerCAmelCase__			  =      is_training
														lowerCAmelCase__			  =      use_labels
														lowerCAmelCase__			  =      hidden_size
														lowerCAmelCase__			  =      num_hidden_layers
														lowerCAmelCase__			  =      num_attention_heads
														lowerCAmelCase__			  =      intermediate_size
														lowerCAmelCase__			  =      hidden_act
														lowerCAmelCase__			  =      hidden_dropout_prob
														lowerCAmelCase__			  =      attention_probs_dropout_prob
														lowerCAmelCase__			  =      type_sequence_label_size
														lowerCAmelCase__			  =      initializer_range
														lowerCAmelCase__			  =      mask_ratio
														lowerCAmelCase__			  =      scope

														# in VideoMAE, the number of tokens equals num_frames/tubelet_size * num_patches per frame
														lowerCAmelCase__			  =      (image_size // patch_size) ** 2
														lowerCAmelCase__			  =      (num_frames // tubelet_size) * self.num_patches_per_frame

														# use this variable to define bool_masked_pos
														lowerCAmelCase__			  =      int(mask_ratio * self.seq_length  )







							def     __SCREAMING_SNAKE_CASE				(						self  )			->				int:
														lowerCAmelCase__			  =      floats_tensor(
														    [self.batch_size, self.num_frames, 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     __SCREAMING_SNAKE_CASE				(						self  )			->				Optional[Any]:
														return VideoMAEConfig(
														    image_size=self.image_size   ,       patch_size=self.patch_size   ,       num_channels=self.num_channels   ,       num_frames=self.num_frames   ,       tubelet_size=self.tubelet_size   ,       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   ,       is_decoder=lowerCamelCase_   ,       initializer_range=self.initializer_range   ,       )







							def     __SCREAMING_SNAKE_CASE				(						self   ,       lowerCamelCase_   ,       lowerCamelCase_   ,       lowerCamelCase_  )			->				Optional[int]:
														lowerCAmelCase__			  =      VideoMAEModel(config=lowerCamelCase_  )
														model.to(lowerCamelCase_  )
														model.eval()
														lowerCAmelCase__			  =      model(lowerCamelCase_  )
														self.parent.assertEqual(result.last_hidden_state.shape   ,       (self.batch_size, self.seq_length, self.hidden_size)  )







							def     __SCREAMING_SNAKE_CASE				(						self   ,       lowerCamelCase_   ,       lowerCamelCase_   ,       lowerCamelCase_  )			->				str:
														lowerCAmelCase__			  =      VideoMAEForPreTraining(lowerCamelCase_  )
														model.to(lowerCamelCase_  )
														model.eval()
														# important: each video needs to have the same number of masked patches
														# hence we define a single mask, which we then repeat for each example in the batch
														lowerCAmelCase__			  =      torch.ones((self.num_masks,)  )
														lowerCAmelCase__			  =      torch.cat([mask, torch.zeros(self.seq_length - mask.size(0  )  )]  )
														lowerCAmelCase__			  =      mask.expand(self.batch_size   ,       -1  ).bool()

														lowerCAmelCase__			  =      model(lowerCamelCase_   ,       lowerCamelCase_  )
														# model only returns predictions for masked patches
														lowerCAmelCase__			  =      mask.sum().item()
														lowerCAmelCase__			  =      3 * self.tubelet_size * self.patch_size**2
														self.parent.assertEqual(result.logits.shape   ,       (self.batch_size, num_masked_patches, decoder_num_labels)  )







							def     __SCREAMING_SNAKE_CASE				(						self  )			->				Union[str, Any]:
														lowerCAmelCase__			  =      self.prepare_config_and_inputs()
														lowerCAmelCase__  ,   lowerCAmelCase__  ,   lowerCAmelCase__			  =      config_and_inputs
														lowerCAmelCase__			  =      {'''pixel_values''': pixel_values}
														return config, inputs_dict




@require_torch
class 						a__							(				a__							,							a__							,							unittest.TestCase    ):





							'''simple docstring'''






							lowercase__     :  List[Any]      		= (
							    (VideoMAEModel, VideoMAEForPreTraining, VideoMAEForVideoClassification) if is_torch_available() else ()
							)
							lowercase__     :  Tuple      		= (
							    {"feature-extraction": VideoMAEModel, "video-classification": VideoMAEForVideoClassification}
							    if is_torch_available()
							    else {}
							)

							lowercase__     :  Optional[Any]      		= False
							lowercase__     :  str      		= False
							lowercase__     :  Any      		= False
							lowercase__     :  Dict      		= False







							def     __SCREAMING_SNAKE_CASE				(						self  )			->				List[Any]:
														lowerCAmelCase__			  =      VideoMAEModelTester(self  )
														lowerCAmelCase__			  =      ConfigTester(self   ,       config_class=lowerCamelCase_   ,       has_text_modality=lowerCamelCase_   ,       hidden_size=37  )







							def     __SCREAMING_SNAKE_CASE				(						self   ,       lowerCamelCase_   ,       lowerCamelCase_   ,       lowerCamelCase_=False  )			->				List[Any]:
														lowerCAmelCase__			  =      copy.deepcopy(lowerCamelCase_  )

														if model_class == VideoMAEForPreTraining:
																					# important: each video needs to have the same number of masked patches
																					# hence we define a single mask, which we then repeat for each example in the batch
																					lowerCAmelCase__			  =      torch.ones((self.model_tester.num_masks,)  )
																					lowerCAmelCase__			  =      torch.cat([mask, torch.zeros(self.model_tester.seq_length - mask.size(0  )  )]  )
																					lowerCAmelCase__			  =      mask.expand(self.model_tester.batch_size   ,       -1  ).bool()
																					lowerCAmelCase__			  =      bool_masked_pos.to(lowerCamelCase_  )

														if return_labels:
																					if model_class in [
																					    *get_values(lowerCamelCase_  ),
																					]:
																												lowerCAmelCase__			  =      torch.zeros(
																												    self.model_tester.batch_size   ,       dtype=torch.long   ,       device=lowerCamelCase_  )

														return inputs_dict







							def     __SCREAMING_SNAKE_CASE				(						self  )			->				int:
														self.config_tester.run_common_tests()







							@unittest.skip(reason='''VideoMAE does not use inputs_embeds'''  )
							def     __SCREAMING_SNAKE_CASE				(						self  )			->				str:
														pass







							def     __SCREAMING_SNAKE_CASE				(						self  )			->				Optional[Any]:
														lowerCAmelCase__  ,   lowerCAmelCase__			  =      self.model_tester.prepare_config_and_inputs_for_common()

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







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

														for model_class in self.all_model_classes:
																					lowerCAmelCase__			  =      model_class(lowerCamelCase_  )
																					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]   ,       lowerCamelCase_  )







							def     __SCREAMING_SNAKE_CASE				(						self  )			->				str:
														lowerCAmelCase__			  =      self.model_tester.prepare_config_and_inputs()
														self.model_tester.create_and_check_model(*lowerCamelCase_  )







							def     __SCREAMING_SNAKE_CASE				(						self  )			->				int:
														lowerCAmelCase__			  =      self.model_tester.prepare_config_and_inputs()
														self.model_tester.create_and_check_for_pretraining(*lowerCamelCase_  )







							@slow
							def     __SCREAMING_SNAKE_CASE				(						self  )			->				Any:
														for model_name in VIDEOMAE_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																					lowerCAmelCase__			  =      VideoMAEModel.from_pretrained(lowerCamelCase_  )
																					self.assertIsNotNone(lowerCamelCase_  )







							def     __SCREAMING_SNAKE_CASE				(						self  )			->				Tuple:
														if not self.has_attentions:
																					pass

														else:
																					lowerCAmelCase__  ,   lowerCAmelCase__			  =      self.model_tester.prepare_config_and_inputs_for_common()
																					lowerCAmelCase__			  =      True

																					for model_class in self.all_model_classes:
																												lowerCAmelCase__			  =      self.model_tester.seq_length - self.model_tester.num_masks
																												lowerCAmelCase__			  =      (
																												    num_visible_patches if model_class == VideoMAEForPreTraining else self.model_tester.seq_length
																												)

																												lowerCAmelCase__			  =      True
																												lowerCAmelCase__			  =      False
																												lowerCAmelCase__			  =      True
																												lowerCAmelCase__			  =      model_class(lowerCamelCase_  )
																												model.to(lowerCamelCase_  )
																												model.eval()
																												with torch.no_grad():
																																			lowerCAmelCase__			  =      model(**self._prepare_for_class(lowerCamelCase_   ,       lowerCamelCase_  )  )
																												lowerCAmelCase__			  =      outputs.attentions
																												self.assertEqual(len(lowerCamelCase_  )   ,       self.model_tester.num_hidden_layers  )

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

																												self.assertListEqual(
																												    list(attentions[0].shape[-3:]  )   ,       [self.model_tester.num_attention_heads, seq_len, seq_len]   ,       )
																												lowerCAmelCase__			  =      len(lowerCamelCase_  )

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

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

																												lowerCAmelCase__			  =      outputs.attentions

																												self.assertEqual(len(lowerCamelCase_  )   ,       self.model_tester.num_hidden_layers  )
																												self.assertListEqual(
																												    list(self_attentions[0].shape[-3:]  )   ,       [self.model_tester.num_attention_heads, seq_len, seq_len]   ,       )







							def     __SCREAMING_SNAKE_CASE				(						self  )			->				Dict:
														def check_hidden_states_output(lowerCamelCase_   ,       lowerCamelCase_   ,       lowerCamelCase_  ):
																					lowerCAmelCase__			  =      model_class(lowerCamelCase_  )
																					model.to(lowerCamelCase_  )
																					model.eval()

																					with torch.no_grad():
																												lowerCAmelCase__			  =      model(**self._prepare_for_class(lowerCamelCase_   ,       lowerCamelCase_  )  )

																					lowerCAmelCase__			  =      outputs.hidden_states
																					lowerCAmelCase__			  =      self.model_tester.num_hidden_layers + 1
																					self.assertEqual(len(lowerCamelCase_  )   ,       lowerCamelCase_  )

																					lowerCAmelCase__			  =      self.model_tester.seq_length - self.model_tester.num_masks
																					lowerCAmelCase__			  =      num_visible_patches if model_class == VideoMAEForPreTraining else self.model_tester.seq_length

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

														lowerCAmelCase__  ,   lowerCAmelCase__			  =      self.model_tester.prepare_config_and_inputs_for_common()

														for model_class in self.all_model_classes:
																					lowerCAmelCase__			  =      True
																					check_hidden_states_output(lowerCamelCase_   ,       lowerCamelCase_   ,       lowerCamelCase_  )

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

																					check_hidden_states_output(lowerCamelCase_   ,       lowerCamelCase_   ,       lowerCamelCase_  )







							@unittest.skip('''Will be fixed soon by reducing the size of the model used for common tests.'''  )
							def     __SCREAMING_SNAKE_CASE				(						self  )			->				int:
														pass


def    _snake_case  (	)		->       Any:
							lowerCAmelCase__			  =      hf_hub_download(
							    repo_id='''hf-internal-testing/spaghetti-video'''					,       filename='''eating_spaghetti.npy'''					,       repo_type='''dataset'''			)
							lowerCAmelCase__			  =      np.load(A			)
							return list(A			)






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





							'''simple docstring'''






							@cached_property
							def     __SCREAMING_SNAKE_CASE				(						self  )			->				Optional[int]:
														# 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     __SCREAMING_SNAKE_CASE				(						self  )			->				Dict:
														lowerCAmelCase__			  =      VideoMAEForVideoClassification.from_pretrained('''MCG-NJU/videomae-base-finetuned-kinetics'''  ).to(
														    lowerCamelCase_  )

														lowerCAmelCase__			  =      self.default_image_processor
														lowerCAmelCase__			  =      prepare_video()
														lowerCAmelCase__			  =      image_processor(lowerCamelCase_   ,       return_tensors='''pt'''  ).to(lowerCamelCase_  )

														# forward pass
														with torch.no_grad():
																					lowerCAmelCase__			  =      model(**lowerCamelCase_  )

														# verify the logits
														lowerCAmelCase__			  =      torch.Size((1, 4_00)  )
														self.assertEqual(outputs.logits.shape   ,       lowerCamelCase_  )

														lowerCAmelCase__			  =      torch.tensor([0.3_669, -0.0_688, -0.2_421]  ).to(lowerCamelCase_  )

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







							@slow
							def     __SCREAMING_SNAKE_CASE				(						self  )			->				str:
														lowerCAmelCase__			  =      VideoMAEForPreTraining.from_pretrained('''MCG-NJU/videomae-base-short'''  ).to(lowerCamelCase_  )

														lowerCAmelCase__			  =      self.default_image_processor
														lowerCAmelCase__			  =      prepare_video()
														lowerCAmelCase__			  =      image_processor(lowerCamelCase_   ,       return_tensors='''pt'''  ).to(lowerCamelCase_  )

														# add boolean mask, indicating which patches to mask
														lowerCAmelCase__			  =      hf_hub_download(repo_id='''hf-internal-testing/bool-masked-pos'''   ,       filename='''bool_masked_pos.pt'''  )
														lowerCAmelCase__			  =      torch.load(lowerCamelCase_  )

														# forward pass
														with torch.no_grad():
																					lowerCAmelCase__			  =      model(**lowerCamelCase_  )

														# verify the logits
														lowerCAmelCase__			  =      torch.Size([1, 14_08, 15_36]  )
														lowerCAmelCase__			  =      torch.tensor(
														    [[0.7_994, 0.9_612, 0.8_508], [0.7_401, 0.8_958, 0.8_302], [0.5_862, 0.7_468, 0.7_325]]   ,       device=lowerCamelCase_  )
														self.assertEqual(outputs.logits.shape   ,       lowerCamelCase_  )
														self.assertTrue(torch.allclose(outputs.logits[0, :3, :3]   ,       lowerCamelCase_   ,       atol=1e-4  )  )

														# verify the loss (`config.norm_pix_loss` = `True`)
														lowerCAmelCase__			  =      torch.tensor([0.5_142]   ,       device=lowerCamelCase_  )
														self.assertTrue(torch.allclose(outputs.loss   ,       lowerCamelCase_   ,       atol=1e-4  )  )

														# verify the loss (`config.norm_pix_loss` = `False`)
														lowerCAmelCase__			  =      VideoMAEForPreTraining.from_pretrained('''MCG-NJU/videomae-base-short'''   ,       norm_pix_loss=lowerCamelCase_  ).to(
														    lowerCamelCase_  )

														with torch.no_grad():
																					lowerCAmelCase__			  =      model(**lowerCamelCase_  )

														lowerCAmelCase__			  =      torch.tensor(torch.tensor([0.6_469]  )   ,       device=lowerCamelCase_  )
														self.assertTrue(torch.allclose(outputs.loss   ,       lowerCamelCase_   ,       atol=1e-4  )  )



'''simple docstring'''






from __future__ import annotations

from random import choice


def    _snake_case  (	A			)		->       int:
							return choice(A			)


def    _snake_case  (	A					,       A			)		->       int:
							lowerCAmelCase__			  =      random_pivot(A			)

							# partition based on pivot
							# linear time
							lowerCAmelCase__			  =      [e for e in lst if e < pivot]
							lowerCAmelCase__			  =      [e for e in lst if e > pivot]

							# if we get lucky, pivot might be the element we want.
							# we can easily see this:
							# small (elements smaller than k)
							# + pivot (kth element)
							# + big (elements larger than k)
							if len(A			) == k - 1:
														return pivot
							# pivot is in elements bigger than k
							elif len(A			) < k - 1:
														return kth_number(A					,       k - len(A			) - 1			)
							# pivot is in elements smaller than k
							else:
														return kth_number(A					,       A			)


if __name__ == "__main__":
		import doctest

		doctest.testmod()