summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJuan Manuel Tomás <jtomas1815@gmail.com>2021-01-30 16:30:43 -0300
committerJuan Manuel Tomás <jtomas1815@gmail.com>2021-01-30 16:30:43 -0300
commitf7f8755215f2701698e173ad753f282231655bdd (patch)
tree68879c722ea0098c0a708a6de38475cb54bb4241
parent4998f5936dc7da36aba0cd018de2a1a6127dda08 (diff)
downloadbezier-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.rs81
-rw-r--r--src/lib.rs4
-rw-r--r--src/main.rs21
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))
+ ))
+ ))
+ );
+ }
+}
diff --git a/src/lib.rs b/src/lib.rs
index 6f26672..d6a1374 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -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);
- },
+ }
_ => {}
}
}