diff options
author | Juan Manuel Tomás <jtomas1815@gmail.com> | 2021-01-30 16:30:43 -0300 |
---|---|---|
committer | Juan Manuel Tomás <jtomas1815@gmail.com> | 2021-01-30 16:30:43 -0300 |
commit | f7f8755215f2701698e173ad753f282231655bdd (patch) | |
tree | 68879c722ea0098c0a708a6de38475cb54bb4241 | |
parent | 4998f5936dc7da36aba0cd018de2a1a6127dda08 (diff) | |
download | bezier-f7f8755215f2701698e173ad753f282231655bdd.tar.gz bezier-f7f8755215f2701698e173ad753f282231655bdd.zip |
Optimize lerp creation
Now it uses Rc instead of Box, reducing the space and time complexity
from O(2^n) to O(n^2).
-rw-r--r-- | src/lerp.rs | 81 | ||||
-rw-r--r-- | src/lib.rs | 4 | ||||
-rw-r--r-- | src/main.rs | 21 |
3 files changed, 79 insertions, 27 deletions
diff --git a/src/lerp.rs b/src/lerp.rs index 4c829a1..b5b771d 100644 --- a/src/lerp.rs +++ b/src/lerp.rs @@ -1,32 +1,40 @@ use crate::poly::Poly; +use std::rc::Rc; +#[derive(PartialEq, Debug)] pub enum Lerp { - Node(Box<Lerp>, Box<Lerp>), + Node(Rc<Lerp>, Rc<Lerp>), Leaf(f32, f32), Just(f32), } impl Lerp { - pub fn new(v: &Vec<f32>) -> Box<Lerp> { - Lerp::new_s(&v[..]) - } - - fn new_s(v: &[f32]) -> Box<Lerp> { + pub fn new(v: &Vec<f32>) -> Rc<Lerp> { match v.len() { - 0 => Box::new(Lerp::Just(0.0)), - 1 => Box::new(Lerp::Just(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()]), - )), + 0 => Rc::new(Lerp::Just(0.0)), + 1 => Rc::new(Lerp::Just(v[0])), + 2 => Rc::new(Lerp::Leaf(v[0], v[1])), + _ => { + let mut lv = Vec::new(); + for i in 0..v.len() - 1 { + lv.push(Rc::new(Lerp::Leaf(v[i], v[i + 1]))); + } + while lv.len() > 1 { + let mut nlv = Vec::new(); + for i in 0..lv.len() - 1 { + nlv.push(Rc::new(Lerp::Node(lv[i].clone(), lv[i + 1].clone()))); + } + lv = nlv; + } + lv[0].clone() + } } } - pub fn to_poly(self) -> Poly { + pub fn to_poly(&self) -> Poly { match self { - Lerp::Just(a) => Poly::new(vec![a]), - Lerp::Leaf(a, b) => Poly::new(vec![a, b - a]), + Lerp::Just(a) => Poly::new(vec![*a]), + Lerp::Leaf(a, b) => Poly::new(vec![*a, *b - *a]), Lerp::Node(a, b) => { let a = a.to_poly(); let b = b.to_poly(); @@ -36,3 +44,44 @@ impl Lerp { } } } + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn new2_test() { + let a = Lerp::new(&vec![1.0, 2.0]); + assert_eq!(a, Rc::new(Lerp::Leaf(1.0, 2.0))); + } + + #[test] + fn new3_test() { + let a = Lerp::new(&vec![1.0, 2.0, 3.0]); + assert_eq!( + a, + Rc::new(Lerp::Node( + Rc::new(Lerp::Leaf(1.0, 2.0)), + Rc::new(Lerp::Leaf(2.0, 3.0)) + )) + ); + } + + #[test] + fn new4_test() { + let a = Lerp::new(&vec![1.0, 2.0, 3.0, 4.0]); + assert_eq!( + a, + Rc::new(Lerp::Node( + Rc::new(Lerp::Node( + Rc::new(Lerp::Leaf(1.0, 2.0)), + Rc::new(Lerp::Leaf(2.0, 3.0)) + )), + Rc::new(Lerp::Node( + Rc::new(Lerp::Leaf(2.0, 3.0)), + Rc::new(Lerp::Leaf(3.0, 4.0)) + )) + )) + ); + } +} @@ -11,7 +11,7 @@ pub struct Bezier { pub px: Poly, pub py: Poly, pub dpx: Poly, - pub dpy: Poly + pub dpy: Poly, } impl Bezier { @@ -47,7 +47,7 @@ impl Bezier { self.degree -= 1; } - pub fn show_x(&self) -> String{ + pub fn show_x(&self) -> String { let mut s = String::new(); for i in 0..self.degree { s.push_str(&self.vx[i].to_string()); diff --git a/src/main.rs b/src/main.rs index a61478f..25a3ec1 100644 --- a/src/main.rs +++ b/src/main.rs @@ -118,13 +118,13 @@ fn compile_bezier_shader(c: &Bezier) -> GLuint { FragColor = vec4(r, c, 0.0, 1.0); }} ", - s = c.degree, - vx = c.show_x(), - vy = c.show_y(), - px = &c.px, - py = &c.py, - sx = c.px.degree() + 1, - sy = c.py.degree() + 1, + s = c.degree, + vx = c.show_x(), + vy = c.show_y(), + px = &c.px, + py = &c.py, + sx = c.px.degree() + 1, + sy = c.py.degree() + 1, dpx = &c.dpx, dpy = &c.dpy, dsx = c.dpx.degree() + 1, @@ -182,7 +182,10 @@ fn main() { gl::Viewport(0, 0, window_w as i32, window_h as i32); } - let vertices: [f32; 18] = [1.0, 1.0, 0.0, 1.0, -1.0, 0.0, -1.0, 1.0, 0.0, 1.0, -1.0, 0.0, -1.0, -1.0, 0.0, -1.0, 1.0, 0.0]; + let vertices: [f32; 18] = [ + 1.0, 1.0, 0.0, 1.0, -1.0, 0.0, -1.0, 1.0, 0.0, 1.0, -1.0, 0.0, -1.0, -1.0, 0.0, -1.0, 1.0, + 0.0, + ]; let mut vbo: GLuint = 0; let mut vao: GLuint = 0; @@ -225,7 +228,7 @@ fn main() { } => { curve.push(x, window_h as i32 - y); compile_bezier_shader(&curve); - }, + } _ => {} } } |