Trait BstSpec 

pub trait BstSpec: Sized {
    type Parent: ParentStrategy<Data = Self::Data>;
    type Data;

    // Required methods
    fn merge(
        left: Option<BstRoot<Self>>,
        right: Option<BstRoot<Self>>,
    ) -> Option<BstRoot<Self>>;
    fn split<Seeker>(
        node: Option<BstRoot<Self>>,
        seeker: Seeker,
        equal_side: EqualSide,
    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
       where Seeker: BstSeeker<Spec = Self>;

    // Provided methods
    fn top_down(_node: BstDataMutRef<'_, Self>) { ... }
    fn bottom_up(_node: BstDataMutRef<'_, Self>) { ... }
}

Required Associated Types

type Parent: ParentStrategy<Data = Self::Data>

type Data

Required Methods

fn merge( left: Option<BstRoot<Self>>, right: Option<BstRoot<Self>>, ) -> Option<BstRoot<Self>>

fn split<Seeker>( node: Option<BstRoot<Self>>, seeker: Seeker, equal_side: EqualSide, ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)

where Seeker: BstSeeker<Spec = Self>,

Provided Methods

fn top_down(_node: BstDataMutRef<'_, Self>)

Examples found in repository

crates/competitive/src/tree/top_tree.rs (line 410)

    unsafe fn rake_rightmost(mut node: RakePtr<S, A>) -> RakePtr<S, A> {
        loop {
            unsafe { RakeBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node)) };
            match unsafe { node.as_ref().child[1] } {
                Some(right) => node = right,
                None => return node,
            }
        }
    }

    unsafe fn rake_insert(
        &mut self,
        root: Option<RakePtr<S, A>>,
        key: S::Point,
    ) -> (RakePtr<S, A>, RakePtr<S, A>) {
        let mut node = self.rake_allocator.allocate(BstNode::new(RakeData {
            sum: key.clone(),
            key,
            action: <A::ActionMonoid as Unital>::unit(),
            buffer: <A::ActionMonoid as Unital>::unit(),
        }));
        if let Some(mut root) = root {
            unsafe {
                node.as_mut().child[0] = Some(root);
                root.as_mut().parent.parent = Some(node);
                Self::pull_rake(node);
            }
        }
        (node, node)
    }

    unsafe fn rake_remove(
        &mut self,
        mut node: RakePtr<S, A>,
    ) -> (Option<RakePtr<S, A>>, A::Action) {
        unsafe {
            Self::splay_rake(node);
            RakeBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node));
        }
        let left = unsafe { node.as_mut().child[0].take() };
        let right = unsafe { node.as_mut().child[1].take() };
        for mut child in [left, right].into_iter().flatten() {
            unsafe { child.as_mut().parent.parent = None };
        }
        let root = match (left, right) {
            (None, right) => right,
            (left, None) => left,
            (Some(left), Some(right)) => {
                let mut root = unsafe { Self::rake_rightmost(left) };
                unsafe {
                    Self::splay_rake(root);
                    root.as_mut().child[1] = Some(right);
                    (*right.as_ptr()).parent.parent = Some(root);
                    Self::pull_rake(root);
                }
                Some(root)
            }
        };
        let node = self.rake_allocator.deallocate(node);
        (root, node.data.buffer)
    }

    fn access_node(&mut self, node: TopPtr<S, A>) {
        unsafe {
            let mut previous: Option<TopPtr<S, A>> = None;
            let mut current = Some(node);
            while let Some(mut cursor) = current {
                Self::splay_top(cursor);
                let next = cursor.as_ref().parent.parent;
                if let Some(right) = cursor.as_mut().child[1].take() {
                    let point = S::add_edge(&right.as_ref().data.sum);
                    let (light, entry) = self.rake_insert(cursor.as_ref().data.light, point);
                    cursor.as_mut().data.light = Some(light);
                    (*right.as_ptr()).data.belong = Some(entry);
                }
                if let Some(previous) = previous {
                    let entry = (*previous.as_ptr())
                        .data
                        .belong
                        .take()
                        .expect("a virtual path must have a rake-tree entry");
                    let (light, action) = self.rake_remove(entry);
                    cursor.as_mut().data.light = light;
                    TopBstSpec::<S, A>::apply_all(previous, &action);
                    cursor.as_mut().child[1] = Some(previous);
                    (*previous.as_ptr()).parent.parent = Some(cursor);
                }
                Self::pull_top(cursor);
                previous = Some(cursor);
                current = next;
            }
            Self::splay_top(node);
        }
    }

    pub fn get(&mut self, node: usize) -> &S::Info {
        let node = self.node(node);
        self.access_node(node);
        unsafe { &node.as_ref().data.info }
    }

    pub fn set(&mut self, node: usize, info: S::Info) {
        self.modify(node, |_| info);
    }

    pub fn modify<F>(&mut self, node: usize, f: F)
    where
        F: FnOnce(&S::Info) -> S::Info,
    {
        let mut node = self.node(node);
        self.access_node(node);
        unsafe {
            node.as_mut().data.info = f(&node.as_ref().data.info);
            Self::pull_top(node);
        }
    }

    pub fn reroot(&mut self, node: usize) {
        let node = self.node(node);
        self.access_node(node);
        unsafe { TopBstSpec::<S, A>::toggle(node) };
    }

    /// `child` and `parent` must belong to different trees.
    pub fn link(&mut self, child: usize, parent: usize) {
        assert_ne!(child, parent);
        self.reroot(child);
        let child = self.node(child);
        let mut parent = self.node(parent);
        self.access_node(parent);
        unsafe {
            (*child.as_ptr()).parent.parent = Some(parent);
            let point = S::add_edge(&child.as_ref().data.sum);
            let (light, entry) = self.rake_insert(parent.as_ref().data.light, point);
            parent.as_mut().data.light = Some(light);
            (*child.as_ptr()).data.belong = Some(entry);
            Self::pull_top(parent);
        }
    }

    /// `(u, v)` must be an edge.
    pub fn cut(&mut self, u: usize, v: usize) {
        assert_ne!(u, v);
        self.reroot(u);
        let mut v = self.node(v);
        self.access_node(v);
        unsafe {
            let mut left = v.as_mut().child[0]
                .take()
                .expect("the specified edge must exist");
            left.as_mut().parent.parent = None;
            Self::pull_top(v);
        }
    }

    pub fn root(&mut self, node: usize) -> usize {
        let mut root = self.node(node);
        self.access_node(root);
        unsafe {
            loop {
                TopBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(root));
                match root.as_ref().child[0] {
                    Some(left) => root = left,
                    None => break,
                }
            }
            Self::splay_top(root);
            root.as_ref().data.index_and_reverse >> 1
        }
    }

    pub fn is_connected(&mut self, u: usize, v: usize) -> bool {
        self.root(u) == self.root(v)
    }

    /// `u` and `v` must be connected.
    pub fn fold_path(&mut self, u: usize, v: usize) -> S::Path {
        self.reroot(u);
        let v = self.node(v);
        self.access_node(v);
        unsafe { v.as_ref().data.sum.clone() }
    }

    /// `u` and `v` must be connected.
    pub fn update_path(&mut self, u: usize, v: usize, action: &A::Action) {
        self.reroot(u);
        let v = self.node(v);
        self.access_node(v);
        if !TopBstSpec::<S, A>::is_unit(action) {
            unsafe { TopBstSpec::<S, A>::apply_heavy(v, action) };
        }
    }

    fn detach_left<R>(mut node: TopPtr<S, A>, f: impl FnOnce(TopPtr<S, A>) -> R) -> R {
        unsafe {
            let left = node.as_mut().child[0].take();
            if let Some(mut left) = left {
                left.as_mut().parent.parent = None;
            }
            Self::pull_top(node);
            let result = f(node);
            node.as_mut().child[0] = left;
            if let Some(mut left) = left {
                left.as_mut().parent.parent = Some(node);
            }
            Self::pull_top(node);
            result
        }
    }

    /// `(node, parent)` must be an edge.
    pub fn fold_subtree(&mut self, node: usize, parent: usize) -> S::Path {
        self.reroot(parent);
        let node = self.node(node);
        self.access_node(node);
        Self::detach_left(node, |node| unsafe { node.as_ref().data.sum.clone() })
    }

    /// `(node, parent)` must be an edge.
    pub fn update_subtree(&mut self, node: usize, parent: usize, action: &A::Action) {
        self.reroot(parent);
        let node = self.node(node);
        self.access_node(node);
        Self::detach_left(node, |node| unsafe {
            TopBstSpec::<S, A>::apply_all(node, action);
            TopBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node));
        });
    }

crates/competitive/src/data_structure/implicit_splay_tree.rs (line 92)

    fn update_act(mut node: BstDataMutRef<'_, Self>, act: &T::Act) {
        if T::is_act_unit(act) {
            return;
        }
        T::act_operate_assign(&mut node.data_mut().value.act, act);
        node.data_mut().value.key = T::act_key(&node.reborrow().into_data().value.key, act);
        if let Some(agg) = T::act_agg(&node.reborrow().into_data().value.agg, act) {
            node.data_mut().value.agg = agg;
        } else {
            Self::top_down(node.reborrow_datamut());
            Self::bottom_up(node);
        }
    }

    fn reverse(mut node: BstDataMutRef<'_, Self>) {
        node.swap_children();
        let data = node.data_mut();
        T::toggle(&mut data.value.agg);
        data.rev ^= true;
    }
}

