Struct PathLinkCutTreeSpec 

pub struct PathLinkCutTreeSpec<L>(PhantomData<fn() -> L>);

Tuple Fields

0: PhantomData<fn() -> L>

Implementations

impl<L> PathLinkCutTreeSpec<L>

where L: LazyMapMonoid,

fn apply_non_unit(data: &mut PathLinkCutTreeData<L>, action: &L::Act)

Examples found in repository

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

    fn top_down(data: &mut Self::Data, children: [Option<&mut Self::Data>; 2]) {
        if L::is_act_unit(&data.value.act) {
            return;
        }
        let action = replace(&mut data.value.act, L::act_unit());
        for child in children.into_iter().flatten() {
            Self::apply_non_unit(child, &action);
        }
    }

    fn bottom_up(data: &mut Self::Data, children: [Option<&Self::Data>; 2]) {
        let mut aggregate = L::single_agg(&data.value.key);
        if let Some(left) = children[0] {
            aggregate = L::agg_operate(&left.value.agg, &aggregate);
        }
        if let Some(right) = children[1] {
            aggregate = L::agg_operate(&aggregate, &right.value.agg);
        }
        data.value.agg = aggregate;
    }

    fn reverse(data: &mut Self::Data) {
        L::toggle(&mut data.value.agg);
    }
}

impl<L> LinkCutTreePathFold for PathLinkCutTreeSpec<L>
where
    L: LazyMapMonoid,
{
    type Path = L::Agg;

    fn fold_path(data: &Self::Data) -> Self::Path {
        data.value.agg.clone()
    }
}

impl<L> LinkCutTreePathUpdate for PathLinkCutTreeSpec<L>
where
    L: LazyMapMonoid,
{
    type PathAction = L::Act;

    fn update_path(data: &mut Self::Data, action: &Self::PathAction) {
        if !L::is_act_unit(action) {
            Self::apply_non_unit(data, action);
        }
    }

Trait Implementations

impl<L> LinkCutTreePathFold for PathLinkCutTreeSpec<L>

where L: LazyMapMonoid,

type Path = <L as LazyMapMonoid>::Agg

fn fold_path(data: &Self::Data) -> Self::Path

impl<L> LinkCutTreePathUpdate for PathLinkCutTreeSpec<L>

where L: LazyMapMonoid,

type PathAction = <L as LazyMapMonoid>::Act

fn update_path(data: &mut Self::Data, action: &Self::PathAction)

impl<L> LinkCutTreeSpec for PathLinkCutTreeSpec<L>

where L: LazyMapMonoid,

const ROOT_TO_NODE_TOP_DOWN: bool = false

Whether splay must propagate from the auxiliary root before rotations.

const MODIFY_REQUIRES_ACCESS: bool = false

Whether modify must expose the node to update virtual subtree state.

type Value = <L as LazyMapMonoid>::Key

type Data = PathLinkCutTreeData<L>

fn new(value: Self::Value) -> Self::Data

fn value(data: &Self::Data) -> &Self::Value

fn value_mut(data: &mut Self::Data) -> &mut Self::Value

fn top_down(data: &mut Self::Data, children: [Option<&mut Self::Data>; 2])

fn bottom_up(data: &mut Self::Data, children: [Option<&Self::Data>; 2])

fn reverse(data: &mut Self::Data)

fn attach_virtual(_parent: &mut Self::Data, _child: &mut Self::Data)

fn detach_virtual(_parent: &mut Self::Data, _child: &mut Self::Data)

fn transfer_path_parent(_old_root: &mut Self::Data, _new_root: &mut Self::Data)

Moves state associated with the same path-parent edge after a splay.