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 52)
47 pub fn from_slice(slice: &[M::T]) -> Self {
48 let n = slice.len();
49 let mut bit = vec![M::unit(); n + 1];
50 for (i, x) in slice.iter().enumerate() {
51 let k = i + 1;
52 M::operate_assign(&mut bit[k], x);
53 let j = k + (k & (!k + 1));
54 if j <= n {
55 bit[j] = M::operate(&bit[j], &bit[k]);
56 }
57 }
58 Self { n, bit }
59 }crates/competitive/src/data_structure/transducer.rs (line 201)
190 pub fn step<S, I, B>(&mut self, mut sigma: S)
191 where
192 S: FnMut() -> I,
193 I: IntoIterator<Item = B>,
194 B: Borrow<T::Input>,
195 {
196 for (state, value) in self.dp.drain() {
197 for input in sigma() {
198 if let Some((nstate, _)) = self.fst.relation(&state, input.borrow()) {
199 self.ndp
200 .entry(nstate)
201 .and_modify(|acc| M::operate_assign(acc, &value))
202 .or_insert_with(|| value.clone());
203 }
204 }
205 }
206 swap(&mut self.dp, &mut self.ndp);
207 self.fst.stepout();
208 }
209 pub fn step_effect<S, I, B, F>(&mut self, mut sigma: S, mut effect: F)
210 where
211 S: FnMut() -> I,
212 I: IntoIterator<Item = B>,
213 B: Borrow<T::Input>,
214 F: FnMut(&M::T, &T::Output) -> M::T,
215 {
216 for (state, value) in self.dp.drain() {
217 for input in sigma() {
218 if let Some((nstate, output)) = self.fst.relation(&state, input.borrow()) {
219 let nvalue = effect(&value, &output);
220 self.ndp
221 .entry(nstate)
222 .and_modify(|acc| M::operate_assign(acc, &nvalue))
223 .or_insert(nvalue);
224 }
225 }
226 }
227 swap(&mut self.dp, &mut self.ndp);
228 self.fst.stepout();
229 }
230 pub fn fold_accept(&self) -> M::T {
231 let mut acc = M::unit();
232 for (state, value) in self.dp.iter() {
233 if self.fst.accept(state) {
234 M::operate_assign(&mut acc, value);
235 }
236 }
237 acc
238 }
239 pub fn map_fold_accept<U, F, D>(&self, mut f: F, mut map: D) -> D
240 where
241 F: FnMut(&T::State) -> U,
242 D: Container<Key = U, Value = M::T>,
243 {
244 for (state, value) in self.dp.iter() {
245 if self.fst.accept(state) {
246 map.entry(f(state))
247 .and_modify(|acc| M::operate_assign(acc, value))
248 .or_insert_with(|| value.clone());
249 }
250 }
251 map
252 }crates/competitive/src/algorithm/sqrt_decomposition.rs (line 86)
75 pub fn fold<R>(&self, range: R) -> <S::M as Magma>::T
76 where
77 R: RangeBounds<usize>,
78 {
79 let range = range.to_range_bounded(0, self.n).expect("invalid range");
80 let mut res = S::M::unit();
81 for (i, (cells, bucket)) in self.buckets.iter().enumerate() {
82 let s = i * self.bucket_size;
83 let t = s + cells.len();
84 if t <= range.start || range.end <= s {
85 } else if range.start <= s && t <= range.end {
86 <S::M as Magma>::operate_assign(&mut res, &S::fold_bucket(bucket));
87 } else {
88 for cell in &cells[range.start.max(s) - s..range.end.min(t) - s] {
89 <S::M as Magma>::operate_assign(&mut res, &S::fold_cell(bucket, cell));
90 }
91 }
92 }
93 res
94 }Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.