impl<T> BstSpec for ImplicitSplayTreeSpec<T>
where
    T: LazyMapMonoid,
{
    type Parent = WithNoParent<Self::Data>;
    type Data = ImplicitSplayTreeData<T>;

    fn top_down(mut node: BstDataMutRef<'_, Self>) {
        if !T::is_act_unit(&node.reborrow().into_data().value.act) {
            let act = replace(&mut node.data_mut().value.act, T::act_unit());
            if let Ok(left) = node.reborrow_datamut().left().descend() {
                Self::update_act(left, &act);
            }
            if let Ok(right) = node.reborrow_datamut().right().descend() {
                Self::update_act(right, &act);
            }
        }
        if node.reborrow().into_data().rev {
            node.data_mut().rev = false;
            if let Ok(left) = node.reborrow_datamut().left().descend() {
                Self::reverse(left);
            }
            if let Ok(right) = node.reborrow_datamut().right().descend() {
                Self::reverse(right);
            }
        }
    }

    fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
        let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
        let mut size = 1;
        if let Ok(left) = node.reborrow().left().descend() {
            let data = left.into_data();
            agg = T::agg_operate(&data.value.agg, &agg);
            size += data.size;
        }
        if let Ok(right) = node.reborrow().right().descend() {
            let data = right.into_data();
            agg = T::agg_operate(&agg, &data.value.agg);
            size += data.size;
        }
        let data = node.data_mut();
        data.value.agg = agg;
        data.size = size;
    }

    fn merge(
        left: Option<ImplicitSplayTreeRoot<T>>,
        right: Option<ImplicitSplayTreeRoot<T>>,
    ) -> Option<ImplicitSplayTreeRoot<T>> {
        splay_operations::merge(left, right)
    }

    fn split<Seeker>(
        node: Option<ImplicitSplayTreeRoot<T>>,
        seeker: Seeker,
        equal_side: EqualSide,
    ) -> (
        Option<ImplicitSplayTreeRoot<T>>,
        Option<ImplicitSplayTreeRoot<T>>,
    )
    where
        Seeker: BstSeeker<Spec = Self>,
    {
        splay_operations::split(node, seeker, equal_side)
    }
}

pub struct ImplicitSplayTree<T, A = MemoryPool<ImplicitSplayTreeNode<T>>>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitSplayTreeNode<T>>,
{
    root: Option<ImplicitSplayTreeRoot<T>>,
    length: usize,
    allocator: ManuallyDrop<A>,
    _marker: PhantomData<fn() -> T>,
}

impl<T, A> Default for ImplicitSplayTree<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitSplayTreeNode<T>> + Default,
{
    fn default() -> Self {
        Self {
            root: None,
            length: 0,
            allocator: ManuallyDrop::new(A::default()),
            _marker: PhantomData,
        }
    }
}

impl<T, A> Drop for ImplicitSplayTree<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitSplayTreeNode<T>>,
{
    fn drop(&mut self) {
        unsafe {
            if let Some(root) = self.root.take() {
                root.into_dying().drop_all(self.allocator.deref_mut());
            }
            ManuallyDrop::drop(&mut self.allocator);
        }
    }
}

impl<T> ImplicitSplayTree<T>
where
    T: LazyMapMonoid,
{
    pub fn new() -> Self {
        Self::default()
    }

    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: None,
            length: 0,
            allocator: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
            _marker: PhantomData,
        }
    }
}

impl<T, A> ImplicitSplayTree<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitSplayTreeNode<T>>,
{
    fn node(&mut self, key: T::Key) -> ImplicitSplayTreeRoot<T> {
        BstRoot::from_data(
            ImplicitSplayTreeData {
                value: LazyMapElement::from_key(key),
                size: 1,
                rev: false,
            },
            self.allocator.deref_mut(),
        )
    }

    #[inline]
    fn splay<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
    where
        Seeker: BstSeeker<Spec = ImplicitSplayTreeSpec<T>>,
    {
        let (ordering, root) = splay_operations::splay(self.root.take()?, seeker);
        self.root = Some(root);
        Some(ordering)
    }

    pub fn len(&self) -> usize {
        self.length
    }

    pub fn is_empty(&self) -> bool {
        self.length == 0
    }

    pub fn update<R>(&mut self, range: R, act: T::Act)
    where
        R: RangeBounds<usize>,
    {
        let mut split = Split3::seek_by_size(&mut self.root, range);
        if let Some(root) = split.mid_datamut() {
            ImplicitSplayTreeSpec::update_act(root, &act);
        }
    }

    pub fn fold<R>(&mut self, range: R) -> T::Agg
    where
        R: RangeBounds<usize>,
    {
        let split = Split3::seek_by_size(&mut self.root, range);
        split
            .mid()
            .map(|node| node.into_data().value.agg.clone())
            .unwrap_or_else(T::agg_unit)
    }

    pub fn reverse<R>(&mut self, range: R)
    where
        R: RangeBounds<usize>,
    {
        let mut split = Split3::seek_by_size(&mut self.root, range);
        if let Some(root) = split.mid_datamut() {
            ImplicitSplayTreeSpec::reverse(root);
        }
    }

    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
        if index >= self.length {
            return None;
        }
        self.splay(SeekBySize::new(index));
        Some(&self.root.as_ref()?.reborrow().into_data().value.key)
    }

    pub fn modify<F>(&mut self, index: usize, f: F)
    where
        F: FnOnce(&T::Key) -> T::Key,
    {
        assert!(index < self.length);
        self.splay(SeekBySize::new(index));
        let mut root = self.root.as_mut().unwrap().borrow_datamut();
        ImplicitSplayTreeSpec::top_down(root.reborrow_datamut());
        {
            let data = root.data_mut();
            data.value.key = f(&data.value.key);
        }
        ImplicitSplayTreeSpec::bottom_up(root);
    }

    pub fn insert(&mut self, index: usize, key: T::Key) {
        assert!(index <= self.length);
        let mut node = self.node(key);
        if self.root.is_none() {
            self.root = Some(node);
        } else if index == self.length {
            self.splay(SeekBySize::new(index));
            unsafe { node.borrow_mut().left_mut().set(self.root.take().unwrap()) };
            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
            self.root = Some(node);
        } else {
            self.splay(SeekBySize::new(index));
            let mut root = self.root.take().unwrap();
            let left = unsafe { root.borrow_mut().left_mut().take() };
            if let Some(left) = left {
                unsafe { node.borrow_mut().left_mut().set(left) };
            }
            ImplicitSplayTreeSpec::bottom_up(root.borrow_datamut());
            unsafe { node.borrow_mut().right_mut().set(root) };
            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
            self.root = Some(node);
        }
        self.length += 1;
    }

    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
        if index >= self.length {
            return None;
        }
        self.splay(SeekBySize::new(index));
        let mut node = self.root.take().unwrap();
        ImplicitSplayTreeSpec::top_down(node.borrow_datamut());
        let left = unsafe { node.borrow_mut().left_mut().take() };
        let right = unsafe { node.borrow_mut().right_mut().take() };
        self.root = ImplicitSplayTreeSpec::merge(left, right);
        self.length -= 1;
        let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
        Some(data.value.key)
    }

crates/competitive/src/data_structure/implicit_treap.rs (line 93)

    fn update_act(mut node: BstDataMutRef<'_, Self>, act: &T::Act) {
        if T::is_act_unit(act) {
            return;
        }
        T::act_operate_assign(&mut node.data_mut().value.act, act);
        node.data_mut().value.key = T::act_key(&node.reborrow().into_data().value.key, act);
        if let Some(agg) = T::act_agg(&node.reborrow().into_data().value.agg, act) {
            node.data_mut().value.agg = agg;
        } else {
            Self::top_down(node.reborrow_datamut());
            Self::bottom_up(node);
        }
    }

    fn reverse(mut node: BstDataMutRef<'_, Self>) {
        node.swap_children();
        let data = node.data_mut();
        T::toggle(&mut data.value.agg);
        data.rev ^= true;
    }
}

