


'''simple docstring'''




class 		UpperCAmelCase_      :





     def __init__( self       :      List[str]    ,      UpperCAmelCase__       :      list[int]    )				->  None:
        lowerCAmelCase     =			len(UpperCAmelCase__    )
        lowerCAmelCase     =			[0] * len_array

        if len_array > 0:
           lowerCAmelCase     =			array[0]

        for i in range(1    ,      UpperCAmelCase__    ):
           lowerCAmelCase     =			self.prefix_sum[i - 1] + array[i]





     def 							__UpperCAmelCase      ( self       :      Optional[Any]    ,      UpperCAmelCase__       :      int    ,      UpperCAmelCase__       :      int    )				->  int:
        if start == 0:
           return self.prefix_sum[end]

        return self.prefix_sum[end] - self.prefix_sum[start - 1]





     def 							__UpperCAmelCase      ( self       :      int    ,      UpperCAmelCase__       :      int    )				->  bool:
        lowerCAmelCase     =			{0}
        for sum_item in self.prefix_sum:
           if sum_item - target_sum in sums:
              return True

           sums.add(UpperCAmelCase__    )

        return False


if __name__ == "__main__":
       import doctest

       doctest.testmod()








import inspect
import unittest

from transformers import ViTConfig
from transformers.testing_utils import (
    require_accelerate,
    require_torch,
    require_torch_gpu,
    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 ViTForImageClassification, ViTForMaskedImageModeling, ViTModel
						from transformers.models.vit.modeling_vit import VIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
						from PIL import Image

						from transformers import ViTImageProcessor



class   __lowercase				:




			"""simple docstring"""







			def __init__( self  :     Any   ,						lowerCAmelCase__  :     Union[str, Any]   ,						lowerCAmelCase__  :     Any=13   ,						lowerCAmelCase__  :     Tuple=30   ,						lowerCAmelCase__  :     List[str]=2   ,						lowerCAmelCase__  :     int=3   ,						lowerCAmelCase__  :     Optional[int]=True   ,						lowerCAmelCase__  :     List[str]=True   ,						lowerCAmelCase__  :     str=32   ,						lowerCAmelCase__  :     Any=5   ,						lowerCAmelCase__  :     str=4   ,						lowerCAmelCase__  :     int=37   ,						lowerCAmelCase__  :     Optional[Any]="gelu"   ,						lowerCAmelCase__  :     Optional[int]=0.1   ,						lowerCAmelCase__  :     Dict=0.1   ,						lowerCAmelCase__  :     Tuple=10   ,						lowerCAmelCase__  :     Optional[Any]=0.02   ,						lowerCAmelCase__  :     List[str]=None   ,						lowerCAmelCase__  :     Union[str, Any]=2   ,						):
									SCREAMING_SNAKE_CASE_: str  		=       parent
									SCREAMING_SNAKE_CASE_: Optional[Any]  		=       batch_size
									SCREAMING_SNAKE_CASE_: str  		=       image_size
									SCREAMING_SNAKE_CASE_: Tuple  		=       patch_size
									SCREAMING_SNAKE_CASE_: int  		=       num_channels
									SCREAMING_SNAKE_CASE_: List[str]  		=       is_training
									SCREAMING_SNAKE_CASE_: str  		=       use_labels
									SCREAMING_SNAKE_CASE_: int  		=       hidden_size
									SCREAMING_SNAKE_CASE_: List[Any]  		=       num_hidden_layers
									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       num_attention_heads
									SCREAMING_SNAKE_CASE_: Any  		=       intermediate_size
									SCREAMING_SNAKE_CASE_: str  		=       hidden_act
									SCREAMING_SNAKE_CASE_: str  		=       hidden_dropout_prob
									SCREAMING_SNAKE_CASE_: List[str]  		=       attention_probs_dropout_prob
									SCREAMING_SNAKE_CASE_: int  		=       type_sequence_label_size
									SCREAMING_SNAKE_CASE_: Dict  		=       initializer_range
									SCREAMING_SNAKE_CASE_: Dict  		=       scope
									SCREAMING_SNAKE_CASE_: Dict  		=       encoder_stride

									# in ViT, the seq length equals the number of patches + 1 (we add 1 for the [CLS] token)
									SCREAMING_SNAKE_CASE_: List[Any]  		=       (image_size // patch_size) ** 2
									SCREAMING_SNAKE_CASE_: Dict  		=       num_patches + 1



			def        _SCREAMING_SNAKE_CASE			( self  :     Union[str, Any]):
									SCREAMING_SNAKE_CASE_: Optional[int]  		=       floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size])

									SCREAMING_SNAKE_CASE_: str  		=       None
									if self.use_labels:
															SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       ids_tensor([self.batch_size]   ,						self.type_sequence_label_size)

									SCREAMING_SNAKE_CASE_: Optional[Any]  		=       self.get_config()

									return config, pixel_values, labels



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[int]):
									return ViTConfig(
									    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=lowerCAmelCase__   ,						initializer_range=self.initializer_range   ,						encoder_stride=self.encoder_stride   ,						)



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[Any]   ,						lowerCAmelCase__  :     int   ,						lowerCAmelCase__  :     int   ,						lowerCAmelCase__  :     Tuple):
									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       ViTModel(config=lowerCAmelCase__)
									model.to(lowerCAmelCase__)
									model.eval()
									SCREAMING_SNAKE_CASE_: Optional[int]  		=       model(lowerCAmelCase__)
									self.parent.assertEqual(result.last_hidden_state.shape   ,						(self.batch_size, self.seq_length, self.hidden_size))



			def        _SCREAMING_SNAKE_CASE			( self  :     Union[str, Any]   ,						lowerCAmelCase__  :     Optional[Any]   ,						lowerCAmelCase__  :     Tuple   ,						lowerCAmelCase__  :     Dict):
									SCREAMING_SNAKE_CASE_: Optional[int]  		=       ViTForMaskedImageModeling(config=lowerCAmelCase__)
									model.to(lowerCAmelCase__)
									model.eval()
									SCREAMING_SNAKE_CASE_: str  		=       model(lowerCAmelCase__)
									self.parent.assertEqual(
									    result.reconstruction.shape   ,						(self.batch_size, self.num_channels, self.image_size, self.image_size))

									# test greyscale images
									SCREAMING_SNAKE_CASE_: Dict  		=       1
									SCREAMING_SNAKE_CASE_: List[str]  		=       ViTForMaskedImageModeling(lowerCAmelCase__)
									model.to(lowerCAmelCase__)
									model.eval()

									SCREAMING_SNAKE_CASE_: List[str]  		=       floats_tensor([self.batch_size, 1, self.image_size, self.image_size])
									SCREAMING_SNAKE_CASE_: str  		=       model(lowerCAmelCase__)
									self.parent.assertEqual(result.reconstruction.shape   ,						(self.batch_size, 1, self.image_size, self.image_size))



			def        _SCREAMING_SNAKE_CASE			( self  :     Any   ,						lowerCAmelCase__  :     List[str]   ,						lowerCAmelCase__  :     List[str]   ,						lowerCAmelCase__  :     Union[str, Any]):
									SCREAMING_SNAKE_CASE_: Tuple  		=       self.type_sequence_label_size
									SCREAMING_SNAKE_CASE_: List[str]  		=       ViTForImageClassification(lowerCAmelCase__)
									model.to(lowerCAmelCase__)
									model.eval()
									SCREAMING_SNAKE_CASE_: Any  		=       model(lowerCAmelCase__   ,						labels=lowerCAmelCase__)
									self.parent.assertEqual(result.logits.shape   ,						(self.batch_size, self.type_sequence_label_size))

									# test greyscale images
									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       1
									SCREAMING_SNAKE_CASE_: List[str]  		=       ViTForImageClassification(lowerCAmelCase__)
									model.to(lowerCAmelCase__)
									model.eval()

									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       floats_tensor([self.batch_size, 1, self.image_size, self.image_size])
									SCREAMING_SNAKE_CASE_: Dict  		=       model(lowerCAmelCase__)
									self.parent.assertEqual(result.logits.shape   ,						(self.batch_size, self.type_sequence_label_size))




			def        _SCREAMING_SNAKE_CASE			( self  :     List[Any]):
									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       self.prepare_config_and_inputs()
									(
									    (
									    SCREAMING_SNAKE_CASE_
									)		,    (
									    SCREAMING_SNAKE_CASE_
									)		,    (
									    SCREAMING_SNAKE_CASE_
									)		,    
									): List[str]  		=       config_and_inputs
									SCREAMING_SNAKE_CASE_: Optional[Any]  		=       {"pixel_values": pixel_values}
									return config, inputs_dict







