yui_core/conc/poly/
mdeg.rs

1//! Multi-degree: a sparse map from variable index to exponent, used as the
2//! degree type of multivariate monomials.
3
4use std::cmp::Ordering;
5use std::collections::BTreeMap;
6use std::ops::{Add, AddAssign, Neg, SubAssign, Sub, Index};
7use std::hash::Hash;
8
9use auto_impl_ops::auto_ops;
10use delegate::delegate;
11use derive_more::{Display, Debug};
12use num_traits::Zero;
13
14use super::MonoOrd;
15
16/// Multi-degree of a monomial, stored sparsely as `{ variable_index → exponent }`.
17/// Zero exponents are elided.
18///
19/// Used as [`MultiVar`](super::MultiVar)'s degree type.
20#[derive(Clone, Default, PartialEq, Eq, Hash, Display, Debug)]
21#[display("{:?}", data)]
22#[debug("{:?}", data)]
23pub struct MultiDeg<I> {
24    data: BTreeMap<usize, I>, // { index => degree }
25    _zero: I
26}
27
28impl<I> MultiDeg<I>
29where I: Zero {
30    fn new_reduced(data: BTreeMap<usize, I>) -> Self {
31        Self { data, _zero: I::zero() }
32    }
33
34    fn reduce(&mut self) {
35        self.data.retain(|_, i| !i.is_zero())
36    }
37
38    pub(crate) fn empty() -> Self {
39        Self::new_reduced(BTreeMap::new())
40    }
41}
42
43impl<I> MultiDeg<I> {
44    delegate! {
45        to self.data {
46            #[call(len)]
47            pub fn ninds(&self) -> usize;
48            pub fn iter(&self) -> impl Iterator<Item = (&usize, &I)>;
49        }
50    }
51
52    pub fn indices(&self) -> impl Iterator<Item = &usize> {
53        self.data.keys()
54    }
55
56    pub fn min_index(&self) -> Option<usize> {
57        self.indices().min().cloned()
58    }
59
60    pub fn max_index(&self) -> Option<usize> {
61        self.indices().max().cloned()
62    }
63}
64
65impl<I> MultiDeg<I>
66where I: Zero + Ord {
67    pub fn all_leq(&self, other: &Self) -> bool {
68        self.iter().all(|(&i0, d0)| {
69            d0 <= &other[i0]
70        }) &&
71        other.iter().all(|(&i1, d1)|
72            &self[i1] <= d1
73        )
74    }
75
76    pub fn all_geq(&self, other: &Self) -> bool {
77        other.all_leq(self)
78    }
79}
80
81impl<I> MultiDeg<I>
82where I: Zero + for<'x> Add<&'x I, Output = I> {
83    pub fn total(&self) -> I {
84        self.iter().map(|(_, d)| d).fold(I::zero(), |res, d| res + d)
85    }
86}
87
88impl<I> From<(usize, I)> for MultiDeg<I>
89where I: Zero {
90    fn from(value: (usize, I)) -> Self {
91        MultiDeg::from_iter([value])
92    }
93}
94
95impl<I, const N: usize> From<[I; N]> for MultiDeg<I>
96where I: Zero {
97    fn from(degrees: [I; N]) -> Self {
98        Self::from_iter(degrees.into_iter().enumerate())
99    }
100}
101
102impl<I> FromIterator<(usize, I)> for MultiDeg<I>
103where I: Zero {
104    fn from_iter<T: IntoIterator<Item = (usize, I)>>(iter: T) -> Self {
105        let data = iter.into_iter().filter(|(_, v)| !v.is_zero()).collect();
106        Self::new_reduced(data)
107    }
108}
109
110impl<I> Index<usize> for MultiDeg<I> {
111    type Output = I;
112
113    fn index(&self, i: usize) -> &Self::Output {
114        self.data.get(&i).unwrap_or(&self._zero)
115    }
116}
117
118impl<I> Zero for MultiDeg<I>
119where I: Zero + for<'x> AddAssign<&'x I> {
120    fn zero() -> Self {
121        Self::empty()
122    }
123
124    fn is_zero(&self) -> bool {
125        self.data.is_empty()
126    }
127}
128
129#[auto_ops]
130impl<I> AddAssign<&MultiDeg<I>> for MultiDeg<I>
131where I: Zero + for<'x> AddAssign<&'x I> {
132    fn add_assign(&mut self, rhs: &MultiDeg<I>) {
133        let data = &mut self.data;
134        for (i, d) in rhs.iter() {
135            if !data.contains_key(i) {
136                data.insert(*i, I::zero());
137            }
138            let d_i = data.get_mut(i).unwrap();
139            d_i.add_assign(d);
140        }
141        self.reduce()
142    }
143}
144
145#[auto_ops]
146impl<I> SubAssign<&MultiDeg<I>> for MultiDeg<I>
147where I: Zero + for<'x> SubAssign<&'x I> {
148    fn sub_assign(&mut self, rhs: &MultiDeg<I>) {
149        let data = &mut self.data;
150        for (i, d) in rhs.iter() {
151            if !data.contains_key(i) {
152                data.insert(*i, I::zero());
153            }
154            let d_i = data.get_mut(i).unwrap();
155            d_i.sub_assign(d);
156        }
157        self.reduce()
158    }
159}
160
161impl<I> Neg for &MultiDeg<I>
162where I: Zero, for<'x> &'x I: Neg<Output = I> {
163    type Output = MultiDeg<I>;
164    fn neg(self) -> Self::Output {
165        let list = self.iter().map(|(&i, d)|
166            (i, -d)
167        ).collect();
168        MultiDeg::new_reduced(list)
169    }
170}
171
172impl<I> MonoOrd for MultiDeg<I>
173where I: Zero + Ord + for<'x> Add<&'x I, Output = I> {
174    fn cmp_lex(&self, other: &Self) -> std::cmp::Ordering {
175        let i0 = usize::min(self.min_index().unwrap_or(0), other.min_index().unwrap_or(0));
176        let i1 = usize::max(self.max_index().unwrap_or(0), other.max_index().unwrap_or(0));
177
178        (i0..=i1).fold(Ordering::Equal, |res, i| {
179            res.then_with(||
180                I::cmp(&self[i], &other[i])
181            )
182        })
183    }
184
185    fn cmp_grlex(&self, other: &Self) -> std::cmp::Ordering {
186        I::cmp(&self.total(), &other.total()).then_with(||
187            Self::cmp_lex(self, other)
188        )
189    }
190}
191
192impl<I> PartialOrd for MultiDeg<I>
193where I: Zero + Ord + for<'x> Add<&'x I, Output = I> {
194    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
195        Some(Self::cmp(self, other))
196    }
197}
198
199impl<I> Ord for MultiDeg<I>
200where I: Zero + Ord + for<'x> Add<&'x I, Output = I> {
201    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
202        Self::cmp_lex(self, other)
203    }
204}
205
206#[cfg(test)]
207mod tests {
208    use std::hash::BuildHasher;
209
210    use super::*;
211
212    #[test]
213    fn reduce() {
214        let data = BTreeMap::from_iter([(1, 0), (0, 1), (7, 0), (2, 3)]);
215        let mut d0 = MultiDeg{ data, _zero: 0 };
216
217        d0.reduce();
218
219        assert_eq!(d0.data, BTreeMap::from_iter([(0, 1), (2, 3)]));
220    }
221
222    #[test]
223    fn deg() {
224        let mdeg = MultiDeg::from_iter([(0, 1), (1, -2), (2, 3), (3, 0)]);
225        assert_eq!(mdeg[1], -2);
226        assert_eq!(mdeg[4], 0);
227    }
228
229    #[test]
230    fn eq() {
231        let d1 = MultiDeg::from_iter([(2, 3), (1, -2), (3, 0), (0, 1)]);
232        let d2 = MultiDeg::from_iter([(0, 1), (1, -2), (2, 3), (3, 0)]);
233        let d3 = MultiDeg::from_iter([(0, 1), (1, -2), (2, 3), (3, 1)]);
234        assert_eq!(d1, d2);
235        assert_ne!(d1, d3);
236    }
237
238    #[test]
239    fn hash() {
240        let d1 = MultiDeg::from_iter([(2, 3), (1, -2), (3, 0), (0, 1)]);
241        let d2 = MultiDeg::from_iter([(0, 1), (1, -2), (2, 3), (3, 0)]);
242        let d3 = MultiDeg::from_iter([(0, 1), (1, -2), (2, 3), (3, 1)]);
243
244        let state = std::collections::hash_map::RandomState::new();
245        let hash = |d: &MultiDeg<_>| state.hash_one(d);
246
247        assert_eq!(hash(&d1), hash(&d2));
248        assert_ne!(hash(&d1), hash(&d3));
249    }
250
251    #[test]
252    fn total() {
253        let mdeg = MultiDeg::from_iter([(0, 1), (1, -2), (2, 3), (3, 0)]);
254        assert_eq!(mdeg.total(), 2);
255    }
256
257    #[test]
258    fn cmp_lex() {
259        let d0 = MultiDeg::<isize>::from_iter([]);                // total: 0
260        let d1 = MultiDeg::from_iter([(0, 1), (1, -2), (2,  3)]); // total: 2
261        let d2 = MultiDeg::from_iter([(0, 1), (1,  2), (2,  3)]); // total: 6
262        let d3 = MultiDeg::from_iter([(0, 2), (1,  2), (2, -2)]); // total: 2
263
264        assert!(MultiDeg::cmp_lex(&d0, &d0).is_eq());
265        assert!(MultiDeg::cmp_lex(&d0, &d1).is_lt());
266        assert!(MultiDeg::cmp_lex(&d1, &d2).is_lt());
267        assert!(MultiDeg::cmp_lex(&d2, &d3).is_lt());
268    }
269
270    #[test]
271    fn cmp_grlex() {
272        let d0 = MultiDeg::<isize>::from_iter([]);                // total: 0
273        let d1 = MultiDeg::from_iter([(0, 1), (1, -2), (2,  3)]); // total: 2
274        let d2 = MultiDeg::from_iter([(0, 1), (1,  2), (2,  3)]); // total: 6
275        let d3 = MultiDeg::from_iter([(0, 2), (1,  2), (2, -2)]); // total: 2
276
277        assert!(MultiDeg::cmp_grlex(&d0, &d0).is_eq());
278        assert!(MultiDeg::cmp_grlex(&d0, &d1).is_lt());
279        assert!(MultiDeg::cmp_grlex(&d1, &d3).is_lt());
280        assert!(MultiDeg::cmp_grlex(&d3, &d2).is_lt());
281    }
282
283    #[test]
284    fn add() {
285        let d1 = MultiDeg::from_iter([(0, 1), (1, -2), (2, 3)]);
286        let d2 = MultiDeg::from_iter([(1, 3), (2, -3), (4, 5)]);
287        assert_eq!(d1 + d2, MultiDeg::from_iter([(0, 1), (1, 1), (4, 5)]))
288    }
289
290    #[test]
291    fn sub() {
292        let d1 = MultiDeg::from_iter([(0, 1), (1, -2), (2, 3)]);
293        let d2 = MultiDeg::from_iter([(1, 3), (2, -3), (4, 5)]);
294        assert_eq!(d1 - d2, MultiDeg::from_iter([(0, 1), (1, -5), (2, 6), (4, -5)]))
295    }
296
297    #[test]
298    fn sub_usize() {
299        let d1 = MultiDeg::<usize>::from_iter([(0, 1), (1, 2), (2, 3)]);
300        let d2 = MultiDeg::<usize>::from_iter([(1, 2), (2, 1)]);
301        assert_eq!(d1 - d2, MultiDeg::from_iter([(0, 1), (2, 2)]))
302    }
303
304    #[test]
305    #[should_panic]
306    fn sub_usize_panic() {
307        let d1 = MultiDeg::<usize>::from_iter([(0, 1), (1, 2), (2, 3)]);
308        let d2 = MultiDeg::<usize>::from_iter([(1, 3), (2, 1)]);
309        let _ = d1 - d2; // panic!
310    }
311}
yui_core/conc/poly/mdeg.rs

yui_core/conc/poly/
mdeg.rs
