use crate::Vec1;
impl<T> Vec1<T>
where
T: Copy + core::ops::Add<Output = T> + core::ops::Mul<Output = T> + Default,
{
pub fn convolve(&self, other: &Vec1<T>) -> Vec1<T> {
if self.is_empty() || other.is_empty() {
return Vec1::new();
}
let n = self.len();
let m = other.len();
let mut out = Vec1::with_capacity(n + m - 1);
for k in 1..=n + m - 1 {
let mut acc = T::default();
let lo = if k > m { k - m + 1 } else { 1 };
let hi = k.min(n);
for i in lo..=hi {
acc = acc + self[i] * other[k - i + 1];
}
out.push(acc);
}
out
}
pub fn cross_correlate(&self, other: &Vec1<T>) -> Vec1<T> {
if self.is_empty() || other.is_empty() {
return Vec1::new();
}
let mut rev = Vec1::with_capacity(other.len());
for i in (1..=other.len()).rev() {
rev.push(other[i]);
}
self.convolve(&rev)
}
pub fn auto_correlate(&self) -> Vec1<T> {
self.cross_correlate(self)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::vec1;
#[test]
fn convolve_basic() {
let a = vec1![1, 2, 3];
let b = vec1![4, 5];
assert_eq!(a.convolve(&b).as_slice(), &[4, 13, 22, 15]);
}
#[test]
fn convolve_with_delta() {
let a = vec1![1, 2, 3, 4];
let delta = vec1![1];
assert_eq!(a.convolve(&delta).as_slice(), a.as_slice());
}
#[test]
fn convolve_empty() {
let a: Vec1<i32> = Vec1::new();
let b = vec1![1, 2];
assert!(a.convolve(&b).is_empty());
}
#[test]
fn cross_correlate_len() {
let a = vec1![1, 2, 3];
let b = vec1![1, 1];
assert_eq!(a.cross_correlate(&b).len(), 4);
}
#[test]
fn auto_correlate_basic() {
let a = vec1![1, 2, 3];
let c = a.auto_correlate();
assert_eq!(c.len(), 5);
assert_eq!(c[1], c[5]);
assert_eq!(c[2], c[4]);
}
}