impl<T> BstSpec for ImplicitTreapSpec<T>
where
    T: LazyMapMonoid,
{
    type Parent = WithNoParent<Self::Data>;
    type Data = ImplicitTreapData<T>;

    fn top_down(mut node: BstDataMutRef<'_, Self>) {
        if !T::is_act_unit(&node.reborrow().into_data().value.act) {
            let act = replace(&mut node.data_mut().value.act, T::act_unit());
            if let Ok(left) = node.reborrow_datamut().left().descend() {
                Self::update_act(left, &act);
            }
            if let Ok(right) = node.reborrow_datamut().right().descend() {
                Self::update_act(right, &act);
            }
        }
        if node.reborrow().into_data().rev {
            node.data_mut().rev = false;
            if let Ok(left) = node.reborrow_datamut().left().descend() {
                Self::reverse(left);
            }
            if let Ok(right) = node.reborrow_datamut().right().descend() {
                Self::reverse(right);
            }
        }
    }

    fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
        let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
        let mut size = 1;
        if let Ok(left) = node.reborrow().left().descend() {
            let data = left.into_data();
            agg = T::agg_operate(&data.value.agg, &agg);
            size += data.size;
        }
        if let Ok(right) = node.reborrow().right().descend() {
            let data = right.into_data();
            agg = T::agg_operate(&agg, &data.value.agg);
            size += data.size;
        }
        let data = node.data_mut();
        data.value.agg = agg;
        data.size = size;
    }

    fn merge(
        left: Option<ImplicitTreapRoot<T>>,
        right: Option<ImplicitTreapRoot<T>>,
    ) -> Option<ImplicitTreapRoot<T>> {
        match (left, right) {
            (None, None) => None,
            (None, Some(node)) | (Some(node), None) => Some(node),
            (Some(mut left), Some(mut right)) => unsafe {
                if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
                    Self::top_down(left.borrow_datamut());
                    let lr = left.borrow_mut().right().take();
                    let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
                    left.borrow_mut().right().set(lr);
                    Self::bottom_up(left.borrow_datamut());
                    Some(left)
                } else {
                    Self::top_down(right.borrow_datamut());
                    let rl = right.borrow_mut().left().take();
                    let rl = Self::merge(Some(left), rl).unwrap_unchecked();
                    right.borrow_mut().left().set(rl);
                    Self::bottom_up(right.borrow_datamut());
                    Some(right)
                }
            },
        }
    }

    fn split<Seeker>(
        node: Option<ImplicitTreapRoot<T>>,
        mut seeker: Seeker,
        equal_side: EqualSide,
    ) -> (Option<ImplicitTreapRoot<T>>, Option<ImplicitTreapRoot<T>>)
    where
        Seeker: BstSeeker<Spec = Self>,
    {
        match node {
            None => (None, None),
            Some(mut node) => {
                Self::top_down(node.borrow_datamut());
                if equal_side.goes_left(seeker.bst_seek(node.reborrow())) {
                    unsafe {
                        let right = node.borrow_mut().right().take();
                        let (l, r) = Self::split(right, seeker, equal_side);
                        if let Some(l) = l {
                            node.borrow_mut().right().set(l);
                        }
                        Self::bottom_up(node.borrow_datamut());
                        (Some(node), r)
                    }
                } else {
                    unsafe {
                        let left = node.borrow_mut().left().take();
                        let (l, r) = Self::split(left, seeker, equal_side);
                        if let Some(r) = r {
                            node.borrow_mut().left().set(r);
                        }
                        Self::bottom_up(node.borrow_datamut());
                        (l, Some(node))
                    }
                }
            }
        }
    }
}

pub struct ImplicitTreap<T, A = MemoryPool<ImplicitTreapNode<T>>>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitTreapNode<T>>,
{
    root: Option<ImplicitTreapRoot<T>>,
    length: usize,
    rng: Xorshift,
    allocator: ManuallyDrop<A>,
    _marker: PhantomData<fn() -> T>,
}

impl<T, A> Default for ImplicitTreap<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitTreapNode<T>> + Default,
{
    fn default() -> Self {
        Self {
            root: None,
            length: 0,
            rng: Xorshift::new(),
            allocator: ManuallyDrop::new(A::default()),
            _marker: PhantomData,
        }
    }
}

impl<T, A> Drop for ImplicitTreap<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitTreapNode<T>>,
{
    fn drop(&mut self) {
        unsafe {
            if let Some(root) = self.root.take() {
                root.into_dying().drop_all(self.allocator.deref_mut());
            }
            ManuallyDrop::drop(&mut self.allocator);
        }
    }
}

impl<T> ImplicitTreap<T>
where
    T: LazyMapMonoid,
{
    pub fn new() -> Self {
        Self::default()
    }

    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: None,
            length: 0,
            rng: Xorshift::new(),
            allocator: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
            _marker: PhantomData,
        }
    }
}

impl<T, A> ImplicitTreap<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitTreapNode<T>>,
{
    fn node(&mut self, key: T::Key) -> ImplicitTreapRoot<T> {
        BstRoot::from_data(
            ImplicitTreapData {
                priority: self.rng.rand64(),
                value: LazyMapElement::from_key(key),
                size: 1,
                rev: false,
            },
            self.allocator.deref_mut(),
        )
    }

    fn build<I>(&mut self, iter: I) -> (Option<ImplicitTreapRoot<T>>, usize)
    where
        I: IntoIterator<Item = T::Key>,
    {
        let mut stack = vec![];
        let mut len = 0;
        for key in iter {
            let mut cur = self.node(key).node;
            let mut left = None;
            unsafe {
                while stack
                    .last()
                    .is_some_and(|node: &NonNull<ImplicitTreapNode<T>>| {
                        node.as_ref().data.priority < cur.as_ref().data.priority
                    })
                {
                    left = stack.pop();
                }
                cur.as_mut().child[0] = left;
                if let Some(parent) = stack.last_mut() {
                    parent.as_mut().child[1] = Some(cur);
                }
            }
            stack.push(cur);
            len += 1;
        }
        let root = stack.first().copied().map(BstRoot::new);
        if let Some(mut root) = root {
            Self::build_bottom_up(root.borrow_datamut());
            (Some(root), len)
        } else {
            (None, len)
        }
    }

    fn build_bottom_up(mut node: BstDataMutRef<'_, ImplicitTreapSpec<T>>) {
        if let Ok(left) = node.reborrow_datamut().left().descend() {
            Self::build_bottom_up(left);
        }
        if let Ok(right) = node.reborrow_datamut().right().descend() {
            Self::build_bottom_up(right);
        }
        ImplicitTreapSpec::<T>::bottom_up(node);
    }

    pub fn len(&self) -> usize {
        self.length
    }

    pub fn is_empty(&self) -> bool {
        self.length == 0
    }

    pub fn update<R>(&mut self, range: R, x: T::Act)
    where
        R: RangeBounds<usize>,
    {
        let mut split = Split3::seek_by_size(&mut self.root, range);
        if let Some(root) = split.mid_datamut() {
            ImplicitTreapSpec::<T>::update_act(root, &x);
        }
    }

    pub fn fold<R>(&mut self, range: R) -> T::Agg
    where
        R: RangeBounds<usize>,
    {
        let split = Split3::seek_by_size(&mut self.root, range);
        split
            .mid()
            .map(|node| node.into_data().value.agg.clone())
            .unwrap_or_else(T::agg_unit)
    }

    pub fn reverse<R>(&mut self, range: R)
    where
        R: RangeBounds<usize>,
    {
        let mut split = Split3::seek_by_size(&mut self.root, range);
        if let Some(root) = split.mid_datamut() {
            ImplicitTreapSpec::<T>::reverse(root);
        }
    }

    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
        if index >= self.length {
            return None;
        }
        let split = Split3::seek_by_size(&mut self.root, index..=index);
        let node = split.mid()?.node;
        drop(split);
        Some(unsafe { &(*node.as_ptr()).data.value.key })
    }

    pub fn modify<F>(&mut self, index: usize, f: F)
    where
        F: FnOnce(&T::Key) -> T::Key,
    {
        assert!(index < self.length);
        let mut split = Split3::seek_by_size(&mut self.root, index..=index);
        let mut node = split.mid_datamut().unwrap();
        ImplicitTreapSpec::<T>::top_down(node.reborrow_datamut());
        {
            let data = node.data_mut();
            data.value.key = f(&data.value.key);
        }
        ImplicitTreapSpec::<T>::bottom_up(node);
    }

    pub fn insert(&mut self, index: usize, x: T::Key) {
        assert!(index <= self.length);
        let node = self.node(x);
        if index == 0 {
            self.root = ImplicitTreapSpec::<T>::merge(Some(node), self.root.take());
        } else if index == self.length {
            self.root = ImplicitTreapSpec::<T>::merge(self.root.take(), Some(node));
        } else {
            let mut node = Some(node);
            let mut split = Split::new(&mut self.root, SeekBySize::new(index), EqualSide::Right);
            split.manually_merge(|left, right| {
                ImplicitTreapSpec::<T>::merge(
                    ImplicitTreapSpec::<T>::merge(left, node.take()),
                    right,
                )
            });
        }
        self.length += 1;
    }

    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
        if index >= self.length {
            return None;
        }
        let mid;
        if index == 0 {
            let (left, right) = ImplicitTreapSpec::<T>::split(
                self.root.take(),
                SeekBySize::new(1),
                EqualSide::Right,
            );
            mid = left;
            self.root = right;
        } else if index + 1 == self.length {
            let (left, right) = ImplicitTreapSpec::<T>::split(
                self.root.take(),
                SeekBySize::new(index),
                EqualSide::Right,
            );
            mid = right;
            self.root = left;
        } else {
            let (left, rest) = ImplicitTreapSpec::<T>::split(
                self.root.take(),
                SeekBySize::new(index),
                EqualSide::Right,
            );
            let (middle, right) =
                ImplicitTreapSpec::<T>::split(rest, SeekBySize::new(1), EqualSide::Right);
            mid = middle;
            self.root = ImplicitTreapSpec::<T>::merge(left, right);
        }
        self.length -= 1;
        let mut node = mid.unwrap();
        ImplicitTreapSpec::<T>::top_down(node.borrow_datamut());
        let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
        Some(data.value.key)
    }

