Optimize lerp creation

Now it uses Rc instead of Box, reducing the space and time complexity
from O(2^n) to O(n^2).

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);
-                },
+                }
                 _ => {}
             }
         }