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

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

    static public int progress;

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

    static ComplexNumber cTwo = new ComplexNumber(2, 0);

    /**
     * Recursively applies the 1D inverse FFT algorithm.
     *
     * @param x ComplexNumber array containing the input to the 1D inverse FFT.
     * @return ComplexNumber array containing the result of the 1D inverse FFT.
     */
    static public ComplexNumber[] recursiveInverseFFT(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 = recursiveInverseFFT(sum);
            odd = recursiveInverseFFT(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;
    }

    /**
     * Takes a TwoDArray, applies the 2D inverse FFT to the input by applying
     * the 1D inverse FFT to each column and then each row in turn.
     *
     * @param input TwoDArray containing the input image data.
     * @return TwoDArray containing the new image data.
     */
    static public TwoDArray transform(TwoDArray input)
    {
        progress = 0;
        TwoDArray intermediate = new TwoDArray(input.width, input.height);
        TwoDArray output = new TwoDArray(input.width, input.height);

        for (int i = 0; i < input.size; ++i)
        {
            progress++;
            intermediate.putColumn(i, recursiveInverseFFT(input.getColumn(i)));
        }

        for (int i = 0; i < intermediate.size; ++i)
        {
            progress++;
            output.putRow(i, recursiveInverseFFT(intermediate.getRow(i)));
        }
        return output;
    }

    static public int[] getPixels(TwoDArray output)
    {
        double[] outputArrayDoubles =
                new double[output.width * output.height];
        outputArrayDoubles = output.getReal();
        //outputArrayDoubles = fft.output.getMagnitude();
        int[] outputArray; // = new int [outputArrayDoubles.length];
        //outputArray = ImageMods.toPixels(outputArrayDoubles);
        outputArray =
                toPixels(allPositive(outputArrayDoubles));

        return outputArray;
    }

    /**
     * Method to slide and scale an array of doubles so that the minimum
     * values is 0 (all positive).
     *
     * @param values An array of doubles.
     * @return An array of positive doubles.
     */
    static private double[] allPositive(double[] values)
    {
        double[] output = new double[values.length];
        double m = minValue(values);
        if (false) // m<0)
        {
            for (int i = 0; i < values.length; ++i)
            {
                output[i] = values[i] - m;
            }
            return output;
        } else
        {
            return values;
        }
    }

    static int[] toInts(double[] values)
    {
        int[] ints = new int[values.length];

        double scale = 1; // 1024 * 16; // ???
        
        for (int i = 0; i < values.length; ++i)
        {
            ints[i] = (int) (values[i]*scale);
        }

        return ints;
    }

    /** 
     * 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 = 1024 * 16;
//    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.
     */
    static 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;
    }

    static public int getProgress()
    {
        return progress;
    }
}