


"""simple docstring"""




from __future__ import annotations

import inspect
import unittest

import numpy as np

from transformers import DeiTConfig
from transformers.testing_utils import require_tf, require_vision, slow
from transformers.utils import cached_property, is_tf_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
			import tensorflow as tf

			from transformers import (
			    TFDeiTForImageClassification,
			    TFDeiTForImageClassificationWithTeacher,
			    TFDeiTForMaskedImageModeling,
			    TFDeiTModel,
			)
			from transformers.models.deit.modeling_tf_deit import TF_DEIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
			from PIL import Image

			from transformers import DeiTImageProcessor


class 	_a							:

							def __init__(							self:     Optional[int]   ,						UpperCamelCase_:     List[Any]   ,						UpperCamelCase_:     Any=13   ,						UpperCamelCase_:     List[str]=30   ,						UpperCamelCase_:     List[str]=2   ,						UpperCamelCase_:     Dict=3   ,						UpperCamelCase_:     Optional[Any]=True   ,						UpperCamelCase_:     Dict=True   ,						UpperCamelCase_:     Optional[int]=32   ,						UpperCamelCase_:     int=2   ,						UpperCamelCase_:     Any=4   ,						UpperCamelCase_:     List[Any]=37   ,						UpperCamelCase_:     Optional[int]="gelu"   ,						UpperCamelCase_:     Tuple=0.1   ,						UpperCamelCase_:     Union[str, Any]=0.1   ,						UpperCamelCase_:     str=10   ,						UpperCamelCase_:     Tuple=0.02   ,						UpperCamelCase_:     List[Any]=3   ,						UpperCamelCase_:     Tuple=None   ,						UpperCamelCase_:     Optional[Any]=2   ,						)      ->       Dict:





									"""simple docstring"""







									lowercase__						=				parent
									lowercase__						=				batch_size
									lowercase__						=				image_size
									lowercase__						=				patch_size
									lowercase__						=				num_channels
									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__						=				scope
									lowercase__						=				encoder_stride

									# in DeiT, the seq length equals the number of patches + 2 (we add 2 for the [CLS] and distilation tokens)
									lowercase__						=				(image_size // patch_size) ** 2
									lowercase__						=				num_patches + 2

							def 				lowerCamelCase_			(							self:     int							)      ->       int:





									"""simple docstring"""







									lowercase__						=				floats_tensor([self.batch_size, 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 				lowerCamelCase_			(							self:     str							)      ->       Dict:





									"""simple docstring"""







									return DeiTConfig(
									    image_size=self.image_size   ,						patch_size=self.patch_size   ,						num_channels=self.num_channels   ,						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   ,						encoder_stride=self.encoder_stride   ,						)

							def 				lowerCamelCase_			(							self:     Optional[int]   ,						UpperCamelCase_:     List[str]   ,						UpperCamelCase_:     Any   ,						UpperCamelCase_:     Optional[Any]							)      ->       Optional[int]:





									"""simple docstring"""







									lowercase__						=				TFDeiTModel(config=_A							)
									lowercase__						=				model(_A							)
									self.parent.assertEqual(result.last_hidden_state.shape   ,						(self.batch_size, self.seq_length, self.hidden_size)							)

							def 				lowerCamelCase_			(							self:     Tuple   ,						UpperCamelCase_:     List[str]   ,						UpperCamelCase_:     Any   ,						UpperCamelCase_:     Any							)      ->       Any:





									"""simple docstring"""







									lowercase__						=				TFDeiTForMaskedImageModeling(config=_A							)
									lowercase__						=				model(_A							)
									self.parent.assertEqual(
									    result.reconstruction.shape   ,						(self.batch_size, self.num_channels, self.image_size, self.image_size)							)

									# test greyscale images
									lowercase__						=				1
									lowercase__						=				TFDeiTForMaskedImageModeling(_A							)

									lowercase__						=				floats_tensor([self.batch_size, 1, self.image_size, self.image_size]							)
									lowercase__						=				model(_A							)
									self.parent.assertEqual(result.reconstruction.shape   ,						(self.batch_size, 1, self.image_size, self.image_size)							)

							def 				lowerCamelCase_			(							self:     Union[str, Any]   ,						UpperCamelCase_:     Dict   ,						UpperCamelCase_:     Union[str, Any]   ,						UpperCamelCase_:     Union[str, Any]							)      ->       Optional[int]:





									"""simple docstring"""







									lowercase__						=				self.type_sequence_label_size
									lowercase__						=				TFDeiTForImageClassification(_A							)
									lowercase__						=				model(_A   ,						labels=_A							)
									self.parent.assertEqual(result.logits.shape   ,						(self.batch_size, self.type_sequence_label_size)							)

									# test greyscale images
									lowercase__						=				1
									lowercase__						=				TFDeiTForImageClassification(_A							)

									lowercase__						=				floats_tensor([self.batch_size, 1, self.image_size, self.image_size]							)
									lowercase__						=				model(_A   ,						labels=_A							)
									self.parent.assertEqual(result.logits.shape   ,						(self.batch_size, self.type_sequence_label_size)							)


							def 				lowerCamelCase_			(							self:     List[Any]							)      ->       Tuple:





									"""simple docstring"""







									lowercase__						=				self.prepare_config_and_inputs()
									lowercase__					,		lowercase__					,		lowercase__						=				config_and_inputs
									lowercase__						=				{'''pixel_values''': pixel_values}
									return config, inputs_dict


@require_tf
class 	_a							(      snake_case__					,     snake_case__					,     unittest.TestCase      ):
							_lowercase     :      Optional[Any]  				=			(
							    (
							        TFDeiTModel,
							        TFDeiTForImageClassification,
							        TFDeiTForImageClassificationWithTeacher,
							        TFDeiTForMaskedImageModeling,
							    )
							    if is_tf_available()
							    else ()
							)
							_lowercase     :      Optional[Any]  				=			(
							    {
							        """feature-extraction""": TFDeiTModel,
							        """image-classification""": (TFDeiTForImageClassification, TFDeiTForImageClassificationWithTeacher),
							    }
							    if is_tf_available()
							    else {}
							)

							_lowercase     :      str  				=			False
							_lowercase     :      str  				=			False
							_lowercase     :      List[str]  				=			False
							_lowercase     :      Optional[int]  				=			False

							def 				lowerCamelCase_			(							self:     Any							)      ->       str:





									"""simple docstring"""







									lowercase__						=				TFDeiTModelTester(self							)
									lowercase__						=				ConfigTester(self   ,						config_class=_A   ,						has_text_modality=_A   ,						hidden_size=37							)

							def 				lowerCamelCase_			(							self:     List[str]							)      ->       int:





									"""simple docstring"""







									self.config_tester.run_common_tests()

							@unittest.skip(reason='''DeiT does not use inputs_embeds'''							)
							def 				lowerCamelCase_			(							self:     List[Any]							)      ->       Tuple:





									"""simple docstring"""







									pass

							def 				lowerCamelCase_			(							self:     Optional[Any]							)      ->       int:





									"""simple docstring"""







									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()   ,						(tf.keras.layers.Layer)							)
											lowercase__						=				model.get_output_embeddings()
											self.assertTrue(x is None or isinstance(_A   ,						tf.keras.layers.Dense							)							)

							def 				lowerCamelCase_			(							self:     Optional[int]							)      ->       Tuple:





									"""simple docstring"""







									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.call							)
											# 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 				lowerCamelCase_			(							self:     List[Any]							)      ->       List[Any]:





									"""simple docstring"""







									lowercase__						=				self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_model(*_A							)

							def 				lowerCamelCase_			(							self:     Dict							)      ->       int:





									"""simple docstring"""







									lowercase__						=				self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_for_masked_image_modeling(*_A							)

							def 				lowerCamelCase_			(							self:     Tuple							)      ->       Any:





									"""simple docstring"""







									lowercase__						=				self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_for_image_classification(*_A							)

							def 				lowerCamelCase_			(							self:     Any   ,						UpperCamelCase_:     Tuple   ,						UpperCamelCase_:     Optional[Any]   ,						UpperCamelCase_:     Any=False							)      ->       Union[str, Any]:





									"""simple docstring"""







									lowercase__						=				super()._prepare_for_class(_A   ,						_A   ,						return_labels=_A							)

									if return_labels:
											if "labels" in inputs_dict and "labels" not in inspect.signature(model_class.call							).parameters:
													del inputs_dict["labels"]

									return inputs_dict


							@slow
							def 				lowerCamelCase_			(							self:     Tuple							)      ->       Union[str, Any]:





									"""simple docstring"""







									for model_name in TF_DEIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
											lowercase__						=				TFDeiTModel.from_pretrained(_A							)
											self.assertIsNotNone(_A							)
def       _a			(				):


		"""simple docstring"""




		lowercase__						=				Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''					)
		return image


