algebraeon_rings/module/
ordered_set_free_module.rs

1use crate::structure::*;
2use algebraeon_sets::structure::*;
3use std::{borrow::Cow, marker::PhantomData};
4
5#[derive(Debug, Clone)]
6pub struct FreeModuleOverOrderedSetStructure<
7    Set: OrdSignature,
8    SetB: BorrowedStructure<Set>,
9    Ring: SemiRingSignature,
10    RingB: BorrowedStructure<Ring>,
11> {
12    _set: PhantomData<Set>,
13    set: SetB,
14    _ring: PhantomData<Ring>,
15    ring: RingB,
16}
17
18impl<
19    Set: OrdSignature,
20    SetB: BorrowedStructure<Set>,
21    Ring: SemiRingSignature,
22    RingB: BorrowedStructure<Ring>,
23> PartialEq for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
24{
25    fn eq(&self, other: &Self) -> bool {
26        self.set == other.set && self.ring == other.ring
27    }
28}
29
30impl<
31    Set: OrdSignature,
32    SetB: BorrowedStructure<Set>,
33    Ring: SemiRingSignature,
34    RingB: BorrowedStructure<Ring>,
35> Eq for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
36{
37}
38
39impl<
40    Set: OrdSignature,
41    SetB: BorrowedStructure<Set>,
42    Ring: SemiRingSignature + EqSignature,
43    RingB: BorrowedStructure<Ring>,
44> FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
45{
46    pub fn new(set: SetB, ring: RingB) -> Self {
47        Self {
48            _set: PhantomData,
49            set,
50            _ring: PhantomData,
51            ring,
52        }
53    }
54
55    pub fn set(&self) -> &Set {
56        self.set.borrow()
57    }
58
59    /// Input: vector of (Set, Ring)
60    /// Output: vector of (Set, Ring) which is
61    ///  - ordered
62    ///  - has no duplicate set elements
63    ///  - has no ring elements equal to 0
64    ///
65    /// and is equal to the sum of the input vectors terms. In other words, the returned vector will pass self.is_element(..)
66    pub fn collapse_terms(&self, v: <Self as SetSignature>::Set) -> <Self as SetSignature>::Set {
67        let mut v = self.set().sort_by_key(v, &|(x, _)| x).into_iter();
68
69        let mut current_x = None;
70        let mut current_a = self.ring().zero();
71
72        let mut w = vec![];
73        loop {
74            enum ItemResult<S, R> {
75                Same(R),
76                Change(S, R),
77                End,
78            }
79
80            let result = if let Some((x, a)) = v.next() {
81                if let Some(current_x) = current_x.as_ref() {
82                    if self.set().equal(current_x, &x) {
83                        ItemResult::Same(a)
84                    } else {
85                        ItemResult::Change(x, a)
86                    }
87                } else {
88                    current_x = Some(x);
89                    ItemResult::Same(a)
90                }
91            } else {
92                ItemResult::End
93            };
94
95            match result {
96                ItemResult::Same(a) => {
97                    self.ring().add_mut(&mut current_a, &a);
98                }
99                ItemResult::Change(x, a) => {
100                    w.push((current_x.unwrap(), current_a));
101                    current_x = Some(x);
102                    current_a = a;
103                }
104                ItemResult::End => {
105                    w.push((current_x.unwrap(), current_a));
106                    break;
107                }
108            }
109        }
110        let w = w
111            .into_iter()
112            .filter(|(_, a)| !self.ring().is_zero(a))
113            .collect();
114        debug_assert!(self.is_element(&w).is_ok());
115        w
116    }
117}
118
119impl<
120    Set: OrdSignature,
121    SetB: BorrowedStructure<Set>,
122    Ring: SemiRingSignature,
123    RingB: BorrowedStructure<Ring>,
124> Signature for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
125{
126}
127
128impl<
129    Set: OrdSignature,
130    SetB: BorrowedStructure<Set>,
131    Ring: SemiRingSignature + EqSignature,
132    RingB: BorrowedStructure<Ring>,
133> SetSignature for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
134{
135    // must be ordered and contain no duplicates wrt the first argument
136    // all ring elements in the second argument must be non-zero
137    type Set = Vec<(Set::Set, Ring::Set)>;
138
139    fn is_element(&self, v: &Self::Set) -> Result<(), String> {
140        if !self.set().is_sorted_and_unique_by_key(v, |(x, _)| x) {
141            return Err("not sorted or has duplicate".to_string());
142        }
143        for (_, a) in v {
144            if self.ring().is_zero(a) {
145                return Err("multiplicity zero".to_string());
146            }
147        }
148        Ok(())
149    }
150}
151
152impl<
153    Set: OrdSignature,
154    SetB: BorrowedStructure<Set>,
155    Ring: SemiRingSignature + EqSignature,
156    RingB: BorrowedStructure<Ring>,
157> EqSignature for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
158{
159    fn equal(&self, v: &Self::Set, w: &Self::Set) -> bool {
160        debug_assert!(self.is_element(v).is_ok());
161        debug_assert!(self.is_element(w).is_ok());
162        // since elements are sorted and exclude entries with zero coefficients, we just need to check if they are identically equal
163        let n = v.len();
164        if n != w.len() {
165            false
166        } else {
167            (0..n).all(|i| {
168                let (vx, va) = &v[i];
169                let (wx, wa) = &w[i];
170                self.set().equal(vx, wx) && self.ring().equal(va, wa)
171            })
172        }
173    }
174}
175
176impl<
177    Set: OrdSignature,
178    SetB: BorrowedStructure<Set>,
179    Ring: SemiRingSignature + EqSignature,
180    RingB: BorrowedStructure<Ring>,
181> RinglikeSpecializationSignature for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
182{
183}
184
185impl<
186    Set: OrdSignature,
187    SetB: BorrowedStructure<Set>,
188    Ring: SemiRingSignature + EqSignature,
189    RingB: BorrowedStructure<Ring>,
190> ZeroSignature for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
191{
192    fn zero(&self) -> Self::Set {
193        vec![]
194    }
195}
196
197impl<
198    Set: OrdSignature,
199    SetB: BorrowedStructure<Set>,
200    Ring: SemiRingSignature + EqSignature,
201    RingB: BorrowedStructure<Ring>,
202> AdditionSignature for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
203{
204    fn add(&self, v: &Self::Set, w: &Self::Set) -> Self::Set {
205        self.collapse_terms(v.iter().chain(w.iter()).cloned().collect())
206    }
207}
208
209impl<
210    Set: OrdSignature,
211    SetB: BorrowedStructure<Set>,
212    Ring: SemiRingSignature + EqSignature,
213    RingB: BorrowedStructure<Ring>,
214> CancellativeAdditionSignature for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
215{
216    fn try_sub(&self, _a: &Self::Set, _b: &Self::Set) -> Option<Self::Set> {
217        todo!()
218    }
219}
220
221impl<
222    Set: OrdSignature,
223    SetB: BorrowedStructure<Set>,
224    Ring: SemiRingSignature + EqSignature,
225    RingB: BorrowedStructure<Ring>,
226> TryNegateSignature for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
227{
228    fn try_neg(&self, v: &Self::Set) -> Option<Self::Set> {
229        v.iter()
230            .map(|(x, a)| Some((x.clone(), self.ring().try_neg(a)?)))
231            .collect::<Option<_>>()
232    }
233}
234
235impl<
236    Set: OrdSignature,
237    SetB: BorrowedStructure<Set>,
238    Ring: SemiRingSignature + EqSignature,
239    RingB: BorrowedStructure<Ring>,
240> AdditiveMonoidSignature for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
241{
242}
243
244impl<
245    Set: OrdSignature,
246    SetB: BorrowedStructure<Set>,
247    Ring: RingSignature + EqSignature,
248    RingB: BorrowedStructure<Ring>,
249> AdditiveGroupSignature for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
250{
251    fn neg(&self, v: &Self::Set) -> Self::Set {
252        v.iter()
253            .map(|(x, a)| (x.clone(), self.ring().neg(a)))
254            .collect()
255    }
256}
257
258impl<
259    Set: OrdSignature,
260    SetB: BorrowedStructure<Set>,
261    Ring: SemiRingSignature + EqSignature,
262    RingB: BorrowedStructure<Ring>,
263> SemiModuleSignature<Ring> for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
264{
265    fn ring(&self) -> &Ring {
266        self.ring.borrow()
267    }
268
269    fn scalar_mul(&self, v: &Self::Set, b: &Ring::Set) -> Self::Set {
270        v.iter()
271            .map(|(x, a)| (x.clone(), self.ring().mul(a, b)))
272            .filter(|(_, a)| !self.ring().is_zero(a))
273            .collect()
274    }
275}
276
277impl<
278    Set: OrdSignature,
279    SetB: BorrowedStructure<Set>,
280    Ring: RingSignature + EqSignature,
281    RingB: BorrowedStructure<Ring>,
282> FreeModuleSignature<Ring> for FreeModuleOverOrderedSetStructure<Set, SetB, Ring, RingB>
283{
284    type Basis = Set;
285
286    fn basis_set(&self) -> impl std::borrow::Borrow<Set> {
287        self.set()
288    }
289
290    fn to_component<'a>(&self, x: &Set::Set, v: &'a Self::Set) -> Cow<'a, Ring::Set> {
291        if let Some((_, a)) = self.set().binary_search_by_key(v, x, |(x, _)| x) {
292            Cow::Borrowed(a)
293        } else {
294            Cow::Owned(self.ring().zero())
295        }
296    }
297
298    fn from_component(&self, x: &Set::Set, a: &Ring::Set) -> Self::Set {
299        if self.ring().is_zero(a) {
300            vec![]
301        } else {
302            vec![(x.clone(), a.clone())]
303        }
304    }
305}
306
307#[cfg(test)]
308mod tests {
309    use algebraeon_nzq::{Integer, Natural};
310    use algebraeon_sets::structure::MetaType;
311
312    use super::FreeModuleOverOrderedSetStructure;
313
314    #[test]
315    fn test_ordered_set_free_module() {
316        let m = FreeModuleOverOrderedSetStructure::new(Natural::structure(), Integer::structure());
317
318        let v = vec![
319            (0u32.into(), 1.into()),
320            (1u32.into(), 1.into()),
321            (0u32.into(), (-1).into()),
322            (1u32.into(), 1.into()),
323        ];
324        let w = m.collapse_terms(v);
325        assert_eq!(w, vec![(1u32.into(), 2.into())]);
326    }
327}
algebraeon_rings/module/ordered_set_free_module.rs

algebraeon_rings/module/
ordered_set_free_module.rs
