





import inspect
import unittest

import numpy as np

from tests.test_modeling_common import floats_tensor
from transformers import MaskaFormerConfig, 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 MaskaFormerForUniversalSegmentation, MaskaFormerModel

     if is_vision_available():
          from transformers import MaskaFormerImageProcessor

if is_vision_available():
     from PIL import Image



class     _UpperCAmelCase   :

  """simple docstring"""


  def __init__(    self			:		List[str] ,  lowerCAmelCase_			:		List[Any] ,  lowerCAmelCase_			:		Tuple=2 ,  lowerCAmelCase_			:		List[Any]=True ,  lowerCAmelCase_			:		List[Any]=False ,  lowerCAmelCase_			:		Optional[int]=1_0 ,  lowerCAmelCase_			:		List[Any]=3 ,  lowerCAmelCase_			:		Union[str, Any]=3_2 * 8 ,  lowerCAmelCase_			:		Dict=3_2 * 8 ,  lowerCAmelCase_			:		str=4 ,  lowerCAmelCase_			:		Optional[int]=6_4 ,  )							->						int:
     __lowerCAmelCase							     =     parent
     __lowerCAmelCase							     =     batch_size
     __lowerCAmelCase							     =     is_training
     __lowerCAmelCase							     =     use_auxiliary_loss
     __lowerCAmelCase							     =     num_queries
     __lowerCAmelCase							     =     num_channels
     __lowerCAmelCase							     =     min_size
     __lowerCAmelCase							     =     max_size
     __lowerCAmelCase							     =     num_labels
     __lowerCAmelCase							     =     hidden_dim
     __lowerCAmelCase							     =     hidden_dim






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

     __lowerCAmelCase							     =     torch.ones([self.batch_size, self.min_size, self.max_size] ,  device=lowerCAmelCase_					)

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

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






  def     lowercase		(    self			:		List[str]					)							->						Optional[Any]:
     __lowerCAmelCase							     =     MaskaFormerConfig(
         hidden_size=self.hidden_dim ,  )
     __lowerCAmelCase							     =     self.num_queries
     __lowerCAmelCase							     =     self.num_labels

     __lowerCAmelCase							     =     [1, 1, 1, 1]
     __lowerCAmelCase							     =     self.num_channels

     __lowerCAmelCase							     =     6_4
     __lowerCAmelCase							     =     1_2_8
     __lowerCAmelCase							     =     self.hidden_dim
     __lowerCAmelCase							     =     self.hidden_dim
     __lowerCAmelCase							     =     self.hidden_dim
     return config






  def     lowercase		(    self			:		Union[str, Any]					)							->						Any:
     __lowerCAmelCase     ,     __lowerCAmelCase     ,     __lowerCAmelCase     ,     __lowerCAmelCase     ,     __lowerCAmelCase							     =     self.prepare_config_and_inputs()
     __lowerCAmelCase							     =     {'pixel_values': pixel_values, 'pixel_mask': pixel_mask}
     return config, inputs_dict






  def     lowercase		(    self			:		Union[str, Any] ,  lowerCAmelCase_			:		Union[str, Any] ,  lowerCAmelCase_			:		str					)							->						List[Any]:
     __lowerCAmelCase							     =     output.encoder_hidden_states
     __lowerCAmelCase							     =     output.pixel_decoder_hidden_states
     __lowerCAmelCase							     =     output.transformer_decoder_hidden_states

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






  def     lowercase		(    self			:		Optional[int] ,  lowerCAmelCase_			:		Optional[Any] ,  lowerCAmelCase_			:		List[Any] ,  lowerCAmelCase_			:		List[str] ,  lowerCAmelCase_			:		List[str]=False					)							->						str:
     with torch.no_grad():
        __lowerCAmelCase							     =     MaskaFormerModel(config=lowerCAmelCase_					)
        model.to(lowerCAmelCase_					)
        model.eval()

        __lowerCAmelCase							     =     model(pixel_values=lowerCAmelCase_ ,  pixel_mask=lowerCAmelCase_					)
        __lowerCAmelCase							     =     model(lowerCAmelCase_ ,  output_hidden_states=lowerCAmelCase_					)

     self.parent.assertEqual(
         output.transformer_decoder_last_hidden_state.shape ,  (self.batch_size, self.num_queries, self.hidden_dim) ,  )
     # 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(lowerCAmelCase_ ,  lowerCAmelCase_					)






  def     lowercase		(    self			:		Optional[Any] ,  lowerCAmelCase_			:		List[str] ,  lowerCAmelCase_			:		Optional[Any] ,  lowerCAmelCase_			:		int ,  lowerCAmelCase_			:		Any ,  lowerCAmelCase_			:		str					)							->						List[Any]:
     __lowerCAmelCase							     =     MaskaFormerForUniversalSegmentation(config=lowerCAmelCase_					)
     model.to(lowerCAmelCase_					)
     model.eval()

     def comm_check_on_output(lowerCAmelCase_			:		Dict					):
        # 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():
        __lowerCAmelCase							     =     model(pixel_values=lowerCAmelCase_ ,  pixel_mask=lowerCAmelCase_					)
        __lowerCAmelCase							     =     model(lowerCAmelCase_					)

        comm_check_on_output(lowerCAmelCase_					)

        __lowerCAmelCase							     =     model(
            pixel_values=lowerCAmelCase_ ,  pixel_mask=lowerCAmelCase_ ,  mask_labels=lowerCAmelCase_ ,  class_labels=lowerCAmelCase_					)

     comm_check_on_output(lowerCAmelCase_					)

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





