symbolic_polynomials/
monomial.rs

1use std::ops::{MulAssign, DivAssign, Add, Neg, Sub, Mul, Div};
2use std::cmp::{Ord, Ordering};
3
4use traits::*;
5use polynomial::Polynomial;
6use composite::Composite;
7
8#[derive(Clone, Default, Debug, Eq)]
9/// A symbolic monomial represented as  C * a_1^p_1 * a_2^p_2 * ... * a_n^p_n.
10pub struct Monomial<I, C, P>
11    where I: Id, C: Coefficient, P: Power {
12    /// The constant coefficient C
13    pub coefficient: C,
14    /// A vector of the pairs (a_i, p_i), where a_i is a Composite expression.
15    pub powers: Vec<(Composite<I, C, P>, P)>,
16}
17
18impl<I, C, P> Monomial<I, C, P>
19    where I: Id, C: Coefficient, P: Power {
20    /// Returns `true` if the the two monomials are equal when we ignore their coefficients.
21    pub fn up_to_coefficient(&self, other: &Monomial<I, C, P>) -> bool {
22        if self.powers.len() == other.powers.len() {
23            for (&(ref c, ref power), &(ref o_c, ref o_power)) in self.powers.iter().zip(other.powers.iter()) {
24                if c != o_c || power != o_power {
25                    return false;
26                }
27            }
28            true
29        } else {
30            false
31        }
32    }
33
34    /// `True` only if the monomial is constant and does not depend on any symbolic variables.
35    pub fn is_constant(&self) -> bool {
36        self.powers.is_empty()
37    }
38
39    /// Evaluates the `Monomial` given the provided mapping of identifier to value assignment.
40    pub fn eval(&self, values: &::std::collections::HashMap<I, C>) -> Result<C, (I, String)> {
41        let mut value = self.coefficient.clone();
42        for &(ref c, ref pow) in &self.powers {
43            value *= ::num::pow(c.eval(values)?, pow.to_usize().unwrap());
44        }
45        Ok(value)
46    }
47
48    /// Returns a code equivalent string representation of the `Monomial`.
49    /// The `format` specifies a function how to render the identifiers;
50    pub fn to_code<F>(&self, format: &F) -> String
51        where F: ::std::ops::Fn(I) -> String {
52        let mut str: String = "".into();
53        if self.coefficient == C::zero() {
54            return "0".into();
55        } else if self.coefficient == C::one() && self.powers.is_empty() {
56            return "1".into();
57        } else if self.coefficient == -C::one() && self.powers.is_empty() {
58            return "- 1".into();
59        } else if self.coefficient == -C::one() {
60            str = "- ".into();
61        } else if self.coefficient < C::zero() {
62            str = "- ".into();
63            str.push_str(&(-self.coefficient.clone()).to_string());
64        } else if self.coefficient != C::one() {
65            str = self.coefficient.clone().to_string();
66        }
67        let mut first = true;
68        for &(ref c, ref pow) in &self.powers {
69            if !first || (self.coefficient != C::one() && self.coefficient != -C::one()) {
70                str.push_str(" * ");
71            }
72            if pow == &P::one() {
73                str.push_str(&c.to_code(format));
74            } else if pow != &P::zero() {
75                str.push_str(&c.to_code(format));
76                for _ in 0..(pow.clone() - P::one()).to_usize().unwrap() {
77                    str.push_str(" * ");
78                    str.push_str(&c.to_code(format));
79                }
80            }
81            first = false;
82        }
83        str
84    }
85}
86
87impl<I, C, P> ::std::fmt::Display for Monomial<I, C, P>
88    where I: Id, C: Coefficient, P: Power {
89    fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::result::Result<(), ::std::fmt::Error> {
90        if self.coefficient == C::zero() {
91            return write!(f, "0");
92        } else if self.coefficient == C::one() && self.powers.is_empty() {
93            return write!(f, "1");
94        } else if self.coefficient == -C::one() && self.powers.is_empty() {
95            return write!(f, "- 1");
96        } else if self.coefficient == -C::one() {
97            write!(f, "- ")?;
98        } else if self.coefficient < C::zero() {
99            write!(f, "- {}", -self.coefficient.clone())?;
100        } else if self.coefficient != C::one() {
101            write!(f, "{}", self.coefficient.clone())?;
102        }
103        for &(ref c, ref pow) in &self.powers {
104            if pow == &P::one() {
105                write!(f, "{}", c)?;
106            } else if pow != &P::zero() {
107                write!(f, "{}^{}", c, pow)?;
108            }
109        }
110        Ok(())
111    }
112}
113
114impl<I, C, P> From<C> for Monomial<I, C, P>
115    where I: Id, C: Coefficient, P: Power {
116    fn from(other: C) -> Self {
117        Monomial {
118            coefficient: other,
119            powers: Vec::new(),
120        }
121    }
122}
123
124impl<I, C, P> PartialEq<C> for Monomial<I, C, P>
125    where I: Id, C: Coefficient, P: Power {
126    fn eq(&self, other: &C) -> bool {
127        if self.coefficient == *other {
128            self.is_constant()
129        } else {
130            false
131        }
132    }
133}
134
135impl<I, C, P> PartialEq for Monomial<I, C, P>
136    where I: Id, C: Coefficient, P: Power {
137    fn eq(&self, other: &Monomial<I, C, P>) -> bool {
138        if self.coefficient == other.coefficient {
139            self.up_to_coefficient(other)
140        } else {
141            false
142        }
143    }
144}
145
146impl<I, C, P> PartialEq<Polynomial<I, C, P>> for Monomial<I, C, P>
147    where I: Id, C: Coefficient, P: Power {
148    fn eq(&self, other: &Polynomial<I, C, P>) -> bool {
149        other.eq(self)
150    }
151}
152
153impl<I, C, P> PartialOrd<C> for Monomial<I, C, P>
154    where I: Id, C: Coefficient, P: Power {
155    fn partial_cmp(&self, other: &C) -> Option<Ordering> {
156        if self.is_constant() {
157            self.coefficient.partial_cmp(&other.clone().into())
158        } else {
159            Some(Ordering::Greater)
160        }
161    }
162}
163
164impl<I, C, P> PartialOrd for Monomial<I, C, P>
165    where I: Id, C: Coefficient, P: Power {
166    fn partial_cmp(&self, other: &Monomial<I, C, P>) -> Option<Ordering> {
167        Some(self.cmp(other))
168    }
169}
170
171impl<I, C, P> PartialOrd<Polynomial<I, C, P>> for Monomial<I, C, P>
172    where I: Id, C: Coefficient, P: Power {
173    fn partial_cmp(&self, other: &Polynomial<I, C, P>) -> Option<Ordering> {
174        match other.partial_cmp(self) {
175            Some(Ordering::Less) => Some(Ordering::Greater),
176            Some(Ordering::Equal) => Some(Ordering::Equal),
177            Some(Ordering::Greater) => Some(Ordering::Less),
178            None => None,
179        }
180    }
181}
182
183impl<I, C, P> Ord for Monomial<I, C, P>
184    where I: Id, C: Coefficient, P: Power {
185    fn cmp(&self, other: &Monomial<I, C, P>) -> Ordering {
186        let min = ::std::cmp::min(self.powers.len(), other.powers.len());
187        for i in 0..min {
188            match Ord::cmp(&self.powers[i].0, &other.powers[i].0) {
189                Ordering::Equal => {
190                    match Ord::cmp(&self.powers[i].1, &other.powers[i].1) {
191                        Ordering::Equal => {}
192                        v => return v,
193                    }
194                }
195                v => return v,
196            }
197        }
198        match Ord::cmp(&self.powers.len(), &other.powers.len()) {
199            Ordering::Equal => Ord::cmp(&self.coefficient, &other.coefficient),
200            v => v,
201        }
202    }
203}
204
205impl<I, C, P> MulAssign<C> for Monomial<I, C, P>
206    where I: Id, C: Coefficient, P: Power {
207    fn mul_assign(&mut self, rhs: C) {
208        self.coefficient *= rhs;
209    }
210}
211
212impl<'a, I, C, P> Mul<C> for &'a Monomial<I, C, P>
213    where I: Id, C: Coefficient, P: Power {
214    type Output = Monomial<I, C, P>;
215    fn mul(self, rhs: C) -> Self::Output {
216        let mut result = self.clone();
217        result *= rhs;
218        result
219    }
220}
221
222impl<'a, I, C, P> MulAssign<&'a Monomial<I, C, P>> for Monomial<I, C, P>
223    where I: Id, C: Coefficient, P: Power {
224    fn mul_assign(&mut self, rhs: &'a Monomial<I, C, P>) {
225        self.coefficient *= rhs.coefficient.clone();
226        let mut i1 = 0;
227        let mut i2 = 0;
228        while i1 < self.powers.len() && i2 < rhs.powers.len() {
229            match Ord::cmp(&self.powers[i1].0, &rhs.powers[i2].0) {
230                Ordering::Greater => {}
231                Ordering::Less => {
232                    self.powers.insert(i1, rhs.powers[i2].clone());
233                    i2 += 1;
234                }
235                Ordering::Equal => {
236                    self.powers[i1] = (self.powers[i1].0.clone(), self.powers[i1].1.clone() + rhs.powers[i2].1.clone());
237                    i2 += 1;
238                }
239            }
240            i1 += 1;
241        }
242        while i2 < rhs.powers.len() {
243            self.powers.push(rhs.powers[i2].clone());
244            i2 += 1;
245        }
246    }
247}
248
249impl<'a, 'b, I, C, P> Mul<&'a Monomial<I, C, P>> for &'b Monomial<I, C, P>
250    where I: Id, C: Coefficient, P: Power {
251    type Output = Monomial<I, C, P>;
252    fn mul(self, rhs: &'a Monomial<I, C, P>) -> Self::Output {
253        let mut result = self.clone();
254        result *= rhs;
255        result
256    }
257}
258
259impl<'a, 'b, I, C, P> Mul<&'a Polynomial<I, C, P>> for &'b Monomial<I, C, P>
260    where I: Id, C: Coefficient, P: Power {
261    type Output = Polynomial<I, C, P>;
262    fn mul(self, rhs: &'a Polynomial<I, C, P>) -> Self::Output {
263        let mut result = rhs.clone();
264        result *= self;
265        result
266    }
267}
268
269// impl<I, C, P> CheckedDiv<C> for Monomial<I, C, P>
270//    where I: Id, C: Coefficient, P: Power {
271//    type Output = Monomial<I, C, P>;
272//    fn checked_div(&self, other: C) -> Option<Self::Output> {
273//        let (d, rem) = self.coefficient.div_rem(&other);
274//        if rem == C::zero() {
275//            Some(Monomial {
276//                coefficient: d,
277//                powers: self.powers.clone(),
278//            })
279//        } else {
280//            None
281//        }
282//    }
283//
284
285impl<'a, I, C, P> Div<C> for &'a Monomial<I, C, P>
286    where I: Id, C: Coefficient, P: Power {
287    type Output = Monomial<I, C, P>;
288    fn div(self, other: C) -> Self::Output {
289        self.checked_div(&other.into()).unwrap()
290    }
291}
292
293impl<I, C, P> DivAssign<C> for Monomial<I, C, P>
294    where I: Id, C: Coefficient, P: Power {
295    fn div_assign(&mut self, rhs: C) {
296        let (d, rem) = self.coefficient.div_rem(&rhs);
297        if rem == C::zero() {
298            self.coefficient = d;
299        } else {
300            panic!("Non integer division via DivAssign")
301        }
302    }
303}
304
305// impl<'a, I, C, P> CheckedDiv<&'a Monomial<I, C, P>> for Monomial<I, C, P>
306//    where I: Id, C: Coefficient, P: Power {
307//    type Output = Monomial<I, C, P>;
308impl<I, C, P> Monomial<I, C, P>
309    where I: Id, C: Coefficient, P: Power {
310    /// If the the monomial is divisible by `rhs` than returns the result
311    /// of that division, otherwise None.
312    pub fn checked_div(&self, rhs: &Monomial<I, C, P>) -> Option<Self> {
313        let (d, rem) = self.coefficient.div_rem(&rhs.coefficient);
314        if rem == C::zero() {
315            let mut result = Monomial {
316                coefficient: d,
317                powers: self.powers.clone(),
318            };
319            let mut i1 = 0;
320            let mut i2 = 0;
321            while i1 < result.powers.len() && i2 < rhs.powers.len() {
322                match Ord::cmp(&result.powers[i1].0, &rhs.powers[i2].0) {
323                    Ordering::Less => return None,
324                    Ordering::Greater => {
325                        i1 += 1;
326                    }
327                    Ordering::Equal => {
328                        match Ord::cmp(&result.powers[i1].1, &rhs.powers[i2].1) {
329                            Ordering::Less => return None,
330                            Ordering::Equal => {
331                                result.powers.remove(i1);
332                                i2 += 1;
333                            }
334                            Ordering::Greater => {
335                                result.powers[i1] = (result.powers[i1].0.clone(),
336                                                     result.powers[i1].1.clone() - rhs.powers[i2].1.clone());
337                                i1 += 1;
338                                i2 += 1;
339                            }
340                        }
341                    }
342                }
343            }
344            if i2 < rhs.powers.len() {
345                None
346            } else {
347                Some(result)
348            }
349        } else {
350            None
351        }
352    }
353}
354
355impl<'a, 'b, I, C, P> Div<&'a Monomial<I, C, P>> for &'b Monomial<I, C, P>
356    where I: Id, C: Coefficient, P: Power {
357    type Output = Monomial<I, C, P>;
358    fn div(self, rhs: &'a Monomial<I, C, P>) -> Self::Output {
359        self.checked_div(rhs).unwrap()
360    }
361}
362
363impl<'a, I, C, P> DivAssign<&'a Monomial<I, C, P>> for Monomial<I, C, P>
364    where I: Id, C: Coefficient, P: Power {
365    fn div_assign(&mut self, rhs: &'a Monomial<I, C, P>) {
366        let result = (self as &Monomial<I, C, P>).checked_div(rhs).unwrap();
367        self.coefficient = result.coefficient;
368        self.powers = result.powers.clone();
369    }
370}
371
372impl<'a, I, C, P> Neg for &'a Monomial<I, C, P>
373    where I: Id, C: Coefficient, P: Power {
374    type Output = Monomial<I, C, P>;
375    fn neg(self) -> Self::Output {
376        Monomial {
377            coefficient: -self.coefficient.clone(),
378            powers: self.powers.clone(),
379        }
380    }
381}
382
383impl<'a, I, C, P> Add<C> for &'a Monomial<I, C, P>
384    where I: Id, C: Coefficient, P: Power {
385    type Output = Polynomial<I, C, P>;
386    fn add(self, rhs: C) -> Self::Output {
387        if rhs == C::zero() {
388            Polynomial { monomials: vec![self.clone()] }
389        } else if self.is_constant() {
390            if rhs == -self.coefficient.clone() {
391                Polynomial { monomials: Vec::new() }
392            } else {
393                let mut result = Polynomial::from(self);
394                result.monomials[0].coefficient += rhs;
395                result
396            }
397        } else {
398            Polynomial { monomials: vec![self.clone(), Monomial::from(rhs)] }
399        }
400    }
401}
402
403impl<'a, 'b, I, C, P> Add<&'b Monomial<I, C, P>> for &'a Monomial<I, C, P>
404    where I: Id, C: Coefficient, P: Power {
405    type Output = Polynomial<I, C, P>;
406    fn add(self, rhs: &'b Monomial<I, C, P>) -> Self::Output {
407        if rhs.coefficient == C::zero() && self.coefficient == C::zero() {
408            Polynomial { monomials: Vec::new() }
409        } else if rhs.coefficient == C::zero() {
410            Polynomial { monomials: vec![self.clone()] }
411        } else if self.coefficient == C::zero() {
412            Polynomial { monomials: vec![rhs.clone()] }
413        } else if self.up_to_coefficient(rhs) {
414            if self.coefficient == -rhs.coefficient.clone() {
415                Polynomial { monomials: Vec::new() }
416            } else {
417                let mut result = Polynomial { monomials: vec![self.clone()] };
418                result.monomials[0].coefficient += rhs.coefficient.clone();
419                result
420            }
421        } else if self > rhs {
422            Polynomial { monomials: vec![self.clone(), rhs.clone()] }
423        } else {
424            Polynomial { monomials: vec![rhs.clone(), self.clone()] }
425        }
426    }
427}
428
429impl<'a, 'b, I, C, P> Add<&'a Polynomial<I, C, P>> for &'b Monomial<I, C, P>
430    where I: Id, C: Coefficient, P: Power {
431    type Output = Polynomial<I, C, P>;
432    fn add(self, rhs: &'a Polynomial<I, C, P>) -> Self::Output {
433        let mut result = rhs.clone();
434        result += self;
435        result
436    }
437}
438
439impl<'a, I, C, P> Sub<C> for &'a Monomial<I, C, P>
440    where I: Id, C: Coefficient, P: Power {
441    type Output = Polynomial<I, C, P>;
442    fn sub(self, rhs: C) -> Self::Output {
443        if rhs == C::zero() {
444            Polynomial { monomials: vec![self.clone()] }
445        } else if self.is_constant() {
446            if rhs == self.coefficient {
447                Polynomial { monomials: Vec::new() }
448            } else {
449                let mut result = Polynomial::from(self);
450                result.monomials[0].coefficient -= rhs;
451                result
452            }
453        } else {
454            Polynomial { monomials: vec![self.clone(), Monomial::from(-rhs)] }
455        }
456    }
457}
458
459impl<'a, 'b, I, C, P> Sub<&'b Monomial<I, C, P>> for &'a Monomial<I, C, P>
460    where I: Id, C: Coefficient, P: Power {
461    type Output = Polynomial<I, C, P>;
462    fn sub(self, rhs: &'b Monomial<I, C, P>) -> Self::Output {
463        if self.coefficient == C::zero() && rhs.coefficient == C::zero() {
464            Polynomial { monomials: Vec::new() }
465        } else if rhs.coefficient == C::zero() {
466            Polynomial { monomials: vec![self.clone()] }
467        } else if self.coefficient == C::zero() {
468            Polynomial { monomials: vec![-rhs] }
469        } else if self.up_to_coefficient(rhs) {
470            if self.coefficient == rhs.coefficient {
471                Polynomial { monomials: Vec::new() }
472            } else {
473                let mut result = Polynomial { monomials: vec![self.clone()] };
474                result.monomials[0].coefficient -= rhs.coefficient.clone();
475                result
476            }
477        } else if self > rhs {
478            Polynomial { monomials: vec![self.clone(), -rhs] }
479        } else {
480            Polynomial { monomials: vec![-rhs, self.clone()] }
481        }
482    }
483}
484
485impl<'a, 'b, I, C, P> Sub<&'a Polynomial<I, C, P>> for &'b Monomial<I, C, P>
486    where I: Id, C: Coefficient, P: Power {
487    type Output = Polynomial<I, C, P>;
488    fn sub(self, rhs: &'a Polynomial<I, C, P>) -> Self::Output {
489        let mut result = -rhs;
490        result += self;
491        result
492    }
493}
symbolic_polynomials/monomial.rs

symbolic_polynomials/
monomial.rs
