haar_lib/algebra/
mod.rs

1//! 代数的構造
2
3pub mod traits;
4
5pub mod affine;
6pub mod bit;
7pub mod dihedral;
8pub mod dual;
9pub mod first_last;
10pub mod max_contiguous;
11pub mod max_contiguous_true;
12pub mod max_partial_sum;
13pub mod min_count;
14pub mod min_max;
15pub mod option;
16pub mod permutation;
17pub mod prod;
18pub mod sum;
19pub mod transform;
20pub mod trivial;
21pub mod tuple;
22
23pub mod action;
24
25pub mod add_min_count;
26pub mod add_sum;
27pub mod affine_sum;
28pub mod update_fold;
29pub mod update_sum;
30
31pub mod semiring;
32
33#[cfg(test)]
34mod tests {
35    use super::traits::*;
36    use std::fmt::Debug;
37
38    fn associative_law<T, I>(a: I)
39    where
40        T: BinaryOp + Associative + Copy + PartialEq + Debug,
41        I: IntoIterator<Item = T>,
42    {
43        let a: Vec<_> = a.into_iter().collect();
44        for x in &a {
45            for y in &a {
46                for z in &a {
47                    let p = x.clone().op(y.clone().op(z.clone()));
48                    let q = (x.clone().op(y.clone())).op(z.clone());
49                    assert_eq!(p, q)
50                }
51            }
52        }
53    }
54
55    fn inverse_law<T, I>(a: I)
56    where
57        T: BinaryOp + Inverse + Identity + Copy + PartialEq + Debug,
58        I: IntoIterator<Item = T>,
59    {
60        for x in a {
61            assert_eq!(x.op(x.inv()), T::id());
62            assert_eq!(x.inv().op(x), T::id());
63        }
64    }
65
66    fn identity_law<T, I>(a: I)
67    where
68        T: BinaryOp + Identity + Copy + PartialEq + Debug,
69        I: IntoIterator<Item = T>,
70    {
71        for x in a {
72            assert_eq!(x.op(T::id()), x);
73            assert_eq!(T::id().op(x), x);
74        }
75    }
76
77    fn commutative_law<T, I>(a: I)
78    where
79        T: BinaryOp + Commutative + Copy + PartialEq + Debug,
80        I: IntoIterator<Item = T>,
81    {
82        let a: Vec<_> = a.into_iter().collect();
83        for x in &a {
84            for y in &a {
85                assert_eq!(x.op(*y), y.op(*x));
86            }
87        }
88    }
89
90    #[test]
91    fn test_dihedral() {
92        use crate::algebra::dihedral::*;
93
94        let k = 20;
95
96        let a = (0..k)
97            .map(|i| Dihedral::r(i, k))
98            .chain((0..k).map(|i| Dihedral::s(i, k)));
99
100        associative_law(a.clone());
101        inverse_law(a.clone());
102        identity_law(a);
103    }
104
105    #[test]
106    fn test_sum_modint() {
107        use crate::num::modint::{algebra::*, *};
108
109        let m: u32 = 73;
110        let ff = ModIntBuilder::new(m);
111        let a = (0..m as u64).map(|x| SumModM::new(ff.from_u64(x)));
112
113        associative_law(a.clone());
114        inverse_law(a.clone());
115        identity_law(a.clone());
116        commutative_law(a);
117    }
118
119    #[test]
120    fn test_prod_modint() {
121        use crate::num::modint::{algebra::*, *};
122
123        let m: u32 = 73;
124        let ff = ModIntBuilder::new(m);
125        let a = (0..m as u64).map(|x| ProdModM::new(ff.from_u64(x)));
126
127        associative_law(a.clone());
128        identity_law(a.clone());
129        commutative_law(a);
130    }
131}
haar_lib/algebra/mod.rs

haar_lib/algebra/
mod.rs