crates/competitive/src/data_structure/binary_search_tree/node.rs (line 146)

    pub fn resolve_top_down<Spec>(node: BstNodeRef<marker::DataMut<'_>, Spec>)
    where
        Spec: BstSpec<Data = Data, Parent = Self>,
    {
        unsafe {
            let (mut node, mut stack) = node.root_path();
            while let Some(is_left) = stack.pop() {
                Spec::top_down(node.reborrow_datamut());
                if is_left {
                    node = node.left().descend().unwrap_unchecked();
                } else {
                    node = node.right().descend().unwrap_unchecked();
                }
            }
            Spec::top_down(node.reborrow_datamut());
        }
    }

crates/competitive/src/tree/link_cut_tree.rs (line 248)

    fn access_node(mut node: LinkCutPtr<S>) {
        unsafe {
            Self::splay(node);
            if let Some(right) = node.as_mut().child[1].take() {
                LinkCutBstSpec::<S>::with_two_inner_mut(node, right, S::attach_virtual);
            }
            Self::pull(node);
            while let Some(mut parent) = node.as_ref().parent.parent {
                Self::splay(parent);
                if let Some(right) = parent.as_mut().child[1].take() {
                    LinkCutBstSpec::<S>::with_two_inner_mut(parent, right, S::attach_virtual);
                }
                LinkCutBstSpec::<S>::with_two_inner_mut(parent, node, S::detach_virtual);
                parent.as_mut().child[1] = Some(node);
                node.as_mut().parent.parent = Some(parent);
                LinkCutBstSpec::<S>::top_down(BstDataMutRef::new_unchecked(node));
                splay_operations::with_parent::rotate::<LinkCutBstSpec<S>, LinkCutData<S>>(node);
                Self::pull(node);
                LinkCutBstSpec::<S>::with_two_inner_mut(parent, node, S::transfer_path_parent);
            }
        }
    }

    pub fn get(&mut self, node: usize) -> &S::Value {
        let node = self.node(node);
        Self::access_node(node);
        unsafe { S::value(&node.as_ref().data.inner) }
    }

    pub fn set(&mut self, node: usize, value: S::Value) {
        self.modify(node, |_| value);
    }

    pub fn modify<F>(&mut self, node: usize, f: F)
    where
        F: FnOnce(&S::Value) -> S::Value,
    {
        let node = self.node(node);
        if S::MODIFY_REQUIRES_ACCESS {
            Self::access_node(node);
        } else {
            unsafe { Self::splay(node) };
        }
        unsafe {
            let data = &mut (*node.as_ptr()).data.inner;
            *S::value_mut(data) = f(S::value(data));
            Self::pull(node);
        }
    }

    pub fn reroot(&mut self, node: usize) {
        let node = self.node(node);
        Self::access_node(node);
        unsafe { LinkCutBstSpec::<S>::toggle(node) };
    }

    /// `child` and `parent` must belong to different trees.
    pub fn link(&mut self, child: usize, parent: usize) {
        assert_ne!(child, parent);
        self.reroot(child);
        let child = self.node(child);
        let parent = self.node(parent);
        Self::access_node(parent);
        unsafe {
            (*child.as_ptr()).parent.parent = Some(parent);
            LinkCutBstSpec::<S>::with_two_inner_mut(parent, child, S::attach_virtual);
            Self::pull(parent);
        }
    }

    /// `(u, v)` must be an edge.
    pub fn cut(&mut self, u: usize, v: usize) {
        assert_ne!(u, v);
        self.reroot(u);
        let mut v = self.node(v);
        Self::access_node(v);
        unsafe {
            let mut left = v.as_mut().child[0]
                .take()
                .expect("the specified edge must exist");
            left.as_mut().parent.parent = None;
            Self::pull(v);
        }
    }

    pub fn root(&mut self, node: usize) -> usize {
        let mut root = self.node(node);
        Self::access_node(root);
        unsafe {
            loop {
                LinkCutBstSpec::<S>::top_down(BstDataMutRef::new_unchecked(root));
                match root.as_ref().child[0] {
                    Some(left) => root = left,
                    None => break,
                }
            }
            Self::splay(root);
            root.as_ref().data.index_and_reverse >> 1
        }
    }

    pub fn is_connected(&mut self, u: usize, v: usize) -> bool {
        self.root(u) == self.root(v)
    }

    fn detach_left<R>(node: LinkCutPtr<S>, f: impl FnOnce(&mut S::Data) -> R) -> R {
        unsafe {
            let left = (*node.as_ptr()).child[0].take();
            if let Some(mut left) = left {
                left.as_mut().parent.parent = None;
            }
            Self::pull(node);
            let result = f(&mut (*node.as_ptr()).data.inner);
            LinkCutBstSpec::<S>::top_down(BstDataMutRef::new_unchecked(node));
            (*node.as_ptr()).child[0] = left;
            if let Some(mut left) = left {
                left.as_mut().parent.parent = Some(node);
            }
            Self::pull(node);
            result
        }
    }

crates/competitive/src/data_structure/treap.rs (line 126)

    fn merge(
        left: Option<TreapRoot<M, L>>,
        right: Option<TreapRoot<M, L>>,
    ) -> Option<TreapRoot<M, L>> {
        match (left, right) {
            (None, None) => None,
            (None, Some(node)) | (Some(node), None) => Some(node),
            (Some(mut left), Some(mut right)) => unsafe {
                if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
                    TreapSpec::top_down(left.borrow_datamut());
                    let lr = left.borrow_mut().right().take();
                    let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
                    left.borrow_mut().right().set(lr);
                    TreapSpec::bottom_up(left.borrow_datamut());
                    Some(left)
                } else {
                    TreapSpec::top_down(right.borrow_datamut());
                    let rl = right.borrow_mut().left().take();
                    let rl = Self::merge(Some(left), rl).unwrap_unchecked();
                    right.borrow_mut().left().set(rl);
                    TreapSpec::bottom_up(right.borrow_datamut());
                    Some(right)
                }
            },
        }
    }

    fn split<Seeker>(
        node: Option<TreapRoot<M, L>>,
        mut seeker: Seeker,
        equal_side: EqualSide,
    ) -> (Option<TreapRoot<M, L>>, Option<TreapRoot<M, L>>)
    where
        Seeker: BstSeeker<Spec = Self>,
    {
        match node {
            None => (None, None),
            Some(mut node) => {
                Self::top_down(node.borrow_datamut());
                if equal_side.goes_left(seeker.bst_seek(node.reborrow())) {
                    unsafe {
                        let right = node.borrow_mut().right().take();
                        let (l, r) = Self::split(right, seeker, equal_side);
                        if let Some(l) = l {
                            node.borrow_mut().right().set(l);
                        }
                        Self::bottom_up(node.borrow_datamut());
                        (Some(node), r)
                    }
                } else {
                    unsafe {
                        let left = node.borrow_mut().left().take();
                        let (l, r) = Self::split(left, seeker, equal_side);
                        if let Some(r) = r {
                            node.borrow_mut().left().set(r);
                        }
                        Self::bottom_up(node.borrow_datamut());
                        (l, Some(node))
                    }
                }
            }
        }
    }
}

impl<M, L> TreapSpec<M, L>
where
    M: MonoidAct<Key: Ord>,
    L: LazyMapMonoid,
{
    pub fn merge_ordered(
        left: Option<TreapRoot<M, L>>,
        right: Option<TreapRoot<M, L>>,
    ) -> Option<TreapRoot<M, L>> {
        match (left, right) {
            (None, None) => None,
            (None, Some(node)) | (Some(node), None) => Some(node),
            (Some(mut left), Some(mut right)) => unsafe {
                if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
                    Self::top_down(left.borrow_datamut());
                    let key = &left.reborrow().into_data().key.key;
                    let (rl, rr) = Self::split(Some(right), SeekByKey::new(key), EqualSide::Right);
                    let ll = left.borrow_mut().left().take();
                    let lr = left.borrow_mut().right().take();
                    if let Some(l) = Self::merge_ordered(ll, rl) {
                        left.borrow_mut().left().set(l);
                    }
                    if let Some(r) = Self::merge_ordered(lr, rr) {
                        left.borrow_mut().right().set(r);
                    }
                    Self::bottom_up(left.borrow_datamut());
                    Some(left)
                } else {
                    Self::top_down(right.borrow_datamut());
                    let key = &right.reborrow().into_data().key.key;
                    let (ll, lr) = Self::split(Some(left), SeekByKey::new(key), EqualSide::Right);
                    let rl = right.borrow_mut().left().take();
                    let rr = right.borrow_mut().right().take();
                    if let Some(l) = Self::merge_ordered(ll, rl) {
                        right.borrow_mut().left().set(l);
                    }
                    if let Some(r) = Self::merge_ordered(lr, rr) {
                        right.borrow_mut().right().set(r);
                    }
                    Self::bottom_up(right.borrow_datamut());
                    Some(right)
                }
            },
        }
    }

Additional examples can be found in:

• crates/competitive/src/data_structure/splay_operations.rs

