use num_bigint::{BigInt, BigUint};
use num_traits::{pow, One, Signed, Zero};
use std::{fmt, ops};
#[derive(Eq, PartialEq, Clone, Debug)]
struct Term {
coeff: BigInt,
base: BigUint,
}
#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Polynomial {
terms: Vec<Term>,
}
impl Polynomial {
pub fn one_term(coeff: BigInt, base: BigUint) -> Polynomial {
Polynomial {
terms: if base.is_zero() || coeff.is_zero() {
vec![]
} else {
vec![Term {
coeff: coeff,
base: base,
}]
},
}
}
pub fn apply(&self, value: usize) -> BigInt {
self.terms.iter().fold(BigInt::zero(), |result, term| {
let term = term.clone();
result + term.coeff * BigInt::from(pow(term.base, value))
})
}
}
trait MergeOps {
fn unary_op(rhs: BigInt) -> BigInt;
fn binary_op(lhs: BigInt, rhs: BigInt) -> BigInt;
}
struct AddOps;
impl MergeOps for AddOps {
fn unary_op(rhs: BigInt) -> BigInt {
rhs
}
fn binary_op(lhs: BigInt, rhs: BigInt) -> BigInt {
lhs + rhs
}
}
struct SubOps;
impl MergeOps for SubOps {
fn unary_op(rhs: BigInt) -> BigInt {
-rhs
}
fn binary_op(lhs: BigInt, rhs: BigInt) -> BigInt {
lhs - rhs
}
}
fn merge_terms<Ops: MergeOps>(output: &mut Vec<Term>, _ops: Ops, lhs: Vec<Term>, rhs: Vec<Term>) {
assert!(output.is_empty());
output.reserve(lhs.len() + rhs.len());
let mut iter_lhs = lhs.into_iter();
let mut iter_rhs = rhs.into_iter();
let mut cur_lhs = iter_lhs.next();
let mut cur_rhs = iter_rhs.next();
loop {
let (next_lhs, next_rhs, next_result) = match (cur_lhs, cur_rhs) {
(Some(a), Some(b)) => {
if a.base < b.base {
(iter_lhs.next(), Some(b), a)
} else if a.base > b.base {
(
Some(a),
iter_rhs.next(),
Term {
coeff: Ops::unary_op(b.coeff),
base: b.base,
},
)
} else {
(
iter_lhs.next(),
iter_rhs.next(),
Term {
coeff: Ops::binary_op(a.coeff, b.coeff),
base: a.base,
},
)
}
}
(Some(a), None) => (iter_lhs.next(), None, a),
(None, Some(b)) => (
None,
iter_rhs.next(),
Term {
coeff: Ops::unary_op(b.coeff),
base: b.base,
},
),
(None, None) => {
break;
}
};
if !next_result.coeff.is_zero() {
output.push(next_result);
}
cur_lhs = next_lhs;
cur_rhs = next_rhs;
}
output.shrink_to_fit();
}
impl ops::Add for Polynomial {
type Output = Polynomial;
fn add(self, other: Polynomial) -> Polynomial {
let mut terms = vec![];
merge_terms(&mut terms, AddOps, self.terms, other.terms);
Polynomial { terms: terms }
}
}
impl ops::Sub for Polynomial {
type Output = Polynomial;
fn sub(self, other: Polynomial) -> Polynomial {
let mut terms = vec![];
merge_terms(&mut terms, SubOps, self.terms, other.terms);
Polynomial { terms: terms }
}
}
impl ops::AddAssign for Polynomial {
fn add_assign(&mut self, other: Polynomial) {
let old_terms = self.terms.drain(..).collect();
merge_terms(&mut self.terms, AddOps, old_terms, other.terms);
}
}
impl ops::SubAssign for Polynomial {
fn sub_assign(&mut self, other: Polynomial) {
let old_terms = self.terms.drain(..).collect();
merge_terms(&mut self.terms, SubOps, old_terms, other.terms);
}
}
impl fmt::Display for Polynomial {
fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
let mut iter = self.terms.iter().rev();
if let Some(first_term) = iter.next() {
if first_term.coeff == BigInt::one() {
write!(fmt, "{}^x", first_term.base)?;
} else {
write!(fmt, "{}*{}^x", first_term.coeff, first_term.base)?;
}
for term in iter {
let sign = if term.coeff.is_positive() { "+" } else { "-" };
let abs_coeff = term.coeff.abs();
if abs_coeff == BigInt::one() {
write!(fmt, " {} {}^x", sign, term.base)?;
} else {
write!(fmt, " {} {}*{}^x", sign, abs_coeff, term.base)?;
}
}
Ok(())
} else {
write!(fmt, "0")
}
}
}
#[cfg(test)]
mod test {
use super::{Polynomial, Term};
use num_bigint::{BigInt, BigUint};
use num_traits::{pow, Zero};
fn test_int1() -> BigInt {
BigInt::from(2i32)
}
fn test_int2() -> BigInt {
BigInt::from(5i32)
}
fn test_uint1() -> BigUint {
BigUint::from(12u32)
}
fn test_uint2() -> BigUint {
BigUint::from(25u32)
}
fn empty_polynomial() -> Polynomial {
Polynomial { terms: vec![] }
}
#[test]
fn one_term_test() {
assert_eq!(
Polynomial::one_term(test_int1(), test_uint1()),
Polynomial {
terms: vec![Term {
coeff: test_int1(),
base: test_uint1()
}]
}
);
assert_eq!(
Polynomial::one_term(BigInt::zero(), test_uint1()),
empty_polynomial()
);
}
#[test]
fn add_test() {
let a = Polynomial::one_term(test_int1(), test_uint1());
let b = Polynomial::one_term(test_int2(), test_uint2());
let sum = Polynomial {
terms: vec![
Term {
coeff: test_int1(),
base: test_uint1(),
},
Term {
coeff: test_int2(),
base: test_uint2(),
},
],
};
assert_eq!(a.clone() + b.clone(), sum);
assert_eq!(b.clone() + a.clone(), sum);
let a = Polynomial::one_term(test_int1(), test_uint1());
let b = Polynomial::one_term(test_int2(), test_uint1());
let sum = Polynomial {
terms: vec![Term {
coeff: test_int1() + test_int2(),
base: test_uint1(),
}],
};
assert_eq!(a.clone() + b.clone(), sum);
assert_eq!(b.clone() + a.clone(), sum);
let a = Polynomial::one_term(test_int1(), test_uint1());
let b = Polynomial::one_term(-test_int1(), test_uint1());
assert_eq!(a.clone() + b.clone(), empty_polynomial());
}
#[test]
fn sub_test() {
let a = Polynomial::one_term(test_int1(), test_uint1());
let b = Polynomial::one_term(test_int2(), test_uint2());
let diff = Polynomial {
terms: vec![
Term {
coeff: test_int1(),
base: test_uint1(),
},
Term {
coeff: -test_int2(),
base: test_uint2(),
},
],
};
assert_eq!(a.clone() - b.clone(), diff);
let diff = Polynomial {
terms: vec![
Term {
coeff: -test_int1(),
base: test_uint1(),
},
Term {
coeff: test_int2(),
base: test_uint2(),
},
],
};
assert_eq!(b.clone() - a.clone(), diff);
let a = Polynomial::one_term(test_int1(), test_uint1());
let b = Polynomial::one_term(test_int2(), test_uint1());
let diff = Polynomial {
terms: vec![Term {
coeff: test_int1() - test_int2(),
base: test_uint1(),
}],
};
assert_eq!(a.clone() - b.clone(), diff);
let diff = Polynomial {
terms: vec![Term {
coeff: test_int2() - test_int1(),
base: test_uint1(),
}],
};
assert_eq!(b.clone() - a.clone(), diff);
assert_eq!(a.clone() - a.clone(), empty_polynomial());
}
#[test]
fn add_assign_test() {
let a = Polynomial::one_term(test_int1(), test_uint1());
let b = Polynomial::one_term(test_int2(), test_uint2());
let mut sum = a.clone();
sum += b.clone();
assert_eq!(sum, a.clone() + b.clone());
let mut sum = b.clone();
sum += a.clone();
assert_eq!(sum, b.clone() + a.clone());
let a = Polynomial::one_term(test_int1(), test_uint1());
let b = Polynomial::one_term(test_int2(), test_uint1());
let mut sum = a.clone();
sum += b.clone();
assert_eq!(sum, a.clone() + b.clone());
let mut sum = b.clone();
sum += a.clone();
assert_eq!(sum, b.clone() + a.clone());
}
#[test]
fn sub_assign_test() {
let a = Polynomial::one_term(test_int1(), test_uint1());
let b = Polynomial::one_term(test_int2(), test_uint2());
let mut diff = a.clone();
diff -= b.clone();
assert_eq!(diff, a.clone() - b.clone());
let mut diff = b.clone();
diff -= a.clone();
assert_eq!(diff, b.clone() - a.clone());
let a = Polynomial::one_term(test_int1(), test_uint1());
let b = Polynomial::one_term(test_int2(), test_uint1());
let mut diff = a.clone();
diff -= b.clone();
assert_eq!(diff, a.clone() - b.clone());
let mut diff = b.clone();
diff -= a.clone();
assert_eq!(diff, b.clone() - a.clone());
}
#[test]
fn apply_test() {
let a = Polynomial::one_term(test_int1(), test_uint1());
let b = Polynomial::one_term(test_int2(), test_uint2());
let x = 50usize;
assert_eq!(
(a.clone() + b.clone()).apply(x),
test_int1() * BigInt::from(pow(test_uint1(), x))
+ test_int2() * BigInt::from(pow(test_uint2(), x))
);
assert_eq!(
(a.clone() - b.clone()).apply(x),
test_int1() * BigInt::from(pow(test_uint1(), x))
- test_int2() * BigInt::from(pow(test_uint2(), x))
);
}
}