From 7fa34698ba8ee80227fa0b8eaab7a7382a5cf465 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Juan=20Manuel=20Tom=C3=A1s?= Date: Sun, 10 Jan 2021 19:54:34 -0300 Subject: Separate project into modules --- src/lerp.rs | 33 ++++++++++++ src/lib.rs | 173 ------------------------------------------------------------ src/main.rs | 32 +++++------ src/poly.rs | 148 +++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 194 insertions(+), 192 deletions(-) create mode 100644 src/lerp.rs delete mode 100644 src/lib.rs create mode 100644 src/poly.rs (limited to 'src') diff --git a/src/lerp.rs b/src/lerp.rs new file mode 100644 index 0000000..7c4994c --- /dev/null +++ b/src/lerp.rs @@ -0,0 +1,33 @@ +use crate::poly::{self, Number, Poly}; + +pub enum Lerp { + Node(Box, Box), + Leaf(Number, Number) +} + +impl Lerp { + pub fn new(v: Vec) -> Box { + Lerp::new_s(&v[..]) + } + + fn new_s(v: &[Number]) -> Box { + match v.len() { + 0 => Box::new(Lerp::Leaf(0.0, 0.0)), + 1 => Box::new(Lerp::Leaf(v[0], v[0])), + 2 => Box::new(Lerp::Leaf(v[0], v[1])), + _ => Box::new(Lerp::Node(Lerp::new_s(&v[0..v.len() - 1]), Lerp::new_s(&v[1..v.len()]))) + } + } +} + +pub fn lp(l: Box) -> Poly { + match *l { + Lerp::Leaf(a, b) => 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) + } + } +} diff --git a/src/lib.rs b/src/lib.rs deleted file mode 100644 index c70a40f..0000000 --- a/src/lib.rs +++ /dev/null @@ -1,173 +0,0 @@ -use std::cmp::Ordering; - -pub type Number = f32; - -pub type Poly = Vec; - -#[derive(Debug)] -pub enum Lerp { - Node(Box, Box), - Leaf(Number, Number) -} - -impl Lerp { - pub fn new(v: Vec) -> Box { - Lerp::new_s(&v[..]) - } - - fn new_s(v: &[Number]) -> Box { - match v.len() { - 0 => Box::new(Lerp::Leaf(0.0, 0.0)), - 1 => Box::new(Lerp::Leaf(v[0], v[0])), - 2 => Box::new(Lerp::Leaf(v[0], v[1])), - _ => Box::new(Lerp::Node(Lerp::new_s(&v[0..v.len() - 1]), Lerp::new_s(&v[1..v.len()]))) - } - } -} - -pub fn lp(l: Box) -> Poly { - match *l { - Lerp::Leaf(a, b) => vec![a, b - a], - Lerp::Node(a, b) => { - let a = lp(a); - let b = lp(b); - let c = sub(&b, &a); - skewed_sum(a, c) - } - } -} - -fn sub(a: &Poly, b: &Poly) -> Poly { - let mut r = a.clone(); - for i in 0..r.len() { - r[i] -= b[i]; - } - r -} - -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]; - } - } - 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() - } else { - gcd(b, &c) - } -} - -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn poly_is_zero() { - let p = vec![0.0; 5]; - assert_eq!(is_zero(&p), true); - } - - #[test] - fn poly_is_not_zero() { - let mut p = vec![0.0; 5]; - p[2] = 8.0; - assert_eq!(is_zero(&p), false); - } - - #[test] - fn degree_is_five() { - let mut p = vec![0.0; 6]; - p[5] = 2.0; - assert_eq!(degree(&p), 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]); - } - - #[test] - fn rem_equal() { - let a = vec![6.0, 7.0, 1.0]; - let b = vec![-6.0, -5.0, 1.0]; - assert_eq!(rem(&a, &b), vec![12.0, 12.0, 0.0]); - } - - #[test] - fn rem_greater() { - let a = vec![-6.0, -5.0, 1.0]; - let b = vec![12.0, 12.0, 0.0]; - assert_eq!(rem(&a, &b), 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]); - } -} diff --git a/src/main.rs b/src/main.rs index 8831976..8c23d3e 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,28 +1,22 @@ -use poly::Poly; -use poly::Number; -use poly::Lerp; +mod poly; +mod lerp; -use sdl2::pixels::Color; -use sdl2::event::Event; -use sdl2::keyboard::Keycode; -use sdl2::rect::Rect; +use crate::poly::Number; +use crate::lerp::Lerp; use std::thread; use std::time::Duration; -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 -} +use sdl2::pixels::Color; +use sdl2::event::Event; +use sdl2::keyboard::Keycode; +use sdl2::rect::Rect; fn main() { let a = Lerp::new(vec![100.0, 200.0, 300.0, 500.0]); let b = Lerp::new(vec![400.0, 140.0, 500.0, 300.0]); - let pa = poly::lp(a); - let pb = poly::lp(b); + let pa = lerp::lp(a); + let pb = lerp::lp(b); let p = poly::gcd(&pa, &pb); let sdl_context = sdl2::init().unwrap(); @@ -50,9 +44,9 @@ fn main() { } for t in 0..800 { - let x = eval_poly(&pa, t as Number / 800.0); - let y = eval_poly(&pb, t as Number / 800.0); - let z = eval_poly(&p, t as Number / 800.0); + let x = poly::eval_poly(&pa, t as Number / 800.0); + let y = poly::eval_poly(&pb, t as Number / 800.0); + let z = poly::eval_poly(&p, t as Number / 800.0); canvas.set_draw_color(Color::RGB(180, 20, 20)); canvas.fill_rect(Rect::new(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 new file mode 100644 index 0000000..2128d38 --- /dev/null +++ b/src/poly.rs @@ -0,0 +1,148 @@ +use std::cmp::Ordering; + +pub type Number = f32; + +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]; + } + } + 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() + } else { + gcd(b, &c) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn poly_is_zero() { + let p = vec![0.0; 5]; + assert_eq!(is_zero(&p), true); + } + + #[test] + fn poly_is_not_zero() { + let mut p = vec![0.0; 5]; + p[2] = 8.0; + assert_eq!(is_zero(&p), false); + } + + #[test] + fn degree_is_five() { + let mut p = vec![0.0; 6]; + p[5] = 2.0; + assert_eq!(degree(&p), 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]); + } + + #[test] + fn rem_equal() { + let a = vec![6.0, 7.0, 1.0]; + let b = vec![-6.0, -5.0, 1.0]; + assert_eq!(rem(&a, &b), vec![12.0, 12.0, 0.0]); + } + + #[test] + fn rem_greater() { + let a = vec![-6.0, -5.0, 1.0]; + let b = vec![12.0, 12.0, 0.0]; + assert_eq!(rem(&a, &b), 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]); + } +} -- cgit v1.2.3