fn bottom_up(_node: BstDataMutRef<'_, Self>)

Examples found in repository

crates/competitive/src/tree/top_tree.rs (line 369)

    unsafe fn pull_top(node: TopPtr<S, A>) {
        unsafe { TopBstSpec::<S, A>::bottom_up(BstDataMutRef::new_unchecked(node)) };
    }

    #[inline]
    unsafe fn pull_rake(node: RakePtr<S, A>) {
        unsafe { RakeBstSpec::<S, A>::bottom_up(BstDataMutRef::new_unchecked(node)) };
    }

crates/competitive/src/tree/link_cut_tree.rs (line 208)

    unsafe fn pull(node: LinkCutPtr<S>) {
        unsafe {
            LinkCutBstSpec::<S>::bottom_up(BstDataMutRef::new_unchecked(node));
        }
    }

crates/competitive/src/data_structure/binary_search_tree/node.rs (line 162)

    pub fn resolve_bottom_up<Spec>(mut node: BstNodeRef<marker::DataMut<'_>, Spec>)
    where
        Spec: BstSpec<Data = Data, Parent = Self>,
    {
        loop {
            Spec::bottom_up(node.reborrow_datamut());
            match node.ascend() {
                Ok(parent) => node = parent,
                Err(_) => break,
            }
        }
    }

    pub fn is_root<Spec>(node: BstNodeRef<marker::Immut<'_>, Spec>) -> bool
    where
        Spec: BstSpec<Data = Data, Parent = Self>,
    {
        unsafe { node.node.as_ref().parent.parent.is_none() }
    }

    pub unsafe fn remove_root<Spec>(
        root: &mut Option<BstRoot<Spec>>,
    ) -> Option<BstNodeRef<marker::Owned, Spec>>
    where
        Spec: BstSpec<Data = Data, Parent = Self>,
    {
        let mut node = root.take()?;
        unsafe {
            let left = node.borrow_mut().left_mut().take();
            let right = node.borrow_mut().right_mut().take();
            *root = Spec::merge(left, right);
            Spec::bottom_up(node.borrow_datamut());
            Some(node)
        }
    }

    pub unsafe fn remove_not_root<Spec>(
        mut node: BstNodeRef<marker::Mut<'_>, Spec>,
    ) -> BstNodeRef<marker::Owned, Spec>
    where
        Spec: BstSpec<Data = Data, Parent = Self>,
    {
        assert!(!Self::is_root(node.reborrow()));
        unsafe {
            let left = node.left_mut().take();
            let right = node.right_mut().take();
            let merged = Spec::merge(left, right);
            let node_inner = node.node;
            let mut parent = node.ascend().unwrap_unchecked();
            let mut node = if let Some(merged) = merged {
                let node = if parent
                    .reborrow()
                    .left()
                    .descend()
                    .is_ok_and(|n| n.node == node_inner)
                {
                    parent.left_mut().replace(merged)
                } else {
                    parent.right_mut().replace(merged)
                };
                Self::resolve_bottom_up(parent.reborrow_datamut());
                node.unwrap_unchecked()
            } else {
                let node = if parent
                    .reborrow()
                    .left()
                    .descend()
                    .is_ok_and(|n| n.node == node_inner)
                {
                    parent.left_mut().take()
                } else {
                    parent.right_mut().take()
                };
                Self::resolve_bottom_up(parent.reborrow_datamut());
                node.unwrap_unchecked()
            };
            Spec::bottom_up(node.borrow_datamut());
            node
        }
    }

crates/competitive/src/data_structure/implicit_splay_tree.rs (line 93)

    fn update_act(mut node: BstDataMutRef<'_, Self>, act: &T::Act) {
        if T::is_act_unit(act) {
            return;
        }
        T::act_operate_assign(&mut node.data_mut().value.act, act);
        node.data_mut().value.key = T::act_key(&node.reborrow().into_data().value.key, act);
        if let Some(agg) = T::act_agg(&node.reborrow().into_data().value.agg, act) {
            node.data_mut().value.agg = agg;
        } else {
            Self::top_down(node.reborrow_datamut());
            Self::bottom_up(node);
        }
    }

    fn reverse(mut node: BstDataMutRef<'_, Self>) {
        node.swap_children();
        let data = node.data_mut();
        T::toggle(&mut data.value.agg);
        data.rev ^= true;
    }
}

impl<T> BstSpec for ImplicitSplayTreeSpec<T>
where
    T: LazyMapMonoid,
{
    type Parent = WithNoParent<Self::Data>;
    type Data = ImplicitSplayTreeData<T>;

    fn top_down(mut node: BstDataMutRef<'_, Self>) {
        if !T::is_act_unit(&node.reborrow().into_data().value.act) {
            let act = replace(&mut node.data_mut().value.act, T::act_unit());
            if let Ok(left) = node.reborrow_datamut().left().descend() {
                Self::update_act(left, &act);
            }
            if let Ok(right) = node.reborrow_datamut().right().descend() {
                Self::update_act(right, &act);
            }
        }
        if node.reborrow().into_data().rev {
            node.data_mut().rev = false;
            if let Ok(left) = node.reborrow_datamut().left().descend() {
                Self::reverse(left);
            }
            if let Ok(right) = node.reborrow_datamut().right().descend() {
                Self::reverse(right);
            }
        }
    }

    fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
        let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
        let mut size = 1;
        if let Ok(left) = node.reborrow().left().descend() {
            let data = left.into_data();
            agg = T::agg_operate(&data.value.agg, &agg);
            size += data.size;
        }
        if let Ok(right) = node.reborrow().right().descend() {
            let data = right.into_data();
            agg = T::agg_operate(&agg, &data.value.agg);
            size += data.size;
        }
        let data = node.data_mut();
        data.value.agg = agg;
        data.size = size;
    }

    fn merge(
        left: Option<ImplicitSplayTreeRoot<T>>,
        right: Option<ImplicitSplayTreeRoot<T>>,
    ) -> Option<ImplicitSplayTreeRoot<T>> {
        splay_operations::merge(left, right)
    }

    fn split<Seeker>(
        node: Option<ImplicitSplayTreeRoot<T>>,
        seeker: Seeker,
        equal_side: EqualSide,
    ) -> (
        Option<ImplicitSplayTreeRoot<T>>,
        Option<ImplicitSplayTreeRoot<T>>,
    )
    where
        Seeker: BstSeeker<Spec = Self>,
    {
        splay_operations::split(node, seeker, equal_side)
    }
}

pub struct ImplicitSplayTree<T, A = MemoryPool<ImplicitSplayTreeNode<T>>>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitSplayTreeNode<T>>,
{
    root: Option<ImplicitSplayTreeRoot<T>>,
    length: usize,
    allocator: ManuallyDrop<A>,
    _marker: PhantomData<fn() -> T>,
}

impl<T, A> Default for ImplicitSplayTree<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitSplayTreeNode<T>> + Default,
{
    fn default() -> Self {
        Self {
            root: None,
            length: 0,
            allocator: ManuallyDrop::new(A::default()),
            _marker: PhantomData,
        }
    }
}

impl<T, A> Drop for ImplicitSplayTree<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitSplayTreeNode<T>>,
{
    fn drop(&mut self) {
        unsafe {
            if let Some(root) = self.root.take() {
                root.into_dying().drop_all(self.allocator.deref_mut());
            }
            ManuallyDrop::drop(&mut self.allocator);
        }
    }
}

impl<T> ImplicitSplayTree<T>
where
    T: LazyMapMonoid,
{
    pub fn new() -> Self {
        Self::default()
    }

    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: None,
            length: 0,
            allocator: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
            _marker: PhantomData,
        }
    }
}

impl<T, A> ImplicitSplayTree<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitSplayTreeNode<T>>,
{
    fn node(&mut self, key: T::Key) -> ImplicitSplayTreeRoot<T> {
        BstRoot::from_data(
            ImplicitSplayTreeData {
                value: LazyMapElement::from_key(key),
                size: 1,
                rev: false,
            },
            self.allocator.deref_mut(),
        )
    }

    #[inline]
    fn splay<Seeker>(&mut self, seeker: Seeker) -> Option<Ordering>
    where
        Seeker: BstSeeker<Spec = ImplicitSplayTreeSpec<T>>,
    {
        let (ordering, root) = splay_operations::splay(self.root.take()?, seeker);
        self.root = Some(root);
        Some(ordering)
    }

    pub fn len(&self) -> usize {
        self.length
    }

    pub fn is_empty(&self) -> bool {
        self.length == 0
    }

    pub fn update<R>(&mut self, range: R, act: T::Act)
    where
        R: RangeBounds<usize>,
    {
        let mut split = Split3::seek_by_size(&mut self.root, range);
        if let Some(root) = split.mid_datamut() {
            ImplicitSplayTreeSpec::update_act(root, &act);
        }
    }

    pub fn fold<R>(&mut self, range: R) -> T::Agg
    where
        R: RangeBounds<usize>,
    {
        let split = Split3::seek_by_size(&mut self.root, range);
        split
            .mid()
            .map(|node| node.into_data().value.agg.clone())
            .unwrap_or_else(T::agg_unit)
    }

    pub fn reverse<R>(&mut self, range: R)
    where
        R: RangeBounds<usize>,
    {
        let mut split = Split3::seek_by_size(&mut self.root, range);
        if let Some(root) = split.mid_datamut() {
            ImplicitSplayTreeSpec::reverse(root);
        }
    }

    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
        if index >= self.length {
            return None;
        }
        self.splay(SeekBySize::new(index));
        Some(&self.root.as_ref()?.reborrow().into_data().value.key)
    }

    pub fn modify<F>(&mut self, index: usize, f: F)
    where
        F: FnOnce(&T::Key) -> T::Key,
    {
        assert!(index < self.length);
        self.splay(SeekBySize::new(index));
        let mut root = self.root.as_mut().unwrap().borrow_datamut();
        ImplicitSplayTreeSpec::top_down(root.reborrow_datamut());
        {
            let data = root.data_mut();
            data.value.key = f(&data.value.key);
        }
        ImplicitSplayTreeSpec::bottom_up(root);
    }

    pub fn insert(&mut self, index: usize, key: T::Key) {
        assert!(index <= self.length);
        let mut node = self.node(key);
        if self.root.is_none() {
            self.root = Some(node);
        } else if index == self.length {
            self.splay(SeekBySize::new(index));
            unsafe { node.borrow_mut().left_mut().set(self.root.take().unwrap()) };
            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
            self.root = Some(node);
        } else {
            self.splay(SeekBySize::new(index));
            let mut root = self.root.take().unwrap();
            let left = unsafe { root.borrow_mut().left_mut().take() };
            if let Some(left) = left {
                unsafe { node.borrow_mut().left_mut().set(left) };
            }
            ImplicitSplayTreeSpec::bottom_up(root.borrow_datamut());
            unsafe { node.borrow_mut().right_mut().set(root) };
            ImplicitSplayTreeSpec::bottom_up(node.borrow_datamut());
            self.root = Some(node);
        }
        self.length += 1;
    }

    pub fn remove(&mut self, index: usize) -> Option<T::Key> {
        if index >= self.length {
            return None;
        }
        self.splay(SeekBySize::new(index));
        let mut node = self.root.take().unwrap();
        ImplicitSplayTreeSpec::top_down(node.borrow_datamut());
        let left = unsafe { node.borrow_mut().left_mut().take() };
        let right = unsafe { node.borrow_mut().right_mut().take() };
        self.root = ImplicitSplayTreeSpec::merge(left, right);
        self.length -= 1;
        let data = unsafe { node.into_dying().into_data(self.allocator.deref_mut()) };
        Some(data.value.key)
    }

    pub fn partition_point_acc<F>(&mut self, left: usize, mut pred: F) -> usize
    where
        F: FnMut(&T::Agg) -> bool,
    {
        let mut split3 = Split3::seek_by_size(&mut self.root, left..);
        let front_size = split3
            .left()
            .map(|node| node.into_data().size)
            .unwrap_or_default();
        let split = split3.split_mid(SeekByAccCond::new(|acc| !pred(acc)), EqualSide::Right);
        let index = split
            .left()
            .map(|node| node.into_data().size)
            .unwrap_or_default();
        front_size + index
    }

    pub fn rpartition_point_acc<F>(&mut self, right: usize, mut pred: F) -> usize
    where
        F: FnMut(&T::Agg) -> bool,
    {
        let mut split3 = Split3::seek_by_size(&mut self.root, ..right);
        let split = split3.split_mid(SeekByRaccCond::new(|acc| !pred(acc)), EqualSide::Left);
        split
            .left()
            .map(|node| node.into_data().size)
            .unwrap_or_default()
    }

    pub fn rotate_left(&mut self, mid: usize) {
        assert!(mid <= self.length);
        if mid == 0 || mid == self.length {
            return;
        }
        let (left, right) =
            ImplicitSplayTreeSpec::split(self.root.take(), SeekBySize::new(mid), EqualSide::Right);
        self.root = ImplicitSplayTreeSpec::merge(right, left);
    }

    pub fn rotate_right(&mut self, k: usize) {
        assert!(k <= self.length);
        self.rotate_left(self.length - k);
    }
}

