





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




		def __init__(self      :	Any							,			A__      :	List[Any]							,			A__      :	str=1_3							,			A__      :	Union[str, Any]=1_0							,			A__      :	Tuple=3							,			A__      :	Tuple=2							,			A__      :	List[str]=2							,			A__      :	Any=2							,			A__      :	Optional[int]=True							,			A__      :	Dict=True							,			A__      :	List[str]=3_2							,			A__      :	Dict=5							,			A__      :	List[Any]=4							,			A__      :	List[str]=3_7							,			A__      :	str="gelu"							,			A__      :	List[str]=0.1							,			A__      :	Tuple=0.1							,			A__      :	Dict=1_0							,			A__      :	List[str]=0.0_2							,			A__      :	str=0.9							,			A__      :	Dict=None							,			)					-> Tuple:
						lowercase         = parent
						lowercase         = batch_size
						lowercase         = image_size
						lowercase         = num_channels
						lowercase         = patch_size
						lowercase         = tubelet_size
						lowercase         = num_frames
						lowercase         = is_training
						lowercase         = use_labels
						lowercase         = hidden_size
						lowercase         = num_hidden_layers
						lowercase         = num_attention_heads
						lowercase         = intermediate_size
						lowercase         = hidden_act
						lowercase         = hidden_dropout_prob
						lowercase         = attention_probs_dropout_prob
						lowercase         = type_sequence_label_size
						lowercase         = initializer_range
						lowercase         = mask_ratio
						lowercase         = scope

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

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




		def 				UpperCAmelCase__   (self      :	Optional[int]				)					-> Tuple:
						lowercase         = floats_tensor(
						    [self.batch_size, self.num_frames, self.num_channels, self.image_size, self.image_size]				)

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

						lowercase         = self.get_config()

						return config, pixel_values, labels




		def 				UpperCAmelCase__   (self      :	Optional[Any]				)					-> str:
						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=A__							,			initializer_range=self.initializer_range							,			)




		def 				UpperCAmelCase__   (self      :	str							,			A__      :	Union[str, Any]							,			A__      :	str							,			A__      :	Optional[Any]				)					-> int:
						lowercase         = VideoMAEModel(config=A__				)
						model.to(A__				)
						model.eval()
						lowercase         = model(A__				)
						self.parent.assertEqual(result.last_hidden_state.shape							,			(self.batch_size, self.seq_length, self.hidden_size)				)




		def 				UpperCAmelCase__   (self      :	Dict							,			A__      :	Optional[int]							,			A__      :	str							,			A__      :	int				)					-> Optional[int]:
						lowercase         = VideoMAEForPreTraining(A__				)
						model.to(A__				)
						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
						lowercase         = torch.ones((self.num_masks,)				)
						lowercase         = torch.cat([mask, torch.zeros(self.seq_length - mask.size(0				)				)]				)
						lowercase         = mask.expand(self.batch_size							,			-1				).bool()

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





		def 				UpperCAmelCase__   (self      :	List[Any]				)					-> Any:
						lowercase         = self.prepare_config_and_inputs()
						lowercase   ,							lowercase   ,							lowercase         = config_and_inputs
						lowercase         = {"pixel_values": pixel_values}
						return config, inputs_dict




