for TUT AdC 2018

gcd_in_polynomial.rs

use std::cmp::Ordering;
use std::fmt;
use std::ops::{Add, Div, Mul, Rem, Sub};

#[derive(Debug, Clone, PartialEq)]
struct Polynomial {
    coefficients: Vec<f32>, // ascend order.
}
trait Zero {
    fn get_zero() -> Self;
}

impl Polynomial {
    fn new(arg: &[f32], is_descend: bool) -> Polynomial {
        let mut coef = arg.to_vec();
        if is_descend {
            coef.reverse();
        }
        Polynomial { coefficients: coef }
    }
    fn get_order(&self) -> usize {
        self.coefficients.len() - 1
    }
}

impl fmt::Display for Polynomial {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut poly = self.coefficients.iter().enumerate().collect::<Vec<_>>();
        poly.reverse();
        let poly = poly.iter().collect::<Vec<_>>();

        let max_order = self.get_order();
        let format_item = |(o, c)| {
            if c == 0.0 {
                if o == 0 { "0" } else { "" }.to_string()
            } else {
                let co_str = if c == 1.0 {
                    "".to_string()
                } else {
                    format!("{}", c)
                };
                match o {
                    0 => format!("{}", c),
                    1 => format!("{}x", co_str),
                    _ => format!("{}x^{}", co_str, o),
                }
            }
        };
        write!(
            f,
            "{}",
            poly.iter()
                .fold(String::from(""), |unit, &&(ord, &coef)| format!(
                    "{}{}{}",
                    unit,
                    if ord != max_order {
                        match coef.partial_cmp(&0.0).unwrap() {
                            Ordering::Greater => " + ",
                            Ordering::Less => " - ",
                            _ => "",
                        }
                    } else {
                        ""
                    }.to_string(),
                    format_item((ord, coef.abs()))
                ))
        )
    }
}

impl Add for Polynomial {
    type Output = Polynomial;
    fn add(self, other: Polynomial) -> Polynomial {
        let lhs_order = self.get_order();
        let rhs_order = other.get_order();
        let lhs_coef = self.coefficients;
        let rhs_coef = other.coefficients;

        let mut added = lhs_coef
            .iter()
            .zip(rhs_coef.iter())
            .map(|(l, r)| l + r)
            .collect::<Vec<_>>();

        let (_, remained) = if lhs_order < rhs_order {
            rhs_coef.split_at(lhs_order + 1)
        } else {
            lhs_coef.split_at(rhs_order + 1)
        };

        added.extend_from_slice(remained);
        let added = if added.iter().all(|&it| it == 0f32) {
            vec![0f32]
        } else {
            added
                .into_iter()
                .rev()
                .skip_while(|&i| i == 0f32)
                .collect::<Vec<_>>()
                .into_iter()
                .rev()
                .collect::<Vec<_>>()
        };

        Polynomial::new(&added, false)
    }
}
impl Sub for Polynomial {
    type Output = Polynomial;
    fn sub(self, other: Polynomial) -> Polynomial {
        let lhs_order = self.get_order();
        let rhs_order = other.get_order();
        let lhs_coef = self.coefficients;
        let rhs_coef = other.coefficients;

        let mut subed = lhs_coef
            .iter()
            .zip(rhs_coef.iter())
            .map(|(l, r)| l - r)
            .collect::<Vec<_>>();

        let (_, remained) = if lhs_order < rhs_order {
            rhs_coef.split_at(lhs_order + 1)
        } else {
            lhs_coef.split_at(rhs_order + 1)
        };

        subed.extend_from_slice(remained);
        let subed = if subed.iter().all(|&it| it == 0f32) {
            vec![0f32]
        } else {
            subed
                .into_iter()
                .rev()
                .skip_while(|&i| i == 0f32)
                .collect::<Vec<_>>()
                .into_iter()
                .rev()
                .collect::<Vec<_>>()
        };
        Polynomial::new(&subed, false)
    }
}
impl Mul for Polynomial {
    type Output = Polynomial;
    fn mul(self, other: Polynomial) -> Polynomial {
        let lhs_coef = self.coefficients.iter().enumerate().collect::<Vec<_>>();
        let mut rhs_coef = other.coefficients;
        rhs_coef.reverse();
        lhs_coef
            .into_iter()
            .map(|(ord, coef)| {
                let mut coefs = rhs_coef.iter().map(|r| coef * r).collect::<Vec<_>>();
                let ord_shift = (0..ord).map(|_| 0.0).collect::<Vec<_>>();
                coefs.extend_from_slice(&ord_shift);
                Polynomial::new(&coefs, true)
            }).fold(Polynomial::new(&[0f32], false), |sum, ele| sum + ele)
    }
}
impl Div for Polynomial {
    type Output = Polynomial;
    fn div(self, other: Polynomial) -> Polynomial {
        let rhs_order = other.get_order();
        let mut acc = self.clone();
        let mut quotient = Polynomial::new(&[0f32], false);

        while acc.get_order() >= rhs_order {
            let order_diff = acc.get_order() - rhs_order;
            let quot_coef =
                acc.coefficients.iter().last().unwrap() / other.coefficients.iter().last().unwrap();
            let quot = Polynomial::new(
                &(0..(order_diff + 1))
                    .map(|i| if i == order_diff { quot_coef } else { 0f32 })
                    .collect::<Vec<_>>(),
                false,
            );
            acc = acc - (other.clone() * quot.clone());
            quotient = quotient + quot.clone();
        }
        quotient
    }
}
impl Rem for Polynomial {
    type Output = Polynomial;
    fn rem(self, other: Polynomial) -> Polynomial {
        self.clone() - (self / other.clone()) * other
    }
}
impl Zero for u32 {
    fn get_zero() -> u32 {
        0
    }
}
impl Zero for Polynomial {
    fn get_zero() -> Polynomial {
        Polynomial::new(&vec![0f32], false)
    }
}
// fn gcd(a: u32, b: u32) -> u32 {
//     if b == 0 { a } else { gcd(b, a % b) }
// }
// fn gcd(a: Polynomial, b: Polynomial) -> Polynomial {
//     if b == Polynomial::new(&vec![0f32], false) {
//         a
//     } else {
//         gcd(b.clone(), a % b)
//     }
// }

fn gcd<T>(a: T, b: T) -> T
where
    T: Add<Output = T>
        + Sub<Output = T>
        + Mul<Output = T>
        + Rem<Output = T>
        + Zero
        + PartialEq
        + Clone,
{
    if b == <T as Zero>::get_zero() {
        a
    } else {
        gcd(b.clone(), a % b)
    }
}
fn main() {
    let fx = Polynomial::new(&[2.0, -7.0, 4.0, -4.0, 2.0, 3.0], true);
    let gx = Polynomial::new(&[1.0, 0.0, 0.0, 0.0, -1.0], true);
    println!("f(x) = {}", fx);
    println!("g(x) = {}", gx);
    println!("gcd(f(x),g(x)) = {}", gcd(fx, gx));
}
#[test]
fn gcd_test() {
    assert_eq!(gcd(7, 5), 1);
    assert_eq!(gcd(36, 1024), 4);
    assert_eq!(
        gcd(
            Polynomial::new(&[24f32, 26f32, 9f32, 1f32], false),
            Polynomial::new(&[8f32, 14f32, 7f32, 1f32], false)
        ),
        Polynomial::new(&[16f32, 12f32, 2f32], false)
    );
}