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().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 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 }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 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 }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 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 197)
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 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/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 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 }Auto Trait Implementations§
impl<Node, Dir> Freeze for BstEdgeHandle<Node, Dir>where
Node: Freeze,
impl<Node, Dir> RefUnwindSafe for BstEdgeHandle<Node, Dir>where
Node: RefUnwindSafe,
Dir: RefUnwindSafe,
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> UnwindSafe for BstEdgeHandle<Node, Dir>where
Node: UnwindSafe,
Dir: UnwindSafe,
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