



'''simple docstring'''
import inspect
import unittest

import numpy as np

from tests.test_modeling_common import floats_tensor
from transformers import DetrConfig, MaskFormerConfig, SwinConfig, is_torch_available, is_vision_available
from transformers.testing_utils import require_torch, require_torch_multi_gpu, require_vision, slow, torch_device
from transformers.utils import cached_property

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
				import torch

				from transformers import MaskFormerForInstanceSegmentation, MaskFormerModel

				if is_vision_available():
								from transformers import MaskFormerImageProcessor

if is_vision_available():
				from PIL import Image


class       _lowerCAmelCase   :







							'''simple docstring'''

							def __init__(self  ,  UpperCAmelCase  ,  UpperCAmelCase=2  ,  UpperCAmelCase=True  ,  UpperCAmelCase=False  ,  UpperCAmelCase=10  ,  UpperCAmelCase=3  ,  UpperCAmelCase=32 * 4  ,  UpperCAmelCase=32 * 6  ,  UpperCAmelCase=4  ,  UpperCAmelCase=32  ,  )					->       Any:
														_snake_case       =  parent
														_snake_case       =  batch_size
														_snake_case       =  is_training
														_snake_case       =  use_auxiliary_loss
														_snake_case       =  num_queries
														_snake_case       =  num_channels
														_snake_case       =  min_size
														_snake_case       =  max_size
														_snake_case       =  num_labels
														_snake_case       =  mask_feature_size

							def 	lowercase							(self  )					->       Tuple:
														_snake_case       =  floats_tensor([self.batch_size, self.num_channels, self.min_size, self.max_size]  ).to(
														    UpperCAmelCase  )

														_snake_case       =  torch.ones([self.batch_size, self.min_size, self.max_size]  ,  device=UpperCAmelCase  )

														_snake_case       =  (
														    torch.rand([self.batch_size, self.num_labels, self.min_size, self.max_size]  ,  device=UpperCAmelCase  ) > 0.5
														).float()
														_snake_case       =  (torch.rand((self.batch_size, self.num_labels)  ,  device=UpperCAmelCase  ) > 0.5).long()

														_snake_case       =  self.get_config()
														return config, pixel_values, pixel_mask, mask_labels, class_labels

							def 	lowercase							(self  )					->       List[str]:
														return MaskFormerConfig.from_backbone_and_decoder_configs(
														    backbone_config=SwinConfig(
														        depths=[1, 1, 1, 1]  ,  )  ,  decoder_config=DetrConfig(
														        decoder_ffn_dim=128  ,  num_queries=self.num_queries  ,  decoder_attention_heads=2  ,  d_model=self.mask_feature_size  ,  )  ,  mask_feature_size=self.mask_feature_size  ,  fpn_feature_size=self.mask_feature_size  ,  num_channels=self.num_channels  ,  num_labels=self.num_labels  ,  )

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

							def 	lowercase							(self  ,  UpperCAmelCase  ,  UpperCAmelCase  )					->       Optional[int]:
														_snake_case       =  output.encoder_hidden_states
														_snake_case       =  output.pixel_decoder_hidden_states
														_snake_case       =  output.transformer_decoder_hidden_states

														self.parent.assertTrue(len(UpperCAmelCase  )  ,  len(config.backbone_config.depths  )  )
														self.parent.assertTrue(len(UpperCAmelCase  )  ,  len(config.backbone_config.depths  )  )
														self.parent.assertTrue(len(UpperCAmelCase  )  ,  config.decoder_config.decoder_layers  )

							def 	lowercase							(self  ,  UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase=False  )					->       Optional[int]:
														with torch.no_grad():
																					_snake_case       =  MaskFormerModel(config=UpperCAmelCase  )
																					model.to(UpperCAmelCase  )
																					model.eval()

																					_snake_case       =  model(pixel_values=UpperCAmelCase  ,  pixel_mask=UpperCAmelCase  )
																					_snake_case       =  model(UpperCAmelCase  ,  output_hidden_states=UpperCAmelCase  )
														# the correct shape of output.transformer_decoder_hidden_states ensure the correcteness of the
														# encoder and pixel decoder
														self.parent.assertEqual(
														    output.transformer_decoder_last_hidden_state.shape  ,  (self.batch_size, self.num_queries, self.mask_feature_size)  ,  )
														# let's ensure the other two hidden state exists
														self.parent.assertTrue(output.pixel_decoder_last_hidden_state is not None  )
														self.parent.assertTrue(output.encoder_last_hidden_state is not None  )

														if output_hidden_states:
																					self.check_output_hidden_state(UpperCAmelCase  ,  UpperCAmelCase  )





							def 	lowercase							(self  ,  UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase  ,  UpperCAmelCase  )					->       str:
														_snake_case       =  MaskFormerForInstanceSegmentation(config=UpperCAmelCase  )
														model.to(UpperCAmelCase  )
														model.eval()

														def comm_check_on_output(UpperCAmelCase  ):
																					# let's still check that all the required stuff is there
																					self.parent.assertTrue(result.transformer_decoder_last_hidden_state is not None  )
																					self.parent.assertTrue(result.pixel_decoder_last_hidden_state is not None  )
																					self.parent.assertTrue(result.encoder_last_hidden_state is not None  )
																					# okay, now we need to check the logits shape
																					# due to the encoder compression, masks have a //4 spatial size
																					self.parent.assertEqual(
																					    result.masks_queries_logits.shape  ,  (self.batch_size, self.num_queries, self.min_size // 4, self.max_size // 4)  ,  )
																					# + 1 for null class
																					self.parent.assertEqual(
																					    result.class_queries_logits.shape  ,  (self.batch_size, self.num_queries, self.num_labels + 1)  )

														with torch.no_grad():
																					_snake_case       =  model(pixel_values=UpperCAmelCase  ,  pixel_mask=UpperCAmelCase  )
																					_snake_case       =  model(UpperCAmelCase  )

																					comm_check_on_output(UpperCAmelCase  )

																					_snake_case       =  model(
																					    pixel_values=UpperCAmelCase  ,  pixel_mask=UpperCAmelCase  ,  mask_labels=UpperCAmelCase  ,  class_labels=UpperCAmelCase  )

														comm_check_on_output(UpperCAmelCase  )

														self.parent.assertTrue(result.loss is not None  )
														self.parent.assertEqual(result.loss.shape  ,  torch.Size([1]  )  )


@require_torch
class       _lowerCAmelCase   (   __snake_case					,							__snake_case					,							unittest.TestCase				):







							'''simple docstring'''

							lowerCAmelCase_ 						=						(MaskFormerModel, MaskFormerForInstanceSegmentation) if is_torch_available() else ()
							lowerCAmelCase_ 						=						(
							    {"feature-extraction": MaskFormerModel, "image-segmentation": MaskFormerForInstanceSegmentation}
							    if is_torch_available()
							    else {}
							)

							lowerCAmelCase_ 						=						False
							lowerCAmelCase_ 						=						False
							lowerCAmelCase_ 						=						False
							lowerCAmelCase_ 						=						False

							def 	lowercase							(self  )					->       Optional[int]:
														_snake_case       =  MaskFormerModelTester(self  )
														_snake_case       =  ConfigTester(self  ,  config_class=UpperCAmelCase  ,  has_text_modality=UpperCAmelCase  )

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

							def 	lowercase							(self  )					->       Union[str, Any]:
														_snake_case,							_snake_case       =  self.model_tester.prepare_config_and_inputs_for_common()
														self.model_tester.create_and_check_maskformer_model(UpperCAmelCase  ,  **UpperCAmelCase  ,  output_hidden_states=UpperCAmelCase  )

							def 	lowercase							(self  )					->       Union[str, Any]:
														_snake_case       =  self.model_tester.prepare_config_and_inputs()
														self.model_tester.create_and_check_maskformer_instance_segmentation_head_model(*UpperCAmelCase  )

							@unittest.skip(reason="""MaskFormer does not use inputs_embeds"""  )
							def 	lowercase							(self  )					->       Union[str, Any]:
														pass

							@unittest.skip(reason="""MaskFormer does not have a get_input_embeddings method"""  )
							def 	lowercase							(self  )					->       Dict:
														pass

							@unittest.skip(reason="""MaskFormer is not a generative model"""  )
							def 	lowercase							(self  )					->       Any:
														pass

							@unittest.skip(reason="""MaskFormer does not use token embeddings"""  )
							def 	lowercase							(self  )					->       Optional[int]:
														pass

							@require_torch_multi_gpu
							@unittest.skip(
							    reason="""MaskFormer has some layers using `add_module` which doesn't work well with `nn.DataParallel`"""  )
							def 	lowercase							(self  )					->       List[str]:
														pass

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

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

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

																					_snake_case       =  ["""pixel_values"""]
																					self.assertListEqual(arg_names[:1]  ,  UpperCAmelCase  )

							@slow
							def 	lowercase							(self  )					->       Tuple:
														for model_name in ["facebook/maskformer-swin-small-coco"]:
																					_snake_case       =  MaskFormerModel.from_pretrained(UpperCAmelCase  )
																					self.assertIsNotNone(UpperCAmelCase  )

							def 	lowercase							(self  )					->       Any:
														_snake_case       =  (self.model_tester.min_size,) * 2
														_snake_case       =  {
														    """pixel_values""": torch.randn((2, 3, *size)  ,  device=UpperCAmelCase  ),
														    """mask_labels""": torch.randn((2, 10, *size)  ,  device=UpperCAmelCase  ),
														    """class_labels""": torch.zeros(2  ,  10  ,  device=UpperCAmelCase  ).long(),
														}

														_snake_case       =  MaskFormerForInstanceSegmentation(MaskFormerConfig()  ).to(UpperCAmelCase  )
														_snake_case       =  model(**UpperCAmelCase  )
														self.assertTrue(outputs.loss is not None  )

							def 	lowercase							(self  )					->       int:
														_snake_case,							_snake_case       =  self.model_tester.prepare_config_and_inputs_for_common()
														self.model_tester.create_and_check_maskformer_model(UpperCAmelCase  ,  **UpperCAmelCase  ,  output_hidden_states=UpperCAmelCase  )

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

														for model_class in self.all_model_classes:
																					_snake_case       =  model_class(UpperCAmelCase  ).to(UpperCAmelCase  )
																					_snake_case       =  model(**UpperCAmelCase  ,  output_attentions=UpperCAmelCase  )
																					self.assertTrue(outputs.attentions is not None  )

							def 	lowercase							(self  )					->       List[Any]:
														if not self.model_tester.is_training:
																					return
														# only MaskFormerForInstanceSegmentation has the loss
														_snake_case       =  self.all_model_classes[1]
														_snake_case,							_snake_case,							_snake_case,							_snake_case,							_snake_case       =  self.model_tester.prepare_config_and_inputs()

														_snake_case       =  model_class(UpperCAmelCase  )
														model.to(UpperCAmelCase  )
														model.train()

														_snake_case       =  model(UpperCAmelCase  ,  mask_labels=UpperCAmelCase  ,  class_labels=UpperCAmelCase  ).loss
														loss.backward()





							def 	lowercase							(self  )					->       int:
														# only MaskFormerForInstanceSegmentation has the loss
														_snake_case       =  self.all_model_classes[1]
														_snake_case,							_snake_case,							_snake_case,							_snake_case,							_snake_case       =  self.model_tester.prepare_config_and_inputs()
														_snake_case       =  True
														_snake_case       =  True

														_snake_case       =  model_class(UpperCAmelCase  )
														model.to(UpperCAmelCase  )
														model.train()

														_snake_case       =  model(UpperCAmelCase  ,  mask_labels=UpperCAmelCase  ,  class_labels=UpperCAmelCase  )

														_snake_case       =  outputs.encoder_hidden_states[0]
														encoder_hidden_states.retain_grad()

														_snake_case       =  outputs.pixel_decoder_hidden_states[0]
														pixel_decoder_hidden_states.retain_grad()
														# we requires_grad=True in inputs_embeds (line 2152), the original implementation don't
														_snake_case       =  outputs.transformer_decoder_hidden_states[0]
														transformer_decoder_hidden_states.retain_grad()

														_snake_case       =  outputs.attentions[0]
														attentions.retain_grad()

														outputs.loss.backward(retain_graph=UpperCAmelCase  )

														self.assertIsNotNone(encoder_hidden_states.grad  )
														self.assertIsNotNone(pixel_decoder_hidden_states.grad  )
														self.assertIsNotNone(transformer_decoder_hidden_states.grad  )
														self.assertIsNotNone(attentions.grad  )
__lowerCAmelCase												=	1E-4






def  __SCREAMING_SNAKE_CASE				(  ):
							_snake_case       =  Image.open("""./tests/fixtures/tests_samples/COCO/000000039769.png"""				)
							return image


@require_vision
@slow
class       _lowerCAmelCase   (   unittest.TestCase				):







							'''simple docstring'''

							@cached_property
							def 	lowercase							(self  )					->       List[str]:
														return (
														    MaskFormerImageProcessor.from_pretrained("""facebook/maskformer-swin-small-coco"""  )
														    if is_vision_available()
														    else None
														)

							def 	lowercase							(self  )					->       Optional[int]:
														_snake_case       =  MaskFormerModel.from_pretrained("""facebook/maskformer-swin-small-coco"""  ).to(UpperCAmelCase  )
														_snake_case       =  self.default_image_processor
														_snake_case       =  prepare_img()
														_snake_case       =  image_processor(UpperCAmelCase  ,  return_tensors="""pt"""  ).to(UpperCAmelCase  )
														_snake_case       =  inputs["""pixel_values"""].shape
														# check size is divisible by 32
														self.assertTrue((inputs_shape[-1] % 32) == 0 and (inputs_shape[-2] % 32) == 0  )
														# check size
														self.assertEqual(UpperCAmelCase  ,  (1, 3, 800, 1088)  )

														with torch.no_grad():
																					_snake_case       =  model(**UpperCAmelCase  )

														_snake_case       =  torch.tensor(
														    [[-0.0482, 0.9228, 0.4951], [-0.2547, 0.8017, 0.8527], [-0.0069, 0.3385, -0.0089]]  ).to(UpperCAmelCase  )
														self.assertTrue(
														    torch.allclose(
														        outputs.encoder_last_hidden_state[0, 0, :3, :3]  ,  UpperCAmelCase  ,  atol=UpperCAmelCase  )  )

														_snake_case       =  torch.tensor(
														    [[-0.8422, -0.8434, -0.9718], [-1.0144, -0.5565, -0.4195], [-1.0038, -0.4484, -0.1961]]  ).to(UpperCAmelCase  )
														self.assertTrue(
														    torch.allclose(
														        outputs.pixel_decoder_last_hidden_state[0, 0, :3, :3]  ,  UpperCAmelCase  ,  atol=UpperCAmelCase  )  )

														_snake_case       =  torch.tensor(
														    [[0.2852, -0.0159, 0.9735], [0.6254, 0.1858, 0.8529], [-0.0680, -0.4116, 1.8413]]  ).to(UpperCAmelCase  )
														self.assertTrue(
														    torch.allclose(
														        outputs.transformer_decoder_last_hidden_state[0, :3, :3]  ,  UpperCAmelCase  ,  atol=UpperCAmelCase  )  )

							def 	lowercase							(self  )					->       Any:
														_snake_case       =  (
														    MaskFormerForInstanceSegmentation.from_pretrained("""facebook/maskformer-swin-small-coco"""  )
														    .to(UpperCAmelCase  )
														    .eval()
														)
														_snake_case       =  self.default_image_processor
														_snake_case       =  prepare_img()
														_snake_case       =  image_processor(UpperCAmelCase  ,  return_tensors="""pt"""  ).to(UpperCAmelCase  )
														_snake_case       =  inputs["""pixel_values"""].shape
														# check size is divisible by 32
														self.assertTrue((inputs_shape[-1] % 32) == 0 and (inputs_shape[-2] % 32) == 0  )
														# check size
														self.assertEqual(UpperCAmelCase  ,  (1, 3, 800, 1088)  )

														with torch.no_grad():
																					_snake_case       =  model(**UpperCAmelCase  )
														# masks_queries_logits
														_snake_case       =  outputs.masks_queries_logits
														self.assertEqual(
														    masks_queries_logits.shape  ,  (1, model.config.decoder_config.num_queries, inputs_shape[-2] // 4, inputs_shape[-1] // 4)  ,  )
														_snake_case       =  [
														    [-1.373_7124, -1.772_4937, -1.936_4233],
														    [-1.597_7281, -1.986_7939, -2.152_3695],
														    [-1.579_5398, -1.926_9832, -2.09_3942],
														]
														_snake_case       =  torch.tensor(UpperCAmelCase  ).to(UpperCAmelCase  )
														self.assertTrue(torch.allclose(masks_queries_logits[0, 0, :3, :3]  ,  UpperCAmelCase  ,  atol=UpperCAmelCase  )  )
														# class_queries_logits
														_snake_case       =  outputs.class_queries_logits
														self.assertEqual(
														    class_queries_logits.shape  ,  (1, model.config.decoder_config.num_queries, model.config.num_labels + 1)  )
														_snake_case       =  torch.tensor(
														    [
														        [1.6_5_1_2e0_0, -5.2_5_7_2e0_0, -3.3_5_1_9e0_0],
														        [3.6_1_6_9e-0_2, -5.9_0_2_5e0_0, -2.9_3_1_3e0_0],
														        [1.0_7_6_6e-0_4, -7.7_6_3_0e0_0, -5.1_2_6_3e0_0],
														    ]  ).to(UpperCAmelCase  )
														self.assertTrue(torch.allclose(outputs.class_queries_logits[0, :3, :3]  ,  UpperCAmelCase  ,  atol=UpperCAmelCase  )  )

							def 	lowercase							(self  )					->       Union[str, Any]:
														_snake_case       =  (
														    MaskFormerForInstanceSegmentation.from_pretrained("""facebook/maskformer-resnet101-coco-stuff"""  )
														    .to(UpperCAmelCase  )
														    .eval()
														)
														_snake_case       =  self.default_image_processor
														_snake_case       =  prepare_img()
														_snake_case       =  image_processor(UpperCAmelCase  ,  return_tensors="""pt"""  ).to(UpperCAmelCase  )
														_snake_case       =  inputs["""pixel_values"""].shape
														# check size is divisible by 32
														self.assertTrue((inputs_shape[-1] % 32) == 0 and (inputs_shape[-2] % 32) == 0  )
														# check size
														self.assertEqual(UpperCAmelCase  ,  (1, 3, 800, 1088)  )

														with torch.no_grad():
																					_snake_case       =  model(**UpperCAmelCase  )
														# masks_queries_logits
														_snake_case       =  outputs.masks_queries_logits
														self.assertEqual(
														    masks_queries_logits.shape  ,  (1, model.config.decoder_config.num_queries, inputs_shape[-2] // 4, inputs_shape[-1] // 4)  ,  )
														_snake_case       =  [[-0.9046, -2.6366, -4.6062], [-3.4179, -5.7890, -8.8057], [-4.9179, -7.6560, -10.7711]]
														_snake_case       =  torch.tensor(UpperCAmelCase  ).to(UpperCAmelCase  )
														self.assertTrue(torch.allclose(masks_queries_logits[0, 0, :3, :3]  ,  UpperCAmelCase  ,  atol=UpperCAmelCase  )  )
														# class_queries_logits
														_snake_case       =  outputs.class_queries_logits
														self.assertEqual(
														    class_queries_logits.shape  ,  (1, model.config.decoder_config.num_queries, model.config.num_labels + 1)  )
														_snake_case       =  torch.tensor(
														    [[4.7188, -3.2585, -2.8857], [6.6871, -2.9181, -1.2487], [7.2449, -2.2764, -2.1874]]  ).to(UpperCAmelCase  )
														self.assertTrue(torch.allclose(outputs.class_queries_logits[0, :3, :3]  ,  UpperCAmelCase  ,  atol=UpperCAmelCase  )  )





							def 	lowercase							(self  )					->       List[str]:
														_snake_case       =  (
														    MaskFormerForInstanceSegmentation.from_pretrained("""facebook/maskformer-swin-small-coco"""  )
														    .to(UpperCAmelCase  )
														    .eval()
														)
														_snake_case       =  self.default_image_processor

														_snake_case       =  image_processor(
														    [np.zeros((3, 800, 1333)  ), np.zeros((3, 800, 1333)  )]  ,  segmentation_maps=[np.zeros((384, 384)  ).astype(np.floataa  ), np.zeros((384, 384)  ).astype(np.floataa  )]  ,  return_tensors="""pt"""  ,  )

														_snake_case       =  inputs["""pixel_values"""].to(UpperCAmelCase  )
														_snake_case       =  [el.to(UpperCAmelCase  ) for el in inputs["""mask_labels"""]]
														_snake_case       =  [el.to(UpperCAmelCase  ) for el in inputs["""class_labels"""]]

														with torch.no_grad():
																					_snake_case       =  model(**UpperCAmelCase  )

														self.assertTrue(outputs.loss is not None  )

'''simple docstring'''
from __future__ import annotations






def  __SCREAMING_SNAKE_CASE				(  _SCREAMING_SNAKE_CASE				):
							_snake_case       =  len(_SCREAMING_SNAKE_CASE				)
							# We need to create solution object to save path.
							_snake_case       =  [[0 for _ in range(_SCREAMING_SNAKE_CASE				)] for _ in range(_SCREAMING_SNAKE_CASE				)]
							_snake_case       =  run_maze(_SCREAMING_SNAKE_CASE							, 0							, 0							, _SCREAMING_SNAKE_CASE				)
							if solved:
														print("""\n""".join(str(_SCREAMING_SNAKE_CASE				) for row in solutions				)				)
							else:
														print("""No solution exists!"""				)
							return solved






def  __SCREAMING_SNAKE_CASE				(  _SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE				):
							_snake_case       =  len(_SCREAMING_SNAKE_CASE				)
							# Final check point.
							if i == j == (size - 1):
														_snake_case       =  1
														return True

							_snake_case       =  (not i < 0) and (not j < 0)  # Check lower bounds
							_snake_case       =  (i < size) and (j < size)  # Check upper bounds

							if lower_flag and upper_flag:
														# check for already visited and block points.
														_snake_case       =  (not solutions[i][j]) and (not maze[i][j])
														if block_flag:
																					# check visited
																					_snake_case       =  1

																					# check for directions
																					if (
																					    run_maze(_SCREAMING_SNAKE_CASE							, i + 1							, _SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE				)
																					    or run_maze(_SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE							, j + 1							, _SCREAMING_SNAKE_CASE				)
																					    or run_maze(_SCREAMING_SNAKE_CASE							, i - 1							, _SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE				)
																					    or run_maze(_SCREAMING_SNAKE_CASE							, _SCREAMING_SNAKE_CASE							, j - 1							, _SCREAMING_SNAKE_CASE				)
																					):
																												return True

																					_snake_case       =  0
																					return False
							return False


if __name__ == "__main__":
				import doctest

				doctest.testmod()