import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import kotlin.Metadata;
import kotlin._Assertions;
import kotlin.collections.ArraysKt;
import kotlin.collections.CollectionsKt;
import kotlin.collections.IntIterator;
import kotlin.jvm.internal.Intrinsics;
import kotlin.math.MathKt;
import kotlin.ranges.IntProgression;
import kotlin.ranges.RangesKt;
import org.jetbrains.annotations.NotNull;
import utils.BitReversalPermutationKt;
import utils.kotlinmath.BasicFunctionsKt;
import utils.kotlinmath.Complex;
import utils.kotlinmath.ComplexKt;

@Metadata(
   mv = {1, 1, 16},
   bv = {1, 0, 3},
   k = 2,
   d1 = {"\u0000,\n\u0000\n\u0002\u0010 \n\u0002\u0018\u0002\n\u0002\b\u0002\n\u0002\u0010\u000b\n\u0000\n\u0002\u0010\b\n\u0002\b\u0002\n\u0002\u0010\u0002\n\u0002\b\u0002\n\u0002\u0010\u0015\n\u0002\b\u0002\u001a$\u0010\u0000\u001a\b\u0012\u0004\u0012\u00020\u00020\u00012\f\u0010\u0003\u001a\b\u0012\u0004\u0012\u00020\u00020\u00012\b\b\u0002\u0010\u0004\u001a\u00020\u0005\u001a\u000e\u0010\u0006\u001a\u00020\u00072\u0006\u0010\b\u001a\u00020\u0007\u001a\u0006\u0010\t\u001a\u00020\n\u001a\u001c\u0010\u000b\u001a\b\u0012\u0004\u0012\u00020\u00020\u00012\u0006\u0010\f\u001a\u00020\r2\u0006\u0010\u000e\u001a\u00020\r¨\u0006\u000f"},
   d2 = {"fft", "", "Lutils/kotlinmath/Complex;", "input", "inverse", "", "logcap", "", "n", "main", "", "polynomialMultiplication", "a", "", "b", "kotlin"}
)
public final class FFTKt {
   public static final int logcap(int n) {
      return Integer.highestOneBit(n + Integer.highestOneBit(n) - 1);
   }

   @NotNull
   public static final List fft(@NotNull List input, boolean inverse) {
      Intrinsics.checkParameterIsNotNull(input, "input");
      boolean var2 = Integer.bitCount(input.size()) == 1;
      boolean var3 = false;
      boolean var4 = false;
      boolean var5;
      if (_Assertions.ENABLED && !var2) {
         var5 = false;
         String var27 = "Assertion failed";
         throw (Throwable)(new AssertionError(var27));
      } else {
         int[] permutation = BitReversalPermutationKt.bitReversalPermutation(Integer.numberOfTrailingZeros(input.size()));
         int n = permutation.length;
         var5 = false;
         ArrayList var6 = new ArrayList(n);
         boolean $i$f$map = false;
         boolean var8 = false;
         int var31 = 0;

         int var9;
         boolean $i$f$forEach;
         for(var9 = n; var31 < var9; ++var31) {
            boolean var11 = false;
            $i$f$forEach = false;
            Complex var22 = (Complex)input.get(permutation[var31]);
            var6.add(var22);
         }

         List var21 = (List)var6;
         Object output = var21;

         for(int len = 2; len <= output.size(); len *= 2) {
            int stride = len / 2;
            IntProgression var10000 = RangesKt.step((IntProgression)CollectionsKt.getIndices((Collection)output), len);
            int block = var10000.getFirst();
            var31 = var10000.getLast();
            var9 = var10000.getStep();
            if (var9 >= 0) {
               if (block > var31) {
                  continue;
               }
            } else if (block < var31) {
               continue;
            }

            while(true) {
               Complex w = (Complex)BasicFunctionsKt.getExp().invoke(ComplexKt.getI((Number)2).times(3.141592653589793D).div((Number)len).times((Number)inverse ? -1 : 1));
               Object wn = ComplexKt.getR((Number)1);
               Iterable $this$forEach$iv = (Iterable)RangesKt.until(block, block + stride);
               $i$f$forEach = false;
               Iterator var14 = $this$forEach$iv.iterator();

               while(var14.hasNext()) {
                  int element$iv = ((IntIterator)var14).nextInt();
                  int var17 = false;
                  Complex a = (Complex)output.get(element$iv);
                  Complex b = ((Complex)output.get(element$iv + stride)).times(wn);
                  wn = wn.times(w);
                  output.set(element$iv, a.plus(b));
                  output.set(element$iv + stride, a.minus(b));
               }

               if (block == var31) {
                  break;
               }

               block += var9;
            }
         }

         List var39;
         if (inverse) {
            Iterable $this$map$iv = (Iterable)output;
            $i$f$map = false;
            Collection destination$iv$iv = (Collection)(new ArrayList(CollectionsKt.collectionSizeOrDefault($this$map$iv, 10)));
            int $i$f$mapTo = false;
            Iterator var35 = $this$map$iv.iterator();

            while(var35.hasNext()) {
               Object item$iv$iv = var35.next();
               Complex it = (Complex)item$iv$iv;
               int var38 = false;
               Complex var40 = it.div((Number)n);
               destination$iv$iv.add(var40);
            }

            var39 = (List)destination$iv$iv;
         } else {
            var39 = output;
         }

         return var39;
      }
   }

