quantlib_rs 0.1.0

A ground-up, idiomatic Rust quantitative finance library inspired by QuantLib.
Documentation
//! Interpolation algorithms (Linear and Natural Cubic Spline).

use thiserror::Error;

/// Error type for interpolation operations.
#[derive(Debug, Clone, PartialEq, Error)]
pub enum InterpolationError {
    /// Insufficient data points provided for interpolation.
    #[error("At least {required} points required, but {provided} were provided")]
    InsufficientPoints {
        /// Number of points required
        required: usize,
        /// Number of points provided
        provided: usize,
    },
    /// Length of x and y slices do not match.
    #[error("Dimension mismatch: x has length {x_len}, y has length {y_len}")]
    DimensionMismatch {
        /// Length of x
        x_len: usize,
        /// Length of y
        y_len: usize,
    },
    /// Provided x-coordinates are not strictly increasing.
    #[error("x-coordinates must be strictly sorted in increasing order")]
    NonMonotonicX,
    /// Query point is outside interpolation range and extrapolation is disabled.
    #[error("Value {0} is outside interpolation range [{1}, {2}]")]
    ExtrapolationNotAllowed(f64, f64, f64),
}

/// Extrapolation policy for out-of-range queries.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum Extrapolation {
    /// Disallow extrapolation; return an error if queried outside $[x_0, x_{n-1}]$.
    #[default]
    None,
    /// Clamp to the boundary values ($y_0$ for $x < x_0$, $y_{n-1}$ for $x > x_{n-1}$).
    Flat,
    /// Linearly extrapolate beyond the boundaries using the outermost slope.
    Linear,
}

/// 1D Linear Interpolation over sorted points $(x_i, y_i)$.
///
/// # Examples
/// ```
/// use quantlib_rs::math::interpolation::{LinearInterpolation, Extrapolation};
///
/// let xs = vec![0.0, 1.0, 2.0, 3.0];
/// let ys = vec![0.0, 10.0, 20.0, 30.0];
/// let interp = LinearInterpolation::new(xs, ys, Extrapolation::Linear).unwrap();
///
/// assert!((interp.interpolate(1.5).unwrap() - 15.0).abs() < 1e-12);
/// assert!((interp.interpolate(3.5).unwrap() - 35.0).abs() < 1e-12);
/// ```
#[derive(Debug, Clone)]
pub struct LinearInterpolation {
    xs: Vec<f64>,
    ys: Vec<f64>,
    extrapolation: Extrapolation,
}

impl LinearInterpolation {
    /// Construct a new [`LinearInterpolation`] instance.
    pub fn new(
        xs: Vec<f64>,
        ys: Vec<f64>,
        extrapolation: Extrapolation,
    ) -> Result<Self, InterpolationError> {
        if xs.len() < 2 {
            return Err(InterpolationError::InsufficientPoints {
                required: 2,
                provided: xs.len(),
            });
        }
        if xs.len() != ys.len() {
            return Err(InterpolationError::DimensionMismatch {
                x_len: xs.len(),
                y_len: ys.len(),
            });
        }
        for i in 1..xs.len() {
            if xs[i] <= xs[i - 1] {
                return Err(InterpolationError::NonMonotonicX);
            }
        }
        Ok(Self {
            xs,
            ys,
            extrapolation,
        })
    }

