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

haar_lib/algebra/
mod.rs