@require_torch
class     _UpperCAmelCase   (   _UpperCamelCase		,   _UpperCamelCase		,   unittest.TestCase   ):

  """simple docstring"""


  a_      =			(MaskaFormerModel, MaskaFormerForUniversalSegmentation) if is_torch_available() else ()
  a_      =			{"""feature-extraction""": MaskaFormerModel} if is_torch_available() else {}

  a_      =			False
  a_      =			False
  a_      =			False
  a_      =			False






  def     lowercase		(    self			:		Union[str, Any]					)							->						Optional[int]:
     __lowerCAmelCase							     =     MaskaFormerModelTester(self					)
     __lowerCAmelCase							     =     ConfigTester(self ,  config_class=lowerCAmelCase_ ,  has_text_modality=lowerCAmelCase_					)






  def     lowercase		(    self			:		Union[str, Any]					)							->						str:
     self.config_tester.run_common_tests()






  def     lowercase		(    self			:		Optional[int]					)							->						Union[str, Any]:
     __lowerCAmelCase     ,     __lowerCAmelCase							     =     self.model_tester.prepare_config_and_inputs_for_common()
     self.model_tester.create_and_check_maskaformer_model(lowerCAmelCase_ ,  **lowerCAmelCase_ ,  output_hidden_states=lowerCAmelCase_					)






  def     lowercase		(    self			:		str					)							->						Any:
     __lowerCAmelCase							     =     self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_maskaformer_instance_segmentation_head_model(*lowerCAmelCase_					)






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






  @unittest.skip(reason='Mask2Former does not have a get_input_embeddings method'					)
  def     lowercase		(    self			:		Any					)							->						str:
     pass






  @unittest.skip(reason='Mask2Former is not a generative model'					)
  def     lowercase		(    self			:		List[str]					)							->						int:
     pass






  @unittest.skip(reason='Mask2Former does not use token embeddings'					)
  def     lowercase		(    self			:		Any					)							->						Dict:
     pass






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






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






  def     lowercase		(    self			:		Tuple					)							->						Any:
     __lowerCAmelCase     ,     __lowerCAmelCase							     =     self.model_tester.prepare_config_and_inputs_for_common()

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

        __lowerCAmelCase							     =     ['pixel_values']
        self.assertListEqual(arg_names[:1] ,  lowerCAmelCase_					)






  @slow
  def     lowercase		(    self			:		Union[str, Any]					)							->						List[str]:
     for model_name in ["facebook/mask2former-swin-small-coco-instance"]:
        __lowerCAmelCase							     =     MaskaFormerModel.from_pretrained(lowerCAmelCase_					)
        self.assertIsNotNone(lowerCAmelCase_					)






  def     lowercase		(    self			:		Union[str, Any]					)							->						List[Any]:
     __lowerCAmelCase							     =     (self.model_tester.min_size,) * 2
     __lowerCAmelCase							     =     {
         'pixel_values': torch.randn((2, 3, *size) ,  device=lowerCAmelCase_					),
         'mask_labels': torch.randn((2, 1_0, *size) ,  device=lowerCAmelCase_					),
         'class_labels': torch.zeros(2 ,  1_0 ,  device=lowerCAmelCase_					).long(),
     }
     __lowerCAmelCase							     =     self.model_tester.get_config()

     __lowerCAmelCase							     =     MaskaFormerForUniversalSegmentation(lowerCAmelCase_					).to(lowerCAmelCase_					)
     __lowerCAmelCase							     =     model(**lowerCAmelCase_					)
     self.assertTrue(outputs.loss is not None					)






  def     lowercase		(    self			:		Tuple					)							->						Any:
     __lowerCAmelCase     ,     __lowerCAmelCase							     =     self.model_tester.prepare_config_and_inputs_for_common()
     self.model_tester.create_and_check_maskaformer_model(lowerCAmelCase_ ,  **lowerCAmelCase_ ,  output_hidden_states=lowerCAmelCase_					)






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

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






  def     lowercase		(    self			:		Optional[int]					)							->						str:
     if not self.model_tester.is_training:
        return

     __lowerCAmelCase							     =     self.all_model_classes[1]
     __lowerCAmelCase     ,     __lowerCAmelCase     ,     __lowerCAmelCase     ,     __lowerCAmelCase     ,     __lowerCAmelCase							     =     self.model_tester.prepare_config_and_inputs()

     __lowerCAmelCase							     =     model_class(lowerCAmelCase_					)
     model.to(lowerCAmelCase_					)
     model.train()

     __lowerCAmelCase							     =     model(lowerCAmelCase_ ,  mask_labels=lowerCAmelCase_ ,  class_labels=lowerCAmelCase_					).loss
     loss.backward()






  def     lowercase		(    self			:		int					)							->						Optional[int]:
     __lowerCAmelCase							     =     self.all_model_classes[1]
     __lowerCAmelCase     ,     __lowerCAmelCase     ,     __lowerCAmelCase     ,     __lowerCAmelCase     ,     __lowerCAmelCase							     =     self.model_tester.prepare_config_and_inputs()
     __lowerCAmelCase							     =     True
     __lowerCAmelCase							     =     True

     __lowerCAmelCase							     =     model_class(lowerCAmelCase_					).to(lowerCAmelCase_					)
     model.train()

     __lowerCAmelCase							     =     model(lowerCAmelCase_ ,  mask_labels=lowerCAmelCase_ ,  class_labels=lowerCAmelCase_					)

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

     __lowerCAmelCase							     =     outputs.pixel_decoder_hidden_states[0]
     pixel_decoder_hidden_states.retain_grad()

     __lowerCAmelCase							     =     outputs.transformer_decoder_hidden_states[0]
     transformer_decoder_hidden_states.retain_grad()

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

     outputs.loss.backward(retain_graph=lowerCAmelCase_					)

     self.assertIsNotNone(encoder_hidden_states.grad					)
     self.assertIsNotNone(pixel_decoder_hidden_states.grad					)
     self.assertIsNotNone(transformer_decoder_hidden_states.grad					)
     self.assertIsNotNone(attentions.grad					)