@require_torch
class   __lowercase				( UpperCAmelCase_		,       UpperCAmelCase_		,       unittest.TestCase	):




			"""simple docstring"""







			_UpperCAmelCase   :							List[Any]										=     (
			    (
			        ViTModel,
			        ViTForImageClassification,
			        ViTForMaskedImageModeling,
			    )
			    if is_torch_available()
			    else ()
			)
			_UpperCAmelCase   :							Tuple										=     (
			    {'''feature-extraction''': ViTModel, '''image-classification''': ViTForImageClassification}
			    if is_torch_available()
			    else {}
			)
			_UpperCAmelCase   :							List[str]										=     True

			_UpperCAmelCase   :							List[Any]										=     False
			_UpperCAmelCase   :							Optional[Any]										=     False
			_UpperCAmelCase   :							Tuple										=     False



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[int]):
									SCREAMING_SNAKE_CASE_: List[str]  		=       ViTModelTester(self)
									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       ConfigTester(self   ,						config_class=lowerCAmelCase__   ,						has_text_modality=lowerCAmelCase__   ,						hidden_size=37)



			def        _SCREAMING_SNAKE_CASE			( self  :     Any):
									self.config_tester.run_common_tests()



			@unittest.skip(reason="ViT does not use inputs_embeds")
			def        _SCREAMING_SNAKE_CASE			( self  :     str):
									pass



			def        _SCREAMING_SNAKE_CASE			( self  :     str):
									SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       self.model_tester.prepare_config_and_inputs_for_common()

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



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[int]):
									SCREAMING_SNAKE_CASE_		,    SCREAMING_SNAKE_CASE_: Optional[Any]  		=       self.model_tester.prepare_config_and_inputs_for_common()

									for model_class in self.all_model_classes:
															SCREAMING_SNAKE_CASE_: List[Any]  		=       model_class(lowerCAmelCase__)
															SCREAMING_SNAKE_CASE_: int  		=       inspect.signature(model.forward)
															# signature.parameters is an OrderedDict => so arg_names order is deterministic
															SCREAMING_SNAKE_CASE_: Optional[Any]  		=       [*signature.parameters.keys()]

															SCREAMING_SNAKE_CASE_: Optional[int]  		=       ["pixel_values"]
															self.assertListEqual(arg_names[:1]   ,						lowerCAmelCase__)



			def        _SCREAMING_SNAKE_CASE			( self  :     Union[str, Any]):
									SCREAMING_SNAKE_CASE_: Tuple  		=       self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_model(*lowerCAmelCase__)



			def        _SCREAMING_SNAKE_CASE			( self  :     Optional[Any]):
									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_for_masked_image_modeling(*lowerCAmelCase__)



			def        _SCREAMING_SNAKE_CASE			( self  :     List[str]):
									SCREAMING_SNAKE_CASE_: int  		=       self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_for_image_classification(*lowerCAmelCase__)




			@slow
			def        _SCREAMING_SNAKE_CASE			( self  :     int):
									for model_name in VIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
															SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       ViTModel.from_pretrained(lowerCAmelCase__)
															self.assertIsNotNone(lowerCAmelCase__)







