var my_version = "fft.js=0.0.1"; if (ver_info_array){ver_info_array.push(my_version)} else {var ver_info_array = [my_version];};

// Javascritp implementation of fft and ifft
// (nympy compatible result with restriction N = 2**n)
//
// This module is released under MIT License
// https://opensource.org/licenses/MIT
//
// Copyright 2021 Shoji SUZUKI
//
// Permission is hereby granted, free of charge, to any person obtaining 
// a copy of this software and associated documentation files (the "Software"), 
// to deal in the Software without restriction, including without limitation 
// the rights to use, copy, modify, merge, publish, distribute, sublicense, 
// and/or sell copies of the Software, and to permit persons to whom the Software 
// is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in 
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 
// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

function fft_ex(real, imag, N, inv=false){
    ///////// FFT/IFFT main function
	// Input
    // real:	Real part array (will be reused for the output)
    // imag:	Imaginery part array (will be reused for the output)
    // N: 		Number of elements (must be a 2's power)
    // inv:		true for ifft
    /////////////////////////////////////////
    // Output
    // real:	Real part array
    // imag:	Imaginery part array
    /////////////////////////////////////////
    let ff = inv ? 1 : -1;
    let rot = new Array(N);
    for(let i = 0; i <N; i++) rot[i] = 0;
    let nhalf = N/2, num = N/2;
    let sc = 2 * Math.PI / N;
    while(num >= 1){
        for(let j = 0; j < N; j += 2 * num) {
            let phi = rot[j] / 2;
            let phi0 = phi + nhalf;
            let c = Math.cos(sc * phi);
            let s = Math.sin(sc * phi * ff);
            for(let k = j; k < j + num; k++) {
                let k1 = k + num;
                let a0 = real[k1] * c - imag[k1] *s;
                let b0 = real[k1] * s + imag[k1] *c;
                real[k1] = real[k] - a0;
                imag[k1] = imag[k] - b0;
                real[k] = real[k] + a0;
                imag[k] = imag[k] + b0;
                rot[k] = phi;
                rot[k1] = phi0;
            }
        }
        num /= 2;
    }

	// bit-reversal
    for(let i = 0; i < N ; i++) {
        let j = rot[i]; 
        if(j > i) {
			[real[i],real[j] ] = [real[j],real[i] ];
			[imag[i],imag[j] ] = [imag[j],imag[i] ];
        }
    }
	if (!inv) return;	// done for fft
	
	// Scale ifft result
	let ninv = 1. / N;
    for(let i = 0; i <N; i++) {
		real[i] *= ninv;
		imag[i] *= ninv;
	}
}

function fft_ex2(y_real, y_imag, N, inv=false){
    ///////// FFT/IFFT sub function
	// Input
    // y_real:	Real part array (the contents to be preserved)
    // y_imag:	Imaginery part array (the contents to be preserved)
    // N: 		Number of elements (must be a 2's power)
    // inv:		true for ifft
    /////////////////////////////////////////
    // Output
    // real:	Real part array (a new array object to be created)
    // imag:	Imaginery part array (a new array object to be created)
    /////////////////////////////////////////
	let real = new Array(N);
	let imag = new Array(N);
	for (let i=0; i<N; i++) {
		real[i] = y_real[i];
		imag[i] = y_imag[i];
	}

	fft_ex(real,imag,N,inv);
	return [real,imag];
}

function fft(y_real, y_imag, N){
    ///////// FFT helper function
	return fft_ex2(y_real,y_imag,N,false);
}

function ifft(y_real, y_imag, N){
    ///////// IFFT helper function
	return fft_ex2(y_real,y_imag,N,true);
}