_snake_case  :   Optional[int]						   =  1e-4

def   a_   (			):
   __lowerCAmelCase							     =     Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'     )
   return image




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

  """simple docstring"""


  @cached_property
  def     lowercase		(    self			:		Dict					)							->						int:
     return "facebook/mask2former-swin-small-coco-instance"






  @cached_property
  def     lowercase		(    self			:		Dict					)							->						Any:
     return MaskaFormerImageProcessor.from_pretrained(self.model_checkpoints					) if is_vision_available() else None






  def     lowercase		(    self			:		str					)							->						Optional[int]:
     __lowerCAmelCase							     =     MaskaFormerModel.from_pretrained(self.model_checkpoints					).to(lowerCAmelCase_					)
     __lowerCAmelCase							     =     self.default_image_processor
     __lowerCAmelCase							     =     prepare_img()
     __lowerCAmelCase							     =     image_processor(lowerCAmelCase_ ,  return_tensors='pt'					).to(lowerCAmelCase_					)
     __lowerCAmelCase							     =     inputs['pixel_values'].shape
     # check size is divisible by 32
     self.assertTrue((inputs_shape[-1] % 3_2) == 0 and (inputs_shape[-2] % 3_2) == 0					)
     # check size
     self.assertEqual(lowerCAmelCase_ ,  (1, 3, 3_8_4, 3_8_4)					)

     with torch.no_grad():
        __lowerCAmelCase							     =     model(**lowerCAmelCase_					)

     __lowerCAmelCase							     =     torch.tensor(
         [[-0.27_90, -1.07_17, -1.16_68], [-0.51_28, -0.31_28, -0.49_87], [-0.58_32, 0.19_71, -0.01_97]]					).to(lowerCAmelCase_					)
     self.assertTrue(
         torch.allclose(
             outputs.encoder_last_hidden_state[0, 0, :3, :3] ,  lowerCAmelCase_ ,  atol=lowerCAmelCase_					)					)

     __lowerCAmelCase							     =     torch.tensor(
         [[0.89_73, 1.18_47, 1.17_76], [1.19_34, 1.50_40, 1.51_28], [1.11_53, 1.44_86, 1.49_51]]					).to(lowerCAmelCase_					)
     self.assertTrue(
         torch.allclose(
             outputs.pixel_decoder_last_hidden_state[0, 0, :3, :3] ,  lowerCAmelCase_ ,  atol=lowerCAmelCase_					)					)

     __lowerCAmelCase							     =     torch.tensor(
         [[2.11_52, 1.70_00, -0.86_03], [1.58_08, 1.80_04, -0.93_53], [1.60_43, 1.74_95, -0.59_99]]					).to(lowerCAmelCase_					)
     self.assertTrue(
         torch.allclose(
             outputs.transformer_decoder_last_hidden_state[0, :3, :3] ,  lowerCAmelCase_ ,  atol=lowerCAmelCase_					)					)






  def     lowercase		(    self			:		Union[str, Any]					)							->						Any:
     __lowerCAmelCase							     =     MaskaFormerForUniversalSegmentation.from_pretrained(self.model_checkpoints					).to(lowerCAmelCase_					).eval()
     __lowerCAmelCase							     =     self.default_image_processor
     __lowerCAmelCase							     =     prepare_img()
     __lowerCAmelCase							     =     image_processor(lowerCAmelCase_ ,  return_tensors='pt'					).to(lowerCAmelCase_					)
     __lowerCAmelCase							     =     inputs['pixel_values'].shape
     # check size is divisible by 32
     self.assertTrue((inputs_shape[-1] % 3_2) == 0 and (inputs_shape[-2] % 3_2) == 0					)
     # check size
     self.assertEqual(lowerCAmelCase_ ,  (1, 3, 3_8_4, 3_8_4)					)

     with torch.no_grad():
        __lowerCAmelCase							     =     model(**lowerCAmelCase_					)
     # masks_queries_logits
     __lowerCAmelCase							     =     outputs.masks_queries_logits
     self.assertEqual(
         masks_queries_logits.shape ,  (1, model.config.num_queries, inputs_shape[-2] // 4, inputs_shape[-1] // 4)					)
     __lowerCAmelCase							     =     [
         [-8.78_39, -9.00_56, -8.81_21],
         [-7.41_04, -7.03_13, -6.54_01],
         [-6.61_05, -6.34_27, -6.46_75],
     ]
     __lowerCAmelCase							     =     torch.tensor(lowerCAmelCase_					).to(lowerCAmelCase_					)
     self.assertTrue(torch.allclose(masks_queries_logits[0, 0, :3, :3] ,  lowerCAmelCase_ ,  atol=lowerCAmelCase_					)					)
     # class_queries_logits
     __lowerCAmelCase							     =     outputs.class_queries_logits
     self.assertEqual(class_queries_logits.shape ,  (1, model.config.num_queries, model.config.num_labels + 1)					)
     __lowerCAmelCase							     =     torch.tensor(
         [
             [1.83_24, -8.08_35, -4.19_22],
             [0.84_50, -9.00_50, -3.60_53],
             [0.30_45, -7.72_93, -3.02_75],
         ]					).to(lowerCAmelCase_					)
     self.assertTrue(torch.allclose(outputs.class_queries_logits[0, :3, :3] ,  lowerCAmelCase_ ,  atol=lowerCAmelCase_					)					)






  def     lowercase		(    self			:		Optional[int]					)							->						Union[str, Any]:
     __lowerCAmelCase							     =     MaskaFormerForUniversalSegmentation.from_pretrained(self.model_checkpoints					).to(lowerCAmelCase_					).eval()
     __lowerCAmelCase							     =     self.default_image_processor

     __lowerCAmelCase							     =     image_processor(
         [np.zeros((3, 8_0_0, 1_3_3_3)					), np.zeros((3, 8_0_0, 1_3_3_3)					)] ,  segmentation_maps=[np.zeros((3_8_4, 3_8_4)					).astype(np.floataa					), np.zeros((3_8_4, 3_8_4)					).astype(np.floataa					)] ,  return_tensors='pt' ,  )

     __lowerCAmelCase							     =     inputs['pixel_values'].to(lowerCAmelCase_					)
     __lowerCAmelCase							     =     [el.to(lowerCAmelCase_					) for el in inputs['mask_labels']]
     __lowerCAmelCase							     =     [el.to(lowerCAmelCase_					) for el in inputs['class_labels']]

     with torch.no_grad():
        __lowerCAmelCase							     =     model(**lowerCAmelCase_					)

     self.assertTrue(outputs.loss is not None					)








import mpmath  # for roots of unity
import numpy as np



class     _UpperCAmelCase   :

  """simple docstring"""


  def __init__(    self			:		List[Any] ,  lowerCAmelCase_			:		Dict=None ,  lowerCAmelCase_			:		str=None					)							->						List[Any]:
     # Input as list
     __lowerCAmelCase							     =     list(poly_a or [0]					)[:]
     __lowerCAmelCase							     =     list(poly_b or [0]					)[:]

     # Remove leading zero coefficients
     while self.polyA[-1] == 0:
        self.polyA.pop()
     __lowerCAmelCase							     =     len(self.polyA					)

     while self.polyB[-1] == 0:
        self.polyB.pop()
     __lowerCAmelCase							     =     len(self.polyB					)

     # Add 0 to make lengths equal a power of 2
     __lowerCAmelCase							     =     int(
         2 ** np.ceil(np.loga(len(self.polyA					) + len(self.polyB					) - 1					)					)					)

     while len(self.polyA					) < self.c_max_length:
        self.polyA.append(0					)
     while len(self.polyB					) < self.c_max_length:
        self.polyB.append(0					)
     # A complex root used for the fourier transform
     __lowerCAmelCase							     =     complex(mpmath.root(x=1 ,  n=self.c_max_length ,  k=1					)					)

     # The product
     __lowerCAmelCase							     =     self.__multiply()






  def     lowercase		(    self			:		Optional[int] ,  lowerCAmelCase_			:		str					)							->						Optional[int]:
     __lowerCAmelCase							     =     [[x] for x in self.polyA] if which == 'A' else [[x] for x in self.polyB]
     # Corner case
     if len(lowerCAmelCase_					) <= 1:
        return dft[0]
     #
     __lowerCAmelCase							     =     self.c_max_length // 2
     while next_ncol > 0:
        __lowerCAmelCase							     =     [[] for i in range(lowerCAmelCase_					)]
        __lowerCAmelCase							     =     self.root**next_ncol

        # First half of next step
        __lowerCAmelCase							     =     1
        for j in range(self.c_max_length // (next_ncol * 2)					):
           for i in range(lowerCAmelCase_					):
              new_dft[i].append(dft[i][j] + current_root * dft[i + next_ncol][j]					)
           current_root *= root
        # Second half of next step
        __lowerCAmelCase							     =     1
        for j in range(self.c_max_length // (next_ncol * 2)					):
           for i in range(lowerCAmelCase_					):
              new_dft[i].append(dft[i][j] - current_root * dft[i + next_ncol][j]					)
           current_root *= root
        # Update
        __lowerCAmelCase							     =     new_dft
        __lowerCAmelCase							     =     next_ncol // 2
     return dft[0]






  def     lowercase		(    self			:		Optional[int]					)							->						Any:
     __lowerCAmelCase							     =     self.__dft('A'					)
     __lowerCAmelCase							     =     self.__dft('B'					)
     __lowerCAmelCase							     =     [[dft_a[i] * dft_b[i] for i in range(self.c_max_length					)]]
     del dft_a
     del dft_b

     # Corner Case
     if len(inverce_c[0]					) <= 1:
        return inverce_c[0]
     # Inverse DFT
     __lowerCAmelCase							     =     2
     while next_ncol <= self.c_max_length:
        __lowerCAmelCase							     =     [[] for i in range(lowerCAmelCase_					)]
        __lowerCAmelCase							     =     self.root ** (next_ncol // 2)
        __lowerCAmelCase							     =     1
        # First half of next step
        for j in range(self.c_max_length // next_ncol					):
           for i in range(next_ncol // 2					):
              # Even positions
              new_inverse_c[i].append(
                  (
                      inverce_c[i][j]
                      + inverce_c[i][j + self.c_max_length // next_ncol]
                  )
                  / 2					)
              # Odd positions
              new_inverse_c[i + next_ncol // 2].append(
                  (
                      inverce_c[i][j]
                      - inverce_c[i][j + self.c_max_length // next_ncol]
                  )
                  / (2 * current_root)					)
           current_root *= root
        # Update
        __lowerCAmelCase							     =     new_inverse_c
        next_ncol *= 2
     # Unpack
     __lowerCAmelCase							     =     [round(x[0].real ,  8					) + round(x[0].imag ,  8					) * 1J for x in inverce_c]

     # Remove leading 0's
     while inverce_c[-1] == 0:
        inverce_c.pop()
     return inverce_c






  def __str__(    self			:		Dict					)							->						int:
     __lowerCAmelCase							     =     'A = ' + ' + '.join(
         f"""{coef}*x^{i}""" for coef, i in enumerate(self.polyA[: self.len_A]					)					)
     __lowerCAmelCase							     =     'B = ' + ' + '.join(
         f"""{coef}*x^{i}""" for coef, i in enumerate(self.polyB[: self.len_B]					)					)
     __lowerCAmelCase							     =     'A*B = ' + ' + '.join(
         f"""{coef}*x^{i}""" for coef, i in enumerate(self.product					)					)

     return f"""{a}\n{b}\n{c}"""


# Unit tests
if __name__ == "__main__":
     import doctest

     doctest.testmod()

