/**
 * File: FFT.java
 * Author: Brian Borowski
 * Date created: October 2000
 * Date last modified: July 1, 2011
 */
public class FFT {
    public static final int FFT = 1, IFFT = -1;

    private final double[] ar, ai, x, y, yfft;
    private final int sampleSize;

    public FFT(final int sampleSize, final char character,
               final int numberOfHarmonics, final double period) {
        this.sampleSize = sampleSize;
        ar = new double[sampleSize];
        ai = new double[sampleSize];
        x = new double[sampleSize];
        y = new double[sampleSize];
        yfft = new double[sampleSize];
        createInputArrays(sampleSize, character);
        compute(FFT);
        for (int i = 0; i < sampleSize; ++i) {
            x[i] = (double)i / sampleSize * period;
            yfft[i] = series(x[i], numberOfHarmonics, period);
        }
    }

    public double[] getXValues() {
        return x;
    }

    public double[] getYValues() {
        return y;
    }

    public double[] getYFFTValues() {
        return yfft;
    }

    public double[] getRealValues() {
        return ar;
    }

    public double[] getImagValues() {
        return ai;
    }

    private double series(final double x, final int numberOfHarmonics,
                          final double period) {
        double y = ar[0] / 2.0;
        for (int i = 1; i <= numberOfHarmonics; ++i) {
            final double val = 2 * Math.PI * i / period * x;
            y += ar[i] * Math.cos(val) + ai[i] * Math.sin(val);
        }
        return y;
    }

    private void compute(final int sign) {
        final double scale = 2.0 / sampleSize;
        int i, j;
        for (i = j = 0; i < sampleSize; ++i) {
            if (j >= i) {
                final double tempr = ar[j] * scale;
                final double tempi = ai[j] * scale;
                ar[j] = ar[i] * scale;
                ai[j] = ai[i] * scale;
                ar[i] = tempr;
                ai[i] = tempi;
            }
            int m = sampleSize >> 1;
            while (m >= 1 && j >= m) {
                j -= m;
                m >>= 1;
            }
            j += m;
        }

        int mmax, istep;
        for (mmax = 1, istep = mmax << 1;
             mmax < sampleSize; mmax = istep, istep = mmax << 1) {

            final double delta = sign * Math.PI / mmax;
            for(int m = 0; m < mmax; ++m) {
                final double w = m * delta;
                final double wr = Math.cos(w);
                final double wi = Math.sin(w);
                for (i = m; i < sampleSize; i += istep) {
                    j = i + mmax;
                    final double tr = wr * ar[j] - wi * ai[j];
                    final double ti = wr * ai[j] + wi * ar[j];
                    ar[j] = ar[i] - tr;
                    ai[j] = ai[i] - ti;
                    ar[i] += tr;
                    ai[i] += ti;
                }
            }
            mmax = istep;
        }
    }

    private void createInputArrays(final int size, final char character) {
        final String s = Utility.binary8BitCode(character);
        for (int i = 0; i < size; ++i) {
            if (s.charAt((i << 3) / size) == '0') {
                ar[i] = y[i] = 0.0;
            } else {
                ar[i] = y[i] = 1.0;
            }
            ai[i] = 0.0;
        }
    }
}