pub struct NodeRef<B, S>where
S: SplaySpec,{
node: NonNull<Node<S::T>>,
_marker: PhantomData<B>,
}Fields§
§node: NonNull<Node<S::T>>§_marker: PhantomData<B>Implementations§
Source§impl<B, S> NodeRef<B, S>where
S: SplaySpec,
impl<B, S> NodeRef<B, S>where
S: SplaySpec,
Sourceunsafe fn new_unchecked(node: NonNull<Node<S::T>>) -> Self
unsafe fn new_unchecked(node: NonNull<Node<S::T>>) -> Self
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 136)
135 fn reborrow(&self) -> NodeRef<marker::Immut<'_>, S> {
136 unsafe { NodeRef::new_unchecked(self.node) }
137 }
138 fn as_ptr(&self) -> *mut Node<S::T> {
139 self.node.as_ptr()
140 }
141}
142
143impl<S> NodeRef<marker::Owned, S>
144where
145 S: SplaySpec,
146{
147 pub fn new(node: NonNull<Node<S::T>>) -> Self {
148 unsafe { NodeRef::new_unchecked(node) }
149 }
150 pub unsafe fn from_data<A>(data: S::T, allocator: &mut A) -> Self
151 where
152 A: Allocator<Node<S::T>>,
153 {
154 Self::new(allocator.allocate(Node::new(data)))
155 }
156 pub fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, S> {
157 unsafe { NodeRef::new_unchecked(self.node) }
158 }
159 pub fn borrow_datamut(&mut self) -> NodeRef<marker::DataMut<'_>, S> {
160 unsafe { NodeRef::new_unchecked(self.node) }
161 }
162 pub fn into_dying(self) -> NodeRef<marker::Dying, S> {
163 unsafe { NodeRef::new_unchecked(self.node) }
164 }
165}
166
167impl<'a, S> NodeRef<marker::Immut<'a>, S>
168where
169 S: SplaySpec<T: 'a>,
170{
171 pub fn data(&self) -> &'a S::T {
172 unsafe { &(*self.as_ptr()).data }
173 }
174 pub fn left(&self) -> Option<Self> {
175 unsafe {
176 (*self.as_ptr())
177 .left
178 .map(|node| NodeRef::new_unchecked(node))
179 }
180 }
181 pub fn right(&self) -> Option<Self> {
182 unsafe {
183 (*self.as_ptr())
184 .right
185 .map(|node| NodeRef::new_unchecked(node))
186 }
187 }
188 pub fn traverse<F>(self, f: &mut F)
189 where
190 S: SplaySpec<T: 'a>,
191 F: FnMut(Self),
192 {
193 if let Some(left) = self.clone().left() {
194 left.traverse(f);
195 }
196 f(self);
197 if let Some(right) = self.clone().right() {
198 right.traverse(f);
199 }
200 }
201}
202
203impl<'a, S> NodeRef<marker::DataMut<'a>, S>
204where
205 S: SplaySpec<T: 'a>,
206{
207 pub fn data(&self) -> &'a S::T {
208 unsafe { &(*self.as_ptr()).data }
209 }
210 pub fn data_mut(&self) -> &'a mut S::T {
211 unsafe { &mut (*self.as_ptr()).data }
212 }
213 pub fn left(&self) -> Option<Self> {
214 unsafe {
215 (*self.as_ptr())
216 .left
217 .map(|node| NodeRef::new_unchecked(node))
218 }
219 }
220 pub fn right(&self) -> Option<Self> {
221 unsafe {
222 (*self.as_ptr())
223 .right
224 .map(|node| NodeRef::new_unchecked(node))
225 }
226 }
227 pub fn reverse(&self) {
228 unsafe {
229 let node = &mut (*self.as_ptr());
230 swap(&mut node.left, &mut node.right);
231 }
232 }
233}
234
235impl<'a, S> NodeRef<marker::Mut<'a>, S>
236where
237 S: SplaySpec<T: 'a>,
238{
239 pub fn data(self) -> &'a S::T {
240 unsafe { &(*self.as_ptr()).data }
241 }
242 pub fn data_mut(self) -> &'a mut S::T {
243 unsafe { &mut (*self.as_ptr()).data }
244 }
245 pub fn take_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
246 Some(NodeRef::new(unsafe { (*self.as_ptr()).left.take()? }))
247 }
248 pub fn take_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
249 Some(NodeRef::new(unsafe { (*self.as_ptr()).right.take()? }))
250 }
251 pub fn set_left(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
252 unsafe { (*self.as_ptr()).left = node.map(|node| node.node) }
253 }
254 pub fn set_right(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
255 unsafe { (*self.as_ptr()).right = node.map(|node| node.node) }
256 }
257}
258
259impl<S> NodeRef<marker::Dying, S>
260where
261 S: SplaySpec,
262{
263 pub unsafe fn into_inner(self) -> NonNull<Node<S::T>> {
264 let node = self.node;
265 unsafe {
266 debug_assert!((*node.as_ptr()).left.is_none());
267 debug_assert!((*node.as_ptr()).right.is_none());
268 }
269 node
270 }
271 pub unsafe fn into_data<A>(self, allocator: &mut A) -> S::T
272 where
273 A: Allocator<Node<S::T>>,
274 {
275 let Node { data, left, right } = allocator.deallocate(self.node);
276 debug_assert!(left.is_none());
277 debug_assert!(right.is_none());
278 data
279 }
280}
281
282impl<S> NodeRef<marker::Owned, S>
283where
284 S: SplaySpec,
285{
286 /// `cmp(key)`: [`Ordering`] between splaying and `key`
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }
480 pub fn is_empty(&self) -> bool {
481 self.root.is_none()
482 }
483 pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484 Some(self.root.as_ref()?.reborrow())
485 }
486 pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487 Some(self.root.as_mut()?.borrow_datamut())
488 }
489 pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490 where
491 Seeker: SplaySeeker<S = S>,
492 {
493 let (ord, root) = self.root.take()?.splay_by(seeker);
494 self.root = Some(root);
495 Some(ord)
496 }
497 pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498 self.root = Some(match self.root.take() {
499 Some(root) => root.insert_left(node),
500 None => {
501 S::bottom_up(node.borrow_datamut());
502 node
503 }
504 });
505 }
506 pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507 self.root = Some(match self.root.take() {
508 Some(root) => root.insert_right(node),
509 None => {
510 S::bottom_up(node.borrow_datamut());
511 node
512 }
513 });
514 }
515 pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516 self.root = Some(match self.root.take() {
517 Some(root) => root.insert_first(node),
518 None => {
519 S::bottom_up(node.borrow_datamut());
520 node
521 }
522 });
523 }
524 pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525 self.root = Some(match self.root.take() {
526 Some(root) => root.insert_last(node),
527 None => {
528 S::bottom_up(node.borrow_datamut());
529 node
530 }
531 });
532 }
533 pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534 let mut root = self.root.take()?;
535 let right = root.borrow_mut().take_right();
536 self.root = root.borrow_mut().take_left();
537 self.append(&mut Self::new(right));
538 Some(root)
539 }
540 pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541 let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542 let right = root.borrow_mut().take_right();
543 self.root = right;
544 Some(root)
545 }
546 pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547 let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548 let left = root.borrow_mut().take_left();
549 self.root = left;
550 Some(root)
551 }
552 pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553 let root = self.root.as_mut()?;
554 let left = root.borrow_mut().take_left();
555 S::bottom_up(root.borrow_datamut());
556 left
557 }
558 pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
559 let root = self.root.as_mut()?;
560 let right = root.borrow_mut().take_right();
561 S::bottom_up(root.borrow_datamut());
562 right
563 }
564 pub fn split_left_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
565 let right = self.split_right();
566 replace(&mut self.root, right)
567 }
568 pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
569 let left = self.split_left();
570 replace(&mut self.root, left)
571 }
572 pub fn append(&mut self, other: &mut Self) {
573 self.root = match (self.root.take(), other.root.take()) {
574 (Some(node), None) | (None, Some(node)) => Some(node),
575 (Some(left), Some(right)) => Some(left.merge(right)),
576 (None, None) => None,
577 }
578 }
579 pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580 where
581 Seeker: SplaySeeker<S = S>,
582 {
583 if self.is_empty() {
584 return NodeRange::new(self);
585 }
586 let right = match end {
587 Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588 Ordering::Greater | Ordering::Equal => self.split_right(),
589 Ordering::Less => self.split_right_eq(),
590 },
591 Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592 Ordering::Greater => self.split_right(),
593 Ordering::Less | Ordering::Equal => self.split_right_eq(),
594 },
595 Bound::Unbounded => None,
596 };
597 if self.is_empty() {
598 return NodeRange::three_way(None, self, right);
599 }
600 let left = match start {
601 Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602 Ordering::Less | Ordering::Equal => self.split_left(),
603 Ordering::Greater => self.split_left_eq(),
604 },
605 Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606 Ordering::Less => self.split_left(),
607 Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608 },
609 Bound::Unbounded => None,
610 };
611 NodeRange::three_way(left, self, right)
612 }
613}
614
615impl<S> Debug for Root<S>
616where
617 S: SplaySpec<T: Debug>,
618{
619 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
620 fn fmt_recurse<'a, S>(
621 node: NodeRef<marker::Immut<'a>, S>,
622 f: &mut fmt::Formatter<'_>,
623 ) -> fmt::Result
624 where
625 S: SplaySpec<T: 'a + Debug>,
626 {
627 write!(f, "[")?;
628 if let Some(left) = node.left() {
629 fmt_recurse(left, f)?;
630 }
631 node.data().fmt(f)?;
632 if let Some(right) = node.right() {
633 fmt_recurse(right, f)?;
634 }
635 write!(f, "]")?;
636 Ok(())
637 }
638 if let Some(root) = self.root.as_ref() {
639 let root = root.reborrow();
640 fmt_recurse(root, f)?;
641 }
642 Ok(())
643 }
644}
645
646pub struct NodeRange<'a, S>
647where
648 S: SplaySpec<T: 'a>,
649{
650 front: Root<S>,
651 back: Root<S>,
652 root: &'a mut Root<S>,
653}
654
655impl<'a, S> Debug for NodeRange<'a, S>
656where
657 S: SplaySpec<T: 'a + Debug>,
658{
659 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
660 f.debug_struct("NodeRange")
661 .field("front", &self.front)
662 .field("back", &self.back)
663 .field("root", &self.root)
664 .finish()
665 }
666}
667impl<'a, S> NodeRange<'a, S>
668where
669 S: SplaySpec<T: 'a>,
670{
671 pub fn new(root: &'a mut Root<S>) -> Self {
672 Self {
673 front: Default::default(),
674 back: Default::default(),
675 root,
676 }
677 }
678 pub fn three_way(
679 front: Option<NodeRef<marker::Owned, S>>,
680 root: &'a mut Root<S>,
681 back: Option<NodeRef<marker::Owned, S>>,
682 ) -> Self {
683 Self {
684 front: Root::new(front),
685 back: Root::new(back),
686 root,
687 }
688 }
689 pub fn next_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
690 let first = self.root.take_first()?;
691 let noderef = unsafe { NodeRef::new_unchecked(first.node) };
692 self.front.insert_last(first);
693 Some(noderef)
694 }
695 pub fn next_back_checked(&mut self) -> Option<NodeRef<marker::DataMut<'a>, S>> {
696 let last = self.root.take_last()?;
697 let noderef = unsafe { NodeRef::new_unchecked(last.node) };
698 self.back.insert_first(last);
699 Some(noderef)
700 }Sourcefn reborrow(&self) -> NodeRef<Immut<'_>, S>
fn reborrow(&self) -> NodeRef<Immut<'_>, S>
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 313)
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }
480 pub fn is_empty(&self) -> bool {
481 self.root.is_none()
482 }
483 pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484 Some(self.root.as_ref()?.reborrow())
485 }
486 pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487 Some(self.root.as_mut()?.borrow_datamut())
488 }
489 pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490 where
491 Seeker: SplaySeeker<S = S>,
492 {
493 let (ord, root) = self.root.take()?.splay_by(seeker);
494 self.root = Some(root);
495 Some(ord)
496 }
497 pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498 self.root = Some(match self.root.take() {
499 Some(root) => root.insert_left(node),
500 None => {
501 S::bottom_up(node.borrow_datamut());
502 node
503 }
504 });
505 }
506 pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507 self.root = Some(match self.root.take() {
508 Some(root) => root.insert_right(node),
509 None => {
510 S::bottom_up(node.borrow_datamut());
511 node
512 }
513 });
514 }
515 pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516 self.root = Some(match self.root.take() {
517 Some(root) => root.insert_first(node),
518 None => {
519 S::bottom_up(node.borrow_datamut());
520 node
521 }
522 });
523 }
524 pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525 self.root = Some(match self.root.take() {
526 Some(root) => root.insert_last(node),
527 None => {
528 S::bottom_up(node.borrow_datamut());
529 node
530 }
531 });
532 }
533 pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534 let mut root = self.root.take()?;
535 let right = root.borrow_mut().take_right();
536 self.root = root.borrow_mut().take_left();
537 self.append(&mut Self::new(right));
538 Some(root)
539 }
540 pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541 let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542 let right = root.borrow_mut().take_right();
543 self.root = right;
544 Some(root)
545 }
546 pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547 let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548 let left = root.borrow_mut().take_left();
549 self.root = left;
550 Some(root)
551 }
552 pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553 let root = self.root.as_mut()?;
554 let left = root.borrow_mut().take_left();
555 S::bottom_up(root.borrow_datamut());
556 left
557 }
558 pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
559 let root = self.root.as_mut()?;
560 let right = root.borrow_mut().take_right();
561 S::bottom_up(root.borrow_datamut());
562 right
563 }
564 pub fn split_left_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
565 let right = self.split_right();
566 replace(&mut self.root, right)
567 }
568 pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
569 let left = self.split_left();
570 replace(&mut self.root, left)
571 }
572 pub fn append(&mut self, other: &mut Self) {
573 self.root = match (self.root.take(), other.root.take()) {
574 (Some(node), None) | (None, Some(node)) => Some(node),
575 (Some(left), Some(right)) => Some(left.merge(right)),
576 (None, None) => None,
577 }
578 }
579 pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580 where
581 Seeker: SplaySeeker<S = S>,
582 {
583 if self.is_empty() {
584 return NodeRange::new(self);
585 }
586 let right = match end {
587 Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588 Ordering::Greater | Ordering::Equal => self.split_right(),
589 Ordering::Less => self.split_right_eq(),
590 },
591 Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592 Ordering::Greater => self.split_right(),
593 Ordering::Less | Ordering::Equal => self.split_right_eq(),
594 },
595 Bound::Unbounded => None,
596 };
597 if self.is_empty() {
598 return NodeRange::three_way(None, self, right);
599 }
600 let left = match start {
601 Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602 Ordering::Less | Ordering::Equal => self.split_left(),
603 Ordering::Greater => self.split_left_eq(),
604 },
605 Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606 Ordering::Less => self.split_left(),
607 Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608 },
609 Bound::Unbounded => None,
610 };
611 NodeRange::three_way(left, self, right)
612 }
613}
614
615impl<S> Debug for Root<S>
616where
617 S: SplaySpec<T: Debug>,
618{
619 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
620 fn fmt_recurse<'a, S>(
621 node: NodeRef<marker::Immut<'a>, S>,
622 f: &mut fmt::Formatter<'_>,
623 ) -> fmt::Result
624 where
625 S: SplaySpec<T: 'a + Debug>,
626 {
627 write!(f, "[")?;
628 if let Some(left) = node.left() {
629 fmt_recurse(left, f)?;
630 }
631 node.data().fmt(f)?;
632 if let Some(right) = node.right() {
633 fmt_recurse(right, f)?;
634 }
635 write!(f, "]")?;
636 Ok(())
637 }
638 if let Some(root) = self.root.as_ref() {
639 let root = root.reborrow();
640 fmt_recurse(root, f)?;
641 }
642 Ok(())
643 }Sourcefn as_ptr(&self) -> *mut Node<S::T>
fn as_ptr(&self) -> *mut Node<S::T>
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 172)
171 pub fn data(&self) -> &'a S::T {
172 unsafe { &(*self.as_ptr()).data }
173 }
174 pub fn left(&self) -> Option<Self> {
175 unsafe {
176 (*self.as_ptr())
177 .left
178 .map(|node| NodeRef::new_unchecked(node))
179 }
180 }
181 pub fn right(&self) -> Option<Self> {
182 unsafe {
183 (*self.as_ptr())
184 .right
185 .map(|node| NodeRef::new_unchecked(node))
186 }
187 }
188 pub fn traverse<F>(self, f: &mut F)
189 where
190 S: SplaySpec<T: 'a>,
191 F: FnMut(Self),
192 {
193 if let Some(left) = self.clone().left() {
194 left.traverse(f);
195 }
196 f(self);
197 if let Some(right) = self.clone().right() {
198 right.traverse(f);
199 }
200 }
201}
202
203impl<'a, S> NodeRef<marker::DataMut<'a>, S>
204where
205 S: SplaySpec<T: 'a>,
206{
207 pub fn data(&self) -> &'a S::T {
208 unsafe { &(*self.as_ptr()).data }
209 }
210 pub fn data_mut(&self) -> &'a mut S::T {
211 unsafe { &mut (*self.as_ptr()).data }
212 }
213 pub fn left(&self) -> Option<Self> {
214 unsafe {
215 (*self.as_ptr())
216 .left
217 .map(|node| NodeRef::new_unchecked(node))
218 }
219 }
220 pub fn right(&self) -> Option<Self> {
221 unsafe {
222 (*self.as_ptr())
223 .right
224 .map(|node| NodeRef::new_unchecked(node))
225 }
226 }
227 pub fn reverse(&self) {
228 unsafe {
229 let node = &mut (*self.as_ptr());
230 swap(&mut node.left, &mut node.right);
231 }
232 }
233}
234
235impl<'a, S> NodeRef<marker::Mut<'a>, S>
236where
237 S: SplaySpec<T: 'a>,
238{
239 pub fn data(self) -> &'a S::T {
240 unsafe { &(*self.as_ptr()).data }
241 }
242 pub fn data_mut(self) -> &'a mut S::T {
243 unsafe { &mut (*self.as_ptr()).data }
244 }
245 pub fn take_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
246 Some(NodeRef::new(unsafe { (*self.as_ptr()).left.take()? }))
247 }
248 pub fn take_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
249 Some(NodeRef::new(unsafe { (*self.as_ptr()).right.take()? }))
250 }
251 pub fn set_left(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
252 unsafe { (*self.as_ptr()).left = node.map(|node| node.node) }
253 }
254 pub fn set_right(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
255 unsafe { (*self.as_ptr()).right = node.map(|node| node.node) }
256 }Source§impl<S> NodeRef<Owned, S>where
S: SplaySpec,
impl<S> NodeRef<Owned, S>where
S: SplaySpec,
Sourcepub fn new(node: NonNull<Node<S::T>>) -> Self
pub fn new(node: NonNull<Node<S::T>>) -> Self
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 154)
150 pub unsafe fn from_data<A>(data: S::T, allocator: &mut A) -> Self
151 where
152 A: Allocator<Node<S::T>>,
153 {
154 Self::new(allocator.allocate(Node::new(data)))
155 }
156 pub fn borrow_mut(&mut self) -> NodeRef<marker::Mut<'_>, S> {
157 unsafe { NodeRef::new_unchecked(self.node) }
158 }
159 pub fn borrow_datamut(&mut self) -> NodeRef<marker::DataMut<'_>, S> {
160 unsafe { NodeRef::new_unchecked(self.node) }
161 }
162 pub fn into_dying(self) -> NodeRef<marker::Dying, S> {
163 unsafe { NodeRef::new_unchecked(self.node) }
164 }
165}
166
167impl<'a, S> NodeRef<marker::Immut<'a>, S>
168where
169 S: SplaySpec<T: 'a>,
170{
171 pub fn data(&self) -> &'a S::T {
172 unsafe { &(*self.as_ptr()).data }
173 }
174 pub fn left(&self) -> Option<Self> {
175 unsafe {
176 (*self.as_ptr())
177 .left
178 .map(|node| NodeRef::new_unchecked(node))
179 }
180 }
181 pub fn right(&self) -> Option<Self> {
182 unsafe {
183 (*self.as_ptr())
184 .right
185 .map(|node| NodeRef::new_unchecked(node))
186 }
187 }
188 pub fn traverse<F>(self, f: &mut F)
189 where
190 S: SplaySpec<T: 'a>,
191 F: FnMut(Self),
192 {
193 if let Some(left) = self.clone().left() {
194 left.traverse(f);
195 }
196 f(self);
197 if let Some(right) = self.clone().right() {
198 right.traverse(f);
199 }
200 }
201}
202
203impl<'a, S> NodeRef<marker::DataMut<'a>, S>
204where
205 S: SplaySpec<T: 'a>,
206{
207 pub fn data(&self) -> &'a S::T {
208 unsafe { &(*self.as_ptr()).data }
209 }
210 pub fn data_mut(&self) -> &'a mut S::T {
211 unsafe { &mut (*self.as_ptr()).data }
212 }
213 pub fn left(&self) -> Option<Self> {
214 unsafe {
215 (*self.as_ptr())
216 .left
217 .map(|node| NodeRef::new_unchecked(node))
218 }
219 }
220 pub fn right(&self) -> Option<Self> {
221 unsafe {
222 (*self.as_ptr())
223 .right
224 .map(|node| NodeRef::new_unchecked(node))
225 }
226 }
227 pub fn reverse(&self) {
228 unsafe {
229 let node = &mut (*self.as_ptr());
230 swap(&mut node.left, &mut node.right);
231 }
232 }
233}
234
235impl<'a, S> NodeRef<marker::Mut<'a>, S>
236where
237 S: SplaySpec<T: 'a>,
238{
239 pub fn data(self) -> &'a S::T {
240 unsafe { &(*self.as_ptr()).data }
241 }
242 pub fn data_mut(self) -> &'a mut S::T {
243 unsafe { &mut (*self.as_ptr()).data }
244 }
245 pub fn take_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
246 Some(NodeRef::new(unsafe { (*self.as_ptr()).left.take()? }))
247 }
248 pub fn take_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
249 Some(NodeRef::new(unsafe { (*self.as_ptr()).right.take()? }))
250 }
251 pub fn set_left(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
252 unsafe { (*self.as_ptr()).left = node.map(|node| node.node) }
253 }
254 pub fn set_right(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
255 unsafe { (*self.as_ptr()).right = node.map(|node| node.node) }
256 }
257}
258
259impl<S> NodeRef<marker::Dying, S>
260where
261 S: SplaySpec,
262{
263 pub unsafe fn into_inner(self) -> NonNull<Node<S::T>> {
264 let node = self.node;
265 unsafe {
266 debug_assert!((*node.as_ptr()).left.is_none());
267 debug_assert!((*node.as_ptr()).right.is_none());
268 }
269 node
270 }
271 pub unsafe fn into_data<A>(self, allocator: &mut A) -> S::T
272 where
273 A: Allocator<Node<S::T>>,
274 {
275 let Node { data, left, right } = allocator.deallocate(self.node);
276 debug_assert!(left.is_none());
277 debug_assert!(right.is_none());
278 data
279 }
280}
281
282impl<S> NodeRef<marker::Owned, S>
283where
284 S: SplaySpec,
285{
286 /// `cmp(key)`: [`Ordering`] between splaying and `key`
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }Sourcepub unsafe fn from_data<A>(data: S::T, allocator: &mut A) -> Self
pub unsafe fn from_data<A>(data: S::T, allocator: &mut A) -> Self
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (lines 366-375)
361 pub fn insert(&mut self, index: usize, x: T::Key) {
362 assert!(index <= self.length);
363 self.root.splay_by(SeekBySize::new(index));
364 let agg = T::single_agg(&x);
365 unsafe {
366 let node = NodeRef::from_data(
367 LazyAggElement {
368 key: x,
369 agg,
370 lazy: T::act_unit(),
371 size: 1,
372 rev: false,
373 },
374 self.alloc.deref_mut(),
375 );
376 if index == self.length {
377 self.root.insert_right(node);
378 } else {
379 self.root.insert_left(node);
380 }
381 }
382 self.length += 1;
383 }
384 pub fn remove(&mut self, index: usize) -> Option<T::Key> {
385 if index >= self.length {
386 return None;
387 }
388 self.root.splay_by(SeekBySize::new(index));
389 self.length -= 1;
390 let node = self.root.take_root().unwrap().into_dying();
391 unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
392 }
393 pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
394 where
395 R: RangeBounds<usize>,
396 F: FnMut(&T::Agg) -> bool,
397 {
398 let mut range = self.range(range);
399 let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
400 if !matches!(ord, Some(Ordering::Equal)) {
401 return None;
402 }
403 let front_size = range.front().size();
404 let left_size = range.root().left_size();
405 Some(front_size + left_size)
406 }
407 pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
408 where
409 R: RangeBounds<usize>,
410 F: FnMut(&T::Agg) -> bool,
411 {
412 let mut range = self.range(range);
413 let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
414 if !matches!(ord, Some(Ordering::Equal)) {
415 return None;
416 }
417 let front_size = range.front().size();
418 let left_size = range.root().left_size();
419 Some(front_size + left_size)
420 }
421 pub fn rotate_left(&mut self, mid: usize) {
422 assert!(mid <= self.length);
423 if mid != 0 || mid != self.length {
424 self.range(mid..).drop_rotate_left()
425 }
426 }
427 pub fn rotate_right(&mut self, k: usize) {
428 assert!(k <= self.length);
429 self.rotate_left(self.length - k);
430 }
431}
432
433impl<T, A> Extend<T::Key> for SplaySequence<T, A>
434where
435 T: LazyMapMonoid,
436 A: Allocator<Node<LazyAggElement<T>>>,
437{
438 fn extend<I>(&mut self, iter: I)
439 where
440 I: IntoIterator<Item = T::Key>,
441 {
442 let nodes: Vec<_> = unsafe {
443 iter.into_iter()
444 .map(|key| {
445 let agg = T::single_agg(&key);
446 NodeRef::from_data(
447 LazyAggElement {
448 key,
449 agg,
450 lazy: T::act_unit(),
451 size: 1,
452 rev: false,
453 },
454 self.alloc.deref_mut(),
455 )
456 })
457 .collect()
458 };
459 self.length += nodes.len();
460 let mut root = unsafe { Root::from_single_nodes(nodes) };
461 self.root.append(&mut root);
462 }More examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (lines 203-206)
189 pub fn insert(&mut self, key: K, value: V) -> Option<V>
190 where
191 K: Ord,
192 {
193 let ord = self.splay_by_key(&key);
194 self.length += (ord != Some(Ordering::Equal)) as usize;
195 match ord {
196 Some(Ordering::Equal) => {
197 return Some(replace(
198 &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
199 value,
200 ));
201 }
202 Some(Ordering::Less) => unsafe {
203 self.root.insert_left(NodeRef::from_data(
204 ((key, value), 1),
205 self.alloc.deref_mut(),
206 ));
207 },
208 _ => unsafe {
209 self.root.insert_right(NodeRef::from_data(
210 ((key, value), 1),
211 self.alloc.deref_mut(),
212 ));
213 },
214 }
215 None
216 }Sourcepub fn borrow_mut(&mut self) -> NodeRef<Mut<'_>, S>
pub fn borrow_mut(&mut self) -> NodeRef<Mut<'_>, S>
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 315)
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }
480 pub fn is_empty(&self) -> bool {
481 self.root.is_none()
482 }
483 pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484 Some(self.root.as_ref()?.reborrow())
485 }
486 pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487 Some(self.root.as_mut()?.borrow_datamut())
488 }
489 pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490 where
491 Seeker: SplaySeeker<S = S>,
492 {
493 let (ord, root) = self.root.take()?.splay_by(seeker);
494 self.root = Some(root);
495 Some(ord)
496 }
497 pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498 self.root = Some(match self.root.take() {
499 Some(root) => root.insert_left(node),
500 None => {
501 S::bottom_up(node.borrow_datamut());
502 node
503 }
504 });
505 }
506 pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507 self.root = Some(match self.root.take() {
508 Some(root) => root.insert_right(node),
509 None => {
510 S::bottom_up(node.borrow_datamut());
511 node
512 }
513 });
514 }
515 pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516 self.root = Some(match self.root.take() {
517 Some(root) => root.insert_first(node),
518 None => {
519 S::bottom_up(node.borrow_datamut());
520 node
521 }
522 });
523 }
524 pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525 self.root = Some(match self.root.take() {
526 Some(root) => root.insert_last(node),
527 None => {
528 S::bottom_up(node.borrow_datamut());
529 node
530 }
531 });
532 }
533 pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534 let mut root = self.root.take()?;
535 let right = root.borrow_mut().take_right();
536 self.root = root.borrow_mut().take_left();
537 self.append(&mut Self::new(right));
538 Some(root)
539 }
540 pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541 let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542 let right = root.borrow_mut().take_right();
543 self.root = right;
544 Some(root)
545 }
546 pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547 let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548 let left = root.borrow_mut().take_left();
549 self.root = left;
550 Some(root)
551 }
552 pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553 let root = self.root.as_mut()?;
554 let left = root.borrow_mut().take_left();
555 S::bottom_up(root.borrow_datamut());
556 left
557 }
558 pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
559 let root = self.root.as_mut()?;
560 let right = root.borrow_mut().take_right();
561 S::bottom_up(root.borrow_datamut());
562 right
563 }Sourcepub fn borrow_datamut(&mut self) -> NodeRef<DataMut<'_>, S>
pub fn borrow_datamut(&mut self) -> NodeRef<DataMut<'_>, S>
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 312)
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }
480 pub fn is_empty(&self) -> bool {
481 self.root.is_none()
482 }
483 pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484 Some(self.root.as_ref()?.reborrow())
485 }
486 pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487 Some(self.root.as_mut()?.borrow_datamut())
488 }
489 pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490 where
491 Seeker: SplaySeeker<S = S>,
492 {
493 let (ord, root) = self.root.take()?.splay_by(seeker);
494 self.root = Some(root);
495 Some(ord)
496 }
497 pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498 self.root = Some(match self.root.take() {
499 Some(root) => root.insert_left(node),
500 None => {
501 S::bottom_up(node.borrow_datamut());
502 node
503 }
504 });
505 }
506 pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507 self.root = Some(match self.root.take() {
508 Some(root) => root.insert_right(node),
509 None => {
510 S::bottom_up(node.borrow_datamut());
511 node
512 }
513 });
514 }
515 pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516 self.root = Some(match self.root.take() {
517 Some(root) => root.insert_first(node),
518 None => {
519 S::bottom_up(node.borrow_datamut());
520 node
521 }
522 });
523 }
524 pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525 self.root = Some(match self.root.take() {
526 Some(root) => root.insert_last(node),
527 None => {
528 S::bottom_up(node.borrow_datamut());
529 node
530 }
531 });
532 }
533 pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534 let mut root = self.root.take()?;
535 let right = root.borrow_mut().take_right();
536 self.root = root.borrow_mut().take_left();
537 self.append(&mut Self::new(right));
538 Some(root)
539 }
540 pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541 let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542 let right = root.borrow_mut().take_right();
543 self.root = right;
544 Some(root)
545 }
546 pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547 let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548 let left = root.borrow_mut().take_left();
549 self.root = left;
550 Some(root)
551 }
552 pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553 let root = self.root.as_mut()?;
554 let left = root.borrow_mut().take_left();
555 S::bottom_up(root.borrow_datamut());
556 left
557 }
558 pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
559 let root = self.root.as_mut()?;
560 let right = root.borrow_mut().take_right();
561 S::bottom_up(root.borrow_datamut());
562 right
563 }Sourcepub fn into_dying(self) -> NodeRef<Dying, S>
pub fn into_dying(self) -> NodeRef<Dying, S>
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 259)
256 fn drop(&mut self) {
257 unsafe {
258 while let Some(node) = self.root.take_first() {
259 self.alloc.deallocate(node.into_dying().into_inner());
260 }
261 ManuallyDrop::drop(&mut self.alloc);
262 }
263 }
264}
265
266impl<T, A> Default for SplaySequence<T, A>
267where
268 T: LazyMapMonoid,
269 A: Allocator<Node<LazyAggElement<T>>> + Default,
270{
271 fn default() -> Self {
272 Self {
273 root: Root::default(),
274 length: 0,
275 alloc: Default::default(),
276 }
277 }
278}
279
280impl<T> SplaySequence<T>
281where
282 T: LazyMapMonoid,
283{
284 pub fn new() -> Self {
285 Default::default()
286 }
287 pub fn with_capacity(capacity: usize) -> Self {
288 Self {
289 root: Root::default(),
290 length: 0,
291 alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
292 }
293 }
294 pub fn len(&self) -> usize {
295 self.length
296 }
297 pub fn is_empty(&self) -> bool {
298 self.length == 0
299 }
300}
301impl<T, A> SplaySequence<T, A>
302where
303 T: LazyMapMonoid,
304 A: Allocator<Node<LazyAggElement<T>>>,
305{
306 fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
307 where
308 R: RangeBounds<usize>,
309 {
310 let start = match range.start_bound() {
311 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
312 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
313 Bound::Unbounded => Bound::Unbounded,
314 };
315 let end = match range.end_bound() {
316 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
317 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
318 Bound::Unbounded => Bound::Unbounded,
319 };
320 self.root.range(start, end)
321 }
322 pub fn update<R>(&mut self, range: R, x: T::Act)
323 where
324 R: RangeBounds<usize>,
325 {
326 if let Some(root) = self.range(range).root_mut().root_data_mut() {
327 LazyAggSplay::<T>::update_lazy(root, &x);
328 }
329 }
330 pub fn fold<R>(&mut self, range: R) -> T::Agg
331 where
332 R: RangeBounds<usize>,
333 {
334 if let Some(root) = self.range(range).root().root() {
335 root.data().agg.clone()
336 } else {
337 T::agg_unit()
338 }
339 }
340 pub fn reverse<R>(&mut self, range: R)
341 where
342 R: RangeBounds<usize>,
343 {
344 if let Some(root) = self.range(range).root_mut().root_data_mut() {
345 LazyAggSplay::<T>::reverse(root);
346 }
347 }
348 pub fn get(&mut self, index: usize) -> Option<&T::Key> {
349 self.root.splay_by(SeekBySize::new(index))?;
350 self.root.root().map(|root| &root.data().key)
351 }
352 pub fn modify<F>(&mut self, index: usize, f: F)
353 where
354 F: FnOnce(&T::Key) -> T::Key,
355 {
356 self.root.splay_by(SeekBySize::new(index)).unwrap();
357 let data = self.root.root_data_mut().unwrap().data_mut();
358 data.key = f(&data.key);
359 LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
360 }
361 pub fn insert(&mut self, index: usize, x: T::Key) {
362 assert!(index <= self.length);
363 self.root.splay_by(SeekBySize::new(index));
364 let agg = T::single_agg(&x);
365 unsafe {
366 let node = NodeRef::from_data(
367 LazyAggElement {
368 key: x,
369 agg,
370 lazy: T::act_unit(),
371 size: 1,
372 rev: false,
373 },
374 self.alloc.deref_mut(),
375 );
376 if index == self.length {
377 self.root.insert_right(node);
378 } else {
379 self.root.insert_left(node);
380 }
381 }
382 self.length += 1;
383 }
384 pub fn remove(&mut self, index: usize) -> Option<T::Key> {
385 if index >= self.length {
386 return None;
387 }
388 self.root.splay_by(SeekBySize::new(index));
389 self.length -= 1;
390 let node = self.root.take_root().unwrap().into_dying();
391 unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
392 }More examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 113)
110 fn drop(&mut self) {
111 unsafe {
112 while let Some(node) = self.root.take_first() {
113 self.alloc.deallocate(node.into_dying().into_inner());
114 }
115 ManuallyDrop::drop(&mut self.alloc);
116 }
117 }
118}
119
120impl<K, V, A> Default for SplayMap<K, V, A>
121where
122 A: Allocator<Node<((K, V), usize)>> + Default,
123{
124 fn default() -> Self {
125 Self {
126 root: Root::default(),
127 length: 0,
128 alloc: Default::default(),
129 }
130 }
131}
132
133impl<K, V> SplayMap<K, V> {
134 pub fn new() -> Self {
135 Default::default()
136 }
137 pub fn with_capacity(capacity: usize) -> Self {
138 Self {
139 root: Root::default(),
140 length: 0,
141 alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
142 }
143 }
144}
145impl<K, V, A> SplayMap<K, V, A>
146where
147 A: Allocator<Node<((K, V), usize)>>,
148{
149 pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
150 where
151 K: Borrow<Q>,
152 Q: Ord + ?Sized,
153 {
154 self.get_key_value(key).map(|(_, v)| v)
155 }
156 fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
157 where
158 K: Borrow<Q>,
159 Q: Ord + ?Sized,
160 {
161 self.root.splay_by(SeekByKey::new(key))
162 }
163 pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
164 where
165 K: Borrow<Q>,
166 Q: Ord + ?Sized,
167 {
168 if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
169 return None;
170 }
171 self.root.root().map(|node| {
172 let ((k, v), _) = node.data();
173 (k, v)
174 })
175 }
176 fn splay_at(&mut self, index: usize) -> Option<Ordering> {
177 self.root.splay_by(SeekBySize::new(index))
178 }
179 pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
180 if index >= self.length {
181 return None;
182 }
183 self.splay_at(index);
184 self.root.root().map(|node| {
185 let ((k, v), _) = node.data();
186 (k, v)
187 })
188 }
189 pub fn insert(&mut self, key: K, value: V) -> Option<V>
190 where
191 K: Ord,
192 {
193 let ord = self.splay_by_key(&key);
194 self.length += (ord != Some(Ordering::Equal)) as usize;
195 match ord {
196 Some(Ordering::Equal) => {
197 return Some(replace(
198 &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
199 value,
200 ));
201 }
202 Some(Ordering::Less) => unsafe {
203 self.root.insert_left(NodeRef::from_data(
204 ((key, value), 1),
205 self.alloc.deref_mut(),
206 ));
207 },
208 _ => unsafe {
209 self.root.insert_right(NodeRef::from_data(
210 ((key, value), 1),
211 self.alloc.deref_mut(),
212 ));
213 },
214 }
215 None
216 }
217 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
218 where
219 K: Borrow<Q>,
220 Q: Ord + ?Sized,
221 {
222 if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
223 return None;
224 }
225 self.length -= 1;
226 let node = self.root.take_root().unwrap().into_dying();
227 unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
228 }
229 pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
230 if index >= self.length {
231 return None;
232 }
233 self.splay_at(index);
234 self.length -= 1;
235 let node = self.root.take_root().unwrap().into_dying();
236 unsafe { Some(node.into_data(self.alloc.deref_mut()).0) }
237 }Source§impl<'a, S> NodeRef<Immut<'a>, S>where
S: SplaySpec<T: 'a>,
impl<'a, S> NodeRef<Immut<'a>, S>where
S: SplaySpec<T: 'a>,
Sourcepub fn data(&self) -> &'a S::T
pub fn data(&self) -> &'a S::T
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 55)
54 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
55 self.key.cmp((node.data().0).0.borrow())
56 }
57}
58
59struct SeekBySize<K, V> {
60 index: usize,
61 _marker: PhantomData<fn() -> (K, V)>,
62}
63impl<K, V> SeekBySize<K, V> {
64 fn new(index: usize) -> Self {
65 Self {
66 index,
67 _marker: PhantomData,
68 }
69 }
70}
71impl<K, V> SplaySeeker for SeekBySize<K, V> {
72 type S = SizedSplay<(K, V)>;
73 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
74 let lsize = node.left().map(|l| l.data().1).unwrap_or_default();
75 let ord = self.index.cmp(&lsize);
76 if matches!(ord, Ordering::Greater) {
77 self.index -= lsize + 1;
78 }
79 ord
80 }
81}
82
83pub struct SplayMap<K, V, A = MemoryPool<Node<((K, V), usize)>>>
84where
85 A: Allocator<Node<((K, V), usize)>>,
86{
87 root: Root<SizedSplay<(K, V)>>,
88 length: usize,
89 alloc: ManuallyDrop<A>,
90}
91
92impl<K, V, A> Debug for SplayMap<K, V, A>
93where
94 K: Debug,
95 V: Debug,
96 A: Allocator<Node<((K, V), usize)>>,
97{
98 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
99 f.debug_struct("SplayMap")
100 .field("root", &self.root)
101 .field("length", &self.length)
102 .finish()
103 }
104}
105
106impl<K, V, A> Drop for SplayMap<K, V, A>
107where
108 A: Allocator<Node<((K, V), usize)>>,
109{
110 fn drop(&mut self) {
111 unsafe {
112 while let Some(node) = self.root.take_first() {
113 self.alloc.deallocate(node.into_dying().into_inner());
114 }
115 ManuallyDrop::drop(&mut self.alloc);
116 }
117 }
118}
119
120impl<K, V, A> Default for SplayMap<K, V, A>
121where
122 A: Allocator<Node<((K, V), usize)>> + Default,
123{
124 fn default() -> Self {
125 Self {
126 root: Root::default(),
127 length: 0,
128 alloc: Default::default(),
129 }
130 }
131}
132
133impl<K, V> SplayMap<K, V> {
134 pub fn new() -> Self {
135 Default::default()
136 }
137 pub fn with_capacity(capacity: usize) -> Self {
138 Self {
139 root: Root::default(),
140 length: 0,
141 alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
142 }
143 }
144}
145impl<K, V, A> SplayMap<K, V, A>
146where
147 A: Allocator<Node<((K, V), usize)>>,
148{
149 pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
150 where
151 K: Borrow<Q>,
152 Q: Ord + ?Sized,
153 {
154 self.get_key_value(key).map(|(_, v)| v)
155 }
156 fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
157 where
158 K: Borrow<Q>,
159 Q: Ord + ?Sized,
160 {
161 self.root.splay_by(SeekByKey::new(key))
162 }
163 pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
164 where
165 K: Borrow<Q>,
166 Q: Ord + ?Sized,
167 {
168 if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
169 return None;
170 }
171 self.root.root().map(|node| {
172 let ((k, v), _) = node.data();
173 (k, v)
174 })
175 }
176 fn splay_at(&mut self, index: usize) -> Option<Ordering> {
177 self.root.splay_by(SeekBySize::new(index))
178 }
179 pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
180 if index >= self.length {
181 return None;
182 }
183 self.splay_at(index);
184 self.root.root().map(|node| {
185 let ((k, v), _) = node.data();
186 (k, v)
187 })
188 }More examples
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 133)
132 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
133 let lsize = node.left().map(|l| l.data().size).unwrap_or_default();
134 let ord = self.index.cmp(&lsize);
135 if matches!(ord, Ordering::Greater) {
136 self.index -= lsize + 1;
137 }
138 ord
139 }
140}
141
142struct SeekByAccCond<F, T>
143where
144 T: LazyMapMonoid,
145{
146 acc: T::Agg,
147 f: F,
148 _marker: PhantomData<fn() -> T>,
149}
150impl<F, T> SeekByAccCond<F, T>
151where
152 T: LazyMapMonoid,
153{
154 fn new(f: F) -> Self {
155 Self {
156 acc: T::agg_unit(),
157 f,
158 _marker: PhantomData,
159 }
160 }
161}
162impl<F, T> SplaySeeker for SeekByAccCond<F, T>
163where
164 F: FnMut(&T::Agg) -> bool,
165 T: LazyMapMonoid,
166{
167 type S = LazyAggSplay<T>;
168 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
169 if let Some(lagg) = node.left().map(|l| &l.data().agg) {
170 let nacc = T::agg_operate(&self.acc, lagg);
171 if (self.f)(&nacc) {
172 return Ordering::Less;
173 }
174 self.acc = nacc;
175 };
176 self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
177 if (self.f)(&self.acc) {
178 Ordering::Equal
179 } else {
180 Ordering::Greater
181 }
182 }
183}
184
185struct SeekByRaccCond<F, T>
186where
187 T: LazyMapMonoid,
188{
189 acc: T::Agg,
190 f: F,
191 _marker: PhantomData<fn() -> T>,
192}
193impl<F, T> SeekByRaccCond<F, T>
194where
195 T: LazyMapMonoid,
196{
197 fn new(f: F) -> Self {
198 Self {
199 acc: T::agg_unit(),
200 f,
201 _marker: PhantomData,
202 }
203 }
204}
205impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
206where
207 F: FnMut(&T::Agg) -> bool,
208 T: LazyMapMonoid,
209{
210 type S = LazyAggSplay<T>;
211 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
212 if let Some(lagg) = node.right().map(|r| &r.data().agg) {
213 let nacc = T::agg_operate(lagg, &self.acc);
214 if (self.f)(&nacc) {
215 return Ordering::Greater;
216 }
217 self.acc = nacc;
218 };
219 self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
220 if (self.f)(&self.acc) {
221 Ordering::Equal
222 } else {
223 Ordering::Less
224 }
225 }
226}
227
228pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
229where
230 T: LazyMapMonoid,
231 A: Allocator<Node<LazyAggElement<T>>>,
232{
233 root: Root<LazyAggSplay<T>>,
234 length: usize,
235 alloc: ManuallyDrop<A>,
236}
237
238impl<T, A> Debug for SplaySequence<T, A>
239where
240 T: LazyMapMonoid<Key: Debug, Agg: Debug, Act: Debug>,
241 A: Allocator<Node<LazyAggElement<T>>>,
242{
243 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
244 f.debug_struct("SplayMap")
245 .field("root", &self.root)
246 .field("length", &self.length)
247 .finish()
248 }
249}
250
251impl<T, A> Drop for SplaySequence<T, A>
252where
253 T: LazyMapMonoid,
254 A: Allocator<Node<LazyAggElement<T>>>,
255{
256 fn drop(&mut self) {
257 unsafe {
258 while let Some(node) = self.root.take_first() {
259 self.alloc.deallocate(node.into_dying().into_inner());
260 }
261 ManuallyDrop::drop(&mut self.alloc);
262 }
263 }
264}
265
266impl<T, A> Default for SplaySequence<T, A>
267where
268 T: LazyMapMonoid,
269 A: Allocator<Node<LazyAggElement<T>>> + Default,
270{
271 fn default() -> Self {
272 Self {
273 root: Root::default(),
274 length: 0,
275 alloc: Default::default(),
276 }
277 }
278}
279
280impl<T> SplaySequence<T>
281where
282 T: LazyMapMonoid,
283{
284 pub fn new() -> Self {
285 Default::default()
286 }
287 pub fn with_capacity(capacity: usize) -> Self {
288 Self {
289 root: Root::default(),
290 length: 0,
291 alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
292 }
293 }
294 pub fn len(&self) -> usize {
295 self.length
296 }
297 pub fn is_empty(&self) -> bool {
298 self.length == 0
299 }
300}
301impl<T, A> SplaySequence<T, A>
302where
303 T: LazyMapMonoid,
304 A: Allocator<Node<LazyAggElement<T>>>,
305{
306 fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
307 where
308 R: RangeBounds<usize>,
309 {
310 let start = match range.start_bound() {
311 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
312 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
313 Bound::Unbounded => Bound::Unbounded,
314 };
315 let end = match range.end_bound() {
316 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
317 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
318 Bound::Unbounded => Bound::Unbounded,
319 };
320 self.root.range(start, end)
321 }
322 pub fn update<R>(&mut self, range: R, x: T::Act)
323 where
324 R: RangeBounds<usize>,
325 {
326 if let Some(root) = self.range(range).root_mut().root_data_mut() {
327 LazyAggSplay::<T>::update_lazy(root, &x);
328 }
329 }
330 pub fn fold<R>(&mut self, range: R) -> T::Agg
331 where
332 R: RangeBounds<usize>,
333 {
334 if let Some(root) = self.range(range).root().root() {
335 root.data().agg.clone()
336 } else {
337 T::agg_unit()
338 }
339 }
340 pub fn reverse<R>(&mut self, range: R)
341 where
342 R: RangeBounds<usize>,
343 {
344 if let Some(root) = self.range(range).root_mut().root_data_mut() {
345 LazyAggSplay::<T>::reverse(root);
346 }
347 }
348 pub fn get(&mut self, index: usize) -> Option<&T::Key> {
349 self.root.splay_by(SeekBySize::new(index))?;
350 self.root.root().map(|root| &root.data().key)
351 }
352 pub fn modify<F>(&mut self, index: usize, f: F)
353 where
354 F: FnOnce(&T::Key) -> T::Key,
355 {
356 self.root.splay_by(SeekBySize::new(index)).unwrap();
357 let data = self.root.root_data_mut().unwrap().data_mut();
358 data.key = f(&data.key);
359 LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
360 }
361 pub fn insert(&mut self, index: usize, x: T::Key) {
362 assert!(index <= self.length);
363 self.root.splay_by(SeekBySize::new(index));
364 let agg = T::single_agg(&x);
365 unsafe {
366 let node = NodeRef::from_data(
367 LazyAggElement {
368 key: x,
369 agg,
370 lazy: T::act_unit(),
371 size: 1,
372 rev: false,
373 },
374 self.alloc.deref_mut(),
375 );
376 if index == self.length {
377 self.root.insert_right(node);
378 } else {
379 self.root.insert_left(node);
380 }
381 }
382 self.length += 1;
383 }
384 pub fn remove(&mut self, index: usize) -> Option<T::Key> {
385 if index >= self.length {
386 return None;
387 }
388 self.root.splay_by(SeekBySize::new(index));
389 self.length -= 1;
390 let node = self.root.take_root().unwrap().into_dying();
391 unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
392 }
393 pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
394 where
395 R: RangeBounds<usize>,
396 F: FnMut(&T::Agg) -> bool,
397 {
398 let mut range = self.range(range);
399 let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
400 if !matches!(ord, Some(Ordering::Equal)) {
401 return None;
402 }
403 let front_size = range.front().size();
404 let left_size = range.root().left_size();
405 Some(front_size + left_size)
406 }
407 pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
408 where
409 R: RangeBounds<usize>,
410 F: FnMut(&T::Agg) -> bool,
411 {
412 let mut range = self.range(range);
413 let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
414 if !matches!(ord, Some(Ordering::Equal)) {
415 return None;
416 }
417 let front_size = range.front().size();
418 let left_size = range.root().left_size();
419 Some(front_size + left_size)
420 }
421 pub fn rotate_left(&mut self, mid: usize) {
422 assert!(mid <= self.length);
423 if mid != 0 || mid != self.length {
424 self.range(mid..).drop_rotate_left()
425 }
426 }
427 pub fn rotate_right(&mut self, k: usize) {
428 assert!(k <= self.length);
429 self.rotate_left(self.length - k);
430 }
431}
432
433impl<T, A> Extend<T::Key> for SplaySequence<T, A>
434where
435 T: LazyMapMonoid,
436 A: Allocator<Node<LazyAggElement<T>>>,
437{
438 fn extend<I>(&mut self, iter: I)
439 where
440 I: IntoIterator<Item = T::Key>,
441 {
442 let nodes: Vec<_> = unsafe {
443 iter.into_iter()
444 .map(|key| {
445 let agg = T::single_agg(&key);
446 NodeRef::from_data(
447 LazyAggElement {
448 key,
449 agg,
450 lazy: T::act_unit(),
451 size: 1,
452 rev: false,
453 },
454 self.alloc.deref_mut(),
455 )
456 })
457 .collect()
458 };
459 self.length += nodes.len();
460 let mut root = unsafe { Root::from_single_nodes(nodes) };
461 self.root.append(&mut root);
462 }
463}
464
465impl<T> Root<LazyAggSplay<T>>
466where
467 T: LazyMapMonoid,
468{
469 fn size(&self) -> usize {
470 self.root().map(|root| root.data().size).unwrap_or_default()
471 }
472 fn left_size(&self) -> usize {
473 self.root()
474 .and_then(|root| root.left().map(|left| left.data().size))
475 .unwrap_or_default()
476 }crates/competitive/src/data_structure/splay_tree/node.rs (line 631)
620 fn fmt_recurse<'a, S>(
621 node: NodeRef<marker::Immut<'a>, S>,
622 f: &mut fmt::Formatter<'_>,
623 ) -> fmt::Result
624 where
625 S: SplaySpec<T: 'a + Debug>,
626 {
627 write!(f, "[")?;
628 if let Some(left) = node.left() {
629 fmt_recurse(left, f)?;
630 }
631 node.data().fmt(f)?;
632 if let Some(right) = node.right() {
633 fmt_recurse(right, f)?;
634 }
635 write!(f, "]")?;
636 Ok(())
637 }Sourcepub fn left(&self) -> Option<Self>
pub fn left(&self) -> Option<Self>
Examples found in repository?
More examples
crates/competitive/src/data_structure/splay_tree/node.rs (line 193)
188 pub fn traverse<F>(self, f: &mut F)
189 where
190 S: SplaySpec<T: 'a>,
191 F: FnMut(Self),
192 {
193 if let Some(left) = self.clone().left() {
194 left.traverse(f);
195 }
196 f(self);
197 if let Some(right) = self.clone().right() {
198 right.traverse(f);
199 }
200 }
201}
202
203impl<'a, S> NodeRef<marker::DataMut<'a>, S>
204where
205 S: SplaySpec<T: 'a>,
206{
207 pub fn data(&self) -> &'a S::T {
208 unsafe { &(*self.as_ptr()).data }
209 }
210 pub fn data_mut(&self) -> &'a mut S::T {
211 unsafe { &mut (*self.as_ptr()).data }
212 }
213 pub fn left(&self) -> Option<Self> {
214 unsafe {
215 (*self.as_ptr())
216 .left
217 .map(|node| NodeRef::new_unchecked(node))
218 }
219 }
220 pub fn right(&self) -> Option<Self> {
221 unsafe {
222 (*self.as_ptr())
223 .right
224 .map(|node| NodeRef::new_unchecked(node))
225 }
226 }
227 pub fn reverse(&self) {
228 unsafe {
229 let node = &mut (*self.as_ptr());
230 swap(&mut node.left, &mut node.right);
231 }
232 }
233}
234
235impl<'a, S> NodeRef<marker::Mut<'a>, S>
236where
237 S: SplaySpec<T: 'a>,
238{
239 pub fn data(self) -> &'a S::T {
240 unsafe { &(*self.as_ptr()).data }
241 }
242 pub fn data_mut(self) -> &'a mut S::T {
243 unsafe { &mut (*self.as_ptr()).data }
244 }
245 pub fn take_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
246 Some(NodeRef::new(unsafe { (*self.as_ptr()).left.take()? }))
247 }
248 pub fn take_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
249 Some(NodeRef::new(unsafe { (*self.as_ptr()).right.take()? }))
250 }
251 pub fn set_left(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
252 unsafe { (*self.as_ptr()).left = node.map(|node| node.node) }
253 }
254 pub fn set_right(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
255 unsafe { (*self.as_ptr()).right = node.map(|node| node.node) }
256 }
257}
258
259impl<S> NodeRef<marker::Dying, S>
260where
261 S: SplaySpec,
262{
263 pub unsafe fn into_inner(self) -> NonNull<Node<S::T>> {
264 let node = self.node;
265 unsafe {
266 debug_assert!((*node.as_ptr()).left.is_none());
267 debug_assert!((*node.as_ptr()).right.is_none());
268 }
269 node
270 }
271 pub unsafe fn into_data<A>(self, allocator: &mut A) -> S::T
272 where
273 A: Allocator<Node<S::T>>,
274 {
275 let Node { data, left, right } = allocator.deallocate(self.node);
276 debug_assert!(left.is_none());
277 debug_assert!(right.is_none());
278 data
279 }
280}
281
282impl<S> NodeRef<marker::Owned, S>
283where
284 S: SplaySpec,
285{
286 /// `cmp(key)`: [`Ordering`] between splaying and `key`
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }
480 pub fn is_empty(&self) -> bool {
481 self.root.is_none()
482 }
483 pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484 Some(self.root.as_ref()?.reborrow())
485 }
486 pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487 Some(self.root.as_mut()?.borrow_datamut())
488 }
489 pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490 where
491 Seeker: SplaySeeker<S = S>,
492 {
493 let (ord, root) = self.root.take()?.splay_by(seeker);
494 self.root = Some(root);
495 Some(ord)
496 }
497 pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498 self.root = Some(match self.root.take() {
499 Some(root) => root.insert_left(node),
500 None => {
501 S::bottom_up(node.borrow_datamut());
502 node
503 }
504 });
505 }
506 pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507 self.root = Some(match self.root.take() {
508 Some(root) => root.insert_right(node),
509 None => {
510 S::bottom_up(node.borrow_datamut());
511 node
512 }
513 });
514 }
515 pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516 self.root = Some(match self.root.take() {
517 Some(root) => root.insert_first(node),
518 None => {
519 S::bottom_up(node.borrow_datamut());
520 node
521 }
522 });
523 }
524 pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525 self.root = Some(match self.root.take() {
526 Some(root) => root.insert_last(node),
527 None => {
528 S::bottom_up(node.borrow_datamut());
529 node
530 }
531 });
532 }
533 pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534 let mut root = self.root.take()?;
535 let right = root.borrow_mut().take_right();
536 self.root = root.borrow_mut().take_left();
537 self.append(&mut Self::new(right));
538 Some(root)
539 }
540 pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541 let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542 let right = root.borrow_mut().take_right();
543 self.root = right;
544 Some(root)
545 }
546 pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547 let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548 let left = root.borrow_mut().take_left();
549 self.root = left;
550 Some(root)
551 }
552 pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553 let root = self.root.as_mut()?;
554 let left = root.borrow_mut().take_left();
555 S::bottom_up(root.borrow_datamut());
556 left
557 }
558 pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
559 let root = self.root.as_mut()?;
560 let right = root.borrow_mut().take_right();
561 S::bottom_up(root.borrow_datamut());
562 right
563 }
564 pub fn split_left_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
565 let right = self.split_right();
566 replace(&mut self.root, right)
567 }
568 pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
569 let left = self.split_left();
570 replace(&mut self.root, left)
571 }
572 pub fn append(&mut self, other: &mut Self) {
573 self.root = match (self.root.take(), other.root.take()) {
574 (Some(node), None) | (None, Some(node)) => Some(node),
575 (Some(left), Some(right)) => Some(left.merge(right)),
576 (None, None) => None,
577 }
578 }
579 pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580 where
581 Seeker: SplaySeeker<S = S>,
582 {
583 if self.is_empty() {
584 return NodeRange::new(self);
585 }
586 let right = match end {
587 Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588 Ordering::Greater | Ordering::Equal => self.split_right(),
589 Ordering::Less => self.split_right_eq(),
590 },
591 Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592 Ordering::Greater => self.split_right(),
593 Ordering::Less | Ordering::Equal => self.split_right_eq(),
594 },
595 Bound::Unbounded => None,
596 };
597 if self.is_empty() {
598 return NodeRange::three_way(None, self, right);
599 }
600 let left = match start {
601 Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602 Ordering::Less | Ordering::Equal => self.split_left(),
603 Ordering::Greater => self.split_left_eq(),
604 },
605 Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606 Ordering::Less => self.split_left(),
607 Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608 },
609 Bound::Unbounded => None,
610 };
611 NodeRange::three_way(left, self, right)
612 }
613}
614
615impl<S> Debug for Root<S>
616where
617 S: SplaySpec<T: Debug>,
618{
619 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
620 fn fmt_recurse<'a, S>(
621 node: NodeRef<marker::Immut<'a>, S>,
622 f: &mut fmt::Formatter<'_>,
623 ) -> fmt::Result
624 where
625 S: SplaySpec<T: 'a + Debug>,
626 {
627 write!(f, "[")?;
628 if let Some(left) = node.left() {
629 fmt_recurse(left, f)?;
630 }
631 node.data().fmt(f)?;
632 if let Some(right) = node.right() {
633 fmt_recurse(right, f)?;
634 }
635 write!(f, "]")?;
636 Ok(())
637 }crates/competitive/src/data_structure/splay_tree/sequence.rs (line 133)
132 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
133 let lsize = node.left().map(|l| l.data().size).unwrap_or_default();
134 let ord = self.index.cmp(&lsize);
135 if matches!(ord, Ordering::Greater) {
136 self.index -= lsize + 1;
137 }
138 ord
139 }
140}
141
142struct SeekByAccCond<F, T>
143where
144 T: LazyMapMonoid,
145{
146 acc: T::Agg,
147 f: F,
148 _marker: PhantomData<fn() -> T>,
149}
150impl<F, T> SeekByAccCond<F, T>
151where
152 T: LazyMapMonoid,
153{
154 fn new(f: F) -> Self {
155 Self {
156 acc: T::agg_unit(),
157 f,
158 _marker: PhantomData,
159 }
160 }
161}
162impl<F, T> SplaySeeker for SeekByAccCond<F, T>
163where
164 F: FnMut(&T::Agg) -> bool,
165 T: LazyMapMonoid,
166{
167 type S = LazyAggSplay<T>;
168 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
169 if let Some(lagg) = node.left().map(|l| &l.data().agg) {
170 let nacc = T::agg_operate(&self.acc, lagg);
171 if (self.f)(&nacc) {
172 return Ordering::Less;
173 }
174 self.acc = nacc;
175 };
176 self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
177 if (self.f)(&self.acc) {
178 Ordering::Equal
179 } else {
180 Ordering::Greater
181 }
182 }
183}
184
185struct SeekByRaccCond<F, T>
186where
187 T: LazyMapMonoid,
188{
189 acc: T::Agg,
190 f: F,
191 _marker: PhantomData<fn() -> T>,
192}
193impl<F, T> SeekByRaccCond<F, T>
194where
195 T: LazyMapMonoid,
196{
197 fn new(f: F) -> Self {
198 Self {
199 acc: T::agg_unit(),
200 f,
201 _marker: PhantomData,
202 }
203 }
204}
205impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
206where
207 F: FnMut(&T::Agg) -> bool,
208 T: LazyMapMonoid,
209{
210 type S = LazyAggSplay<T>;
211 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
212 if let Some(lagg) = node.right().map(|r| &r.data().agg) {
213 let nacc = T::agg_operate(lagg, &self.acc);
214 if (self.f)(&nacc) {
215 return Ordering::Greater;
216 }
217 self.acc = nacc;
218 };
219 self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
220 if (self.f)(&self.acc) {
221 Ordering::Equal
222 } else {
223 Ordering::Less
224 }
225 }
226}
227
228pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
229where
230 T: LazyMapMonoid,
231 A: Allocator<Node<LazyAggElement<T>>>,
232{
233 root: Root<LazyAggSplay<T>>,
234 length: usize,
235 alloc: ManuallyDrop<A>,
236}
237
238impl<T, A> Debug for SplaySequence<T, A>
239where
240 T: LazyMapMonoid<Key: Debug, Agg: Debug, Act: Debug>,
241 A: Allocator<Node<LazyAggElement<T>>>,
242{
243 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
244 f.debug_struct("SplayMap")
245 .field("root", &self.root)
246 .field("length", &self.length)
247 .finish()
248 }
249}
250
251impl<T, A> Drop for SplaySequence<T, A>
252where
253 T: LazyMapMonoid,
254 A: Allocator<Node<LazyAggElement<T>>>,
255{
256 fn drop(&mut self) {
257 unsafe {
258 while let Some(node) = self.root.take_first() {
259 self.alloc.deallocate(node.into_dying().into_inner());
260 }
261 ManuallyDrop::drop(&mut self.alloc);
262 }
263 }
264}
265
266impl<T, A> Default for SplaySequence<T, A>
267where
268 T: LazyMapMonoid,
269 A: Allocator<Node<LazyAggElement<T>>> + Default,
270{
271 fn default() -> Self {
272 Self {
273 root: Root::default(),
274 length: 0,
275 alloc: Default::default(),
276 }
277 }
278}
279
280impl<T> SplaySequence<T>
281where
282 T: LazyMapMonoid,
283{
284 pub fn new() -> Self {
285 Default::default()
286 }
287 pub fn with_capacity(capacity: usize) -> Self {
288 Self {
289 root: Root::default(),
290 length: 0,
291 alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
292 }
293 }
294 pub fn len(&self) -> usize {
295 self.length
296 }
297 pub fn is_empty(&self) -> bool {
298 self.length == 0
299 }
300}
301impl<T, A> SplaySequence<T, A>
302where
303 T: LazyMapMonoid,
304 A: Allocator<Node<LazyAggElement<T>>>,
305{
306 fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
307 where
308 R: RangeBounds<usize>,
309 {
310 let start = match range.start_bound() {
311 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
312 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
313 Bound::Unbounded => Bound::Unbounded,
314 };
315 let end = match range.end_bound() {
316 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
317 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
318 Bound::Unbounded => Bound::Unbounded,
319 };
320 self.root.range(start, end)
321 }
322 pub fn update<R>(&mut self, range: R, x: T::Act)
323 where
324 R: RangeBounds<usize>,
325 {
326 if let Some(root) = self.range(range).root_mut().root_data_mut() {
327 LazyAggSplay::<T>::update_lazy(root, &x);
328 }
329 }
330 pub fn fold<R>(&mut self, range: R) -> T::Agg
331 where
332 R: RangeBounds<usize>,
333 {
334 if let Some(root) = self.range(range).root().root() {
335 root.data().agg.clone()
336 } else {
337 T::agg_unit()
338 }
339 }
340 pub fn reverse<R>(&mut self, range: R)
341 where
342 R: RangeBounds<usize>,
343 {
344 if let Some(root) = self.range(range).root_mut().root_data_mut() {
345 LazyAggSplay::<T>::reverse(root);
346 }
347 }
348 pub fn get(&mut self, index: usize) -> Option<&T::Key> {
349 self.root.splay_by(SeekBySize::new(index))?;
350 self.root.root().map(|root| &root.data().key)
351 }
352 pub fn modify<F>(&mut self, index: usize, f: F)
353 where
354 F: FnOnce(&T::Key) -> T::Key,
355 {
356 self.root.splay_by(SeekBySize::new(index)).unwrap();
357 let data = self.root.root_data_mut().unwrap().data_mut();
358 data.key = f(&data.key);
359 LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
360 }
361 pub fn insert(&mut self, index: usize, x: T::Key) {
362 assert!(index <= self.length);
363 self.root.splay_by(SeekBySize::new(index));
364 let agg = T::single_agg(&x);
365 unsafe {
366 let node = NodeRef::from_data(
367 LazyAggElement {
368 key: x,
369 agg,
370 lazy: T::act_unit(),
371 size: 1,
372 rev: false,
373 },
374 self.alloc.deref_mut(),
375 );
376 if index == self.length {
377 self.root.insert_right(node);
378 } else {
379 self.root.insert_left(node);
380 }
381 }
382 self.length += 1;
383 }
384 pub fn remove(&mut self, index: usize) -> Option<T::Key> {
385 if index >= self.length {
386 return None;
387 }
388 self.root.splay_by(SeekBySize::new(index));
389 self.length -= 1;
390 let node = self.root.take_root().unwrap().into_dying();
391 unsafe { Some(node.into_data(self.alloc.deref_mut()).key) }
392 }
393 pub fn position_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
394 where
395 R: RangeBounds<usize>,
396 F: FnMut(&T::Agg) -> bool,
397 {
398 let mut range = self.range(range);
399 let ord = range.root_mut().splay_by(SeekByAccCond::new(f));
400 if !matches!(ord, Some(Ordering::Equal)) {
401 return None;
402 }
403 let front_size = range.front().size();
404 let left_size = range.root().left_size();
405 Some(front_size + left_size)
406 }
407 pub fn rposition_acc<R, F>(&mut self, range: R, f: F) -> Option<usize>
408 where
409 R: RangeBounds<usize>,
410 F: FnMut(&T::Agg) -> bool,
411 {
412 let mut range = self.range(range);
413 let ord = range.root_mut().splay_by(SeekByRaccCond::new(f));
414 if !matches!(ord, Some(Ordering::Equal)) {
415 return None;
416 }
417 let front_size = range.front().size();
418 let left_size = range.root().left_size();
419 Some(front_size + left_size)
420 }
421 pub fn rotate_left(&mut self, mid: usize) {
422 assert!(mid <= self.length);
423 if mid != 0 || mid != self.length {
424 self.range(mid..).drop_rotate_left()
425 }
426 }
427 pub fn rotate_right(&mut self, k: usize) {
428 assert!(k <= self.length);
429 self.rotate_left(self.length - k);
430 }
431}
432
433impl<T, A> Extend<T::Key> for SplaySequence<T, A>
434where
435 T: LazyMapMonoid,
436 A: Allocator<Node<LazyAggElement<T>>>,
437{
438 fn extend<I>(&mut self, iter: I)
439 where
440 I: IntoIterator<Item = T::Key>,
441 {
442 let nodes: Vec<_> = unsafe {
443 iter.into_iter()
444 .map(|key| {
445 let agg = T::single_agg(&key);
446 NodeRef::from_data(
447 LazyAggElement {
448 key,
449 agg,
450 lazy: T::act_unit(),
451 size: 1,
452 rev: false,
453 },
454 self.alloc.deref_mut(),
455 )
456 })
457 .collect()
458 };
459 self.length += nodes.len();
460 let mut root = unsafe { Root::from_single_nodes(nodes) };
461 self.root.append(&mut root);
462 }
463}
464
465impl<T> Root<LazyAggSplay<T>>
466where
467 T: LazyMapMonoid,
468{
469 fn size(&self) -> usize {
470 self.root().map(|root| root.data().size).unwrap_or_default()
471 }
472 fn left_size(&self) -> usize {
473 self.root()
474 .and_then(|root| root.left().map(|left| left.data().size))
475 .unwrap_or_default()
476 }Sourcepub fn right(&self) -> Option<Self>
pub fn right(&self) -> Option<Self>
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 197)
188 pub fn traverse<F>(self, f: &mut F)
189 where
190 S: SplaySpec<T: 'a>,
191 F: FnMut(Self),
192 {
193 if let Some(left) = self.clone().left() {
194 left.traverse(f);
195 }
196 f(self);
197 if let Some(right) = self.clone().right() {
198 right.traverse(f);
199 }
200 }
201}
202
203impl<'a, S> NodeRef<marker::DataMut<'a>, S>
204where
205 S: SplaySpec<T: 'a>,
206{
207 pub fn data(&self) -> &'a S::T {
208 unsafe { &(*self.as_ptr()).data }
209 }
210 pub fn data_mut(&self) -> &'a mut S::T {
211 unsafe { &mut (*self.as_ptr()).data }
212 }
213 pub fn left(&self) -> Option<Self> {
214 unsafe {
215 (*self.as_ptr())
216 .left
217 .map(|node| NodeRef::new_unchecked(node))
218 }
219 }
220 pub fn right(&self) -> Option<Self> {
221 unsafe {
222 (*self.as_ptr())
223 .right
224 .map(|node| NodeRef::new_unchecked(node))
225 }
226 }
227 pub fn reverse(&self) {
228 unsafe {
229 let node = &mut (*self.as_ptr());
230 swap(&mut node.left, &mut node.right);
231 }
232 }
233}
234
235impl<'a, S> NodeRef<marker::Mut<'a>, S>
236where
237 S: SplaySpec<T: 'a>,
238{
239 pub fn data(self) -> &'a S::T {
240 unsafe { &(*self.as_ptr()).data }
241 }
242 pub fn data_mut(self) -> &'a mut S::T {
243 unsafe { &mut (*self.as_ptr()).data }
244 }
245 pub fn take_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
246 Some(NodeRef::new(unsafe { (*self.as_ptr()).left.take()? }))
247 }
248 pub fn take_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
249 Some(NodeRef::new(unsafe { (*self.as_ptr()).right.take()? }))
250 }
251 pub fn set_left(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
252 unsafe { (*self.as_ptr()).left = node.map(|node| node.node) }
253 }
254 pub fn set_right(&mut self, node: Option<NodeRef<marker::Owned, S>>) {
255 unsafe { (*self.as_ptr()).right = node.map(|node| node.node) }
256 }
257}
258
259impl<S> NodeRef<marker::Dying, S>
260where
261 S: SplaySpec,
262{
263 pub unsafe fn into_inner(self) -> NonNull<Node<S::T>> {
264 let node = self.node;
265 unsafe {
266 debug_assert!((*node.as_ptr()).left.is_none());
267 debug_assert!((*node.as_ptr()).right.is_none());
268 }
269 node
270 }
271 pub unsafe fn into_data<A>(self, allocator: &mut A) -> S::T
272 where
273 A: Allocator<Node<S::T>>,
274 {
275 let Node { data, left, right } = allocator.deallocate(self.node);
276 debug_assert!(left.is_none());
277 debug_assert!(right.is_none());
278 data
279 }
280}
281
282impl<S> NodeRef<marker::Owned, S>
283where
284 S: SplaySpec,
285{
286 /// `cmp(key)`: [`Ordering`] between splaying and `key`
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }
480 pub fn is_empty(&self) -> bool {
481 self.root.is_none()
482 }
483 pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484 Some(self.root.as_ref()?.reborrow())
485 }
486 pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487 Some(self.root.as_mut()?.borrow_datamut())
488 }
489 pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490 where
491 Seeker: SplaySeeker<S = S>,
492 {
493 let (ord, root) = self.root.take()?.splay_by(seeker);
494 self.root = Some(root);
495 Some(ord)
496 }
497 pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498 self.root = Some(match self.root.take() {
499 Some(root) => root.insert_left(node),
500 None => {
501 S::bottom_up(node.borrow_datamut());
502 node
503 }
504 });
505 }
506 pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507 self.root = Some(match self.root.take() {
508 Some(root) => root.insert_right(node),
509 None => {
510 S::bottom_up(node.borrow_datamut());
511 node
512 }
513 });
514 }
515 pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516 self.root = Some(match self.root.take() {
517 Some(root) => root.insert_first(node),
518 None => {
519 S::bottom_up(node.borrow_datamut());
520 node
521 }
522 });
523 }
524 pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525 self.root = Some(match self.root.take() {
526 Some(root) => root.insert_last(node),
527 None => {
528 S::bottom_up(node.borrow_datamut());
529 node
530 }
531 });
532 }
533 pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534 let mut root = self.root.take()?;
535 let right = root.borrow_mut().take_right();
536 self.root = root.borrow_mut().take_left();
537 self.append(&mut Self::new(right));
538 Some(root)
539 }
540 pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541 let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542 let right = root.borrow_mut().take_right();
543 self.root = right;
544 Some(root)
545 }
546 pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547 let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548 let left = root.borrow_mut().take_left();
549 self.root = left;
550 Some(root)
551 }
552 pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553 let root = self.root.as_mut()?;
554 let left = root.borrow_mut().take_left();
555 S::bottom_up(root.borrow_datamut());
556 left
557 }
558 pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
559 let root = self.root.as_mut()?;
560 let right = root.borrow_mut().take_right();
561 S::bottom_up(root.borrow_datamut());
562 right
563 }
564 pub fn split_left_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
565 let right = self.split_right();
566 replace(&mut self.root, right)
567 }
568 pub fn split_right_eq(&mut self) -> Option<NodeRef<marker::Owned, S>> {
569 let left = self.split_left();
570 replace(&mut self.root, left)
571 }
572 pub fn append(&mut self, other: &mut Self) {
573 self.root = match (self.root.take(), other.root.take()) {
574 (Some(node), None) | (None, Some(node)) => Some(node),
575 (Some(left), Some(right)) => Some(left.merge(right)),
576 (None, None) => None,
577 }
578 }
579 pub fn range<Seeker>(&mut self, start: Bound<Seeker>, end: Bound<Seeker>) -> NodeRange<'_, S>
580 where
581 Seeker: SplaySeeker<S = S>,
582 {
583 if self.is_empty() {
584 return NodeRange::new(self);
585 }
586 let right = match end {
587 Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
588 Ordering::Greater | Ordering::Equal => self.split_right(),
589 Ordering::Less => self.split_right_eq(),
590 },
591 Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
592 Ordering::Greater => self.split_right(),
593 Ordering::Less | Ordering::Equal => self.split_right_eq(),
594 },
595 Bound::Unbounded => None,
596 };
597 if self.is_empty() {
598 return NodeRange::three_way(None, self, right);
599 }
600 let left = match start {
601 Bound::Included(seeker) => match self.splay_by(seeker).unwrap() {
602 Ordering::Less | Ordering::Equal => self.split_left(),
603 Ordering::Greater => self.split_left_eq(),
604 },
605 Bound::Excluded(seeker) => match self.splay_by(seeker).unwrap() {
606 Ordering::Less => self.split_left(),
607 Ordering::Greater | Ordering::Equal => self.split_left_eq(),
608 },
609 Bound::Unbounded => None,
610 };
611 NodeRange::three_way(left, self, right)
612 }
613}
614
615impl<S> Debug for Root<S>
616where
617 S: SplaySpec<T: Debug>,
618{
619 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
620 fn fmt_recurse<'a, S>(
621 node: NodeRef<marker::Immut<'a>, S>,
622 f: &mut fmt::Formatter<'_>,
623 ) -> fmt::Result
624 where
625 S: SplaySpec<T: 'a + Debug>,
626 {
627 write!(f, "[")?;
628 if let Some(left) = node.left() {
629 fmt_recurse(left, f)?;
630 }
631 node.data().fmt(f)?;
632 if let Some(right) = node.right() {
633 fmt_recurse(right, f)?;
634 }
635 write!(f, "]")?;
636 Ok(())
637 }More examples
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 212)
211 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
212 if let Some(lagg) = node.right().map(|r| &r.data().agg) {
213 let nacc = T::agg_operate(lagg, &self.acc);
214 if (self.f)(&nacc) {
215 return Ordering::Greater;
216 }
217 self.acc = nacc;
218 };
219 self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
220 if (self.f)(&self.acc) {
221 Ordering::Equal
222 } else {
223 Ordering::Less
224 }
225 }Sourcepub fn traverse<F>(self, f: &mut F)
pub fn traverse<F>(self, f: &mut F)
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 194)
188 pub fn traverse<F>(self, f: &mut F)
189 where
190 S: SplaySpec<T: 'a>,
191 F: FnMut(Self),
192 {
193 if let Some(left) = self.clone().left() {
194 left.traverse(f);
195 }
196 f(self);
197 if let Some(right) = self.clone().right() {
198 right.traverse(f);
199 }
200 }Source§impl<'a, S> NodeRef<DataMut<'a>, S>where
S: SplaySpec<T: 'a>,
impl<'a, S> NodeRef<DataMut<'a>, S>where
S: SplaySpec<T: 'a>,
Sourcepub fn data(&self) -> &'a S::T
pub fn data(&self) -> &'a S::T
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 24)
23 fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
24 let l = node.left().map(|p| p.data().1).unwrap_or_default();
25 let r = node.right().map(|p| p.data().1).unwrap_or_default();
26 node.data_mut().1 = l + r + 1;
27 }
28}
29
30struct SeekByKey<'a, K, V, Q>
31where
32 Q: ?Sized,
33{
34 key: &'a Q,
35 _marker: PhantomData<fn() -> (K, V)>,
36}
37impl<'a, K, V, Q> SeekByKey<'a, K, V, Q>
38where
39 Q: ?Sized,
40{
41 fn new(key: &'a Q) -> Self {
42 Self {
43 key,
44 _marker: PhantomData,
45 }
46 }
47}
48impl<K, V, Q> SplaySeeker for SeekByKey<'_, K, V, Q>
49where
50 K: Borrow<Q>,
51 Q: Ord + ?Sized,
52{
53 type S = SizedSplay<(K, V)>;
54 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
55 self.key.cmp((node.data().0).0.borrow())
56 }
57}
58
59struct SeekBySize<K, V> {
60 index: usize,
61 _marker: PhantomData<fn() -> (K, V)>,
62}
63impl<K, V> SeekBySize<K, V> {
64 fn new(index: usize) -> Self {
65 Self {
66 index,
67 _marker: PhantomData,
68 }
69 }
70}
71impl<K, V> SplaySeeker for SeekBySize<K, V> {
72 type S = SizedSplay<(K, V)>;
73 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
74 let lsize = node.left().map(|l| l.data().1).unwrap_or_default();
75 let ord = self.index.cmp(&lsize);
76 if matches!(ord, Ordering::Greater) {
77 self.index -= lsize + 1;
78 }
79 ord
80 }
81}
82
83pub struct SplayMap<K, V, A = MemoryPool<Node<((K, V), usize)>>>
84where
85 A: Allocator<Node<((K, V), usize)>>,
86{
87 root: Root<SizedSplay<(K, V)>>,
88 length: usize,
89 alloc: ManuallyDrop<A>,
90}
91
92impl<K, V, A> Debug for SplayMap<K, V, A>
93where
94 K: Debug,
95 V: Debug,
96 A: Allocator<Node<((K, V), usize)>>,
97{
98 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
99 f.debug_struct("SplayMap")
100 .field("root", &self.root)
101 .field("length", &self.length)
102 .finish()
103 }
104}
105
106impl<K, V, A> Drop for SplayMap<K, V, A>
107where
108 A: Allocator<Node<((K, V), usize)>>,
109{
110 fn drop(&mut self) {
111 unsafe {
112 while let Some(node) = self.root.take_first() {
113 self.alloc.deallocate(node.into_dying().into_inner());
114 }
115 ManuallyDrop::drop(&mut self.alloc);
116 }
117 }
118}
119
120impl<K, V, A> Default for SplayMap<K, V, A>
121where
122 A: Allocator<Node<((K, V), usize)>> + Default,
123{
124 fn default() -> Self {
125 Self {
126 root: Root::default(),
127 length: 0,
128 alloc: Default::default(),
129 }
130 }
131}
132
133impl<K, V> SplayMap<K, V> {
134 pub fn new() -> Self {
135 Default::default()
136 }
137 pub fn with_capacity(capacity: usize) -> Self {
138 Self {
139 root: Root::default(),
140 length: 0,
141 alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
142 }
143 }
144}
145impl<K, V, A> SplayMap<K, V, A>
146where
147 A: Allocator<Node<((K, V), usize)>>,
148{
149 pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
150 where
151 K: Borrow<Q>,
152 Q: Ord + ?Sized,
153 {
154 self.get_key_value(key).map(|(_, v)| v)
155 }
156 fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
157 where
158 K: Borrow<Q>,
159 Q: Ord + ?Sized,
160 {
161 self.root.splay_by(SeekByKey::new(key))
162 }
163 pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
164 where
165 K: Borrow<Q>,
166 Q: Ord + ?Sized,
167 {
168 if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
169 return None;
170 }
171 self.root.root().map(|node| {
172 let ((k, v), _) = node.data();
173 (k, v)
174 })
175 }
176 fn splay_at(&mut self, index: usize) -> Option<Ordering> {
177 self.root.splay_by(SeekBySize::new(index))
178 }
179 pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
180 if index >= self.length {
181 return None;
182 }
183 self.splay_at(index);
184 self.root.root().map(|node| {
185 let ((k, v), _) = node.data();
186 (k, v)
187 })
188 }
189 pub fn insert(&mut self, key: K, value: V) -> Option<V>
190 where
191 K: Ord,
192 {
193 let ord = self.splay_by_key(&key);
194 self.length += (ord != Some(Ordering::Equal)) as usize;
195 match ord {
196 Some(Ordering::Equal) => {
197 return Some(replace(
198 &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
199 value,
200 ));
201 }
202 Some(Ordering::Less) => unsafe {
203 self.root.insert_left(NodeRef::from_data(
204 ((key, value), 1),
205 self.alloc.deref_mut(),
206 ));
207 },
208 _ => unsafe {
209 self.root.insert_right(NodeRef::from_data(
210 ((key, value), 1),
211 self.alloc.deref_mut(),
212 ));
213 },
214 }
215 None
216 }
217 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
218 where
219 K: Borrow<Q>,
220 Q: Ord + ?Sized,
221 {
222 if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
223 return None;
224 }
225 self.length -= 1;
226 let node = self.root.take_root().unwrap().into_dying();
227 unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
228 }
229 pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
230 if index >= self.length {
231 return None;
232 }
233 self.splay_at(index);
234 self.length -= 1;
235 let node = self.root.take_root().unwrap().into_dying();
236 unsafe { Some(node.into_data(self.alloc.deref_mut()).0) }
237 }
238 pub fn len(&self) -> usize {
239 self.length
240 }
241 pub fn is_empty(&self) -> bool {
242 self.len() == 0
243 }
244 pub fn iter(&mut self) -> Iter<'_, K, V> {
245 Iter {
246 iter: NodeRange::new(&mut self.root),
247 }
248 }
249 pub fn range<Q, R>(&mut self, range: R) -> Iter<'_, K, V>
250 where
251 K: Borrow<Q>,
252 Q: Ord + ?Sized,
253 R: RangeBounds<Q>,
254 {
255 let start = match range.start_bound() {
256 Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
257 Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
258 Bound::Unbounded => Bound::Unbounded,
259 };
260 let end = match range.end_bound() {
261 Bound::Included(key) => Bound::Included(SeekByKey::new(key)),
262 Bound::Excluded(key) => Bound::Excluded(SeekByKey::new(key)),
263 Bound::Unbounded => Bound::Unbounded,
264 };
265 Iter {
266 iter: self.root.range(start, end),
267 }
268 }
269 pub fn range_at<R>(&mut self, range: R) -> Iter<'_, K, V>
270 where
271 R: RangeBounds<usize>,
272 {
273 let start = match range.start_bound() {
274 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
275 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
276 Bound::Unbounded => Bound::Unbounded,
277 };
278 let end = match range.end_bound() {
279 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
280 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
281 Bound::Unbounded => Bound::Unbounded,
282 };
283 Iter {
284 iter: self.root.range(start, end),
285 }
286 }
287}
288
289#[derive(Debug)]
290pub struct Iter<'a, K, V> {
291 iter: NodeRange<'a, SizedSplay<(K, V)>>,
292}
293impl<K, V> Iterator for Iter<'_, K, V>
294where
295 K: Clone,
296 V: Clone,
297{
298 type Item = (K, V);
299 fn next(&mut self) -> Option<Self::Item> {
300 self.iter.next_checked().map(|node| node.data().0.clone())
301 }
302 fn last(mut self) -> Option<Self::Item> {
303 self.next_back()
304 }
305 fn min(mut self) -> Option<Self::Item> {
306 self.next()
307 }
308 fn max(mut self) -> Option<Self::Item> {
309 self.next_back()
310 }
311}
312impl<K, V> FusedIterator for Iter<'_, K, V>
313where
314 K: Clone,
315 V: Clone,
316{
317}
318impl<K, V> DoubleEndedIterator for Iter<'_, K, V>
319where
320 K: Clone,
321 V: Clone,
322{
323 fn next_back(&mut self) -> Option<Self::Item> {
324 self.iter
325 .next_back_checked()
326 .map(|node| node.data().0.clone())
327 }More examples
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 48)
46 pub fn update_lazy(mut node: NodeRef<marker::DataMut<'_>, Self>, lazy: &T::Act) {
47 T::act_operate_assign(&mut node.data_mut().lazy, lazy);
48 node.data_mut().key = T::act_key(&node.data().key, lazy);
49 if let Some(nxlazy) = T::act_agg(&node.data().agg, lazy) {
50 node.data_mut().agg = nxlazy;
51 } else {
52 node = Self::propagate(node);
53 Self::recalc(node);
54 }
55 }
56 pub fn reverse(node: NodeRef<marker::DataMut<'_>, Self>) {
57 node.reverse();
58 T::toggle(&mut node.data_mut().agg);
59 node.data_mut().rev ^= true;
60 }
61 fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
62 let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
63 if let Some(left) = node.left() {
64 Self::update_lazy(left, &lazy);
65 }
66 if let Some(right) = node.right() {
67 Self::update_lazy(right, &lazy);
68 }
69 if replace(&mut node.data_mut().rev, false) {
70 if let Some(left) = node.left() {
71 Self::reverse(left);
72 }
73 if let Some(right) = node.right() {
74 Self::reverse(right);
75 }
76 }
77 node
78 }
79 fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
80 let mut agg = T::single_agg(&node.data().key);
81 let mut size = 1;
82 if let Some(left) = node.left() {
83 let data = left.data();
84 agg = T::agg_operate(&data.agg, &agg);
85 // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
86 size += data.size;
87 }
88 if let Some(right) = node.right() {
89 let data = right.data();
90 agg = T::agg_operate(&agg, &data.agg);
91 size += data.size;
92 }
93 let data = node.data_mut();
94 data.agg = agg;
95 data.size = size;
96 node
97 }Sourcepub fn data_mut(&self) -> &'a mut S::T
pub fn data_mut(&self) -> &'a mut S::T
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 26)
23 fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
24 let l = node.left().map(|p| p.data().1).unwrap_or_default();
25 let r = node.right().map(|p| p.data().1).unwrap_or_default();
26 node.data_mut().1 = l + r + 1;
27 }
28}
29
30struct SeekByKey<'a, K, V, Q>
31where
32 Q: ?Sized,
33{
34 key: &'a Q,
35 _marker: PhantomData<fn() -> (K, V)>,
36}
37impl<'a, K, V, Q> SeekByKey<'a, K, V, Q>
38where
39 Q: ?Sized,
40{
41 fn new(key: &'a Q) -> Self {
42 Self {
43 key,
44 _marker: PhantomData,
45 }
46 }
47}
48impl<K, V, Q> SplaySeeker for SeekByKey<'_, K, V, Q>
49where
50 K: Borrow<Q>,
51 Q: Ord + ?Sized,
52{
53 type S = SizedSplay<(K, V)>;
54 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
55 self.key.cmp((node.data().0).0.borrow())
56 }
57}
58
59struct SeekBySize<K, V> {
60 index: usize,
61 _marker: PhantomData<fn() -> (K, V)>,
62}
63impl<K, V> SeekBySize<K, V> {
64 fn new(index: usize) -> Self {
65 Self {
66 index,
67 _marker: PhantomData,
68 }
69 }
70}
71impl<K, V> SplaySeeker for SeekBySize<K, V> {
72 type S = SizedSplay<(K, V)>;
73 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
74 let lsize = node.left().map(|l| l.data().1).unwrap_or_default();
75 let ord = self.index.cmp(&lsize);
76 if matches!(ord, Ordering::Greater) {
77 self.index -= lsize + 1;
78 }
79 ord
80 }
81}
82
83pub struct SplayMap<K, V, A = MemoryPool<Node<((K, V), usize)>>>
84where
85 A: Allocator<Node<((K, V), usize)>>,
86{
87 root: Root<SizedSplay<(K, V)>>,
88 length: usize,
89 alloc: ManuallyDrop<A>,
90}
91
92impl<K, V, A> Debug for SplayMap<K, V, A>
93where
94 K: Debug,
95 V: Debug,
96 A: Allocator<Node<((K, V), usize)>>,
97{
98 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
99 f.debug_struct("SplayMap")
100 .field("root", &self.root)
101 .field("length", &self.length)
102 .finish()
103 }
104}
105
106impl<K, V, A> Drop for SplayMap<K, V, A>
107where
108 A: Allocator<Node<((K, V), usize)>>,
109{
110 fn drop(&mut self) {
111 unsafe {
112 while let Some(node) = self.root.take_first() {
113 self.alloc.deallocate(node.into_dying().into_inner());
114 }
115 ManuallyDrop::drop(&mut self.alloc);
116 }
117 }
118}
119
120impl<K, V, A> Default for SplayMap<K, V, A>
121where
122 A: Allocator<Node<((K, V), usize)>> + Default,
123{
124 fn default() -> Self {
125 Self {
126 root: Root::default(),
127 length: 0,
128 alloc: Default::default(),
129 }
130 }
131}
132
133impl<K, V> SplayMap<K, V> {
134 pub fn new() -> Self {
135 Default::default()
136 }
137 pub fn with_capacity(capacity: usize) -> Self {
138 Self {
139 root: Root::default(),
140 length: 0,
141 alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
142 }
143 }
144}
145impl<K, V, A> SplayMap<K, V, A>
146where
147 A: Allocator<Node<((K, V), usize)>>,
148{
149 pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
150 where
151 K: Borrow<Q>,
152 Q: Ord + ?Sized,
153 {
154 self.get_key_value(key).map(|(_, v)| v)
155 }
156 fn splay_by_key<Q>(&mut self, key: &Q) -> Option<Ordering>
157 where
158 K: Borrow<Q>,
159 Q: Ord + ?Sized,
160 {
161 self.root.splay_by(SeekByKey::new(key))
162 }
163 pub fn get_key_value<Q>(&mut self, key: &Q) -> Option<(&K, &V)>
164 where
165 K: Borrow<Q>,
166 Q: Ord + ?Sized,
167 {
168 if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
169 return None;
170 }
171 self.root.root().map(|node| {
172 let ((k, v), _) = node.data();
173 (k, v)
174 })
175 }
176 fn splay_at(&mut self, index: usize) -> Option<Ordering> {
177 self.root.splay_by(SeekBySize::new(index))
178 }
179 pub fn get_key_value_at(&mut self, index: usize) -> Option<(&K, &V)> {
180 if index >= self.length {
181 return None;
182 }
183 self.splay_at(index);
184 self.root.root().map(|node| {
185 let ((k, v), _) = node.data();
186 (k, v)
187 })
188 }
189 pub fn insert(&mut self, key: K, value: V) -> Option<V>
190 where
191 K: Ord,
192 {
193 let ord = self.splay_by_key(&key);
194 self.length += (ord != Some(Ordering::Equal)) as usize;
195 match ord {
196 Some(Ordering::Equal) => {
197 return Some(replace(
198 &mut (self.root.root_data_mut().unwrap().data_mut().0).1,
199 value,
200 ));
201 }
202 Some(Ordering::Less) => unsafe {
203 self.root.insert_left(NodeRef::from_data(
204 ((key, value), 1),
205 self.alloc.deref_mut(),
206 ));
207 },
208 _ => unsafe {
209 self.root.insert_right(NodeRef::from_data(
210 ((key, value), 1),
211 self.alloc.deref_mut(),
212 ));
213 },
214 }
215 None
216 }More examples
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 47)
46 pub fn update_lazy(mut node: NodeRef<marker::DataMut<'_>, Self>, lazy: &T::Act) {
47 T::act_operate_assign(&mut node.data_mut().lazy, lazy);
48 node.data_mut().key = T::act_key(&node.data().key, lazy);
49 if let Some(nxlazy) = T::act_agg(&node.data().agg, lazy) {
50 node.data_mut().agg = nxlazy;
51 } else {
52 node = Self::propagate(node);
53 Self::recalc(node);
54 }
55 }
56 pub fn reverse(node: NodeRef<marker::DataMut<'_>, Self>) {
57 node.reverse();
58 T::toggle(&mut node.data_mut().agg);
59 node.data_mut().rev ^= true;
60 }
61 fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
62 let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
63 if let Some(left) = node.left() {
64 Self::update_lazy(left, &lazy);
65 }
66 if let Some(right) = node.right() {
67 Self::update_lazy(right, &lazy);
68 }
69 if replace(&mut node.data_mut().rev, false) {
70 if let Some(left) = node.left() {
71 Self::reverse(left);
72 }
73 if let Some(right) = node.right() {
74 Self::reverse(right);
75 }
76 }
77 node
78 }
79 fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
80 let mut agg = T::single_agg(&node.data().key);
81 let mut size = 1;
82 if let Some(left) = node.left() {
83 let data = left.data();
84 agg = T::agg_operate(&data.agg, &agg);
85 // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
86 size += data.size;
87 }
88 if let Some(right) = node.right() {
89 let data = right.data();
90 agg = T::agg_operate(&agg, &data.agg);
91 size += data.size;
92 }
93 let data = node.data_mut();
94 data.agg = agg;
95 data.size = size;
96 node
97 }
98}
99impl<T> SplaySpec for LazyAggSplay<T>
100where
101 T: LazyMapMonoid,
102{
103 type T = LazyAggElement<T>;
104 fn has_bottom_up() -> bool {
105 true
106 }
107 fn top_down(node: NodeRef<marker::DataMut<'_>, Self>) {
108 Self::propagate(node);
109 }
110 fn bottom_up(node: NodeRef<marker::DataMut<'_>, Self>) {
111 Self::recalc(node);
112 }
113}
114
115struct SeekBySize<T> {
116 index: usize,
117 _marker: PhantomData<fn() -> T>,
118}
119impl<T> SeekBySize<T> {
120 fn new(index: usize) -> Self {
121 Self {
122 index,
123 _marker: PhantomData,
124 }
125 }
126}
127impl<T> SplaySeeker for SeekBySize<T>
128where
129 T: LazyMapMonoid,
130{
131 type S = LazyAggSplay<T>;
132 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
133 let lsize = node.left().map(|l| l.data().size).unwrap_or_default();
134 let ord = self.index.cmp(&lsize);
135 if matches!(ord, Ordering::Greater) {
136 self.index -= lsize + 1;
137 }
138 ord
139 }
140}
141
142struct SeekByAccCond<F, T>
143where
144 T: LazyMapMonoid,
145{
146 acc: T::Agg,
147 f: F,
148 _marker: PhantomData<fn() -> T>,
149}
150impl<F, T> SeekByAccCond<F, T>
151where
152 T: LazyMapMonoid,
153{
154 fn new(f: F) -> Self {
155 Self {
156 acc: T::agg_unit(),
157 f,
158 _marker: PhantomData,
159 }
160 }
161}
162impl<F, T> SplaySeeker for SeekByAccCond<F, T>
163where
164 F: FnMut(&T::Agg) -> bool,
165 T: LazyMapMonoid,
166{
167 type S = LazyAggSplay<T>;
168 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
169 if let Some(lagg) = node.left().map(|l| &l.data().agg) {
170 let nacc = T::agg_operate(&self.acc, lagg);
171 if (self.f)(&nacc) {
172 return Ordering::Less;
173 }
174 self.acc = nacc;
175 };
176 self.acc = T::agg_operate(&self.acc, &T::single_agg(&node.data().key));
177 if (self.f)(&self.acc) {
178 Ordering::Equal
179 } else {
180 Ordering::Greater
181 }
182 }
183}
184
185struct SeekByRaccCond<F, T>
186where
187 T: LazyMapMonoid,
188{
189 acc: T::Agg,
190 f: F,
191 _marker: PhantomData<fn() -> T>,
192}
193impl<F, T> SeekByRaccCond<F, T>
194where
195 T: LazyMapMonoid,
196{
197 fn new(f: F) -> Self {
198 Self {
199 acc: T::agg_unit(),
200 f,
201 _marker: PhantomData,
202 }
203 }
204}
205impl<F, T> SplaySeeker for SeekByRaccCond<F, T>
206where
207 F: FnMut(&T::Agg) -> bool,
208 T: LazyMapMonoid,
209{
210 type S = LazyAggSplay<T>;
211 fn splay_seek(&mut self, node: NodeRef<marker::Immut<'_>, Self::S>) -> Ordering {
212 if let Some(lagg) = node.right().map(|r| &r.data().agg) {
213 let nacc = T::agg_operate(lagg, &self.acc);
214 if (self.f)(&nacc) {
215 return Ordering::Greater;
216 }
217 self.acc = nacc;
218 };
219 self.acc = T::agg_operate(&T::single_agg(&node.data().key), &self.acc);
220 if (self.f)(&self.acc) {
221 Ordering::Equal
222 } else {
223 Ordering::Less
224 }
225 }
226}
227
228pub struct SplaySequence<T, A = MemoryPool<Node<LazyAggElement<T>>>>
229where
230 T: LazyMapMonoid,
231 A: Allocator<Node<LazyAggElement<T>>>,
232{
233 root: Root<LazyAggSplay<T>>,
234 length: usize,
235 alloc: ManuallyDrop<A>,
236}
237
238impl<T, A> Debug for SplaySequence<T, A>
239where
240 T: LazyMapMonoid<Key: Debug, Agg: Debug, Act: Debug>,
241 A: Allocator<Node<LazyAggElement<T>>>,
242{
243 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
244 f.debug_struct("SplayMap")
245 .field("root", &self.root)
246 .field("length", &self.length)
247 .finish()
248 }
249}
250
251impl<T, A> Drop for SplaySequence<T, A>
252where
253 T: LazyMapMonoid,
254 A: Allocator<Node<LazyAggElement<T>>>,
255{
256 fn drop(&mut self) {
257 unsafe {
258 while let Some(node) = self.root.take_first() {
259 self.alloc.deallocate(node.into_dying().into_inner());
260 }
261 ManuallyDrop::drop(&mut self.alloc);
262 }
263 }
264}
265
266impl<T, A> Default for SplaySequence<T, A>
267where
268 T: LazyMapMonoid,
269 A: Allocator<Node<LazyAggElement<T>>> + Default,
270{
271 fn default() -> Self {
272 Self {
273 root: Root::default(),
274 length: 0,
275 alloc: Default::default(),
276 }
277 }
278}
279
280impl<T> SplaySequence<T>
281where
282 T: LazyMapMonoid,
283{
284 pub fn new() -> Self {
285 Default::default()
286 }
287 pub fn with_capacity(capacity: usize) -> Self {
288 Self {
289 root: Root::default(),
290 length: 0,
291 alloc: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
292 }
293 }
294 pub fn len(&self) -> usize {
295 self.length
296 }
297 pub fn is_empty(&self) -> bool {
298 self.length == 0
299 }
300}
301impl<T, A> SplaySequence<T, A>
302where
303 T: LazyMapMonoid,
304 A: Allocator<Node<LazyAggElement<T>>>,
305{
306 fn range<R>(&mut self, range: R) -> NodeRange<'_, LazyAggSplay<T>>
307 where
308 R: RangeBounds<usize>,
309 {
310 let start = match range.start_bound() {
311 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
312 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
313 Bound::Unbounded => Bound::Unbounded,
314 };
315 let end = match range.end_bound() {
316 Bound::Included(&index) => Bound::Included(SeekBySize::new(index)),
317 Bound::Excluded(&index) => Bound::Excluded(SeekBySize::new(index)),
318 Bound::Unbounded => Bound::Unbounded,
319 };
320 self.root.range(start, end)
321 }
322 pub fn update<R>(&mut self, range: R, x: T::Act)
323 where
324 R: RangeBounds<usize>,
325 {
326 if let Some(root) = self.range(range).root_mut().root_data_mut() {
327 LazyAggSplay::<T>::update_lazy(root, &x);
328 }
329 }
330 pub fn fold<R>(&mut self, range: R) -> T::Agg
331 where
332 R: RangeBounds<usize>,
333 {
334 if let Some(root) = self.range(range).root().root() {
335 root.data().agg.clone()
336 } else {
337 T::agg_unit()
338 }
339 }
340 pub fn reverse<R>(&mut self, range: R)
341 where
342 R: RangeBounds<usize>,
343 {
344 if let Some(root) = self.range(range).root_mut().root_data_mut() {
345 LazyAggSplay::<T>::reverse(root);
346 }
347 }
348 pub fn get(&mut self, index: usize) -> Option<&T::Key> {
349 self.root.splay_by(SeekBySize::new(index))?;
350 self.root.root().map(|root| &root.data().key)
351 }
352 pub fn modify<F>(&mut self, index: usize, f: F)
353 where
354 F: FnOnce(&T::Key) -> T::Key,
355 {
356 self.root.splay_by(SeekBySize::new(index)).unwrap();
357 let data = self.root.root_data_mut().unwrap().data_mut();
358 data.key = f(&data.key);
359 LazyAggSplay::<T>::bottom_up(self.root.root_data_mut().unwrap());
360 }Sourcepub fn left(&self) -> Option<Self>
pub fn left(&self) -> Option<Self>
Examples found in repository?
More examples
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 63)
61 fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
62 let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
63 if let Some(left) = node.left() {
64 Self::update_lazy(left, &lazy);
65 }
66 if let Some(right) = node.right() {
67 Self::update_lazy(right, &lazy);
68 }
69 if replace(&mut node.data_mut().rev, false) {
70 if let Some(left) = node.left() {
71 Self::reverse(left);
72 }
73 if let Some(right) = node.right() {
74 Self::reverse(right);
75 }
76 }
77 node
78 }
79 fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
80 let mut agg = T::single_agg(&node.data().key);
81 let mut size = 1;
82 if let Some(left) = node.left() {
83 let data = left.data();
84 agg = T::agg_operate(&data.agg, &agg);
85 // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
86 size += data.size;
87 }
88 if let Some(right) = node.right() {
89 let data = right.data();
90 agg = T::agg_operate(&agg, &data.agg);
91 size += data.size;
92 }
93 let data = node.data_mut();
94 data.agg = agg;
95 data.size = size;
96 node
97 }Sourcepub fn right(&self) -> Option<Self>
pub fn right(&self) -> Option<Self>
Examples found in repository?
More examples
crates/competitive/src/data_structure/splay_tree/sequence.rs (line 66)
61 fn propagate(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
62 let lazy = replace(&mut node.data_mut().lazy, T::act_unit());
63 if let Some(left) = node.left() {
64 Self::update_lazy(left, &lazy);
65 }
66 if let Some(right) = node.right() {
67 Self::update_lazy(right, &lazy);
68 }
69 if replace(&mut node.data_mut().rev, false) {
70 if let Some(left) = node.left() {
71 Self::reverse(left);
72 }
73 if let Some(right) = node.right() {
74 Self::reverse(right);
75 }
76 }
77 node
78 }
79 fn recalc(node: NodeRef<marker::DataMut<'_>, Self>) -> NodeRef<marker::DataMut<'_>, Self> {
80 let mut agg = T::single_agg(&node.data().key);
81 let mut size = 1;
82 if let Some(left) = node.left() {
83 let data = left.data();
84 agg = T::agg_operate(&data.agg, &agg);
85 // agg = <T::AggMonoid as Magma>::operate(&data.agg, &agg);
86 size += data.size;
87 }
88 if let Some(right) = node.right() {
89 let data = right.data();
90 agg = T::agg_operate(&agg, &data.agg);
91 size += data.size;
92 }
93 let data = node.data_mut();
94 data.agg = agg;
95 data.size = size;
96 node
97 }Source§impl<'a, S> NodeRef<Mut<'a>, S>where
S: SplaySpec<T: 'a>,
impl<'a, S> NodeRef<Mut<'a>, S>where
S: SplaySpec<T: 'a>,
pub fn data(self) -> &'a S::T
pub fn data_mut(self) -> &'a mut S::T
Sourcepub fn take_left(&mut self) -> Option<NodeRef<Owned, S>>
pub fn take_left(&mut self) -> Option<NodeRef<Owned, S>>
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 315)
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }
480 pub fn is_empty(&self) -> bool {
481 self.root.is_none()
482 }
483 pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484 Some(self.root.as_ref()?.reborrow())
485 }
486 pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487 Some(self.root.as_mut()?.borrow_datamut())
488 }
489 pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490 where
491 Seeker: SplaySeeker<S = S>,
492 {
493 let (ord, root) = self.root.take()?.splay_by(seeker);
494 self.root = Some(root);
495 Some(ord)
496 }
497 pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498 self.root = Some(match self.root.take() {
499 Some(root) => root.insert_left(node),
500 None => {
501 S::bottom_up(node.borrow_datamut());
502 node
503 }
504 });
505 }
506 pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507 self.root = Some(match self.root.take() {
508 Some(root) => root.insert_right(node),
509 None => {
510 S::bottom_up(node.borrow_datamut());
511 node
512 }
513 });
514 }
515 pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516 self.root = Some(match self.root.take() {
517 Some(root) => root.insert_first(node),
518 None => {
519 S::bottom_up(node.borrow_datamut());
520 node
521 }
522 });
523 }
524 pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525 self.root = Some(match self.root.take() {
526 Some(root) => root.insert_last(node),
527 None => {
528 S::bottom_up(node.borrow_datamut());
529 node
530 }
531 });
532 }
533 pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534 let mut root = self.root.take()?;
535 let right = root.borrow_mut().take_right();
536 self.root = root.borrow_mut().take_left();
537 self.append(&mut Self::new(right));
538 Some(root)
539 }
540 pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541 let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542 let right = root.borrow_mut().take_right();
543 self.root = right;
544 Some(root)
545 }
546 pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547 let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548 let left = root.borrow_mut().take_left();
549 self.root = left;
550 Some(root)
551 }
552 pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553 let root = self.root.as_mut()?;
554 let left = root.borrow_mut().take_left();
555 S::bottom_up(root.borrow_datamut());
556 left
557 }Sourcepub fn take_right(&mut self) -> Option<NodeRef<Owned, S>>
pub fn take_right(&mut self) -> Option<NodeRef<Owned, S>>
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 321)
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }
480 pub fn is_empty(&self) -> bool {
481 self.root.is_none()
482 }
483 pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484 Some(self.root.as_ref()?.reborrow())
485 }
486 pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487 Some(self.root.as_mut()?.borrow_datamut())
488 }
489 pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490 where
491 Seeker: SplaySeeker<S = S>,
492 {
493 let (ord, root) = self.root.take()?.splay_by(seeker);
494 self.root = Some(root);
495 Some(ord)
496 }
497 pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498 self.root = Some(match self.root.take() {
499 Some(root) => root.insert_left(node),
500 None => {
501 S::bottom_up(node.borrow_datamut());
502 node
503 }
504 });
505 }
506 pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507 self.root = Some(match self.root.take() {
508 Some(root) => root.insert_right(node),
509 None => {
510 S::bottom_up(node.borrow_datamut());
511 node
512 }
513 });
514 }
515 pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516 self.root = Some(match self.root.take() {
517 Some(root) => root.insert_first(node),
518 None => {
519 S::bottom_up(node.borrow_datamut());
520 node
521 }
522 });
523 }
524 pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525 self.root = Some(match self.root.take() {
526 Some(root) => root.insert_last(node),
527 None => {
528 S::bottom_up(node.borrow_datamut());
529 node
530 }
531 });
532 }
533 pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534 let mut root = self.root.take()?;
535 let right = root.borrow_mut().take_right();
536 self.root = root.borrow_mut().take_left();
537 self.append(&mut Self::new(right));
538 Some(root)
539 }
540 pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541 let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542 let right = root.borrow_mut().take_right();
543 self.root = right;
544 Some(root)
545 }
546 pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547 let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548 let left = root.borrow_mut().take_left();
549 self.root = left;
550 Some(root)
551 }
552 pub fn split_left(&mut self) -> Option<NodeRef<marker::Owned, S>> {
553 let root = self.root.as_mut()?;
554 let left = root.borrow_mut().take_left();
555 S::bottom_up(root.borrow_datamut());
556 left
557 }
558 pub fn split_right(&mut self) -> Option<NodeRef<marker::Owned, S>> {
559 let root = self.root.as_mut()?;
560 let right = root.borrow_mut().take_right();
561 S::bottom_up(root.borrow_datamut());
562 right
563 }Sourcepub fn set_left(&mut self, node: Option<NodeRef<Owned, S>>)
pub fn set_left(&mut self, node: Option<NodeRef<Owned, S>>)
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 321)
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }Sourcepub fn set_right(&mut self, node: Option<NodeRef<Owned, S>>)
pub fn set_right(&mut self, node: Option<NodeRef<Owned, S>>)
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 323)
287 pub fn splay_by<Seeker>(self, mut seeker: Seeker) -> (Ordering, Self)
288 where
289 Seeker: SplaySeeker<S = S>,
290 {
291 let mut x = self;
292 // let dummy = Node { data: None, left: left_subtree, right: right_subtree };
293 let mut left_subtree: Option<NonNull<Node<S::T>>> = None;
294 let mut right_subtree: Option<NonNull<Node<S::T>>> = None;
295 let mut left_entry = &mut left_subtree;
296 let mut right_entry = &mut right_subtree;
297 let mut stack = vec![];
298
299 macro_rules! add {
300 (@left Some($ptr:ident)) => { add!(@inner Some($ptr.node), left_entry $ptr right); };
301 (@right Some($ptr:ident)) => { add!(@inner Some($ptr.node), right_entry $ptr left); };
302 (@inner $node:expr, $entry:ident $ptr:ident $dir:ident) => {
303 *$entry = $node;
304 if S::has_bottom_up() {
305 stack.push($ptr.node);
306 }
307 $entry = unsafe { &mut (*$entry.as_mut().unwrap().as_ptr()).$dir };
308 };
309 }
310
311 let root_ord = loop {
312 S::top_down(x.borrow_datamut());
313 match seeker.splay_seek(x.reborrow()) {
314 Ordering::Less => {
315 if let Some(mut y) = x.borrow_mut().take_left() {
316 S::top_down(y.borrow_datamut());
317 match seeker.splay_seek(y.reborrow()) {
318 Ordering::Less => {
319 if let Some(mut z) = y.borrow_mut().take_left() {
320 S::top_down(z.borrow_datamut());
321 x.borrow_mut().set_left(y.borrow_mut().take_right());
322 S::bottom_up(x.borrow_datamut());
323 y.borrow_mut().set_right(Some(x));
324 add!(@right Some(y));
325 x = z;
326 } else {
327 add!(@right Some(x));
328 x = y;
329 break Ordering::Less;
330 }
331 }
332 Ordering::Equal => {
333 add!(@right Some(x));
334 x = y;
335 break Ordering::Equal;
336 }
337 Ordering::Greater => {
338 if let Some(mut z) = y.borrow_mut().take_right() {
339 S::top_down(z.borrow_datamut());
340 add!(@right Some(x));
341 add!(@left Some(y));
342 x = z;
343 } else {
344 add!(@right Some(x));
345 x = y;
346 break Ordering::Greater;
347 }
348 }
349 }
350 } else {
351 break Ordering::Less;
352 }
353 }
354 Ordering::Equal => break Ordering::Equal,
355 Ordering::Greater => {
356 if let Some(mut y) = x.borrow_mut().take_right() {
357 S::top_down(y.borrow_datamut());
358 match seeker.splay_seek(y.reborrow()) {
359 Ordering::Less => {
360 if let Some(mut z) = y.borrow_mut().take_left() {
361 S::top_down(z.borrow_datamut());
362 add!(@left Some(x));
363 add!(@right Some(y));
364 x = z;
365 } else {
366 add!(@left Some(x));
367 x = y;
368 break Ordering::Less;
369 }
370 }
371 Ordering::Equal => {
372 add!(@left Some(x));
373 x = y;
374 break Ordering::Equal;
375 }
376 Ordering::Greater => {
377 if let Some(mut z) = y.borrow_mut().take_right() {
378 S::top_down(z.borrow_datamut());
379 x.borrow_mut().set_right(y.borrow_mut().take_left());
380 S::bottom_up(x.borrow_datamut());
381 y.borrow_mut().set_left(Some(x));
382 add!(@left Some(y));
383 x = z;
384 } else {
385 add!(@left Some(x));
386 x = y;
387 break Ordering::Greater;
388 }
389 }
390 }
391 } else {
392 break Ordering::Greater;
393 }
394 }
395 }
396 };
397 *left_entry = x.borrow_mut().take_left().map(|node| node.node);
398 *right_entry = x.borrow_mut().take_right().map(|node| node.node);
399 unsafe {
400 x.borrow_mut()
401 .set_left(left_subtree.map(|node| NodeRef::new_unchecked(node)));
402 x.borrow_mut()
403 .set_right(right_subtree.map(|node| NodeRef::new_unchecked(node)));
404 if S::has_bottom_up() {
405 while let Some(node) = stack.pop() {
406 S::bottom_up(NodeRef::new_unchecked(node));
407 }
408 }
409 }
410 S::bottom_up(x.borrow_datamut());
411 (root_ord, x)
412 }
413 pub fn insert_left(mut self, mut node: Self) -> Self {
414 if let Some(left) = self.borrow_mut().take_left() {
415 node.borrow_mut().set_left(Some(left));
416 S::bottom_up(self.borrow_datamut());
417 };
418 node.borrow_mut().set_right(Some(self));
419 S::bottom_up(node.borrow_datamut());
420 node
421 }
422 pub fn insert_right(mut self, mut node: Self) -> Self {
423 if let Some(right) = self.borrow_mut().take_right() {
424 node.borrow_mut().set_right(Some(right));
425 S::bottom_up(self.borrow_datamut());
426 }
427 node.borrow_mut().set_left(Some(self));
428 S::bottom_up(node.borrow_datamut());
429 node
430 }
431 pub fn insert_first(self, mut node: Self) -> Self {
432 node.borrow_mut().set_right(Some(self));
433 S::bottom_up(node.borrow_datamut());
434 node
435 }
436 pub fn insert_last(self, mut node: Self) -> Self {
437 node.borrow_mut().set_left(Some(self));
438 S::bottom_up(node.borrow_datamut());
439 node
440 }
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }Source§impl<S> NodeRef<Dying, S>where
S: SplaySpec,
impl<S> NodeRef<Dying, S>where
S: SplaySpec,
Sourcepub unsafe fn into_inner(self) -> NonNull<Node<S::T>>
pub unsafe fn into_inner(self) -> NonNull<Node<S::T>>
Examples found in repository?
More examples
Sourcepub unsafe fn into_data<A>(self, allocator: &mut A) -> S::T
pub unsafe fn into_data<A>(self, allocator: &mut A) -> S::T
Examples found in repository?
More examples
crates/competitive/src/data_structure/splay_tree/sized_map.rs (line 227)
217 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
218 where
219 K: Borrow<Q>,
220 Q: Ord + ?Sized,
221 {
222 if !matches!(self.splay_by_key(key)?, Ordering::Equal) {
223 return None;
224 }
225 self.length -= 1;
226 let node = self.root.take_root().unwrap().into_dying();
227 unsafe { Some((node.into_data(self.alloc.deref_mut()).0).1) }
228 }
229 pub fn remove_at(&mut self, index: usize) -> Option<(K, V)> {
230 if index >= self.length {
231 return None;
232 }
233 self.splay_at(index);
234 self.length -= 1;
235 let node = self.root.take_root().unwrap().into_dying();
236 unsafe { Some(node.into_data(self.alloc.deref_mut()).0) }
237 }Source§impl<S> NodeRef<Owned, S>where
S: SplaySpec,
impl<S> NodeRef<Owned, S>where
S: SplaySpec,
Sourcepub fn splay_by<Seeker>(self, seeker: Seeker) -> (Ordering, Self)where
Seeker: SplaySeeker<S = S>,
pub fn splay_by<Seeker>(self, seeker: Seeker) -> (Ordering, Self)where
Seeker: SplaySeeker<S = S>,
cmp(key): Ordering between splaying and key
Examples found in repository?
crates/competitive/src/data_structure/splay_tree/node.rs (line 448)
441 pub fn merge(mut self, mut other: Self) -> Self {
442 if other.reborrow().left().is_none() {
443 S::top_down(other.borrow_datamut());
444 other.borrow_mut().set_left(Some(self));
445 S::bottom_up(other.borrow_datamut());
446 other
447 } else {
448 self = self.splay_by(SeekRight::new()).1;
449 self.borrow_mut().set_right(Some(other));
450 S::bottom_up(self.borrow_datamut());
451 self
452 }
453 }
454}
455
456impl<S> Root<S>
457where
458 S: SplaySpec,
459{
460 pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
461 Self { root }
462 }
463 pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
464 unsafe { Self::from_single_nodes_inner(&nodes) }
465 }
466 unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
467 if nodes.is_empty() {
468 Self::new(None)
469 } else {
470 let m = nodes.len() / 2;
471 let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
472 let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
473 let mut node = NodeRef::new(nodes[m].node);
474 node.borrow_mut().set_left(left.root);
475 node.borrow_mut().set_right(right.root);
476 S::bottom_up(node.borrow_datamut());
477 Self::new(Some(node))
478 }
479 }
480 pub fn is_empty(&self) -> bool {
481 self.root.is_none()
482 }
483 pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
484 Some(self.root.as_ref()?.reborrow())
485 }
486 pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
487 Some(self.root.as_mut()?.borrow_datamut())
488 }
489 pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
490 where
491 Seeker: SplaySeeker<S = S>,
492 {
493 let (ord, root) = self.root.take()?.splay_by(seeker);
494 self.root = Some(root);
495 Some(ord)
496 }
497 pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
498 self.root = Some(match self.root.take() {
499 Some(root) => root.insert_left(node),
500 None => {
501 S::bottom_up(node.borrow_datamut());
502 node
503 }
504 });
505 }
506 pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
507 self.root = Some(match self.root.take() {
508 Some(root) => root.insert_right(node),
509 None => {
510 S::bottom_up(node.borrow_datamut());
511 node
512 }
513 });
514 }
515 pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
516 self.root = Some(match self.root.take() {
517 Some(root) => root.insert_first(node),
518 None => {
519 S::bottom_up(node.borrow_datamut());
520 node
521 }
522 });
523 }
524 pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
525 self.root = Some(match self.root.take() {
526 Some(root) => root.insert_last(node),
527 None => {
528 S::bottom_up(node.borrow_datamut());
529 node
530 }
531 });
532 }
533 pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
534 let mut root = self.root.take()?;
535 let right = root.borrow_mut().take_right();
536 self.root = root.borrow_mut().take_left();
537 self.append(&mut Self::new(right));
538 Some(root)
539 }
540 pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
541 let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
542 let right = root.borrow_mut().take_right();
543 self.root = right;
544 Some(root)
545 }
546 pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
547 let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
548 let left = root.borrow_mut().take_left();
549 self.root = left;
550 Some(root)
551 }Sourcepub fn insert_left(self, node: Self) -> Self
pub fn insert_left(self, node: Self) -> Self
Sourcepub fn insert_right(self, node: Self) -> Self
pub fn insert_right(self, node: Self) -> Self
Sourcepub fn insert_first(self, node: Self) -> Self
pub fn insert_first(self, node: Self) -> Self
Sourcepub fn insert_last(self, node: Self) -> Self
pub fn insert_last(self, node: Self) -> Self
Trait Implementations§
impl<'a, S> Copy for NodeRef<Immut<'a>, S>where
S: SplaySpec<T: 'a>,
Auto Trait Implementations§
impl<B, S> Freeze for NodeRef<B, S>
impl<B, S> RefUnwindSafe for NodeRef<B, S>
impl<B, S> !Send for NodeRef<B, S>
impl<B, S> !Sync for NodeRef<B, S>
impl<B, S> Unpin for NodeRef<B, S>where
B: Unpin,
impl<B, S> UnsafeUnpin for NodeRef<B, S>
impl<B, S> UnwindSafe for NodeRef<B, S>
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