



import inspect
import unittest

from transformers import SegformerConfig, is_torch_available, is_vision_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, slow, torch_device

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 transformers import (
       MODEL_MAPPING,
       SegformerForImageClassification,
       SegformerForSemanticSegmentation,
       SegformerModel,
   )
   from transformers.models.segformer.modeling_segformer import SEGFORMER_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
   from PIL import Image

   from transformers import SegformerImageProcessor



class     _UpperCAmelCase			(       A__     ):




     def 		snake_case_		(				self):
         A__		 =					self.config_class(**self.inputs_dict)
         self.parent.assertTrue(hasattr(a__ ,						'''hidden_sizes'''))
         self.parent.assertTrue(hasattr(a__ ,						'''num_attention_heads'''))
         self.parent.assertTrue(hasattr(a__ ,						'''num_encoder_blocks'''))







class     _UpperCAmelCase			:




     def __init__(				self ,						a__ ,						a__=1_3 ,						a__=6_4 ,						a__=3 ,						a__=4 ,						a__=[2, 2, 2, 2] ,						a__=[8, 4, 2, 1] ,						a__=[1_6, 3_2, 6_4, 1_2_8] ,						a__=[1, 4, 8, 1_6] ,						a__=[1, 2, 4, 8] ,						a__=True ,						a__=True ,						a__="gelu" ,						a__=0.1 ,						a__=0.1 ,						a__=0.0_2 ,						a__=3 ,						a__=None ,						):
         A__		 =					parent
         A__		 =					batch_size
         A__		 =					image_size
         A__		 =					num_channels
         A__		 =					num_encoder_blocks
         A__		 =					sr_ratios
         A__		 =					depths
         A__		 =					hidden_sizes
         A__		 =					downsampling_rates
         A__		 =					num_attention_heads
         A__		 =					is_training
         A__		 =					use_labels
         A__		 =					hidden_act
         A__		 =					hidden_dropout_prob
         A__		 =					attention_probs_dropout_prob
         A__		 =					initializer_range
         A__		 =					num_labels
         A__		 =					scope




     def 		snake_case_		(				self):
         A__		 =					floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size])

         A__		 =					None
         if self.use_labels:
             A__		 =					ids_tensor([self.batch_size, self.image_size, self.image_size] ,						self.num_labels)

         A__		 =					self.get_config()
         return config, pixel_values, labels




     def 		snake_case_		(				self):
         return SegformerConfig(
             image_size=self.image_size ,						num_channels=self.num_channels ,						num_encoder_blocks=self.num_encoder_blocks ,						depths=self.depths ,						hidden_sizes=self.hidden_sizes ,						num_attention_heads=self.num_attention_heads ,						hidden_act=self.hidden_act ,						hidden_dropout_prob=self.hidden_dropout_prob ,						attention_probs_dropout_prob=self.attention_probs_dropout_prob ,						initializer_range=self.initializer_range ,						)




     def 		snake_case_		(				self ,						a__ ,						a__ ,						a__):
         A__		 =					SegformerModel(config=a__)
         model.to(a__)
         model.eval()
         A__		 =					model(a__)
         A__		 =					A__		 =					self.image_size // (self.downsampling_rates[-1] * 2)
         self.parent.assertEqual(
             result.last_hidden_state.shape ,						(self.batch_size, self.hidden_sizes[-1], expected_height, expected_width))




     def 		snake_case_		(				self ,						a__ ,						a__ ,						a__):
         A__		 =					self.num_labels
         A__		 =					SegformerForSemanticSegmentation(a__)
         model.to(a__)
         model.eval()
         A__		 =					model(a__)
         self.parent.assertEqual(
             result.logits.shape ,						(self.batch_size, self.num_labels, self.image_size // 4, self.image_size // 4))
         A__		 =					model(a__ ,						labels=a__)
         self.parent.assertEqual(
             result.logits.shape ,						(self.batch_size, self.num_labels, self.image_size // 4, self.image_size // 4))
         self.parent.assertGreater(result.loss ,						0.0)




     def 		snake_case_		(				self ,						a__ ,						a__ ,						a__):
         A__		 =					1
         A__		 =					SegformerForSemanticSegmentation(config=a__)
         model.to(a__)
         model.eval()
         A__		 =					torch.randint(0 ,						1 ,						(self.batch_size, self.image_size, self.image_size)).to(a__)
         A__		 =					model(a__ ,						labels=a__)
         self.parent.assertGreater(result.loss ,						0.0)




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







@require_torch
class     _UpperCAmelCase			(       A__			,      A__			,      unittest.TestCase     ):
     UpperCamelCase__		    =				(
         (
             SegformerModel,
             SegformerForSemanticSegmentation,
             SegformerForImageClassification,
         )
         if is_torch_available()
         else ()
     )
     UpperCamelCase__		    =				(
         {
             '''feature-extraction''': SegformerModel,
             '''image-classification''': SegformerForImageClassification,
             '''image-segmentation''': SegformerForSemanticSegmentation,
         }
         if is_torch_available()
         else {}
     )

     UpperCamelCase__		    =				True
     UpperCamelCase__		    =				False
     UpperCamelCase__		    =				False
     UpperCamelCase__		    =				False




     def 		snake_case_		(				self):
         A__		 =					SegformerModelTester(self)
         A__		 =					SegformerConfigTester(self ,						config_class=a__)




     def 		snake_case_		(				self):
         self.config_tester.run_common_tests()




     def 		snake_case_		(				self):
         A__		 =					self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_model(*a__)




     def 		snake_case_		(				self):
         A__		 =					self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_binary_image_segmentation(*a__)




     def 		snake_case_		(				self):
         A__		 =					self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_image_segmentation(*a__)




     @unittest.skip('''SegFormer does not use inputs_embeds''')
     def 		snake_case_		(				self):
         pass




     @unittest.skip('''SegFormer does not have get_input_embeddings method and get_output_embeddings methods''')
     def 		snake_case_		(				self):
         pass




     def 		snake_case_		(				self):
         A__ ,	A__		 =					self.model_tester.prepare_config_and_inputs_for_common()

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

             A__		 =					['''pixel_values''']
             self.assertListEqual(arg_names[:1] ,						a__)




     def 		snake_case_		(				self):
         A__ ,	A__		 =					self.model_tester.prepare_config_and_inputs_for_common()
         A__		 =					True

         for model_class in self.all_model_classes:
             A__		 =					True
             A__		 =					False
             A__		 =					True
             A__		 =					model_class(a__)
             model.to(a__)
             model.eval()
             with torch.no_grad():
                 A__		 =					model(**self._prepare_for_class(a__ ,						a__))
             A__		 =					outputs.attentions

             A__		 =					sum(self.model_tester.depths)
             self.assertEqual(len(a__) ,						a__)

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

             self.assertEqual(len(a__) ,						a__)

             # verify the first attentions (first block, first layer)
             A__		 =					(self.model_tester.image_size // 4) ** 2
             A__		 =					(self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
             self.assertListEqual(
                 list(attentions[0].shape[-3:]) ,						[self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len] ,						)

             # verify the last attentions (last block, last layer)
             A__		 =					(self.model_tester.image_size // 3_2) ** 2
             A__		 =					(self.model_tester.image_size // (3_2 * self.model_tester.sr_ratios[-1])) ** 2
             self.assertListEqual(
                 list(attentions[-1].shape[-3:]) ,						[self.model_tester.num_attention_heads[-1], expected_seq_len, expected_reduced_seq_len] ,						)
             A__		 =					len(a__)

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

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

             A__		 =					outputs.attentions

             self.assertEqual(len(a__) ,						a__)
             # verify the first attentions (first block, first layer)
             A__		 =					(self.model_tester.image_size // 4) ** 2
             A__		 =					(self.model_tester.image_size // (4 * self.model_tester.sr_ratios[0])) ** 2
             self.assertListEqual(
                 list(self_attentions[0].shape[-3:]) ,						[self.model_tester.num_attention_heads[0], expected_seq_len, expected_reduced_seq_len] ,						)




     def 		snake_case_		(				self):
         def check_hidden_states_output(a__ ,						a__ ,						a__):
             A__		 =					model_class(a__)
             model.to(a__)
             model.eval()

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

             A__		 =					outputs.hidden_states

             A__		 =					self.model_tester.num_encoder_blocks
             self.assertEqual(len(a__) ,						a__)

             # verify the first hidden states (first block)
             self.assertListEqual(
                 list(hidden_states[0].shape[-3:]) ,						[
                     self.model_tester.hidden_sizes[0],
                     self.model_tester.image_size // 4,
                     self.model_tester.image_size // 4,
                 ] ,						)

         A__ ,	A__		 =					self.model_tester.prepare_config_and_inputs_for_common()

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

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

             check_hidden_states_output(a__ ,						a__ ,						a__)




     def 		snake_case_		(				self):
         if not self.model_tester.is_training:
             return

         A__ ,	A__		 =					self.model_tester.prepare_config_and_inputs_for_common()
         A__		 =					True

         for model_class in self.all_model_classes:
             if model_class in get_values(a__):
                 continue

             A__		 =					model_class(a__)
             model.to(a__)
             model.train()
             A__		 =					self._prepare_for_class(a__ ,						a__ ,						return_labels=a__)
             A__		 =					model(**a__).loss
             loss.backward()




     @unittest.skip('''Will be fixed soon by reducing the size of the model used for common tests.''')
     def 		snake_case_		(				self):
         pass




     @slow
     def 		snake_case_		(				self):
         for model_name in SEGFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
             A__		 =					SegformerModel.from_pretrained(a__)
             self.assertIsNotNone(a__)







def 		lowerCAmelCase__    (					)->  Optional[int]:
    A__		 =					Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''	)
    return image



@require_torch
class     _UpperCAmelCase			(       unittest.TestCase     ):




     @slow
     def 		snake_case_		(				self):
         # only resize + normalize
         A__		 =					SegformerImageProcessor(
             image_scale=(5_1_2, 5_1_2) ,						keep_ratio=a__ ,						align=a__ ,						do_random_crop=a__)
         A__		 =					SegformerForSemanticSegmentation.from_pretrained('''nvidia/segformer-b0-finetuned-ade-512-512''').to(
             a__)

         A__		 =					prepare_img()
         A__		 =					image_processor(images=a__ ,						return_tensors='''pt''')
         A__		 =					encoded_inputs.pixel_values.to(a__)

         with torch.no_grad():
             A__		 =					model(a__)

         A__		 =					torch.Size((1, model.config.num_labels, 1_2_8, 1_2_8))
         self.assertEqual(outputs.logits.shape ,						a__)

         A__		 =					torch.tensor(
             [
                 [[-4.6_3_1_0, -5.5_2_3_2, -6.2_3_5_6], [-5.1_9_2_1, -6.1_4_4_4, -6.5_9_9_6], [-5.4_4_2_4, -6.2_7_9_0, -6.7_5_7_4]],
                 [[-1_2.1_3_9_1, -1_3.3_1_2_2, -1_3.9_5_5_4], [-1_2.8_7_3_2, -1_3.9_3_5_2, -1_4.3_5_6_3], [-1_2.9_4_3_8, -1_3.8_2_2_6, -1_4.2_5_1_3]],
                 [[-1_2.5_1_3_4, -1_3.4_6_8_6, -1_4.4_9_1_5], [-1_2.8_6_6_9, -1_4.4_3_4_3, -1_4.7_7_5_8], [-1_3.2_5_2_3, -1_4.5_8_1_9, -1_5.0_6_9_4]],
             ]).to(a__)
         self.assertTrue(torch.allclose(outputs.logits[0, :3, :3, :3] ,						a__ ,						atol=1e-4))




     @slow
     def 		snake_case_		(				self):
         # only resize + normalize
         A__		 =					SegformerImageProcessor(
             image_scale=(5_1_2, 5_1_2) ,						keep_ratio=a__ ,						align=a__ ,						do_random_crop=a__)
         A__		 =					SegformerForSemanticSegmentation.from_pretrained(
             '''nvidia/segformer-b1-finetuned-cityscapes-1024-1024''').to(a__)

         A__		 =					prepare_img()
         A__		 =					image_processor(images=a__ ,						return_tensors='''pt''')
         A__		 =					encoded_inputs.pixel_values.to(a__)

         with torch.no_grad():
             A__		 =					model(a__)

         A__		 =					torch.Size((1, model.config.num_labels, 1_2_8, 1_2_8))
         self.assertEqual(outputs.logits.shape ,						a__)

         A__		 =					torch.tensor(
             [
                 [[-1_3.5_7_4_8, -1_3.9_1_1_1, -1_2.6_5_0_0], [-1_4.3_5_0_0, -1_5.3_6_8_3, -1_4.2_3_2_8], [-1_4.7_5_3_2, -1_6.0_4_2_4, -1_5.6_0_8_7]],
                 [[-1_7.1_6_5_1, -1_5.8_7_2_5, -1_2.9_6_5_3], [-1_7.2_5_8_0, -1_7.3_7_1_8, -1_4.8_2_2_3], [-1_6.6_0_5_8, -1_6.8_7_8_3, -1_6.7_4_5_2]],
                 [[-3.6_4_5_6, -3.0_2_0_9, -1.4_2_0_3], [-3.0_7_9_7, -3.1_9_5_9, -2.0_0_0_0], [-1.8_7_5_7, -1.9_2_1_7, -1.6_9_9_7]],
             ]).to(a__)
         self.assertTrue(torch.allclose(outputs.logits[0, :3, :3, :3] ,						a__ ,						atol=1e-1))




     @slow
     def 		snake_case_		(				self):
         # only resize + normalize
         A__		 =					SegformerImageProcessor(
             image_scale=(5_1_2, 5_1_2) ,						keep_ratio=a__ ,						align=a__ ,						do_random_crop=a__)
         A__		 =					SegformerForSemanticSegmentation.from_pretrained('''nvidia/segformer-b0-finetuned-ade-512-512''').to(
             a__)

         A__		 =					prepare_img()
         A__		 =					image_processor(images=a__ ,						return_tensors='''pt''')
         A__		 =					encoded_inputs.pixel_values.to(a__)

         with torch.no_grad():
             A__		 =					model(a__)

         A__		 =					outputs.logits.detach().cpu()

         A__		 =					image_processor.post_process_semantic_segmentation(outputs=a__ ,						target_sizes=[(5_0_0, 3_0_0)])
         A__		 =					torch.Size((5_0_0, 3_0_0))
         self.assertEqual(segmentation[0].shape ,						a__)

         A__		 =					image_processor.post_process_semantic_segmentation(outputs=a__)
         A__		 =					torch.Size((1_2_8, 1_2_8))
         self.assertEqual(segmentation[0].shape ,						a__)








from __future__ import annotations



def 		lowerCAmelCase__    (					UpperCamelCase_				:       str ,       UpperCamelCase_				:       list[str] | None = None	)->  list[list[str]]:
    A__		 =					word_bank or []
    # create a table
    A__		 =					len(UpperCamelCase_	) + 1

    A__		 =					[]
    for _ in range(UpperCamelCase_	):
        table.append([]	)
    # seed value
    A__		 =					[[]]  # because empty string has empty combination

    # iterate through the indices
    for i in range(UpperCamelCase_	):
        # condition
        if table[i] != []:
            for word in word_bank:
                # slice condition
                if target[i : i + len(UpperCamelCase_	)] == word:
                    A__		 =					[
                        [word, *way] for way in table[i]
                    ]
                    # adds the word to every combination the current position holds
                    # now,push that combination to the table[i+len(word)]
                    table[i + len(UpperCamelCase_	)] += new_combinations

    # combinations are in reverse order so reverse for better output
    for combination in table[len(UpperCamelCase_	)]:
        combination.reverse()

    return table[len(UpperCamelCase_	)]


if __name__ == "__main__":
   print(all_construct("jwajalapa", ["jwa", "j", "w", "a", "la", "lapa"]))
   print(all_construct("rajamati", ["s", "raj", "amat", "raja", "ma", "i", "t"]))
   print(
       all_construct(
           "hexagonosaurus",
           ["h", "ex", "hex", "ag", "ago", "ru", "auru", "rus", "go", "no", "o", "s"],
       )
   )
