one-indexed-vec 0.2.0

A one-based (1-indexed) wrapper around Vec<T>: element at position N is accessed via vec[N].
Documentation
//! Convolution and correlation.

use crate::Vec1;

impl<T> Vec1<T>
where
    T: Copy + core::ops::Add<Output = T> + core::ops::Mul<Output = T> + Default,
{
    /// Discrete convolution.
    ///
    /// Result length = `self.len() + other.len() - 1`, 1-based.
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    ///
    /// let a = vec1![1, 2, 3];
    /// let b = vec1![4, 5];
    /// let c = a.convolve(&b);
    /// assert_eq!(c.as_slice(), &[4, 13, 22, 15]);
    /// ```
    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
    }

    /// Cross-correlation of `self` with `other`.
    ///
    /// Equivalent to `self.convolve(&other.reversed())`.
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    ///
    /// let a = vec1![1, 2, 3];
    /// let b = vec1![1, 1];
    /// let c = a.cross_correlate(&b);
    /// assert_eq!(c.len(), 4);
    /// ```
    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)
    }

    /// Auto-correlation of `self` with itself.
    ///
    /// ```rust
    /// use one_indexed_vec::vec1;
    ///
    /// let a = vec1![1, 2, 3];
    /// let c = a.auto_correlate();
    /// // Result length = 2*3 - 1 = 5
    /// assert_eq!(c.len(), 5);
    /// ```
    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() {
        // Convolution with [1] is identity
        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();
        // Auto-correlation length = 2*3 - 1 = 5
        assert_eq!(c.len(), 5);
        // Symmetric around center: c[1] == c[5], c[2] == c[4]
        assert_eq!(c[1], c[5]);
        assert_eq!(c[2], c[4]);
    }
}