mod iter;

use crate::number::Number;
use iter::Iter;
use std::ops::{Add, Sub, Mul, Div};

#[derive(PartialEq, Debug, Clone)]
pub struct Poly(pub Vec<Number>);

impl Poly {
    fn mono(degree: usize, coefficient: Number) -> Poly {
        let mut p = vec![0.0; degree + 1];
        p[degree] = coefficient;
        Poly(p)
    }

    fn degree(&self) -> usize {
        let mut i = self.0.len() - 1;
        while self.0[i] == 0.0 && i > 0 {
            i -= 1;
        }
        i
    }

    fn lc(&self) -> Number {
        self.0[self.degree()]
    }

    fn iter(&self) -> Iter {
        Iter::new(self.0.clone(), self.degree())
    }

    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 &Poly {
    type Output = Poly;

    fn add(self, other: Self) -> Poly {
        Poly(self.iter().zip(other.iter()).map(|(x, y)| {x + y}).collect())
    }
}

impl Sub for &Poly {
    type Output = Poly;

    fn sub(self, other: Self) -> Poly {
        Poly(self.iter().zip(other.iter()).map(|(x, y)| {x - y}).collect())
    }
}

impl Mul for &Poly {
    type Output = Poly;

    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];
            let mut suffix: Vec<Number> = self.iter()
                .take(self.degree() + 1)
                .map(|x| {x * other.0[i]})
                .collect();
            prefix.append(&mut suffix);
            r.push(Poly(prefix));
        }
        r.iter().fold(Poly(vec![0.0]), |acc, x| &acc + x)
    }
}

impl Div for &Poly {
    type Output = (Poly, Poly);

    fn div(self, divisor: Self) -> (Poly, Poly) {
        let mut q = Poly(vec![0.0]);
        let mut r = self.clone();
        while !r.is_zero() && r.degree() >= divisor.degree() {
            let s = Poly::mono(r.degree() - divisor.degree(), r.lc() / divisor.lc());
            q = &q + &s;
            r = &r - &(&s * divisor);
        }
        (q, r)
    }
}

pub fn gcd(a: &Poly, b: &Poly) -> Poly {
    let (_, c) = a / b;
    if c.is_zero() {
        b.clone()
    } else {
        gcd(b, &c)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn div_equal() {
        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![1.0]), Poly(vec![12.0, 12.0, 0.0])));
    }

    #[test]
    fn div_greater() {
        let a = Poly(vec![-6.0, -5.0, 1.0]);
        let b = Poly(vec![12.0, 12.0]);
        assert_eq!(&a / &b, (Poly(vec![-0.5, 1.0/12.0]), Poly(vec![0.0, 0.0])));
    }

    #[test]
    fn div_less() {
        let a = Poly(vec![12.0, 12.0]);
        let b = Poly(vec![-6.0, -5.0, 1.0]);
        assert_eq!(&a / &b, (Poly(vec![0.0]), a));
    }

    #[test]
    fn mul_test() {
        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 = 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 = 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 = 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!(Poly(p).is_zero(), false);
    }

    #[test]
    fn degree_is_five() {
        let mut p = vec![0.0; 6];
        p[5] = 2.0;
        assert_eq!(Poly(p).degree(), 5);
    }

    #[test]
    fn degree_is_zero() {
        let p = Poly(vec![0.0; 6]);
        assert_eq!(p.degree(), 0);
    }

    #[test]
    fn gcd_test() {
        let a = Poly(vec![2.0, -8.0, 8.0]);
        let b = Poly(vec![-1.0, 4.0, -1.0]);
        assert_eq!(gcd(&a, &b), Poly(vec![-0.0625, 0.0]));
    }
}