pub struct BstEdgeHandle<Node, Dir> {
node: Node,
_marker: PhantomData<Dir>,
}Fields§
§node: Node§_marker: PhantomData<Dir>Implementations§
Source§impl<BorrowType, Spec, Dir> BstEdgeHandle<BstNodeRef<BorrowType, Spec>, Dir>
impl<BorrowType, Spec, Dir> BstEdgeHandle<BstNodeRef<BorrowType, Spec>, Dir>
Sourcepub fn descend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self>
pub fn descend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self>
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().left().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().right().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/splay_tree.rs (line 82)
78 fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
79 let left = node
80 .reborrow()
81 .left()
82 .descend()
83 .map(|node| node.into_data().size)
84 .unwrap_or_default();
85 let right = node
86 .reborrow()
87 .right()
88 .descend()
89 .map(|node| node.into_data().size)
90 .unwrap_or_default();
91 node.data_mut().size = left + right + 1;
92 }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 if L::is_act_unit(act) {
148 return;
149 }
150 L::act_operate_assign(&mut node.data_mut().bst_data_mut().act, act);
151 node.data_mut().bst_data_mut().key =
152 L::act_key(&node.reborrow().into_data().bst_data().key, act);
153 if let Some(nxlazy) = L::act_agg(&node.reborrow().into_data().bst_data().agg, act) {
154 node.data_mut().bst_data_mut().agg = nxlazy;
155 } else {
156 Self::top_down(node.reborrow_datamut());
157 Self::bottom_up(node.reborrow_datamut());
158 }
159 }
160
161 pub fn top_down<Spec>(mut node: BstDataMutRef<'_, Spec>)
162 where
163 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
164 {
165 if L::is_act_unit(&node.reborrow().into_data().bst_data().act) {
166 return;
167 }
168 let act = replace(&mut node.data_mut().bst_data_mut().act, L::act_unit());
169 if let Ok(left) = node.reborrow_datamut().left().descend() {
170 Self::update_act(left, &act);
171 }
172 if let Ok(right) = node.reborrow_datamut().right().descend() {
173 Self::update_act(right, &act);
174 }
175 }
176
177 pub fn bottom_up<Spec>(mut node: BstDataMutRef<'_, Spec>)
178 where
179 Spec: BstSpec<Data: BstDataAccess<marker::LazyMap, Value = Self>>,
180 {
181 let mut agg = L::single_agg(&node.reborrow().into_data().bst_data().key);
182 if let Ok(left) = node.reborrow().left().descend() {
183 agg = L::agg_operate(&left.into_data().bst_data().agg, &agg);
184 }
185 if let Ok(right) = node.reborrow().right().descend() {
186 agg = L::agg_operate(&agg, &right.into_data().bst_data().agg);
187 }
188 node.data_mut().bst_data_mut().agg = agg;
189 }crates/competitive/src/data_structure/binary_search_tree/node.rs (line 148)
139 pub fn resolve_top_down<Spec>(node: BstNodeRef<marker::DataMut<'_>, Spec>)
140 where
141 Spec: BstSpec<Data = Data, Parent = Self>,
142 {
143 unsafe {
144 let (mut node, mut stack) = node.root_path();
145 while let Some(is_left) = stack.pop() {
146 Spec::top_down(node.reborrow_datamut());
147 if is_left {
148 node = node.left().descend().unwrap_unchecked();
149 } else {
150 node = node.right().descend().unwrap_unchecked();
151 }
152 }
153 Spec::top_down(node.reborrow_datamut());
154 }
155 }
156
157 pub fn resolve_bottom_up<Spec>(mut node: BstNodeRef<marker::DataMut<'_>, Spec>)
158 where
159 Spec: BstSpec<Data = Data, Parent = Self>,
160 {
161 loop {
162 Spec::bottom_up(node.reborrow_datamut());
163 match node.ascend() {
164 Ok(parent) => node = parent,
165 Err(_) => break,
166 }
167 }
168 }
169
170 pub fn is_root<Spec>(node: BstNodeRef<marker::Immut<'_>, Spec>) -> bool
171 where
172 Spec: BstSpec<Data = Data, Parent = Self>,
173 {
174 unsafe { node.node.as_ref().parent.parent.is_none() }
175 }
176
177 pub unsafe fn remove_root<Spec>(
178 root: &mut Option<BstRoot<Spec>>,
179 ) -> Option<BstNodeRef<marker::Owned, Spec>>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 let mut node = root.take()?;
184 unsafe {
185 let left = node.borrow_mut().left_mut().take();
186 let right = node.borrow_mut().right_mut().take();
187 *root = Spec::merge(left, right);
188 Spec::bottom_up(node.borrow_datamut());
189 Some(node)
190 }
191 }
192
193 pub unsafe fn remove_not_root<Spec>(
194 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
195 ) -> BstNodeRef<marker::Owned, Spec>
196 where
197 Spec: BstSpec<Data = Data, Parent = Self>,
198 {
199 assert!(!Self::is_root(node.reborrow()));
200 unsafe {
201 let left = node.left_mut().take();
202 let right = node.right_mut().take();
203 let merged = Spec::merge(left, right);
204 let node_inner = node.node;
205 let mut parent = node.ascend().unwrap_unchecked();
206 let mut node = if let Some(merged) = merged {
207 let node = if parent
208 .reborrow()
209 .left()
210 .descend()
211 .is_ok_and(|n| n.node == node_inner)
212 {
213 parent.left_mut().replace(merged)
214 } else {
215 parent.right_mut().replace(merged)
216 };
217 Self::resolve_bottom_up(parent.reborrow_datamut());
218 node.unwrap_unchecked()
219 } else {
220 let node = if parent
221 .reborrow()
222 .left()
223 .descend()
224 .is_ok_and(|n| n.node == node_inner)
225 {
226 parent.left_mut().take()
227 } else {
228 parent.right_mut().take()
229 };
230 Self::resolve_bottom_up(parent.reborrow_datamut());
231 node.unwrap_unchecked()
232 };
233 Spec::bottom_up(node.borrow_datamut());
234 node
235 }
236 }
237}
238
239pub struct BstNodeRef<BorrowType, Spec>
240where
241 Spec: BstSpec,
242{
243 pub node: NonNull<BstNode<Spec::Data, Spec::Parent>>,
244 _marker: PhantomData<BorrowType>,
245}
246
247impl<'a, Spec> Copy for BstNodeRef<marker::Immut<'a>, Spec> where Spec: BstSpec<Data: 'a> {}
248impl<'a, Spec> Clone for BstNodeRef<marker::Immut<'a>, Spec>
249where
250 Spec: BstSpec<Data: 'a>,
251{
252 fn clone(&self) -> Self {
253 *self
254 }
255}
256
257impl<BorrowType, Spec> BstNodeRef<BorrowType, Spec>
258where
259 Spec: BstSpec,
260 BorrowType: marker::BorrowType,
261{
262 pub unsafe fn new_unchecked(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
263 Self {
264 node,
265 _marker: PhantomData,
266 }
267 }
268 pub fn reborrow(&self) -> BstNodeRef<marker::Immut<'_>, Spec> {
269 BstNodeRef {
270 node: self.node,
271 _marker: PhantomData,
272 }
273 }
274 pub fn left(self) -> BstEdgeHandle<Self, marker::Left> {
275 BstEdgeHandle {
276 node: self,
277 _marker: PhantomData,
278 }
279 }
280 pub fn right(self) -> BstEdgeHandle<Self, marker::Right> {
281 BstEdgeHandle {
282 node: self,
283 _marker: PhantomData,
284 }
285 }
286}
287
288impl<BorrowType, Spec, Data> BstNodeRef<BorrowType, Spec>
289where
290 Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
291 BorrowType: marker::BorrowType,
292{
293 pub fn ascend(self) -> Result<BstNodeRef<BorrowType, Spec>, Self> {
294 const {
295 assert!(BorrowType::TRAVERSAL_PERMIT);
296 };
297 let parent = unsafe { self.node.as_ref().parent.parent };
298 parent
299 .map(|node| BstNodeRef {
300 node,
301 _marker: PhantomData,
302 })
303 .ok_or(self)
304 }
305 pub fn root_path(self) -> (Self, Vec<bool>) {
306 let mut node = self;
307 let mut nn = node.node;
308 let mut stack = vec![];
309 let root = loop {
310 match node.ascend() {
311 Ok(parent) => {
312 node = parent;
313 stack.push(
314 node.reborrow()
315 .left()
316 .descend()
317 .is_ok_and(|node| node.node == nn),
318 );
319 nn = node.node;
320 }
321 Err(node) => {
322 break node;
323 }
324 }
325 };
326 (root, stack)
327 }
328}
329
330impl<Spec> BstNodeRef<marker::Owned, Spec>
331where
332 Spec: BstSpec,
333{
334 pub fn new(node: NonNull<BstNode<Spec::Data, Spec::Parent>>) -> Self {
335 Self {
336 node,
337 _marker: PhantomData,
338 }
339 }
340 pub fn from_data<A>(data: Spec::Data, allocator: &mut A) -> Self
341 where
342 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
343 {
344 Self::new(allocator.allocate(BstNode::new(data)))
345 }
346 pub fn borrow_mut(&mut self) -> BstNodeRef<marker::Mut<'_>, Spec> {
347 BstNodeRef {
348 node: self.node,
349 _marker: PhantomData,
350 }
351 }
352 pub fn borrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
353 BstNodeRef {
354 node: self.node,
355 _marker: PhantomData,
356 }
357 }
358 pub fn into_dying(self) -> BstNodeRef<marker::Dying, Spec> {
359 BstNodeRef {
360 node: self.node,
361 _marker: PhantomData,
362 }
363 }
364}
365
366impl<'a, Spec> BstNodeRef<marker::Immut<'a>, Spec>
367where
368 Spec: BstSpec<Parent: 'a, Data: 'a>,
369{
370 pub fn into_data(self) -> &'a Spec::Data {
371 unsafe { &self.node.as_ref().data }
372 }
373
374 pub fn traverse<F>(self, f: &mut F)
375 where
376 F: FnMut(Self),
377 {
378 if let Ok(left) = self.left().descend() {
379 left.traverse(f);
380 }
381 f(self);
382 if let Ok(right) = self.right().descend() {
383 right.traverse(f);
384 }
385 }
386
387 pub fn leftmost(self) -> Self {
388 let mut node = self;
389 while let Ok(left) = node.left().descend() {
390 node = left;
391 }
392 node
393 }
394
395 pub fn rightmost(self) -> Self {
396 let mut node = self;
397 while let Ok(right) = node.right().descend() {
398 node = right;
399 }
400 node
401 }
402}
403
404impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
405where
406 Spec: BstSpec,
407{
408 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
409 BstNodeRef {
410 node: self.node,
411 _marker: PhantomData,
412 }
413 }
414 pub fn data_mut(&mut self) -> &mut Spec::Data {
415 unsafe { &mut self.node.as_mut().data }
416 }
417
418 pub fn swap_children(&mut self) {
419 unsafe { self.node.as_mut().child.swap(0, 1) };
420 }
421}
422
423impl<'a, Spec> BstNodeRef<marker::DataMut<'a>, Spec>
424where
425 Spec: BstSpec<Parent: 'a, Data: 'a>,
426{
427 pub fn into_data_mut(mut self) -> &'a mut Spec::Data {
428 unsafe { &mut self.node.as_mut().data }
429 }
430}
431
432impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
433where
434 Spec: BstSpec,
435{
436 pub fn reborrow_datamut(&mut self) -> BstNodeRef<marker::DataMut<'_>, Spec> {
437 BstNodeRef {
438 node: self.node,
439 _marker: PhantomData,
440 }
441 }
442
443 pub fn left_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Left> {
444 BstEdgeHandle {
445 node: BstNodeRef {
446 node: self.node,
447 _marker: PhantomData,
448 },
449 _marker: PhantomData,
450 }
451 }
452
453 pub fn right_mut(&mut self) -> BstEdgeHandle<BstNodeRef<marker::Mut<'_>, Spec>, marker::Right> {
454 BstEdgeHandle {
455 node: BstNodeRef {
456 node: self.node,
457 _marker: PhantomData,
458 },
459 _marker: PhantomData,
460 }
461 }
462}
463
464impl<'a, Spec> BstNodeRef<marker::Mut<'a>, Spec>
465where
466 Spec: BstSpec<Data: 'a>,
467{
468 pub fn dormant(self) -> BstNodeRef<marker::DormantMut, Spec> {
469 BstNodeRef {
470 node: self.node,
471 _marker: PhantomData,
472 }
473 }
474}
475
476impl<Spec> BstNodeRef<marker::DormantMut, Spec>
477where
478 Spec: BstSpec,
479{
480 pub unsafe fn awaken<'a>(self) -> BstNodeRef<marker::Mut<'a>, Spec> {
481 BstNodeRef {
482 node: self.node,
483 _marker: PhantomData,
484 }
485 }
486}
487
488impl<Spec> BstNodeRef<marker::Dying, Spec>
489where
490 Spec: BstSpec,
491{
492 pub unsafe fn into_data<A>(self, allocator: &mut A) -> Spec::Data
493 where
494 A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
495 {
496 debug_assert!(self.reborrow().left().descend().is_err());
497 debug_assert!(self.reborrow().right().descend().is_err());
498 allocator.deallocate(self.node).data
499 }crates/competitive/src/data_structure/implicit_splay_tree.rs (line 115)
112 fn top_down(mut node: BstDataMutRef<'_, Self>) {
113 if !T::is_act_unit(&node.reborrow().into_data().value.act) {
114 let act = replace(&mut node.data_mut().value.act, T::act_unit());
115 if let Ok(left) = node.reborrow_datamut().left().descend() {
116 Self::update_act(left, &act);
117 }
118 if let Ok(right) = node.reborrow_datamut().right().descend() {
119 Self::update_act(right, &act);
120 }
121 }
122 if node.reborrow().into_data().rev {
123 node.data_mut().rev = false;
124 if let Ok(left) = node.reborrow_datamut().left().descend() {
125 Self::reverse(left);
126 }
127 if let Ok(right) = node.reborrow_datamut().right().descend() {
128 Self::reverse(right);
129 }
130 }
131 }
132
133 fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
134 let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
135 let mut size = 1;
136 if let Ok(left) = node.reborrow().left().descend() {
137 let data = left.into_data();
138 agg = T::agg_operate(&data.value.agg, &agg);
139 size += data.size;
140 }
141 if let Ok(right) = node.reborrow().right().descend() {
142 let data = right.into_data();
143 agg = T::agg_operate(&agg, &data.value.agg);
144 size += data.size;
145 }
146 let data = node.data_mut();
147 data.value.agg = agg;
148 data.size = size;
149 }crates/competitive/src/data_structure/implicit_treap.rs (line 116)
113 fn top_down(mut node: BstDataMutRef<'_, Self>) {
114 if !T::is_act_unit(&node.reborrow().into_data().value.act) {
115 let act = replace(&mut node.data_mut().value.act, T::act_unit());
116 if let Ok(left) = node.reborrow_datamut().left().descend() {
117 Self::update_act(left, &act);
118 }
119 if let Ok(right) = node.reborrow_datamut().right().descend() {
120 Self::update_act(right, &act);
121 }
122 }
123 if node.reborrow().into_data().rev {
124 node.data_mut().rev = false;
125 if let Ok(left) = node.reborrow_datamut().left().descend() {
126 Self::reverse(left);
127 }
128 if let Ok(right) = node.reborrow_datamut().right().descend() {
129 Self::reverse(right);
130 }
131 }
132 }
133
134 fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
135 let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
136 let mut size = 1;
137 if let Ok(left) = node.reborrow().left().descend() {
138 let data = left.into_data();
139 agg = T::agg_operate(&data.value.agg, &agg);
140 size += data.size;
141 }
142 if let Ok(right) = node.reborrow().right().descend() {
143 let data = right.into_data();
144 agg = T::agg_operate(&agg, &data.value.agg);
145 size += data.size;
146 }
147 let data = node.data_mut();
148 data.value.agg = agg;
149 data.size = size;
150 }
151
152 fn merge(
153 left: Option<ImplicitTreapRoot<T>>,
154 right: Option<ImplicitTreapRoot<T>>,
155 ) -> Option<ImplicitTreapRoot<T>> {
156 match (left, right) {
157 (None, None) => None,
158 (None, Some(node)) | (Some(node), None) => Some(node),
159 (Some(mut left), Some(mut right)) => unsafe {
160 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
161 Self::top_down(left.borrow_datamut());
162 let lr = left.borrow_mut().right().take();
163 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
164 left.borrow_mut().right().set(lr);
165 Self::bottom_up(left.borrow_datamut());
166 Some(left)
167 } else {
168 Self::top_down(right.borrow_datamut());
169 let rl = right.borrow_mut().left().take();
170 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
171 right.borrow_mut().left().set(rl);
172 Self::bottom_up(right.borrow_datamut());
173 Some(right)
174 }
175 },
176 }
177 }
178
179 fn split<Seeker>(
180 node: Option<ImplicitTreapRoot<T>>,
181 mut seeker: Seeker,
182 equal_side: EqualSide,
183 ) -> (Option<ImplicitTreapRoot<T>>, Option<ImplicitTreapRoot<T>>)
184 where
185 Seeker: BstSeeker<Spec = Self>,
186 {
187 match node {
188 None => (None, None),
189 Some(mut node) => {
190 Self::top_down(node.borrow_datamut());
191 if equal_side.goes_left(seeker.bst_seek(node.reborrow())) {
192 unsafe {
193 let right = node.borrow_mut().right().take();
194 let (l, r) = Self::split(right, seeker, equal_side);
195 if let Some(l) = l {
196 node.borrow_mut().right().set(l);
197 }
198 Self::bottom_up(node.borrow_datamut());
199 (Some(node), r)
200 }
201 } else {
202 unsafe {
203 let left = node.borrow_mut().left().take();
204 let (l, r) = Self::split(left, seeker, equal_side);
205 if let Some(r) = r {
206 node.borrow_mut().left().set(r);
207 }
208 Self::bottom_up(node.borrow_datamut());
209 (l, Some(node))
210 }
211 }
212 }
213 }
214 }
215}
216
217pub struct ImplicitTreap<T, A = MemoryPool<ImplicitTreapNode<T>>>
218where
219 T: LazyMapMonoid,
220 A: Allocator<ImplicitTreapNode<T>>,
221{
222 root: Option<ImplicitTreapRoot<T>>,
223 length: usize,
224 rng: Xorshift,
225 allocator: ManuallyDrop<A>,
226 _marker: PhantomData<fn() -> T>,
227}
228
229impl<T, A> Default for ImplicitTreap<T, A>
230where
231 T: LazyMapMonoid,
232 A: Allocator<ImplicitTreapNode<T>> + Default,
233{
234 fn default() -> Self {
235 Self {
236 root: None,
237 length: 0,
238 rng: Xorshift::new(),
239 allocator: ManuallyDrop::new(A::default()),
240 _marker: PhantomData,
241 }
242 }
243}
244
245impl<T, A> Drop for ImplicitTreap<T, A>
246where
247 T: LazyMapMonoid,
248 A: Allocator<ImplicitTreapNode<T>>,
249{
250 fn drop(&mut self) {
251 unsafe {
252 if let Some(root) = self.root.take() {
253 root.into_dying().drop_all(self.allocator.deref_mut());
254 }
255 ManuallyDrop::drop(&mut self.allocator);
256 }
257 }
258}
259
260impl<T> ImplicitTreap<T>
261where
262 T: LazyMapMonoid,
263{
264 pub fn new() -> Self {
265 Self::default()
266 }
267
268 pub fn with_capacity(capacity: usize) -> Self {
269 Self {
270 root: None,
271 length: 0,
272 rng: Xorshift::new(),
273 allocator: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
274 _marker: PhantomData,
275 }
276 }
277}
278
279impl<T, A> ImplicitTreap<T, A>
280where
281 T: LazyMapMonoid,
282 A: Allocator<ImplicitTreapNode<T>>,
283{
284 fn node(&mut self, key: T::Key) -> ImplicitTreapRoot<T> {
285 BstRoot::from_data(
286 ImplicitTreapData {
287 priority: self.rng.rand64(),
288 value: LazyMapElement::from_key(key),
289 size: 1,
290 rev: false,
291 },
292 self.allocator.deref_mut(),
293 )
294 }
295
296 fn build<I>(&mut self, iter: I) -> (Option<ImplicitTreapRoot<T>>, usize)
297 where
298 I: IntoIterator<Item = T::Key>,
299 {
300 let mut stack = vec![];
301 let mut len = 0;
302 for key in iter {
303 let mut cur = self.node(key).node;
304 let mut left = None;
305 unsafe {
306 while stack
307 .last()
308 .is_some_and(|node: &NonNull<ImplicitTreapNode<T>>| {
309 node.as_ref().data.priority < cur.as_ref().data.priority
310 })
311 {
312 left = stack.pop();
313 }
314 cur.as_mut().child[0] = left;
315 if let Some(parent) = stack.last_mut() {
316 parent.as_mut().child[1] = Some(cur);
317 }
318 }
319 stack.push(cur);
320 len += 1;
321 }
322 let root = stack.first().copied().map(BstRoot::new);
323 if let Some(mut root) = root {
324 Self::build_bottom_up(root.borrow_datamut());
325 (Some(root), len)
326 } else {
327 (None, len)
328 }
329 }
330
331 fn build_bottom_up(mut node: BstDataMutRef<'_, ImplicitTreapSpec<T>>) {
332 if let Ok(left) = node.reborrow_datamut().left().descend() {
333 Self::build_bottom_up(left);
334 }
335 if let Ok(right) = node.reborrow_datamut().right().descend() {
336 Self::build_bottom_up(right);
337 }
338 ImplicitTreapSpec::<T>::bottom_up(node);
339 }Additional examples can be found in:
Source§impl<'a, Spec, Dir> BstEdgeHandle<BstNodeRef<Mut<'a>, Spec>, Dir>where
Spec: BstSpec,
Dir: BstDirection,
impl<'a, Spec, Dir> BstEdgeHandle<BstNodeRef<Mut<'a>, Spec>, Dir>where
Spec: BstSpec,
Dir: BstDirection,
Sourcepub unsafe fn take(&mut self) -> Option<BstNodeRef<Owned, Spec>>
pub unsafe fn take(&mut self) -> Option<BstNodeRef<Owned, Spec>>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 185)
177 pub unsafe fn remove_root<Spec>(
178 root: &mut Option<BstRoot<Spec>>,
179 ) -> Option<BstNodeRef<marker::Owned, Spec>>
180 where
181 Spec: BstSpec<Data = Data, Parent = Self>,
182 {
183 let mut node = root.take()?;
184 unsafe {
185 let left = node.borrow_mut().left_mut().take();
186 let right = node.borrow_mut().right_mut().take();
187 *root = Spec::merge(left, right);
188 Spec::bottom_up(node.borrow_datamut());
189 Some(node)
190 }
191 }
192
193 pub unsafe fn remove_not_root<Spec>(
194 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
195 ) -> BstNodeRef<marker::Owned, Spec>
196 where
197 Spec: BstSpec<Data = Data, Parent = Self>,
198 {
199 assert!(!Self::is_root(node.reborrow()));
200 unsafe {
201 let left = node.left_mut().take();
202 let right = node.right_mut().take();
203 let merged = Spec::merge(left, right);
204 let node_inner = node.node;
205 let mut parent = node.ascend().unwrap_unchecked();
206 let mut node = if let Some(merged) = merged {
207 let node = if parent
208 .reborrow()
209 .left()
210 .descend()
211 .is_ok_and(|n| n.node == node_inner)
212 {
213 parent.left_mut().replace(merged)
214 } else {
215 parent.right_mut().replace(merged)
216 };
217 Self::resolve_bottom_up(parent.reborrow_datamut());
218 node.unwrap_unchecked()
219 } else {
220 let node = if parent
221 .reborrow()
222 .left()
223 .descend()
224 .is_ok_and(|n| n.node == node_inner)
225 {
226 parent.left_mut().take()
227 } else {
228 parent.right_mut().take()
229 };
230 Self::resolve_bottom_up(parent.reborrow_datamut());
231 node.unwrap_unchecked()
232 };
233 Spec::bottom_up(node.borrow_datamut());
234 node
235 }
236 }More examples
crates/competitive/src/data_structure/implicit_splay_tree.rs (line 333)
320 pub fn insert(&mut self, index: usize, key: T::Key) {
321 assert!(index <= self.length);
322 let mut node = self.node(key);
323 if self.root.is_none() {
324 self.root = Some(node);
325 } else if index == self.length {
326 self.splay(SeekBySize::new(index));
327 unsafe { node.borrow_mut().left_mut().set(self.root.take().unwrap()) };
328 ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
329 self.root = Some(node);
330 } else {
331 self.splay(SeekBySize::new(index));
332 let mut root = self.root.take().unwrap();
333 let left = unsafe { root.borrow_mut().left_mut().take() };
334 if let Some(left) = left {
335 unsafe { node.borrow_mut().left_mut().set(left) };
336 }
337 ImplicitSplayTreeSpec::bottom_up(root.borrow_datamut());
338 unsafe { node.borrow_mut().right_mut().set(root) };
339 ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
340 self.root = Some(node);
341 }
342 self.length += 1;
343 }
344
345 pub fn remove(&mut self, index: usize) -> Option<T::Key> {
346 if index >= self.length {
347 return None;
348 }
349 self.splay(SeekBySize::new(index));
350 let mut node = self.root.take().unwrap();
351 ImplicitSplayTreeSpec::top_down(node.borrow_datamut());
352 let left = unsafe { node.borrow_mut().left_mut().take() };
353 let right = unsafe { node.borrow_mut().right_mut().take() };
354 self.root = ImplicitSplayTreeSpec::merge(left, right);
355 self.length -= 1;
356 let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
357 Some(data.value.key)
358 }crates/competitive/src/data_structure/implicit_treap.rs (line 162)
152 fn merge(
153 left: Option<ImplicitTreapRoot<T>>,
154 right: Option<ImplicitTreapRoot<T>>,
155 ) -> Option<ImplicitTreapRoot<T>> {
156 match (left, right) {
157 (None, None) => None,
158 (None, Some(node)) | (Some(node), None) => Some(node),
159 (Some(mut left), Some(mut right)) => unsafe {
160 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
161 Self::top_down(left.borrow_datamut());
162 let lr = left.borrow_mut().right().take();
163 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
164 left.borrow_mut().right().set(lr);
165 Self::bottom_up(left.borrow_datamut());
166 Some(left)
167 } else {
168 Self::top_down(right.borrow_datamut());
169 let rl = right.borrow_mut().left().take();
170 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
171 right.borrow_mut().left().set(rl);
172 Self::bottom_up(right.borrow_datamut());
173 Some(right)
174 }
175 },
176 }
177 }
178
179 fn split<Seeker>(
180 node: Option<ImplicitTreapRoot<T>>,
181 mut seeker: Seeker,
182 equal_side: EqualSide,
183 ) -> (Option<ImplicitTreapRoot<T>>, Option<ImplicitTreapRoot<T>>)
184 where
185 Seeker: BstSeeker<Spec = Self>,
186 {
187 match node {
188 None => (None, None),
189 Some(mut node) => {
190 Self::top_down(node.borrow_datamut());
191 if equal_side.goes_left(seeker.bst_seek(node.reborrow())) {
192 unsafe {
193 let right = node.borrow_mut().right().take();
194 let (l, r) = Self::split(right, seeker, equal_side);
195 if let Some(l) = l {
196 node.borrow_mut().right().set(l);
197 }
198 Self::bottom_up(node.borrow_datamut());
199 (Some(node), r)
200 }
201 } else {
202 unsafe {
203 let left = node.borrow_mut().left().take();
204 let (l, r) = Self::split(left, seeker, equal_side);
205 if let Some(r) = r {
206 node.borrow_mut().left().set(r);
207 }
208 Self::bottom_up(node.borrow_datamut());
209 (l, Some(node))
210 }
211 }
212 }
213 }
214 }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 equal_side: EqualSide,
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 if equal_side.goes_left(seeker.bst_seek(node.reborrow())) {
157 unsafe {
158 let right = node.borrow_mut().right().take();
159 let (l, r) = Self::split(right, seeker, equal_side);
160 if let Some(l) = l {
161 node.borrow_mut().right().set(l);
162 }
163 Self::bottom_up(node.borrow_datamut());
164 (Some(node), r)
165 }
166 } else {
167 unsafe {
168 let left = node.borrow_mut().left().take();
169 let (l, r) = Self::split(left, seeker, equal_side);
170 if let Some(r) = r {
171 node.borrow_mut().left().set(r);
172 }
173 Self::bottom_up(node.borrow_datamut());
174 (l, Some(node))
175 }
176 }
177 }
178 }
179 }
180}
181
182impl<M, L> TreapSpec<M, L>
183where
184 M: MonoidAct<Key: Ord>,
185 L: LazyMapMonoid,
186{
187 pub fn merge_ordered(
188 left: Option<TreapRoot<M, L>>,
189 right: Option<TreapRoot<M, L>>,
190 ) -> Option<TreapRoot<M, L>> {
191 match (left, right) {
192 (None, None) => None,
193 (None, Some(node)) | (Some(node), None) => Some(node),
194 (Some(mut left), Some(mut right)) => unsafe {
195 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
196 Self::top_down(left.borrow_datamut());
197 let key = &left.reborrow().into_data().key.key;
198 let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), EqualSide::Right);
199 let ll = left.borrow_mut().left().take();
200 let lr = left.borrow_mut().right().take();
201 if let Some(l) = Self::merge_ordered(ll, rl) {
202 left.borrow_mut().left().set(l);
203 }
204 if let Some(r) = Self::merge_ordered(lr, rr) {
205 left.borrow_mut().right().set(r);
206 }
207 Self::bottom_up(left.borrow_datamut());
208 Some(left)
209 } else {
210 Self::top_down(right.borrow_datamut());
211 let key = &right.reborrow().into_data().key.key;
212 let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), EqualSide::Right);
213 let rl = right.borrow_mut().left().take();
214 let rr = right.borrow_mut().right().take();
215 if let Some(l) = Self::merge_ordered(ll, rl) {
216 right.borrow_mut().left().set(l);
217 }
218 if let Some(r) = Self::merge_ordered(lr, rr) {
219 right.borrow_mut().right().set(r);
220 }
221 Self::bottom_up(right.borrow_datamut());
222 Some(right)
223 }
224 },
225 }
226 }crates/competitive/src/data_structure/splay_tree.rs (line 260)
232 pub fn insert(&mut self, key: K, value: V) -> Option<V>
233 where
234 K: Ord,
235 {
236 let ordering = self.splay_by_key(&key);
237 if matches!(ordering, Some(Ordering::Equal)) {
238 return Some(replace(
239 &mut self
240 .root
241 .as_mut()
242 .unwrap()
243 .borrow_datamut()
244 .data_mut()
245 .value,
246 value,
247 ));
248 }
249 let mut node = BstRoot::from_data(
250 SplayTreeData {
251 key,
252 value,
253 size: 1,
254 },
255 self.allocator.deref_mut(),
256 );
257 if let Some(mut root) = self.root.take() {
258 match ordering.unwrap() {
259 Ordering::Greater => {
260 let left = unsafe { root.borrow_mut().left_mut().take() };
261 if let Some(left) = left {
262 unsafe { node.borrow_mut().left_mut().set(left) };
263 }
264 SplayTreeSpec::bottom_up(root.borrow_datamut());
265 unsafe { node.borrow_mut().right_mut().set(root) };
266 }
267 Ordering::Less => {
268 let right = unsafe { root.borrow_mut().right_mut().take() };
269 if let Some(right) = right {
270 unsafe { node.borrow_mut().right_mut().set(right) };
271 }
272 SplayTreeSpec::bottom_up(root.borrow_datamut());
273 unsafe { node.borrow_mut().left_mut().set(root) };
274 }
275 Ordering::Equal => unreachable!(),
276 }
277 SplayTreeSpec::bottom_up(node.borrow_datamut());
278 }
279 self.root = Some(node);
280 self.length += 1;
281 None
282 }
283
284 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
285 where
286 K: Borrow<Q>,
287 Q: Ord + ?Sized,
288 {
289 if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
290 return None;
291 }
292 Some(self.remove_root().1)
293 }
294
295 pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
296 if index >= self.length {
297 return None;
298 }
299 self.splay_by_size(index);
300 Some(self.remove_root())
301 }
302
303 fn remove_root(&mut self) -> (K, V) {
304 let mut node = self.root.take().unwrap();
305 let left = unsafe { node.borrow_mut().left_mut().take() };
306 let right = unsafe { node.borrow_mut().right_mut().take() };
307 self.root = SplayTreeSpec::merge(left, right);
308 self.length -= 1;
309 let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
310 (data.key, data.value)
311 }crates/competitive/src/data_structure/splay_operations.rs (line 279)
234pub fn splay<Spec, Data, Seeker>(
235 root: BstRoot<Spec>,
236 mut seeker: Seeker,
237) -> (Ordering, BstRoot<Spec>)
238where
239 Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
240 Seeker: BstSeeker<Spec = Spec>,
241{
242 let mut root = root;
243 let mut left_subtree = None;
244 let mut right_subtree = None;
245 let mut left_entry = &mut left_subtree;
246 let mut right_entry = &mut right_subtree;
247 let mut inline_stack = [None; 24];
248 let mut inline_len = 0;
249 let mut overflow_stack = vec![];
250
251 macro_rules! push_node {
252 ($node:expr) => {
253 if inline_len < inline_stack.len() {
254 inline_stack[inline_len] = Some($node);
255 inline_len += 1;
256 } else {
257 overflow_stack.push($node);
258 }
259 };
260 }
261
262 macro_rules! add {
263 (@left $node:ident) => {
264 *left_entry = Some($node.node);
265 push_node!($node.node);
266 left_entry = unsafe { &mut $node.node.as_mut().child[1] };
267 };
268 (@right $node:ident) => {
269 *right_entry = Some($node.node);
270 push_node!($node.node);
271 right_entry = unsafe { &mut $node.node.as_mut().child[0] };
272 };
273 }
274
275 let root_ordering = loop {
276 Spec::top_down(root.borrow_datamut());
277 match seeker.bst_seek(root.reborrow()) {
278 Ordering::Greater => {
279 let Some(mut child) = (unsafe { root.borrow_mut().left_mut().take() }) else {
280 break Ordering::Greater;
281 };
282 Spec::top_down(child.borrow_datamut());
283 match seeker.bst_seek(child.reborrow()) {
284 Ordering::Greater => {
285 let Some(mut grandchild) =
286 (unsafe { child.borrow_mut().left_mut().take() })
287 else {
288 add!(@right root);
289 root = child;
290 break Ordering::Greater;
291 };
292 Spec::top_down(grandchild.borrow_datamut());
293 let child_right = unsafe { child.borrow_mut().right_mut().take() };
294 if let Some(child_right) = child_right {
295 unsafe { root.borrow_mut().left_mut().set(child_right) };
296 }
297 Spec::bottom_up(root.borrow_datamut());
298 unsafe { child.borrow_mut().right_mut().set(root) };
299 add!(@right child);
300 root = grandchild;
301 }
302 Ordering::Equal => {
303 add!(@right root);
304 root = child;
305 break Ordering::Equal;
306 }
307 Ordering::Less => {
308 let Some(mut grandchild) =
309 (unsafe { child.borrow_mut().right_mut().take() })
310 else {
311 add!(@right root);
312 root = child;
313 break Ordering::Less;
314 };
315 Spec::top_down(grandchild.borrow_datamut());
316 add!(@right root);
317 add!(@left child);
318 root = grandchild;
319 }
320 }
321 }
322 Ordering::Equal => break Ordering::Equal,
323 Ordering::Less => {
324 let Some(mut child) = (unsafe { root.borrow_mut().right_mut().take() }) else {
325 break Ordering::Less;
326 };
327 Spec::top_down(child.borrow_datamut());
328 match seeker.bst_seek(child.reborrow()) {
329 Ordering::Greater => {
330 let Some(mut grandchild) =
331 (unsafe { child.borrow_mut().left_mut().take() })
332 else {
333 add!(@left root);
334 root = child;
335 break Ordering::Greater;
336 };
337 Spec::top_down(grandchild.borrow_datamut());
338 add!(@left root);
339 add!(@right child);
340 root = grandchild;
341 }
342 Ordering::Equal => {
343 add!(@left root);
344 root = child;
345 break Ordering::Equal;
346 }
347 Ordering::Less => {
348 let Some(mut grandchild) =
349 (unsafe { child.borrow_mut().right_mut().take() })
350 else {
351 add!(@left root);
352 root = child;
353 break Ordering::Less;
354 };
355 Spec::top_down(grandchild.borrow_datamut());
356 let child_left = unsafe { child.borrow_mut().left_mut().take() };
357 if let Some(child_left) = child_left {
358 unsafe { root.borrow_mut().right_mut().set(child_left) };
359 }
360 Spec::bottom_up(root.borrow_datamut());
361 unsafe { child.borrow_mut().left_mut().set(root) };
362 add!(@left child);
363 root = grandchild;
364 }
365 }
366 }
367 }
368 };
369
370 *left_entry = unsafe { root.borrow_mut().left_mut().take() }.map(|node| node.node);
371 *right_entry = unsafe { root.borrow_mut().right_mut().take() }.map(|node| node.node);
372 unsafe {
373 root.node.as_mut().child[0] = left_subtree;
374 root.node.as_mut().child[1] = right_subtree;
375 while let Some(node) = overflow_stack.pop() {
376 Spec::bottom_up(BstRoot::new(node).borrow_datamut());
377 }
378 while inline_len > 0 {
379 inline_len -= 1;
380 let node = inline_stack[inline_len].unwrap_unchecked();
381 Spec::bottom_up(BstRoot::new(node).borrow_datamut());
382 }
383 }
384 Spec::bottom_up(root.borrow_datamut());
385 (root_ordering, root)
386}
387
388#[inline]
389pub fn merge<Spec, Data>(
390 left: Option<BstRoot<Spec>>,
391 right: Option<BstRoot<Spec>>,
392) -> Option<BstRoot<Spec>>
393where
394 Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
395{
396 match (left, right) {
397 (None, None) => None,
398 (None, Some(root)) | (Some(root), None) => Some(root),
399 (Some(left), Some(mut right)) if right.reborrow().left().descend().is_err() => {
400 Spec::top_down(right.borrow_datamut());
401 unsafe { right.borrow_mut().left_mut().set(left) };
402 Spec::bottom_up(right.borrow_datamut());
403 Some(right)
404 }
405 (Some(left), Some(right)) => {
406 let (_, mut root) = splay(left, SeekRight::default());
407 unsafe { root.borrow_mut().right_mut().set(right) };
408 Spec::bottom_up(root.borrow_datamut());
409 Some(root)
410 }
411 }
412}
413
414#[inline]
415pub fn split<Spec, Data, Seeker>(
416 root: Option<BstRoot<Spec>>,
417 seeker: Seeker,
418 equal_side: EqualSide,
419) -> (Option<BstRoot<Spec>>, Option<BstRoot<Spec>>)
420where
421 Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
422 Seeker: BstSeeker<Spec = Spec>,
423{
424 let Some(root) = root else {
425 return (None, None);
426 };
427 let (ordering, mut root) = splay(root, seeker);
428 if equal_side.goes_left(ordering) {
429 let right = unsafe { root.borrow_mut().right_mut().take() };
430 Spec::bottom_up(root.borrow_datamut());
431 (Some(root), right)
432 } else {
433 let left = unsafe { root.borrow_mut().left_mut().take() };
434 Spec::bottom_up(root.borrow_datamut());
435 (left, Some(root))
436 }
437}Sourcepub unsafe fn replace(
&mut self,
other: BstNodeRef<Owned, Spec>,
) -> Option<BstNodeRef<Owned, Spec>>
pub unsafe fn replace( &mut self, other: BstNodeRef<Owned, Spec>, ) -> Option<BstNodeRef<Owned, Spec>>
Examples found in repository?
crates/competitive/src/data_structure/binary_search_tree/node.rs (line 213)
193 pub unsafe fn remove_not_root<Spec>(
194 mut node: BstNodeRef<marker::Mut<'_>, Spec>,
195 ) -> BstNodeRef<marker::Owned, Spec>
196 where
197 Spec: BstSpec<Data = Data, Parent = Self>,
198 {
199 assert!(!Self::is_root(node.reborrow()));
200 unsafe {
201 let left = node.left_mut().take();
202 let right = node.right_mut().take();
203 let merged = Spec::merge(left, right);
204 let node_inner = node.node;
205 let mut parent = node.ascend().unwrap_unchecked();
206 let mut node = if let Some(merged) = merged {
207 let node = if parent
208 .reborrow()
209 .left()
210 .descend()
211 .is_ok_and(|n| n.node == node_inner)
212 {
213 parent.left_mut().replace(merged)
214 } else {
215 parent.right_mut().replace(merged)
216 };
217 Self::resolve_bottom_up(parent.reborrow_datamut());
218 node.unwrap_unchecked()
219 } else {
220 let node = if parent
221 .reborrow()
222 .left()
223 .descend()
224 .is_ok_and(|n| n.node == node_inner)
225 {
226 parent.left_mut().take()
227 } else {
228 parent.right_mut().take()
229 };
230 Self::resolve_bottom_up(parent.reborrow_datamut());
231 node.unwrap_unchecked()
232 };
233 Spec::bottom_up(node.borrow_datamut());
234 node
235 }
236 }Sourcepub unsafe fn set(&mut self, other: BstNodeRef<Owned, Spec>)
pub unsafe fn set(&mut self, other: BstNodeRef<Owned, Spec>)
Examples found in repository?
crates/competitive/src/data_structure/implicit_splay_tree.rs (line 327)
320 pub fn insert(&mut self, index: usize, key: T::Key) {
321 assert!(index <= self.length);
322 let mut node = self.node(key);
323 if self.root.is_none() {
324 self.root = Some(node);
325 } else if index == self.length {
326 self.splay(SeekBySize::new(index));
327 unsafe { node.borrow_mut().left_mut().set(self.root.take().unwrap()) };
328 ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
329 self.root = Some(node);
330 } else {
331 self.splay(SeekBySize::new(index));
332 let mut root = self.root.take().unwrap();
333 let left = unsafe { root.borrow_mut().left_mut().take() };
334 if let Some(left) = left {
335 unsafe { node.borrow_mut().left_mut().set(left) };
336 }
337 ImplicitSplayTreeSpec::bottom_up(root.borrow_datamut());
338 unsafe { node.borrow_mut().right_mut().set(root) };
339 ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
340 self.root = Some(node);
341 }
342 self.length += 1;
343 }More examples
crates/competitive/src/data_structure/implicit_treap.rs (line 164)
152 fn merge(
153 left: Option<ImplicitTreapRoot<T>>,
154 right: Option<ImplicitTreapRoot<T>>,
155 ) -> Option<ImplicitTreapRoot<T>> {
156 match (left, right) {
157 (None, None) => None,
158 (None, Some(node)) | (Some(node), None) => Some(node),
159 (Some(mut left), Some(mut right)) => unsafe {
160 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
161 Self::top_down(left.borrow_datamut());
162 let lr = left.borrow_mut().right().take();
163 let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
164 left.borrow_mut().right().set(lr);
165 Self::bottom_up(left.borrow_datamut());
166 Some(left)
167 } else {
168 Self::top_down(right.borrow_datamut());
169 let rl = right.borrow_mut().left().take();
170 let rl = Self::merge(Some(left), rl).unwrap_unchecked();
171 right.borrow_mut().left().set(rl);
172 Self::bottom_up(right.borrow_datamut());
173 Some(right)
174 }
175 },
176 }
177 }
178
179 fn split<Seeker>(
180 node: Option<ImplicitTreapRoot<T>>,
181 mut seeker: Seeker,
182 equal_side: EqualSide,
183 ) -> (Option<ImplicitTreapRoot<T>>, Option<ImplicitTreapRoot<T>>)
184 where
185 Seeker: BstSeeker<Spec = Self>,
186 {
187 match node {
188 None => (None, None),
189 Some(mut node) => {
190 Self::top_down(node.borrow_datamut());
191 if equal_side.goes_left(seeker.bst_seek(node.reborrow())) {
192 unsafe {
193 let right = node.borrow_mut().right().take();
194 let (l, r) = Self::split(right, seeker, equal_side);
195 if let Some(l) = l {
196 node.borrow_mut().right().set(l);
197 }
198 Self::bottom_up(node.borrow_datamut());
199 (Some(node), r)
200 }
201 } else {
202 unsafe {
203 let left = node.borrow_mut().left().take();
204 let (l, r) = Self::split(left, seeker, equal_side);
205 if let Some(r) = r {
206 node.borrow_mut().left().set(r);
207 }
208 Self::bottom_up(node.borrow_datamut());
209 (l, Some(node))
210 }
211 }
212 }
213 }
214 }crates/competitive/src/data_structure/treap.rs (line 129)
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 equal_side: EqualSide,
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 if equal_side.goes_left(seeker.bst_seek(node.reborrow())) {
157 unsafe {
158 let right = node.borrow_mut().right().take();
159 let (l, r) = Self::split(right, seeker, equal_side);
160 if let Some(l) = l {
161 node.borrow_mut().right().set(l);
162 }
163 Self::bottom_up(node.borrow_datamut());
164 (Some(node), r)
165 }
166 } else {
167 unsafe {
168 let left = node.borrow_mut().left().take();
169 let (l, r) = Self::split(left, seeker, equal_side);
170 if let Some(r) = r {
171 node.borrow_mut().left().set(r);
172 }
173 Self::bottom_up(node.borrow_datamut());
174 (l, Some(node))
175 }
176 }
177 }
178 }
179 }
180}
181
182impl<M, L> TreapSpec<M, L>
183where
184 M: MonoidAct<Key: Ord>,
185 L: LazyMapMonoid,
186{
187 pub fn merge_ordered(
188 left: Option<TreapRoot<M, L>>,
189 right: Option<TreapRoot<M, L>>,
190 ) -> Option<TreapRoot<M, L>> {
191 match (left, right) {
192 (None, None) => None,
193 (None, Some(node)) | (Some(node), None) => Some(node),
194 (Some(mut left), Some(mut right)) => unsafe {
195 if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
196 Self::top_down(left.borrow_datamut());
197 let key = &left.reborrow().into_data().key.key;
198 let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), EqualSide::Right);
199 let ll = left.borrow_mut().left().take();
200 let lr = left.borrow_mut().right().take();
201 if let Some(l) = Self::merge_ordered(ll, rl) {
202 left.borrow_mut().left().set(l);
203 }
204 if let Some(r) = Self::merge_ordered(lr, rr) {
205 left.borrow_mut().right().set(r);
206 }
207 Self::bottom_up(left.borrow_datamut());
208 Some(left)
209 } else {
210 Self::top_down(right.borrow_datamut());
211 let key = &right.reborrow().into_data().key.key;
212 let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), EqualSide::Right);
213 let rl = right.borrow_mut().left().take();
214 let rr = right.borrow_mut().right().take();
215 if let Some(l) = Self::merge_ordered(ll, rl) {
216 right.borrow_mut().left().set(l);
217 }
218 if let Some(r) = Self::merge_ordered(lr, rr) {
219 right.borrow_mut().right().set(r);
220 }
221 Self::bottom_up(right.borrow_datamut());
222 Some(right)
223 }
224 },
225 }
226 }crates/competitive/src/data_structure/splay_tree.rs (line 262)
232 pub fn insert(&mut self, key: K, value: V) -> Option<V>
233 where
234 K: Ord,
235 {
236 let ordering = self.splay_by_key(&key);
237 if matches!(ordering, Some(Ordering::Equal)) {
238 return Some(replace(
239 &mut self
240 .root
241 .as_mut()
242 .unwrap()
243 .borrow_datamut()
244 .data_mut()
245 .value,
246 value,
247 ));
248 }
249 let mut node = BstRoot::from_data(
250 SplayTreeData {
251 key,
252 value,
253 size: 1,
254 },
255 self.allocator.deref_mut(),
256 );
257 if let Some(mut root) = self.root.take() {
258 match ordering.unwrap() {
259 Ordering::Greater => {
260 let left = unsafe { root.borrow_mut().left_mut().take() };
261 if let Some(left) = left {
262 unsafe { node.borrow_mut().left_mut().set(left) };
263 }
264 SplayTreeSpec::bottom_up(root.borrow_datamut());
265 unsafe { node.borrow_mut().right_mut().set(root) };
266 }
267 Ordering::Less => {
268 let right = unsafe { root.borrow_mut().right_mut().take() };
269 if let Some(right) = right {
270 unsafe { node.borrow_mut().right_mut().set(right) };
271 }
272 SplayTreeSpec::bottom_up(root.borrow_datamut());
273 unsafe { node.borrow_mut().left_mut().set(root) };
274 }
275 Ordering::Equal => unreachable!(),
276 }
277 SplayTreeSpec::bottom_up(node.borrow_datamut());
278 }
279 self.root = Some(node);
280 self.length += 1;
281 None
282 }crates/competitive/src/data_structure/splay_operations.rs (line 295)
234pub fn splay<Spec, Data, Seeker>(
235 root: BstRoot<Spec>,
236 mut seeker: Seeker,
237) -> (Ordering, BstRoot<Spec>)
238where
239 Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
240 Seeker: BstSeeker<Spec = Spec>,
241{
242 let mut root = root;
243 let mut left_subtree = None;
244 let mut right_subtree = None;
245 let mut left_entry = &mut left_subtree;
246 let mut right_entry = &mut right_subtree;
247 let mut inline_stack = [None; 24];
248 let mut inline_len = 0;
249 let mut overflow_stack = vec![];
250
251 macro_rules! push_node {
252 ($node:expr) => {
253 if inline_len < inline_stack.len() {
254 inline_stack[inline_len] = Some($node);
255 inline_len += 1;
256 } else {
257 overflow_stack.push($node);
258 }
259 };
260 }
261
262 macro_rules! add {
263 (@left $node:ident) => {
264 *left_entry = Some($node.node);
265 push_node!($node.node);
266 left_entry = unsafe { &mut $node.node.as_mut().child[1] };
267 };
268 (@right $node:ident) => {
269 *right_entry = Some($node.node);
270 push_node!($node.node);
271 right_entry = unsafe { &mut $node.node.as_mut().child[0] };
272 };
273 }
274
275 let root_ordering = loop {
276 Spec::top_down(root.borrow_datamut());
277 match seeker.bst_seek(root.reborrow()) {
278 Ordering::Greater => {
279 let Some(mut child) = (unsafe { root.borrow_mut().left_mut().take() }) else {
280 break Ordering::Greater;
281 };
282 Spec::top_down(child.borrow_datamut());
283 match seeker.bst_seek(child.reborrow()) {
284 Ordering::Greater => {
285 let Some(mut grandchild) =
286 (unsafe { child.borrow_mut().left_mut().take() })
287 else {
288 add!(@right root);
289 root = child;
290 break Ordering::Greater;
291 };
292 Spec::top_down(grandchild.borrow_datamut());
293 let child_right = unsafe { child.borrow_mut().right_mut().take() };
294 if let Some(child_right) = child_right {
295 unsafe { root.borrow_mut().left_mut().set(child_right) };
296 }
297 Spec::bottom_up(root.borrow_datamut());
298 unsafe { child.borrow_mut().right_mut().set(root) };
299 add!(@right child);
300 root = grandchild;
301 }
302 Ordering::Equal => {
303 add!(@right root);
304 root = child;
305 break Ordering::Equal;
306 }
307 Ordering::Less => {
308 let Some(mut grandchild) =
309 (unsafe { child.borrow_mut().right_mut().take() })
310 else {
311 add!(@right root);
312 root = child;
313 break Ordering::Less;
314 };
315 Spec::top_down(grandchild.borrow_datamut());
316 add!(@right root);
317 add!(@left child);
318 root = grandchild;
319 }
320 }
321 }
322 Ordering::Equal => break Ordering::Equal,
323 Ordering::Less => {
324 let Some(mut child) = (unsafe { root.borrow_mut().right_mut().take() }) else {
325 break Ordering::Less;
326 };
327 Spec::top_down(child.borrow_datamut());
328 match seeker.bst_seek(child.reborrow()) {
329 Ordering::Greater => {
330 let Some(mut grandchild) =
331 (unsafe { child.borrow_mut().left_mut().take() })
332 else {
333 add!(@left root);
334 root = child;
335 break Ordering::Greater;
336 };
337 Spec::top_down(grandchild.borrow_datamut());
338 add!(@left root);
339 add!(@right child);
340 root = grandchild;
341 }
342 Ordering::Equal => {
343 add!(@left root);
344 root = child;
345 break Ordering::Equal;
346 }
347 Ordering::Less => {
348 let Some(mut grandchild) =
349 (unsafe { child.borrow_mut().right_mut().take() })
350 else {
351 add!(@left root);
352 root = child;
353 break Ordering::Less;
354 };
355 Spec::top_down(grandchild.borrow_datamut());
356 let child_left = unsafe { child.borrow_mut().left_mut().take() };
357 if let Some(child_left) = child_left {
358 unsafe { root.borrow_mut().right_mut().set(child_left) };
359 }
360 Spec::bottom_up(root.borrow_datamut());
361 unsafe { child.borrow_mut().left_mut().set(root) };
362 add!(@left child);
363 root = grandchild;
364 }
365 }
366 }
367 }
368 };
369
370 *left_entry = unsafe { root.borrow_mut().left_mut().take() }.map(|node| node.node);
371 *right_entry = unsafe { root.borrow_mut().right_mut().take() }.map(|node| node.node);
372 unsafe {
373 root.node.as_mut().child[0] = left_subtree;
374 root.node.as_mut().child[1] = right_subtree;
375 while let Some(node) = overflow_stack.pop() {
376 Spec::bottom_up(BstRoot::new(node).borrow_datamut());
377 }
378 while inline_len > 0 {
379 inline_len -= 1;
380 let node = inline_stack[inline_len].unwrap_unchecked();
381 Spec::bottom_up(BstRoot::new(node).borrow_datamut());
382 }
383 }
384 Spec::bottom_up(root.borrow_datamut());
385 (root_ordering, root)
386}
387
388#[inline]
389pub fn merge<Spec, Data>(
390 left: Option<BstRoot<Spec>>,
391 right: Option<BstRoot<Spec>>,
392) -> Option<BstRoot<Spec>>
393where
394 Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
395{
396 match (left, right) {
397 (None, None) => None,
398 (None, Some(root)) | (Some(root), None) => Some(root),
399 (Some(left), Some(mut right)) if right.reborrow().left().descend().is_err() => {
400 Spec::top_down(right.borrow_datamut());
401 unsafe { right.borrow_mut().left_mut().set(left) };
402 Spec::bottom_up(right.borrow_datamut());
403 Some(right)
404 }
405 (Some(left), Some(right)) => {
406 let (_, mut root) = splay(left, SeekRight::default());
407 unsafe { root.borrow_mut().right_mut().set(right) };
408 Spec::bottom_up(root.borrow_datamut());
409 Some(root)
410 }
411 }
412}Auto Trait Implementations§
impl<Node, Dir> Freeze for BstEdgeHandle<Node, Dir>
impl<Node, Dir> RefUnwindSafe for BstEdgeHandle<Node, Dir>
impl<Node, Dir> Send for BstEdgeHandle<Node, Dir>
impl<Node, Dir> Sync for BstEdgeHandle<Node, Dir>
impl<Node, Dir> Unpin for BstEdgeHandle<Node, Dir>
impl<Node, Dir> UnsafeUnpin for BstEdgeHandle<Node, Dir>
impl<Node, Dir> UnwindSafe for BstEdgeHandle<Node, Dir>
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