Skip to main content

splay

competitive::data_structure::splay_operations

Function splay 

Source 
pub fn splay<Spec, Data, Seeker>(
    root: BstRoot<Spec>,
    seeker: Seeker,
) -> (Ordering, BstRoot<Spec>)
where
    Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
    Seeker: BstSeeker<Spec = Spec>,
Examples found in repository?
crates/competitive/src/data_structure/splay_tree.rs (line 187)
183    fn splay<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
184    where
185        Seeker: BstSeeker<Spec = SplayTreeSpec<K, V>>,
186    {
187        let (ordering, root) = splay_operations::splay(self.root.take()?, seeker);
188        self.root = Some(root);
189        Some(ordering)
190    }
More examples
Hide additional examples
crates/competitive/src/data_structure/implicit_splay_tree.rs (line 253)
249    fn splay<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
250    where
251        Seeker: BstSeeker<Spec = ImplicitSplayTreeSpec<T>>,
252    {
253        let (ordering, root) = splay_operations::splay(self.root.take()?, seeker);
254        self.root = Some(root);
255        Some(ordering)
256    }
crates/competitive/src/data_structure/splay_operations.rs (line 406)
389pub fn merge<Spec, Data>(
390    left: Option<BstRoot<Spec>>,
391    right: Option<BstRoot<Spec>>,
392) -> Option<BstRoot<Spec>>
393where
394    Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
395{
396    match (left, right) {
397        (None, None) => None,
398        (None, Some(root)) | (Some(root), None) => Some(root),
399        (Some(left), Some(mut right)) if right.reborrow().left().descend().is_err() => {
400            Spec::top_down(right.borrow_datamut());
401            unsafe { right.borrow_mut().left_mut().set(left) };
402            Spec::bottom_up(right.borrow_datamut());
403            Some(right)
404        }
405        (Some(left), Some(right)) => {
406            let (_, mut root) = splay(left, SeekRight::default());
407            unsafe { root.borrow_mut().right_mut().set(right) };
408            Spec::bottom_up(root.borrow_datamut());
409            Some(root)
410        }
411    }
412}
413
414#[inline]
415pub fn split<Spec, Data, Seeker>(
416    root: Option<BstRoot<Spec>>,
417    seeker: Seeker,
418    equal_side: EqualSide,
419) -> (Option<BstRoot<Spec>>, Option<BstRoot<Spec>>)
420where
421    Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
422    Seeker: BstSeeker<Spec = Spec>,
423{
424    let Some(root) = root else {
425        return (None, None);
426    };
427    let (ordering, mut root) = splay(root, seeker);
428    if equal_side.goes_left(ordering) {
429        let right = unsafe { root.borrow_mut().right_mut().take() };
430        Spec::bottom_up(root.borrow_datamut());
431        (Some(root), right)
432    } else {
433        let left = unsafe { root.borrow_mut().left_mut().take() };
434        Spec::bottom_up(root.borrow_datamut());
435        (left, Some(root))
436    }
437}