competitive/data_structure/binary_search_tree/
data.rs

1use super::{BstDataMutRef, BstSpec, LazyMapMonoid, Monoid, MonoidAct};
2use std::{fmt, fmt::Debug, mem::replace};
3
4pub trait BstDataAccess<Tag> {
5    type Value: ?Sized;
6
7    fn bst_data(&self) -> &Self::Value;
8
9    fn bst_data_mut(&mut self) -> &mut Self::Value;
10}
11
12pub struct MonoidAggElement<M>
13where
14    M: Monoid,
15{
16    pub agg: M::T,
17}
18
19impl<M> Debug for MonoidAggElement<M>
20where
21    M: Monoid<T: Debug>,
22{
23    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
24        f.debug_struct("MonoidAggElement")
25            .field("agg", &self.agg)
26            .finish()
27    }
28}
29
30impl<M> MonoidAggElement<M>
31where
32    M: Monoid,
33{
34    pub fn top_down<Spec>(_node: BstDataMutRef<'_, Spec>)
35    where
36        Spec: BstSpec<Data: BstDataAccess<marker::MonoidAgg, Value = Self>>,
37    {
38    }
39
40    pub fn bottom_up<Spec>(mut node: BstDataMutRef<'_, Spec>)
41    where
42        Spec: BstSpec<Data: BstDataAccess<marker::MonoidAgg, Value = Self>>,
43    {
44        let mut agg = node.reborrow().into_data().bst_data().agg.clone();
45        if let Ok(left) = node.reborrow().left().descend() {
46            agg = M::operate(&left.into_data().bst_data().agg, &agg);
47        }
48        if let Ok(right) = node.reborrow().right().descend() {
49            agg = M::operate(&agg, &right.into_data().bst_data().agg);
50        }
51        node.data_mut().bst_data_mut().agg = agg;
52    }
53}
54
55pub struct MonoidActElement<M>
56where
57    M: MonoidAct,
58{
59    pub key: M::Key,
60    pub act: M::Act,
61}
62
63impl<M> Debug for MonoidActElement<M>
64where
65    M: MonoidAct<Key: Debug, Act: Debug>,
66{
67    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
68        f.debug_struct("MonoidActElement")
69            .field("key", &self.key)
70            .field("act", &self.act)
71            .finish()
72    }
73}
74
75impl<M> MonoidActElement<M>
76where
77    M: MonoidAct,
78{
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    }
106}
107
108pub struct LazyMapElement<L>
109where
110    L: LazyMapMonoid,
111{
112    pub key: L::Key,
113    pub agg: L::Agg,
114    pub act: L::Act,
115}
116
117impl<L> Debug for LazyMapElement<L>
118where
119    L: LazyMapMonoid<Key: Debug, Agg: Debug, Act: Debug>,
120{
121    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
122        f.debug_struct("LazyMapElement")
123            .field("key", &self.key)
124            .field("agg", &self.agg)
125            .field("act", &self.act)
126            .finish()
127    }
128}
129
130impl<L> LazyMapElement<L>
131where
132    L: LazyMapMonoid,
133{
134    pub fn from_key(key: L::Key) -> Self {
135        let agg = L::single_agg(&key);
136        Self {
137            key,
138            agg,
139            act: L::act_unit(),
140        }
141    }
142
143    pub fn update_act<Spec>(mut node: BstDataMutRef<'_, Spec>, act: &L::Act)
144    where
145        Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
146    {
147        if L::is_act_unit(act) {
148            return;
149        }
150        L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
151        node.data_mut().bst_data_mut().key =
152            L::act_key(&node.reborrow().into_data().bst_data().key, act);
153        if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
154            node.data_mut().bst_data_mut().agg = nxlazy;
155        } else {
156            Self::top_down(node.reborrow_datamut());
157            Self::bottom_up(node.reborrow_datamut());
158        }
159    }
160
161    pub fn top_down<Spec>(mut node: BstDataMutRef<'_, Spec>)
162    where
163        Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
164    {
165        if L::is_act_unit(&node.reborrow().into_data().bst_data().act) {
166            return;
167        }
168        let act = replace(&mut node.data_mut().bst_data_mut().act, L::act_unit());
169        if let Ok(left) = node.reborrow_datamut().left().descend() {
170            Self::update_act(left, &act);
171        }
172        if let Ok(right) = node.reborrow_datamut().right().descend() {
173            Self::update_act(right, &act);
174        }
175    }
176
177    pub fn bottom_up<Spec>(mut node: BstDataMutRef<'_, Spec>)
178    where
179        Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
180    {
181        let mut agg = L::single_agg(&node.reborrow().into_data().bst_data().key);
182        if let Ok(left) = node.reborrow().left().descend() {
183            agg = L::agg_operate(&left.into_data().bst_data().agg, &agg);
184        }
185        if let Ok(right) = node.reborrow().right().descend() {
186            agg = L::agg_operate(&agg, &right.into_data().bst_data().agg);
187        }
188        node.data_mut().bst_data_mut().agg = agg;
189    }
190}
191
192pub mod marker {
193    pub enum Key {}
194    pub enum Size {}
195    pub enum MonoidAgg {}
196    pub enum MonoidAct {}
197    pub enum LazyMap {}
198}
competitive/data_structure/binary_search_tree/data.rs

competitive/data_structure/binary_search_tree/
data.rs
