competitive/algebra/
magma.rs

1//! algebraic traits
2
3/// binary operaion: $T \circ T \to T$
4pub trait Magma {
5    /// type of operands: $T$
6    type T: Clone;
7    /// binary operaion: $\circ$
8    fn operate(x: &Self::T, y: &Self::T) -> Self::T;
9    #[inline]
10    fn reverse_operate(x: &Self::T, y: &Self::T) -> Self::T {
11        Self::operate(y, x)
12    }
13    #[inline]
14    fn operate_assign(x: &mut Self::T, y: &Self::T) {
15        *x = Self::operate(x, y);
16    }
17}
18
19/// $\forall a,\forall b,\forall c \in T, (a \circ b) \circ c = a \circ (b \circ c)$
20pub trait Associative {}
21
22/// associative binary operation
23pub trait SemiGroup: Magma + Associative {}
24
25impl<S> SemiGroup for S where S: Magma + Associative {}
26
27/// $\exists e \in T, \forall a \in T, e \circ a = a \circ e = e$
28pub trait Unital: Magma {
29    /// identity element: $e$
30    fn unit() -> Self::T;
31    #[inline]
32    fn is_unit(x: &Self::T) -> bool
33    where
34        <Self as Magma>::T: PartialEq,
35    {
36        x == &Self::unit()
37    }
38    #[inline]
39    fn set_unit(x: &mut Self::T) {
40        *x = Self::unit();
41    }
42}
43
44pub trait ExpBits {
45    type Iter: Iterator<Item = bool>;
46    fn bits(self) -> Self::Iter;
47}
48
49pub trait SignedExpBits {
50    type T: ExpBits;
51
52    fn neg_and_bits(self) -> (bool, Self::T);
53}
54
55pub struct Bits<T> {
56    n: T,
57}
58
59macro_rules! impl_exp_bits_for_uint {
60    ($($t:ty)*) => {
61        $(
62            impl Iterator for Bits<$t> {
63                type Item = bool;
64                fn next(&mut self) -> Option<bool> {
65                    if self.n == 0 {
66                        None
67                    } else {
68                        let bit = (self.n & 1) == 1;
69                        self.n >>= 1;
70                        Some(bit)
71                    }
72                }
73            }
74            impl ExpBits for $t {
75                type Iter = Bits<$t>;
76                fn bits(self) -> Self::Iter {
77                    Bits { n: self }
78                }
79            }
80            impl SignedExpBits for $t {
81                type T = $t;
82                fn neg_and_bits(self) -> (bool, Self::T) {
83                    (false, self)
84                }
85            }
86        )*
87    };
88}
89impl_exp_bits_for_uint!(u8 u16 u32 u64 u128 usize);
90
91macro_rules! impl_signed_exp_bits_for_sint {
92    ($($s:ty, $u:ty;)*) => {
93        $(
94            impl SignedExpBits for $s {
95                type T = $u;
96                fn neg_and_bits(self) -> (bool, Self::T) {
97                    (self < 0, self.unsigned_abs())
98                }
99            }
100        )*
101    };
102}
103impl_signed_exp_bits_for_sint!(i8, u8; i16, u16; i32, u32; i64, u64; i128, u128; isize, usize;);
104
105/// associative binary operation and an identity element
106pub trait Monoid: SemiGroup + Unital {
107    /// binary exponentiation: $x^n = x\circ\ddots\circ x$
108    fn pow<E>(mut x: Self::T, exp: E) -> Self::T
109    where
110        E: ExpBits,
111    {
112        let mut res = Self::unit();
113        for bit in exp.bits() {
114            if bit {
115                res = Self::operate(&res, &x);
116            }
117            x = Self::operate(&x, &x);
118        }
119        res
120    }
121
122    fn fold<I>(iter: I) -> Self::T
123    where
124        I: IntoIterator<Item = Self::T>,
125    {
126        let mut iter = iter.into_iter();
127        if let Some(item) = iter.next() {
128            iter.fold(item, |acc, x| Self::operate(&acc, &x))
129        } else {
130            Self::unit()
131        }
132    }
133}
134
135impl<M> Monoid for M where M: SemiGroup + Unital {}
136
137/// $\exists e \in T, \forall a \in T, \exists b,c \in T, b \circ a = a \circ c = e$
138pub trait Invertible: Magma {
139    /// $a$ where $a \circ x = e$
140    fn inverse(x: &Self::T) -> Self::T;
141    #[inline]
142    fn rinv_operate(x: &Self::T, y: &Self::T) -> Self::T {
143        Self::operate(x, &Self::inverse(y))
144    }
145    #[inline]
146    fn rinv_operate_assign(x: &mut Self::T, y: &Self::T) {
147        *x = Self::rinv_operate(x, y);
148    }
149}
150
151/// associative binary operation and an identity element and inverse elements
152pub trait Group: Monoid + Invertible {
153    fn signed_pow<E>(x: Self::T, exp: E) -> Self::T
154    where
155        E: SignedExpBits,
156    {
157        let (neg, exp) = E::neg_and_bits(exp);
158        let res = Self::pow(x, exp);
159        if neg { Self::inverse(&res) } else { res }
160    }
161}
162
163impl<G> Group for G where G: Monoid + Invertible {}
164
165/// $\forall a,\forall b \in T, a \circ b = b \circ a$
166pub trait Commutative {}
167
168/// commutative monoid
169pub trait AbelianMonoid: Monoid + Commutative {}
170
171impl<M> AbelianMonoid for M where M: Monoid + Commutative {}
172
173/// commutative group
174pub trait AbelianGroup: Group + Commutative {}
175
176impl<G> AbelianGroup for G where G: Group + Commutative {}
177
178/// $\forall a \in T, a \circ a = a$
179pub trait Idempotent {}
180
181/// idempotent monoid
182pub trait IdempotentMonoid: Monoid + Idempotent {}
183
184impl<M> IdempotentMonoid for M where M: Monoid + Idempotent {}
185
186#[macro_export]
187macro_rules! monoid_fold {
188    ($m:ty) => { <$m as Unital>::unit() };
189    ($m:ty,) => { <$m as Unital>::unit() };
190    ($m:ty, $f:expr) => { $f };
191    ($m:ty, $f:expr, $($ff:expr),*) => { <$m as Magma>::operate(&($f), &monoid_fold!($m, $($ff),*)) };
192}
193
194#[macro_export]
195macro_rules! define_monoid {
196    ($Name:ident, $t:ty, |$x:ident, $y:ident| $op:expr, $unit:expr) => {
197        struct $Name;
198        impl Magma for $Name {
199            type T = $t;
200            fn operate($x: &Self::T, $y: &Self::T) -> Self::T {
201                $op
202            }
203        }
204        impl Unital for $Name {
205            fn unit() -> Self::T {
206                $unit
207            }
208        }
209        impl Associative for $Name {}
210    };
211}
212
213#[cfg(test)]
214mod tests {
215    use super::*;
216    use crate::{
217        algebra::operations::{AdditiveOperation, MaxOperation},
218        monoid_fold,
219    };
220
221    #[test]
222    fn test_monoid_pow() {
223        assert_eq!(AdditiveOperation::pow(2, 0u32), 0);
224        assert_eq!(AdditiveOperation::pow(2, 1u32), 2);
225        assert_eq!(AdditiveOperation::pow(2, 3u32), 6);
226        assert_eq!(AdditiveOperation::pow(2, 4usize), 8);
227    }
228
229    #[test]
230    #[allow(clippy::eq_op)]
231    fn test_monoid_fold() {
232        assert_eq!(monoid_fold!(MaxOperation<u32>,), 0);
233        assert_eq!(monoid_fold!(MaxOperation<u32>, 1), 1);
234        assert_eq!(monoid_fold!(MaxOperation<u32>, 1, 2), 2);
235        assert_eq!(monoid_fold!(MaxOperation<u32>, 0, 1, 5, 2), 5);
236    }
237}
competitive/algebra/magma.rs

competitive/algebra/
magma.rs
