package com.android.Algorithm;

public final class FastFourierTransform {

  private int n, nu;

  private int bitrev(int j) {

    int j2;
    int j1 = j;
    int k = 0;
    for (int i = 1; i <= nu; i++) {
      j2 = j1/2;
      k  = 2*k + j1 - 2*j2;
      j1 = j2;
    }
    return k;
  }
  /*public final int[] fftMag(int[] x) {
    // assume n is a power of 2
    n = x.length;
    nu = (int)(this.log(n)/this.log(2));
    int n2 = n/2;
    int nu1 = nu - 1;
    float[] xre = new float[n];
    float[] xim = new float[n];
    int[] mag = new int[n2];
    float tr, ti, p, arg, c, s;
    for (int i = 0; i < n; i++) {
      xre[i] = x[i];
      xim[i] = 0.0f;
    }
    int k = 0;

    for (int l = 1; l <= nu; l++) {
      while (k < n) {
        for (int i = 1; i <= n2; i++) {
          p = bitrev (k >> nu1);
          arg = 2 * (float) Math.PI * p / n;
          c = (float) Math.cos (arg);
          s = (float) Math.sin (arg);
          tr = xre[k+n2]*c + xim[k+n2]*s;
          ti = xim[k+n2]*c - xre[k+n2]*s;
          xre[k+n2] = xre[k] - tr;
          xim[k+n2] = xim[k] - ti;
          xre[k] += tr;
          xim[k] += ti;
          k++;
        }
        k += n2;
      }
      k = 0;
      nu1--;
      n2 = n2/2;
    }
    k = 0;
    int r;
    while (k < n) {
      r = bitrev (k);
      if (r > k) {
        tr = xre[k];
        ti = xim[k];
        xre[k] = xre[r];
        xim[k] = xim[r];
        xre[r] = tr;
        xim[r] = ti;
      }
      k++;
    }

    mag[0] = (int) (Math.sqrt(xre[0]*xre[0] + xim[0]*xim[0]))/n;
    for (int i = 1; i < n/2; i++)
      mag[i]= (int)(2 * (float) (Math.sqrt(xre[i]*xre[i] + xim[i]*xim[i]))/n);
    return mag;
  }*/
    public final double[] fftMag(double[] x) {
       // assume n is a power of 2
       n = x.length;
       nu = (int) (this.log(n) / this.log(2));
       int n2 = n / 2;
       int nu1 = nu - 1;
       double[] xre = new double[n];
       double[] xim = new double[n];
       double[] mag = new double[n2];
       double tr, ti, p, arg, c, s;
       for (int i = 0; i < n; i++) {
           xre[i] = x[i];
           xim[i] = 0.0f;
       }
       int k = 0;

       for (int l = 1; l <= nu; l++) {
           while (k < n) {
               for (int i = 1; i <= n2; i++) {
                   p = bitrev(k >> nu1);
                   arg = 2 * (float)Math.PI * p / n;
                   c = (float)Math.cos(arg);
                   s = (float)Math.sin(arg);
                   tr = xre[k + n2] * c + xim[k + n2] * s;
                   ti = xim[k + n2] * c - xre[k + n2] * s;
                   xre[k + n2] = xre[k] - tr;
                   xim[k + n2] = xim[k] - ti;
                   xre[k] += tr;
                   xim[k] += ti;
                   k++;
               }
               k += n2;
           }
           k = 0;
           nu1--;
           n2 = n2 / 2;
       }
       k = 0;
       int r;
       while (k < n) {
           r = bitrev(k);
           if (r > k) {
               tr = xre[k];
               ti = xim[k];
               xre[k] = xre[r];
               xim[k] = xim[r];
               xre[r] = tr;
               xim[r] = ti;
           }
           k++;
       }
       /*System.out.print("xre[]= ");
          for (int i = 0; i < n / 2; i++)
              System.out.print("("+i+")"+xre[i]+" ");
          System.out.println("");
          System.out.print("xim[]= ");
          for (int i = 0; i < n / 2; i++)
              System.out.print("("+i+")"+xim[i]+" ");
       System.out.println("");*/
       if(((Math.sqrt(xre[0] * xre[0] + xim[0] * xim[0])) / n)!=0)
    	   mag[0] = ((float) 10*log((Math.sqrt(xre[0] * xre[0] + xim[0] * xim[0])) / n));
       for (int i = 1; i < n / 2; i++){
    	   if(((Math.sqrt(xre[i] * xre[i] + xim[i] * xim[i])) / n)!=0)
    		   mag[i] = (10*log(2 * (float) (Math.sqrt(xre[i] * xre[i] + xim[i] * xim[i])) / n));
       }
       /*System.out.println("");
          System.out.print("mag[]= ");
          for (int i = 0; i < n / 2; i++)
              System.out.print("("+i+")"+mag[i]+" ");
       System.out.println("");*/

       return mag;
}
public final double[] fftMag2(double[] x) {
   // assume n is a power of 2
   n = x.length;
   nu = (int) (this.log(n) / this.log(2));
   int n2 = n / 2;
   int nu1 = nu - 1;
   double[] xre = new double[n];
   double[] xim = new double[n];
   double[] mag = new double[n2];
   double tr, ti, p, arg, c, s;
   for (int i = 0; i < n; i++) {
       xre[i] = x[i];
       xim[i] = 0.0f;
   }
   int k = 0;

   for (int l = 1; l <= nu; l++) {
       while (k < n) {
           for (int i = 1; i <= n2; i++) {
               p = bitrev(k >> nu1);
               arg = 2 * (float) Math.PI * p / n;
               c = (float) Math.cos(arg);
               s = (float) Math.sin(arg);
               tr = xre[k + n2] * c + xim[k + n2] * s;
               ti = xim[k + n2] * c - xre[k + n2] * s;
               xre[k + n2] = xre[k] - tr;
               xim[k + n2] = xim[k] - ti;
               xre[k] += tr;
               xim[k] += ti;
               k++;
           }
           k += n2;
       }
       k = 0;
       nu1--;
       n2 = n2 / 2;
   }
   k = 0;
   int r;
   while (k < n) {
       r = bitrev(k);
       if (r > k) {
           tr = xre[k];
           ti = xim[k];
           xre[k] = xre[r];
           xim[k] = xim[r];
           xre[r] = tr;
           xim[r] = ti;
       }
       k++;
   }

   mag[0] = (float) ((Math.sqrt(xre[0] * xre[0] + xim[0] * xim[0])) / n);
   for (int i = 1; i < n / 2; i++)
       mag[i] = (2 * (float) (Math.sqrt(xre[i] * xre[i] + xim[i] * xim[i])) / n);
   return mag;
}

