free_algebra/
module.rs

1//!
2//!Contains [ModuleString] and the types and traits relevant to its system
3//!
4//!For more information see the struct-level docs
5//!
6
7use super::*;
8
9use std::collections::hash_map;
10
11///
12///Creates free-arithmetic constructions based upon order-invariant addition of terms of type `C` with
13///multiplication with scalar coefficients of type `R`
14///
15///# Basic Construction
16///
17///Given type parameters `R`, `T`, and `A`, the construction goes as follows:
18/// * Internally, each instance contains a [map](HashMap) from instances of `T` to coefficients from `R`
19/// * Addition is then implemented by merging the arguments' [HashMaps](HashMap) where repeated terms
20///  have their coefficients added together
21/// * Multiplication with `R` values is applied by each term's coefficient with the given scalar
22/// * Multiplication between terms is performed by multiplying the coefficients and apply the rule
23///  defined by type `A`
24/// * Then, full multiplication is defined by distributing over each pair of terms and summing
25///
26///With this system, using different `A` rules and `T`/`R` types, a number of variants can be defined:
27/// * [`FreeModule<R,T>`](FreeModule) defines a [vector-space](VectorSpace) over `R` using the default
28///  addition and `R`-multiplication without having a multiplication rule
29/// * [`FreeAlgebra<R,T>`](FreeAlgebra) is a `FreeModule<R,T>` but where the multiplication rule
30///  between terms is built as with a [`FreeMonoid<T>`](FreeMonoid)
31/// * [`MonoidRing<R,T>`](MonoidRing) is a `FreeModule<R,T>` but where the multiplication rule
32///  for terms simply uses the intrinsic multiplication of `T`
33///
34///# Other `impls`
35///
36///In addition to the basic arithmetic operations, [ModuleString] implements a number of other
37///notable traits depending on the type arguments:
38/// * [Sub], [SubAssign], [Neg], etc. These apply by negating each coefficient whenever `R` is negatable
39/// * [Index] gets coefficient references from a term reference
40/// * [MulAssociative] and [MulCommutative] whenever `R` is and `A` implements [AssociativeMonoidRule]
41///  or [CommutativeMonoidRule]
42/// * [Distributive] whenever `R` is
43/// * [Extend], [FromIterator], and [Sum] all are implemented using repeated addition.
44///
45///# A note on [IterMut]
46///
47///The method [ModuleString.iter_mut()] *will* give an valid iterator over mutable references to each
48///element of the object, but it is of note that because of the nature of some of the [`AlgebraRule`]'s,
49///the method will reallocate internal storage and iterate through *every* element,
50///even if dropped.
51///
52///The reason for this is that if it did not, it would be possible to modify a ModuleString into
53///an invalid state. Hence, to mitigate this, the iterator must remultiply every element again as it
54///iterates over the references.
55///
56#[derive(Derivative)]
57#[derivative(Clone(clone_from="true"))]
58#[derivative(Default(bound=""))]
59#[derivative(PartialEq, Eq, Hash)]
60#[derivative(Debug="transparent")]
61pub struct ModuleString<R,T:Hash+Eq,A:?Sized> {
62    #[derivative(Hash(bound="HashMap<T,R>:Hash"))]
63    #[derivative(Default(value="HashMap::with_capacity(0)"))]
64    terms: HashMap<T,R>,
65
66    #[derivative(PartialEq="ignore", Hash="ignore")]
67    #[derivative(Debug="ignore")]
68    rule: PhantomData<Box<A>>
69}
70
71///
72///Formats the [ModuleString] as a sequence of factors separated by `+`'s
73///
74///# Examples
75///```
76///use maths_traits::algebra::{One, Zero};
77///use free_algebra::{FreeAlgebra, FreeMonoid};
78///
79///let one = FreeMonoid::one();
80///let x:FreeMonoid<_> = 'x'.into();
81///let y:FreeMonoid<_> = 'y'.into();
82///
83///let mut p = FreeAlgebra::zero();
84///assert_eq!(format!("{}", p), "0");
85///
86///p += (1.0, one.clone());
87///assert_eq!(format!("{}", p), "1");
88///
89///p += (2.5, one);
90///assert_eq!(format!("{}", p), "3.5");
91///
92///p += x;
93///assert!(format!("{}", p) == "(3.5 + x)" || format!("{}", p) == "(x + 3.5)");
94///
95///p *= (1.0, y);
96///assert!(format!("{}", p) == "(3.5*y + x*y)" || format!("{}", p) == "(x*y + 3.5*y)");
97///assert!(format!("{:#}", p) == "(3.5y + xy)" || format!("{:#}", p) == "(xy + 3.5y)");
98///
99///```
100///
101impl<R:Display,T:Hash+Eq+Display,A:?Sized> Display for ModuleString<R,T,A> {
102    fn fmt(&self, f: &mut Formatter) -> ::std::fmt::Result {
103        if self.len() == 0 {
104            //try to print 0 as formatted by R
105            match R::_zero() {
106                Some(zero) => write!(f, "{}", zero)?,
107                None => write!(f, "{}", 0)?,
108            }
109        } else {
110            //put parens around sums
111            if self.len() > 1 { write!(f, "(")?; }
112
113            //use specialization to determine if a T is one
114            trait IsTOne<R,T> { fn _is_t_one(t:&T) -> bool; }
115            impl<R,T,A:?Sized> IsTOne<R,T> for A { default fn _is_t_one(_:&T) -> bool {false} }
116            impl<R,T,A:UnitalAlgebraRule<R,T>+?Sized> IsTOne<R,T> for A { fn _is_t_one(t:&T) -> bool {A::is_one(t)} }
117
118            //use specialization to determine if a R is one
119            trait IsOne { fn _is_one(&self) -> bool; }
120            impl<R> IsOne for R { default fn _is_one(&self) -> bool {false} }
121            impl<R:One+PartialEq> IsOne for R { fn _is_one(&self) -> bool { self.is_one() } }
122
123            //print every term in a sum
124            let mut first = true;
125            for (r,t) in self.iter() {
126
127                //add the plus sign to the previous sum
128                if !first {
129                    write!(f, " + ")?;
130                } else {
131                    first = false;
132                }
133
134                //if the term isn't one, write the term
135                if !<A as IsTOne<R,T>>::_is_t_one(t) {
136                    //if the coeffient is one, don't write it
137                    if (*r)._is_one() {
138                        if f.alternate() {
139                            write!(f, "{:#}", t)?;
140                        } else {
141                            write!(f, "{}", t)?;
142                        }
143                    } else {
144                        if f.alternate() {
145                            write!(f, "{:#}{:#}", r, t)?;
146                        } else {
147                            write!(f, "{}*{}", r, t)?;
148                        }
149                    }
150                } else {
151                    write!(f, "{}", r)?;
152                }
153            }
154
155            //put parens around sums
156            if self.len() > 1 { write!(f, ")")?; }
157        }
158
159        //success
160        Ok(())
161    }
162}
163
164///Iterates over references to the terms and coefficients of a [ModuleString]
165pub type Iter<'a,R,T> = Map<hash_map::Iter<'a,T,R>, fn((&'a T,&'a R)) -> (&'a R,&'a T)>;
166
167///Iterates over terms and coefficients of a [ModuleString]
168pub type IntoIter<R,T> = Map<hash_map::IntoIter<T,R>, fn((T,R)) -> (R,T)>;
169
170///
171///Iterates over mutable references to the terms and coefficients of a [ModuleString]
172///
173///Note that this causes a reallocation of the internal [HashMap] since it's possible that an
174///element mutation could create an illegal state if not reconstructed from the sums of the mutated
175///terms. (For example, one could easily mutate two terms to have the same `T` value and thus
176///potentially overwrite the coeffient of one of them if not handled properly)
177///
178pub struct IterMut<'a, R:AddAssign, T:Hash+Eq, A:?Sized> {
179    dest_ref: &'a mut ModuleString<R,T,A>,
180    next: Option<(R,T)>,
181    iter: IntoIter<R,T>
182}
183
184impl<'a,T:Hash+Eq,R:AddAssign,A:?Sized> FusedIterator for IterMut<'a,R,T,A> {}
185impl<'a,T:Hash+Eq,R:AddAssign,A:?Sized> ExactSizeIterator for IterMut<'a,R,T,A> {}
186impl<'a,T:Hash+Eq,R:AddAssign,A:?Sized> Iterator for IterMut<'a,R,T,A> {
187    type Item = (&'a mut R, &'a mut T);
188    fn next(&mut self) -> Option<Self::Item> {
189        self.next.take().map(|t| *self.dest_ref += t);
190        self.next = self.iter.next();
191
192        //we know that the given reference is lifetime 'a because in order for next to be dropped,
193        //either self must be borrowed mutably again or dropped, which cannot happen while the reference lives
194        self.next.as_mut().map(|t| unsafe {&mut *(t as *mut (R,T))} ).map(|t| (&mut t.0, &mut t.1))
195    }
196
197    fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() }
198}
199
200impl<'a,T:Hash+Eq,R:AddAssign,A:?Sized> Drop for IterMut<'a,R,T,A> {
201    fn drop(&mut self) {
202        loop { if let None = self.next() {break;} }
203    }
204}
205
206impl<T:Hash+Eq,R:One,A:?Sized> From<T> for ModuleString<R,T,A> {
207    #[inline] fn from(t:T) -> Self {(R::one(),t).into()}
208}
209
210impl<T:Hash+Eq,R:One,A:?Sized> From<(R, T)> for ModuleString<R,T,A> {
211    #[inline]
212    fn from((r,t):(R,T)) -> Self {
213        let mut m = HashMap::new();
214        m.insert(t, r);
215        ModuleString{terms:m, rule:PhantomData}
216    }
217}
218
219impl<T:Hash+Eq,R,A:?Sized,I> Index<I> for ModuleString<R,T,A> where HashMap<T,R>:Index<I> {
220    type Output = <HashMap<T,R> as Index<I>>::Output;
221    #[inline] fn index(&self, i:I) -> &Self::Output {&self.terms[i]}
222}
223
224impl<T:Hash+Eq,R,A:?Sized> IntoIterator for ModuleString<R,T,A> {
225    type Item = (R,T);
226    type IntoIter = IntoIter<R,T>;
227    #[inline] fn into_iter(self) -> IntoIter<R,T> { self.terms.into_iter().map(|(t,r)| (r,t)) }
228}
229
230impl<T:Hash+Eq,R,A:?Sized> ModuleString<R,T,A> {
231
232    ///
233    ///Returns the number of terms in this module element
234    ///
235    ///## Examples
236    ///```
237    ///use maths_traits::algebra::Zero;
238    ///use free_algebra::FreeModule;
239    ///
240    ///let p = FreeModule::zero();
241    ///let q = &p + (3.5, 'x');
242    ///let r = &q + (2.0, 'y');
243    ///let s = &r + (2.0, 'x'); //adds to first term without increasing length
244    ///
245    ///assert_eq!(p.len(), 0);
246    ///assert_eq!(q.len(), 1);
247    ///assert_eq!(r.len(), 2);
248    ///assert_eq!(s.len(), 2);
249    ///
250    ///```
251    ///
252    pub fn len(&self) -> usize {self.terms.len()}
253
254    ///
255    ///Retrieves a reference to the coefficient of a term, if it is non-zero
256    ///
257    ///## Examples
258    ///```
259    ///use maths_traits::algebra::Zero;
260    ///use free_algebra::FreeModule;
261    ///
262    ///let p = FreeModule::zero() + (3.5, 'x') + (2.0, 'y') + (1.0, 'z');
263    ///
264    ///assert_eq!(p.get_ref(&'x'), Some(&3.5));
265    ///assert_eq!(p.get_ref(&'y'), Some(&2.0));
266    ///assert_eq!(p.get_ref(&'z'), Some(&1.0));
267    ///assert_eq!(p.get_ref(&'w'), None);
268    ///
269    ///```
270    ///
271    pub fn get_ref<Q:Hash+Eq>(&self, t: &Q) -> Option<&R> where T:Borrow<Q> {
272        self.terms.get(t)
273    }
274
275    ///
276    ///Clones a the coefficient of a term or returns [zero](Zero::zero()) if it doesn't exist
277    ///
278    ///## Examples
279    ///```
280    ///use maths_traits::algebra::Zero;
281    ///use free_algebra::FreeModule;
282    ///
283    ///let p = FreeModule::zero() + (3.5, 'x') + (2.0, 'y') + (1.0, 'z');
284    ///
285    ///assert_eq!(p.get(&'x'), 3.5);
286    ///assert_eq!(p.get(&'y'), 2.0);
287    ///assert_eq!(p.get(&'z'), 1.0);
288    ///assert_eq!(p.get(&'w'), 0.0);
289    ///
290    ///```
291    ///
292    pub fn get<Q:Hash+Eq>(&self, t: &Q) -> R where T:Borrow<Q>, R:Zero+Clone {
293        self.terms.get(t).map_or_else(|| R::zero(), |r| r.clone())
294    }
295
296    ///Produces an iterator over references to the terms and references in this element
297    pub fn iter<'a>(&'a self) -> Iter<'a,R,T> { self.terms.iter().map(|(t,r)| (r,t)) }
298
299    ///
300    ///Produces an iterator over mutable references to the terms and references in this element
301    ///
302    ///## Examples
303    ///```
304    ///use maths_traits::algebra::Zero;
305    ///use free_algebra::FreeModule;
306    ///
307    ///let mut p = FreeModule::zero() + (3.5, 'x') + (2.0, 'y') + (1.0, 'z');
308    ///for (_, t) in p.iter_mut() {
309    ///    *t = 'a';
310    ///}
311    ///
312    ///assert_eq!(p.get(&'x'), 0.0);
313    ///assert_eq!(p.get(&'y'), 0.0);
314    ///assert_eq!(p.get(&'z'), 0.0);
315    ///assert_eq!(p.get(&'a'), 6.5);
316    ///
317    ///```
318    ///
319    pub fn iter_mut<'a>(&'a mut self) -> IterMut<'a,R,T,A> where R:AddAssign {
320        let mut temp = Self { terms: HashMap::with_capacity(self.len()), rule:PhantomData };
321        ::std::mem::swap(self, &mut temp);
322        IterMut { dest_ref: self, next: None, iter: temp.into_iter() }
323    }
324
325    ///
326    ///Computes the algebraic commutator `[a,b] = a*b - b*a`
327    ///
328    ///## Examples
329    ///```
330    ///use maths_traits::algebra::One;
331    ///use free_algebra::{FreeAlgebra, FreeMonoid};
332    ///
333    ///let one = FreeMonoid::<char>::one();
334    ///let x:FreeMonoid<_> = 'x'.into();
335    ///let y:FreeMonoid<_> = 'y'.into();
336    ///
337    ///let p:FreeAlgebra<f32,_> = FreeAlgebra::one() + &x;
338    ///let q:FreeAlgebra<f32,_> = FreeAlgebra::one() + &y;
339    ///
340    ///let commutator = p.commutator(q);
341    ///
342    ///assert_eq!(commutator.get(&one), 0.0);
343    ///assert_eq!(commutator.get(&x), 0.0);
344    ///assert_eq!(commutator.get(&y), 0.0);
345    ///assert_eq!(commutator.get(&(&x*&y)), 1.0);
346    ///assert_eq!(commutator.get(&(&y*&x)), -1.0);
347    ///```
348    ///
349    ///A property of significance for this product is that when the arguments commute, the
350    ///output is always `0`.
351    ///
352    ///```
353    ///use maths_traits::algebra::{One, Zero};
354    ///use free_algebra::{FreeAlgebra, FreeMonoid};
355    ///
356    ///let p = FreeAlgebra::<f32,_>::one() + FreeMonoid::from('x');
357    ///
358    ///let commutator = p.clone().commutator(p);
359    ///assert!(commutator.is_zero());
360    ///```
361    ///
362    ///
363    ///
364    pub fn commutator(self, rhs:Self) -> Self where Self:MulMagma+Sub<Output=Self> {
365        self.clone()*rhs.clone() - rhs*self
366    }
367
368}
369
370impl<T:Hash+Eq,R,A:?Sized> ModuleString<R,T,A> {
371
372    fn insert_term<F:Fn(R)->R>(&mut self, rhs:(R,T), f:F) where R:AddAssign{
373        if !rhs.0._is_zero() {
374            let (r, t) = (f(rhs.0), rhs.1);
375            if let Some(r2) = self.terms.get_mut(&t) {
376                *r2 += r;
377
378                //Note, we must be VERY careful here because simply doing r2._is_zero() will run
379                //_is_zero() on the REFERENCE to the coefficient, not the coeffient itself
380                if (*r2)._is_zero() { self.terms.remove(&t); }
381            } else if !r._is_zero() {
382                self.terms.insert(t, r);
383            }
384        }
385    }
386
387    fn insert<I:IntoIterator<Item=(R,T)>, F:Fn(R)->R+Copy>(&mut self, rhs:I, f:F) where R:AddAssign {
388        rhs.into_iter().for_each(|term| self.insert_term(term, f));
389    }
390
391    ///removes all terms with a coeffient of zero
392    fn clean(&mut self) { self.terms.retain(|_,r| !r._is_zero()); }
393}
394
395impl<T:Hash+Eq,R:AddAssign,A:?Sized> Extend<(R,T)> for ModuleString<R,T,A> {
396    fn extend<I:IntoIterator<Item=(R,T)>>(&mut self, iter:I) { self.insert(iter, |r| r) }
397}
398
399impl<T:Hash+Eq,R:AddAssign,A:?Sized> FromIterator<(R,T)> for ModuleString<R,T,A> {
400    fn from_iter<I:IntoIterator<Item=(R,T)>>(iter:I) -> Self {
401        let mut from = Self::default();
402        from.extend(iter);
403        from
404    }
405}
406
407impl<T:Hash+Eq,R:AddAssign+One,A:?Sized> FromIterator<T> for ModuleString<R,T,A> {
408    fn from_iter<I:IntoIterator<Item=T>>(iter:I) -> Self {
409        Self::from_iter(iter.into_iter().map(|t| (R::one(), t)))
410    }
411}
412
413impl<T:Hash+Eq,R:AddAssign,A:?Sized> FromIterator<Self> for ModuleString<R,T,A> {
414    fn from_iter<I:IntoIterator<Item=Self>>(iter:I) -> Self {
415        Self::from_iter(iter.into_iter().flatten())
416    }
417}
418
419impl<T:Hash+Eq,R:AddAssign,A:?Sized,K> Sum<K> for ModuleString<R,T,A> where Self:FromIterator<K> {
420    fn sum<I:Iterator<Item=K>>(iter:I) -> Self { Self::from_iter(iter) }
421}
422
423impl<T:Hash+Eq,R,A:?Sized,K> Product<K> for ModuleString<R,T,A> where Self:Mul<K,Output=Self>+One {
424    fn product<I:Iterator<Item=K>>(iter:I) -> Self { iter.into_iter().fold(Self::one(), |m,k| m*k) }
425}
426
427///Dictates a rule for how to multiply terms in a [ModuleString]
428pub trait AlgebraRule<R,T> {
429    ///Multiplies two terms together to produce another `T` and an optional coeffient
430    fn apply(t1:T, t2:T) -> (Option<R>,T);
431}
432
433///An [AlgebraRule] that is evaluation order independent
434pub trait AssociativeAlgebraRule<R,T>: AlgebraRule<R,T> {}
435///An [AlgebraRule] that is order independent
436pub trait CommutativeAlgebraRule<R,T>: AlgebraRule<R,T> {}
437
438///An [AlgebraRule] where a term can be one
439pub trait UnitalAlgebraRule<R,T>: AlgebraRule<R,T> {
440    ///Creates a `T` with a value of one
441    fn one() -> T;
442    ///Determines if a `T` is equal to one
443    fn is_one(t:&T) -> bool;
444}
445
446impl<T:Hash+Eq,R:AddAssociative,A:?Sized> AddAssociative for ModuleString<R,T,A> {}
447impl<T:Hash+Eq,R:AddCommutative,A:?Sized> AddCommutative for ModuleString<R,T,A> {}
448impl<T:Hash+Eq,R:MulAssociative,A:?Sized+AssociativeAlgebraRule<R,T>> MulAssociative for ModuleString<R,T,A> {}
449impl<T:Hash+Eq,R:MulCommutative,A:?Sized+CommutativeAlgebraRule<R,T>> MulCommutative for ModuleString<R,T,A> {}
450
451impl<T:Hash+Eq,R:Distributive,A:?Sized> Distributive for ModuleString<R,T,A> {}
452
453impl<T:Hash+Eq,R:AddAssign,A:?Sized> AddAssign for ModuleString<R,T,A> {
454    fn add_assign(&mut self, rhs:Self) {self.insert(rhs, |r| r)}
455}
456impl<T:Hash+Eq,R:AddAssign+Neg<Output=R>,A:?Sized> SubAssign for ModuleString<R,T,A> {
457    fn sub_assign(&mut self, rhs:Self) {self.insert(rhs, |r| -r)}
458}
459
460impl<T:Hash+Eq,R:AddAssign,A:?Sized> AddAssign<(R,T)> for ModuleString<R,T,A> {
461    fn add_assign(&mut self, rhs:(R,T)) {self.insert_term(rhs, |r| r)}
462}
463impl<T:Hash+Eq,R:AddAssign+Neg<Output=R>,A:?Sized> SubAssign<(R,T)> for ModuleString<R,T,A> {
464    fn sub_assign(&mut self, rhs:(R,T)) {self.insert_term(rhs, |r| -r)}
465}
466
467impl<T:Hash+Eq,R:AddAssign+One,A:?Sized> AddAssign<T> for ModuleString<R,T,A> {
468    fn add_assign(&mut self, rhs:T) {*self+=(R::one(),rhs)}
469}
470impl<T:Hash+Eq,R:AddAssign+Neg<Output=R>+One,A:?Sized> SubAssign<T> for ModuleString<R,T,A> {
471    fn sub_assign(&mut self, rhs:T) {*self-=(R::one(),rhs)}
472}
473
474impl<T:Hash+Eq,R:MulAssign+Clone,A:?Sized> MulAssign<R> for ModuleString<R,T,A> {
475    fn mul_assign(&mut self, rhs:R) {
476        for r2 in self.terms.values_mut() { *r2 *= rhs.clone() }
477        self.clean();
478    }
479}
480impl<T:Hash+Eq,R:DivAssign+Clone,A:?Sized> DivAssign<R> for ModuleString<R,T,A> {
481    fn div_assign(&mut self, rhs:R) {
482        for r2 in self.terms.values_mut() { *r2 /= rhs.clone() }
483        self.clean();
484    }
485}
486
487impl_arith!(impl<T,R,A> AddAssign<&Self>.add_assign for ModuleString<R,T,A> where T:Hash+Eq,A:?Sized);
488impl_arith!(impl<T,R,A> SubAssign<&Self>.sub_assign for ModuleString<R,T,A> where T:Hash+Eq,A:?Sized);
489
490impl_arith!(impl<T,R,A> AddAssign<&T>.add_assign for ModuleString<R,T,A> where T:Hash+Eq,A:?Sized);
491impl_arith!(impl<T,R,A> SubAssign<&T>.sub_assign for ModuleString<R,T,A> where T:Hash+Eq,A:?Sized);
492
493impl_arith!(impl<T,R,A> MulAssign<&R>.mul_assign for ModuleString<R,T,A> where T:Hash+Eq,A:?Sized);
494impl_arith!(impl<T,R,A> DivAssign<&R>.div_assign for ModuleString<R,T,A> where T:Hash+Eq,A:?Sized);
495
496impl_arith!(impl<T,R,A> Add.add with AddAssign.add_assign for ModuleString<R,T,A> where T:Hash+Eq, A:?Sized);
497impl_arith!(impl<T,R,A> Sub.sub with SubAssign.sub_assign for ModuleString<R,T,A> where T:Hash+Eq, A:?Sized);
498impl_arith!(impl<T,R,A> Mul.mul with MulAssign.mul_assign for ModuleString<R,T,A> where T:Hash+Eq, A:?Sized);
499impl_arith!(impl<T,R,A> Div.div with DivAssign.div_assign for ModuleString<R,T,A> where T:Hash+Eq, A:?Sized);
500
501impl<T:Hash+Eq,R:Neg,A:?Sized> Neg for ModuleString<R,T,A> {
502    type Output = ModuleString<R::Output,T,A>;
503    fn neg(self) -> Self::Output {
504        ModuleString {
505            terms: self.terms.into_iter().map(|(t,r)| (t,-r)).filter(|(_,r)| r._is_zero()).collect(),
506            rule: PhantomData
507        }
508    }
509}
510
511impl<'a,T:Hash+Eq,R:Neg,A:?Sized> Neg for &'a ModuleString<R,T,A> where ModuleString<R,T,A>:Clone {
512    type Output = ModuleString<R::Output,T,A>;
513    #[inline] fn neg(self) -> Self::Output {-(*self).clone()}
514}
515
516impl<T:Hash+Eq,R:AddAssign,A:?Sized> Zero for ModuleString<R,T,A> {
517    #[inline] fn zero() -> Self {Default::default()}
518    #[inline] fn is_zero(&self) -> bool {self.terms.len()==0}
519}
520
521impl<T:Clone+Hash+Eq,R:PartialEq+UnitalSemiring,A:UnitalAlgebraRule<R,T>+?Sized> One for ModuleString<R,T,A> {
522    #[inline] fn one() -> Self { A::one().into() }
523    #[inline] fn is_one(&self) -> bool {
524        if self.terms.len()==1 {
525            let term = self.iter().next().unwrap();
526            term.0.is_one() && A::is_one(term.1)
527        } else {
528            false
529        }
530    }
531}
532
533
534impl<T:Hash+Eq+Clone,R:MulMagma+AddMagma,A:?Sized+AlgebraRule<R,T>> MulAssign<(R,T)> for ModuleString<R,T,A> {
535    fn mul_assign(&mut self, (r1,t1): (R,T)) {
536        let mut temp = HashMap::with_capacity(0);
537        ::std::mem::swap(&mut self.terms, &mut temp);
538        *self = temp.into_iter().map(
539            |(t, r)| {
540                let (coeff, t2) = A::apply(t, t1.clone());
541                match coeff {
542                    Some(r2) => ((r*r1.clone())*r2, t2),
543                    None => (r*r1.clone(), t2),
544                }
545            }
546        ).sum();
547    }
548}
549
550impl<T:Hash+Eq+Clone,R:Semiring,A:?Sized+AlgebraRule<R,T>> MulAssign for ModuleString<R,T,A> {
551    fn mul_assign(&mut self, rhs:Self) {
552        *self = rhs.terms.into_iter().map(|(t, r)| self.clone() * (r,t)).sum();
553    }
554}
555
556impl<Z,R,T,A> Pow<Z> for ModuleString<R,T,A> where
557    Z:Natural,
558    T:Hash+Eq+Clone,
559    R:PartialEq+UnitalSemiring,
560    A:?Sized+UnitalAlgebraRule<R,T>+AssociativeAlgebraRule<R,T>
561{
562    type Output = Self;
563    fn pow(self, p:Z) -> Self { repeated_squaring(self, p) }
564}
free_algebra/module.rs

free_algebra/
module.rs
