





'''simple docstring'''




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     A_      :




 def __init__(   self			:       Union[str, Any]      ,     snake_case_			:       Optional[int]      ,     snake_case_			:       List[str]=1_3      ,     snake_case_			:       Optional[int]=1_0      ,     snake_case_			:       str=3      ,     snake_case_			:       int=2      ,     snake_case_			:       Optional[Any]=2      ,     snake_case_			:       Any=True      ,     snake_case_			:       Optional[int]=True      ,     snake_case_			:       List[Any]=3_2      ,     snake_case_			:       Optional[Any]=5      ,     snake_case_			:       str=4      ,     snake_case_			:       Optional[int]=3_7      ,     snake_case_			:       int="gelu"      ,     snake_case_			:       Dict=0.1      ,     snake_case_			:       Optional[Any]=0.1      ,     snake_case_			:       Dict=1_0      ,     snake_case_			:       List[Any]=0.0_2      ,     snake_case_			:       Dict="divided_space_time"      ,     snake_case_			:       Any=None      ,     ):
      _UpperCAmelCase					=  parent
      _UpperCAmelCase					=  batch_size
      _UpperCAmelCase					=  image_size
      _UpperCAmelCase					=  num_channels
      _UpperCAmelCase					=  patch_size
      _UpperCAmelCase					=  num_frames
      _UpperCAmelCase					=  is_training
      _UpperCAmelCase					=  use_labels
      _UpperCAmelCase					=  hidden_size
      _UpperCAmelCase					=  num_hidden_layers
      _UpperCAmelCase					=  num_attention_heads
      _UpperCAmelCase					=  intermediate_size
      _UpperCAmelCase					=  hidden_act
      _UpperCAmelCase					=  hidden_dropout_prob
      _UpperCAmelCase					=  attention_probs_dropout_prob
      _UpperCAmelCase					=  attention_type
      _UpperCAmelCase					=  initializer_range
      _UpperCAmelCase					=  scope
      _UpperCAmelCase					=  num_labels

      # in TimeSformer, the number of spatial tokens equals num_frames * num_patches per frame + 1 CLS token
      _UpperCAmelCase					=  (image_size // patch_size) ** 2
      _UpperCAmelCase					=  (num_frames) * self.num_patches_per_frame + 1




 def 	lowercase      (   self			:       Tuple       ):
      _UpperCAmelCase					=  floats_tensor(
          [self.batch_size, self.num_frames, self.num_channels, self.image_size, self.image_size]       )

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

      _UpperCAmelCase					=  self.get_config()

      return config, pixel_values, labels




 def 	lowercase      (   self			:       Union[str, Any]       ):
      _UpperCAmelCase					=  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      ,     )
      _UpperCAmelCase					=  self.num_labels
      return config




 def 	lowercase      (   self			:       int      ,     snake_case_			:       Tuple      ,     snake_case_			:       List[Any]      ,     snake_case_			:       int       ):
      _UpperCAmelCase					=  TimesformerModel(config=snake_case_       )
      model.to(snake_case_       )
      model.eval()
      _UpperCAmelCase					=  model(snake_case_       )
      self.parent.assertEqual(result.last_hidden_state.shape      ,     (self.batch_size, self.seq_length, self.hidden_size)       )




 def 	lowercase      (   self			:       Optional[Any]      ,     snake_case_			:       Tuple      ,     snake_case_			:       Dict      ,     snake_case_			:       Any       ):
      _UpperCAmelCase					=  TimesformerForVideoClassification(snake_case_       )
      model.to(snake_case_       )
      model.eval()

      _UpperCAmelCase					=  model(snake_case_       )

      # verify the logits shape
      _UpperCAmelCase					=  torch.Size((self.batch_size, self.num_labels)       )
      self.parent.assertEqual(result.logits.shape      ,     snake_case_       )




 def 	lowercase      (   self			:       Optional[int]       ):
      _UpperCAmelCase					=  self.prepare_config_and_inputs()
      _UpperCAmelCase					=  config_and_inputs
      _UpperCAmelCase					=  {"pixel_values": pixel_values}
      return config, inputs_dict







