Trait LinkCutTreeSpec

Source

pub trait LinkCutTreeSpec: Sized {
    type Value;
    type Data;

    const ROOT_TO_NODE_TOP_DOWN: bool = true;
    const MODIFY_REQUIRES_ACCESS: bool = true;

    // Required methods
    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 bottom_up(data: &mut Self::Data, children: [Option<&Self::Data>; 2]);
    fn reverse(data: &mut Self::Data);

    // Provided methods
    fn top_down(_data: &mut Self::Data, _children: [Option<&mut Self::Data>; 2]) { ... }
    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,
    ) { ... }
}

Provided Associated Constants§

Source

const ROOT_TO_NODE_TOP_DOWN: bool = true

Whether splay must propagate from the auxiliary root before rotations.

Source

const MODIFY_REQUIRES_ACCESS: bool = true

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

Required Associated Types§

Source

type Value

Source

type Data

Required Methods§

Source

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

Provided Methods§

Source

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

Examples found in repository ?

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

99    fn top_down(mut node: BstDataMutRef<'_, Self>) {
100        let pointer = node.node;
101        if node.reborrow().into_data().index_and_reverse & 1 != 0 {
102            node.data_mut().index_and_reverse &= !1;
103            let children = unsafe { pointer.as_ref().child };
104            for child in children.into_iter().flatten() {
105                unsafe { Self::toggle(child) };
106            }
107        }
108        let children = unsafe { pointer.as_ref().child };
109        let data = unsafe { &mut (*pointer.as_ptr()).data.inner };
110        let children =
111            children.map(|child| child.map(|child| unsafe { &mut (*child.as_ptr()).data.inner }));
112        S::top_down(data, children);
113    }