competitive::data_structure::splay_tree::node

Struct SeekRight

pub struct SeekRight<S> { /* private fields */ }

Implementations§

Source §

impl<S> SeekRight<S>

Source

pub fn new() -> Self

Examples found in repository ?

crates/competitive/src/data_structure/splay_tree/node.rs (line 457)

450    pub fn merge(mut self, mut other: Self) -> Self {
451        if other.reborrow().left().is_none() {
452            S::top_down(other.borrow_datamut());
453            other.borrow_mut().set_left(Some(self));
454            S::bottom_up(other.borrow_datamut());
455            other
456        } else {
457            self = self.splay_by(SeekRight::new()).1;
458            self.borrow_mut().set_right(Some(other));
459            S::bottom_up(self.borrow_datamut());
460            self
461        }
462    }
463}
464
465impl<S> Root<S>
466where
467    S: SplaySpec,
468{
469    pub fn new(root: Option<NodeRef<marker::Owned, S>>) -> Self {
470        Self { root }
471    }
472    pub unsafe fn from_single_nodes(nodes: Vec<NodeRef<marker::Owned, S>>) -> Self {
473        unsafe { Self::from_single_nodes_inner(&nodes) }
474    }
475    unsafe fn from_single_nodes_inner(nodes: &[NodeRef<marker::Owned, S>]) -> Self {
476        if nodes.is_empty() {
477            Self::new(None)
478        } else {
479            let m = nodes.len() / 2;
480            let left = unsafe { Self::from_single_nodes_inner(&nodes[..m]) };
481            let right = unsafe { Self::from_single_nodes_inner(&nodes[m + 1..]) };
482            let mut node = NodeRef::new(nodes[m].node);
483            node.borrow_mut().set_left(left.root);
484            node.borrow_mut().set_right(right.root);
485            S::bottom_up(node.borrow_datamut());
486            Self::new(Some(node))
487        }
488    }
489    pub fn is_empty(&self) -> bool {
490        self.root.is_none()
491    }
492    pub fn root(&self) -> Option<NodeRef<marker::Immut<'_>, S>> {
493        Some(self.root.as_ref()?.reborrow())
494    }
495    pub fn root_data_mut(&mut self) -> Option<NodeRef<marker::DataMut<'_>, S>> {
496        Some(self.root.as_mut()?.borrow_datamut())
497    }
498    pub fn splay_by<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
499    where
500        Seeker: SplaySeeker<S = S>,
501    {
502        let (ord, root) = self.root.take()?.splay_by(seeker);
503        self.root = Some(root);
504        Some(ord)
505    }
506    pub fn insert_left(&mut self, mut node: NodeRef<marker::Owned, S>) {
507        self.root = Some(match self.root.take() {
508            Some(root) => root.insert_left(node),
509            None => {
510                S::bottom_up(node.borrow_datamut());
511                node
512            }
513        });
514    }
515    pub fn insert_right(&mut self, mut node: NodeRef<marker::Owned, S>) {
516        self.root = Some(match self.root.take() {
517            Some(root) => root.insert_right(node),
518            None => {
519                S::bottom_up(node.borrow_datamut());
520                node
521            }
522        });
523    }
524    pub fn insert_first(&mut self, mut node: NodeRef<marker::Owned, S>) {
525        self.root = Some(match self.root.take() {
526            Some(root) => root.insert_first(node),
527            None => {
528                S::bottom_up(node.borrow_datamut());
529                node
530            }
531        });
532    }
533    pub fn insert_last(&mut self, mut node: NodeRef<marker::Owned, S>) {
534        self.root = Some(match self.root.take() {
535            Some(root) => root.insert_last(node),
536            None => {
537                S::bottom_up(node.borrow_datamut());
538                node
539            }
540        });
541    }
542    pub fn take_root(&mut self) -> Option<NodeRef<marker::Owned, S>> {
543        let mut root = self.root.take()?;
544        let right = root.borrow_mut().take_right();
545        self.root = root.borrow_mut().take_left();
546        self.append(&mut Self::new(right));
547        Some(root)
548    }
549    pub fn take_first(&mut self) -> Option<NodeRef<marker::Owned, S>> {
550        let mut root = self.root.take()?.splay_by(SeekLeft::new()).1;
551        let right = root.borrow_mut().take_right();
552        self.root = right;
553        Some(root)
554    }
555    pub fn take_last(&mut self) -> Option<NodeRef<marker::Owned, S>> {
556        let mut root = self.root.take()?.splay_by(SeekRight::new()).1;
557        let left = root.borrow_mut().take_left();
558        self.root = left;
559        Some(root)
560    }