@require_torch
class     A_      (    __A				,		__A				,		unittest.TestCase     ):
 _lowerCamelCase    :					Optional[int]       			=				(TimesformerModel, TimesformerForVideoClassification) if is_torch_available() else ()
 _lowerCamelCase    :					List[Any]       			=				(
     {"""feature-extraction""": TimesformerModel, """video-classification""": TimesformerForVideoClassification}
     if is_torch_available()
     else {}
 )

 _lowerCamelCase    :					Dict       			=				False
 _lowerCamelCase    :					Any       			=				False
 _lowerCamelCase    :					List[Any]       			=				False
 _lowerCamelCase    :					List[str]       			=				False




 def 	lowercase      (   self			:       int       ):
      _UpperCAmelCase					=  TimesformerModelTester(self       )
      _UpperCAmelCase					=  ConfigTester(
          self      ,     config_class=snake_case_      ,     has_text_modality=snake_case_      ,     hidden_size=3_7       )




 def 	lowercase      (   self			:       Union[str, Any]      ,     snake_case_			:       Union[str, Any]      ,     snake_case_			:       Dict      ,     snake_case_			:       Optional[Any]=False       ):
      _UpperCAmelCase					=  copy.deepcopy(snake_case_       )

      if return_labels:
           if model_class in get_values(snake_case_       ):
                _UpperCAmelCase					=  torch.zeros(
                    self.model_tester.batch_size      ,     dtype=torch.long      ,     device=snake_case_       )

      return inputs_dict




 def 	lowercase      (   self			:       List[str]       ):
      self.config_tester.run_common_tests()




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




 def 	lowercase      (   self			:       Tuple       ):
      _UpperCAmelCase					=  self.model_tester.prepare_config_and_inputs_for_common()

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




 def 	lowercase      (   self			:       List[str]       ):
      _UpperCAmelCase					=  self.model_tester.prepare_config_and_inputs_for_common()

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




 def 	lowercase      (   self			:       Union[str, Any]       ):
      _UpperCAmelCase					=  self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_model(*snake_case_       )




 def 	lowercase      (   self			:       Optional[int]       ):
      _UpperCAmelCase					=  self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_for_video_classification(*snake_case_       )




 @slow
 def 	lowercase      (   self			:       Any       ):

      for model_name in TIMESFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
           _UpperCAmelCase					=  TimesformerModel.from_pretrained(snake_case_       )
           self.assertIsNotNone(snake_case_       )




 def 	lowercase      (   self			:       str       ):

      if not self.has_attentions:
           pass

      else:
           _UpperCAmelCase					=  self.model_tester.prepare_config_and_inputs_for_common()
           _UpperCAmelCase					=  True

           for model_class in self.all_model_classes:
                _UpperCAmelCase					=  self.model_tester.seq_length
                _UpperCAmelCase					=  self.model_tester.num_frames

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

                # check that output_attentions also work using config
                del inputs_dict["output_attentions"]
                _UpperCAmelCase					=  True
                _UpperCAmelCase					=  model_class(snake_case_       )
                model.to(snake_case_       )
                model.eval()
                with torch.no_grad():
                     _UpperCAmelCase					=  model(**self._prepare_for_class(snake_case_      ,     snake_case_       )       )
                _UpperCAmelCase					=  outputs.attentions
                self.assertEqual(len(snake_case_       )      ,     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]      ,     )
                _UpperCAmelCase					=  len(snake_case_       )

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

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

                _UpperCAmelCase					=  outputs.attentions

                self.assertEqual(len(snake_case_       )      ,     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(snake_case_			:       Tuple      ,     snake_case_			:       Dict      ,     snake_case_			:       Tuple       ):
           _UpperCAmelCase					=  model_class(snake_case_       )
           model.to(snake_case_       )
           model.eval()

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

           _UpperCAmelCase					=  outputs.hidden_states
           _UpperCAmelCase					=  self.model_tester.num_hidden_layers + 1
           self.assertEqual(len(snake_case_       )      ,     snake_case_       )

           _UpperCAmelCase					=  self.model_tester.seq_length

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

      _UpperCAmelCase					=  self.model_tester.prepare_config_and_inputs_for_common()

      for model_class in self.all_model_classes:
           _UpperCAmelCase					=  True
           check_hidden_states_output(snake_case_      ,     snake_case_      ,     snake_case_       )

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

           check_hidden_states_output(snake_case_      ,     snake_case_      ,     snake_case_       )





def       UpperCAmelCase_				(   )						->			Tuple:


     '''simple docstring'''



     _UpperCAmelCase					=  hf_hub_download(
         repo_id="hf-internal-testing/spaghetti-video"     ,	filename="eating_spaghetti.npy"     ,	repo_type="dataset"			)
     _UpperCAmelCase					=  np.load(_a			)
     return list(_a			)







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




 @cached_property
 def 	lowercase      (   self			:       int       ):
      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			:       Dict       ):
      _UpperCAmelCase					=  TimesformerForVideoClassification.from_pretrained("facebook/timesformer-base-finetuned-k400"       ).to(
          snake_case_       )

      _UpperCAmelCase					=  self.default_image_processor
      _UpperCAmelCase					=  prepare_video()
      _UpperCAmelCase					=  image_processor(video[:8]      ,     return_tensors="pt"       ).to(snake_case_       )

      # forward pass
      with torch.no_grad():
           _UpperCAmelCase					=  model(**snake_case_       )

      # verify the logits
      _UpperCAmelCase					=  torch.Size((1, 4_0_0)       )
      self.assertEqual(outputs.logits.shape      ,     snake_case_       )

      _UpperCAmelCase					=  torch.tensor([-0.3_0_1_6, -0.7_7_1_3, -0.4_2_0_5]       ).to(snake_case_       )

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







