package jsci.maths;

/**
* The Fourier math library.
* This class cannot be subclassed or instantiated because all methods are static.
* Use sort(transform(sort(...))) for the discrete analogue of the continuous Fourier transform,
* and sort(inverseTransform(sort(...))) for the inverse transform.
* @jsci.planetmath FourierTransform
* @version 0.9
* @author Mark Hale
*/
public final class FourierMath extends AbstractMath implements NumericalConstants {
        private FourierMath() {}

        /**
        * Fourier transform (2Pi convention).
        * @param data an array containing the positive time part of the signal
        * followed by the negative time part.
        * @return an array containing positive frequencies in ascending order
        * followed by negative frequencies in ascending order.
        * @author Don Cross
        */
        public static Complex[] transform(final Complex data[]) {
                final int N=data.length;
                if(!isPowerOf2(N))
                        throw new IllegalArgumentException("The number of samples must be a power of 2.");

                final double arrayRe[]=new double[N];
                final double arrayIm[]=new double[N];

                final int numBits=numberOfBitsNeeded(N);
// Simultaneous data copy and bit-reversal ordering into output
                for(int i=0;i0)
                                return i;
                }
        }
        /**
        * Reverse bits.
        * @author Don Cross
        */
        private static int reverseBits(int index,final int numBits) {
                int i,rev;
                for(i=rev=0;i>=1;
                }
                return rev;
        }

        /**
        * Sorts the output from the Fourier transfom methods into
        * ascending frequency/time order.
        */
        public static Complex[] sort(final Complex output[]) {
                final Complex ret[]=new Complex[output.length];
                final int Nby2=output.length/2;
                for(int i=0;i