impl<T, A> Extend<T::Key> for ImplicitSplayTree<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitSplayTreeNode<T>>,
{
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = T::Key>,
    {
        let nodes = iter
            .into_iter()
            .map(|key| self.node(key))
            .collect::<Vec<_>>();
        let len = nodes.len();
        let root = if len == 0 {
            None
        } else {
            let mut stack = Vec::with_capacity(64);
            stack.push((0, len, None::<(usize, usize)>, false));
            while let Some((start, end, parent, visited)) = stack.pop() {
                if start == end {
                    continue;
                }
                let mid = start + (end - start) / 2;
                if visited {
                    ImplicitSplayTreeSpec::bottom_up(
                        BstRoot::new(nodes[mid].node).borrow_datamut(),
                    );
                    continue;
                }
                if let Some((parent, direction)) = parent {
                    let mut parent = nodes[parent].node;
                    unsafe { parent.as_mut().child[direction] = Some(nodes[mid].node) };
                }
                stack.push((start, end, parent, true));
                stack.push((mid + 1, end, Some((mid, 1)), false));
                stack.push((start, mid, Some((mid, 0)), false));
            }
            Some(BstRoot::new(nodes[len / 2].node))
        };
        self.root = ImplicitSplayTreeSpec::merge(self.root.take(), root);
        self.length += len;
    }

crates/competitive/src/data_structure/implicit_treap.rs (line 94)

    fn update_act(mut node: BstDataMutRef<'_, Self>, act: &T::Act) {
        if T::is_act_unit(act) {
            return;
        }
        T::act_operate_assign(&mut node.data_mut().value.act, act);
        node.data_mut().value.key = T::act_key(&node.reborrow().into_data().value.key, act);
        if let Some(agg) = T::act_agg(&node.reborrow().into_data().value.agg, act) {
            node.data_mut().value.agg = agg;
        } else {
            Self::top_down(node.reborrow_datamut());
            Self::bottom_up(node);
        }
    }

    fn reverse(mut node: BstDataMutRef<'_, Self>) {
        node.swap_children();
        let data = node.data_mut();
        T::toggle(&mut data.value.agg);
        data.rev ^= true;
    }
}

impl<T> BstSpec for ImplicitTreapSpec<T>
where
    T: LazyMapMonoid,
{
    type Parent = WithNoParent<Self::Data>;
    type Data = ImplicitTreapData<T>;

    fn top_down(mut node: BstDataMutRef<'_, Self>) {
        if !T::is_act_unit(&node.reborrow().into_data().value.act) {
            let act = replace(&mut node.data_mut().value.act, T::act_unit());
            if let Ok(left) = node.reborrow_datamut().left().descend() {
                Self::update_act(left, &act);
            }
            if let Ok(right) = node.reborrow_datamut().right().descend() {
                Self::update_act(right, &act);
            }
        }
        if node.reborrow().into_data().rev {
            node.data_mut().rev = false;
            if let Ok(left) = node.reborrow_datamut().left().descend() {
                Self::reverse(left);
            }
            if let Ok(right) = node.reborrow_datamut().right().descend() {
                Self::reverse(right);
            }
        }
    }

    fn bottom_up(mut node: BstDataMutRef<'_, Self>) {
        let mut agg = T::single_agg(&node.reborrow().into_data().value.key);
        let mut size = 1;
        if let Ok(left) = node.reborrow().left().descend() {
            let data = left.into_data();
            agg = T::agg_operate(&data.value.agg, &agg);
            size += data.size;
        }
        if let Ok(right) = node.reborrow().right().descend() {
            let data = right.into_data();
            agg = T::agg_operate(&agg, &data.value.agg);
            size += data.size;
        }
        let data = node.data_mut();
        data.value.agg = agg;
        data.size = size;
    }

    fn merge(
        left: Option<ImplicitTreapRoot<T>>,
        right: Option<ImplicitTreapRoot<T>>,
    ) -> Option<ImplicitTreapRoot<T>> {
        match (left, right) {
            (None, None) => None,
            (None, Some(node)) | (Some(node), None) => Some(node),
            (Some(mut left), Some(mut right)) => unsafe {
                if left.reborrow().into_data().priority > right.reborrow().into_data().priority {
                    Self::top_down(left.borrow_datamut());
                    let lr = left.borrow_mut().right().take();
                    let lr = Self::merge(lr, Some(right)).unwrap_unchecked();
                    left.borrow_mut().right().set(lr);
                    Self::bottom_up(left.borrow_datamut());
                    Some(left)
                } else {
                    Self::top_down(right.borrow_datamut());
                    let rl = right.borrow_mut().left().take();
                    let rl = Self::merge(Some(left), rl).unwrap_unchecked();
                    right.borrow_mut().left().set(rl);
                    Self::bottom_up(right.borrow_datamut());
                    Some(right)
                }
            },
        }
    }

    fn split<Seeker>(
        node: Option<ImplicitTreapRoot<T>>,
        mut seeker: Seeker,
        equal_side: EqualSide,
    ) -> (Option<ImplicitTreapRoot<T>>, Option<ImplicitTreapRoot<T>>)
    where
        Seeker: BstSeeker<Spec = Self>,
    {
        match node {
            None => (None, None),
            Some(mut node) => {
                Self::top_down(node.borrow_datamut());
                if equal_side.goes_left(seeker.bst_seek(node.reborrow())) {
                    unsafe {
                        let right = node.borrow_mut().right().take();
                        let (l, r) = Self::split(right, seeker, equal_side);
                        if let Some(l) = l {
                            node.borrow_mut().right().set(l);
                        }
                        Self::bottom_up(node.borrow_datamut());
                        (Some(node), r)
                    }
                } else {
                    unsafe {
                        let left = node.borrow_mut().left().take();
                        let (l, r) = Self::split(left, seeker, equal_side);
                        if let Some(r) = r {
                            node.borrow_mut().left().set(r);
                        }
                        Self::bottom_up(node.borrow_datamut());
                        (l, Some(node))
                    }
                }
            }
        }
    }
}

pub struct ImplicitTreap<T, A = MemoryPool<ImplicitTreapNode<T>>>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitTreapNode<T>>,
{
    root: Option<ImplicitTreapRoot<T>>,
    length: usize,
    rng: Xorshift,
    allocator: ManuallyDrop<A>,
    _marker: PhantomData<fn() -> T>,
}

impl<T, A> Default for ImplicitTreap<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitTreapNode<T>> + Default,
{
    fn default() -> Self {
        Self {
            root: None,
            length: 0,
            rng: Xorshift::new(),
            allocator: ManuallyDrop::new(A::default()),
            _marker: PhantomData,
        }
    }
}

impl<T, A> Drop for ImplicitTreap<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitTreapNode<T>>,
{
    fn drop(&mut self) {
        unsafe {
            if let Some(root) = self.root.take() {
                root.into_dying().drop_all(self.allocator.deref_mut());
            }
            ManuallyDrop::drop(&mut self.allocator);
        }
    }
}

impl<T> ImplicitTreap<T>
where
    T: LazyMapMonoid,
{
    pub fn new() -> Self {
        Self::default()
    }

    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            root: None,
            length: 0,
            rng: Xorshift::new(),
            allocator: ManuallyDrop::new(MemoryPool::with_capacity(capacity)),
            _marker: PhantomData,
        }
    }
}

