use std::cmp::Ordering;

pub type Number = f32;

pub type Poly = Vec<Number>;

#[derive(Debug)]
pub enum Lerp {
    Node(Box<Lerp>, Box<Lerp>),
    Leaf(Number, Number)
}

impl Lerp {
    pub fn new(v: Vec<Number>) -> Box<Lerp> {
        Lerp::new_s(&v[..])
    }

    fn new_s(v: &[Number]) -> Box<Lerp> {
        match v.len() {
            0 => Box::new(Lerp::Leaf(0.0, 0.0)),
            1 => Box::new(Lerp::Leaf(v[0], 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()])))
        }
    }
}

pub fn lp(l: Box<Lerp>) -> Poly {
    match *l {
        Lerp::Leaf(a, b) => vec![a, b - a],
        Lerp::Node(a, b) => {
            let a = lp(a);
            let b = lp(b);
            let c = sub(&b, &a);
            skewed_sum(a, c)
        }
    }
}

fn sub(a: &Poly, b: &Poly) -> Poly {
    let mut r = a.clone();
    for i in 0..r.len() {
        r[i] -= b[i];
    }
    r
}

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];
        }
    }
    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()
    } else {
        gcd(b, &c)
    }
}

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

    #[test]
    fn poly_is_zero() {
        let p = vec![0.0; 5];
        assert_eq!(is_zero(&p), true);
    }

    #[test]
    fn poly_is_not_zero() {
        let mut p = vec![0.0; 5];
        p[2] = 8.0;
        assert_eq!(is_zero(&p), false);
    }

    #[test]
    fn degree_is_five() {
        let mut p = vec![0.0; 6];
        p[5] = 2.0;
        assert_eq!(degree(&p), 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]);
    }

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

    #[test]
    fn rem_greater() {
        let a = vec![-6.0, -5.0, 1.0];
        let b = vec![12.0, 12.0, 0.0];
        assert_eq!(rem(&a, &b), 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]);
    }
}