pub struct BstNodeRef<BorrowType, Spec>where
Spec: BstSpec,{
pub node: NonNull<BstNode<Spec::Data, Spec::Parent>>,
_marker: PhantomData<BorrowType>,
}Fields§
§node: NonNull<BstNode<Spec::Data, Spec::Parent>>§_marker: PhantomData<BorrowType>Implementations§
Source§impl<BorrowType, Spec> BstNodeRef<BorrowType, Spec>where
Spec: BstSpec,
BorrowType: BorrowType,
impl<BorrowType, Spec> BstNodeRef<BorrowType, Spec>where
Spec: BstSpec,
BorrowType: BorrowType,
Sourcepub unsafe fn new_unchecked(
node: NonNull<BstNode<Spec::Data, Spec::Parent>>,
) -> Self
pub unsafe fn new_unchecked( node: NonNull<BstNode<Spec::Data, Spec::Parent>>, ) -> Self
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node_id.rs (line 57)
53 pub unsafe fn reborrow<'a>(
54 self,
55 _root: &'a Option<BstRoot<Spec>>,
56 ) -> BstNodeRef<node::marker::Immut<'a>, Spec> {
57 unsafe { BstNodeRef::new_unchecked(self.node) }
58 }
59
60 pub unsafe fn reborrow_datamut<'a>(
61 self,
62 _root: &'a mut Option<BstRoot<Spec>>,
63 ) -> BstNodeRef<node::marker::DataMut<'a>, Spec> {
64 unsafe { BstNodeRef::new_unchecked(self.node) }
65 }
66
67 pub unsafe fn reborrow_mut<'a>(
68 self,
69 _root: &'a mut Option<BstRoot<Spec>>,
70 ) -> BstNodeRef<node::marker::Mut<'a>, Spec> {
71 unsafe { BstNodeRef::new_unchecked(self.node) }
72 }Sourcepub fn reborrow(&self) -> BstNodeRef<Immut<'_>, Spec>
pub fn reborrow(&self) -> BstNodeRef<Immut<'_>, Spec>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/split.rs (line 37)
36 pub fn left(&self) -> Option<BstImmutRef<'_, Spec>> {
37 self.left.as_ref().map(|node| node.reborrow())
38 }
39
40 pub fn right(&self) -> Option<BstImmutRef<'_, Spec>> {
41 self.right.as_ref().map(|node| node.reborrow())
42 }
43
44 pub fn left_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>> {
45 self.left.as_mut().map(|node| node.borrow_datamut())
46 }
47
48 pub fn right_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>> {
49 self.right.as_mut().map(|node| node.borrow_datamut())
50 }
51
52 pub fn manually_merge<F>(&mut self, mut f: F)
53 where
54 F: FnMut(Option<BstRoot<Spec>>, Option<BstRoot<Spec>>) -> Option<BstRoot<Spec>>,
55 {
56 self.left = f(self.left.take(), self.right.take());
57 }
58}
59
60impl<'a, Spec> Drop for Split<'a, Spec>
61where
62 Spec: BstSpec,
63{
64 fn drop(&mut self) {
65 *self.root = Spec::merge(self.left.take(), self.right.take());
66 }
67}
68
69pub struct Split3<'a, Spec>
70where
71 Spec: BstSpec,
72{
73 left: Option<BstRoot<Spec>>,
74 mid: Option<BstRoot<Spec>>,
75 right: Option<BstRoot<Spec>>,
76 root: &'a mut Option<BstRoot<Spec>>,
77}
78
79impl<'a, Spec> Split3<'a, Spec>
80where
81 Spec: BstSpec,
82{
83 pub fn new<Seek1, Seek2>(
84 node: &'a mut Option<BstRoot<Spec>>,
85 start: Bound<Seek1>,
86 end: Bound<Seek2>,
87 ) -> Self
88 where
89 Seek1: BstSeeker<Spec = Spec>,
90 Seek2: BstSeeker<Spec = Spec>,
91 {
92 let (mut rest, right) = match end {
93 Bound::Included(seeker) => Spec::split(node.take(), seeker, true),
94 Bound::Excluded(seeker) => Spec::split(node.take(), seeker, false),
95 Bound::Unbounded => (node.take(), None),
96 };
97 let (left, mid) = match start {
98 Bound::Included(seeker) => Spec::split(rest.take(), seeker, false),
99 Bound::Excluded(seeker) => Spec::split(rest.take(), seeker, true),
100 Bound::Unbounded => (None, rest),
101 };
102 Self {
103 left,
104 mid,
105 right,
106 root: node,
107 }
108 }
109
110 pub fn left(&self) -> Option<BstImmutRef<'_, Spec>> {
111 self.left.as_ref().map(|node| node.reborrow())
112 }
113
114 pub fn mid(&self) -> Option<BstImmutRef<'_, Spec>> {
115 self.mid.as_ref().map(|node| node.reborrow())
116 }
117
118 pub fn right(&self) -> Option<BstImmutRef<'_, Spec>> {
119 self.right.as_ref().map(|node| node.reborrow())
120 }More examples
crates/competitive/src/data_structure/binary_search_tree/seeker.rs (line 29)
28 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
29 if node.reborrow().right().descend().is_ok() {
30 Ordering::Greater
31 } else {
32 Ordering::Equal
33 }
34 }
35}
36
37pub struct SeekRight<Spec> {
38 _marker: PhantomData<fn() -> Spec>,
39}
40
41impl<S> Default for SeekRight<S> {
42 fn default() -> Self {
43 Self {
44 _marker: PhantomData,
45 }
46 }
47}
48
49impl<Spec> BstSeeker for SeekRight<Spec>
50where
51 Spec: BstSpec,
52{
53 type Spec = Spec;
54 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
55 if node.reborrow().left().descend().is_ok() {
56 Ordering::Less
57 } else {
58 Ordering::Equal
59 }
60 }
61}
62
63pub struct SeekByKey<'a, Spec, K, Q>
64where
65 Q: ?Sized,
66{
67 key: &'a Q,
68 _marker: PhantomData<fn() -> (Spec, K)>,
69}
70
71impl<'a, Spec, K, Q> SeekByKey<'a, Spec, K, Q>
72where
73 Q: ?Sized,
74{
75 pub fn new(key: &'a Q) -> Self {
76 Self {
77 key,
78 _marker: PhantomData,
79 }
80 }
81}
82
83impl<Spec, K, Q> BstSeeker for SeekByKey<'_, Spec, K, Q>
84where
85 Spec: BstSpec<Data: BstDataAccess<data::marker::Key, Value = K>>,
86 K: Borrow<Q>,
87 Q: Ord + ?Sized,
88{
89 type Spec = Spec;
90
91 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
92 node.reborrow()
93 .into_data()
94 .bst_data()
95 .borrow()
96 .cmp(self.key)
97 }
98}
99
100pub struct SeekBySize<Spec> {
101 index: usize,
102 _marker: PhantomData<fn() -> Spec>,
103}
104
105impl<Spec> SeekBySize<Spec> {
106 pub fn new(index: usize) -> Self {
107 Self {
108 index,
109 _marker: PhantomData,
110 }
111 }
112}
113
114impl<Spec> BstSeeker for SeekBySize<Spec>
115where
116 Spec: BstSpec<Data: BstDataAccess<data::marker::Size, Value = usize>>,
117{
118 type Spec = Spec;
119
120 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
121 let lsize = node
122 .reborrow()
123 .left()
124 .descend()
125 .map(|l| *l.into_data().bst_data())
126 .unwrap_or_default();
127 let ord = lsize.cmp(&self.index);
128 if matches!(ord, Ordering::Less) {
129 self.index -= lsize + 1;
130 }
131 ord
132 }
133}
134
135pub struct SeekByAccCond<Spec, L, F>
136where
137 L: LazyMapMonoid,
138{
139 acc: L::Agg,
140 f: F,
141 _marker: PhantomData<fn() -> (Spec, L)>,
142}
143
144impl<Spec, L, F> SeekByAccCond<Spec, L, F>
145where
146 L: LazyMapMonoid,
147 F: FnMut(&L::Agg) -> bool,
148{
149 pub fn new(f: F) -> Self {
150 Self {
151 acc: L::agg_unit(),
152 f,
153 _marker: PhantomData,
154 }
155 }
156}
157
158impl<Spec, L, F> BstSeeker for SeekByAccCond<Spec, L, F>
159where
160 Spec: BstSpec<Data: BstDataAccess<data::marker::LazyMap, Value = LazyMapElement<L>>>,
161 L: LazyMapMonoid,
162 F: FnMut(&L::Agg) -> bool,
163{
164 type Spec = Spec;
165
166 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
167 if let Ok(left) = node.reborrow().left().descend() {
168 let left_agg = &left.into_data().bst_data().agg;
169 let nagg = L::agg_operate(&self.acc, left_agg);
170 if (self.f)(&nagg) {
171 return Ordering::Greater;
172 }
173 let nagg = L::agg_operate(
174 &nagg,
175 &L::single_agg(&node.reborrow().into_data().bst_data().key),
176 );
177 if (self.f)(&nagg) {
178 Ordering::Equal
179 } else {
180 self.acc = nagg;
181 Ordering::Less
182 }
183 } else {
184 let nagg = L::agg_operate(
185 &self.acc,
186 &L::single_agg(&node.reborrow().into_data().bst_data().key),
187 );
188 if (self.f)(&nagg) {
189 Ordering::Equal
190 } else {
191 self.acc = nagg;
192 Ordering::Less
193 }
194 }
195 }
196}
197
198pub struct SeekByRaccCond<Spec, L, F>
199where
200 L: LazyMapMonoid,
201{
202 acc: L::Agg,
203 f: F,
204 _marker: PhantomData<fn() -> (Spec, L)>,
205}
206
207impl<Spec, L, F> SeekByRaccCond<Spec, L, F>
208where
209 L: LazyMapMonoid,
210 F: FnMut(&L::Agg) -> bool,
211{
212 pub fn new(f: F) -> Self {
213 Self {
214 acc: L::agg_unit(),
215 f,
216 _marker: PhantomData,
217 }
218 }
219}
220
221impl<Spec, L, F> BstSeeker for SeekByRaccCond<Spec, L, F>
222where
223 Spec: BstSpec<Data: BstDataAccess<data::marker::LazyMap, Value = LazyMapElement<L>>>,
224 L: LazyMapMonoid,
225 F: FnMut(&L::Agg) -> bool,
226{
227 type Spec = Spec;
228
229 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
230 if let Ok(right) = node.reborrow().right().descend() {
231 let right_agg = &right.into_data().bst_data().agg;
232 let nagg = L::agg_operate(right_agg, &self.acc);
233 if (self.f)(&nagg) {
234 return Ordering::Less;
235 }
236 let nagg = L::agg_operate(
237 &L::single_agg(&node.reborrow().into_data().bst_data().key),
238 &nagg,
239 );
240 if (self.f)(&nagg) {
241 Ordering::Equal
242 } else {
243 self.acc = nagg;
244 Ordering::Greater
245 }
246 } else {
247 let nagg = L::agg_operate(
248 &L::single_agg(&node.reborrow().into_data().bst_data().key),
249 &self.acc,
250 );
251 if (self.f)(&nagg) {
252 Ordering::Equal
253 } else {
254 self.acc = nagg;
255 Ordering::Greater
256 }
257 }
258 }crates/competitive/src/data_structure/binary_search_tree/data.rs (line 44)
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 L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
148 node.data_mut().bst_data_mut().key =
149 L::act_key(&node.reborrow().into_data().bst_data().key, act);
150 if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
151 node.data_mut().bst_data_mut().agg = nxlazy;
152 } else {
153 Self::top_down(node.reborrow_datamut());
154 Self::bottom_up(node.reborrow_datamut());
155 }
156 }
157
158 pub fn top_down<Spec>(mut node: BstDataMutRef<'_, Spec>)
159 where
160 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
161 {
162 let act = replace(&mut node.data_mut().bst_data_mut().act, L::act_unit());
163 if let Ok(left) = node.reborrow_datamut().left().descend() {
164 Self::update_act(left, &act);
165 }
166 if let Ok(right) = node.reborrow_datamut().right().descend() {
167 Self::update_act(right, &act);
168 }
169 }
170
171 pub fn bottom_up<Spec>(mut node: BstDataMutRef<'_, Spec>)
172 where
173 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
174 {
175 let mut agg = L::single_agg(&node.reborrow().into_data().bst_data().key);
176 if let Ok(left) = node.reborrow().left().descend() {
177 agg = L::agg_operate(&left.into_data().bst_data().agg, &agg);
178 }
179 if let Ok(right) = node.reborrow().right().descend() {
180 agg = L::agg_operate(&agg, &right.into_data().bst_data().agg);
181 }
182 node.data_mut().bst_data_mut().agg = agg;
183 }crates/competitive/src/data_structure/treap.rs (line 125)
117 fn merge(
118 left: Option<TreapRoot<M, L>>,
119 right: Option<TreapRoot<M, L>>,
120 ) -> Option<TreapRoot<M, L>> {
121 match (left, right) {
122 (None, None) => None,
123 (None, Some(node)) | (Some(node), None) => Some(node),
124 (Some(mut left), Some(mut right)) => unsafe {
125 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
126 TreapSpec::top_down(left.borrow_datamut());
127 let lr = left.borrow_mut().right().take();
128 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
129 left.borrow_mut().right().set(lr);
130 TreapSpec::bottom_up(left.borrow_datamut());
131 Some(left)
132 } else {
133 TreapSpec::top_down(right.borrow_datamut());
134 let rl = right.borrow_mut().left().take();
135 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
136 right.borrow_mut().left().set(rl);
137 TreapSpec::bottom_up(right.borrow_datamut());
138 Some(right)
139 }
140 },
141 }
142 }
143
144 fn split<Seeker>(
145 node: Option<TreapRoot<M, L>>,
146 mut seeker: Seeker,
147 eq_left: bool,
148 ) -> (Option<TreapRoot<M, L>>, Option<TreapRoot<M, L>>)
149 where
150 Seeker: BstSeeker<Spec = Self>,
151 {
152 match node {
153 None => (None, None),
154 Some(mut node) => {
155 Self::top_down(node.borrow_datamut());
156 let seek_left = match seeker.bst_seek(node.reborrow()) {
157 Ordering::Less => false,
158 Ordering::Equal => !eq_left,
159 Ordering::Greater => true,
160 };
161 if seek_left {
162 unsafe {
163 let left = node.borrow_mut().left().take();
164 let (l, r) = Self::split(left, seeker, eq_left);
165 if let Some(r) = r {
166 node.borrow_mut().left().set(r);
167 }
168 Self::bottom_up(node.borrow_datamut());
169 (l, Some(node))
170 }
171 } else {
172 unsafe {
173 let right = node.borrow_mut().right().take();
174 let (l, r) = Self::split(right, seeker, eq_left);
175 if let Some(l) = l {
176 node.borrow_mut().right().set(l);
177 }
178 Self::bottom_up(node.borrow_datamut());
179 (Some(node), r)
180 }
181 }
182 }
183 }
184 }
185}
186
187impl<M, L> TreapSpec<M, L>
188where
189 M: MonoidAct<Key: Ord>,
190 L: LazyMapMonoid,
191{
192 pub fn merge_ordered(
193 left: Option<TreapRoot<M, L>>,
194 right: Option<TreapRoot<M, L>>,
195 ) -> Option<TreapRoot<M, L>> {
196 match (left, right) {
197 (None, None) => None,
198 (None, Some(node)) | (Some(node), None) => Some(node),
199 (Some(mut left), Some(mut right)) => unsafe {
200 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
201 Self::top_down(left.borrow_datamut());
202 let key = &left.reborrow().into_data().key.key;
203 let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), false);
204 let ll = left.borrow_mut().left().take();
205 let lr = left.borrow_mut().right().take();
206 if let Some(l) = Self::merge_ordered(ll, rl) {
207 left.borrow_mut().left().set(l);
208 }
209 if let Some(r) = Self::merge_ordered(lr, rr) {
210 left.borrow_mut().right().set(r);
211 }
212 Self::bottom_up(left.borrow_datamut());
213 Some(left)
214 } else {
215 Self::top_down(right.borrow_datamut());
216 let key = &right.reborrow().into_data().key.key;
217 let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), false);
218 let rl = right.borrow_mut().left().take();
219 let rr = right.borrow_mut().right().take();
220 if let Some(l) = Self::merge_ordered(ll, rl) {
221 right.borrow_mut().left().set(l);
222 }
223 if let Some(r) = Self::merge_ordered(lr, rr) {
224 right.borrow_mut().right().set(r);
225 }
226 Self::bottom_up(right.borrow_datamut());
227 Some(right)
228 }
229 },
230 }
231 }
232}
233
234pub struct Treap<M, L, A = BoxAllocator<TreapNode<M, L>>>
235where
236 M: MonoidAct<Key: Ord>,
237 L: LazyMapMonoid,
238 A: Allocator<TreapNode<M, L>>,
239{
240 root: Option<TreapRoot<M, L>>,
241 node_id_manager: BstNodeIdManager<TreapSpec<M, L>>,
242 rng: Xorshift,
243 allocator: ManuallyDrop<A>,
244 _marker: PhantomData<(M, L)>,
245}
246
247impl<M, L, A> Default for Treap<M, L, A>
248where
249 M: MonoidAct<Key: Ord>,
250 L: LazyMapMonoid,
251 A: Allocator<TreapNode<M, L>> + Default,
252{
253 fn default() -> Self {
254 Self {
255 root: None,
256 node_id_manager: Default::default(),
257 rng: Xorshift::new(),
258 allocator: ManuallyDrop::new(A::default()),
259 _marker: PhantomData,
260 }
261 }
262}
263
264impl<M, L, A> Drop for Treap<M, L, A>
265where
266 M: MonoidAct<Key: Ord>,
267 L: LazyMapMonoid,
268 A: Allocator<TreapNode<M, L>>,
269{
270 fn drop(&mut self) {
271 unsafe {
272 if let Some(root) = self.root.take() {
273 root.into_dying().drop_all(self.allocator.deref_mut());
274 }
275 ManuallyDrop::drop(&mut self.allocator);
276 }
277 }
278}
279
280impl<M, L> Treap<M, L>
281where
282 M: MonoidAct<Key: Ord>,
283 L: LazyMapMonoid,
284{
285 pub fn new() -> Self {
286 Self::default()
287 }
288}
289
290impl<M, L, A> Treap<M, L, A>
291where
292 M: MonoidAct<Key: Ord>,
293 L: LazyMapMonoid,
294 A: Allocator<TreapNode<M, L>>,
295{
296 pub fn len(&self) -> usize {
297 self.node_id_manager.len()
298 }
299
300 pub fn is_empty(&self) -> bool {
301 self.node_id_manager.is_empty()
302 }
303
304 pub fn clear(&mut self) {
305 unsafe {
306 if let Some(root) = self.root.take() {
307 root.into_dying().drop_all(self.allocator.deref_mut());
308 }
309 self.node_id_manager.clear();
310 }
311 }
312
313 pub fn get(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(&M::Key, &L::Key)> {
314 if !self.node_id_manager.contains(&node_id) {
315 return None;
316 }
317 unsafe {
318 WithParent::resolve_top_down::<TreapSpec<M, L>>(
319 node_id.reborrow_datamut(&mut self.root),
320 );
321 let data = node_id.reborrow(&self.root).into_data();
322 Some((&data.key.key, &data.value.key))
323 }
324 }
325
326 pub fn change(
327 &mut self,
328 node_id: BstNodeId<TreapSpec<M, L>>,
329 f: impl FnOnce(&mut L::Key),
330 ) -> bool {
331 if !self.node_id_manager.contains(&node_id) {
332 return false;
333 }
334 unsafe {
335 WithParent::resolve_top_down::<TreapSpec<M, L>>(
336 node_id.reborrow_datamut(&mut self.root),
337 );
338 let data = node_id.reborrow_datamut(&mut self.root).into_data_mut();
339 f(&mut data.value.key);
340 WithParent::resolve_bottom_up::<TreapSpec<M, L>>(
341 node_id.reborrow_datamut(&mut self.root),
342 );
343 }
344 true
345 }
346
347 pub fn change_key_value(
348 &mut self,
349 node_id: BstNodeId<TreapSpec<M, L>>,
350 f: impl FnOnce(&mut M::Key, &mut L::Key),
351 ) -> bool {
352 if !self.node_id_manager.contains(&node_id) {
353 return false;
354 }
355 unsafe {
356 WithParent::resolve_top_down::<TreapSpec<M, L>>(
357 node_id.reborrow_datamut(&mut self.root),
358 );
359 let mut node = if WithParent::is_root(node_id.reborrow(&self.root)) {
360 WithParent::remove_root(&mut self.root).unwrap_unchecked()
361 } else {
362 WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
363 };
364 let data = node.borrow_datamut().into_data_mut();
365 f(&mut data.key.key, &mut data.value.key);
366 self.root = TreapSpec::merge_ordered(self.root.take(), Some(node));
367 true
368 }
369 }
370
371 pub fn insert(&mut self, key: M::Key, value: L::Key) -> BstNodeId<TreapSpec<M, L>> {
372 let (left, right) = TreapSpec::split(self.root.take(), SeekByKey::new(&key), false);
373 let data = TreapData {
374 priority: self.rng.rand64(),
375 key: MonoidActElement::from_key(key),
376 value: LazyMapElement::from_key(value),
377 };
378 let node = BstRoot::from_data(data, self.allocator.deref_mut());
379 let node_id = self.node_id_manager.register(&node);
380 self.root = TreapSpec::merge(TreapSpec::merge(left, Some(node)), right);
381 node_id
382 }
383
384 pub fn remove(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(M::Key, L::Key)> {
385 if !self.node_id_manager.contains(&node_id) {
386 return None;
387 }
388 unsafe {
389 WithParent::resolve_top_down::<TreapSpec<M, L>>(
390 node_id.reborrow_datamut(&mut self.root),
391 );
392 let node = if WithParent::is_root(node_id.reborrow(&self.root)) {
393 WithParent::remove_root(&mut self.root).unwrap_unchecked()
394 } else {
395 WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
396 };
397 self.node_id_manager.unregister(node_id);
398 let data = node.into_dying().into_data(self.allocator.deref_mut());
399 Some((data.key.key, data.value.key))
400 }
401 }
402
403 pub fn range_by_key<Q, R>(&mut self, range: R) -> TreapSplit3<'_, M, L>
404 where
405 M: MonoidAct<Key: Borrow<Q>>,
406 Q: Ord + ?Sized,
407 R: RangeBounds<Q>,
408 {
409 let split3 = Split3::seek_by_key(&mut self.root, range);
410 TreapSplit3 {
411 split3,
412 key_updated: false,
413 }
414 }
415
416 pub fn find_by_key<Q>(&mut self, key: &Q) -> Option<BstNodeId<TreapSpec<M, L>>>
417 where
418 M: MonoidAct<Key: Borrow<Q>>,
419 Q: Ord + ?Sized,
420 {
421 let split = Split::new(
422 &mut self.root,
423 SeekByKey::<TreapSpec<M, L>, M::Key, Q>::new(key),
424 false,
425 );
426 let node = split.right()?.leftmost()?;
427 matches!(node.into_data().key.key.borrow().cmp(key), Ordering::Equal)
428 .then(|| self.node_id_manager.registerd_node_id(node))
429 .flatten()
430 }
431
432 pub fn find_by_acc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
433 where
434 F: FnMut(&L::Agg) -> bool,
435 {
436 let split = Split::new(
437 &mut self.root,
438 SeekByAccCond::<TreapSpec<M, L>, L, F>::new(f),
439 false,
440 );
441 let node = split.right()?.leftmost()?;
442 self.node_id_manager.registerd_node_id(node)
443 }
444
445 pub fn find_by_racc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
446 where
447 F: FnMut(&L::Agg) -> bool,
448 {
449 let split = Split::new(
450 &mut self.root,
451 SeekByRaccCond::<TreapSpec<M, L>, L, F>::new(f),
452 true,
453 );
454 let node = split.left()?.rightmost()?;
455 self.node_id_manager.registerd_node_id(node)
456 }
457}
458
459pub struct TreapSplit3<'a, M, L>
460where
461 M: MonoidAct<Key: Ord>,
462 L: LazyMapMonoid,
463{
464 split3: Split3<'a, TreapSpec<M, L>>,
465 key_updated: bool,
466}
467
468impl<'a, M, L> TreapSplit3<'a, M, L>
469where
470 M: MonoidAct<Key: Ord>,
471 L: LazyMapMonoid,
472{
473 pub fn fold(&self) -> L::Agg {
474 if let Some(node) = self.split3.mid() {
475 node.reborrow().into_data().value.agg.clone()
476 } else {
477 L::agg_unit()
478 }
479 }crates/competitive/src/data_structure/binary_search_tree/node.rs (line 183)
177 pub unsafe fn remove_not_root<Spec>(
178 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
179 ) -> BstNodeRef<marker::Owned, Spec>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 assert!(!Self::is_root(node.reborrow()));
184 unsafe {
185 let left = node.left_mut().take();
186 let right = node.right_mut().take();
187 let merged = Spec::merge(left, right);
188 let node_inner = node.node;
189 let mut parent = node.ascend().unwrap_unchecked();
190 let mut node = if let Some(merged) = merged {
191 let node = if parent
192 .reborrow()
193 .left()
194 .descend()
195 .is_ok_and(|n| n.node == node_inner)
196 {
197 parent.left_mut().replace(merged)
198 } else {
199 parent.right_mut().replace(merged)
200 };
201 Self::resolve_bottom_up(parent.reborrow_datamut());
202 node.unwrap_unchecked()
203 } else {
204 let node = if parent
205 .reborrow()
206 .left()
207 .descend()
208 .is_ok_and(|n| n.node == node_inner)
209 {
210 parent.left_mut().take()
211 } else {
212 parent.right_mut().take()
213 };
214 Self::resolve_bottom_up(parent.reborrow_datamut());
215 node.unwrap_unchecked()
216 };
217 Spec::bottom_up(node.borrow_datamut());
218 node
219 }
220 }
221}
222
223pub struct BstNodeRef<BorrowType, Spec>
224where
225 Spec: BstSpec,
226{
227 pub node: NonNull<BstNode<Spec::Data, Spec::Parent>>,
228 _marker: PhantomData<BorrowType>,
229}
230
231impl<'a, Spec> Copy for BstNodeRef<marker::Immut<'a>, Spec> where Spec: BstSpec<Data: 'a> {}
232impl<'a, Spec> Clone for BstNodeRef<marker::Immut<'a>, Spec>
233where
234 Spec: BstSpec<Data: 'a>,
235{
236 fn clone(&self) -> Self {
237 *self
238 }
239}
240
241impl<BorrowType, Spec> BstNodeRef<BorrowType, Spec>
242where
243 Spec: BstSpec,
244 BorrowType: marker::BorrowType,
245{
246 pub unsafe fn new_unchecked(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
247 Self {
248 node,
249 _marker: PhantomData,
250 }
251 }
252 pub fn reborrow(&self) -> BstNodeRef<marker::Immut<'_>, Spec> {
253 BstNodeRef {
254 node: self.node,
255 _marker: PhantomData,
256 }
257 }
258 pub fn left(self) -> BstEdgeHandle<Self, marker::Left> {
259 BstEdgeHandle {
260 node: self,
261 _marker: PhantomData,
262 }
263 }
264 pub fn right(self) -> BstEdgeHandle<Self, marker::Right> {
265 BstEdgeHandle {
266 node: self,
267 _marker: PhantomData,
268 }
269 }
270}
271
272impl<BorrowType, Spec, Data> BstNodeRef<BorrowType, Spec>
273where
274 Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
275 BorrowType: marker::BorrowType,
276{
277 pub fn ascend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self> {
278 const {
279 assert!(BorrowType::TRAVERSAL_PERMIT);
280 };
281 let parent = unsafe { self.node.as_ref().parent.parent };
282 parent
283 .map(|node| BstNodeRef {
284 node,
285 _marker: PhantomData,
286 })
287 .ok_or(self)
288 }
289 pub fn root_path(self) -> (Self, Vec<bool>) {
290 let mut node = self;
291 let mut nn = node.node;
292 let mut stack = vec![];
293 let root = loop {
294 match node.ascend() {
295 Ok(parent) => {
296 node = parent;
297 stack.push(
298 node.reborrow()
299 .left()
300 .descend()
301 .is_ok_and(|node| node.node == nn),
302 );
303 nn = node.node;
304 }
305 Err(node) => {
306 break node;
307 }
308 }
309 };
310 (root, stack)
311 }
312}
313
314impl<Spec> BstNodeRef<marker::Owned, Spec>
315where
316 Spec: BstSpec,
317{
318 pub fn new(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
319 Self {
320 node,
321 _marker: PhantomData,
322 }
323 }
324 pub fn from_data<A>(data: Spec::Data, allocator: &mut A) -> Self
325 where
326 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
327 {
328 Self::new(allocator.allocate(BstNode::new(data)))
329 }
330 pub fn borrow_mut(&mut self) -> BstNodeRef<marker::Mut<'_>, Spec> {
331 BstNodeRef {
332 node: self.node,
333 _marker: PhantomData,
334 }
335 }
336 pub fn borrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
337 BstNodeRef {
338 node: self.node,
339 _marker: PhantomData,
340 }
341 }
342 pub fn into_dying(self) -> BstNodeRef<marker::Dying, Spec> {
343 BstNodeRef {
344 node: self.node,
345 _marker: PhantomData,
346 }
347 }
348}
349
350impl<'a, Spec> BstNodeRef<marker::Immut<'a>, Spec>
351where
352 Spec: BstSpec<Parent: 'a, Data: 'a>,
353{
354 pub fn into_data(self) -> &'a Spec::Data {
355 unsafe { &self.node.as_ref().data }
356 }
357
358 pub fn traverse<F>(self, f: &mut F)
359 where
360 F: FnMut(Self),
361 {
362 if let Ok(left) = self.left().descend() {
363 left.traverse(f);
364 }
365 f(self);
366 if let Ok(right) = self.right().descend() {
367 right.traverse(f);
368 }
369 }
370
371 pub fn leftmost(self) -> Option<Self> {
372 let mut node = self;
373 while let Ok(left) = node.left().descend() {
374 node = left;
375 }
376 Some(node)
377 }
378
379 pub fn rightmost(self) -> Option<Self> {
380 let mut node = self;
381 while let Ok(right) = node.right().descend() {
382 node = right;
383 }
384 Some(node)
385 }
386}
387
388impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
389where
390 Spec: BstSpec,
391{
392 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
393 BstNodeRef {
394 node: self.node,
395 _marker: PhantomData,
396 }
397 }
398 pub fn data_mut(&mut self) -> &mut Spec::Data {
399 unsafe { &mut self.node.as_mut().data }
400 }
401}
402
403impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
404where
405 Spec: BstSpec<Parent: 'a, Data: 'a>,
406{
407 pub fn into_data_mut(mut self) -> &'a mut Spec::Data {
408 unsafe { &mut self.node.as_mut().data }
409 }
410}
411
412impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
413where
414 Spec: BstSpec,
415{
416 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
417 BstNodeRef {
418 node: self.node,
419 _marker: PhantomData,
420 }
421 }
422
423 pub fn left_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Left> {
424 BstEdgeHandle {
425 node: BstNodeRef {
426 node: self.node,
427 _marker: PhantomData,
428 },
429 _marker: PhantomData,
430 }
431 }
432
433 pub fn right_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Right> {
434 BstEdgeHandle {
435 node: BstNodeRef {
436 node: self.node,
437 _marker: PhantomData,
438 },
439 _marker: PhantomData,
440 }
441 }
442}
443
444impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
445where
446 Spec: BstSpec<Data: 'a>,
447{
448 pub fn dormant(self) -> BstNodeRef<marker::DormantMut, Spec> {
449 BstNodeRef {
450 node: self.node,
451 _marker: PhantomData,
452 }
453 }
454}
455
456impl<Spec> BstNodeRef<marker::DormantMut, Spec>
457where
458 Spec: BstSpec,
459{
460 pub unsafe fn awaken<'a>(self) -> BstNodeRef<marker::Mut<'a>, Spec> {
461 BstNodeRef {
462 node: self.node,
463 _marker: PhantomData,
464 }
465 }
466}
467
468impl<Spec> BstNodeRef<marker::Dying, Spec>
469where
470 Spec: BstSpec,
471{
472 pub unsafe fn into_data<A>(self, allocator: &mut A) -> Spec::Data
473 where
474 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
475 {
476 assert!(self.reborrow().left().descend().is_err());
477 assert!(self.reborrow().right().descend().is_err());
478 allocator.deallocate(self.node).data
479 }Sourcepub fn left(self) -> BstEdgeHandle<Self, Left>
pub fn left(self) -> BstEdgeHandle<Self, Left>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/seeker.rs (line 55)
54 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
55 if node.reborrow().left().descend().is_ok() {
56 Ordering::Less
57 } else {
58 Ordering::Equal
59 }
60 }
61}
62
63pub struct SeekByKey<'a, Spec, K, Q>
64where
65 Q: ?Sized,
66{
67 key: &'a Q,
68 _marker: PhantomData<fn() -> (Spec, K)>,
69}
70
71impl<'a, Spec, K, Q> SeekByKey<'a, Spec, K, Q>
72where
73 Q: ?Sized,
74{
75 pub fn new(key: &'a Q) -> Self {
76 Self {
77 key,
78 _marker: PhantomData,
79 }
80 }
81}
82
83impl<Spec, K, Q> BstSeeker for SeekByKey<'_, Spec, K, Q>
84where
85 Spec: BstSpec<Data: BstDataAccess<data::marker::Key, Value = K>>,
86 K: Borrow<Q>,
87 Q: Ord + ?Sized,
88{
89 type Spec = Spec;
90
91 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
92 node.reborrow()
93 .into_data()
94 .bst_data()
95 .borrow()
96 .cmp(self.key)
97 }
98}
99
100pub struct SeekBySize<Spec> {
101 index: usize,
102 _marker: PhantomData<fn() -> Spec>,
103}
104
105impl<Spec> SeekBySize<Spec> {
106 pub fn new(index: usize) -> Self {
107 Self {
108 index,
109 _marker: PhantomData,
110 }
111 }
112}
113
114impl<Spec> BstSeeker for SeekBySize<Spec>
115where
116 Spec: BstSpec<Data: BstDataAccess<data::marker::Size, Value = usize>>,
117{
118 type Spec = Spec;
119
120 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
121 let lsize = node
122 .reborrow()
123 .left()
124 .descend()
125 .map(|l| *l.into_data().bst_data())
126 .unwrap_or_default();
127 let ord = lsize.cmp(&self.index);
128 if matches!(ord, Ordering::Less) {
129 self.index -= lsize + 1;
130 }
131 ord
132 }
133}
134
135pub struct SeekByAccCond<Spec, L, F>
136where
137 L: LazyMapMonoid,
138{
139 acc: L::Agg,
140 f: F,
141 _marker: PhantomData<fn() -> (Spec, L)>,
142}
143
144impl<Spec, L, F> SeekByAccCond<Spec, L, F>
145where
146 L: LazyMapMonoid,
147 F: FnMut(&L::Agg) -> bool,
148{
149 pub fn new(f: F) -> Self {
150 Self {
151 acc: L::agg_unit(),
152 f,
153 _marker: PhantomData,
154 }
155 }
156}
157
158impl<Spec, L, F> BstSeeker for SeekByAccCond<Spec, L, F>
159where
160 Spec: BstSpec<Data: BstDataAccess<data::marker::LazyMap, Value = LazyMapElement<L>>>,
161 L: LazyMapMonoid,
162 F: FnMut(&L::Agg) -> bool,
163{
164 type Spec = Spec;
165
166 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
167 if let Ok(left) = node.reborrow().left().descend() {
168 let left_agg = &left.into_data().bst_data().agg;
169 let nagg = L::agg_operate(&self.acc, left_agg);
170 if (self.f)(&nagg) {
171 return Ordering::Greater;
172 }
173 let nagg = L::agg_operate(
174 &nagg,
175 &L::single_agg(&node.reborrow().into_data().bst_data().key),
176 );
177 if (self.f)(&nagg) {
178 Ordering::Equal
179 } else {
180 self.acc = nagg;
181 Ordering::Less
182 }
183 } else {
184 let nagg = L::agg_operate(
185 &self.acc,
186 &L::single_agg(&node.reborrow().into_data().bst_data().key),
187 );
188 if (self.f)(&nagg) {
189 Ordering::Equal
190 } else {
191 self.acc = nagg;
192 Ordering::Less
193 }
194 }
195 }More examples
crates/competitive/src/data_structure/binary_search_tree/data.rs (line 45)
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 L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
148 node.data_mut().bst_data_mut().key =
149 L::act_key(&node.reborrow().into_data().bst_data().key, act);
150 if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
151 node.data_mut().bst_data_mut().agg = nxlazy;
152 } else {
153 Self::top_down(node.reborrow_datamut());
154 Self::bottom_up(node.reborrow_datamut());
155 }
156 }
157
158 pub fn top_down<Spec>(mut node: BstDataMutRef<'_, Spec>)
159 where
160 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
161 {
162 let act = replace(&mut node.data_mut().bst_data_mut().act, L::act_unit());
163 if let Ok(left) = node.reborrow_datamut().left().descend() {
164 Self::update_act(left, &act);
165 }
166 if let Ok(right) = node.reborrow_datamut().right().descend() {
167 Self::update_act(right, &act);
168 }
169 }
170
171 pub fn bottom_up<Spec>(mut node: BstDataMutRef<'_, Spec>)
172 where
173 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
174 {
175 let mut agg = L::single_agg(&node.reborrow().into_data().bst_data().key);
176 if let Ok(left) = node.reborrow().left().descend() {
177 agg = L::agg_operate(&left.into_data().bst_data().agg, &agg);
178 }
179 if let Ok(right) = node.reborrow().right().descend() {
180 agg = L::agg_operate(&agg, &right.into_data().bst_data().agg);
181 }
182 node.data_mut().bst_data_mut().agg = agg;
183 }crates/competitive/src/data_structure/binary_search_tree/node.rs (line 132)
123 pub fn resolve_top_down<Spec>(node: BstNodeRef<marker::DataMut<'_>, Spec>)
124 where
125 Spec: BstSpec<Data = Data, Parent = Self>,
126 {
127 unsafe {
128 let (mut node, mut stack) = node.root_path();
129 while let Some(is_left) = stack.pop() {
130 Spec::top_down(node.reborrow_datamut());
131 if is_left {
132 node = node.left().descend().unwrap_unchecked();
133 } else {
134 node = node.right().descend().unwrap_unchecked();
135 }
136 }
137 Spec::top_down(node.reborrow_datamut());
138 }
139 }
140
141 pub fn resolve_bottom_up<Spec>(mut node: BstNodeRef<marker::DataMut<'_>, Spec>)
142 where
143 Spec: BstSpec<Data = Data, Parent = Self>,
144 {
145 loop {
146 Spec::bottom_up(node.reborrow_datamut());
147 match node.ascend() {
148 Ok(parent) => node = parent,
149 Err(_) => break,
150 }
151 }
152 }
153
154 pub fn is_root<Spec>(node: BstNodeRef<marker::Immut<'_>, Spec>) -> bool
155 where
156 Spec: BstSpec<Data = Data, Parent = Self>,
157 {
158 unsafe { node.node.as_ref().parent.parent.is_none() }
159 }
160
161 pub unsafe fn remove_root<Spec>(
162 root: &mut Option<BstRoot<Spec>>,
163 ) -> Option<BstNodeRef<marker::Owned, Spec>>
164 where
165 Spec: BstSpec<Data = Data, Parent = Self>,
166 {
167 let mut node = root.take()?;
168 unsafe {
169 let left = node.borrow_mut().left_mut().take();
170 let right = node.borrow_mut().right_mut().take();
171 *root = Spec::merge(left, right);
172 Spec::bottom_up(node.borrow_datamut());
173 Some(node)
174 }
175 }
176
177 pub unsafe fn remove_not_root<Spec>(
178 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
179 ) -> BstNodeRef<marker::Owned, Spec>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 assert!(!Self::is_root(node.reborrow()));
184 unsafe {
185 let left = node.left_mut().take();
186 let right = node.right_mut().take();
187 let merged = Spec::merge(left, right);
188 let node_inner = node.node;
189 let mut parent = node.ascend().unwrap_unchecked();
190 let mut node = if let Some(merged) = merged {
191 let node = if parent
192 .reborrow()
193 .left()
194 .descend()
195 .is_ok_and(|n| n.node == node_inner)
196 {
197 parent.left_mut().replace(merged)
198 } else {
199 parent.right_mut().replace(merged)
200 };
201 Self::resolve_bottom_up(parent.reborrow_datamut());
202 node.unwrap_unchecked()
203 } else {
204 let node = if parent
205 .reborrow()
206 .left()
207 .descend()
208 .is_ok_and(|n| n.node == node_inner)
209 {
210 parent.left_mut().take()
211 } else {
212 parent.right_mut().take()
213 };
214 Self::resolve_bottom_up(parent.reborrow_datamut());
215 node.unwrap_unchecked()
216 };
217 Spec::bottom_up(node.borrow_datamut());
218 node
219 }
220 }
221}
222
223pub struct BstNodeRef<BorrowType, Spec>
224where
225 Spec: BstSpec,
226{
227 pub node: NonNull<BstNode<Spec::Data, Spec::Parent>>,
228 _marker: PhantomData<BorrowType>,
229}
230
231impl<'a, Spec> Copy for BstNodeRef<marker::Immut<'a>, Spec> where Spec: BstSpec<Data: 'a> {}
232impl<'a, Spec> Clone for BstNodeRef<marker::Immut<'a>, Spec>
233where
234 Spec: BstSpec<Data: 'a>,
235{
236 fn clone(&self) -> Self {
237 *self
238 }
239}
240
241impl<BorrowType, Spec> BstNodeRef<BorrowType, Spec>
242where
243 Spec: BstSpec,
244 BorrowType: marker::BorrowType,
245{
246 pub unsafe fn new_unchecked(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
247 Self {
248 node,
249 _marker: PhantomData,
250 }
251 }
252 pub fn reborrow(&self) -> BstNodeRef<marker::Immut<'_>, Spec> {
253 BstNodeRef {
254 node: self.node,
255 _marker: PhantomData,
256 }
257 }
258 pub fn left(self) -> BstEdgeHandle<Self, marker::Left> {
259 BstEdgeHandle {
260 node: self,
261 _marker: PhantomData,
262 }
263 }
264 pub fn right(self) -> BstEdgeHandle<Self, marker::Right> {
265 BstEdgeHandle {
266 node: self,
267 _marker: PhantomData,
268 }
269 }
270}
271
272impl<BorrowType, Spec, Data> BstNodeRef<BorrowType, Spec>
273where
274 Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
275 BorrowType: marker::BorrowType,
276{
277 pub fn ascend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self> {
278 const {
279 assert!(BorrowType::TRAVERSAL_PERMIT);
280 };
281 let parent = unsafe { self.node.as_ref().parent.parent };
282 parent
283 .map(|node| BstNodeRef {
284 node,
285 _marker: PhantomData,
286 })
287 .ok_or(self)
288 }
289 pub fn root_path(self) -> (Self, Vec<bool>) {
290 let mut node = self;
291 let mut nn = node.node;
292 let mut stack = vec![];
293 let root = loop {
294 match node.ascend() {
295 Ok(parent) => {
296 node = parent;
297 stack.push(
298 node.reborrow()
299 .left()
300 .descend()
301 .is_ok_and(|node| node.node == nn),
302 );
303 nn = node.node;
304 }
305 Err(node) => {
306 break node;
307 }
308 }
309 };
310 (root, stack)
311 }
312}
313
314impl<Spec> BstNodeRef<marker::Owned, Spec>
315where
316 Spec: BstSpec,
317{
318 pub fn new(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
319 Self {
320 node,
321 _marker: PhantomData,
322 }
323 }
324 pub fn from_data<A>(data: Spec::Data, allocator: &mut A) -> Self
325 where
326 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
327 {
328 Self::new(allocator.allocate(BstNode::new(data)))
329 }
330 pub fn borrow_mut(&mut self) -> BstNodeRef<marker::Mut<'_>, Spec> {
331 BstNodeRef {
332 node: self.node,
333 _marker: PhantomData,
334 }
335 }
336 pub fn borrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
337 BstNodeRef {
338 node: self.node,
339 _marker: PhantomData,
340 }
341 }
342 pub fn into_dying(self) -> BstNodeRef<marker::Dying, Spec> {
343 BstNodeRef {
344 node: self.node,
345 _marker: PhantomData,
346 }
347 }
348}
349
350impl<'a, Spec> BstNodeRef<marker::Immut<'a>, Spec>
351where
352 Spec: BstSpec<Parent: 'a, Data: 'a>,
353{
354 pub fn into_data(self) -> &'a Spec::Data {
355 unsafe { &self.node.as_ref().data }
356 }
357
358 pub fn traverse<F>(self, f: &mut F)
359 where
360 F: FnMut(Self),
361 {
362 if let Ok(left) = self.left().descend() {
363 left.traverse(f);
364 }
365 f(self);
366 if let Ok(right) = self.right().descend() {
367 right.traverse(f);
368 }
369 }
370
371 pub fn leftmost(self) -> Option<Self> {
372 let mut node = self;
373 while let Ok(left) = node.left().descend() {
374 node = left;
375 }
376 Some(node)
377 }
378
379 pub fn rightmost(self) -> Option<Self> {
380 let mut node = self;
381 while let Ok(right) = node.right().descend() {
382 node = right;
383 }
384 Some(node)
385 }
386}
387
388impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
389where
390 Spec: BstSpec,
391{
392 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
393 BstNodeRef {
394 node: self.node,
395 _marker: PhantomData,
396 }
397 }
398 pub fn data_mut(&mut self) -> &mut Spec::Data {
399 unsafe { &mut self.node.as_mut().data }
400 }
401}
402
403impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
404where
405 Spec: BstSpec<Parent: 'a, Data: 'a>,
406{
407 pub fn into_data_mut(mut self) -> &'a mut Spec::Data {
408 unsafe { &mut self.node.as_mut().data }
409 }
410}
411
412impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
413where
414 Spec: BstSpec,
415{
416 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
417 BstNodeRef {
418 node: self.node,
419 _marker: PhantomData,
420 }
421 }
422
423 pub fn left_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Left> {
424 BstEdgeHandle {
425 node: BstNodeRef {
426 node: self.node,
427 _marker: PhantomData,
428 },
429 _marker: PhantomData,
430 }
431 }
432
433 pub fn right_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Right> {
434 BstEdgeHandle {
435 node: BstNodeRef {
436 node: self.node,
437 _marker: PhantomData,
438 },
439 _marker: PhantomData,
440 }
441 }
442}
443
444impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
445where
446 Spec: BstSpec<Data: 'a>,
447{
448 pub fn dormant(self) -> BstNodeRef<marker::DormantMut, Spec> {
449 BstNodeRef {
450 node: self.node,
451 _marker: PhantomData,
452 }
453 }
454}
455
456impl<Spec> BstNodeRef<marker::DormantMut, Spec>
457where
458 Spec: BstSpec,
459{
460 pub unsafe fn awaken<'a>(self) -> BstNodeRef<marker::Mut<'a>, Spec> {
461 BstNodeRef {
462 node: self.node,
463 _marker: PhantomData,
464 }
465 }
466}
467
468impl<Spec> BstNodeRef<marker::Dying, Spec>
469where
470 Spec: BstSpec,
471{
472 pub unsafe fn into_data<A>(self, allocator: &mut A) -> Spec::Data
473 where
474 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
475 {
476 assert!(self.reborrow().left().descend().is_err());
477 assert!(self.reborrow().right().descend().is_err());
478 allocator.deallocate(self.node).data
479 }crates/competitive/src/data_structure/treap.rs (line 134)
117 fn merge(
118 left: Option<TreapRoot<M, L>>,
119 right: Option<TreapRoot<M, L>>,
120 ) -> Option<TreapRoot<M, L>> {
121 match (left, right) {
122 (None, None) => None,
123 (None, Some(node)) | (Some(node), None) => Some(node),
124 (Some(mut left), Some(mut right)) => unsafe {
125 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
126 TreapSpec::top_down(left.borrow_datamut());
127 let lr = left.borrow_mut().right().take();
128 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
129 left.borrow_mut().right().set(lr);
130 TreapSpec::bottom_up(left.borrow_datamut());
131 Some(left)
132 } else {
133 TreapSpec::top_down(right.borrow_datamut());
134 let rl = right.borrow_mut().left().take();
135 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
136 right.borrow_mut().left().set(rl);
137 TreapSpec::bottom_up(right.borrow_datamut());
138 Some(right)
139 }
140 },
141 }
142 }
143
144 fn split<Seeker>(
145 node: Option<TreapRoot<M, L>>,
146 mut seeker: Seeker,
147 eq_left: bool,
148 ) -> (Option<TreapRoot<M, L>>, Option<TreapRoot<M, L>>)
149 where
150 Seeker: BstSeeker<Spec = Self>,
151 {
152 match node {
153 None => (None, None),
154 Some(mut node) => {
155 Self::top_down(node.borrow_datamut());
156 let seek_left = match seeker.bst_seek(node.reborrow()) {
157 Ordering::Less => false,
158 Ordering::Equal => !eq_left,
159 Ordering::Greater => true,
160 };
161 if seek_left {
162 unsafe {
163 let left = node.borrow_mut().left().take();
164 let (l, r) = Self::split(left, seeker, eq_left);
165 if let Some(r) = r {
166 node.borrow_mut().left().set(r);
167 }
168 Self::bottom_up(node.borrow_datamut());
169 (l, Some(node))
170 }
171 } else {
172 unsafe {
173 let right = node.borrow_mut().right().take();
174 let (l, r) = Self::split(right, seeker, eq_left);
175 if let Some(l) = l {
176 node.borrow_mut().right().set(l);
177 }
178 Self::bottom_up(node.borrow_datamut());
179 (Some(node), r)
180 }
181 }
182 }
183 }
184 }
185}
186
187impl<M, L> TreapSpec<M, L>
188where
189 M: MonoidAct<Key: Ord>,
190 L: LazyMapMonoid,
191{
192 pub fn merge_ordered(
193 left: Option<TreapRoot<M, L>>,
194 right: Option<TreapRoot<M, L>>,
195 ) -> Option<TreapRoot<M, L>> {
196 match (left, right) {
197 (None, None) => None,
198 (None, Some(node)) | (Some(node), None) => Some(node),
199 (Some(mut left), Some(mut right)) => unsafe {
200 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
201 Self::top_down(left.borrow_datamut());
202 let key = &left.reborrow().into_data().key.key;
203 let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), false);
204 let ll = left.borrow_mut().left().take();
205 let lr = left.borrow_mut().right().take();
206 if let Some(l) = Self::merge_ordered(ll, rl) {
207 left.borrow_mut().left().set(l);
208 }
209 if let Some(r) = Self::merge_ordered(lr, rr) {
210 left.borrow_mut().right().set(r);
211 }
212 Self::bottom_up(left.borrow_datamut());
213 Some(left)
214 } else {
215 Self::top_down(right.borrow_datamut());
216 let key = &right.reborrow().into_data().key.key;
217 let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), false);
218 let rl = right.borrow_mut().left().take();
219 let rr = right.borrow_mut().right().take();
220 if let Some(l) = Self::merge_ordered(ll, rl) {
221 right.borrow_mut().left().set(l);
222 }
223 if let Some(r) = Self::merge_ordered(lr, rr) {
224 right.borrow_mut().right().set(r);
225 }
226 Self::bottom_up(right.borrow_datamut());
227 Some(right)
228 }
229 },
230 }
231 }Sourcepub fn right(self) -> BstEdgeHandle<Self, Right>
pub fn right(self) -> BstEdgeHandle<Self, Right>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/seeker.rs (line 29)
28 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
29 if node.reborrow().right().descend().is_ok() {
30 Ordering::Greater
31 } else {
32 Ordering::Equal
33 }
34 }
35}
36
37pub struct SeekRight<Spec> {
38 _marker: PhantomData<fn() -> Spec>,
39}
40
41impl<S> Default for SeekRight<S> {
42 fn default() -> Self {
43 Self {
44 _marker: PhantomData,
45 }
46 }
47}
48
49impl<Spec> BstSeeker for SeekRight<Spec>
50where
51 Spec: BstSpec,
52{
53 type Spec = Spec;
54 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
55 if node.reborrow().left().descend().is_ok() {
56 Ordering::Less
57 } else {
58 Ordering::Equal
59 }
60 }
61}
62
63pub struct SeekByKey<'a, Spec, K, Q>
64where
65 Q: ?Sized,
66{
67 key: &'a Q,
68 _marker: PhantomData<fn() -> (Spec, K)>,
69}
70
71impl<'a, Spec, K, Q> SeekByKey<'a, Spec, K, Q>
72where
73 Q: ?Sized,
74{
75 pub fn new(key: &'a Q) -> Self {
76 Self {
77 key,
78 _marker: PhantomData,
79 }
80 }
81}
82
83impl<Spec, K, Q> BstSeeker for SeekByKey<'_, Spec, K, Q>
84where
85 Spec: BstSpec<Data: BstDataAccess<data::marker::Key, Value = K>>,
86 K: Borrow<Q>,
87 Q: Ord + ?Sized,
88{
89 type Spec = Spec;
90
91 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
92 node.reborrow()
93 .into_data()
94 .bst_data()
95 .borrow()
96 .cmp(self.key)
97 }
98}
99
100pub struct SeekBySize<Spec> {
101 index: usize,
102 _marker: PhantomData<fn() -> Spec>,
103}
104
105impl<Spec> SeekBySize<Spec> {
106 pub fn new(index: usize) -> Self {
107 Self {
108 index,
109 _marker: PhantomData,
110 }
111 }
112}
113
114impl<Spec> BstSeeker for SeekBySize<Spec>
115where
116 Spec: BstSpec<Data: BstDataAccess<data::marker::Size, Value = usize>>,
117{
118 type Spec = Spec;
119
120 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
121 let lsize = node
122 .reborrow()
123 .left()
124 .descend()
125 .map(|l| *l.into_data().bst_data())
126 .unwrap_or_default();
127 let ord = lsize.cmp(&self.index);
128 if matches!(ord, Ordering::Less) {
129 self.index -= lsize + 1;
130 }
131 ord
132 }
133}
134
135pub struct SeekByAccCond<Spec, L, F>
136where
137 L: LazyMapMonoid,
138{
139 acc: L::Agg,
140 f: F,
141 _marker: PhantomData<fn() -> (Spec, L)>,
142}
143
144impl<Spec, L, F> SeekByAccCond<Spec, L, F>
145where
146 L: LazyMapMonoid,
147 F: FnMut(&L::Agg) -> bool,
148{
149 pub fn new(f: F) -> Self {
150 Self {
151 acc: L::agg_unit(),
152 f,
153 _marker: PhantomData,
154 }
155 }
156}
157
158impl<Spec, L, F> BstSeeker for SeekByAccCond<Spec, L, F>
159where
160 Spec: BstSpec<Data: BstDataAccess<data::marker::LazyMap, Value = LazyMapElement<L>>>,
161 L: LazyMapMonoid,
162 F: FnMut(&L::Agg) -> bool,
163{
164 type Spec = Spec;
165
166 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
167 if let Ok(left) = node.reborrow().left().descend() {
168 let left_agg = &left.into_data().bst_data().agg;
169 let nagg = L::agg_operate(&self.acc, left_agg);
170 if (self.f)(&nagg) {
171 return Ordering::Greater;
172 }
173 let nagg = L::agg_operate(
174 &nagg,
175 &L::single_agg(&node.reborrow().into_data().bst_data().key),
176 );
177 if (self.f)(&nagg) {
178 Ordering::Equal
179 } else {
180 self.acc = nagg;
181 Ordering::Less
182 }
183 } else {
184 let nagg = L::agg_operate(
185 &self.acc,
186 &L::single_agg(&node.reborrow().into_data().bst_data().key),
187 );
188 if (self.f)(&nagg) {
189 Ordering::Equal
190 } else {
191 self.acc = nagg;
192 Ordering::Less
193 }
194 }
195 }
196}
197
198pub struct SeekByRaccCond<Spec, L, F>
199where
200 L: LazyMapMonoid,
201{
202 acc: L::Agg,
203 f: F,
204 _marker: PhantomData<fn() -> (Spec, L)>,
205}
206
207impl<Spec, L, F> SeekByRaccCond<Spec, L, F>
208where
209 L: LazyMapMonoid,
210 F: FnMut(&L::Agg) -> bool,
211{
212 pub fn new(f: F) -> Self {
213 Self {
214 acc: L::agg_unit(),
215 f,
216 _marker: PhantomData,
217 }
218 }
219}
220
221impl<Spec, L, F> BstSeeker for SeekByRaccCond<Spec, L, F>
222where
223 Spec: BstSpec<Data: BstDataAccess<data::marker::LazyMap, Value = LazyMapElement<L>>>,
224 L: LazyMapMonoid,
225 F: FnMut(&L::Agg) -> bool,
226{
227 type Spec = Spec;
228
229 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
230 if let Ok(right) = node.reborrow().right().descend() {
231 let right_agg = &right.into_data().bst_data().agg;
232 let nagg = L::agg_operate(right_agg, &self.acc);
233 if (self.f)(&nagg) {
234 return Ordering::Less;
235 }
236 let nagg = L::agg_operate(
237 &L::single_agg(&node.reborrow().into_data().bst_data().key),
238 &nagg,
239 );
240 if (self.f)(&nagg) {
241 Ordering::Equal
242 } else {
243 self.acc = nagg;
244 Ordering::Greater
245 }
246 } else {
247 let nagg = L::agg_operate(
248 &L::single_agg(&node.reborrow().into_data().bst_data().key),
249 &self.acc,
250 );
251 if (self.f)(&nagg) {
252 Ordering::Equal
253 } else {
254 self.acc = nagg;
255 Ordering::Greater
256 }
257 }
258 }More examples
crates/competitive/src/data_structure/binary_search_tree/data.rs (line 48)
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 L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
148 node.data_mut().bst_data_mut().key =
149 L::act_key(&node.reborrow().into_data().bst_data().key, act);
150 if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
151 node.data_mut().bst_data_mut().agg = nxlazy;
152 } else {
153 Self::top_down(node.reborrow_datamut());
154 Self::bottom_up(node.reborrow_datamut());
155 }
156 }
157
158 pub fn top_down<Spec>(mut node: BstDataMutRef<'_, Spec>)
159 where
160 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
161 {
162 let act = replace(&mut node.data_mut().bst_data_mut().act, L::act_unit());
163 if let Ok(left) = node.reborrow_datamut().left().descend() {
164 Self::update_act(left, &act);
165 }
166 if let Ok(right) = node.reborrow_datamut().right().descend() {
167 Self::update_act(right, &act);
168 }
169 }
170
171 pub fn bottom_up<Spec>(mut node: BstDataMutRef<'_, Spec>)
172 where
173 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
174 {
175 let mut agg = L::single_agg(&node.reborrow().into_data().bst_data().key);
176 if let Ok(left) = node.reborrow().left().descend() {
177 agg = L::agg_operate(&left.into_data().bst_data().agg, &agg);
178 }
179 if let Ok(right) = node.reborrow().right().descend() {
180 agg = L::agg_operate(&agg, &right.into_data().bst_data().agg);
181 }
182 node.data_mut().bst_data_mut().agg = agg;
183 }crates/competitive/src/data_structure/binary_search_tree/node.rs (line 134)
123 pub fn resolve_top_down<Spec>(node: BstNodeRef<marker::DataMut<'_>, Spec>)
124 where
125 Spec: BstSpec<Data = Data, Parent = Self>,
126 {
127 unsafe {
128 let (mut node, mut stack) = node.root_path();
129 while let Some(is_left) = stack.pop() {
130 Spec::top_down(node.reborrow_datamut());
131 if is_left {
132 node = node.left().descend().unwrap_unchecked();
133 } else {
134 node = node.right().descend().unwrap_unchecked();
135 }
136 }
137 Spec::top_down(node.reborrow_datamut());
138 }
139 }
140
141 pub fn resolve_bottom_up<Spec>(mut node: BstNodeRef<marker::DataMut<'_>, Spec>)
142 where
143 Spec: BstSpec<Data = Data, Parent = Self>,
144 {
145 loop {
146 Spec::bottom_up(node.reborrow_datamut());
147 match node.ascend() {
148 Ok(parent) => node = parent,
149 Err(_) => break,
150 }
151 }
152 }
153
154 pub fn is_root<Spec>(node: BstNodeRef<marker::Immut<'_>, Spec>) -> bool
155 where
156 Spec: BstSpec<Data = Data, Parent = Self>,
157 {
158 unsafe { node.node.as_ref().parent.parent.is_none() }
159 }
160
161 pub unsafe fn remove_root<Spec>(
162 root: &mut Option<BstRoot<Spec>>,
163 ) -> Option<BstNodeRef<marker::Owned, Spec>>
164 where
165 Spec: BstSpec<Data = Data, Parent = Self>,
166 {
167 let mut node = root.take()?;
168 unsafe {
169 let left = node.borrow_mut().left_mut().take();
170 let right = node.borrow_mut().right_mut().take();
171 *root = Spec::merge(left, right);
172 Spec::bottom_up(node.borrow_datamut());
173 Some(node)
174 }
175 }
176
177 pub unsafe fn remove_not_root<Spec>(
178 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
179 ) -> BstNodeRef<marker::Owned, Spec>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 assert!(!Self::is_root(node.reborrow()));
184 unsafe {
185 let left = node.left_mut().take();
186 let right = node.right_mut().take();
187 let merged = Spec::merge(left, right);
188 let node_inner = node.node;
189 let mut parent = node.ascend().unwrap_unchecked();
190 let mut node = if let Some(merged) = merged {
191 let node = if parent
192 .reborrow()
193 .left()
194 .descend()
195 .is_ok_and(|n| n.node == node_inner)
196 {
197 parent.left_mut().replace(merged)
198 } else {
199 parent.right_mut().replace(merged)
200 };
201 Self::resolve_bottom_up(parent.reborrow_datamut());
202 node.unwrap_unchecked()
203 } else {
204 let node = if parent
205 .reborrow()
206 .left()
207 .descend()
208 .is_ok_and(|n| n.node == node_inner)
209 {
210 parent.left_mut().take()
211 } else {
212 parent.right_mut().take()
213 };
214 Self::resolve_bottom_up(parent.reborrow_datamut());
215 node.unwrap_unchecked()
216 };
217 Spec::bottom_up(node.borrow_datamut());
218 node
219 }
220 }
221}
222
223pub struct BstNodeRef<BorrowType, Spec>
224where
225 Spec: BstSpec,
226{
227 pub node: NonNull<BstNode<Spec::Data, Spec::Parent>>,
228 _marker: PhantomData<BorrowType>,
229}
230
231impl<'a, Spec> Copy for BstNodeRef<marker::Immut<'a>, Spec> where Spec: BstSpec<Data: 'a> {}
232impl<'a, Spec> Clone for BstNodeRef<marker::Immut<'a>, Spec>
233where
234 Spec: BstSpec<Data: 'a>,
235{
236 fn clone(&self) -> Self {
237 *self
238 }
239}
240
241impl<BorrowType, Spec> BstNodeRef<BorrowType, Spec>
242where
243 Spec: BstSpec,
244 BorrowType: marker::BorrowType,
245{
246 pub unsafe fn new_unchecked(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
247 Self {
248 node,
249 _marker: PhantomData,
250 }
251 }
252 pub fn reborrow(&self) -> BstNodeRef<marker::Immut<'_>, Spec> {
253 BstNodeRef {
254 node: self.node,
255 _marker: PhantomData,
256 }
257 }
258 pub fn left(self) -> BstEdgeHandle<Self, marker::Left> {
259 BstEdgeHandle {
260 node: self,
261 _marker: PhantomData,
262 }
263 }
264 pub fn right(self) -> BstEdgeHandle<Self, marker::Right> {
265 BstEdgeHandle {
266 node: self,
267 _marker: PhantomData,
268 }
269 }
270}
271
272impl<BorrowType, Spec, Data> BstNodeRef<BorrowType, Spec>
273where
274 Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
275 BorrowType: marker::BorrowType,
276{
277 pub fn ascend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self> {
278 const {
279 assert!(BorrowType::TRAVERSAL_PERMIT);
280 };
281 let parent = unsafe { self.node.as_ref().parent.parent };
282 parent
283 .map(|node| BstNodeRef {
284 node,
285 _marker: PhantomData,
286 })
287 .ok_or(self)
288 }
289 pub fn root_path(self) -> (Self, Vec<bool>) {
290 let mut node = self;
291 let mut nn = node.node;
292 let mut stack = vec![];
293 let root = loop {
294 match node.ascend() {
295 Ok(parent) => {
296 node = parent;
297 stack.push(
298 node.reborrow()
299 .left()
300 .descend()
301 .is_ok_and(|node| node.node == nn),
302 );
303 nn = node.node;
304 }
305 Err(node) => {
306 break node;
307 }
308 }
309 };
310 (root, stack)
311 }
312}
313
314impl<Spec> BstNodeRef<marker::Owned, Spec>
315where
316 Spec: BstSpec,
317{
318 pub fn new(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
319 Self {
320 node,
321 _marker: PhantomData,
322 }
323 }
324 pub fn from_data<A>(data: Spec::Data, allocator: &mut A) -> Self
325 where
326 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
327 {
328 Self::new(allocator.allocate(BstNode::new(data)))
329 }
330 pub fn borrow_mut(&mut self) -> BstNodeRef<marker::Mut<'_>, Spec> {
331 BstNodeRef {
332 node: self.node,
333 _marker: PhantomData,
334 }
335 }
336 pub fn borrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
337 BstNodeRef {
338 node: self.node,
339 _marker: PhantomData,
340 }
341 }
342 pub fn into_dying(self) -> BstNodeRef<marker::Dying, Spec> {
343 BstNodeRef {
344 node: self.node,
345 _marker: PhantomData,
346 }
347 }
348}
349
350impl<'a, Spec> BstNodeRef<marker::Immut<'a>, Spec>
351where
352 Spec: BstSpec<Parent: 'a, Data: 'a>,
353{
354 pub fn into_data(self) -> &'a Spec::Data {
355 unsafe { &self.node.as_ref().data }
356 }
357
358 pub fn traverse<F>(self, f: &mut F)
359 where
360 F: FnMut(Self),
361 {
362 if let Ok(left) = self.left().descend() {
363 left.traverse(f);
364 }
365 f(self);
366 if let Ok(right) = self.right().descend() {
367 right.traverse(f);
368 }
369 }
370
371 pub fn leftmost(self) -> Option<Self> {
372 let mut node = self;
373 while let Ok(left) = node.left().descend() {
374 node = left;
375 }
376 Some(node)
377 }
378
379 pub fn rightmost(self) -> Option<Self> {
380 let mut node = self;
381 while let Ok(right) = node.right().descend() {
382 node = right;
383 }
384 Some(node)
385 }
386}
387
388impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
389where
390 Spec: BstSpec,
391{
392 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
393 BstNodeRef {
394 node: self.node,
395 _marker: PhantomData,
396 }
397 }
398 pub fn data_mut(&mut self) -> &mut Spec::Data {
399 unsafe { &mut self.node.as_mut().data }
400 }
401}
402
403impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
404where
405 Spec: BstSpec<Parent: 'a, Data: 'a>,
406{
407 pub fn into_data_mut(mut self) -> &'a mut Spec::Data {
408 unsafe { &mut self.node.as_mut().data }
409 }
410}
411
412impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
413where
414 Spec: BstSpec,
415{
416 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
417 BstNodeRef {
418 node: self.node,
419 _marker: PhantomData,
420 }
421 }
422
423 pub fn left_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Left> {
424 BstEdgeHandle {
425 node: BstNodeRef {
426 node: self.node,
427 _marker: PhantomData,
428 },
429 _marker: PhantomData,
430 }
431 }
432
433 pub fn right_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Right> {
434 BstEdgeHandle {
435 node: BstNodeRef {
436 node: self.node,
437 _marker: PhantomData,
438 },
439 _marker: PhantomData,
440 }
441 }
442}
443
444impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
445where
446 Spec: BstSpec<Data: 'a>,
447{
448 pub fn dormant(self) -> BstNodeRef<marker::DormantMut, Spec> {
449 BstNodeRef {
450 node: self.node,
451 _marker: PhantomData,
452 }
453 }
454}
455
456impl<Spec> BstNodeRef<marker::DormantMut, Spec>
457where
458 Spec: BstSpec,
459{
460 pub unsafe fn awaken<'a>(self) -> BstNodeRef<marker::Mut<'a>, Spec> {
461 BstNodeRef {
462 node: self.node,
463 _marker: PhantomData,
464 }
465 }
466}
467
468impl<Spec> BstNodeRef<marker::Dying, Spec>
469where
470 Spec: BstSpec,
471{
472 pub unsafe fn into_data<A>(self, allocator: &mut A) -> Spec::Data
473 where
474 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
475 {
476 assert!(self.reborrow().left().descend().is_err());
477 assert!(self.reborrow().right().descend().is_err());
478 allocator.deallocate(self.node).data
479 }crates/competitive/src/data_structure/treap.rs (line 127)
117 fn merge(
118 left: Option<TreapRoot<M, L>>,
119 right: Option<TreapRoot<M, L>>,
120 ) -> Option<TreapRoot<M, L>> {
121 match (left, right) {
122 (None, None) => None,
123 (None, Some(node)) | (Some(node), None) => Some(node),
124 (Some(mut left), Some(mut right)) => unsafe {
125 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
126 TreapSpec::top_down(left.borrow_datamut());
127 let lr = left.borrow_mut().right().take();
128 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
129 left.borrow_mut().right().set(lr);
130 TreapSpec::bottom_up(left.borrow_datamut());
131 Some(left)
132 } else {
133 TreapSpec::top_down(right.borrow_datamut());
134 let rl = right.borrow_mut().left().take();
135 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
136 right.borrow_mut().left().set(rl);
137 TreapSpec::bottom_up(right.borrow_datamut());
138 Some(right)
139 }
140 },
141 }
142 }
143
144 fn split<Seeker>(
145 node: Option<TreapRoot<M, L>>,
146 mut seeker: Seeker,
147 eq_left: bool,
148 ) -> (Option<TreapRoot<M, L>>, Option<TreapRoot<M, L>>)
149 where
150 Seeker: BstSeeker<Spec = Self>,
151 {
152 match node {
153 None => (None, None),
154 Some(mut node) => {
155 Self::top_down(node.borrow_datamut());
156 let seek_left = match seeker.bst_seek(node.reborrow()) {
157 Ordering::Less => false,
158 Ordering::Equal => !eq_left,
159 Ordering::Greater => true,
160 };
161 if seek_left {
162 unsafe {
163 let left = node.borrow_mut().left().take();
164 let (l, r) = Self::split(left, seeker, eq_left);
165 if let Some(r) = r {
166 node.borrow_mut().left().set(r);
167 }
168 Self::bottom_up(node.borrow_datamut());
169 (l, Some(node))
170 }
171 } else {
172 unsafe {
173 let right = node.borrow_mut().right().take();
174 let (l, r) = Self::split(right, seeker, eq_left);
175 if let Some(l) = l {
176 node.borrow_mut().right().set(l);
177 }
178 Self::bottom_up(node.borrow_datamut());
179 (Some(node), r)
180 }
181 }
182 }
183 }
184 }
185}
186
187impl<M, L> TreapSpec<M, L>
188where
189 M: MonoidAct<Key: Ord>,
190 L: LazyMapMonoid,
191{
192 pub fn merge_ordered(
193 left: Option<TreapRoot<M, L>>,
194 right: Option<TreapRoot<M, L>>,
195 ) -> Option<TreapRoot<M, L>> {
196 match (left, right) {
197 (None, None) => None,
198 (None, Some(node)) | (Some(node), None) => Some(node),
199 (Some(mut left), Some(mut right)) => unsafe {
200 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
201 Self::top_down(left.borrow_datamut());
202 let key = &left.reborrow().into_data().key.key;
203 let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), false);
204 let ll = left.borrow_mut().left().take();
205 let lr = left.borrow_mut().right().take();
206 if let Some(l) = Self::merge_ordered(ll, rl) {
207 left.borrow_mut().left().set(l);
208 }
209 if let Some(r) = Self::merge_ordered(lr, rr) {
210 left.borrow_mut().right().set(r);
211 }
212 Self::bottom_up(left.borrow_datamut());
213 Some(left)
214 } else {
215 Self::top_down(right.borrow_datamut());
216 let key = &right.reborrow().into_data().key.key;
217 let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), false);
218 let rl = right.borrow_mut().left().take();
219 let rr = right.borrow_mut().right().take();
220 if let Some(l) = Self::merge_ordered(ll, rl) {
221 right.borrow_mut().left().set(l);
222 }
223 if let Some(r) = Self::merge_ordered(lr, rr) {
224 right.borrow_mut().right().set(r);
225 }
226 Self::bottom_up(right.borrow_datamut());
227 Some(right)
228 }
229 },
230 }
231 }Source§impl<BorrowType, Spec, Data> BstNodeRef<BorrowType, Spec>
impl<BorrowType, Spec, Data> BstNodeRef<BorrowType, Spec>
Sourcepub fn ascend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self>
pub fn ascend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 147)
141 pub fn resolve_bottom_up<Spec>(mut node: BstNodeRef<marker::DataMut<'_>, Spec>)
142 where
143 Spec: BstSpec<Data = Data, Parent = Self>,
144 {
145 loop {
146 Spec::bottom_up(node.reborrow_datamut());
147 match node.ascend() {
148 Ok(parent) => node = parent,
149 Err(_) => break,
150 }
151 }
152 }
153
154 pub fn is_root<Spec>(node: BstNodeRef<marker::Immut<'_>, Spec>) -> bool
155 where
156 Spec: BstSpec<Data = Data, Parent = Self>,
157 {
158 unsafe { node.node.as_ref().parent.parent.is_none() }
159 }
160
161 pub unsafe fn remove_root<Spec>(
162 root: &mut Option<BstRoot<Spec>>,
163 ) -> Option<BstNodeRef<marker::Owned, Spec>>
164 where
165 Spec: BstSpec<Data = Data, Parent = Self>,
166 {
167 let mut node = root.take()?;
168 unsafe {
169 let left = node.borrow_mut().left_mut().take();
170 let right = node.borrow_mut().right_mut().take();
171 *root = Spec::merge(left, right);
172 Spec::bottom_up(node.borrow_datamut());
173 Some(node)
174 }
175 }
176
177 pub unsafe fn remove_not_root<Spec>(
178 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
179 ) -> BstNodeRef<marker::Owned, Spec>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 assert!(!Self::is_root(node.reborrow()));
184 unsafe {
185 let left = node.left_mut().take();
186 let right = node.right_mut().take();
187 let merged = Spec::merge(left, right);
188 let node_inner = node.node;
189 let mut parent = node.ascend().unwrap_unchecked();
190 let mut node = if let Some(merged) = merged {
191 let node = if parent
192 .reborrow()
193 .left()
194 .descend()
195 .is_ok_and(|n| n.node == node_inner)
196 {
197 parent.left_mut().replace(merged)
198 } else {
199 parent.right_mut().replace(merged)
200 };
201 Self::resolve_bottom_up(parent.reborrow_datamut());
202 node.unwrap_unchecked()
203 } else {
204 let node = if parent
205 .reborrow()
206 .left()
207 .descend()
208 .is_ok_and(|n| n.node == node_inner)
209 {
210 parent.left_mut().take()
211 } else {
212 parent.right_mut().take()
213 };
214 Self::resolve_bottom_up(parent.reborrow_datamut());
215 node.unwrap_unchecked()
216 };
217 Spec::bottom_up(node.borrow_datamut());
218 node
219 }
220 }
221}
222
223pub struct BstNodeRef<BorrowType, Spec>
224where
225 Spec: BstSpec,
226{
227 pub node: NonNull<BstNode<Spec::Data, Spec::Parent>>,
228 _marker: PhantomData<BorrowType>,
229}
230
231impl<'a, Spec> Copy for BstNodeRef<marker::Immut<'a>, Spec> where Spec: BstSpec<Data: 'a> {}
232impl<'a, Spec> Clone for BstNodeRef<marker::Immut<'a>, Spec>
233where
234 Spec: BstSpec<Data: 'a>,
235{
236 fn clone(&self) -> Self {
237 *self
238 }
239}
240
241impl<BorrowType, Spec> BstNodeRef<BorrowType, Spec>
242where
243 Spec: BstSpec,
244 BorrowType: marker::BorrowType,
245{
246 pub unsafe fn new_unchecked(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
247 Self {
248 node,
249 _marker: PhantomData,
250 }
251 }
252 pub fn reborrow(&self) -> BstNodeRef<marker::Immut<'_>, Spec> {
253 BstNodeRef {
254 node: self.node,
255 _marker: PhantomData,
256 }
257 }
258 pub fn left(self) -> BstEdgeHandle<Self, marker::Left> {
259 BstEdgeHandle {
260 node: self,
261 _marker: PhantomData,
262 }
263 }
264 pub fn right(self) -> BstEdgeHandle<Self, marker::Right> {
265 BstEdgeHandle {
266 node: self,
267 _marker: PhantomData,
268 }
269 }
270}
271
272impl<BorrowType, Spec, Data> BstNodeRef<BorrowType, Spec>
273where
274 Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
275 BorrowType: marker::BorrowType,
276{
277 pub fn ascend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self> {
278 const {
279 assert!(BorrowType::TRAVERSAL_PERMIT);
280 };
281 let parent = unsafe { self.node.as_ref().parent.parent };
282 parent
283 .map(|node| BstNodeRef {
284 node,
285 _marker: PhantomData,
286 })
287 .ok_or(self)
288 }
289 pub fn root_path(self) -> (Self, Vec<bool>) {
290 let mut node = self;
291 let mut nn = node.node;
292 let mut stack = vec![];
293 let root = loop {
294 match node.ascend() {
295 Ok(parent) => {
296 node = parent;
297 stack.push(
298 node.reborrow()
299 .left()
300 .descend()
301 .is_ok_and(|node| node.node == nn),
302 );
303 nn = node.node;
304 }
305 Err(node) => {
306 break node;
307 }
308 }
309 };
310 (root, stack)
311 }Sourcepub fn root_path(self) -> (Self, Vec<bool>)
pub fn root_path(self) -> (Self, Vec<bool>)
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 128)
123 pub fn resolve_top_down<Spec>(node: BstNodeRef<marker::DataMut<'_>, Spec>)
124 where
125 Spec: BstSpec<Data = Data, Parent = Self>,
126 {
127 unsafe {
128 let (mut node, mut stack) = node.root_path();
129 while let Some(is_left) = stack.pop() {
130 Spec::top_down(node.reborrow_datamut());
131 if is_left {
132 node = node.left().descend().unwrap_unchecked();
133 } else {
134 node = node.right().descend().unwrap_unchecked();
135 }
136 }
137 Spec::top_down(node.reborrow_datamut());
138 }
139 }Source§impl<Spec> BstNodeRef<Owned, Spec>where
Spec: BstSpec,
impl<Spec> BstNodeRef<Owned, Spec>where
Spec: BstSpec,
Sourcepub fn new(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self
pub fn new(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 328)
324 pub fn from_data<A>(data: Spec::Data, allocator: &mut A) -> Self
325 where
326 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
327 {
328 Self::new(allocator.allocate(BstNode::new(data)))
329 }
330 pub fn borrow_mut(&mut self) -> BstNodeRef<marker::Mut<'_>, Spec> {
331 BstNodeRef {
332 node: self.node,
333 _marker: PhantomData,
334 }
335 }
336 pub fn borrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
337 BstNodeRef {
338 node: self.node,
339 _marker: PhantomData,
340 }
341 }
342 pub fn into_dying(self) -> BstNodeRef<marker::Dying, Spec> {
343 BstNodeRef {
344 node: self.node,
345 _marker: PhantomData,
346 }
347 }
348}
349
350impl<'a, Spec> BstNodeRef<marker::Immut<'a>, Spec>
351where
352 Spec: BstSpec<Parent: 'a, Data: 'a>,
353{
354 pub fn into_data(self) -> &'a Spec::Data {
355 unsafe { &self.node.as_ref().data }
356 }
357
358 pub fn traverse<F>(self, f: &mut F)
359 where
360 F: FnMut(Self),
361 {
362 if let Ok(left) = self.left().descend() {
363 left.traverse(f);
364 }
365 f(self);
366 if let Ok(right) = self.right().descend() {
367 right.traverse(f);
368 }
369 }
370
371 pub fn leftmost(self) -> Option<Self> {
372 let mut node = self;
373 while let Ok(left) = node.left().descend() {
374 node = left;
375 }
376 Some(node)
377 }
378
379 pub fn rightmost(self) -> Option<Self> {
380 let mut node = self;
381 while let Ok(right) = node.right().descend() {
382 node = right;
383 }
384 Some(node)
385 }
386}
387
388impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
389where
390 Spec: BstSpec,
391{
392 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
393 BstNodeRef {
394 node: self.node,
395 _marker: PhantomData,
396 }
397 }
398 pub fn data_mut(&mut self) -> &mut Spec::Data {
399 unsafe { &mut self.node.as_mut().data }
400 }
401}
402
403impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
404where
405 Spec: BstSpec<Parent: 'a, Data: 'a>,
406{
407 pub fn into_data_mut(mut self) -> &'a mut Spec::Data {
408 unsafe { &mut self.node.as_mut().data }
409 }
410}
411
412impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
413where
414 Spec: BstSpec,
415{
416 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
417 BstNodeRef {
418 node: self.node,
419 _marker: PhantomData,
420 }
421 }
422
423 pub fn left_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Left> {
424 BstEdgeHandle {
425 node: BstNodeRef {
426 node: self.node,
427 _marker: PhantomData,
428 },
429 _marker: PhantomData,
430 }
431 }
432
433 pub fn right_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Right> {
434 BstEdgeHandle {
435 node: BstNodeRef {
436 node: self.node,
437 _marker: PhantomData,
438 },
439 _marker: PhantomData,
440 }
441 }
442}
443
444impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
445where
446 Spec: BstSpec<Data: 'a>,
447{
448 pub fn dormant(self) -> BstNodeRef<marker::DormantMut, Spec> {
449 BstNodeRef {
450 node: self.node,
451 _marker: PhantomData,
452 }
453 }
454}
455
456impl<Spec> BstNodeRef<marker::DormantMut, Spec>
457where
458 Spec: BstSpec,
459{
460 pub unsafe fn awaken<'a>(self) -> BstNodeRef<marker::Mut<'a>, Spec> {
461 BstNodeRef {
462 node: self.node,
463 _marker: PhantomData,
464 }
465 }
466}
467
468impl<Spec> BstNodeRef<marker::Dying, Spec>
469where
470 Spec: BstSpec,
471{
472 pub unsafe fn into_data<A>(self, allocator: &mut A) -> Spec::Data
473 where
474 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
475 {
476 assert!(self.reborrow().left().descend().is_err());
477 assert!(self.reborrow().right().descend().is_err());
478 allocator.deallocate(self.node).data
479 }
480
481 pub unsafe fn drop_all<A>(self, allocator: &mut A)
482 where
483 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
484 {
485 let BstNode { child, .. } = allocator.deallocate(self.node);
486 for node in child.into_iter().flatten() {
487 unsafe {
488 BstNodeRef::<marker::Owned, Spec>::new(node)
489 .into_dying()
490 .drop_all(allocator)
491 }
492 }
493 }Sourcepub fn from_data<A>(data: Spec::Data, allocator: &mut A) -> Self
pub fn from_data<A>(data: Spec::Data, allocator: &mut A) -> Self
Examples found in repository?
crates/competitive/src/data_structure/treap.rs (line 378)
371 pub fn insert(&mut self, key: M::Key, value: L::Key) -> BstNodeId<TreapSpec<M, L>> {
372 let (left, right) = TreapSpec::split(self.root.take(), SeekByKey::new(&key), false);
373 let data = TreapData {
374 priority: self.rng.rand64(),
375 key: MonoidActElement::from_key(key),
376 value: LazyMapElement::from_key(value),
377 };
378 let node = BstRoot::from_data(data, self.allocator.deref_mut());
379 let node_id = self.node_id_manager.register(&node);
380 self.root = TreapSpec::merge(TreapSpec::merge(left, Some(node)), right);
381 node_id
382 }Sourcepub fn borrow_mut(&mut self) -> BstNodeRef<Mut<'_>, Spec>
pub fn borrow_mut(&mut self) -> BstNodeRef<Mut<'_>, Spec>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 169)
161 pub unsafe fn remove_root<Spec>(
162 root: &mut Option<BstRoot<Spec>>,
163 ) -> Option<BstNodeRef<marker::Owned, Spec>>
164 where
165 Spec: BstSpec<Data = Data, Parent = Self>,
166 {
167 let mut node = root.take()?;
168 unsafe {
169 let left = node.borrow_mut().left_mut().take();
170 let right = node.borrow_mut().right_mut().take();
171 *root = Spec::merge(left, right);
172 Spec::bottom_up(node.borrow_datamut());
173 Some(node)
174 }
175 }
176
177 pub unsafe fn remove_not_root<Spec>(
178 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
179 ) -> BstNodeRef<marker::Owned, Spec>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 assert!(!Self::is_root(node.reborrow()));
184 unsafe {
185 let left = node.left_mut().take();
186 let right = node.right_mut().take();
187 let merged = Spec::merge(left, right);
188 let node_inner = node.node;
189 let mut parent = node.ascend().unwrap_unchecked();
190 let mut node = if let Some(merged) = merged {
191 let node = if parent
192 .reborrow()
193 .left()
194 .descend()
195 .is_ok_and(|n| n.node == node_inner)
196 {
197 parent.left_mut().replace(merged)
198 } else {
199 parent.right_mut().replace(merged)
200 };
201 Self::resolve_bottom_up(parent.reborrow_datamut());
202 node.unwrap_unchecked()
203 } else {
204 let node = if parent
205 .reborrow()
206 .left()
207 .descend()
208 .is_ok_and(|n| n.node == node_inner)
209 {
210 parent.left_mut().take()
211 } else {
212 parent.right_mut().take()
213 };
214 Self::resolve_bottom_up(parent.reborrow_datamut());
215 node.unwrap_unchecked()
216 };
217 Spec::bottom_up(node.borrow_datamut());
218 node
219 }
220 }
221}
222
223pub struct BstNodeRef<BorrowType, Spec>
224where
225 Spec: BstSpec,
226{
227 pub node: NonNull<BstNode<Spec::Data, Spec::Parent>>,
228 _marker: PhantomData<BorrowType>,
229}
230
231impl<'a, Spec> Copy for BstNodeRef<marker::Immut<'a>, Spec> where Spec: BstSpec<Data: 'a> {}
232impl<'a, Spec> Clone for BstNodeRef<marker::Immut<'a>, Spec>
233where
234 Spec: BstSpec<Data: 'a>,
235{
236 fn clone(&self) -> Self {
237 *self
238 }
239}
240
241impl<BorrowType, Spec> BstNodeRef<BorrowType, Spec>
242where
243 Spec: BstSpec,
244 BorrowType: marker::BorrowType,
245{
246 pub unsafe fn new_unchecked(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
247 Self {
248 node,
249 _marker: PhantomData,
250 }
251 }
252 pub fn reborrow(&self) -> BstNodeRef<marker::Immut<'_>, Spec> {
253 BstNodeRef {
254 node: self.node,
255 _marker: PhantomData,
256 }
257 }
258 pub fn left(self) -> BstEdgeHandle<Self, marker::Left> {
259 BstEdgeHandle {
260 node: self,
261 _marker: PhantomData,
262 }
263 }
264 pub fn right(self) -> BstEdgeHandle<Self, marker::Right> {
265 BstEdgeHandle {
266 node: self,
267 _marker: PhantomData,
268 }
269 }
270}
271
272impl<BorrowType, Spec, Data> BstNodeRef<BorrowType, Spec>
273where
274 Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
275 BorrowType: marker::BorrowType,
276{
277 pub fn ascend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self> {
278 const {
279 assert!(BorrowType::TRAVERSAL_PERMIT);
280 };
281 let parent = unsafe { self.node.as_ref().parent.parent };
282 parent
283 .map(|node| BstNodeRef {
284 node,
285 _marker: PhantomData,
286 })
287 .ok_or(self)
288 }
289 pub fn root_path(self) -> (Self, Vec<bool>) {
290 let mut node = self;
291 let mut nn = node.node;
292 let mut stack = vec![];
293 let root = loop {
294 match node.ascend() {
295 Ok(parent) => {
296 node = parent;
297 stack.push(
298 node.reborrow()
299 .left()
300 .descend()
301 .is_ok_and(|node| node.node == nn),
302 );
303 nn = node.node;
304 }
305 Err(node) => {
306 break node;
307 }
308 }
309 };
310 (root, stack)
311 }
312}
313
314impl<Spec> BstNodeRef<marker::Owned, Spec>
315where
316 Spec: BstSpec,
317{
318 pub fn new(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
319 Self {
320 node,
321 _marker: PhantomData,
322 }
323 }
324 pub fn from_data<A>(data: Spec::Data, allocator: &mut A) -> Self
325 where
326 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
327 {
328 Self::new(allocator.allocate(BstNode::new(data)))
329 }
330 pub fn borrow_mut(&mut self) -> BstNodeRef<marker::Mut<'_>, Spec> {
331 BstNodeRef {
332 node: self.node,
333 _marker: PhantomData,
334 }
335 }
336 pub fn borrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
337 BstNodeRef {
338 node: self.node,
339 _marker: PhantomData,
340 }
341 }
342 pub fn into_dying(self) -> BstNodeRef<marker::Dying, Spec> {
343 BstNodeRef {
344 node: self.node,
345 _marker: PhantomData,
346 }
347 }
348}
349
350impl<'a, Spec> BstNodeRef<marker::Immut<'a>, Spec>
351where
352 Spec: BstSpec<Parent: 'a, Data: 'a>,
353{
354 pub fn into_data(self) -> &'a Spec::Data {
355 unsafe { &self.node.as_ref().data }
356 }
357
358 pub fn traverse<F>(self, f: &mut F)
359 where
360 F: FnMut(Self),
361 {
362 if let Ok(left) = self.left().descend() {
363 left.traverse(f);
364 }
365 f(self);
366 if let Ok(right) = self.right().descend() {
367 right.traverse(f);
368 }
369 }
370
371 pub fn leftmost(self) -> Option<Self> {
372 let mut node = self;
373 while let Ok(left) = node.left().descend() {
374 node = left;
375 }
376 Some(node)
377 }
378
379 pub fn rightmost(self) -> Option<Self> {
380 let mut node = self;
381 while let Ok(right) = node.right().descend() {
382 node = right;
383 }
384 Some(node)
385 }
386}
387
388impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
389where
390 Spec: BstSpec,
391{
392 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
393 BstNodeRef {
394 node: self.node,
395 _marker: PhantomData,
396 }
397 }
398 pub fn data_mut(&mut self) -> &mut Spec::Data {
399 unsafe { &mut self.node.as_mut().data }
400 }
401}
402
403impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
404where
405 Spec: BstSpec<Parent: 'a, Data: 'a>,
406{
407 pub fn into_data_mut(mut self) -> &'a mut Spec::Data {
408 unsafe { &mut self.node.as_mut().data }
409 }
410}
411
412impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
413where
414 Spec: BstSpec,
415{
416 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
417 BstNodeRef {
418 node: self.node,
419 _marker: PhantomData,
420 }
421 }
422
423 pub fn left_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Left> {
424 BstEdgeHandle {
425 node: BstNodeRef {
426 node: self.node,
427 _marker: PhantomData,
428 },
429 _marker: PhantomData,
430 }
431 }
432
433 pub fn right_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Right> {
434 BstEdgeHandle {
435 node: BstNodeRef {
436 node: self.node,
437 _marker: PhantomData,
438 },
439 _marker: PhantomData,
440 }
441 }
442}
443
444impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
445where
446 Spec: BstSpec<Data: 'a>,
447{
448 pub fn dormant(self) -> BstNodeRef<marker::DormantMut, Spec> {
449 BstNodeRef {
450 node: self.node,
451 _marker: PhantomData,
452 }
453 }
454}
455
456impl<Spec> BstNodeRef<marker::DormantMut, Spec>
457where
458 Spec: BstSpec,
459{
460 pub unsafe fn awaken<'a>(self) -> BstNodeRef<marker::Mut<'a>, Spec> {
461 BstNodeRef {
462 node: self.node,
463 _marker: PhantomData,
464 }
465 }
466}
467
468impl<Spec> BstNodeRef<marker::Dying, Spec>
469where
470 Spec: BstSpec,
471{
472 pub unsafe fn into_data<A>(self, allocator: &mut A) -> Spec::Data
473 where
474 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
475 {
476 assert!(self.reborrow().left().descend().is_err());
477 assert!(self.reborrow().right().descend().is_err());
478 allocator.deallocate(self.node).data
479 }
480
481 pub unsafe fn drop_all<A>(self, allocator: &mut A)
482 where
483 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
484 {
485 let BstNode { child, .. } = allocator.deallocate(self.node);
486 for node in child.into_iter().flatten() {
487 unsafe {
488 BstNodeRef::<marker::Owned, Spec>::new(node)
489 .into_dying()
490 .drop_all(allocator)
491 }
492 }
493 }
494}
495
496pub struct BstEdgeHandle<Node, Dir> {
497 node: Node,
498 _marker: PhantomData<Dir>,
499}
500
501impl<BorrowType, Spec, Dir> BstEdgeHandle<BstNodeRef<BorrowType, Spec>, Dir>
502where
503 Spec: BstSpec,
504 BorrowType: marker::BorrowType,
505 Dir: marker::BstDirection,
506{
507 pub fn descend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self> {
508 const {
509 assert!(BorrowType::TRAVERSAL_PERMIT);
510 };
511 let child = unsafe { self.node.node.as_ref().child.get_unchecked(Dir::IDX) };
512 child
513 .map(|node| BstNodeRef {
514 node,
515 _marker: PhantomData,
516 })
517 .ok_or(self)
518 }
519}
520
521impl<'a, Spec, Dir> BstEdgeHandle<BstNodeRef<marker::Mut<'a>, Spec>, Dir>
522where
523 Spec: BstSpec,
524 Dir: marker::BstDirection,
525{
526 pub unsafe fn take(&mut self) -> Option<BstNodeRef<marker::Owned, Spec>> {
527 let child = unsafe { self.node.node.as_mut().child.get_unchecked_mut(Dir::IDX) };
528 child.take().map(|node| {
529 let mut node = BstNodeRef {
530 node,
531 _marker: PhantomData,
532 };
533 Spec::Parent::take_parent(node.borrow_mut());
534 node
535 })
536 }
537 pub unsafe fn replace(
538 &mut self,
539 mut other: BstNodeRef<marker::Owned, Spec>,
540 ) -> Option<BstNodeRef<marker::Owned, Spec>> {
541 let child = unsafe { self.node.node.as_mut().child.get_unchecked_mut(Dir::IDX) };
542 Spec::Parent::set_parent(other.borrow_mut(), Some(self.node.node));
543 child.replace(other.node).map(|node| {
544 let mut node = BstNodeRef {
545 node,
546 _marker: PhantomData,
547 };
548 Spec::Parent::take_parent(node.borrow_mut());
549 node
550 })
551 }
552 pub unsafe fn set(&mut self, mut other: BstNodeRef<marker::Owned, Spec>) {
553 let child = unsafe { self.node.node.as_mut().child.get_unchecked_mut(Dir::IDX) };
554 Spec::Parent::set_parent(other.borrow_mut(), Some(self.node.node));
555 *child = Some(other.node);
556 }More examples
crates/competitive/src/data_structure/treap.rs (line 127)
117 fn merge(
118 left: Option<TreapRoot<M, L>>,
119 right: Option<TreapRoot<M, L>>,
120 ) -> Option<TreapRoot<M, L>> {
121 match (left, right) {
122 (None, None) => None,
123 (None, Some(node)) | (Some(node), None) => Some(node),
124 (Some(mut left), Some(mut right)) => unsafe {
125 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
126 TreapSpec::top_down(left.borrow_datamut());
127 let lr = left.borrow_mut().right().take();
128 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
129 left.borrow_mut().right().set(lr);
130 TreapSpec::bottom_up(left.borrow_datamut());
131 Some(left)
132 } else {
133 TreapSpec::top_down(right.borrow_datamut());
134 let rl = right.borrow_mut().left().take();
135 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
136 right.borrow_mut().left().set(rl);
137 TreapSpec::bottom_up(right.borrow_datamut());
138 Some(right)
139 }
140 },
141 }
142 }
143
144 fn split<Seeker>(
145 node: Option<TreapRoot<M, L>>,
146 mut seeker: Seeker,
147 eq_left: bool,
148 ) -> (Option<TreapRoot<M, L>>, Option<TreapRoot<M, L>>)
149 where
150 Seeker: BstSeeker<Spec = Self>,
151 {
152 match node {
153 None => (None, None),
154 Some(mut node) => {
155 Self::top_down(node.borrow_datamut());
156 let seek_left = match seeker.bst_seek(node.reborrow()) {
157 Ordering::Less => false,
158 Ordering::Equal => !eq_left,
159 Ordering::Greater => true,
160 };
161 if seek_left {
162 unsafe {
163 let left = node.borrow_mut().left().take();
164 let (l, r) = Self::split(left, seeker, eq_left);
165 if let Some(r) = r {
166 node.borrow_mut().left().set(r);
167 }
168 Self::bottom_up(node.borrow_datamut());
169 (l, Some(node))
170 }
171 } else {
172 unsafe {
173 let right = node.borrow_mut().right().take();
174 let (l, r) = Self::split(right, seeker, eq_left);
175 if let Some(l) = l {
176 node.borrow_mut().right().set(l);
177 }
178 Self::bottom_up(node.borrow_datamut());
179 (Some(node), r)
180 }
181 }
182 }
183 }
184 }
185}
186
187impl<M, L> TreapSpec<M, L>
188where
189 M: MonoidAct<Key: Ord>,
190 L: LazyMapMonoid,
191{
192 pub fn merge_ordered(
193 left: Option<TreapRoot<M, L>>,
194 right: Option<TreapRoot<M, L>>,
195 ) -> Option<TreapRoot<M, L>> {
196 match (left, right) {
197 (None, None) => None,
198 (None, Some(node)) | (Some(node), None) => Some(node),
199 (Some(mut left), Some(mut right)) => unsafe {
200 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
201 Self::top_down(left.borrow_datamut());
202 let key = &left.reborrow().into_data().key.key;
203 let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), false);
204 let ll = left.borrow_mut().left().take();
205 let lr = left.borrow_mut().right().take();
206 if let Some(l) = Self::merge_ordered(ll, rl) {
207 left.borrow_mut().left().set(l);
208 }
209 if let Some(r) = Self::merge_ordered(lr, rr) {
210 left.borrow_mut().right().set(r);
211 }
212 Self::bottom_up(left.borrow_datamut());
213 Some(left)
214 } else {
215 Self::top_down(right.borrow_datamut());
216 let key = &right.reborrow().into_data().key.key;
217 let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), false);
218 let rl = right.borrow_mut().left().take();
219 let rr = right.borrow_mut().right().take();
220 if let Some(l) = Self::merge_ordered(ll, rl) {
221 right.borrow_mut().left().set(l);
222 }
223 if let Some(r) = Self::merge_ordered(lr, rr) {
224 right.borrow_mut().right().set(r);
225 }
226 Self::bottom_up(right.borrow_datamut());
227 Some(right)
228 }
229 },
230 }
231 }Sourcepub fn borrow_datamut(&mut self) -> BstNodeRef<DataMut<'_>, Spec>
pub fn borrow_datamut(&mut self) -> BstNodeRef<DataMut<'_>, Spec>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/split.rs (line 45)
44 pub fn left_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>> {
45 self.left.as_mut().map(|node| node.borrow_datamut())
46 }
47
48 pub fn right_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>> {
49 self.right.as_mut().map(|node| node.borrow_datamut())
50 }
51
52 pub fn manually_merge<F>(&mut self, mut f: F)
53 where
54 F: FnMut(Option<BstRoot<Spec>>, Option<BstRoot<Spec>>) -> Option<BstRoot<Spec>>,
55 {
56 self.left = f(self.left.take(), self.right.take());
57 }
58}
59
60impl<'a, Spec> Drop for Split<'a, Spec>
61where
62 Spec: BstSpec,
63{
64 fn drop(&mut self) {
65 *self.root = Spec::merge(self.left.take(), self.right.take());
66 }
67}
68
69pub struct Split3<'a, Spec>
70where
71 Spec: BstSpec,
72{
73 left: Option<BstRoot<Spec>>,
74 mid: Option<BstRoot<Spec>>,
75 right: Option<BstRoot<Spec>>,
76 root: &'a mut Option<BstRoot<Spec>>,
77}
78
79impl<'a, Spec> Split3<'a, Spec>
80where
81 Spec: BstSpec,
82{
83 pub fn new<Seek1, Seek2>(
84 node: &'a mut Option<BstRoot<Spec>>,
85 start: Bound<Seek1>,
86 end: Bound<Seek2>,
87 ) -> Self
88 where
89 Seek1: BstSeeker<Spec = Spec>,
90 Seek2: BstSeeker<Spec = Spec>,
91 {
92 let (mut rest, right) = match end {
93 Bound::Included(seeker) => Spec::split(node.take(), seeker, true),
94 Bound::Excluded(seeker) => Spec::split(node.take(), seeker, false),
95 Bound::Unbounded => (node.take(), None),
96 };
97 let (left, mid) = match start {
98 Bound::Included(seeker) => Spec::split(rest.take(), seeker, false),
99 Bound::Excluded(seeker) => Spec::split(rest.take(), seeker, true),
100 Bound::Unbounded => (None, rest),
101 };
102 Self {
103 left,
104 mid,
105 right,
106 root: node,
107 }
108 }
109
110 pub fn left(&self) -> Option<BstImmutRef<'_, Spec>> {
111 self.left.as_ref().map(|node| node.reborrow())
112 }
113
114 pub fn mid(&self) -> Option<BstImmutRef<'_, Spec>> {
115 self.mid.as_ref().map(|node| node.reborrow())
116 }
117
118 pub fn right(&self) -> Option<BstImmutRef<'_, Spec>> {
119 self.right.as_ref().map(|node| node.reborrow())
120 }
121
122 pub fn left_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>> {
123 self.left.as_mut().map(|node| node.borrow_datamut())
124 }
125
126 pub fn mid_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>> {
127 self.mid.as_mut().map(|node| node.borrow_datamut())
128 }
129
130 pub fn right_datamut(&mut self) -> Option<BstDataMutRef<'_, Spec>> {
131 self.right.as_mut().map(|node| node.borrow_datamut())
132 }More examples
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 172)
161 pub unsafe fn remove_root<Spec>(
162 root: &mut Option<BstRoot<Spec>>,
163 ) -> Option<BstNodeRef<marker::Owned, Spec>>
164 where
165 Spec: BstSpec<Data = Data, Parent = Self>,
166 {
167 let mut node = root.take()?;
168 unsafe {
169 let left = node.borrow_mut().left_mut().take();
170 let right = node.borrow_mut().right_mut().take();
171 *root = Spec::merge(left, right);
172 Spec::bottom_up(node.borrow_datamut());
173 Some(node)
174 }
175 }
176
177 pub unsafe fn remove_not_root<Spec>(
178 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
179 ) -> BstNodeRef<marker::Owned, Spec>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 assert!(!Self::is_root(node.reborrow()));
184 unsafe {
185 let left = node.left_mut().take();
186 let right = node.right_mut().take();
187 let merged = Spec::merge(left, right);
188 let node_inner = node.node;
189 let mut parent = node.ascend().unwrap_unchecked();
190 let mut node = if let Some(merged) = merged {
191 let node = if parent
192 .reborrow()
193 .left()
194 .descend()
195 .is_ok_and(|n| n.node == node_inner)
196 {
197 parent.left_mut().replace(merged)
198 } else {
199 parent.right_mut().replace(merged)
200 };
201 Self::resolve_bottom_up(parent.reborrow_datamut());
202 node.unwrap_unchecked()
203 } else {
204 let node = if parent
205 .reborrow()
206 .left()
207 .descend()
208 .is_ok_and(|n| n.node == node_inner)
209 {
210 parent.left_mut().take()
211 } else {
212 parent.right_mut().take()
213 };
214 Self::resolve_bottom_up(parent.reborrow_datamut());
215 node.unwrap_unchecked()
216 };
217 Spec::bottom_up(node.borrow_datamut());
218 node
219 }
220 }crates/competitive/src/data_structure/treap.rs (line 126)
117 fn merge(
118 left: Option<TreapRoot<M, L>>,
119 right: Option<TreapRoot<M, L>>,
120 ) -> Option<TreapRoot<M, L>> {
121 match (left, right) {
122 (None, None) => None,
123 (None, Some(node)) | (Some(node), None) => Some(node),
124 (Some(mut left), Some(mut right)) => unsafe {
125 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
126 TreapSpec::top_down(left.borrow_datamut());
127 let lr = left.borrow_mut().right().take();
128 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
129 left.borrow_mut().right().set(lr);
130 TreapSpec::bottom_up(left.borrow_datamut());
131 Some(left)
132 } else {
133 TreapSpec::top_down(right.borrow_datamut());
134 let rl = right.borrow_mut().left().take();
135 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
136 right.borrow_mut().left().set(rl);
137 TreapSpec::bottom_up(right.borrow_datamut());
138 Some(right)
139 }
140 },
141 }
142 }
143
144 fn split<Seeker>(
145 node: Option<TreapRoot<M, L>>,
146 mut seeker: Seeker,
147 eq_left: bool,
148 ) -> (Option<TreapRoot<M, L>>, Option<TreapRoot<M, L>>)
149 where
150 Seeker: BstSeeker<Spec = Self>,
151 {
152 match node {
153 None => (None, None),
154 Some(mut node) => {
155 Self::top_down(node.borrow_datamut());
156 let seek_left = match seeker.bst_seek(node.reborrow()) {
157 Ordering::Less => false,
158 Ordering::Equal => !eq_left,
159 Ordering::Greater => true,
160 };
161 if seek_left {
162 unsafe {
163 let left = node.borrow_mut().left().take();
164 let (l, r) = Self::split(left, seeker, eq_left);
165 if let Some(r) = r {
166 node.borrow_mut().left().set(r);
167 }
168 Self::bottom_up(node.borrow_datamut());
169 (l, Some(node))
170 }
171 } else {
172 unsafe {
173 let right = node.borrow_mut().right().take();
174 let (l, r) = Self::split(right, seeker, eq_left);
175 if let Some(l) = l {
176 node.borrow_mut().right().set(l);
177 }
178 Self::bottom_up(node.borrow_datamut());
179 (Some(node), r)
180 }
181 }
182 }
183 }
184 }
185}
186
187impl<M, L> TreapSpec<M, L>
188where
189 M: MonoidAct<Key: Ord>,
190 L: LazyMapMonoid,
191{
192 pub fn merge_ordered(
193 left: Option<TreapRoot<M, L>>,
194 right: Option<TreapRoot<M, L>>,
195 ) -> Option<TreapRoot<M, L>> {
196 match (left, right) {
197 (None, None) => None,
198 (None, Some(node)) | (Some(node), None) => Some(node),
199 (Some(mut left), Some(mut right)) => unsafe {
200 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
201 Self::top_down(left.borrow_datamut());
202 let key = &left.reborrow().into_data().key.key;
203 let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), false);
204 let ll = left.borrow_mut().left().take();
205 let lr = left.borrow_mut().right().take();
206 if let Some(l) = Self::merge_ordered(ll, rl) {
207 left.borrow_mut().left().set(l);
208 }
209 if let Some(r) = Self::merge_ordered(lr, rr) {
210 left.borrow_mut().right().set(r);
211 }
212 Self::bottom_up(left.borrow_datamut());
213 Some(left)
214 } else {
215 Self::top_down(right.borrow_datamut());
216 let key = &right.reborrow().into_data().key.key;
217 let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), false);
218 let rl = right.borrow_mut().left().take();
219 let rr = right.borrow_mut().right().take();
220 if let Some(l) = Self::merge_ordered(ll, rl) {
221 right.borrow_mut().left().set(l);
222 }
223 if let Some(r) = Self::merge_ordered(lr, rr) {
224 right.borrow_mut().right().set(r);
225 }
226 Self::bottom_up(right.borrow_datamut());
227 Some(right)
228 }
229 },
230 }
231 }
232}
233
234pub struct Treap<M, L, A = BoxAllocator<TreapNode<M, L>>>
235where
236 M: MonoidAct<Key: Ord>,
237 L: LazyMapMonoid,
238 A: Allocator<TreapNode<M, L>>,
239{
240 root: Option<TreapRoot<M, L>>,
241 node_id_manager: BstNodeIdManager<TreapSpec<M, L>>,
242 rng: Xorshift,
243 allocator: ManuallyDrop<A>,
244 _marker: PhantomData<(M, L)>,
245}
246
247impl<M, L, A> Default for Treap<M, L, A>
248where
249 M: MonoidAct<Key: Ord>,
250 L: LazyMapMonoid,
251 A: Allocator<TreapNode<M, L>> + Default,
252{
253 fn default() -> Self {
254 Self {
255 root: None,
256 node_id_manager: Default::default(),
257 rng: Xorshift::new(),
258 allocator: ManuallyDrop::new(A::default()),
259 _marker: PhantomData,
260 }
261 }
262}
263
264impl<M, L, A> Drop for Treap<M, L, A>
265where
266 M: MonoidAct<Key: Ord>,
267 L: LazyMapMonoid,
268 A: Allocator<TreapNode<M, L>>,
269{
270 fn drop(&mut self) {
271 unsafe {
272 if let Some(root) = self.root.take() {
273 root.into_dying().drop_all(self.allocator.deref_mut());
274 }
275 ManuallyDrop::drop(&mut self.allocator);
276 }
277 }
278}
279
280impl<M, L> Treap<M, L>
281where
282 M: MonoidAct<Key: Ord>,
283 L: LazyMapMonoid,
284{
285 pub fn new() -> Self {
286 Self::default()
287 }
288}
289
290impl<M, L, A> Treap<M, L, A>
291where
292 M: MonoidAct<Key: Ord>,
293 L: LazyMapMonoid,
294 A: Allocator<TreapNode<M, L>>,
295{
296 pub fn len(&self) -> usize {
297 self.node_id_manager.len()
298 }
299
300 pub fn is_empty(&self) -> bool {
301 self.node_id_manager.is_empty()
302 }
303
304 pub fn clear(&mut self) {
305 unsafe {
306 if let Some(root) = self.root.take() {
307 root.into_dying().drop_all(self.allocator.deref_mut());
308 }
309 self.node_id_manager.clear();
310 }
311 }
312
313 pub fn get(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(&M::Key, &L::Key)> {
314 if !self.node_id_manager.contains(&node_id) {
315 return None;
316 }
317 unsafe {
318 WithParent::resolve_top_down::<TreapSpec<M, L>>(
319 node_id.reborrow_datamut(&mut self.root),
320 );
321 let data = node_id.reborrow(&self.root).into_data();
322 Some((&data.key.key, &data.value.key))
323 }
324 }
325
326 pub fn change(
327 &mut self,
328 node_id: BstNodeId<TreapSpec<M, L>>,
329 f: impl FnOnce(&mut L::Key),
330 ) -> bool {
331 if !self.node_id_manager.contains(&node_id) {
332 return false;
333 }
334 unsafe {
335 WithParent::resolve_top_down::<TreapSpec<M, L>>(
336 node_id.reborrow_datamut(&mut self.root),
337 );
338 let data = node_id.reborrow_datamut(&mut self.root).into_data_mut();
339 f(&mut data.value.key);
340 WithParent::resolve_bottom_up::<TreapSpec<M, L>>(
341 node_id.reborrow_datamut(&mut self.root),
342 );
343 }
344 true
345 }
346
347 pub fn change_key_value(
348 &mut self,
349 node_id: BstNodeId<TreapSpec<M, L>>,
350 f: impl FnOnce(&mut M::Key, &mut L::Key),
351 ) -> bool {
352 if !self.node_id_manager.contains(&node_id) {
353 return false;
354 }
355 unsafe {
356 WithParent::resolve_top_down::<TreapSpec<M, L>>(
357 node_id.reborrow_datamut(&mut self.root),
358 );
359 let mut node = if WithParent::is_root(node_id.reborrow(&self.root)) {
360 WithParent::remove_root(&mut self.root).unwrap_unchecked()
361 } else {
362 WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
363 };
364 let data = node.borrow_datamut().into_data_mut();
365 f(&mut data.key.key, &mut data.value.key);
366 self.root = TreapSpec::merge_ordered(self.root.take(), Some(node));
367 true
368 }
369 }Sourcepub fn into_dying(self) -> BstNodeRef<Dying, Spec>
pub fn into_dying(self) -> BstNodeRef<Dying, Spec>
Examples found in repository?
crates/competitive/src/data_structure/treap.rs (line 273)
270 fn drop(&mut self) {
271 unsafe {
272 if let Some(root) = self.root.take() {
273 root.into_dying().drop_all(self.allocator.deref_mut());
274 }
275 ManuallyDrop::drop(&mut self.allocator);
276 }
277 }
278}
279
280impl<M, L> Treap<M, L>
281where
282 M: MonoidAct<Key: Ord>,
283 L: LazyMapMonoid,
284{
285 pub fn new() -> Self {
286 Self::default()
287 }
288}
289
290impl<M, L, A> Treap<M, L, A>
291where
292 M: MonoidAct<Key: Ord>,
293 L: LazyMapMonoid,
294 A: Allocator<TreapNode<M, L>>,
295{
296 pub fn len(&self) -> usize {
297 self.node_id_manager.len()
298 }
299
300 pub fn is_empty(&self) -> bool {
301 self.node_id_manager.is_empty()
302 }
303
304 pub fn clear(&mut self) {
305 unsafe {
306 if let Some(root) = self.root.take() {
307 root.into_dying().drop_all(self.allocator.deref_mut());
308 }
309 self.node_id_manager.clear();
310 }
311 }
312
313 pub fn get(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(&M::Key, &L::Key)> {
314 if !self.node_id_manager.contains(&node_id) {
315 return None;
316 }
317 unsafe {
318 WithParent::resolve_top_down::<TreapSpec<M, L>>(
319 node_id.reborrow_datamut(&mut self.root),
320 );
321 let data = node_id.reborrow(&self.root).into_data();
322 Some((&data.key.key, &data.value.key))
323 }
324 }
325
326 pub fn change(
327 &mut self,
328 node_id: BstNodeId<TreapSpec<M, L>>,
329 f: impl FnOnce(&mut L::Key),
330 ) -> bool {
331 if !self.node_id_manager.contains(&node_id) {
332 return false;
333 }
334 unsafe {
335 WithParent::resolve_top_down::<TreapSpec<M, L>>(
336 node_id.reborrow_datamut(&mut self.root),
337 );
338 let data = node_id.reborrow_datamut(&mut self.root).into_data_mut();
339 f(&mut data.value.key);
340 WithParent::resolve_bottom_up::<TreapSpec<M, L>>(
341 node_id.reborrow_datamut(&mut self.root),
342 );
343 }
344 true
345 }
346
347 pub fn change_key_value(
348 &mut self,
349 node_id: BstNodeId<TreapSpec<M, L>>,
350 f: impl FnOnce(&mut M::Key, &mut L::Key),
351 ) -> bool {
352 if !self.node_id_manager.contains(&node_id) {
353 return false;
354 }
355 unsafe {
356 WithParent::resolve_top_down::<TreapSpec<M, L>>(
357 node_id.reborrow_datamut(&mut self.root),
358 );
359 let mut node = if WithParent::is_root(node_id.reborrow(&self.root)) {
360 WithParent::remove_root(&mut self.root).unwrap_unchecked()
361 } else {
362 WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
363 };
364 let data = node.borrow_datamut().into_data_mut();
365 f(&mut data.key.key, &mut data.value.key);
366 self.root = TreapSpec::merge_ordered(self.root.take(), Some(node));
367 true
368 }
369 }
370
371 pub fn insert(&mut self, key: M::Key, value: L::Key) -> BstNodeId<TreapSpec<M, L>> {
372 let (left, right) = TreapSpec::split(self.root.take(), SeekByKey::new(&key), false);
373 let data = TreapData {
374 priority: self.rng.rand64(),
375 key: MonoidActElement::from_key(key),
376 value: LazyMapElement::from_key(value),
377 };
378 let node = BstRoot::from_data(data, self.allocator.deref_mut());
379 let node_id = self.node_id_manager.register(&node);
380 self.root = TreapSpec::merge(TreapSpec::merge(left, Some(node)), right);
381 node_id
382 }
383
384 pub fn remove(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(M::Key, L::Key)> {
385 if !self.node_id_manager.contains(&node_id) {
386 return None;
387 }
388 unsafe {
389 WithParent::resolve_top_down::<TreapSpec<M, L>>(
390 node_id.reborrow_datamut(&mut self.root),
391 );
392 let node = if WithParent::is_root(node_id.reborrow(&self.root)) {
393 WithParent::remove_root(&mut self.root).unwrap_unchecked()
394 } else {
395 WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
396 };
397 self.node_id_manager.unregister(node_id);
398 let data = node.into_dying().into_data(self.allocator.deref_mut());
399 Some((data.key.key, data.value.key))
400 }
401 }More examples
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 489)
481 pub unsafe fn drop_all<A>(self, allocator: &mut A)
482 where
483 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
484 {
485 let BstNode { child, .. } = allocator.deallocate(self.node);
486 for node in child.into_iter().flatten() {
487 unsafe {
488 BstNodeRef::<marker::Owned, Spec>::new(node)
489 .into_dying()
490 .drop_all(allocator)
491 }
492 }
493 }Source§impl<'a, Spec> BstNodeRef<Immut<'a>, Spec>where
Spec: BstSpec<Parent: 'a, Data: 'a>,
impl<'a, Spec> BstNodeRef<Immut<'a>, Spec>where
Spec: BstSpec<Parent: 'a, Data: 'a>,
Sourcepub fn into_data(self) -> &'a Spec::Data
pub fn into_data(self) -> &'a Spec::Data
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/seeker.rs (line 93)
91 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
92 node.reborrow()
93 .into_data()
94 .bst_data()
95 .borrow()
96 .cmp(self.key)
97 }
98}
99
100pub struct SeekBySize<Spec> {
101 index: usize,
102 _marker: PhantomData<fn() -> Spec>,
103}
104
105impl<Spec> SeekBySize<Spec> {
106 pub fn new(index: usize) -> Self {
107 Self {
108 index,
109 _marker: PhantomData,
110 }
111 }
112}
113
114impl<Spec> BstSeeker for SeekBySize<Spec>
115where
116 Spec: BstSpec<Data: BstDataAccess<data::marker::Size, Value = usize>>,
117{
118 type Spec = Spec;
119
120 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
121 let lsize = node
122 .reborrow()
123 .left()
124 .descend()
125 .map(|l| *l.into_data().bst_data())
126 .unwrap_or_default();
127 let ord = lsize.cmp(&self.index);
128 if matches!(ord, Ordering::Less) {
129 self.index -= lsize + 1;
130 }
131 ord
132 }
133}
134
135pub struct SeekByAccCond<Spec, L, F>
136where
137 L: LazyMapMonoid,
138{
139 acc: L::Agg,
140 f: F,
141 _marker: PhantomData<fn() -> (Spec, L)>,
142}
143
144impl<Spec, L, F> SeekByAccCond<Spec, L, F>
145where
146 L: LazyMapMonoid,
147 F: FnMut(&L::Agg) -> bool,
148{
149 pub fn new(f: F) -> Self {
150 Self {
151 acc: L::agg_unit(),
152 f,
153 _marker: PhantomData,
154 }
155 }
156}
157
158impl<Spec, L, F> BstSeeker for SeekByAccCond<Spec, L, F>
159where
160 Spec: BstSpec<Data: BstDataAccess<data::marker::LazyMap, Value = LazyMapElement<L>>>,
161 L: LazyMapMonoid,
162 F: FnMut(&L::Agg) -> bool,
163{
164 type Spec = Spec;
165
166 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
167 if let Ok(left) = node.reborrow().left().descend() {
168 let left_agg = &left.into_data().bst_data().agg;
169 let nagg = L::agg_operate(&self.acc, left_agg);
170 if (self.f)(&nagg) {
171 return Ordering::Greater;
172 }
173 let nagg = L::agg_operate(
174 &nagg,
175 &L::single_agg(&node.reborrow().into_data().bst_data().key),
176 );
177 if (self.f)(&nagg) {
178 Ordering::Equal
179 } else {
180 self.acc = nagg;
181 Ordering::Less
182 }
183 } else {
184 let nagg = L::agg_operate(
185 &self.acc,
186 &L::single_agg(&node.reborrow().into_data().bst_data().key),
187 );
188 if (self.f)(&nagg) {
189 Ordering::Equal
190 } else {
191 self.acc = nagg;
192 Ordering::Less
193 }
194 }
195 }
196}
197
198pub struct SeekByRaccCond<Spec, L, F>
199where
200 L: LazyMapMonoid,
201{
202 acc: L::Agg,
203 f: F,
204 _marker: PhantomData<fn() -> (Spec, L)>,
205}
206
207impl<Spec, L, F> SeekByRaccCond<Spec, L, F>
208where
209 L: LazyMapMonoid,
210 F: FnMut(&L::Agg) -> bool,
211{
212 pub fn new(f: F) -> Self {
213 Self {
214 acc: L::agg_unit(),
215 f,
216 _marker: PhantomData,
217 }
218 }
219}
220
221impl<Spec, L, F> BstSeeker for SeekByRaccCond<Spec, L, F>
222where
223 Spec: BstSpec<Data: BstDataAccess<data::marker::LazyMap, Value = LazyMapElement<L>>>,
224 L: LazyMapMonoid,
225 F: FnMut(&L::Agg) -> bool,
226{
227 type Spec = Spec;
228
229 fn bst_seek(&mut self, node: BstImmutRef<'_, Self::Spec>) -> Ordering {
230 if let Ok(right) = node.reborrow().right().descend() {
231 let right_agg = &right.into_data().bst_data().agg;
232 let nagg = L::agg_operate(right_agg, &self.acc);
233 if (self.f)(&nagg) {
234 return Ordering::Less;
235 }
236 let nagg = L::agg_operate(
237 &L::single_agg(&node.reborrow().into_data().bst_data().key),
238 &nagg,
239 );
240 if (self.f)(&nagg) {
241 Ordering::Equal
242 } else {
243 self.acc = nagg;
244 Ordering::Greater
245 }
246 } else {
247 let nagg = L::agg_operate(
248 &L::single_agg(&node.reborrow().into_data().bst_data().key),
249 &self.acc,
250 );
251 if (self.f)(&nagg) {
252 Ordering::Equal
253 } else {
254 self.acc = nagg;
255 Ordering::Greater
256 }
257 }
258 }More examples
crates/competitive/src/data_structure/binary_search_tree/data.rs (line 44)
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 L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
148 node.data_mut().bst_data_mut().key =
149 L::act_key(&node.reborrow().into_data().bst_data().key, act);
150 if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
151 node.data_mut().bst_data_mut().agg = nxlazy;
152 } else {
153 Self::top_down(node.reborrow_datamut());
154 Self::bottom_up(node.reborrow_datamut());
155 }
156 }
157
158 pub fn top_down<Spec>(mut node: BstDataMutRef<'_, Spec>)
159 where
160 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
161 {
162 let act = replace(&mut node.data_mut().bst_data_mut().act, L::act_unit());
163 if let Ok(left) = node.reborrow_datamut().left().descend() {
164 Self::update_act(left, &act);
165 }
166 if let Ok(right) = node.reborrow_datamut().right().descend() {
167 Self::update_act(right, &act);
168 }
169 }
170
171 pub fn bottom_up<Spec>(mut node: BstDataMutRef<'_, Spec>)
172 where
173 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
174 {
175 let mut agg = L::single_agg(&node.reborrow().into_data().bst_data().key);
176 if let Ok(left) = node.reborrow().left().descend() {
177 agg = L::agg_operate(&left.into_data().bst_data().agg, &agg);
178 }
179 if let Ok(right) = node.reborrow().right().descend() {
180 agg = L::agg_operate(&agg, &right.into_data().bst_data().agg);
181 }
182 node.data_mut().bst_data_mut().agg = agg;
183 }crates/competitive/src/data_structure/treap.rs (line 125)
117 fn merge(
118 left: Option<TreapRoot<M, L>>,
119 right: Option<TreapRoot<M, L>>,
120 ) -> Option<TreapRoot<M, L>> {
121 match (left, right) {
122 (None, None) => None,
123 (None, Some(node)) | (Some(node), None) => Some(node),
124 (Some(mut left), Some(mut right)) => unsafe {
125 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
126 TreapSpec::top_down(left.borrow_datamut());
127 let lr = left.borrow_mut().right().take();
128 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
129 left.borrow_mut().right().set(lr);
130 TreapSpec::bottom_up(left.borrow_datamut());
131 Some(left)
132 } else {
133 TreapSpec::top_down(right.borrow_datamut());
134 let rl = right.borrow_mut().left().take();
135 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
136 right.borrow_mut().left().set(rl);
137 TreapSpec::bottom_up(right.borrow_datamut());
138 Some(right)
139 }
140 },
141 }
142 }
143
144 fn split<Seeker>(
145 node: Option<TreapRoot<M, L>>,
146 mut seeker: Seeker,
147 eq_left: bool,
148 ) -> (Option<TreapRoot<M, L>>, Option<TreapRoot<M, L>>)
149 where
150 Seeker: BstSeeker<Spec = Self>,
151 {
152 match node {
153 None => (None, None),
154 Some(mut node) => {
155 Self::top_down(node.borrow_datamut());
156 let seek_left = match seeker.bst_seek(node.reborrow()) {
157 Ordering::Less => false,
158 Ordering::Equal => !eq_left,
159 Ordering::Greater => true,
160 };
161 if seek_left {
162 unsafe {
163 let left = node.borrow_mut().left().take();
164 let (l, r) = Self::split(left, seeker, eq_left);
165 if let Some(r) = r {
166 node.borrow_mut().left().set(r);
167 }
168 Self::bottom_up(node.borrow_datamut());
169 (l, Some(node))
170 }
171 } else {
172 unsafe {
173 let right = node.borrow_mut().right().take();
174 let (l, r) = Self::split(right, seeker, eq_left);
175 if let Some(l) = l {
176 node.borrow_mut().right().set(l);
177 }
178 Self::bottom_up(node.borrow_datamut());
179 (Some(node), r)
180 }
181 }
182 }
183 }
184 }
185}
186
187impl<M, L> TreapSpec<M, L>
188where
189 M: MonoidAct<Key: Ord>,
190 L: LazyMapMonoid,
191{
192 pub fn merge_ordered(
193 left: Option<TreapRoot<M, L>>,
194 right: Option<TreapRoot<M, L>>,
195 ) -> Option<TreapRoot<M, L>> {
196 match (left, right) {
197 (None, None) => None,
198 (None, Some(node)) | (Some(node), None) => Some(node),
199 (Some(mut left), Some(mut right)) => unsafe {
200 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
201 Self::top_down(left.borrow_datamut());
202 let key = &left.reborrow().into_data().key.key;
203 let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), false);
204 let ll = left.borrow_mut().left().take();
205 let lr = left.borrow_mut().right().take();
206 if let Some(l) = Self::merge_ordered(ll, rl) {
207 left.borrow_mut().left().set(l);
208 }
209 if let Some(r) = Self::merge_ordered(lr, rr) {
210 left.borrow_mut().right().set(r);
211 }
212 Self::bottom_up(left.borrow_datamut());
213 Some(left)
214 } else {
215 Self::top_down(right.borrow_datamut());
216 let key = &right.reborrow().into_data().key.key;
217 let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), false);
218 let rl = right.borrow_mut().left().take();
219 let rr = right.borrow_mut().right().take();
220 if let Some(l) = Self::merge_ordered(ll, rl) {
221 right.borrow_mut().left().set(l);
222 }
223 if let Some(r) = Self::merge_ordered(lr, rr) {
224 right.borrow_mut().right().set(r);
225 }
226 Self::bottom_up(right.borrow_datamut());
227 Some(right)
228 }
229 },
230 }
231 }
232}
233
234pub struct Treap<M, L, A = BoxAllocator<TreapNode<M, L>>>
235where
236 M: MonoidAct<Key: Ord>,
237 L: LazyMapMonoid,
238 A: Allocator<TreapNode<M, L>>,
239{
240 root: Option<TreapRoot<M, L>>,
241 node_id_manager: BstNodeIdManager<TreapSpec<M, L>>,
242 rng: Xorshift,
243 allocator: ManuallyDrop<A>,
244 _marker: PhantomData<(M, L)>,
245}
246
247impl<M, L, A> Default for Treap<M, L, A>
248where
249 M: MonoidAct<Key: Ord>,
250 L: LazyMapMonoid,
251 A: Allocator<TreapNode<M, L>> + Default,
252{
253 fn default() -> Self {
254 Self {
255 root: None,
256 node_id_manager: Default::default(),
257 rng: Xorshift::new(),
258 allocator: ManuallyDrop::new(A::default()),
259 _marker: PhantomData,
260 }
261 }
262}
263
264impl<M, L, A> Drop for Treap<M, L, A>
265where
266 M: MonoidAct<Key: Ord>,
267 L: LazyMapMonoid,
268 A: Allocator<TreapNode<M, L>>,
269{
270 fn drop(&mut self) {
271 unsafe {
272 if let Some(root) = self.root.take() {
273 root.into_dying().drop_all(self.allocator.deref_mut());
274 }
275 ManuallyDrop::drop(&mut self.allocator);
276 }
277 }
278}
279
280impl<M, L> Treap<M, L>
281where
282 M: MonoidAct<Key: Ord>,
283 L: LazyMapMonoid,
284{
285 pub fn new() -> Self {
286 Self::default()
287 }
288}
289
290impl<M, L, A> Treap<M, L, A>
291where
292 M: MonoidAct<Key: Ord>,
293 L: LazyMapMonoid,
294 A: Allocator<TreapNode<M, L>>,
295{
296 pub fn len(&self) -> usize {
297 self.node_id_manager.len()
298 }
299
300 pub fn is_empty(&self) -> bool {
301 self.node_id_manager.is_empty()
302 }
303
304 pub fn clear(&mut self) {
305 unsafe {
306 if let Some(root) = self.root.take() {
307 root.into_dying().drop_all(self.allocator.deref_mut());
308 }
309 self.node_id_manager.clear();
310 }
311 }
312
313 pub fn get(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(&M::Key, &L::Key)> {
314 if !self.node_id_manager.contains(&node_id) {
315 return None;
316 }
317 unsafe {
318 WithParent::resolve_top_down::<TreapSpec<M, L>>(
319 node_id.reborrow_datamut(&mut self.root),
320 );
321 let data = node_id.reborrow(&self.root).into_data();
322 Some((&data.key.key, &data.value.key))
323 }
324 }
325
326 pub fn change(
327 &mut self,
328 node_id: BstNodeId<TreapSpec<M, L>>,
329 f: impl FnOnce(&mut L::Key),
330 ) -> bool {
331 if !self.node_id_manager.contains(&node_id) {
332 return false;
333 }
334 unsafe {
335 WithParent::resolve_top_down::<TreapSpec<M, L>>(
336 node_id.reborrow_datamut(&mut self.root),
337 );
338 let data = node_id.reborrow_datamut(&mut self.root).into_data_mut();
339 f(&mut data.value.key);
340 WithParent::resolve_bottom_up::<TreapSpec<M, L>>(
341 node_id.reborrow_datamut(&mut self.root),
342 );
343 }
344 true
345 }
346
347 pub fn change_key_value(
348 &mut self,
349 node_id: BstNodeId<TreapSpec<M, L>>,
350 f: impl FnOnce(&mut M::Key, &mut L::Key),
351 ) -> bool {
352 if !self.node_id_manager.contains(&node_id) {
353 return false;
354 }
355 unsafe {
356 WithParent::resolve_top_down::<TreapSpec<M, L>>(
357 node_id.reborrow_datamut(&mut self.root),
358 );
359 let mut node = if WithParent::is_root(node_id.reborrow(&self.root)) {
360 WithParent::remove_root(&mut self.root).unwrap_unchecked()
361 } else {
362 WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
363 };
364 let data = node.borrow_datamut().into_data_mut();
365 f(&mut data.key.key, &mut data.value.key);
366 self.root = TreapSpec::merge_ordered(self.root.take(), Some(node));
367 true
368 }
369 }
370
371 pub fn insert(&mut self, key: M::Key, value: L::Key) -> BstNodeId<TreapSpec<M, L>> {
372 let (left, right) = TreapSpec::split(self.root.take(), SeekByKey::new(&key), false);
373 let data = TreapData {
374 priority: self.rng.rand64(),
375 key: MonoidActElement::from_key(key),
376 value: LazyMapElement::from_key(value),
377 };
378 let node = BstRoot::from_data(data, self.allocator.deref_mut());
379 let node_id = self.node_id_manager.register(&node);
380 self.root = TreapSpec::merge(TreapSpec::merge(left, Some(node)), right);
381 node_id
382 }
383
384 pub fn remove(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(M::Key, L::Key)> {
385 if !self.node_id_manager.contains(&node_id) {
386 return None;
387 }
388 unsafe {
389 WithParent::resolve_top_down::<TreapSpec<M, L>>(
390 node_id.reborrow_datamut(&mut self.root),
391 );
392 let node = if WithParent::is_root(node_id.reborrow(&self.root)) {
393 WithParent::remove_root(&mut self.root).unwrap_unchecked()
394 } else {
395 WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
396 };
397 self.node_id_manager.unregister(node_id);
398 let data = node.into_dying().into_data(self.allocator.deref_mut());
399 Some((data.key.key, data.value.key))
400 }
401 }
402
403 pub fn range_by_key<Q, R>(&mut self, range: R) -> TreapSplit3<'_, M, L>
404 where
405 M: MonoidAct<Key: Borrow<Q>>,
406 Q: Ord + ?Sized,
407 R: RangeBounds<Q>,
408 {
409 let split3 = Split3::seek_by_key(&mut self.root, range);
410 TreapSplit3 {
411 split3,
412 key_updated: false,
413 }
414 }
415
416 pub fn find_by_key<Q>(&mut self, key: &Q) -> Option<BstNodeId<TreapSpec<M, L>>>
417 where
418 M: MonoidAct<Key: Borrow<Q>>,
419 Q: Ord + ?Sized,
420 {
421 let split = Split::new(
422 &mut self.root,
423 SeekByKey::<TreapSpec<M, L>, M::Key, Q>::new(key),
424 false,
425 );
426 let node = split.right()?.leftmost()?;
427 matches!(node.into_data().key.key.borrow().cmp(key), Ordering::Equal)
428 .then(|| self.node_id_manager.registerd_node_id(node))
429 .flatten()
430 }
431
432 pub fn find_by_acc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
433 where
434 F: FnMut(&L::Agg) -> bool,
435 {
436 let split = Split::new(
437 &mut self.root,
438 SeekByAccCond::<TreapSpec<M, L>, L, F>::new(f),
439 false,
440 );
441 let node = split.right()?.leftmost()?;
442 self.node_id_manager.registerd_node_id(node)
443 }
444
445 pub fn find_by_racc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
446 where
447 F: FnMut(&L::Agg) -> bool,
448 {
449 let split = Split::new(
450 &mut self.root,
451 SeekByRaccCond::<TreapSpec<M, L>, L, F>::new(f),
452 true,
453 );
454 let node = split.left()?.rightmost()?;
455 self.node_id_manager.registerd_node_id(node)
456 }
457}
458
459pub struct TreapSplit3<'a, M, L>
460where
461 M: MonoidAct<Key: Ord>,
462 L: LazyMapMonoid,
463{
464 split3: Split3<'a, TreapSpec<M, L>>,
465 key_updated: bool,
466}
467
468impl<'a, M, L> TreapSplit3<'a, M, L>
469where
470 M: MonoidAct<Key: Ord>,
471 L: LazyMapMonoid,
472{
473 pub fn fold(&self) -> L::Agg {
474 if let Some(node) = self.split3.mid() {
475 node.reborrow().into_data().value.agg.clone()
476 } else {
477 L::agg_unit()
478 }
479 }Sourcepub fn traverse<F>(self, f: &mut F)where
F: FnMut(Self),
pub fn traverse<F>(self, f: &mut F)where
F: FnMut(Self),
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 363)
358 pub fn traverse<F>(self, f: &mut F)
359 where
360 F: FnMut(Self),
361 {
362 if let Ok(left) = self.left().descend() {
363 left.traverse(f);
364 }
365 f(self);
366 if let Ok(right) = self.right().descend() {
367 right.traverse(f);
368 }
369 }Sourcepub fn leftmost(self) -> Option<Self>
pub fn leftmost(self) -> Option<Self>
Examples found in repository?
crates/competitive/src/data_structure/treap.rs (line 426)
416 pub fn find_by_key<Q>(&mut self, key: &Q) -> Option<BstNodeId<TreapSpec<M, L>>>
417 where
418 M: MonoidAct<Key: Borrow<Q>>,
419 Q: Ord + ?Sized,
420 {
421 let split = Split::new(
422 &mut self.root,
423 SeekByKey::<TreapSpec<M, L>, M::Key, Q>::new(key),
424 false,
425 );
426 let node = split.right()?.leftmost()?;
427 matches!(node.into_data().key.key.borrow().cmp(key), Ordering::Equal)
428 .then(|| self.node_id_manager.registerd_node_id(node))
429 .flatten()
430 }
431
432 pub fn find_by_acc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
433 where
434 F: FnMut(&L::Agg) -> bool,
435 {
436 let split = Split::new(
437 &mut self.root,
438 SeekByAccCond::<TreapSpec<M, L>, L, F>::new(f),
439 false,
440 );
441 let node = split.right()?.leftmost()?;
442 self.node_id_manager.registerd_node_id(node)
443 }Sourcepub fn rightmost(self) -> Option<Self>
pub fn rightmost(self) -> Option<Self>
Examples found in repository?
crates/competitive/src/data_structure/treap.rs (line 454)
445 pub fn find_by_racc_cond<F>(&mut self, f: F) -> Option<BstNodeId<TreapSpec<M, L>>>
446 where
447 F: FnMut(&L::Agg) -> bool,
448 {
449 let split = Split::new(
450 &mut self.root,
451 SeekByRaccCond::<TreapSpec<M, L>, L, F>::new(f),
452 true,
453 );
454 let node = split.left()?.rightmost()?;
455 self.node_id_manager.registerd_node_id(node)
456 }Source§impl<'a, Spec> BstNodeRef<DataMut<'a>, Spec>where
Spec: BstSpec,
impl<'a, Spec> BstNodeRef<DataMut<'a>, Spec>where
Spec: BstSpec,
Sourcepub fn reborrow_datamut(&mut self) -> BstNodeRef<DataMut<'_>, Spec>
pub fn reborrow_datamut(&mut self) -> BstNodeRef<DataMut<'_>, Spec>
Examples found in repository?
More examples
crates/competitive/src/data_structure/binary_search_tree/data.rs (line 99)
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 L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
148 node.data_mut().bst_data_mut().key =
149 L::act_key(&node.reborrow().into_data().bst_data().key, act);
150 if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
151 node.data_mut().bst_data_mut().agg = nxlazy;
152 } else {
153 Self::top_down(node.reborrow_datamut());
154 Self::bottom_up(node.reborrow_datamut());
155 }
156 }
157
158 pub fn top_down<Spec>(mut node: BstDataMutRef<'_, Spec>)
159 where
160 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
161 {
162 let act = replace(&mut node.data_mut().bst_data_mut().act, L::act_unit());
163 if let Ok(left) = node.reborrow_datamut().left().descend() {
164 Self::update_act(left, &act);
165 }
166 if let Ok(right) = node.reborrow_datamut().right().descend() {
167 Self::update_act(right, &act);
168 }
169 }crates/competitive/src/data_structure/binary_search_tree/node.rs (line 130)
123 pub fn resolve_top_down<Spec>(node: BstNodeRef<marker::DataMut<'_>, Spec>)
124 where
125 Spec: BstSpec<Data = Data, Parent = Self>,
126 {
127 unsafe {
128 let (mut node, mut stack) = node.root_path();
129 while let Some(is_left) = stack.pop() {
130 Spec::top_down(node.reborrow_datamut());
131 if is_left {
132 node = node.left().descend().unwrap_unchecked();
133 } else {
134 node = node.right().descend().unwrap_unchecked();
135 }
136 }
137 Spec::top_down(node.reborrow_datamut());
138 }
139 }
140
141 pub fn resolve_bottom_up<Spec>(mut node: BstNodeRef<marker::DataMut<'_>, Spec>)
142 where
143 Spec: BstSpec<Data = Data, Parent = Self>,
144 {
145 loop {
146 Spec::bottom_up(node.reborrow_datamut());
147 match node.ascend() {
148 Ok(parent) => node = parent,
149 Err(_) => break,
150 }
151 }
152 }Sourcepub fn data_mut(&mut self) -> &mut Spec::Data
pub fn data_mut(&mut self) -> &mut Spec::Data
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/data.rs (line 51)
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 L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
148 node.data_mut().bst_data_mut().key =
149 L::act_key(&node.reborrow().into_data().bst_data().key, act);
150 if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
151 node.data_mut().bst_data_mut().agg = nxlazy;
152 } else {
153 Self::top_down(node.reborrow_datamut());
154 Self::bottom_up(node.reborrow_datamut());
155 }
156 }
157
158 pub fn top_down<Spec>(mut node: BstDataMutRef<'_, Spec>)
159 where
160 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
161 {
162 let act = replace(&mut node.data_mut().bst_data_mut().act, L::act_unit());
163 if let Ok(left) = node.reborrow_datamut().left().descend() {
164 Self::update_act(left, &act);
165 }
166 if let Ok(right) = node.reborrow_datamut().right().descend() {
167 Self::update_act(right, &act);
168 }
169 }
170
171 pub fn bottom_up<Spec>(mut node: BstDataMutRef<'_, Spec>)
172 where
173 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
174 {
175 let mut agg = L::single_agg(&node.reborrow().into_data().bst_data().key);
176 if let Ok(left) = node.reborrow().left().descend() {
177 agg = L::agg_operate(&left.into_data().bst_data().agg, &agg);
178 }
179 if let Ok(right) = node.reborrow().right().descend() {
180 agg = L::agg_operate(&agg, &right.into_data().bst_data().agg);
181 }
182 node.data_mut().bst_data_mut().agg = agg;
183 }Source§impl<'a, Spec> BstNodeRef<DataMut<'a>, Spec>where
Spec: BstSpec<Parent: 'a, Data: 'a>,
impl<'a, Spec> BstNodeRef<DataMut<'a>, Spec>where
Spec: BstSpec<Parent: 'a, Data: 'a>,
Sourcepub fn into_data_mut(self) -> &'a mut Spec::Data
pub fn into_data_mut(self) -> &'a mut Spec::Data
Examples found in repository?
crates/competitive/src/data_structure/treap.rs (line 338)
326 pub fn change(
327 &mut self,
328 node_id: BstNodeId<TreapSpec<M, L>>,
329 f: impl FnOnce(&mut L::Key),
330 ) -> bool {
331 if !self.node_id_manager.contains(&node_id) {
332 return false;
333 }
334 unsafe {
335 WithParent::resolve_top_down::<TreapSpec<M, L>>(
336 node_id.reborrow_datamut(&mut self.root),
337 );
338 let data = node_id.reborrow_datamut(&mut self.root).into_data_mut();
339 f(&mut data.value.key);
340 WithParent::resolve_bottom_up::<TreapSpec<M, L>>(
341 node_id.reborrow_datamut(&mut self.root),
342 );
343 }
344 true
345 }
346
347 pub fn change_key_value(
348 &mut self,
349 node_id: BstNodeId<TreapSpec<M, L>>,
350 f: impl FnOnce(&mut M::Key, &mut L::Key),
351 ) -> bool {
352 if !self.node_id_manager.contains(&node_id) {
353 return false;
354 }
355 unsafe {
356 WithParent::resolve_top_down::<TreapSpec<M, L>>(
357 node_id.reborrow_datamut(&mut self.root),
358 );
359 let mut node = if WithParent::is_root(node_id.reborrow(&self.root)) {
360 WithParent::remove_root(&mut self.root).unwrap_unchecked()
361 } else {
362 WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
363 };
364 let data = node.borrow_datamut().into_data_mut();
365 f(&mut data.key.key, &mut data.value.key);
366 self.root = TreapSpec::merge_ordered(self.root.take(), Some(node));
367 true
368 }
369 }Source§impl<'a, Spec> BstNodeRef<Mut<'a>, Spec>where
Spec: BstSpec,
impl<'a, Spec> BstNodeRef<Mut<'a>, Spec>where
Spec: BstSpec,
Sourcepub fn reborrow_datamut(&mut self) -> BstNodeRef<DataMut<'_>, Spec>
pub fn reborrow_datamut(&mut self) -> BstNodeRef<DataMut<'_>, Spec>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 201)
177 pub unsafe fn remove_not_root<Spec>(
178 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
179 ) -> BstNodeRef<marker::Owned, Spec>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 assert!(!Self::is_root(node.reborrow()));
184 unsafe {
185 let left = node.left_mut().take();
186 let right = node.right_mut().take();
187 let merged = Spec::merge(left, right);
188 let node_inner = node.node;
189 let mut parent = node.ascend().unwrap_unchecked();
190 let mut node = if let Some(merged) = merged {
191 let node = if parent
192 .reborrow()
193 .left()
194 .descend()
195 .is_ok_and(|n| n.node == node_inner)
196 {
197 parent.left_mut().replace(merged)
198 } else {
199 parent.right_mut().replace(merged)
200 };
201 Self::resolve_bottom_up(parent.reborrow_datamut());
202 node.unwrap_unchecked()
203 } else {
204 let node = if parent
205 .reborrow()
206 .left()
207 .descend()
208 .is_ok_and(|n| n.node == node_inner)
209 {
210 parent.left_mut().take()
211 } else {
212 parent.right_mut().take()
213 };
214 Self::resolve_bottom_up(parent.reborrow_datamut());
215 node.unwrap_unchecked()
216 };
217 Spec::bottom_up(node.borrow_datamut());
218 node
219 }
220 }Sourcepub fn left_mut(&mut self) -> BstEdgeHandle<BstNodeRef<Mut<'_>, Spec>, Left>
pub fn left_mut(&mut self) -> BstEdgeHandle<BstNodeRef<Mut<'_>, Spec>, Left>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 169)
161 pub unsafe fn remove_root<Spec>(
162 root: &mut Option<BstRoot<Spec>>,
163 ) -> Option<BstNodeRef<marker::Owned, Spec>>
164 where
165 Spec: BstSpec<Data = Data, Parent = Self>,
166 {
167 let mut node = root.take()?;
168 unsafe {
169 let left = node.borrow_mut().left_mut().take();
170 let right = node.borrow_mut().right_mut().take();
171 *root = Spec::merge(left, right);
172 Spec::bottom_up(node.borrow_datamut());
173 Some(node)
174 }
175 }
176
177 pub unsafe fn remove_not_root<Spec>(
178 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
179 ) -> BstNodeRef<marker::Owned, Spec>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 assert!(!Self::is_root(node.reborrow()));
184 unsafe {
185 let left = node.left_mut().take();
186 let right = node.right_mut().take();
187 let merged = Spec::merge(left, right);
188 let node_inner = node.node;
189 let mut parent = node.ascend().unwrap_unchecked();
190 let mut node = if let Some(merged) = merged {
191 let node = if parent
192 .reborrow()
193 .left()
194 .descend()
195 .is_ok_and(|n| n.node == node_inner)
196 {
197 parent.left_mut().replace(merged)
198 } else {
199 parent.right_mut().replace(merged)
200 };
201 Self::resolve_bottom_up(parent.reborrow_datamut());
202 node.unwrap_unchecked()
203 } else {
204 let node = if parent
205 .reborrow()
206 .left()
207 .descend()
208 .is_ok_and(|n| n.node == node_inner)
209 {
210 parent.left_mut().take()
211 } else {
212 parent.right_mut().take()
213 };
214 Self::resolve_bottom_up(parent.reborrow_datamut());
215 node.unwrap_unchecked()
216 };
217 Spec::bottom_up(node.borrow_datamut());
218 node
219 }
220 }Sourcepub fn right_mut(&mut self) -> BstEdgeHandle<BstNodeRef<Mut<'_>, Spec>, Right>
pub fn right_mut(&mut self) -> BstEdgeHandle<BstNodeRef<Mut<'_>, Spec>, Right>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 170)
161 pub unsafe fn remove_root<Spec>(
162 root: &mut Option<BstRoot<Spec>>,
163 ) -> Option<BstNodeRef<marker::Owned, Spec>>
164 where
165 Spec: BstSpec<Data = Data, Parent = Self>,
166 {
167 let mut node = root.take()?;
168 unsafe {
169 let left = node.borrow_mut().left_mut().take();
170 let right = node.borrow_mut().right_mut().take();
171 *root = Spec::merge(left, right);
172 Spec::bottom_up(node.borrow_datamut());
173 Some(node)
174 }
175 }
176
177 pub unsafe fn remove_not_root<Spec>(
178 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
179 ) -> BstNodeRef<marker::Owned, Spec>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 assert!(!Self::is_root(node.reborrow()));
184 unsafe {
185 let left = node.left_mut().take();
186 let right = node.right_mut().take();
187 let merged = Spec::merge(left, right);
188 let node_inner = node.node;
189 let mut parent = node.ascend().unwrap_unchecked();
190 let mut node = if let Some(merged) = merged {
191 let node = if parent
192 .reborrow()
193 .left()
194 .descend()
195 .is_ok_and(|n| n.node == node_inner)
196 {
197 parent.left_mut().replace(merged)
198 } else {
199 parent.right_mut().replace(merged)
200 };
201 Self::resolve_bottom_up(parent.reborrow_datamut());
202 node.unwrap_unchecked()
203 } else {
204 let node = if parent
205 .reborrow()
206 .left()
207 .descend()
208 .is_ok_and(|n| n.node == node_inner)
209 {
210 parent.left_mut().take()
211 } else {
212 parent.right_mut().take()
213 };
214 Self::resolve_bottom_up(parent.reborrow_datamut());
215 node.unwrap_unchecked()
216 };
217 Spec::bottom_up(node.borrow_datamut());
218 node
219 }
220 }Source§impl<'a, Spec> BstNodeRef<Mut<'a>, Spec>where
Spec: BstSpec<Data: 'a>,
impl<'a, Spec> BstNodeRef<Mut<'a>, Spec>where
Spec: BstSpec<Data: 'a>,
pub fn dormant(self) -> BstNodeRef<DormantMut, Spec>
Source§impl<Spec> BstNodeRef<DormantMut, Spec>where
Spec: BstSpec,
impl<Spec> BstNodeRef<DormantMut, Spec>where
Spec: BstSpec,
pub unsafe fn awaken<'a>(self) -> BstNodeRef<Mut<'a>, Spec>
Source§impl<Spec> BstNodeRef<Dying, Spec>where
Spec: BstSpec,
impl<Spec> BstNodeRef<Dying, Spec>where
Spec: BstSpec,
Sourcepub unsafe fn into_data<A>(self, allocator: &mut A) -> Spec::Data
pub unsafe fn into_data<A>(self, allocator: &mut A) -> Spec::Data
Examples found in repository?
crates/competitive/src/data_structure/treap.rs (line 398)
384 pub fn remove(&mut self, node_id: BstNodeId<TreapSpec<M, L>>) -> Option<(M::Key, L::Key)> {
385 if !self.node_id_manager.contains(&node_id) {
386 return None;
387 }
388 unsafe {
389 WithParent::resolve_top_down::<TreapSpec<M, L>>(
390 node_id.reborrow_datamut(&mut self.root),
391 );
392 let node = if WithParent::is_root(node_id.reborrow(&self.root)) {
393 WithParent::remove_root(&mut self.root).unwrap_unchecked()
394 } else {
395 WithParent::remove_not_root(node_id.reborrow_mut(&mut self.root))
396 };
397 self.node_id_manager.unregister(node_id);
398 let data = node.into_dying().into_data(self.allocator.deref_mut());
399 Some((data.key.key, data.value.key))
400 }
401 }Sourcepub unsafe fn drop_all<A>(self, allocator: &mut A)
pub unsafe fn drop_all<A>(self, allocator: &mut A)
Examples found in repository?
crates/competitive/src/data_structure/treap.rs (line 273)
270 fn drop(&mut self) {
271 unsafe {
272 if let Some(root) = self.root.take() {
273 root.into_dying().drop_all(self.allocator.deref_mut());
274 }
275 ManuallyDrop::drop(&mut self.allocator);
276 }
277 }
278}
279
280impl<M, L> Treap<M, L>
281where
282 M: MonoidAct<Key: Ord>,
283 L: LazyMapMonoid,
284{
285 pub fn new() -> Self {
286 Self::default()
287 }
288}
289
290impl<M, L, A> Treap<M, L, A>
291where
292 M: MonoidAct<Key: Ord>,
293 L: LazyMapMonoid,
294 A: Allocator<TreapNode<M, L>>,
295{
296 pub fn len(&self) -> usize {
297 self.node_id_manager.len()
298 }
299
300 pub fn is_empty(&self) -> bool {
301 self.node_id_manager.is_empty()
302 }
303
304 pub fn clear(&mut self) {
305 unsafe {
306 if let Some(root) = self.root.take() {
307 root.into_dying().drop_all(self.allocator.deref_mut());
308 }
309 self.node_id_manager.clear();
310 }
311 }More examples
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 490)
481 pub unsafe fn drop_all<A>(self, allocator: &mut A)
482 where
483 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
484 {
485 let BstNode { child, .. } = allocator.deallocate(self.node);
486 for node in child.into_iter().flatten() {
487 unsafe {
488 BstNodeRef::<marker::Owned, Spec>::new(node)
489 .into_dying()
490 .drop_all(allocator)
491 }
492 }
493 }Trait Implementations§
impl<'a, Spec> Copy for BstNodeRef<Immut<'a>, Spec>where
Spec: BstSpec<Data: 'a>,
Auto Trait Implementations§
impl<BorrowType, Spec> Freeze for BstNodeRef<BorrowType, Spec>
impl<BorrowType, Spec> RefUnwindSafe for BstNodeRef<BorrowType, Spec>where
BorrowType: RefUnwindSafe,
<Spec as BstSpec>::Data: RefUnwindSafe,
<Spec as BstSpec>::Parent: RefUnwindSafe,
impl<BorrowType, Spec> !Send for BstNodeRef<BorrowType, Spec>
impl<BorrowType, Spec> !Sync for BstNodeRef<BorrowType, Spec>
impl<BorrowType, Spec> Unpin for BstNodeRef<BorrowType, Spec>where
BorrowType: Unpin,
impl<BorrowType, Spec> UnwindSafe for BstNodeRef<BorrowType, Spec>where
BorrowType: UnwindSafe,
<Spec as BstSpec>::Data: RefUnwindSafe,
<Spec as BstSpec>::Parent: RefUnwindSafe,
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more