import javolution.context.ObjectFactory;
import javolution.context.StackContext;
import javolution.lang.ValueType;

/**
 * JavaWorld: Real-time Java Application Development For Multi-core Systems.
 * This code is public domain.
 */
public class Test2 {

    static final int LOG2_N = 14;
    static final int N = << LOG2_N;
    static final int K = 16// Number of frames.

    public static void main(String[] argsthrows Exception {
        Complex[][] frames = new Complex[K][N];
        Complex[][] results = new Complex[K][N];
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < N; j++) {
                frames[i][j= Complex.valueOf(Math.random(), Math.random());
            }
        }
        fft(frames[0], results[0])// Forces code compilation if -XX:CompileThreshold=1  
        long max = 0, sum = 0;
        final int n = 1000;
        for (int i = 0; i < n; i++) {
            // Thread.sleep(5); Not needed anymore.
            long time = System.nanoTime();
            fft(frames[i % K], results[i % K]);
            time = System.nanoTime() - time;
            // System.out.println(time / 1000000.0); // Milliseconds.
            if (time > max) {
                max = time;
            }
            sum += time;
        }
        System.out.println("Maximum Execution Time: " (max / 1000000.0" ms");
        System.out.println("Average Execution Time: " (sum / n / 1000000.0" ms");
    }

    static void fft(Complex[] a, final Complex[] A) {
        StackContext.enter()// Enters new allocation stack.
        try {
            for (int i = 0; i < N; ++i) {
                A[reverseBits(i)] = a[i];
            }
            for (int s = 1; s <= LOG2_N; ++s) {
                int m = << s;
                Complex w = Complex.valueOf(10);
                Complex wm = Complex.valueOf(Math.cos(* Math.PI / m), Math.sin(* Math.PI / m));
                for (int j = 0; j < m / 2; ++j) {
                    for (int k = j; k < N; k += m) {
                        Complex t = w.times(A[k + m / 2]);
                        Complex u = A[k];
                        A[k= u.plus(t);
                        A[k + m / 2= u.minus(t);
                    }
                    w = w.times(wm);
                }
            }
        finally {
            StackContext.outerCopy(A)// Exports array results
            StackContext.exit()// Resets stack.
        }
    }

    static int reverseBits(int x) {
        int n = 0;
        for (int i = 0; i < LOG2_N; i++) {
            n <<= 1;
            n |= (x & 1);
            x >>= 1;
        }
        return n;
    }

    static class Complex implements ValueType {

        static final ObjectFactory<Complex> FACTORY =
                new ObjectFactory<Complex>() {

                    @Override
                    protected Complex create() {
                        return new Complex();
                    }
                };
        double _real, _imag;

        static Complex valueOf(double real, double imag) {
            Complex complex = FACTORY.object();
            complex._real = real;
            complex._imag = imag;
            return complex;
        }

        Complex plus(Complex that) {
            return Complex.valueOf(this._real + that._real, this._imag + that._real);
        }

        Complex minus(Complex that) {
            return Complex.valueOf(this._real - that._real, this._imag - that._real);
        }

        Complex times(Complex that) {
            return Complex.valueOf(this._real * that._real - this._imag * that._imag,
                    this._real * that._imag + this._imag * that._real);
        }

        public Complex copy() { // Implements ValueType.
            return Complex.valueOf(_real, _imag);
        }
    }
}