impl<T, A> ImplicitTreap<T, A>
where
    T: LazyMapMonoid,
    A: Allocator<ImplicitTreapNode<T>>,
{
    fn node(&mut self, key: T::Key) -> ImplicitTreapRoot<T> {
        BstRoot::from_data(
            ImplicitTreapData {
                priority: self.rng.rand64(),
                value: LazyMapElement::from_key(key),
                size: 1,
                rev: false,
            },
            self.allocator.deref_mut(),
        )
    }

    fn build<I>(&mut self, iter: I) -> (Option<ImplicitTreapRoot<T>>, usize)
    where
        I: IntoIterator<Item = T::Key>,
    {
        let mut stack = vec![];
        let mut len = 0;
        for key in iter {
            let mut cur = self.node(key).node;
            let mut left = None;
            unsafe {
                while stack
                    .last()
                    .is_some_and(|node: &NonNull<ImplicitTreapNode<T>>| {
                        node.as_ref().data.priority < cur.as_ref().data.priority
                    })
                {
                    left = stack.pop();
                }
                cur.as_mut().child[0] = left;
                if let Some(parent) = stack.last_mut() {
                    parent.as_mut().child[1] = Some(cur);
                }
            }
            stack.push(cur);
            len += 1;
        }
        let root = stack.first().copied().map(BstRoot::new);
        if let Some(mut root) = root {
            Self::build_bottom_up(root.borrow_datamut());
            (Some(root), len)
        } else {
            (None, len)
        }
    }

    fn build_bottom_up(mut node: BstDataMutRef<'_, ImplicitTreapSpec<T>>) {
        if let Ok(left) = node.reborrow_datamut().left().descend() {
            Self::build_bottom_up(left);
        }
        if let Ok(right) = node.reborrow_datamut().right().descend() {
            Self::build_bottom_up(right);
        }
        ImplicitTreapSpec::<T>::bottom_up(node);
    }

    pub fn len(&self) -> usize {
        self.length
    }

    pub fn is_empty(&self) -> bool {
        self.length == 0
    }

    pub fn update<R>(&mut self, range: R, x: T::Act)
    where
        R: RangeBounds<usize>,
    {
        let mut split = Split3::seek_by_size(&mut self.root, range);
        if let Some(root) = split.mid_datamut() {
            ImplicitTreapSpec::<T>::update_act(root, &x);
        }
    }

    pub fn fold<R>(&mut self, range: R) -> T::Agg
    where
        R: RangeBounds<usize>,
    {
        let split = Split3::seek_by_size(&mut self.root, range);
        split
            .mid()
            .map(|node| node.into_data().value.agg.clone())
            .unwrap_or_else(T::agg_unit)
    }

    pub fn reverse<R>(&mut self, range: R)
    where
        R: RangeBounds<usize>,
    {
        let mut split = Split3::seek_by_size(&mut self.root, range);
        if let Some(root) = split.mid_datamut() {
            ImplicitTreapSpec::<T>::reverse(root);
        }
    }

    pub fn get(&mut self, index: usize) -> Option<&T::Key> {
        if index >= self.length {
            return None;
        }
        let split = Split3::seek_by_size(&mut self.root, index..=index);
        let node = split.mid()?.node;
        drop(split);
        Some(unsafe { &(*node.as_ptr()).data.value.key })
    }

    pub fn modify<F>(&mut self, index: usize, f: F)
    where
        F: FnOnce(&T::Key) -> T::Key,
    {
        assert!(index < self.length);
        let mut split = Split3::seek_by_size(&mut self.root, index..=index);
        let mut node = split.mid_datamut().unwrap();
        ImplicitTreapSpec::<T>::top_down(node.reborrow_datamut());
        {
            let data = node.data_mut();
            data.value.key = f(&data.value.key);
        }
        ImplicitTreapSpec::<T>::bottom_up(node);
    }

crates/competitive/src/data_structure/splay_operations.rs (line 65)

    pub unsafe fn rotate<Spec, Data>(mut node: NodePtr<Spec>)
    where
        Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
    {
        let (parent, direction) = unsafe { internal_parent::<Spec, Data>(node) }
            .expect("an auxiliary root cannot be rotated");
        unsafe {
            node.as_mut().parent.parent = parent.as_ref().parent.parent;
            if let Ok((mut grandparent, direction)) = internal_parent::<Spec, Data>(parent) {
                grandparent.as_mut().child[direction] = Some(node);
            }
            rotate_at::<Spec, Data>(node, parent, direction);
            Spec::bottom_up(BstDataMutRef::new_unchecked(parent));
        }
    }

    /// Moves `node` to the root of its auxiliary tree and returns the previous root.
    ///
    /// # Safety
    ///
    /// `node` and every pointer reachable through its auxiliary-parent chain must
    /// refer to live nodes of the same tree.
    #[inline(always)]
    pub unsafe fn splay<Spec, Data>(node: NodePtr<Spec>) -> NodePtr<Spec>
    where
        Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
    {
        let mut inline_stack = [const { MaybeUninit::uninit() }; 64];
        let mut inline_len = 0;
        let mut overflow_stack = Vec::new();
        let mut current = node;
        loop {
            if inline_len < inline_stack.len() {
                inline_stack[inline_len].write(current);
                inline_len += 1;
            } else {
                overflow_stack.push(current);
            }
            match unsafe { internal_parent::<Spec, Data>(current) } {
                Ok((parent, _)) => current = parent,
                Err(_) => break,
            }
        }
        for &node in overflow_stack.iter().rev() {
            unsafe { Spec::top_down(BstDataMutRef::new_unchecked(node)) };
        }
        while inline_len > 0 {
            inline_len -= 1;
            unsafe {
                Spec::top_down(BstDataMutRef::new_unchecked(
                    *inline_stack[inline_len].assume_init_ref(),
                ));
            }
        }

        while let Ok((parent, node_direction)) = unsafe { internal_parent::<Spec, Data>(node) } {
            if let Ok((_, parent_direction)) = unsafe { internal_parent::<Spec, Data>(parent) } {
                if node_direction == parent_direction {
                    unsafe { rotate::<Spec, Data>(parent) };
                } else {
                    unsafe { rotate::<Spec, Data>(node) };
                }
            }
            unsafe { rotate::<Spec, Data>(node) };
        }
        unsafe { Spec::bottom_up(BstDataMutRef::new_unchecked(node)) };
        current
    }

    /// Moves `node` to the root by propagating only the nodes involved in each rotation and
    /// returns the previous root.
    ///
    /// # Safety
    ///
    /// `node` and every pointer reachable through its auxiliary-parent chain must refer to live
    /// nodes of the same tree. Propagating an ancestor after its descendant must be valid for
    /// `Spec`.
    #[inline(always)]
    pub unsafe fn splay_with_local_top_down<Spec, Data>(mut node: NodePtr<Spec>) -> NodePtr<Spec>
    where
        Spec: BstSpec<Data = Data, Parent = WithParent<Data>>,
    {
        let mut current = node;
        unsafe { Spec::top_down(BstDataMutRef::new_unchecked(node)) };
        while let Ok((parent, _)) = unsafe { internal_parent::<Spec, Data>(node) } {
            match unsafe { internal_parent::<Spec, Data>(parent) } {
                Ok((grandparent, _)) => {
                    current = grandparent;
                    unsafe {
                        Spec::top_down(BstDataMutRef::new_unchecked(grandparent));
                        Spec::top_down(BstDataMutRef::new_unchecked(parent));
                        Spec::top_down(BstDataMutRef::new_unchecked(node));
                        let node_direction = usize::from(parent.as_ref().child[1] == Some(node));
                        let parent_direction =
                            usize::from(grandparent.as_ref().child[1] == Some(parent));
                        node.as_mut().parent.parent = grandparent.as_ref().parent.parent;
                        if let Ok((mut ancestor, direction)) =
                            internal_parent::<Spec, Data>(grandparent)
                        {
                            ancestor.as_mut().child[direction] = Some(node);
                        }
                        if node_direction == parent_direction {
                            rotate_at::<Spec, Data>(parent, grandparent, parent_direction);
                            rotate_at::<Spec, Data>(node, parent, node_direction);
                            Spec::bottom_up(BstDataMutRef::new_unchecked(grandparent));
                            Spec::bottom_up(BstDataMutRef::new_unchecked(parent));
                        } else {
                            rotate_at::<Spec, Data>(node, parent, node_direction);
                            rotate_at::<Spec, Data>(node, grandparent, parent_direction);
                            Spec::bottom_up(BstDataMutRef::new_unchecked(parent));
                            Spec::bottom_up(BstDataMutRef::new_unchecked(grandparent));
                        }
                    }
                }
                Err(ancestor) => {
                    current = parent;
                    unsafe {
                        Spec::top_down(BstDataMutRef::new_unchecked(parent));
                        Spec::top_down(BstDataMutRef::new_unchecked(node));
                        let direction = usize::from(parent.as_ref().child[1] == Some(node));
                        node.as_mut().parent.parent = ancestor;
                        rotate_at::<Spec, Data>(node, parent, direction);
                        Spec::bottom_up(BstDataMutRef::new_unchecked(parent));
                    }
                }
            }
        }
        unsafe { Spec::bottom_up(BstDataMutRef::new_unchecked(node)) };
        current
    }
}