def 			A_      (    ):
						SCREAMING_SNAKE_CASE_: List[Any]  		=       Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"    )
						return image



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




			"""simple docstring"""







			@cached_property
			def        _SCREAMING_SNAKE_CASE			( self  :     int):
									return ViTImageProcessor.from_pretrained("google/vit-base-patch16-224") if is_vision_available() else None



			@slow
			def        _SCREAMING_SNAKE_CASE			( self  :     Union[str, Any]):
									SCREAMING_SNAKE_CASE_: int  		=       ViTForImageClassification.from_pretrained("google/vit-base-patch16-224").to(lowerCAmelCase__)

									SCREAMING_SNAKE_CASE_: Optional[Any]  		=       self.default_image_processor
									SCREAMING_SNAKE_CASE_: str  		=       prepare_img()
									SCREAMING_SNAKE_CASE_: Optional[Any]  		=       image_processor(images=lowerCAmelCase__   ,						return_tensors="pt").to(lowerCAmelCase__)

									# forward pass
									with torch.no_grad():
															SCREAMING_SNAKE_CASE_: Optional[int]  		=       model(**lowerCAmelCase__)

									# verify the logits
									SCREAMING_SNAKE_CASE_: Any  		=       torch.Size((1, 1000))
									self.assertEqual(outputs.logits.shape   ,						lowerCAmelCase__)

									SCREAMING_SNAKE_CASE_: List[Any]  		=       torch.tensor([-0.2744, 0.8215, -0.0836]).to(lowerCAmelCase__)

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



			@slow
			def        _SCREAMING_SNAKE_CASE			( self  :     List[Any]):
									# ViT models have an `interpolate_pos_encoding` argument in their forward method,
									# allowing to interpolate the pre-trained position embeddings in order to use
									# the model on higher resolutions. The DINO model by Facebook AI leverages this
									# to visualize self-attention on higher resolution images.
									SCREAMING_SNAKE_CASE_: str  		=       ViTModel.from_pretrained("facebook/dino-vits8").to(lowerCAmelCase__)

									SCREAMING_SNAKE_CASE_: List[Any]  		=       ViTImageProcessor.from_pretrained("facebook/dino-vits8"   ,						size=480)
									SCREAMING_SNAKE_CASE_: List[Any]  		=       prepare_img()
									SCREAMING_SNAKE_CASE_: List[Any]  		=       image_processor(images=lowerCAmelCase__   ,						return_tensors="pt")
									SCREAMING_SNAKE_CASE_: int  		=       inputs.pixel_values.to(lowerCAmelCase__)

									# forward pass
									with torch.no_grad():
															SCREAMING_SNAKE_CASE_: Optional[int]  		=       model(lowerCAmelCase__   ,						interpolate_pos_encoding=lowerCAmelCase__)

									# verify the logits
									SCREAMING_SNAKE_CASE_: Tuple  		=       torch.Size((1, 3601, 384))
									self.assertEqual(outputs.last_hidden_state.shape   ,						lowerCAmelCase__)

									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       torch.tensor(
									    [[4.2340, 4.3906, -6.6692], [4.5463, 1.8928, -6.7257], [4.4429, 0.8496, -5.8585]]).to(lowerCAmelCase__)

									self.assertTrue(torch.allclose(outputs.last_hidden_state[0, :3, :3]   ,						lowerCAmelCase__   ,						atol=1E-4))




			@slow
			@require_accelerate
			@require_torch_gpu
			def        _SCREAMING_SNAKE_CASE			( self  :     int):
									SCREAMING_SNAKE_CASE_: Dict  		=       ViTModel.from_pretrained("facebook/dino-vits8"   ,						torch_dtype=torch.floataa   ,						device_map="auto")
									SCREAMING_SNAKE_CASE_: int  		=       self.default_image_processor

									SCREAMING_SNAKE_CASE_: Union[str, Any]  		=       prepare_img()
									SCREAMING_SNAKE_CASE_: Dict  		=       image_processor(images=lowerCAmelCase__   ,						return_tensors="pt")
									SCREAMING_SNAKE_CASE_: str  		=       inputs.pixel_values.to(lowerCAmelCase__)

									# forward pass to make sure inference works in fp16
									with torch.no_grad():
															SCREAMING_SNAKE_CASE_: str  		=       model(lowerCAmelCase__)






