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 chmax_max;
29pub mod chmin_min;
30pub mod update_fold;
31pub mod update_sum;
32
33pub mod semiring;
34
35#[cfg(test)]
36mod tests {
37    use super::traits::*;
38    use std::fmt::Debug;
39
40    fn associative_law<T, I>(a: I)
41    where
42        T: BinaryOp + Associative + Copy + PartialEq + Debug,
43        I: IntoIterator<Item = T>,
44    {
45        let a: Vec<_> = a.into_iter().collect();
46        for x in &a {
47            for y in &a {
48                for z in &a {
49                    let p = x.clone().op(y.clone().op(z.clone()));
50                    let q = (x.clone().op(y.clone())).op(z.clone());
51                    assert_eq!(p, q)
52                }
53            }
54        }
55    }
56
57    fn inverse_law<T, I>(a: I)
58    where
59        T: BinaryOp + Inverse + Identity + Copy + PartialEq + Debug,
60        I: IntoIterator<Item = T>,
61    {
62        for x in a {
63            assert_eq!(x.op(x.inv()), T::id());
64            assert_eq!(x.inv().op(x), T::id());
65        }
66    }
67
68    fn identity_law<T, I>(a: I)
69    where
70        T: BinaryOp + Identity + Copy + PartialEq + Debug,
71        I: IntoIterator<Item = T>,
72    {
73        for x in a {
74            assert_eq!(x.op(T::id()), x);
75            assert_eq!(T::id().op(x), x);
76        }
77    }
78
79    fn commutative_law<T, I>(a: I)
80    where
81        T: BinaryOp + Commutative + Copy + PartialEq + Debug,
82        I: IntoIterator<Item = T>,
83    {
84        let a: Vec<_> = a.into_iter().collect();
85        for x in &a {
86            for y in &a {
87                assert_eq!(x.op(*y), y.op(*x));
88            }
89        }
90    }
91
92    #[test]
93    fn test_dihedral() {
94        use crate::algebra::dihedral::*;
95
96        let k = 20;
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(a.clone());
103        inverse_law(a.clone());
104        identity_law(a);
105    }
106
107    #[test]
108    fn test_sum_modint() {
109        use crate::num::modint::{algebra::*, *};
110
111        let m: u32 = 73;
112        let ff = ModIntBuilder::new(m);
113        let a = (0..m as u64).map(|x| SumModM::new(ff.from_u64(x)));
114
115        associative_law(a.clone());
116        inverse_law(a.clone());
117        identity_law(a.clone());
118        commutative_law(a);
119    }
120
121    #[test]
122    fn test_prod_modint() {
123        use crate::num::modint::{algebra::*, *};
124
125        let m: u32 = 73;
126        let ff = ModIntBuilder::new(m);
127        let a = (0..m as u64).map(|x| ProdModM::new(ff.from_u64(x)));
128
129        associative_law(a.clone());
130        identity_law(a.clone());
131        commutative_law(a);
132    }
133}
haar_lib/algebra/mod.rs

haar_lib/algebra/
mod.rs
