Optimize lerp creation

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

1 files changed, 65 insertions, 16 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))
+                ))
+            ))
+        );
+    }
+}