import collections
import inspect
import unittest

from transformers import SwinConfig
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_backbone_common import BackboneTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, _config_zero_init, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
						import torch
						from torch import nn

						from transformers import SwinBackbone, SwinForImageClassification, SwinForMaskedImageModeling, SwinModel
						from transformers.models.swin.modeling_swin import SWIN_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
						from PIL import Image

						from transformers import AutoImageProcessor
class 	_a  :



	"""simple docstring"""



	def __init__(   self       ,  lowerCAmelCase_       ,  lowerCAmelCase_=13       ,  lowerCAmelCase_=32       ,  lowerCAmelCase_=2       ,  lowerCAmelCase_=3       ,  lowerCAmelCase_=16       ,  lowerCAmelCase_=[1, 2, 1]       ,  lowerCAmelCase_=[2, 2, 4]       ,  lowerCAmelCase_=2       ,  lowerCAmelCase_=2.0       ,  lowerCAmelCase_=True       ,  lowerCAmelCase_=0.0       ,  lowerCAmelCase_=0.0       ,  lowerCAmelCase_=0.1       ,  lowerCAmelCase_="gelu"       ,  lowerCAmelCase_=False       ,  lowerCAmelCase_=True       ,  lowerCAmelCase_=0.0_2       ,  lowerCAmelCase_=1e-5       ,  lowerCAmelCase_=True       ,  lowerCAmelCase_=None       ,  lowerCAmelCase_=True       ,  lowerCAmelCase_=10       ,  lowerCAmelCase_=8       ,  lowerCAmelCase_=["stage1", "stage2"]       ,  lowerCAmelCase_=[1, 2]       ,  ):
		_lowercase   =parent
		_lowercase   =batch_size
		_lowercase   =image_size
		_lowercase   =patch_size
		_lowercase   =num_channels
		_lowercase   =embed_dim
		_lowercase   =depths
		_lowercase   =num_heads
		_lowercase   =window_size
		_lowercase   =mlp_ratio
		_lowercase   =qkv_bias
		_lowercase   =hidden_dropout_prob
		_lowercase   =attention_probs_dropout_prob
		_lowercase   =drop_path_rate
		_lowercase   =hidden_act
		_lowercase   =use_absolute_embeddings
		_lowercase   =patch_norm
		_lowercase   =layer_norm_eps
		_lowercase   =initializer_range
		_lowercase   =is_training
		_lowercase   =scope
		_lowercase   =use_labels
		_lowercase   =type_sequence_label_size
		_lowercase   =encoder_stride
		_lowercase   =out_features
		_lowercase   =out_indices


	def __lowerCAmelCase      (   self       ):
		_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       ):
		return SwinConfig(
		    image_size=self.image_size       ,  patch_size=self.patch_size       ,  num_channels=self.num_channels       ,  embed_dim=self.embed_dim       ,  depths=self.depths       ,  num_heads=self.num_heads       ,  window_size=self.window_size       ,  mlp_ratio=self.mlp_ratio       ,  qkv_bias=self.qkv_bias       ,  hidden_dropout_prob=self.hidden_dropout_prob       ,  attention_probs_dropout_prob=self.attention_probs_dropout_prob       ,  drop_path_rate=self.drop_path_rate       ,  hidden_act=self.hidden_act       ,  use_absolute_embeddings=self.use_absolute_embeddings       ,  path_norm=self.patch_norm       ,  layer_norm_eps=self.layer_norm_eps       ,  initializer_range=self.initializer_range       ,  encoder_stride=self.encoder_stride       ,  out_features=self.out_features       ,  out_indices=self.out_indices       ,  )


	def __lowerCAmelCase      (   self       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ):
		_lowercase   =SwinModel(config=lowerCAmelCase_       )
		model.to(lowerCAmelCase_       )
		model.eval()
		_lowercase   =model(lowerCAmelCase_       )

		_lowercase   =((config.image_size // config.patch_size) ** 2) // (4 ** (len(config.depths       ) - 1))
		_lowercase   =int(config.embed_dim * 2 ** (len(config.depths       ) - 1)       )

		self.parent.assertEqual(result.last_hidden_state.shape       ,  (self.batch_size, expected_seq_len, expected_dim)       )


	def __lowerCAmelCase      (   self       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ):
		_lowercase   =SwinBackbone(config=lowerCAmelCase_       )
		model.to(lowerCAmelCase_       )
		model.eval()
		_lowercase   =model(lowerCAmelCase_       )

		# verify hidden states
		self.parent.assertEqual(len(result.feature_maps       )       ,  len(config.out_features       )       )
		self.parent.assertListEqual(list(result.feature_maps[0].shape       )       ,  [self.batch_size, model.channels[0], 16, 16]       )

		# verify channels
		self.parent.assertEqual(len(model.channels       )       ,  len(config.out_features       )       )

		# verify backbone works with out_features=None
		_lowercase   =None
		_lowercase   =SwinBackbone(config=lowerCAmelCase_       )
		model.to(lowerCAmelCase_       )
		model.eval()
		_lowercase   =model(lowerCAmelCase_       )

		# verify feature maps
		self.parent.assertEqual(len(result.feature_maps       )       ,  1       )
		self.parent.assertListEqual(list(result.feature_maps[0].shape       )       ,  [self.batch_size, model.channels[-1], 4, 4]       )

		# verify channels
		self.parent.assertEqual(len(model.channels       )       ,  1       )


	def __lowerCAmelCase      (   self       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ):
		_lowercase   =SwinForMaskedImageModeling(config=lowerCAmelCase_       )
		model.to(lowerCAmelCase_       )
		model.eval()
		_lowercase   =model(lowerCAmelCase_       )
		self.parent.assertEqual(
		    result.logits.shape       ,  (self.batch_size, self.num_channels, self.image_size, self.image_size)       )

		# test greyscale images
		_lowercase   =1
		_lowercase   =SwinForMaskedImageModeling(lowerCAmelCase_       )
		model.to(lowerCAmelCase_       )
		model.eval()

		_lowercase   =floats_tensor([self.batch_size, 1, self.image_size, self.image_size]       )
		_lowercase   =model(lowerCAmelCase_       )
		self.parent.assertEqual(result.logits.shape       ,  (self.batch_size, 1, self.image_size, self.image_size)       )


	def __lowerCAmelCase      (   self       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ):
		_lowercase   =self.type_sequence_label_size
		_lowercase   =SwinForImageClassification(lowerCAmelCase_       )
		model.to(lowerCAmelCase_       )
		model.eval()
		_lowercase   =model(lowerCAmelCase_       ,  labels=lowerCAmelCase_       )
		self.parent.assertEqual(result.logits.shape       ,  (self.batch_size, self.type_sequence_label_size)       )

		# test greyscale images
		_lowercase   =1
		_lowercase   =SwinForImageClassification(lowerCAmelCase_       )
		model.to(lowerCAmelCase_       )
		model.eval()

		_lowercase   =floats_tensor([self.batch_size, 1, self.image_size, self.image_size]       )
		_lowercase   =model(lowerCAmelCase_       )
		self.parent.assertEqual(result.logits.shape       ,  (self.batch_size, self.type_sequence_label_size)       )


	def __lowerCAmelCase      (   self       ):
		_lowercase   =self.prepare_config_and_inputs()
		(
		    (
		    _lowercase
		)   ,  (
		    _lowercase
		)   ,  (
		    _lowercase
		)   ,  
		)   =config_and_inputs
		_lowercase   ={"pixel_values": pixel_values}
		return config, inputs_dict

@require_torch
class 	_a  (							lowerCamelCase_							,		lowerCamelCase_							,		unittest.TestCase					):



	"""simple docstring"""



	__SCREAMING_SNAKE_CASE              =					(
	    (
	        SwinModel,
	        SwinBackbone,
	        SwinForImageClassification,
	        SwinForMaskedImageModeling,
	    )
	    if is_torch_available()
	    else ()
	)
	__SCREAMING_SNAKE_CASE              =					(
	    {'feature-extraction': SwinModel, 'image-classification': SwinForImageClassification}
	    if is_torch_available()
	    else {}
	)
	__SCREAMING_SNAKE_CASE              =					True

	__SCREAMING_SNAKE_CASE              =					False
	__SCREAMING_SNAKE_CASE              =					False
	__SCREAMING_SNAKE_CASE              =					False


	def __lowerCAmelCase      (   self       ):
		_lowercase   =SwinModelTester(self       )
		_lowercase   =ConfigTester(self       ,  config_class=lowerCAmelCase_       ,  embed_dim=37       )


	def __lowerCAmelCase      (   self       ):
		self.create_and_test_config_common_properties()
		self.config_tester.create_and_test_config_to_json_string()
		self.config_tester.create_and_test_config_to_json_file()
		self.config_tester.create_and_test_config_from_and_save_pretrained()
		self.config_tester.create_and_test_config_with_num_labels()
		self.config_tester.check_config_can_be_init_without_params()
		self.config_tester.check_config_arguments_init()


	def __lowerCAmelCase      (   self       ):
		return


	def __lowerCAmelCase      (   self       ):
		_lowercase   =self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_model(*lowerCAmelCase_       )


	@unittest.skip(reason="Got `CUDA error: misaligned address` with PyTorch 2.0.0."       )
	def __lowerCAmelCase      (   self       ):
		pass


	def __lowerCAmelCase      (   self       ):
		super().test_training_gradient_checkpointing()


	def __lowerCAmelCase      (   self       ):
		_lowercase   =self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_backbone(*lowerCAmelCase_       )


	def __lowerCAmelCase      (   self       ):
		_lowercase   =self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_for_masked_image_modeling(*lowerCAmelCase_       )


	def __lowerCAmelCase      (   self       ):
		_lowercase   =self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_for_image_classification(*lowerCAmelCase_       )


	@unittest.skip(reason="Swin does not use inputs_embeds"       )
	def __lowerCAmelCase      (   self       ):
		pass


	@unittest.skip(reason="Swin Transformer does not use feedforward chunking"       )
	def __lowerCAmelCase      (   self       ):
		pass


	def __lowerCAmelCase      (   self       ):
		_lowercase   ,  _lowercase   =self.model_tester.prepare_config_and_inputs_for_common()

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


	def __lowerCAmelCase      (   self       ):
		_lowercase   ,  _lowercase   =self.model_tester.prepare_config_and_inputs_for_common()

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


	def __lowerCAmelCase      (   self       ):
		_lowercase   ,  _lowercase   =self.model_tester.prepare_config_and_inputs_for_common()
		_lowercase   =True

		for model_class in self.all_model_classes:
			_lowercase   =True
			_lowercase   =False
			_lowercase   =True
			_lowercase   =model_class(lowerCAmelCase_       )
			model.to(lowerCAmelCase_       )
			model.eval()
			with torch.no_grad():
				_lowercase   =model(**self._prepare_for_class(lowerCAmelCase_       ,  lowerCAmelCase_       )       )
			_lowercase   =outputs.attentions
			_lowercase   =len(self.model_tester.depths       )
			self.assertEqual(len(lowerCAmelCase_       )       ,  lowerCAmelCase_       )

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

			self.assertListEqual(
			    list(attentions[0].shape[-3:]       )       ,  [self.model_tester.num_heads[0], window_size_squared, window_size_squared]       ,  )
			_lowercase   =len(lowerCAmelCase_       )

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

			# also another +1 for reshaped_hidden_states
			_lowercase   =1 if model_class.__name__ == "SwinBackbone" else 2
			self.assertEqual(out_len + added_hidden_states       ,  len(lowerCAmelCase_       )       )

			_lowercase   =outputs.attentions

			self.assertEqual(len(lowerCAmelCase_       )       ,  lowerCAmelCase_       )

			self.assertListEqual(
			    list(self_attentions[0].shape[-3:]       )       ,  [self.model_tester.num_heads[0], window_size_squared, window_size_squared]       ,  )


	def __lowerCAmelCase      (   self       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ):
		_lowercase   =model_class(lowerCAmelCase_       )
		model.to(lowerCAmelCase_       )
		model.eval()

		with torch.no_grad():
			_lowercase   =model(**self._prepare_for_class(lowerCAmelCase_       ,  lowerCAmelCase_       )       )

		_lowercase   =outputs.hidden_states

		_lowercase   =getattr(
		    self.model_tester       ,  "expected_num_hidden_layers"       ,  len(self.model_tester.depths       ) + 1       )
		self.assertEqual(len(lowerCAmelCase_       )       ,  lowerCAmelCase_       )

		# Swin has a different seq_length
		_lowercase   =(
		    config.patch_size
		    if isinstance(config.patch_size       ,  collections.abc.Iterable       )
		    else (config.patch_size, config.patch_size)
		)

		_lowercase   =(image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])

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

		if not model_class.__name__ == "SwinBackbone":
			_lowercase   =outputs.reshaped_hidden_states
			self.assertEqual(len(lowerCAmelCase_       )       ,  lowerCAmelCase_       )

			_lowercase   ,  _lowercase   ,  _lowercase   ,  _lowercase   =reshaped_hidden_states[0].shape
			_lowercase   =(
			    reshaped_hidden_states[0].view(lowerCAmelCase_       ,  lowerCAmelCase_       ,  height * width       ).permute(0       ,  2       ,  1       )
			)
			self.assertListEqual(
			    list(reshaped_hidden_states.shape[-2:]       )       ,  [num_patches, self.model_tester.embed_dim]       ,  )


	def __lowerCAmelCase      (   self       ):
		_lowercase   ,  _lowercase   =self.model_tester.prepare_config_and_inputs_for_common()

		_lowercase   =(
		    self.model_tester.image_size
		    if isinstance(self.model_tester.image_size       ,  collections.abc.Iterable       )
		    else (self.model_tester.image_size, self.model_tester.image_size)
		)

		for model_class in self.all_model_classes:
			_lowercase   =True
			self.check_hidden_states_output(lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       )

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

			self.check_hidden_states_output(lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       )


	def __lowerCAmelCase      (   self       ):
		_lowercase   ,  _lowercase   =self.model_tester.prepare_config_and_inputs_for_common()
		_lowercase   =3

		_lowercase   =(
		    self.model_tester.image_size
		    if isinstance(self.model_tester.image_size       ,  collections.abc.Iterable       )
		    else (self.model_tester.image_size, self.model_tester.image_size)
		)
		_lowercase   =(
		    config.patch_size
		    if isinstance(config.patch_size       ,  collections.abc.Iterable       )
		    else (config.patch_size, config.patch_size)
		)

		_lowercase   =image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
		_lowercase   =image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

		for model_class in self.all_model_classes:
			_lowercase   =True
			self.check_hidden_states_output(lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ,  (padded_height, padded_width)       )

			# check that output_hidden_states also work using config
			del inputs_dict["output_hidden_states"]
			_lowercase   =True
			self.check_hidden_states_output(lowerCAmelCase_       ,  lowerCAmelCase_       ,  lowerCAmelCase_       ,  (padded_height, padded_width)       )


	@slow
	def __lowerCAmelCase      (   self       ):
		for model_name in SWIN_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
			_lowercase   =SwinModel.from_pretrained(lowerCAmelCase_       )
			self.assertIsNotNone(lowerCAmelCase_       )


	def __lowerCAmelCase      (   self       ):
		_lowercase   ,  _lowercase   =self.model_tester.prepare_config_and_inputs_for_common()

		_lowercase   =_config_zero_init(lowerCAmelCase_       )
		for model_class in self.all_model_classes:
			_lowercase   =model_class(config=lowerCAmelCase_       )
			for name, param in model.named_parameters():
				if "embeddings" not in name and param.requires_grad:
					self.assertIn(
					    ((param.data.mean() * 1e9).round() / 1e9).item()       ,  [0.0, 1.0]       ,  msg=F'''Parameter {name} of model {model_class} seems not properly initialized'''       ,  )

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



	"""simple docstring"""



	@cached_property
	def __lowerCAmelCase      (   self       ):
		return (
		    AutoImageProcessor.from_pretrained("microsoft/swin-tiny-patch4-window7-224"       )
		    if is_vision_available()
		    else None
		)


	@slow
	def __lowerCAmelCase      (   self       ):
		_lowercase   =SwinForImageClassification.from_pretrained("microsoft/swin-tiny-patch4-window7-224"       ).to(lowerCAmelCase_       )
		_lowercase   =self.default_image_processor

		_lowercase   =Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"       )
		_lowercase   =image_processor(images=lowerCAmelCase_       ,  return_tensors="pt"       ).to(lowerCAmelCase_       )

		# forward pass
		with torch.no_grad():
			_lowercase   =model(**lowerCAmelCase_       )

		# verify the logits
		_lowercase   =torch.Size((1, 1000)       )
		self.assertEqual(outputs.logits.shape       ,  lowerCAmelCase_       )
		_lowercase   =torch.tensor([-0.0_9_4_8, -0.6_4_5_4, -0.0_9_2_1]       ).to(lowerCAmelCase_       )
		self.assertTrue(torch.allclose(outputs.logits[0, :3]       ,  lowerCAmelCase_       ,  atol=1e-4       )       )

@require_torch
class 	_a  (							unittest.TestCase							,		lowerCamelCase_					):



	"""simple docstring"""



	__SCREAMING_SNAKE_CASE              =					(SwinBackbone,) if is_torch_available() else ()
	__SCREAMING_SNAKE_CASE              =					SwinConfig


	def __lowerCAmelCase      (   self       ):
		_lowercase   =SwinModelTester(self       )





import heapq

def 				UpperCamelCase					(     lowerCAmelCase_							,       lowerCAmelCase_							,       lowerCAmelCase_ )		->    Dict:




       '''simple docstring'''






       _A=						[(0, start)]  # cost from start node,end node
       _A=						set()
       while heap:
              ((_A),      (_A))=						heapq.heappop(lowerCAmelCase_ )
              if u in visited:
                     continue
              visited.add(lowerCAmelCase_ )
              if u == end:
                     return cost
              for v, c in graph[u]:
                     if v in visited:
                            continue
                     _A=						cost + c
                     heapq.heappush(lowerCAmelCase_							,       (next_item, v) )
       return -1


UpperCAmelCase_    		=				{
    '''A''': [['''B''', 2], ['''C''', 5]],
    '''B''': [['''A''', 2], ['''D''', 3], ['''E''', 1], ['''F''', 1]],
    '''C''': [['''A''', 5], ['''F''', 3]],
    '''D''': [['''B''', 3]],
    '''E''': [['''B''', 4], ['''F''', 3]],
    '''F''': [['''C''', 3], ['''E''', 3]],
}
UpperCAmelCase_    		=				{
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''F''', 3]],
    '''F''': [],
}
UpperCAmelCase_    		=				{
    '''B''': [['''C''', 1]],
    '''C''': [['''D''', 1]],
    '''D''': [['''F''', 1]],
    '''E''': [['''B''', 1], ['''G''', 2]],
    '''F''': [],
    '''G''': [['''F''', 1]],
}

UpperCAmelCase_    		=				dijkstra(G, '''E''', '''C''')
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

UpperCAmelCase_    		=				dijkstra(Ga, '''E''', '''F''')
print(short_distance)  # E -- 3 --> F == 3

UpperCAmelCase_    		=				dijkstra(Ga, '''E''', '''F''')
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
      import doctest

      doctest.testmod()