diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/lerp.rs | 4 | ||||
| -rw-r--r-- | src/poly.rs | 109 |
2 files changed, 61 insertions, 52 deletions
diff --git a/src/lerp.rs b/src/lerp.rs index 96506df..2ea444e 100644 --- a/src/lerp.rs +++ b/src/lerp.rs @@ -23,12 +23,12 @@ impl Lerp { pub fn lp(l: Box<Lerp>) -> Poly { match *l { - Lerp::Leaf(a, b) => Poly(vec![a, b - a]), + Lerp::Leaf(a, b) => Poly::new(vec![a, b - a]), Lerp::Node(a, b) => { let a = lp(a); let b = lp(b); let c = &b - &a; - &a + &(&c * &Poly(vec![0.0, 1.0])) + &a + &(&c * &Poly::new(vec![0.0, 1.0])) } } } diff --git a/src/poly.rs b/src/poly.rs index 60eb707..90b7b78 100644 --- a/src/poly.rs +++ b/src/poly.rs @@ -5,42 +5,53 @@ use iter::Iter; use std::ops::{Add, Sub, Mul, Div}; #[derive(PartialEq, Debug, Clone)] -pub struct Poly(pub Vec<Number>); +pub struct Poly { + data: Vec<Number>, + degree: usize +} impl Poly { + pub fn new(data: Vec<Number>) -> Poly { + let mut i = data.len() - 1; + while data[i] == 0.0 && i > 0 { + i -= 1; + } + Poly { data, degree : i } + } + fn mono(degree: usize, coefficient: Number) -> Poly { - let mut p = vec![0.0; degree + 1]; - p[degree] = coefficient; - Poly(p) + if coefficient != 0.0 { + let mut p = vec![0.0; degree + 1]; + p[degree] = coefficient; + Poly::new(p) + } else { + Poly::new(vec![0.0]) + } } fn degree(&self) -> usize { - let mut i = self.0.len() - 1; - while self.0[i] == 0.0 && i > 0 { - i -= 1; - } - i + self.degree } fn lc(&self) -> Number { - self.0[self.degree()] + self.data[self.degree()] } fn iter(&self) -> Iter { - Iter::new(self.0.clone(), self.degree()) + Iter::new(self.data.clone(), self.degree()) } pub fn eval(&self, n: Number) -> Number { let mut r = 0.0; - for i in 0..self.0.len() { - r += self.0[i] * n.powi(i as i32); + for i in 0..self.data.len() { + r += self.data[i] * n.powi(i as i32); } r } fn is_zero(&self) -> bool { - for i in 0..self.0.len() { - if self.0[i] != 0.0 { + for i in 0..self.data.len() { + if self.data[i] != 0.0 { return false } } @@ -52,7 +63,7 @@ impl Add for &Poly { type Output = Poly; fn add(self, other: Self) -> Poly { - Poly(self.iter().zip(other.iter()).map(|(x, y)| {x + y}).collect()) + Poly::new(self.iter().zip(other.iter()).map(|(x, y)| {x + y}).collect()) } } @@ -60,7 +71,7 @@ impl Sub for &Poly { type Output = Poly; fn sub(self, other: Self) -> Poly { - Poly(self.iter().zip(other.iter()).map(|(x, y)| {x - y}).collect()) + Poly::new(self.iter().zip(other.iter()).map(|(x, y)| {x - y}).collect()) } } @@ -73,12 +84,12 @@ impl Mul for &Poly { let mut prefix = vec![0.0; i]; let mut suffix: Vec<Number> = self.iter() .take(self.degree() + 1) - .map(|x| {x * other.0[i]}) + .map(|x| {x * other.data[i]}) .collect(); prefix.append(&mut suffix); - r.push(Poly(prefix)); + r.push(Poly::new(prefix)); } - r.iter().fold(Poly(vec![0.0]), |acc, x| &acc + x) + r.iter().fold(Poly::new(vec![0.0]), |acc, x| &acc + x) } } @@ -86,7 +97,7 @@ impl Div for &Poly { type Output = (Poly, Poly); fn div(self, divisor: Self) -> (Poly, Poly) { - let mut q = Poly(vec![0.0]); + let mut q = Poly::new(vec![0.0]); let mut r = self.clone(); while !r.is_zero() && r.degree() >= divisor.degree() { let s = Poly::mono(r.degree() - divisor.degree(), r.lc() / divisor.lc()); @@ -112,76 +123,74 @@ mod tests { #[test] fn div_equal() { - let a = Poly(vec![6.0, 7.0, 1.0]); - let b = Poly(vec![-6.0, -5.0, 1.0]); - assert_eq!(&a / &b, (Poly(vec![1.0]), Poly(vec![12.0, 12.0, 0.0]))); + let a = Poly::new(vec![6.0, 7.0, 1.0]); + let b = Poly::new(vec![-6.0, -5.0, 1.0]); + assert_eq!(&a / &b, (Poly::new(vec![1.0]), Poly::new(vec![12.0, 12.0, 0.0]))); } #[test] fn div_greater() { - let a = Poly(vec![-6.0, -5.0, 1.0]); - let b = Poly(vec![12.0, 12.0]); - assert_eq!(&a / &b, (Poly(vec![-0.5, 1.0/12.0]), Poly(vec![0.0, 0.0]))); + let a = Poly::new(vec![-6.0, -5.0, 1.0]); + let b = Poly::new(vec![12.0, 12.0]); + assert_eq!(&a / &b, (Poly::new(vec![-0.5, 1.0/12.0]), Poly::new(vec![0.0, 0.0]))); } #[test] fn div_less() { - let a = Poly(vec![12.0, 12.0]); - let b = Poly(vec![-6.0, -5.0, 1.0]); - assert_eq!(&a / &b, (Poly(vec![0.0]), a)); + let a = Poly::new(vec![12.0, 12.0]); + let b = Poly::new(vec![-6.0, -5.0, 1.0]); + assert_eq!(&a / &b, (Poly::new(vec![0.0]), a)); } #[test] fn mul_test() { - let a = Poly(vec![1.0, 2.0, 3.0]); - let b = Poly(vec![1.0, 2.0]); - assert_eq!(&a * &b, Poly(vec![1.0, 4.0, 7.0, 6.0])); + let a = Poly::new(vec![1.0, 2.0, 3.0]); + let b = Poly::new(vec![1.0, 2.0]); + assert_eq!(&a * &b, Poly::new(vec![1.0, 4.0, 7.0, 6.0])); } #[test] fn add_test() { - let a = Poly(vec![1.0]); - let b = Poly(vec![0.0, 0.0, 0.0, 1.0]); - assert_eq!(&a + &b, Poly(vec![1.0, 0.0, 0.0, 1.0])); + let a = Poly::new(vec![1.0]); + let b = Poly::new(vec![0.0, 0.0, 0.0, 1.0]); + assert_eq!(&a + &b, Poly::new(vec![1.0, 0.0, 0.0, 1.0])); } #[test] fn sub_test() { - let a = Poly(vec![1.0, 2.0, 3.0]); - let b = Poly(vec![1.0, 1.0, 1.0]); - assert_eq!(&a - &b, Poly(vec![0.0, 1.0, 2.0])); + let a = Poly::new(vec![1.0, 2.0, 3.0]); + let b = Poly::new(vec![1.0, 1.0, 1.0]); + assert_eq!(&a - &b, Poly::new(vec![0.0, 1.0, 2.0])); } #[test] fn poly_is_zero() { - let p = Poly(vec![0.0; 5]); + let p = Poly::new(vec![0.0; 5]); assert_eq!(p.is_zero(), true); } #[test] fn poly_is_not_zero() { - let mut p = vec![0.0; 5]; - p[2] = 8.0; - assert_eq!(Poly(p).is_zero(), false); + let p = Poly::mono(5, 8.0); + assert_eq!(p.is_zero(), false); } #[test] fn degree_is_five() { - let mut p = vec![0.0; 6]; - p[5] = 2.0; - assert_eq!(Poly(p).degree(), 5); + let p = Poly::mono(5, 2.0); + assert_eq!(p.degree(), 5); } #[test] fn degree_is_zero() { - let p = Poly(vec![0.0; 6]); + let p = Poly::new(vec![0.0; 6]); assert_eq!(p.degree(), 0); } #[test] fn gcd_test() { - let a = Poly(vec![2.0, -8.0, 8.0]); - let b = Poly(vec![-1.0, 4.0, -1.0]); - assert_eq!(gcd(&a, &b), Poly(vec![-0.0625, 0.0])); + let a = Poly::new(vec![2.0, -8.0, 8.0]); + let b = Poly::new(vec![-1.0, 4.0, -1.0]); + assert_eq!(gcd(&a, &b), Poly::new(vec![-0.0625, 0.0])); } } |