    /// Evaluate the interpolated value at `x`.
    pub fn interpolate(&self, x: f64) -> Result<f64, InterpolationError> {
        let n = self.xs.len();
        let x_min = self.xs[0];
        let x_max = self.xs[n - 1];

        if x < x_min {
            return match self.extrapolation {
                Extrapolation::None => {
                    Err(InterpolationError::ExtrapolationNotAllowed(x, x_min, x_max))
                }
                Extrapolation::Flat => Ok(self.ys[0]),
                Extrapolation::Linear => {
                    let dx = self.xs[1] - self.xs[0];
                    let dy = self.ys[1] - self.ys[0];
                    let slope = dy / dx;
                    Ok(self.ys[0] + slope * (x - x_min))
                }
            };
        }

        if x > x_max {
            return match self.extrapolation {
                Extrapolation::None => {
                    Err(InterpolationError::ExtrapolationNotAllowed(x, x_min, x_max))
                }
                Extrapolation::Flat => Ok(self.ys[n - 1]),
                Extrapolation::Linear => {
                    let dx = self.xs[n - 1] - self.xs[n - 2];
                    let dy = self.ys[n - 1] - self.ys[n - 2];
                    let slope = dy / dx;
                    Ok(self.ys[n - 1] + slope * (x - x_max))
                }
            };
        }

        // Binary search for interval [xs[i], xs[i+1]] containing x
        let idx = self.xs.partition_point(|&val| val <= x);
        let i = if idx == 0 {
            0
        } else if idx >= n {
            n - 2
        } else {
            idx - 1
        };

        let x0 = self.xs[i];
        let x1 = self.xs[i + 1];
        let y0 = self.ys[i];
        let y1 = self.ys[i + 1];

        let t = (x - x0) / (x1 - x0);
        Ok(y0 + t * (y1 - y0))
    }
}

/// Natural Cubic Spline interpolation ($C^2$ continuous, zero curvature at boundaries).
///
/// Second derivatives $M_i = S''(x_i)$ are computed by solving a tridiagonal linear
/// system via the Thomas algorithm in $O(n)$ time.
///
/// # Examples
/// ```
/// use quantlib_rs::math::interpolation::{CubicSpline, Extrapolation};
///
/// let xs = vec![0.0, 1.0, 2.0, 3.0, 4.0];
/// let ys = vec![0.0, 1.0, 8.0, 27.0, 64.0]; // y = x^3
/// let spline = CubicSpline::new(xs, ys, Extrapolation::Linear).unwrap();
///
/// let val = spline.interpolate(2.0).unwrap();
/// assert!((val - 8.0).abs() < 1e-10);
/// ```
#[derive(Debug, Clone)]
pub struct CubicSpline {
    xs: Vec<f64>,
    ys: Vec<f64>,
    /// Second derivatives $M_i$ at each knot
    m: Vec<f64>,
    extrapolation: Extrapolation,
}

impl CubicSpline {
    /// Construct a new Natural Cubic Spline.
    pub fn new(
        xs: Vec<f64>,
        ys: Vec<f64>,
        extrapolation: Extrapolation,
    ) -> Result<Self, InterpolationError> {
        let n = xs.len();
        if n < 3 {
            return Err(InterpolationError::InsufficientPoints {
                required: 3,
                provided: n,
            });
        }
        if n != ys.len() {
            return Err(InterpolationError::DimensionMismatch {
                x_len: n,
                y_len: ys.len(),
            });
        }
        for i in 1..n {
            if xs[i] <= xs[i - 1] {
                return Err(InterpolationError::NonMonotonicX);
            }
        }

        // Step 1: Compute interval lengths h_i = x_{i+1} - x_i
        let mut h = vec![0.0; n - 1];
        for i in 0..n - 1 {
            h[i] = xs[i + 1] - xs[i];
        }

        // Step 2: Set up tridiagonal system for interior second derivatives M_1 .. M_{n-2}
        // Natural boundary condition: M_0 = 0, M_{n-1} = 0
        let m_size = n - 2;
        let mut a = vec![0.0; m_size]; // sub-diagonal
        let mut b = vec![0.0; m_size]; // main diagonal
        let mut c = vec![0.0; m_size]; // super-diagonal
        let mut d = vec![0.0; m_size]; // right hand side

        for i in 0..m_size {
            let knot = i + 1;
            let h_prev = h[knot - 1];
            let h_curr = h[knot];

            b[i] = 2.0 * (h_prev + h_curr);
            if i > 0 {
                a[i] = h_prev;
            }
            if i < m_size - 1 {
                c[i] = h_curr;
            }

            let slope_curr = (ys[knot + 1] - ys[knot]) / h_curr;
            let slope_prev = (ys[knot] - ys[knot - 1]) / h_prev;
            d[i] = 6.0 * (slope_curr - slope_prev);
        }

        // Step 3: Solve tridiagonal system using Thomas algorithm
        let mut c_prime = vec![0.0; m_size];
        let mut d_prime = vec![0.0; m_size];

        c_prime[0] = c[0] / b[0];
        d_prime[0] = d[0] / b[0];

        for i in 1..m_size {
            let denom = b[i] - a[i] * c_prime[i - 1];
            c_prime[i] = if i < m_size - 1 { c[i] / denom } else { 0.0 };
            d_prime[i] = (d[i] - a[i] * d_prime[i - 1]) / denom;
        }

        let mut m_interior = vec![0.0; m_size];
        m_interior[m_size - 1] = d_prime[m_size - 1];
        for i in (0..m_size - 1).rev() {
            m_interior[i] = d_prime[i] - c_prime[i] * m_interior[i + 1];
        }

        // Full second derivatives array with natural boundary conditions
        let mut m = vec![0.0; n];
        m[0] = 0.0;
        m[n - 1] = 0.0;
        m[1..n - 1].copy_from_slice(&m_interior);

        Ok(Self {
            xs,
            ys,
            m,
            extrapolation,
        })
    }