  public final float[] fftMag(float[] x) {
    // assume n is a power of 2
    n = x.length;
    nu = (int)(this.log(n)/this.log(2));
    int n2 = n/2;
    int nu1 = nu - 1;
    float[] xre = new float[n];
    float[] xim = new float[n];
    float[] mag = new float[n2];
    float tr, ti, p, arg, c, s;
    for (int i = 0; i < n; i++) {
      xre[i] = x[i];
      xim[i] = 0.0f;
    }
    int k = 0;

    for (int l = 1; l <= nu; l++) {
      while (k < n) {
        for (int i = 1; i <= n2; i++) {
          p = bitrev (k >> nu1);
          arg = 2 * (float) Math.PI * p / n;
          c = (float) Math.cos (arg);
          s = (float) Math.sin (arg);
          tr = xre[k+n2]*c + xim[k+n2]*s;
          ti = xim[k+n2]*c - xre[k+n2]*s;
          xre[k+n2] = xre[k] - tr;
          xim[k+n2] = xim[k] - ti;
          xre[k] += tr;
          xim[k] += ti;
          k++;
        }
        k += n2;
      }
      k = 0;
      nu1--;
      n2 = n2/2;
    }
    k = 0;
    int r;
    while (k < n) {
      r = bitrev (k);
      if (r > k) {
        tr = xre[k];
        ti = xim[k];
        xre[k] = xre[r];
        xim[k] = xim[r];
        xre[r] = tr;
        xim[r] = ti;
      }
      k++;
    }

    mag[0] = (float) (Math.sqrt(xre[0]*xre[0] + xim[0]*xim[0]))/n;
    for (int i = 1; i < n/2; i++)
      mag[i]= 2 * (float) (Math.sqrt(xre[i]*xre[i] + xim[i]*xim[i]))/n;
    return mag;
  }
  static private double _log(double x){
   if(!(x>0.))
     return Double.NaN;
   //
   double f=0.0;
   //
   int appendix=0;
   while(x>0.0 && x<=1.0)
   {
     x*=2.0;
     appendix++;
   }
   //
   x/=2.0;
   appendix--;
   //
   double y1=x-1.;
   double y2=x+1.;
   double y=y1/y2;
   //
   double k=y;
   y2=k*y;
   //x
   for(long i=1; i<50; i+=2)
   {
     f+=k/i;
     k*=y2;
   }
   //
   f*=2.0;
   for(int i=0; i<appendix; i++)
     f+=-0.6931471805599453094;
   //
   return f;
 }

 static public double log(double x)
  {
    if(!(x>0.))
      return Double.NaN;
    //
    if(x==1.0)
      return 0.0;
    // Argument of _log must be (0; 1]
    if (x>1.)
    {
      x=1/x;
      //System.out.println("here A");
      return -_log(x);
    };
    //
    return _log(x);
  }

}
