Refactor Poly

1 files changed, 67 insertions, 136 deletions

diff --git a/src/poly.rs b/src/poly.rs
index f6ee63c..9c95796 100644
--- a/src/poly.rs
+++ b/src/poly.rs
@@ -5,12 +5,12 @@ use iter::Iter;
 use std::cmp;
 use std::cmp::Ordering;
 use std::ops::{Add, Sub, Mul, Rem};
-use std::iter::{Sum, Zip, Take};
+use std::iter::{Zip, Take};
 
 #[derive(PartialEq, Debug)]
-pub struct P(Vec<Number>);
+pub struct Poly(pub Vec<Number>);
 
-impl P {
+impl Poly {
     fn degree(&self) -> usize {
         let mut i = self.0.len() - 1;
         while self.0[i] == 0.0 && i > 0 {
@@ -29,28 +29,45 @@ impl P {
         let b = other.iter().take(deg);
         a.zip(b)
     }
+
+    pub fn eval(&self, n: Number) -> Number {
+        let mut r = 0.0;
+        for i in 0..self.0.len() {
+            r += self.0[i] * n.powi(i as i32);
+        }
+        r
+    }
+
+    fn is_zero(&self) -> bool {
+        for i in 0..self.0.len() {
+            if self.0[i] != 0.0 {
+                return false
+            }
+        }
+        true
+    }
 }
 
-impl Add for &P {
-    type Output = P;
+impl Add for &Poly {
+    type Output = Poly;
 
-    fn add(self, other: Self) -> P {
-        P(self.zip(other).map(|(x, y)| {x + y}).collect())
+    fn add(self, other: Self) -> Poly {
+        Poly(self.zip(other).map(|(x, y)| {x + y}).collect())
     }
 }
 
-impl Sub for &P {
-    type Output = P;
+impl Sub for &Poly {
+    type Output = Poly;
 
-    fn sub(self, other: Self) -> P {
-        P(self.zip(other).map(|(x, y)| {x - y}).collect())
+    fn sub(self, other: Self) -> Poly {
+        Poly(self.zip(other).map(|(x, y)| {x - y}).collect())
     }
 }
 
-impl Mul for &P {
-    type Output = P;
+impl Mul for &Poly {
+    type Output = Poly;
 
-    fn mul(self, other: Self) -> P {
+    fn mul(self, other: Self) -> Poly {
         let mut r = Vec::new();
         for i in 0..other.degree() + 1 {
             let mut prefix = vec![0.0; i];
@@ -59,110 +76,36 @@ impl Mul for &P {
                 .map(|x| {x * other.0[i]})
                 .collect();
             prefix.append(&mut suffix);
-            r.push(P(prefix));
+            r.push(Poly(prefix));
         }
-        r.iter().fold(P(vec![0.0]), |acc, x| &acc + x)
+        r.iter().fold(Poly(vec![0.0]), |acc, x| &acc + x)
     }
 }
 
-impl Rem for &P {
-    type Output = P;
+impl Rem for &Poly {
+    type Output = Poly;
 
-    fn rem(self, other: Self) -> P {
+    fn rem(self, other: Self) -> Poly {
         let ad = self.degree();
         let bd = other.degree();
         let an = self.0[ad];
         let bn = other.0[bd];
         match ad.cmp(&bd) {
-            Ordering::Equal => self - &(other * &P(vec![an / bn])),
+            Ordering::Equal => self - &(other * &Poly(vec![an / bn])),
             Ordering::Greater => {
-                let mut qv = vec![0.0; ad];
+                let mut qv = vec![0.0; ad + 1];
                 qv[ad - bd] = an / bn;
-                self - &(other * &P(qv))
+                self - &(other * &Poly(qv))
             },
-            Ordering::Less => P(vec![0.0])
-        }
-    }
-}
-
-//****************************REFACTORING************************************
-
-pub type Poly = Vec<Number>;
-
-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];
+            Ordering::Less => Poly(vec![0.0])
         }
     }
-    r
-}
-
-fn rem(a: &Poly, b: &Poly) -> Poly {
-    let an = a[degree(a)];
-    let bn = b[degree(b)];
-    match degree(a).cmp(&degree(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()
+    let c = a % b;
+    if c.is_zero() {
+        Poly(b.0.clone())
     } else {
         gcd(b, &c)
     }
@@ -174,81 +117,69 @@ mod tests {
 
     #[test]
     fn mul_test() {
-        let a = P(vec![1.0, 2.0, 3.0]);
-        let b = P(vec![1.0, 2.0]);
-        assert_eq!(&a * &b, P(vec![1.0, 4.0, 7.0, 6.0]));
+        let a = Poly(vec![1.0, 2.0, 3.0]);
+        let b = Poly(vec![1.0, 2.0]);
+        assert_eq!(&a * &b, Poly(vec![1.0, 4.0, 7.0, 6.0]));
     }
 
     #[test]
     fn add_test() {
-        let a = P(vec![1.0]);
-        let b = P(vec![0.0, 0.0, 0.0, 1.0]);
-        assert_eq!(&a + &b, P(vec![1.0, 0.0, 0.0, 1.0]));
+        let a = Poly(vec![1.0]);
+        let b = Poly(vec![0.0, 0.0, 0.0, 1.0]);
+        assert_eq!(&a + &b, Poly(vec![1.0, 0.0, 0.0, 1.0]));
     }
 
     #[test]
     fn sub_test() {
-        let a = P(vec![1.0, 2.0, 3.0]);
-        let b = P(vec![1.0]);
-        assert_eq!(&a - &b, P(vec![0.0, 2.0, 3.0]));
+        let a = Poly(vec![1.0, 2.0, 3.0]);
+        let b = Poly(vec![1.0, 1.0, 1.0]);
+        assert_eq!(&a - &b, Poly(vec![0.0, 1.0, 2.0]));
     }
 
     #[test]
     fn poly_is_zero() {
-        let p = vec![0.0; 5];
-        assert_eq!(is_zero(&p), true);
+        let p = Poly(vec![0.0; 5]);
+        assert_eq!(p.is_zero(), true);
     }
 
     #[test]
     fn poly_is_not_zero() {
         let mut p = vec![0.0; 5];
         p[2] = 8.0;
-        assert_eq!(is_zero(&p), false);
+        assert_eq!(Poly(p).is_zero(), false);
     }
 
     #[test]
     fn degree_is_five() {
         let mut p = vec![0.0; 6];
         p[5] = 2.0;
-        assert_eq!(degree(&p), 5);
+        assert_eq!(Poly(p).degree(), 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]);
+        let p = Poly(vec![0.0; 6]);
+        assert_eq!(p.degree(), 0);
     }
 
     #[test]
     fn rem_equal() {
-        let a = P(vec![6.0, 7.0, 1.0]);
-        let b = P(vec![-6.0, -5.0, 1.0]);
-        assert_eq!(&a % &b, P(vec![12.0, 12.0, 0.0]));
+        let a = Poly(vec![6.0, 7.0, 1.0]);
+        let b = Poly(vec![-6.0, -5.0, 1.0]);
+        assert_eq!(&a % &b, Poly(vec![12.0, 12.0, 0.0]));
     }
 
     #[test]
     fn rem_greater() {
-        let a = P(vec![-6.0, -5.0, 1.0]);
-        let b = P(vec![12.0, 12.0, 0.0]);
-        assert_eq!(&a % &b, P(vec![-6.0, -6.0, 0.0]));
+        let a = Poly(vec![-6.0, -5.0, 1.0]);
+        let b = Poly(vec![12.0, 12.0]);
+        assert_eq!(&a % &b, Poly(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]);
+        let a = Poly(vec![6.0, 7.0, 1.0]);
+        let b = Poly(vec![-6.0, -5.0, 1.0]);
+        assert_eq!(gcd(&a, &b), Poly(vec![-6.0, -6.0, 0.0]));
     }
 }