from __future__ import annotations

import math






class _UpperCamelCase				:
			'''simple docstring'''







			def __init__(      self				:			Dict   ,   a				:			int						)				->							None:

				"""simple docstring"""

				SCREAMING_SNAKE_CASE :   Dict					  =							size
				# approximate the overall size of segment tree with given value
				SCREAMING_SNAKE_CASE :   Any					  =							[0 for i in range(0   ,   4 * size						)]
				# create array to store lazy update
				SCREAMING_SNAKE_CASE :   Union[str, Any]					  =							[0 for i in range(0   ,   4 * size						)]
				SCREAMING_SNAKE_CASE :   Any					  =							[0 for i in range(0   ,   4 * size						)]  # flag for lazy update
			def 				__UpperCamelCase			(      self				:			Tuple   ,   a				:			int						)				->							int:

				"""simple docstring"""

				return idx * 2
			def 				__UpperCamelCase			(      self				:			str   ,   a				:			int						)				->							int:

				"""simple docstring"""

				return idx * 2 + 1
			def 				__UpperCamelCase			(      self				:			int   ,   a				:			int   ,   a				:			int   ,   a				:			int   ,   a				:			list[int]						)				->							None:

				"""simple docstring"""

				if left_element == right_element:
					SCREAMING_SNAKE_CASE :   int					  =							a[left_element - 1]
				else:
					SCREAMING_SNAKE_CASE :   Optional[int]					  =							(left_element + right_element) // 2
					self.build(self.left(a						)   ,   a   ,   a   ,   a						)
					self.build(self.right(a						)   ,   mid + 1   ,   a   ,   a						)
					SCREAMING_SNAKE_CASE :   List[Any]					  =							max(
					    self.segment_tree[self.left(a						)]   ,   self.segment_tree[self.right(a						)]						)
			def 				__UpperCamelCase			(      self				:			Optional[Any]   ,   a				:			int   ,   a				:			int   ,   a				:			int   ,   a				:			int   ,   a				:			int   ,   a				:			int						)				->							bool:

				"""simple docstring"""

				if self.flag[idx] is True:
					SCREAMING_SNAKE_CASE :   Any					  =							self.lazy[idx]
					SCREAMING_SNAKE_CASE :   List[str]					  =							False
					if left_element != right_element:
						SCREAMING_SNAKE_CASE :   Optional[Any]					  =							self.lazy[idx]
						SCREAMING_SNAKE_CASE :   int					  =							self.lazy[idx]
						SCREAMING_SNAKE_CASE :   Any					  =							True
						SCREAMING_SNAKE_CASE :   List[Any]					  =							True

				if right_element < a or left_element > b:
					return True
				if left_element >= a and right_element <= b:
					SCREAMING_SNAKE_CASE :   Optional[Any]					  =							val
					if left_element != right_element:
						SCREAMING_SNAKE_CASE :   str					  =							val
						SCREAMING_SNAKE_CASE :   str					  =							val
						SCREAMING_SNAKE_CASE :   Tuple					  =							True
						SCREAMING_SNAKE_CASE :   Optional[Any]					  =							True
					return True
				SCREAMING_SNAKE_CASE :   int					  =							(left_element + right_element) // 2
				self.update(self.left(a						)   ,   a   ,   a   ,   a   ,   a   ,   a						)
				self.update(self.right(a						)   ,   mid + 1   ,   a   ,   a   ,   a   ,   a						)
				SCREAMING_SNAKE_CASE :   Optional[int]					  =							max(
				    self.segment_tree[self.left(a						)]   ,   self.segment_tree[self.right(a						)]						)
				return True
			def 				__UpperCamelCase			(      self				:			Dict   ,   a				:			int   ,   a				:			int   ,   a				:			int   ,   a				:			int   ,   a				:			int						)				->							int | float:

				"""simple docstring"""

				if self.flag[idx] is True:
					SCREAMING_SNAKE_CASE :   int					  =							self.lazy[idx]
					SCREAMING_SNAKE_CASE :   List[Any]					  =							False
					if left_element != right_element:
						SCREAMING_SNAKE_CASE :   Optional[Any]					  =							self.lazy[idx]
						SCREAMING_SNAKE_CASE :   Optional[Any]					  =							self.lazy[idx]
						SCREAMING_SNAKE_CASE :   Optional[Any]					  =							True
						SCREAMING_SNAKE_CASE :   Union[str, Any]					  =							True
				if right_element < a or left_element > b:
					return -math.inf
				if left_element >= a and right_element <= b:
					return self.segment_tree[idx]
				SCREAMING_SNAKE_CASE :   Dict					  =							(left_element + right_element) // 2
				SCREAMING_SNAKE_CASE :   Tuple					  =							self.query(self.left(a						)   ,   a   ,   a   ,   a   ,   a						)
				SCREAMING_SNAKE_CASE :   Tuple					  =							self.query(self.right(a						)   ,   mid + 1   ,   a   ,   a   ,   a						)
				return max(a   ,   a						)






			def __str__(      self				:			str						)				->							str:

				"""simple docstring"""

				return str([self.query(1   ,   1   ,   self.size   ,   a   ,   a						) for i in range(1   ,   self.size + 1						)]						)


if __name__ == "__main__":
			a_      =     [1, 2, -4, 7, 3, -5, 6, 11, -20, 9, 14, 15, 5, 2, -8]
			a_      =     15
			a_      =     SegmentTree(size)
			segt.build(1, 1, size, A)
			print(segt.query(1, 1, size, 4, 6))
			print(segt.query(1, 1, size, 7, 11))
			print(segt.query(1, 1, size, 7, 12))
			segt.update(1, 1, size, 1, 3, 111)
			print(segt.query(1, 1, size, 1, 15))
			segt.update(1, 1, size, 7, 8, 235)
			print(segt)