   // $FF: synthetic method
   public static List fft$default(List var0, boolean var1, int var2, Object var3) {
      if ((var2 & 2) != 0) {
         var1 = false;
      }

      return fft(var0, var1);
   }

   @NotNull
   public static final List polynomialMultiplication(@NotNull int[] a, @NotNull int[] b) {
      Intrinsics.checkParameterIsNotNull(a, "a");
      Intrinsics.checkParameterIsNotNull(b, "b");
      int size = logcap(a.length + b.length);
      int[] $this$map$iv = ArraysKt.plus(a, new int[size - a.length]);
      int $i$f$map = false;
      Collection destination$iv$iv = (Collection)(new ArrayList($this$map$iv.length));
      int $i$f$mapTo = false;
      int[] var9 = $this$map$iv;
      int var10 = $this$map$iv.length;

      int var11;
      int item$iv$iv;
      Complex var20;
      for(var11 = 0; var11 < var10; ++var11) {
         item$iv$iv = var9[var11];
         int var14 = false;
         var20 = ComplexKt.getR((Number)item$iv$iv);
         destination$iv$iv.add(var20);
      }

      List afft = fft$default((List)destination$iv$iv, false, 2, (Object)null);
      int[] $this$map$iv = ArraysKt.plus(b, new int[size - b.length]);
      int $i$f$map = false;
      Collection destination$iv$iv = (Collection)(new ArrayList($this$map$iv.length));
      int $i$f$mapTo = false;
      int[] var30 = $this$map$iv;
      var11 = $this$map$iv.length;

      int item$iv$iv;
      for(item$iv$iv = 0; item$iv$iv < var11; ++item$iv$iv) {
         item$iv$iv = var30[item$iv$iv];
         int var15 = false;
         var20 = ComplexKt.getR((Number)item$iv$iv);
         destination$iv$iv.add(var20);
      }

      List bfft = fft$default((List)destination$iv$iv, false, 2, (Object)null);
      Iterable $this$zip$iv = (Iterable)afft;
      int $i$f$zip = false;
      Iterator first$iv = $this$zip$iv.iterator();
      Iterator second$iv = ((Iterable)bfft).iterator();
      var10 = CollectionsKt.collectionSizeOrDefault($this$zip$iv, 10);
      var11 = CollectionsKt.collectionSizeOrDefault((Iterable)bfft, 10);
      boolean var31 = false;
      item$iv$iv = Math.min(var10, var11);
      ArrayList list$iv = new ArrayList(item$iv$iv);

      while(first$iv.hasNext() && second$iv.hasNext()) {
         Object var10001 = first$iv.next();
         Complex bi = (Complex)second$iv.next();
         Complex ai = (Complex)var10001;
         int var18 = false;
         var20 = ai.times(bi);
         list$iv.add(var20);
      }

      List cfft = (List)list$iv;
      return fft(cfft, true);
   }

   public static final void main() {
      Iterable $this$map$iv = (Iterable)polynomialMultiplication(new int[]{3, 1, 5}, new int[]{2, 1, 9});
      int $i$f$map = false;
      Collection destination$iv$iv = (Collection)(new ArrayList(CollectionsKt.collectionSizeOrDefault($this$map$iv, 10)));
      int $i$f$mapTo = false;
      Iterator var5 = $this$map$iv.iterator();

      while(var5.hasNext()) {
         Object item$iv$iv = var5.next();
         Complex it = (Complex)item$iv$iv;
         int var8 = false;
         Integer var10 = MathKt.roundToInt(it.getRe());
         destination$iv$iv.add(var10);
      }

      List var11 = (List)destination$iv$iv;
      $i$f$map = false;
      System.out.println(var11);
   }

   // $FF: synthetic method
   public static void main(String[] var0) {
      main();
   }
}