@require_torch
class       UpperCAmelCase (						_lowercase			,       _lowercase			,       unittest.TestCase  ):
		UpperCAmelCase					:	Any 			=		(
		    (VideoMAEModel, VideoMAEForPreTraining, VideoMAEForVideoClassification) if is_torch_available() else ()
		)
		UpperCAmelCase					:	str 			=		(
		    {'''feature-extraction''': VideoMAEModel, '''video-classification''': VideoMAEForVideoClassification}
		    if is_torch_available()
		    else {}
		)

		UpperCAmelCase					:	List[str] 			=		False
		UpperCAmelCase					:	int 			=		False
		UpperCAmelCase					:	Tuple 			=		False
		UpperCAmelCase					:	int 			=		False




		def 				UpperCAmelCase__   (self      :	Optional[int]				)					-> Optional[Any]:
						lowercase         = VideoMAEModelTester(self				)
						lowercase         = ConfigTester(self							,			config_class=A__							,			has_text_modality=A__							,			hidden_size=3_7				)




		def 				UpperCAmelCase__   (self      :	List[Any]							,			A__      :	Dict							,			A__      :	Any							,			A__      :	Tuple=False				)					-> Tuple:
						lowercase         = copy.deepcopy(A__				)

						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
										lowercase         = torch.ones((self.model_tester.num_masks,)				)
										lowercase         = torch.cat([mask, torch.zeros(self.model_tester.seq_length - mask.size(0				)				)]				)
										lowercase         = mask.expand(self.model_tester.batch_size							,			-1				).bool()
										lowercase         = bool_masked_pos.to(A__				)

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

						return inputs_dict




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




		@unittest.skip(reason="VideoMAE does not use inputs_embeds"				)
		def 				UpperCAmelCase__   (self      :	List[Any]				)					-> Optional[int]:
						pass




		def 				UpperCAmelCase__   (self      :	Dict				)					-> Union[str, Any]:
						lowercase   ,							lowercase         = self.model_tester.prepare_config_and_inputs_for_common()

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




		def 				UpperCAmelCase__   (self      :	Tuple				)					-> Any:
						lowercase   ,							lowercase         = self.model_tester.prepare_config_and_inputs_for_common()

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

										lowercase         = ["pixel_values"]
										self.assertListEqual(arg_names[:1]							,			A__				)




		def 				UpperCAmelCase__   (self      :	Optional[int]				)					-> Optional[int]:
						lowercase         = self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_model(*A__				)




		def 				UpperCAmelCase__   (self      :	Optional[Any]				)					-> Tuple:
						lowercase         = self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_for_pretraining(*A__				)




		@slow
		def 				UpperCAmelCase__   (self      :	Any				)					-> Any:
						for model_name in VIDEOMAE_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
										lowercase         = VideoMAEModel.from_pretrained(A__				)
										self.assertIsNotNone(A__				)




		def 				UpperCAmelCase__   (self      :	Optional[int]				)					-> List[str]:
						if not self.has_attentions:
										pass

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

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

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

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

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

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

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

														lowercase         = outputs.attentions

														self.assertEqual(len(A__				)							,			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 				UpperCAmelCase__   (self      :	Tuple				)					-> List[Any]:
						def check_hidden_states_output(A__      :	List[Any]							,			A__      :	Optional[Any]							,			A__      :	Tuple				):
										lowercase         = model_class(A__				)
										model.to(A__				)
										model.eval()

										with torch.no_grad():
														lowercase         = model(**self._prepare_for_class(A__							,			A__				)				)

										lowercase         = outputs.hidden_states
										lowercase         = self.model_tester.num_hidden_layers + 1
										self.assertEqual(len(A__				)							,			A__				)

										lowercase         = self.model_tester.seq_length - self.model_tester.num_masks
										lowercase         = 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]							,			)

						lowercase   ,							lowercase         = self.model_tester.prepare_config_and_inputs_for_common()

						for model_class in self.all_model_classes:
										lowercase         = True
										check_hidden_states_output(A__							,			A__							,			A__				)

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

										check_hidden_states_output(A__							,			A__							,			A__				)





		@unittest.skip("Will be fixed soon by reducing the size of the model used for common tests."				)
		def 				UpperCAmelCase__   (self      :	Optional[int]				)					-> List[Any]:
						pass







def 							UpperCAmelCase_    (	):

				"""simple docstring"""






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


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




		@cached_property
		def 				UpperCAmelCase__   (self      :	Any				)					-> 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 				UpperCAmelCase__   (self      :	List[str]				)					-> Optional[int]:
						lowercase         = VideoMAEForVideoClassification.from_pretrained("MCG-NJU/videomae-base-finetuned-kinetics"				).to(
						    A__				)

						lowercase         = self.default_image_processor
						lowercase         = prepare_video()
						lowercase         = image_processor(A__							,			return_tensors="pt"				).to(A__				)

						# forward pass
						with torch.no_grad():
										lowercase         = model(**A__				)

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

						lowercase         = torch.tensor([0.3_6_6_9, -0.0_6_8_8, -0.2_4_2_1]				).to(A__				)

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





		@slow
		def 				UpperCAmelCase__   (self      :	Union[str, Any]				)					-> List[Any]:
						lowercase         = VideoMAEForPreTraining.from_pretrained("MCG-NJU/videomae-base-short"				).to(A__				)

						lowercase         = self.default_image_processor
						lowercase         = prepare_video()
						lowercase         = image_processor(A__							,			return_tensors="pt"				).to(A__				)

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

						# forward pass
						with torch.no_grad():
										lowercase         = model(**A__				)

						# verify the logits
						lowercase         = torch.Size([1, 1_4_0_8, 1_5_3_6]				)
						lowercase         = torch.tensor(
						    [[0.7_9_9_4, 0.9_6_1_2, 0.8_5_0_8], [0.7_4_0_1, 0.8_9_5_8, 0.8_3_0_2], [0.5_8_6_2, 0.7_4_6_8, 0.7_3_2_5]]							,			device=A__				)
						self.assertEqual(outputs.logits.shape							,			A__				)
						self.assertTrue(torch.allclose(outputs.logits[0, :3, :3]							,			A__							,			atol=1e-4				)				)

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

						# verify the loss (`config.norm_pix_loss` = `False`)
						lowercase         = VideoMAEForPreTraining.from_pretrained("MCG-NJU/videomae-base-short"							,			norm_pix_loss=A__				).to(
						    A__				)

						with torch.no_grad():
										lowercase         = model(**A__				)

						lowercase         = torch.tensor(torch.tensor([0.6_4_6_9]				)							,			device=A__				)
						self.assertTrue(torch.allclose(outputs.loss							,			A__							,			atol=1e-4				)				)











