pub trait MonoidAct {
type Key;
type Act: Clone;
type ActMonoid: Monoid<T = Self::Act>;
// Required method
fn act(x: &Self::Key, a: &Self::Act) -> Self::Key;
// Provided methods
fn act_assign(x: &mut Self::Key, a: &Self::Act) { ... }
fn unit() -> Self::Act { ... }
fn operate(x: &Self::Act, y: &Self::Act) -> Self::Act { ... }
fn operate_assign(x: &mut Self::Act, y: &Self::Act) { ... }
}Required Associated Types§
Required Methods§
Provided Methods§
Sourcefn act_assign(x: &mut Self::Key, a: &Self::Act)
fn act_assign(x: &mut Self::Key, a: &Self::Act)
Examples found in repository?
More examples
Sourcefn unit() -> Self::Act
fn unit() -> Self::Act
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/data.rs (line 82)
79 pub fn from_key(key: M::Key) -> Self {
80 Self {
81 key,
82 act: M::unit(),
83 }
84 }
85
86 pub fn update_act<Spec>(mut node: BstDataMutRef<'_, Spec>, act: &M::Act)
87 where
88 Spec: BstSpec<Data: BstDataAccess<marker::MonoidAct, Value = Self>>,
89 {
90 M::operate_assign(&mut node.data_mut().bst_data_mut().act, act);
91 M::act_assign(&mut node.data_mut().bst_data_mut().key, act);
92 }
93
94 pub fn top_down<Spec>(mut node: BstDataMutRef<'_, Spec>)
95 where
96 Spec: BstSpec<Data: BstDataAccess<marker::MonoidAct, Value = Self>>,
97 {
98 let act = replace(&mut node.data_mut().bst_data_mut().act, M::unit());
99 if let Ok(left) = node.reborrow_datamut().left().descend() {
100 Self::update_act(left, &act);
101 }
102 if let Ok(right) = node.reborrow_datamut().right().descend() {
103 Self::update_act(right, &act);
104 }
105 }More examples
crates/competitive/src/data_structure/pairing_heap.rs (line 30)
25 fn new(value: T) -> Self {
26 Self {
27 value,
28 first_child: None,
29 next_sibling: None,
30 lazy: A::unit(),
31 }
32 }
33
34 fn apply(&mut self, act: &A::Act) {
35 A::act_assign(&mut self.value, act);
36 A::operate_assign(&mut self.lazy, act);
37 }
38
39 fn propagate(&mut self) {
40 if !<A::ActMonoid as Unital>::is_unit(&self.lazy) {
41 let act = replace(&mut self.lazy, A::unit());
42 if let Some(node) = self.first_child.as_mut() {
43 node.apply(&act);
44 }
45 if let Some(node) = self.next_sibling.as_mut() {
46 node.apply(&act);
47 }
48 }
49 }crates/competitive/src/data_structure/dual_segment_tree.rs (line 52)
47 pub fn new(len: usize, key: M::Key) -> Self {
48 let n = len.next_power_of_two();
49 Self {
50 n,
51 keys: vec![key; len],
52 lazy: vec![M::unit(); n],
53 }
54 }
55 pub fn from_keys(keys: impl ExactSizeIterator<Item = M::Key>) -> Self {
56 let keys: Vec<_> = keys.collect();
57 let n = keys.len().next_power_of_two();
58 Self {
59 n,
60 keys,
61 lazy: vec![M::unit(); n],
62 }
63 }
64 fn update_at(&mut self, k: usize, a: &M::Act) {
65 if k < self.n {
66 M::operate_assign(&mut self.lazy[k], a);
67 } else {
68 M::act_assign(&mut self.keys[k - self.n], a);
69 }
70 }
71 fn propagate_at(&mut self, k: usize) {
72 let a = replace(&mut self.lazy[k], M::unit());
73 if !M::ActMonoid::is_unit(&a) {
74 self.update_at(2 * k, &a);
75 self.update_at(2 * k + 1, &a);
76 }
77 }fn operate(x: &Self::Act, y: &Self::Act) -> Self::Act
Sourcefn operate_assign(x: &mut Self::Act, y: &Self::Act)
fn operate_assign(x: &mut Self::Act, y: &Self::Act)
Examples found in repository?
More examples
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".