competitive::data_structure::splay_tree::node

Struct SeekRight

pub struct SeekRight<S> {
    _marker: PhantomData<fn() -> S>,
}

Fields§

§_marker: PhantomData<fn() -> S>

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 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    }