import java.lang.Math.*;
import java.awt.*;

/**
 * The FFT class contains methods to apply the 2D FFT to a
 * TwoDArray.
 *
 * @author Simon Horne
 */
public class FFT
{

    /**
     * Data structure to hold the input to the algorithm.
     */
    public TwoDArray input;
    /**
     * Data structure to hold the intermediate results of the algorithm.
     * After applying the 1D FFT to the columns but before the rows.
     */
    public TwoDArray intermediate;
    /**
     * Data structure to hold the ouput of the algorithm.
     */
    public TwoDArray output;
    public int progress;

    /**
     * Default no argument constructor.
     */
    public FFT()
    {
    }

    /** 
     * Constructor to set up an FFT object and then automatically 
     * apply the FFT algorithm.
     *
     * @param pixels  int array containing the image data.
     * @param w  The width of the image in pixels.
     * @param h  The height of the image in pixels.
     */
    public FFT(double[] pixels, int w, int h)
    {
        progress = 0;
        input = new TwoDArray(pixels, w, h);
        intermediate = new TwoDArray(pixels, w, h);
        output = new TwoDArray(pixels, w, h);
        transform();
    }

    static ComplexNumber cTwo = new ComplexNumber(2, 0);
    /**
     * Method to recursively apply the 1D FFT to a ComplexNumber array.
     *
     * @param  x  A ComplexNumber array containing a row or a column of
     * image data.
     * @return A ComplexNumber array containing the result of the 1D FFT.
     */
    static ComplexNumber[] recursiveFFT(ComplexNumber[] x)
    {
        ComplexNumber z1, z2, z3, z4, tmp;
        int n = x.length;
        int m = n / 2;
        ComplexNumber[] result = new ComplexNumber[n];
        ComplexNumber[] even = new ComplexNumber[m];
        ComplexNumber[] odd = new ComplexNumber[m];
        ComplexNumber[] sum = new ComplexNumber[m];
        ComplexNumber[] diff = new ComplexNumber[m];
        if (n == 1)
        {
            result[0] = x[0];
        } else
        {
            z1 = new ComplexNumber(0.0, -2 * (Math.PI) / n);
            tmp = ComplexNumber.cExp(z1);
            z1 = new ComplexNumber(1.0, 0.0);
            for (int i = 0; i < m; ++i)
            {
                z3 = ComplexNumber.cSum(x[i], x[i + m]);
                sum[i] = ComplexNumber.cDiv(z3, cTwo);

                z3 = ComplexNumber.cDif(x[i], x[i + m]);
                z4 = ComplexNumber.cMult(z3, z1);
                diff[i] = ComplexNumber.cDiv(z4, cTwo);

                z2 = ComplexNumber.cMult(z1, tmp);
                z1 = new ComplexNumber(z2);
            }
            even = recursiveFFT(sum);
            odd = recursiveFFT(diff);

            for (int i = 0; i < m; ++i)
            {
                result[i * 2] = new ComplexNumber(even[i]);
                result[i * 2 + 1] = new ComplexNumber(odd[i]);
            }
        }
        return result;
    }

    /**
     * Method to apply the 2D FFT by applying the recursive 1D FFT to the
     * columns and then the rows of image data.
     */
    void transform()
    {

        for (int i = 0; i < input.size; ++i)
        {
            progress++;
            intermediate.putColumn(i, recursiveFFT(input.getColumn(i)));
        }
        for (int i = 0; i < intermediate.size; ++i)
        {
            //System.out.println("i = " + i);
            progress++;
            output.putRow(i, recursiveFFT(intermediate.getRow(i)));
        }
    /*
    for(int j=0;j<output.values.length;++j){
    for(int i=0;i<output.values[0].length;++i){
    intermediate.values[i][j] = output.values[i][j];
    input.values[i][j] = output.values[i][j];
    }
    }
     */
    }

    public int[] getPixels()
    {
//	return toPixels(logs(intermediate.DCToCentre(intermediate.getMagnitude())));
        return toPixels(logs(output.DCToCentre(output.getMagnitude())));
    }

    /**
     * A method to convert an array of doubles to an array of their log values.
     *
     * @param values An array of doubles (all positive).
     * @return An array of doubles.
     */
    private double[] logs(double[] values)
    {
        double[] output = new double[values.length];
        /*
        for(int i=0;i<values.length;++i){
        values[i] = values[i]*1024*1024;
        }
        double c = 255/Math.log(1+maxValue(values));
         * */
        for (int i = 0; i < values.length; ++i)
        {
//      output[i] = c * Math.log(1+values[i]);
            output[i] = 127 * Math.log(1 + values[i]);
        }
        return output;
    }

    /** 
     * A method to convert an array of grey values to an array of pixel values.
     *
     * @param values An array of grey values (all positive).
     * @return An array of pixel values.
     */
    static int[] toPixels(double[] values)
    {
        int grey;
//    double [] greys = new double [values.length];
        int[] pixels = new int[values.length];
//    for(int i=0;i<greys.length;++i){
//      greys[i] = values[i];
//    }
//    double max = maxValue(greys);
//    double max = maxValue(values);
        double scale;
//    if (max == 0)
        scale = 1; // 1024.0*1024;
//    else scale = 255.0/max;

        //System.out.println(max);
//    for(int i=0;i<greys.length;++i){
        for (int i = 0; i < values.length; ++i)
        {
//      greys[i] = greys[i] * 255/max;
//      grey = (int) Math.round(greys[i]);
            grey = (int) /*Math.round*/ (values[i] * scale);
            if (grey < 0)
            {
                grey = 0;
            }
            pixels[i] = grey; // new Color(grey,grey,grey).getRGB(); //recombine greys
        }
        return pixels;
    }

    /**
     * Method to find the maximum value from an array of doubles.
     *
     * @param values an array of doubles.
     * @return The maximum value.
     */
    static private double maxValue(double[] values)
    {
        double max = values[0];
        for (int i = 1; i < values.length; ++i)
        {
            if (values[i] > max)
            {
                max = values[i];
            }
        }
        return max;
    }

    /**
     * Method to find the minimum value from an array of doubles.
     *
     * @param values an array of doubles.
     * @return The minimum value.
     */
    private double minValue(double[] values)
    {
        double min = values[0];
        for (int i = 1; i < values.length; ++i)
        {
            if (values[i] < min)
            {
                min = values[i];
            }
        }
        return min;
    }

    public int getProgress()
    {
        return progress;
    }
}