@require_tf
@require_vision
class 	_a							(      unittest.TestCase      ):

							@cached_property
							def 				lowerCamelCase_			(							self:     List[Any]							)      ->       List[Any]:





									"""simple docstring"""







									return (
									    DeiTImageProcessor.from_pretrained('''facebook/deit-base-distilled-patch16-224'''							)
									    if is_vision_available()
									    else None
									)


							@slow
							def 				lowerCamelCase_			(							self:     Dict							)      ->       Dict:





									"""simple docstring"""







									lowercase__						=				TFDeiTForImageClassificationWithTeacher.from_pretrained('''facebook/deit-base-distilled-patch16-224'''							)

									lowercase__						=				self.default_image_processor
									lowercase__						=				prepare_img()
									lowercase__						=				image_processor(images=_A   ,						return_tensors='''tf'''							)

									# forward pass
									lowercase__						=				model(**_A							)

									# verify the logits
									lowercase__						=				tf.TensorShape((1, 1_000)							)
									self.assertEqual(outputs.logits.shape   ,						_A							)

									lowercase__						=				tf.constant([-1.0266, 0.1912, -1.2861]							)

									self.assertTrue(np.allclose(outputs.logits[0, :3]   ,						_A   ,						atol=1E-4							)							)






from collections.abc import Sequence
from queue import Queue


