use crate::Vec1;
#[cfg(not(feature = "std"))]
use alloc::vec::Vec;
#[cfg(feature = "std")]
use std::vec::Vec;
pub type Complex = (f64, f64);
impl Vec1<f64> {
pub fn dft(&self) -> Vec1<Complex> {
let n = self.len();
let mut out = Vec1::with_capacity(n);
for k in 1..=n {
let mut re = 0.0;
let mut im = 0.0;
for i in 1..=n {
let angle = -2.0 * core::f64::consts::PI * ((k - 1) * (i - 1)) as f64 / n as f64;
re += self[i] * libm::cos(angle);
im += self[i] * libm::sin(angle);
}
out.push((re, im));
}
out
}
}
impl Vec1<Complex> {
pub fn idft(&self) -> Vec1<f64> {
let n = self.len();
let mut out = Vec1::with_capacity(n);
for i in 1..=n {
let mut v = 0.0;
for k in 1..=n {
let angle = 2.0 * core::f64::consts::PI * ((k - 1) * (i - 1)) as f64 / n as f64;
let (re, im) = self[k];
v += re * libm::cos(angle) - im * libm::sin(angle);
}
out.push(v / n as f64);
}
out
}
pub fn fft(&self) -> Vec1<Complex> {
let n = self.len();
assert!(n.is_power_of_two(), "fft: length must be a power of two");
let mut buf: Vec<Complex> = (1..=n).map(|i| self[i]).collect();
let mut j = 0usize;
for i in 0..n {
if i < j {
buf.swap(i, j);
}
let mut m = n >> 1;
while m >= 1 && j >= m {
j -= m;
m >>= 1;
}
j += m;
}
let mut len = 2;
while len <= n {
let ang = -2.0 * core::f64::consts::PI / len as f64;
let (wr, wi) = (libm::cos(ang), libm::sin(ang));
let half = len / 2;
let mut i = 0;
while i < n {
let mut cur = (1.0, 0.0);
for k in 0..half {
let (ur, ui) = buf[i + k];
let (vr, vi) = buf[i + k + half];
let tr = cur.0 * vr - cur.1 * vi;
let ti = cur.0 * vi + cur.1 * vr;
buf[i + k] = (ur + tr, ui + ti);
buf[i + k + half] = (ur - tr, ui - ti);
let nr = cur.0 * wr - cur.1 * wi;
let ni = cur.0 * wi + cur.1 * wr;
cur = (nr, ni);
}
i += len;
}
len <<= 1;
}
let mut out = Vec1::with_capacity(n);
for v in buf {
out.push(v);
}
out
}
pub fn magnitude(&self) -> Vec1<f64> {
let mut out = Vec1::with_capacity(self.len());
for i in 1..=self.len() {
let (re, im) = self[i];
out.push(libm::sqrt(re * re + im * im));
}
out
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::vec1;
#[test]
fn dft_constant_signal() {
let s = vec1![1.0, 1.0, 1.0, 1.0];
let x = s.dft();
assert!((x[1].0 - 4.0).abs() < 1e-10);
assert!(x[1].1.abs() < 1e-10);
}
#[test]
fn fft_matches_dft() {
let s = vec1![1.0, 2.0, 3.0, 4.0];
let d = s.dft();
let sc: Vec1<Complex> = (1..=s.len()).map(|i| (s[i], 0.0)).collect();
let f = sc.fft();
for k in 1..=s.len() {
assert!((d[k].0 - f[k].0).abs() < 1e-10);
assert!((d[k].1 - f[k].1).abs() < 1e-10);
}
}
#[test]
fn idft_roundtrip() {
let s = vec1![1.0, 2.0, 3.0, 4.0];
let x = s.dft();
let back = x.idft();
for i in 1..=s.len() {
assert!((s[i] - back[i]).abs() < 1e-10);
}
}
#[test]
fn magnitude_basic() {
let spec = vec1![(3.0, 4.0), (0.0, 0.0)];
let mag = spec.magnitude();
assert!((mag[1] - 5.0).abs() < 1e-10);
assert!((mag[2] - 0.0).abs() < 1e-10);
}
}