    /// Evaluate the cubic spline at point `x`.
    pub fn interpolate(&self, x: f64) -> Result<f64, InterpolationError> {
        let n = self.xs.len();
        let x_min = self.xs[0];
        let x_max = self.xs[n - 1];

        if x < x_min {
            return match self.extrapolation {
                Extrapolation::None => {
                    Err(InterpolationError::ExtrapolationNotAllowed(x, x_min, x_max))
                }
                Extrapolation::Flat => Ok(self.ys[0]),
                Extrapolation::Linear => {
                    let slope = self.derivative(x_min);
                    Ok(self.ys[0] + slope * (x - x_min))
                }
            };
        }

        if x > x_max {
            return match self.extrapolation {
                Extrapolation::None => {
                    Err(InterpolationError::ExtrapolationNotAllowed(x, x_min, x_max))
                }
                Extrapolation::Flat => Ok(self.ys[n - 1]),
                Extrapolation::Linear => {
                    let slope = self.derivative(x_max);
                    Ok(self.ys[n - 1] + slope * (x - x_max))
                }
            };
        }

        // Locate interval
        let idx = self.xs.partition_point(|&val| val <= x);
        let i = if idx == 0 {
            0
        } else if idx >= n {
            n - 2
        } else {
            idx - 1
        };

        let x_i = self.xs[i];
        let x_ip1 = self.xs[i + 1];
        let h = x_ip1 - x_i;
        let y_i = self.ys[i];
        let y_ip1 = self.ys[i + 1];
        let m_i = self.m[i];
        let m_ip1 = self.m[i + 1];

        let dx_left = x - x_i;
        let dx_right = x_ip1 - x;

        let term1 = (m_i * dx_right.powi(3) + m_ip1 * dx_left.powi(3)) / (6.0 * h);
        let term2 = (y_i - m_i * h.powi(2) / 6.0) * dx_right / h;
        let term3 = (y_ip1 - m_ip1 * h.powi(2) / 6.0) * dx_left / h;

        Ok(term1 + term2 + term3)
    }

    /// Evaluate the first derivative of the spline at point `x`.
    pub fn derivative(&self, x: f64) -> f64 {
        let n = self.xs.len();
        let idx = self.xs.partition_point(|&val| val <= x);
        let i = if idx == 0 {
            0
        } else if idx >= n {
            n - 2
        } else {
            idx - 1
        };

        let x_i = self.xs[i];
        let x_ip1 = self.xs[i + 1];
        let h = x_ip1 - x_i;
        let y_i = self.ys[i];
        let y_ip1 = self.ys[i + 1];
        let m_i = self.m[i];
        let m_ip1 = self.m[i + 1];

        let dx_left = x - x_i;
        let dx_right = x_ip1 - x;

        -m_i * dx_right.powi(2) / (2.0 * h)
            + m_ip1 * dx_left.powi(2) / (2.0 * h)
            + (y_ip1 - y_i) / h
            - (m_ip1 - m_i) * h / 6.0
    }
}