'''simple docstring'''

from __future__ import annotations

from collections import deque
from collections.abc import Sequence
from dataclasses import dataclass
from typing import Any

@dataclass
class       UpperCAmelCase :
		UpperCAmelCase					:	int
		UpperCAmelCase					:	Node | None 			=		None
		UpperCAmelCase					:	Node | None 			=		None







def 							UpperCAmelCase_    (	):

				"""simple docstring"""






				lowercase         = Node(1							)
				lowercase         = Node(2							)
				lowercase         = Node(3							)
				lowercase         = Node(4							)
				lowercase         = Node(5							)
				return tree







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return [root.data, *preorder(root.left							), *preorder(root.right							)] if root else []







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return postorder(root.left							) + postorder(root.right							) + [root.data] if root else []







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return [*inorder(root.left							), root.data, *inorder(root.right							)] if root else []







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				return (max(height(root.left							)		,							height(root.right							)							) + 1) if root else 0







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				lowercase         = []

				if root is None:
								return output

				lowercase         = deque([root]							)

				while process_queue:
								lowercase         = process_queue.popleft()
								output.append(node.data							)

								if node.left:
												process_queue.append(node.left							)
								if node.right:
												process_queue.append(node.right							)
				return output







def 							UpperCAmelCase_    (	lowerCAmelCase_		,							lowerCAmelCase_							):

				"""simple docstring"""






				lowercase         = []

				def populate_output(lowerCAmelCase_		,							lowerCAmelCase_							) -> None:
								if not root:
												return
								if level == 1:
												output.append(root.data							)
								elif level > 1:
												populate_output(root.left		,							level - 1							)
												populate_output(root.right		,							level - 1							)

				populate_output(lowerCAmelCase_		,							lowerCAmelCase_							)
				return output







def 							UpperCAmelCase_    (	lowerCAmelCase_		,							lowerCAmelCase_							):

				"""simple docstring"""






				lowercase         = []

				def populate_output(lowerCAmelCase_		,							lowerCAmelCase_							) -> None:
								if root is None:
												return
								if level == 1:
												output.append(root.data							)
								elif level > 1:
												populate_output(root.right		,							level - 1							)
												populate_output(root.left		,							level - 1							)

				populate_output(lowerCAmelCase_		,							lowerCAmelCase_							)
				return output







def 							UpperCAmelCase_    (	lowerCAmelCase_							):

				"""simple docstring"""






				if root is None:
								return []

				lowercase         = []

				lowercase         = 0
				lowercase         = height(lowerCAmelCase_							)

				for h in range(1		,							height_tree + 1							):
								if not flag:
												output.append(get_nodes_from_left_to_right(lowerCAmelCase_		,							lowerCAmelCase_							)							)
												lowercase         = 1
								else:
												output.append(get_nodes_from_right_to_left(lowerCAmelCase_		,							lowerCAmelCase_							)							)
												lowercase         = 0

				return output







def 							UpperCAmelCase_    (	):  # Main function for testing.

				"""simple docstring"""






				lowercase         = make_tree()
				print(f'In-order Traversal: {inorder(lowerCAmelCase_							)}'							)
				print(f'Pre-order Traversal: {preorder(lowerCAmelCase_							)}'							)
				print(f'Post-order Traversal: {postorder(lowerCAmelCase_							)}'		,							"\n"							)

				print(f'Height of Tree: {height(lowerCAmelCase_							)}'		,							"\n"							)

				print("Complete Level Order Traversal: "							)
				print(level_order(lowerCAmelCase_							)		,							"\n"							)

				print("Level-wise order Traversal: "							)

				for level in range(1		,							height(lowerCAmelCase_							) + 1							):
								print(f'Level {level}:'		,							get_nodes_from_left_to_right(lowerCAmelCase_		,							level=lowerCAmelCase_							)							)

				print("\nZigZag order Traversal: "							)
				print(zigzag(lowerCAmelCase_							)							)


if __name__ == "__main__":
			import doctest

			doctest.testmod()
			main()