pub fn rooted_heavy_order(
    vertices_size: usize,
    edges: &[(usize, usize)],
) -> Vec<(usize, usize, bool)> {
    if vertices_size == 0 {
        return Vec::new();
    }
    let mut head = vec![usize::MAX; vertices_size];
    let mut to = Vec::with_capacity(edges.len() * 2);
    let mut next = Vec::with_capacity(edges.len() * 2);
    for &(u, v) in edges {
        to.push(v);
        next.push(head[u]);
        head[u] = to.len() - 1;
        to.push(u);
        next.push(head[v]);
        head[v] = to.len() - 1;
    }
    let mut parent = vec![usize::MAX; vertices_size];
    let mut stack = vec![0];
    let mut order = Vec::with_capacity(vertices_size - 1);
    parent[0] = 0;
    while let Some(u) = stack.pop() {
        let mut edge = head[u];
        while edge != usize::MAX {
            let v = to[edge];
            if parent[v] == usize::MAX {
                parent[v] = u;
                order.push((v, u));
                stack.push(v);
            }
            edge = next[edge];
        }
    }
    let mut size = vec![1usize; vertices_size];
    let mut heavy = vec![usize::MAX; vertices_size];
    for &(child, parent) in order.iter().rev() {
        size[parent] += size[child];
        if heavy[parent] == usize::MAX || size[heavy[parent]] < size[child] {
            heavy[parent] = child;
        }
    }
    order
        .into_iter()
        .map(|(child, parent)| (child, parent, heavy[parent] == child))
        .collect()
}

#[inline]
pub fn splay<Spec, Data, Seeker>(
    root: BstRoot<Spec>,
    mut seeker: Seeker,
) -> (Ordering, BstRoot<Spec>)
where
    Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
    Seeker: BstSeeker<Spec = Spec>,
{
    let mut root = root;
    let mut left_subtree = None;
    let mut right_subtree = None;
    let mut left_entry = &mut left_subtree;
    let mut right_entry = &mut right_subtree;
    let mut inline_stack = [None; 24];
    let mut inline_len = 0;
    let mut overflow_stack = vec![];

    macro_rules! push_node {
        ($node:expr) => {
            if inline_len < inline_stack.len() {
                inline_stack[inline_len] = Some($node);
                inline_len += 1;
            } else {
                overflow_stack.push($node);
            }
        };
    }

    macro_rules! add {
        (@left $node:ident) => {
            *left_entry = Some($node.node);
            push_node!($node.node);
            left_entry = unsafe { &mut $node.node.as_mut().child[1] };
        };
        (@right $node:ident) => {
            *right_entry = Some($node.node);
            push_node!($node.node);
            right_entry = unsafe { &mut $node.node.as_mut().child[0] };
        };
    }

    let root_ordering = loop {
        Spec::top_down(root.borrow_datamut());
        match seeker.bst_seek(root.reborrow()) {
            Ordering::Greater => {
                let Some(mut child) = (unsafe { root.borrow_mut().left_mut().take() }) else {
                    break Ordering::Greater;
                };
                Spec::top_down(child.borrow_datamut());
                match seeker.bst_seek(child.reborrow()) {
                    Ordering::Greater => {
                        let Some(mut grandchild) =
                            (unsafe { child.borrow_mut().left_mut().take() })
                        else {
                            add!(@right root);
                            root = child;
                            break Ordering::Greater;
                        };
                        Spec::top_down(grandchild.borrow_datamut());
                        let child_right = unsafe { child.borrow_mut().right_mut().take() };
                        if let Some(child_right) = child_right {
                            unsafe { root.borrow_mut().left_mut().set(child_right) };
                        }
                        Spec::bottom_up(root.borrow_datamut());
                        unsafe { child.borrow_mut().right_mut().set(root) };
                        add!(@right child);
                        root = grandchild;
                    }
                    Ordering::Equal => {
                        add!(@right root);
                        root = child;
                        break Ordering::Equal;
                    }
                    Ordering::Less => {
                        let Some(mut grandchild) =
                            (unsafe { child.borrow_mut().right_mut().take() })
                        else {
                            add!(@right root);
                            root = child;
                            break Ordering::Less;
                        };
                        Spec::top_down(grandchild.borrow_datamut());
                        add!(@right root);
                        add!(@left child);
                        root = grandchild;
                    }
                }
            }
            Ordering::Equal => break Ordering::Equal,
            Ordering::Less => {
                let Some(mut child) = (unsafe { root.borrow_mut().right_mut().take() }) else {
                    break Ordering::Less;
                };
                Spec::top_down(child.borrow_datamut());
                match seeker.bst_seek(child.reborrow()) {
                    Ordering::Greater => {
                        let Some(mut grandchild) =
                            (unsafe { child.borrow_mut().left_mut().take() })
                        else {
                            add!(@left root);
                            root = child;
                            break Ordering::Greater;
                        };
                        Spec::top_down(grandchild.borrow_datamut());
                        add!(@left root);
                        add!(@right child);
                        root = grandchild;
                    }
                    Ordering::Equal => {
                        add!(@left root);
                        root = child;
                        break Ordering::Equal;
                    }
                    Ordering::Less => {
                        let Some(mut grandchild) =
                            (unsafe { child.borrow_mut().right_mut().take() })
                        else {
                            add!(@left root);
                            root = child;
                            break Ordering::Less;
                        };
                        Spec::top_down(grandchild.borrow_datamut());
                        let child_left = unsafe { child.borrow_mut().left_mut().take() };
                        if let Some(child_left) = child_left {
                            unsafe { root.borrow_mut().right_mut().set(child_left) };
                        }
                        Spec::bottom_up(root.borrow_datamut());
                        unsafe { child.borrow_mut().left_mut().set(root) };
                        add!(@left child);
                        root = grandchild;
                    }
                }
            }
        }
    };

    *left_entry = unsafe { root.borrow_mut().left_mut().take() }.map(|node| node.node);
    *right_entry = unsafe { root.borrow_mut().right_mut().take() }.map(|node| node.node);
    unsafe {
        root.node.as_mut().child[0] = left_subtree;
        root.node.as_mut().child[1] = right_subtree;
        while let Some(node) = overflow_stack.pop() {
            Spec::bottom_up(BstRoot::new(node).borrow_datamut());
        }
        while inline_len > 0 {
            inline_len -= 1;
            let node = inline_stack[inline_len].unwrap_unchecked();
            Spec::bottom_up(BstRoot::new(node).borrow_datamut());
        }
    }
    Spec::bottom_up(root.borrow_datamut());
    (root_ordering, root)
}

#[inline]
pub fn merge<Spec, Data>(
    left: Option<BstRoot<Spec>>,
    right: Option<BstRoot<Spec>>,
) -> Option<BstRoot<Spec>>
where
    Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
{
    match (left, right) {
        (None, None) => None,
        (None, Some(root)) | (Some(root), None) => Some(root),
        (Some(left), Some(mut right)) if right.reborrow().left().descend().is_err() => {
            Spec::top_down(right.borrow_datamut());
            unsafe { right.borrow_mut().left_mut().set(left) };
            Spec::bottom_up(right.borrow_datamut());
            Some(right)
        }
        (Some(left), Some(right)) => {
            let (_, mut root) = splay(left, SeekRight::default());
            unsafe { root.borrow_mut().right_mut().set(right) };
            Spec::bottom_up(root.borrow_datamut());
            Some(root)
        }
    }
}

#[inline]
pub fn split<Spec, Data, Seeker>(
    root: Option<BstRoot<Spec>>,
    seeker: Seeker,
    equal_side: EqualSide,
) -> (Option<BstRoot<Spec>>, Option<BstRoot<Spec>>)
where
    Spec: BstSpec<Data = Data, Parent = WithNoParent<Data>>,
    Seeker: BstSeeker<Spec = Spec>,
{
    let Some(root) = root else {
        return (None, None);
    };
    let (ordering, mut root) = splay(root, seeker);
    if equal_side.goes_left(ordering) {
        let right = unsafe { root.borrow_mut().right_mut().take() };
        Spec::bottom_up(root.borrow_datamut());
        (Some(root), right)
    } else {
        let left = unsafe { root.borrow_mut().left_mut().take() };
        Spec::bottom_up(root.borrow_datamut());
        (left, Some(root))
    }
}

Additional examples can be found in:

• crates/competitive/src/data_structure/treap.rs
• crates/competitive/src/data_structure/splay_tree.rs

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors

impl<K, V> BstSpec for SplayTreeSpec<K, V>

type Parent = WithNoParent<<SplayTreeSpec<K, V> as BstSpec>::Data>

type Data = SplayTreeData<K, V>

impl<M, L> BstSpec for TreapSpec<M, L>

where M: MonoidAct<Key: Ord>, L: LazyMapMonoid,

type Parent = WithParent<<TreapSpec<M, L> as BstSpec>::Data>

type Data = TreapData<M, L>

impl<S, A> BstSpec for RakeBstSpec<S, A>

where S: TopTreeSpec, A: TopTreeAction<S>,

type Parent = WithParent<<RakeBstSpec<S, A> as BstSpec>::Data>

type Data = RakeData<S, A>

impl<S, A> BstSpec for TopBstSpec<S, A>

where S: TopTreeSpec, A: TopTreeAction<S>,

type Parent = WithParent<<TopBstSpec<S, A> as BstSpec>::Data>

type Data = TopTreeData<S, A>

impl<S> BstSpec for LinkCutBstSpec<S>

where S: LinkCutTreeSpec,

type Parent = WithParent<<LinkCutBstSpec<S> as BstSpec>::Data>

type Data = LinkCutData<S>

impl<T> BstSpec for ImplicitSplayTreeSpec<T>

where T: LazyMapMonoid,

type Parent = WithNoParent<<ImplicitSplayTreeSpec<T> as BstSpec>::Data>

type Data = ImplicitSplayTreeData<T>

impl<T> BstSpec for ImplicitTreapSpec<T>

where T: LazyMapMonoid,

type Parent = WithNoParent<<ImplicitTreapSpec<T> as BstSpec>::Data>

type Data = ImplicitTreapData<T>