#![cfg_attr(test, allow(clippy::unwrap_used, reason = "test scope"))]
use super::{check_bounds, validate_nodes, Interpolation1D};
use eunomia::{NumericElement, RealField};
use leto::{LetoError, Result};
#[derive(Debug, Clone)]
pub struct LagrangeInterpolation<T: RealField> {
x_data: Vec<T>,
y_data: Vec<T>,
weights: Vec<T>,
}
impl<T: RealField> LagrangeInterpolation<T> {
pub fn new(x_data: Vec<T>, y_data: Vec<T>) -> Result<Self> {
if x_data.len() != y_data.len() {
return Err(LetoError::InvalidInput(
"x_data and y_data must have equal length".into(),
));
}
validate_nodes(&x_data, 2)?;
let weights = barycentric_weights(&x_data);
Ok(Self {
x_data,
y_data,
weights,
})
}
}
fn barycentric_weights<T: RealField>(x: &[T]) -> Vec<T> {
let n = x.len();
let mut w = vec![T::ONE; n];
for i in 0..n {
for j in 0..n {
if i != j {
w[i] *= x[i] - x[j];
}
}
w[i] = T::ONE / w[i];
}
w
}
impl<T: RealField> Interpolation1D<T> for LagrangeInterpolation<T> {
fn interpolate(&self, x: T) -> Result<T> {
let n = self.x_data.len();
check_bounds(x, self.x_data[0], self.x_data[n - 1])?;
for (i, &xi) in self.x_data.iter().enumerate() {
if (x - xi).abs() < T::EPSILON {
return Ok(self.y_data[i]);
}
}
let mut num = <T as NumericElement>::ZERO;
let mut den = <T as NumericElement>::ZERO;
for i in 0..n {
let diff = x - self.x_data[i];
let term = self.weights[i] / diff;
num += term * self.y_data[i];
den += term;
}
if den == <T as NumericElement>::ZERO {
return Err(LetoError::NumericalBreakdown(
"Lagrange denominator is zero".into(),
));
}
Ok(num / den)
}
fn bounds(&self) -> (T, T) {
let n = self.x_data.len();
(self.x_data[0], self.x_data[n - 1])
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn quadratic_exact() {
let xs = vec![0.0, 1.0, 2.0];
let ys = vec![1.0, 3.0, 7.0]; let interp = LagrangeInterpolation::new(xs, ys).unwrap();
assert!((interp.interpolate(0.5).unwrap() - 1.75).abs() < 1e-10);
}
#[test]
fn nodes_exact() {
let xs = vec![0.0, 1.0, 2.0];
let ys = vec![1.0, 3.0, 7.0];
let interp = LagrangeInterpolation::new(xs.clone(), ys.clone()).unwrap();
for (&xi, &yi) in xs.iter().zip(ys.iter()) {
assert!((interp.interpolate(xi).unwrap() - yi).abs() < 1e-10);
}
}
}