From 857b9974b7a8e89016357cc91ca4a37561ead7be Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Juan=20Manuel=20Tom=C3=A1s?= Date: Mon, 11 Jan 2021 11:29:19 -0300 Subject: Refactor Poly --- src/lerp.rs | 8 +-- src/main.rs | 16 +++-- src/poly.rs | 203 ++++++++++++++++++++---------------------------------------- 3 files changed, 78 insertions(+), 149 deletions(-) diff --git a/src/lerp.rs b/src/lerp.rs index 8a33e8f..96506df 100644 --- a/src/lerp.rs +++ b/src/lerp.rs @@ -1,5 +1,5 @@ use crate::number::Number; -use crate::poly::{self, Poly}; +use crate::poly::Poly; pub enum Lerp { Node(Box, Box), @@ -23,12 +23,12 @@ impl Lerp { pub fn lp(l: Box) -> Poly { match *l { - Lerp::Leaf(a, b) => vec![a, b - a], + Lerp::Leaf(a, b) => Poly(vec![a, b - a]), Lerp::Node(a, b) => { let a = lp(a); let b = lp(b); - let c = poly::sub(&b, &a); - poly::skewed_sum(a, c) + let c = &b - &a; + &a + &(&c * &Poly(vec![0.0, 1.0])) } } } diff --git a/src/main.rs b/src/main.rs index e5e4112..bd7e1a2 100644 --- a/src/main.rs +++ b/src/main.rs @@ -14,12 +14,10 @@ use sdl2::keyboard::Keycode; use sdl2::rect::Rect; fn main() { - //let a = Lerp::new(vec![2.0, -2.0, 2.0]); - //let b = Lerp::new(vec![-1.0, 1.0, 2.0]); - //let pa = lerp::lp(a); - //let pb = lerp::lp(b); - let pa = vec![1.0, 5.0, -2.0]; - let pb = vec![5.0, -4.0, 0.0]; + let a = Lerp::new(vec![2.0, -2.0, 2.0]); + let b = Lerp::new(vec![-1.0, 1.0, 2.0]); + let pa = lerp::lp(a); + let pb = lerp::lp(b); let p = poly::gcd(&pa, &pb); let sdl_context = sdl2::init().unwrap(); @@ -49,9 +47,9 @@ fn main() { let s = -600.0 / 10.0; let k = 600.0 / 2.0; for t in -800..800 { - let x = k + s * poly::eval_poly(&pa, t as Number / 100.0); - let y = k + s * poly::eval_poly(&pb, t as Number / 100.0); - let z = k + s * poly::eval_poly(&p, t as Number / 100.0); + let x = k + s * pa.eval(t as Number / 100.0); + let y = k + s * pb.eval(t as Number / 100.0); + let z = k + s * p.eval(t as Number / 100.0); canvas.set_draw_color(Color::RGB(180, 20, 20)); canvas.fill_rect(Rect::new(400 + t, x as i32, 5, 5)).unwrap(); canvas.set_draw_color(Color::RGB(20, 180, 20)); diff --git a/src/poly.rs b/src/poly.rs index f6ee63c..9c95796 100644 --- a/src/poly.rs +++ b/src/poly.rs @@ -5,12 +5,12 @@ use iter::Iter; use std::cmp; use std::cmp::Ordering; use std::ops::{Add, Sub, Mul, Rem}; -use std::iter::{Sum, Zip, Take}; +use std::iter::{Zip, Take}; #[derive(PartialEq, Debug)] -pub struct P(Vec); +pub struct Poly(pub Vec); -impl P { +impl Poly { fn degree(&self) -> usize { let mut i = self.0.len() - 1; while self.0[i] == 0.0 && i > 0 { @@ -29,28 +29,45 @@ impl P { let b = other.iter().take(deg); a.zip(b) } + + 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); + } + r + } + + fn is_zero(&self) -> bool { + for i in 0..self.0.len() { + if self.0[i] != 0.0 { + return false + } + } + true + } } -impl Add for &P { - type Output = P; +impl Add for &Poly { + type Output = Poly; - fn add(self, other: Self) -> P { - P(self.zip(other).map(|(x, y)| {x + y}).collect()) + fn add(self, other: Self) -> Poly { + Poly(self.zip(other).map(|(x, y)| {x + y}).collect()) } } -impl Sub for &P { - type Output = P; +impl Sub for &Poly { + type Output = Poly; - fn sub(self, other: Self) -> P { - P(self.zip(other).map(|(x, y)| {x - y}).collect()) + fn sub(self, other: Self) -> Poly { + Poly(self.zip(other).map(|(x, y)| {x - y}).collect()) } } -impl Mul for &P { - type Output = P; +impl Mul for &Poly { + type Output = Poly; - fn mul(self, other: Self) -> P { + fn mul(self, other: Self) -> Poly { let mut r = Vec::new(); for i in 0..other.degree() + 1 { let mut prefix = vec![0.0; i]; @@ -59,110 +76,36 @@ impl Mul for &P { .map(|x| {x * other.0[i]}) .collect(); prefix.append(&mut suffix); - r.push(P(prefix)); + r.push(Poly(prefix)); } - r.iter().fold(P(vec![0.0]), |acc, x| &acc + x) + r.iter().fold(Poly(vec![0.0]), |acc, x| &acc + x) } } -impl Rem for &P { - type Output = P; +impl Rem for &Poly { + type Output = Poly; - fn rem(self, other: Self) -> P { + fn rem(self, other: Self) -> Poly { let ad = self.degree(); let bd = other.degree(); let an = self.0[ad]; let bn = other.0[bd]; match ad.cmp(&bd) { - Ordering::Equal => self - &(other * &P(vec![an / bn])), + Ordering::Equal => self - &(other * &Poly(vec![an / bn])), Ordering::Greater => { - let mut qv = vec![0.0; ad]; + let mut qv = vec![0.0; ad + 1]; qv[ad - bd] = an / bn; - self - &(other * &P(qv)) + self - &(other * &Poly(qv)) }, - Ordering::Less => P(vec![0.0]) - } - } -} - -//****************************REFACTORING************************************ - -pub type Poly = Vec; - -pub fn eval_poly(p: &Poly, t: Number) -> Number { - let mut r = 0.0; - for i in 0..p.len() { - r += p[i] * t.powi(i as i32); - } - r -} - -pub fn sub(a: &Poly, b: &Poly) -> Poly { - let mut r = a.clone(); - for i in 0..r.len() { - r[i] -= b[i]; - } - r -} - -pub fn skewed_sum(a: Poly, b: Poly) -> Poly { - let mut r = a.clone(); - for i in 0..r.len() - 1 { - r[i + 1] += b[i]; - } - r.push(b[b.len() - 1]); - r -} - -fn is_zero(p: &Poly) -> bool { - for i in 0..p.len() { - if p[i] != 0.0 { - return false - } - } - true -} - -fn degree(p: &Poly) -> usize { - let mut i = p.len() - 1; - while p[i] == 0.0 && i > 0 { - i -= 1; - } - i -} - -fn prod(p: &Poly, n: Number) -> Poly { - let mut r = p.clone(); - for i in 0..r.len() { - r[i] *= n; - } - r -} - -fn shift(p: &Poly, amount: usize) -> Poly { - let mut r = vec![0.0; p.len()]; - for i in 0..p.len() { - if i + amount < r.len() { - r[i + amount] = p[i]; + Ordering::Less => Poly(vec![0.0]) } } - r -} - -fn rem(a: &Poly, b: &Poly) -> Poly { - let an = a[degree(a)]; - let bn = b[degree(b)]; - match degree(a).cmp(°ree(b)) { - Ordering::Equal => sub(a, &prod(b, an / bn)), - Ordering::Greater => sub(a, &prod(&shift(b, (degree(a) - degree(b)) as usize), an / bn)), - Ordering::Less => vec![0.0; b.len()] - } } pub fn gcd(a: &Poly, b: &Poly) -> Poly { - let c = rem(a, b); - if is_zero(&c) { - b.clone() + let c = a % b; + if c.is_zero() { + Poly(b.0.clone()) } else { gcd(b, &c) } @@ -174,81 +117,69 @@ mod tests { #[test] fn mul_test() { - let a = P(vec![1.0, 2.0, 3.0]); - let b = P(vec![1.0, 2.0]); - assert_eq!(&a * &b, P(vec![1.0, 4.0, 7.0, 6.0])); + 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])); } #[test] fn add_test() { - let a = P(vec![1.0]); - let b = P(vec![0.0, 0.0, 0.0, 1.0]); - assert_eq!(&a + &b, P(vec![1.0, 0.0, 0.0, 1.0])); + 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])); } #[test] fn sub_test() { - let a = P(vec![1.0, 2.0, 3.0]); - let b = P(vec![1.0]); - assert_eq!(&a - &b, P(vec![0.0, 2.0, 3.0])); + 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])); } #[test] fn poly_is_zero() { - let p = vec![0.0; 5]; - assert_eq!(is_zero(&p), true); + let p = Poly(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!(is_zero(&p), false); + assert_eq!(Poly(p).is_zero(), false); } #[test] fn degree_is_five() { let mut p = vec![0.0; 6]; p[5] = 2.0; - assert_eq!(degree(&p), 5); + assert_eq!(Poly(p).degree(), 5); } #[test] fn degree_is_zero() { - let p = vec![0.0; 6]; - assert_eq!(degree(&p), 0); - } - - #[test] - fn prod_test() { - let p = vec![1.0, 2.0, 3.0, 4.0, 5.0]; - assert_eq!(prod(&p, 2.0), vec![2.0, 4.0, 6.0, 8.0, 10.0]); - } - - #[test] - fn shift_test() { - let p = vec![1.0, 2.0, 3.0, 0.0, 0.0]; - assert_eq!(shift(&p, 2), vec![0.0, 0.0, 1.0, 2.0, 3.0]); + let p = Poly(vec![0.0; 6]); + assert_eq!(p.degree(), 0); } #[test] fn rem_equal() { - let a = P(vec![6.0, 7.0, 1.0]); - let b = P(vec![-6.0, -5.0, 1.0]); - assert_eq!(&a % &b, P(vec![12.0, 12.0, 0.0])); + 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![12.0, 12.0, 0.0])); } #[test] fn rem_greater() { - let a = P(vec![-6.0, -5.0, 1.0]); - let b = P(vec![12.0, 12.0, 0.0]); - assert_eq!(&a % &b, P(vec![-6.0, -6.0, 0.0])); + let a = Poly(vec![-6.0, -5.0, 1.0]); + let b = Poly(vec![12.0, 12.0]); + assert_eq!(&a % &b, Poly(vec![-6.0, -6.0, 0.0])); } #[test] fn gcd_test() { - let a = vec![6.0, 7.0, 1.0]; - let b = vec![-6.0, -5.0, 1.0]; - assert_eq!(gcd(&a, &b), vec![-6.0, -6.0, 0.0]); + let a = Poly(vec![6.0, 7.0, 1.0]); + let b = Poly(vec![-6.0, -5.0, 1.0]); + assert_eq!(gcd(&a, &b), Poly(vec![-6.0, -6.0, 0.0])); } } -- cgit v1.2.3