Struct RakeBstSpec 

struct RakeBstSpec<S, A>(PhantomData<fn() -> (S, A)>);

Tuple Fields

0: PhantomData<fn() -> (S, A)>

Implementations

impl<S, A> RakeBstSpec<S, A>

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

unsafe fn apply( node: NonNull<BstNode<RakeData<S, A>, WithParent<RakeData<S, A>>>>, action: &A::Action, )

Examples found in repository

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

    fn top_down(mut node: BstDataMutRef<'_, Self>) {
        let pointer = node.node;
        if node.reborrow().into_data().index_and_reverse & 1 != 0 {
            node.data_mut().index_and_reverse &= !1;
            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
                unsafe { Self::toggle(child) };
            }
        }

        if !Self::is_unit(&node.reborrow().into_data().heavy_action) {
            let action = replace(
                &mut node.data_mut().heavy_action,
                <A::ActionMonoid as Unital>::unit(),
            );
            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
                unsafe { Self::apply_heavy(child, &action) };
            }
        }
        if !Self::is_unit(&node.reborrow().into_data().light_action) {
            let action = replace(
                &mut node.data_mut().light_action,
                <A::ActionMonoid as Unital>::unit(),
            );
            for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
                unsafe { Self::apply_light(child, &action) };
            }
            if let Some(light) = node.reborrow().into_data().light {
                unsafe { RakeBstSpec::<S, A>::apply(light, &action) };
            }
        }
    }

    #[inline]
    fn bottom_up(node: BstDataMutRef<'_, Self>) {
        let pointer = node.node;
        let data = unsafe { &mut (*pointer.as_ptr()).data };
        let mut sum = if let Some(light) = data.light {
            S::add_vertex(unsafe { &light.as_ref().data.sum }, &data.info)
        } else {
            S::vertex(&data.info)
        };
        if let Some(left) = unsafe { pointer.as_ref().child[0] } {
            sum = S::compress(unsafe { &left.as_ref().data.sum }, &sum);
        }
        if let Some(right) = unsafe { pointer.as_ref().child[1] } {
            sum = S::compress(&sum, unsafe { &right.as_ref().data.sum });
        }
        data.sum = sum;
    }

    fn merge(_left: Option<BstRoot<Self>>, _right: Option<BstRoot<Self>>) -> Option<BstRoot<Self>> {
        unreachable!("top trees do not merge auxiliary trees through BstSpec")
    }

    fn split<Seeker>(
        _node: Option<BstRoot<Self>>,
        _seeker: Seeker,
        _equal_side: EqualSide,
    ) -> (Option<BstRoot<Self>>, Option<BstRoot<Self>>)
    where
        Seeker: BstSeeker<Spec = Self>,
    {
        unreachable!("top trees do not split auxiliary trees through BstSpec")
    }
}

impl<S, A> RakeBstSpec<S, A>
where
    S: TopTreeSpec,
    A: TopTreeAction<S>,
{
    #[inline]
    unsafe fn apply(mut node: RakePtr<S, A>, action: &A::Action) {
        let data = unsafe { &mut node.as_mut().data };
        A::act_point(&mut data.key, action);
        A::act_point(&mut data.sum, action);
        TopBstSpec::<S, A>::compose(&mut data.action, action);
        TopBstSpec::<S, A>::compose(&mut data.buffer, action);
    }
}

impl<S, A> BstSpec for RakeBstSpec<S, A>
where
    S: TopTreeSpec,
    A: TopTreeAction<S>,
{
    type Parent = WithParent<Self::Data>;
    type Data = RakeData<S, A>;

    #[inline]
    fn top_down(mut node: BstDataMutRef<'_, Self>) {
        if TopBstSpec::<S, A>::is_unit(&node.reborrow().into_data().action) {
            return;
        }
        let pointer = node.node;
        let action = replace(
            &mut node.data_mut().action,
            <A::ActionMonoid as Unital>::unit(),
        );
        for child in unsafe { pointer.as_ref().child }.into_iter().flatten() {
            unsafe { Self::apply(child, &action) };
        }
    }

Trait Implementations

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>

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

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

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