yui_core/conc/poly/
mvar.rs

1//! Multivariate monomial in indexed variables `X₀^{d₀} X₁^{d₁} ⋯ Xₙ^{dₙ}`,
2//! with the base symbol `X` as a const generic and a [`MultiDeg`] holding
3//! the exponents. With `I = isize` it is a Laurent monomial.
4
5use std::fmt::{Display, Debug};
6use std::ops::{AddAssign, MulAssign, Mul, Div, DivAssign, SubAssign, Add};
7use std::str::FromStr;
8use num_traits::{Zero, One, Pow, ToPrimitive, FromPrimitive};
9use itertools::Itertools;
10use auto_impl_ops::auto_ops;
11
12use crate::abst::{MathType, IndexType};
13use crate::lc::LcKey;
14use crate::util::format::subscript;
15use crate::util::parse_err::ParseErr;
16use super::{Mono, MultiDeg, MonoOrd};
17use super::var::{fmt_mono, parse_mono_deg};
18
19/// A multivariate monomial in indexed variables `Xᵢ`, with exponents stored
20/// in a [`MultiDeg`]. The base symbol `X` is a const generic; the actual
21/// variables are `X₀, X₁, …` (displayed with subscripts).
22#[derive(Clone, PartialEq, Eq, Hash, Default)]
23#[cfg_attr(feature = "serde", derive(serde_with::DeserializeFromStr))]
24pub struct MultiVar<const X: char, I> (
25    MultiDeg<I>
26);
27
28impl<const X: char, I> MultiVar<X, I> {
29    pub fn var_symbol() -> char {
30        X
31    }
32
33    pub fn deg_for(&self, i: usize) -> I
34    where I: Copy {
35        self.0[i]
36    }
37
38    pub fn total_deg(&self) -> I
39    where I: Zero + for<'x> Add<&'x I, Output = I> {
40        self.0.total()
41    }
42
43    pub fn eval<R>(&self, v: &[R]) -> R
44    where R: One + Mul<Output = R>, I: Copy, for<'x> &'x R: Pow<I, Output = R> {
45        assert!(v.len() >= self.0.ninds());
46        self.0.iter().fold(R::one(), |acc, (&i, &d)| acc * v[i].pow(d))
47    }
48
49    fn to_string_u(&self, unicode: bool) -> String
50    where I: ToPrimitive {
51        let seq = self.0.iter().map(|(&i, d)| {
52            let x = if unicode {
53                format!("{X}{}", subscript(i))
54            } else {
55                format!("{X}_{}", i)
56            };
57            (x, d)
58        });
59        fmt_mono_n(seq, unicode)
60    }
61}
62
63impl<const X: char, I> From<MultiDeg<I>> for MultiVar<X, I> {
64    fn from(d: MultiDeg<I>) -> Self {
65        Self(d)
66    }
67}
68
69impl<const X: char, I> From<(usize, I)> for MultiVar<X, I>
70where I: Zero {
71    fn from(value: (usize, I)) -> Self {
72        Self::from_iter([value])
73    }
74}
75
76impl<const X: char, const N: usize, I> From<[I; N]> for MultiVar<X, I>
77where I: Zero {
78    fn from(degs: [I; N]) -> Self {
79        Self::from(MultiDeg::from(degs))
80    }
81}
82
83impl<const X: char, I> FromIterator<(usize, I)> for MultiVar<X, I>
84where I: Zero {
85    fn from_iter<T: IntoIterator<Item = (usize, I)>>(iter: T) -> Self {
86        Self::from(MultiDeg::from_iter(iter))
87    }
88}
89
90impl<const X: char, I> FromStr for MultiVar<X, I>
91where I: Zero + FromStr + FromPrimitive {
92    type Err = ParseErr;
93    fn from_str(s: &str) -> Result<Self, Self::Err> {
94        use regex::Regex;
95
96        if s == "1" {
97            return Ok(MultiVar::from(MultiDeg::empty()))
98        }
99
100        // TODO must support braced indices.
101
102        let p = format!(r"({X}_([0-9]+))(\^\{{?-?[0-9]+\}}?)?");
103        let p_all = format!(r"^({p}\s?)+$");
104
105        if !Regex::new(&p_all).unwrap().is_match(s) {
106            return Err(ParseErr::invalid(s, &format!("a monomial in {X}_i")))
107        }
108
109        let r = Regex::new(&p).unwrap();
110        let mut degs = vec![];
111
112        for c in r.captures_iter(s) {
113            let x = &c[1];
114            let i = usize::from_str(&c[2]).map_err(|e|
115                ParseErr::new(format!("bad index in \"{s}\": {e}"))
116            )?;
117            let d = parse_mono_deg(x, &c[0]).ok_or_else(||
118                ParseErr::invalid(s, &format!("a monomial in {X}_i"))
119            )?;
120            degs.push((i, d));
121        };
122
123        let mvar = MultiVar::from_iter(degs);
124        Ok(mvar)
125    }
126}
127
128// note: clippy flags the `+`/`-` below, but exponents add on × and subtract on ÷.
129// `#[allow]` doesn't help: `#[auto_ops]` regenerates these impls and drops it.
130#[auto_ops]
131impl<const X: char, I> MulAssign<&MultiVar<X, I>> for MultiVar<X, I>
132where I: Zero + for<'x> AddAssign<&'x I> {
133    fn mul_assign(&mut self, rhs: &MultiVar<X, I>) {
134        self.0 += &rhs.0 // x^i * x^j = x^{i+j}
135    }
136}
137
138#[auto_ops]
139impl<const X: char, I> DivAssign<&MultiVar<X, I>> for MultiVar<X, I>
140where I: Zero + for<'x> SubAssign<&'x I> {
141    fn div_assign(&mut self, rhs: &MultiVar<X, I>) {
142        self.0 -= &rhs.0 // x^i / x^j = x^{i-j}
143    }
144}
145
146impl<const X: char, I> One for MultiVar<X, I>
147where I: Zero + for<'x> AddAssign<&'x I> {
148    fn one() -> Self {
149        Self::from(MultiDeg::zero()) // x^0 = 1.
150    }
151}
152
153impl<const X: char, I> Display for MultiVar<X, I>
154where I: ToPrimitive {
155    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
156        let s = self.to_string_u(true);
157        f.write_str(&s)
158    }
159}
160
161impl<const X: char, I> Debug for MultiVar<X, I>
162where I: ToPrimitive {
163    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
164        Display::fmt(self, f)
165    }
166}
167
168impl<const X: char, I> MonoOrd for MultiVar<X, I>
169where I: Zero + Ord + for<'x> Add<&'x I, Output = I> {
170    fn cmp_lex(&self, other: &Self) -> std::cmp::Ordering {
171        MultiDeg::cmp_lex(&self.0, &other.0)
172    }
173
174    fn cmp_grlex(&self, other: &Self) -> std::cmp::Ordering {
175        MultiDeg::cmp_grlex(&self.0, &other.0)
176    }
177}
178
179impl<const X: char, I> PartialOrd for MultiVar<X, I>
180where I: Zero + Ord + for<'x> Add<&'x I, Output = I> {
181    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
182        Some(Self::cmp(self, other))
183    }
184}
185
186impl<const X: char, I> Ord for MultiVar<X, I>
187where I: Zero + Ord + for<'x> Add<&'x I, Output = I> {
188    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
189        Self::cmp_lex(self, other)
190    }
191}
192
193
194#[cfg(feature = "serde")]
195impl<const X: char, I> serde::Serialize for MultiVar<X, I>
196where I: ToPrimitive {
197    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
198    where S: serde::Serializer {
199        serializer.serialize_str(&self.to_string_u(false))
200    }
201}
202
203impl<const X: char, I> MathType for MultiVar<X, I>
204where I: IndexType + ToPrimitive {
205    fn math_symbol() -> String {
206        format!("{X}")
207    }
208}
209
210impl<const X: char, I> LcKey for MultiVar<X, I>
211where I: IndexType + Zero + ToPrimitive + for<'x> Add<&'x I, Output = I> {}
212
213macro_rules! impl_multivar_unsigned {
214    ($I:ty) => {
215        impl<const X: char> Mono for MultiVar<X, $I> {
216            type Deg = MultiDeg<$I>;
217
218            fn deg(&self) -> Self::Deg {
219                self.0.clone()
220            }
221
222            fn is_unit(&self) -> bool {
223                self.0.is_zero()
224            }
225
226            fn inv(&self) -> Option<Self> {
227                if self.is_unit() {
228                    Some(Self(MultiDeg::zero()))
229                } else {
230                    None
231                }
232            }
233
234            fn divides(&self, other: &Self) -> bool {
235                self.0.all_leq(&other.0)
236            }
237        }
238
239        impl<const X: char> MultiVar<X, $I> {
240            pub fn generate(n: usize, tot_deg: usize) -> impl Iterator<Item = Self> {
241                use dinglebit_combinatorics::Combination as C;
242                use crate::algo::rep_comb;
243
244                // MEMO:
245                // Mathematically this restriction is unnecessary,
246                // but (n, tot_deg) = (0, 0) will fail.
247                assert!(n > 0);
248
249                let c = C::new(n + tot_deg - 1, n - 1);
250                c.into_iter().map(move |mut list| {
251                    list.push(n + tot_deg - 1); // the right-end wall
252                    Self::from_iter( rep_comb(&list) )
253                })
254            }
255        }
256    };
257}
258
259macro_rules! impl_multivar_signed {
260    ($I:ty) => {
261        impl<const X: char> Mono for MultiVar<X, $I> {
262            type Deg = MultiDeg<$I>;
263
264            fn deg(&self) -> Self::Deg {
265                self.0.clone()
266            }
267
268            fn is_unit(&self) -> bool {
269                true
270            }
271
272            fn inv(&self) -> Option<Self> { // (x^i)^{-1} = x^{-i}
273                Some(Self(-&self.0))
274            }
275
276            fn divides(&self, _other: &Self) -> bool {
277                true
278            }
279        }
280    };
281}
282
283impl_multivar_unsigned!(usize);
284impl_multivar_signed!  (isize);
285
286pub(crate) fn fmt_mono_n<'a, X, I, S>(seq: S, unicode: bool) -> String
287where X: ToString, I: 'a + ToPrimitive, S: IntoIterator<Item = (X, &'a I)> {
288    let s = seq.into_iter().map(|(x, d)| {
289        let m = fmt_mono(&x.to_string(), d, unicode);
290        if m == "1" {
291            "".to_string()
292        } else {
293            m
294        }
295    }).join("");
296
297    if s.is_empty() {
298        "1".to_string()
299    } else {
300        s
301    }
302}
303
304mod tex {
305    use crate::util::tex::TeX;
306    use super::*;
307
308    impl<const X: char, I> TeX for MultiVar<X, I>
309    where I: ToPrimitive {
310        fn tex_math_symbol() -> String {
311            format!("{X}_1,\\ldots")
312        }
313        fn tex_string(&self) -> String {
314            self.to_string_u(false)
315        }
316    }
317}
318
319#[cfg(test)]
320mod tests {
321    use itertools::Itertools;
322    use num_integer::binomial;
323
324    use super::*;
325
326    #[test]
327    fn display() {
328        type M = MultiVar<'X', usize>;
329
330        assert_eq!(format!("{}", M::from([])), "1");
331        assert_eq!(format!("{}", M::from([0])), "1");
332        assert_eq!(format!("{}", M::from([1])), "X₀");
333        assert_eq!(format!("{}", M::from([3])), "X₀³");
334        assert_eq!(format!("{}", M::from([1,0,3])), "X₀X₂³");
335    }
336
337    #[test]
338    fn from_pair() {
339        type M = MultiVar<'X', usize>;
340
341        let d = M::from((2, 3)); // X₂³
342        assert_eq!(d.0, MultiDeg::from_iter([(2, 3)]));
343    }
344
345    #[test]
346    fn from_arr() {
347        type M = MultiVar<'X', usize>;
348
349        let d = M::from([1,0,3]); // X₀X₂³
350        assert_eq!(d.0, MultiDeg::from_iter([(0, 1), (2, 3)]));
351    }
352
353    #[test]
354    fn from_iter() {
355        type M = MultiVar<'X', usize>;
356
357        let d = M::from_iter([(0, 1), (2, 3)]); // X₀X₂³
358        assert_eq!(d.0, MultiDeg::from_iter([(0, 1), (2, 3)]));
359    }
360
361    #[test]
362    fn deg_for() {
363        type M = MultiVar<'X', usize>;
364
365        let d = M::from([1,0,3]); // X₀X₂³
366        assert_eq!(d.deg_for(0), 1);
367        assert_eq!(d.deg_for(1), 0);
368        assert_eq!(d.deg_for(2), 3);
369        assert_eq!(d.deg_for(3), 0);
370    }
371
372    #[test]
373    fn total_deg() {
374        type M = MultiVar<'X', usize>;
375
376        let d = M::from([1,0,3]); // X₀X₂³
377        assert_eq!(d.total_deg(), 4);
378    }
379
380    #[test]
381    fn eval() {
382        type M = MultiVar<'X', usize>;
383        let v = [2, 3, 5];
384
385        assert_eq!(M::from([]).eval::<i32>(&v), 1);
386        assert_eq!(M::from([1]).eval::<i32>(&v), 2);
387        assert_eq!(M::from([0, 1]).eval::<i32>(&v), 3);
388        assert_eq!(M::from([2, 3]).eval::<i32>(&v), 4 * 27);
389        assert_eq!(M::from([1, 0, 3]).eval::<i32>(&v), 2 * 125);
390    }
391
392    #[test]
393    fn eval_f2() {
394        use crate::num::FF2;
395
396        type M = MultiVar<'X', usize>;
397        let v = [FF2::from(2), FF2::from(3), FF2::from(5)];
398
399        assert_eq!(M::from([]).eval::<FF2>(&v), FF2::from(1));
400        assert_eq!(M::from([1]).eval::<FF2>(&v), FF2::from(0));
401        assert_eq!(M::from([0, 1]).eval::<FF2>(&v), FF2::from(1));
402        assert_eq!(M::from([2, 3]).eval::<FF2>(&v), FF2::from(0));
403        assert_eq!(M::from([1, 0, 3]).eval::<FF2>(&v), FF2::from(0));
404    }
405
406    #[test]
407    fn is_divisible() {
408        type M = MultiVar<'X', usize>;
409
410        let one = M::from([]);
411        let d1 = M::from([1,2,3]);
412        let d2 = M::from([0,2,1]);
413        let d3 = M::from([1,3,0]);
414
415        assert!(one.divides(&d1));
416        assert!(d1.divides(&d1));
417        assert!(d2.divides(&d1));
418        assert!(!d1.divides(&d2));
419        assert!(!d3.divides(&d1));
420        assert!(!d1.divides(&d3));
421    }
422
423    #[test]
424    fn div() {
425        type M = MultiVar<'X', usize>;
426
427        let one = M::from([]);
428        let d1 = M::from([1,2,3]);
429        let d2 = M::from([0,2,1]);
430
431        assert_eq!(&d1 / &one, d1);
432        assert_eq!(&d1 / &d1, M::from([]));
433        assert_eq!(&d1 / &d2, M::from([1,0,2]));
434    }
435
436    #[test]
437    fn is_divisible_isize() {
438        type M = MultiVar<'X', isize>;
439
440        let one = M::from([]);
441        let d1 = M::from([1,2,3]);
442        let d2 = M::from([0,2,1]);
443        let d3 = M::from([1,3]);
444
445        assert!(one.divides(&d1));
446        assert!(d1.divides(&d1));
447        assert!(d2.divides(&d1));
448        assert!(d1.divides(&d2));
449        assert!(d3.divides(&d1));
450        assert!(d1.divides(&d3));
451    }
452
453    #[test]
454    fn div_isize() {
455        type M = MultiVar<'X', isize>;
456
457        let one = M::from([]);
458        let d1 = M::from([1,2,3]);
459        let d2 = M::from([0,2,1]);
460
461        assert_eq!(&d1 / &one, d1);
462        assert_eq!(&one / &d1, d1.inv().unwrap());
463        assert_eq!(&d1 / &d2, M::from([1,0,2]));
464        assert_eq!(&d2 / &d1, M::from([-1,0,-2]));
465    }
466
467    #[test]
468    fn gen_mons() {
469        type M = MultiVar<'X', usize>;
470
471        let n = 3;
472        let tot = 5;
473        let mons = M::generate(n, tot).collect_vec();
474
475        assert_eq!(mons.len(), binomial(n + tot - 1, n - 1));
476        assert!(mons.iter().all(|x| x.total_deg() == tot));
477        assert!(mons.iter().all_unique());
478
479        assert_eq!(M::generate(n, 0).collect_vec(), vec![M::one()]); // deg(1) = 0, using n-vars.
480    }
481
482    #[test]
483    fn from_str() {
484        type M = MultiVar<'X', isize>;
485
486        let s = "1";
487        assert_eq!(M::from_str(s), Ok(M::one()));
488
489        let s = "X_0";
490        assert_eq!(M::from_str(s), Ok(M::from((0, 1))));
491
492        let s = "X_1";
493        assert_eq!(M::from_str(s), Ok(M::from((1, 1))));
494
495        let s = "X_1^2";
496        assert_eq!(M::from_str(s), Ok(M::from((1, 2))));
497
498        let s = "X_0X_2^3";
499        assert_eq!(M::from_str(s), Ok(M::from_iter([(0, 1), (2, 3)])));
500
501        let s = "X_0^{-1}";
502        assert_eq!(M::from_str(s), Ok(M::from((0, -1))));
503
504        let s = "X_0^{-1}X_2^{12}";
505        assert_eq!(M::from_str(s), Ok(M::from_iter([(0, -1), (2, 12)])));
506
507        let s = "2";
508        assert!(M::from_str(s).is_err());
509
510        let s = "Y_0";
511        assert!(M::from_str(s).is_err());
512
513        // unbraced, beyond one digit: the term must not be dropped
514        let s = "X_0^23";
515        assert_eq!(M::from_str(s), Ok(M::from((0, 23))));
516
517        let s = "X_0^5 X_1^23";
518        assert_eq!(M::from_str(s), Ok(M::from_iter([(0, 5), (1, 23)])));
519    }
520
521    #[test]
522    #[cfg(feature = "serde")]
523    fn serialize() {
524        type M = MultiVar<'X', isize>;
525
526        let d = M::from([]);
527        let ser = serde_json::to_string(&d).unwrap();
528        let des = serde_json::from_str::<M>(&ser).unwrap();
529
530        assert_eq!(&ser, "\"1\"");
531        assert_eq!(d, des);
532
533        let d = M::from([1]);
534        let ser = serde_json::to_string(&d).unwrap();
535        let des = serde_json::from_str::<M>(&ser).unwrap();
536
537        assert_eq!(&ser, "\"X_0\"");
538        assert_eq!(d, des);
539
540        let d = M::from([2]);
541        let ser = serde_json::to_string(&d).unwrap();
542        let des = serde_json::from_str::<M>(&ser).unwrap();
543
544        assert_eq!(&ser, "\"X_0^2\"");
545        assert_eq!(d, des);
546
547        let d = M::from([-1, 0, 3]);
548        let ser = serde_json::to_string(&d).unwrap();
549        let des = serde_json::from_str::<M>(&ser).unwrap();
550
551        assert_eq!(&ser, "\"X_0^{-1}X_2^3\"");
552        assert_eq!(d, des);
553    }
554}
yui_core/conc/poly/mvar.rs

yui_core/conc/poly/
mvar.rs
