pub trait Magma {
type T: Clone;
// Required method
fn operate(x: &Self::T, y: &Self::T) -> Self::T;
// Provided methods
fn reverse_operate(x: &Self::T, y: &Self::T) -> Self::T { ... }
fn operate_assign(x: &mut Self::T, y: &Self::T) { ... }
}Expand description
binary operaion: $T \circ T \to T$
Required Associated Types§
Required Methods§
Provided Methods§
fn reverse_operate(x: &Self::T, y: &Self::T) -> Self::T
Sourcefn operate_assign(x: &mut Self::T, y: &Self::T)
fn operate_assign(x: &mut Self::T, y: &Self::T)
Examples found in repository?
More examples
crates/competitive/src/data_structure/binary_indexed_tree.rs (line 51)
46 pub fn from_slice(slice: &[M::T]) -> Self {
47 let n = slice.len();
48 let mut bit = vec![M::unit(); n + 1];
49 for (i, x) in slice.iter().enumerate() {
50 let k = i + 1;
51 M::operate_assign(&mut bit[k], x);
52 let j = k + (k & (!k + 1));
53 if j <= n {
54 bit[j] = M::operate(&bit[j], &bit[k]);
55 }
56 }
57 Self { n, bit }
58 }crates/competitive/src/math/bitwiseand_convolve.rs (line 98)
89 pub fn push(&mut self, x: M::T) {
90 let i = self.data.len();
91 self.data.push(x);
92 let mut k = 0;
93 while i >> k & 1 == 1 {
94 let size = 1 << k;
95 let chunk = &mut self.data[i - (size * 2 - 1)..];
96 let (x, y) = chunk.split_at_mut(size);
97 for (x, y) in x.iter_mut().zip(y.iter()) {
98 M::operate_assign(x, y);
99 }
100 k += 1;
101 }
102 }crates/competitive/src/algorithm/doubling.rs (line 155)
148 pub fn find_first(
149 &self,
150 pos: usize,
151 mut pred: impl FnMut(usize, &M::T) -> bool,
152 ) -> Option<(usize, (usize, M::T))> {
153 let (mut k, (mut pos, mut x)) = self.find_last(pos, |k, x| !pred(k, x));
154 k += 1;
155 M::operate_assign(&mut x, &self.table[pos].1);
156 pos = self.table[pos].0;
157 if pred(pos, &x) {
158 Some((k, (pos, x)))
159 } else {
160 None
161 }
162 }crates/competitive/src/data_structure/transducer.rs (line 194)
183 pub fn step<S, I, B>(&mut self, mut sigma: S)
184 where
185 S: FnMut() -> I,
186 I: IntoIterator<Item = B>,
187 B: Borrow<T::Input>,
188 {
189 for (state, value) in self.dp.drain() {
190 for input in sigma() {
191 if let Some((nstate, _)) = self.fst.relation(&state, input.borrow()) {
192 self.ndp
193 .entry(nstate)
194 .and_modify(|acc| M::operate_assign(acc, &value))
195 .or_insert_with(|| value.clone());
196 }
197 }
198 }
199 swap(&mut self.dp, &mut self.ndp);
200 self.fst.stepout();
201 }
202 pub fn step_effect<S, I, B, F>(&mut self, mut sigma: S, mut effect: F)
203 where
204 S: FnMut() -> I,
205 I: IntoIterator<Item = B>,
206 B: Borrow<T::Input>,
207 F: FnMut(&M::T, &T::Output) -> M::T,
208 {
209 for (state, value) in self.dp.drain() {
210 for input in sigma() {
211 if let Some((nstate, output)) = self.fst.relation(&state, input.borrow()) {
212 let nvalue = effect(&value, &output);
213 self.ndp
214 .entry(nstate)
215 .and_modify(|acc| M::operate_assign(acc, &nvalue))
216 .or_insert(nvalue);
217 }
218 }
219 }
220 swap(&mut self.dp, &mut self.ndp);
221 self.fst.stepout();
222 }
223 pub fn fold_accept(&self) -> M::T {
224 let mut acc = M::unit();
225 for (state, value) in self.dp.iter() {
226 if self.fst.accept(state) {
227 M::operate_assign(&mut acc, value);
228 }
229 }
230 acc
231 }
232 pub fn map_fold_accept<U, F, D>(&self, mut f: F, mut map: D) -> D
233 where
234 F: FnMut(&T::State) -> U,
235 D: Container<Key = U, Value = M::T>,
236 {
237 for (state, value) in self.dp.iter() {
238 if self.fst.accept(state) {
239 map.entry(f(state))
240 .and_modify(|acc| M::operate_assign(acc, value))
241 .or_insert_with(|| value.clone());
242 }
243 }
244 map
245 }crates/competitive/src/algorithm/sqrt_decomposition.rs (line 95)
84 pub fn fold<R>(&self, range: R) -> <S::M as Magma>::T
85 where
86 R: RangeBounds<usize>,
87 {
88 let range = range.to_range_bounded(0, self.n).expect("invalid range");
89 let mut res = S::M::unit();
90 for (i, Bucket { cells, bucket }) in self.buckets.iter().enumerate() {
91 let s = i * self.bucket_size;
92 let t = s + cells.len();
93 if t <= range.start || range.end <= s {
94 } else if range.start <= s && t <= range.end {
95 <S::M as Magma>::operate_assign(&mut res, &S::fold_bucket(bucket));
96 } else {
97 for cell in &cells[range.start.max(s) - s..range.end.min(t) - s] {
98 <S::M as Magma>::operate_assign(&mut res, &S::fold_cell(bucket, cell));
99 }
100 }
101 }
102 res
103 }
104}
105
106pub struct RangeUpdateRangeFoldSqrtDecomposition<M>
107where
108 M: Monoid,
109{
110 _marker: PhantomData<fn() -> M>,
111}
112
113impl<M> SqrtDecomposition for RangeUpdateRangeFoldSqrtDecomposition<M>
114where
115 M: Monoid,
116{
117 type M = M;
118 // fold, lazy, size
119 type B = (M::T, M::T, usize);
120 fn bucket(bsize: usize) -> Self::B {
121 (M::unit(), M::unit(), bsize)
122 }
123 fn update_bucket(bucket: &mut Self::B, x: &<Self::M as Magma>::T) {
124 M::operate_assign(&mut bucket.1, x);
125 }
126 fn update_cell(
127 bucket: &mut Self::B,
128 cell: &mut <Self::M as Magma>::T,
129 x: &<Self::M as Magma>::T,
130 ) {
131 M::operate_assign(&mut bucket.0, x);
132 M::operate_assign(cell, x);
133 }Additional examples can be found in:
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".