prcn_lib/
monoid.rs

1use num::{Bounded, Integer, One, Zero};
2use std::ops::{Add, BitAnd, BitOr, BitXor, Mul, Sub};
3
4/// 単位元が定義される `T -> T -> T`型の演算
5pub trait Monoid: Sized {
6    fn identity() -> Self;
7
8    fn op(x: &Self, y: &Self) -> Self;
9
10    fn fold(v: &[Self]) -> Self {
11        v.iter().fold(Self::identity(), |a, b| Self::op(&a, b))
12    }
13}
14
15/// 一行目にモノイド名、
16/// 二行目に単位元
17/// 三行目に`x`と`y`を引数に取って、同じ型の演算結果を返すクロージャを渡す
18#[macro_export]
19macro_rules! monoid_def {
20    {
21        $M:ident<$t:ty>,
22        $id:expr,
23        $me:expr
24    } => {
25        #[derive(Debug, Clone, Copy)]
26        pub struct $M($t);
27
28        impl Monoid for $M {
29            fn identity() -> Self {
30                $M($id)
31            }
32
33            fn op(x: &Self, y: &Self) -> Self {
34                let f = $me;
35                $M(f(x.0, y.0))
36            }
37        }
38    };
39}
40
41/// 区間和
42#[derive(Clone, Copy, Debug)]
43pub struct Sum<T: Clone + Copy>(T);
44
45impl<T: Clone + Copy + Zero + Add<Output = T>> Monoid for Sum<T> {
46    fn identity() -> Self {
47        Self(T::zero())
48    }
49    fn op(x: &Self, y: &Self) -> Self {
50        Self(x.0.clone() + y.0.clone())
51    }
52}
53
54impl<T: Copy> From<T> for Sum<T> {
55    fn from(x: T) -> Self {
56        Sum(x)
57    }
58}
59
60/// 区間積
61#[derive(Clone, Copy, Debug)]
62pub struct Product<T>(T);
63
64impl<T: Clone + Copy + One + Mul<Output = T>> Monoid for Product<T> {
65    fn identity() -> Self {
66        Self(T::one())
67    }
68    fn op(x: &Self, y: &Self) -> Self {
69        Self(x.0.clone() * y.0.clone())
70    }
71}
72
73impl<T> From<T> for Product<T> {
74    fn from(x: T) -> Self {
75        Product(x)
76    }
77}
78
79#[derive(Debug, Copy, Clone)]
80pub struct Max<T>(T);
81
82impl<T: Copy + Clone + Bounded + Ord> Monoid for Max<T> {
83    fn identity() -> Self {
84        Max(T::min_value())
85    }
86    fn op(x: &Self, y: &Self) -> Self {
87        Max(x.0.max(y.0))
88    }
89}
90
91impl<T> From<T> for Max<T> {
92    fn from(x: T) -> Self {
93        Max(x)
94    }
95}
96
97#[derive(Debug, Copy, Clone)]
98pub struct Min<T>(T);
99
100impl<T: Copy + Clone + Bounded + Ord> Monoid for Min<T> {
101    fn identity() -> Self {
102        Min(T::max_value())
103    }
104    fn op(x: &Self, y: &Self) -> Self {
105        Min(x.0.min(y.0))
106    }
107}
108
109impl<T> From<T> for Min<T> {
110    fn from(x: T) -> Self {
111        Min(x)
112    }
113}
114
115#[derive(Debug, Copy, Clone)]
116pub struct Xor<T>(T);
117
118impl<T: Copy + Clone + BitXor<Output = T> + Zero> Monoid for Xor<T> {
119    fn identity() -> Self {
120        Xor(T::zero())
121    }
122
123    fn op(x: &Self, y: &Self) -> Self {
124        Xor(x.0 ^ y.0)
125    }
126}
127
128impl<T> From<T> for Xor<T> {
129    fn from(x: T) -> Self {
130        Xor(x)
131    }
132}
133
134#[derive(Debug, Copy, Clone)]
135pub struct And<T>(T);
136
137impl<T> Monoid for And<T>
138where
139    T: Copy + Clone + BitAnd<Output = T> + Bounded + Sub<Output = T> + One,
140{
141    fn identity() -> Self {
142        And(T::max_value() - T::one())
143    }
144
145    fn op(x: &Self, y: &Self) -> Self {
146        And(x.0 & y.0)
147    }
148}
149
150impl<T> From<T> for And<T> {
151    fn from(x: T) -> Self {
152        And(x)
153    }
154}
155
156#[derive(Debug, Copy, Clone)]
157pub struct Or<T>(T);
158
159impl<T: Copy + Clone + BitOr<Output = T> + Zero> Monoid for Or<T> {
160    fn identity() -> Self {
161        Or(T::zero())
162    }
163
164    fn op(x: &Self, y: &Self) -> Self {
165        Or(x.0 | y.0)
166    }
167}
168
169impl<T> From<T> for Or<T> {
170    fn from(x: T) -> Self {
171        Or(x)
172    }
173}
174
175#[derive(Debug, Clone, Copy)]
176pub struct Gcd<T: Integer>(T);
177
178impl<T: Integer> Monoid for Gcd<T> {
179    fn identity() -> Self {
180        Gcd(T::zero())
181    }
182
183    fn op(x: &Self, y: &Self) -> Self {
184        Gcd(x.0.gcd(&y.0))
185    }
186}
187
188impl<T: Integer> From<T> for Gcd<T> {
189    fn from(x: T) -> Self {
190        Gcd(x)
191    }
192}
193
194#[derive(Debug, Clone, Copy)]
195pub struct Lcm<T: Integer>(T);
196
197impl<T: Integer> Monoid for Lcm<T> {
198    fn identity() -> Self {
199        Lcm(T::one())
200    }
201
202    fn op(x: &Self, y: &Self) -> Self {
203        Lcm(x.0.lcm(&y.0))
204    }
205}
206
207impl<T: Integer> From<T> for Lcm<T> {
208    fn from(x: T) -> Self {
209        Lcm(x)
210    }
211}
212
213monoid_def! {
214    BoolAnd<bool>,
215    true,
216    |x, y| x && y
217}
218
219monoid_def! {
220    BoolOr<bool>,
221    false,
222    |x, y| x || y
223}
224
225monoid_def! {
226    BoolXor<bool>,
227    false,
228    |x, y| !(x && y) || !(!x && !y)
229}
prcn_lib/monoid.rs

prcn_lib/
monoid.rs