class 	_a							:

							def __init__(							self:     Tuple   ,						UpperCamelCase_:     Optional[int]   ,						UpperCamelCase_:     int   ,						UpperCamelCase_:     Optional[Any]   ,						UpperCamelCase_:     Union[str, Any]=None   ,						UpperCamelCase_:     Dict=None							)      ->       Tuple:





									"""simple docstring"""







									lowercase__						=				start
									lowercase__						=				end
									lowercase__						=				val
									lowercase__						=				(start + end) // 2
									lowercase__						=				left
									lowercase__						=				right


							def __repr__(							self:     Optional[int]							)      ->       Optional[Any]:





									"""simple docstring"""







									return f'SegmentTreeNode(start={self.start}, end={self.end}, val={self.val})'


class 	_a							:

							def __init__(							self:     Any   ,						UpperCamelCase_:     Sequence   ,						UpperCamelCase_:     Any							)      ->       List[str]:





									"""simple docstring"""







									lowercase__						=				collection
									lowercase__						=				function
									if self.collection:
											lowercase__						=				self._build_tree(0   ,						len(UpperCamelCase_							) - 1							)

							def 				lowerCamelCase_			(							self:     int   ,						UpperCamelCase_:     Union[str, Any]   ,						UpperCamelCase_:     Union[str, Any]							)      ->       Union[str, Any]:





									"""simple docstring"""







									self._update_tree(self.root   ,						UpperCamelCase_   ,						UpperCamelCase_							)

							def 				lowerCamelCase_			(							self:     str   ,						UpperCamelCase_:     int   ,						UpperCamelCase_:     List[str]							)      ->       Optional[Any]:





									"""simple docstring"""







									return self._query_range(self.root   ,						UpperCamelCase_   ,						UpperCamelCase_							)

							def 				lowerCamelCase_			(							self:     List[str]   ,						UpperCamelCase_:     Tuple   ,						UpperCamelCase_:     Dict							)      ->       str:





									"""simple docstring"""







									if start == end:
											return SegmentTreeNode(UpperCamelCase_   ,						UpperCamelCase_   ,						self.collection[start]							)
									lowercase__						=				(start + end) // 2
									lowercase__						=				self._build_tree(UpperCamelCase_   ,						UpperCamelCase_							)
									lowercase__						=				self._build_tree(mid + 1   ,						UpperCamelCase_							)
									return SegmentTreeNode(UpperCamelCase_   ,						UpperCamelCase_   ,						self.fn(left.val   ,						right.val							)   ,						UpperCamelCase_   ,						UpperCamelCase_							)

							def 				lowerCamelCase_			(							self:     List[Any]   ,						UpperCamelCase_:     Dict   ,						UpperCamelCase_:     Tuple   ,						UpperCamelCase_:     Union[str, Any]							)      ->       Dict:





									"""simple docstring"""







									if node.start == i and node.end == i:
											lowercase__						=				val
											return
									if i <= node.mid:
											self._update_tree(node.left   ,						UpperCamelCase_   ,						UpperCamelCase_							)
									else:
											self._update_tree(node.right   ,						UpperCamelCase_   ,						UpperCamelCase_							)
									lowercase__						=				self.fn(node.left.val   ,						node.right.val							)

							def 				lowerCamelCase_			(							self:     List[Any]   ,						UpperCamelCase_:     str   ,						UpperCamelCase_:     Dict   ,						UpperCamelCase_:     Dict							)      ->       List[Any]:





									"""simple docstring"""







									if node.start == i and node.end == j:
											return node.val

									if i <= node.mid:
											if j <= node.mid:
													# range in left child tree
													return self._query_range(node.left   ,						UpperCamelCase_   ,						UpperCamelCase_							)
											else:
													# range in left child tree and right child tree
													return self.fn(
													    self._query_range(node.left   ,						UpperCamelCase_   ,						node.mid							)   ,						self._query_range(node.right   ,						node.mid + 1   ,						UpperCamelCase_							)   ,						)
									else:
											# range in right child tree
											return self._query_range(node.right   ,						UpperCamelCase_   ,						UpperCamelCase_							)


							def 				lowerCamelCase_			(							self:     Optional[int]							)      ->       str:





									"""simple docstring"""







									if self.root is not None:
											lowercase__						=				Queue()
											queue.put(self.root							)
											while not queue.empty():
													lowercase__						=				queue.get()
													yield node

													if node.left is not None:
															queue.put(node.left							)

													if node.right is not None:
															queue.put(node.right							)


if __name__ == "__main__":
			import operator

			for fn in [operator.add, max, min]:
						print('*' * 50)
						lowerCAmelCase	=							SegmentTree([2, 1, 5, 3, 4], fn)
						for node in arr.traverse():
									print(node)
						print()

						arr.update(1, 5)
						for node in arr.traverse():
									print(node)
						print()

						print(arr.query_range(3, 4))  # 7
						print(arr.query_range(2, 2))  # 5
						print(arr.query_range(1, 3))  # 13
						print()


