Struct Node 

struct Node<M>
where
    M: LazyMapMonoid,
{
    child: [usize; 2],
    parent: usize,
    agg: M::Agg,
    lazy: M::Act,
}

Fields

child: [usize; 2]

parent: usize

agg: M::Agg

lazy: M::Act

Implementations

impl<M> Node<M>

where M: LazyMapMonoid,

fn new(parent: usize) -> Self

Examples found in repository

crates/competitive/src/data_structure/binary_trie.rs (line 62)

    pub fn with_capacity(bit_len: usize, capacity: usize) -> Self {
        assert!(bit_len <= 64);
        let max_key = if bit_len == 64 {
            u64::MAX
        } else {
            (1u64 << bit_len) - 1
        };
        let mut nodes = Vec::with_capacity(
            capacity
                .saturating_mul(bit_len.saturating_add(1))
                .saturating_add(1),
        );
        nodes.push(Node::new(usize::MAX));
        Self {
            bit_len,
            max_key,
            len: 0,
            xor_mask: 0,
            nodes,
        }
    }

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

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

    pub fn clear(&mut self) {
        self.len = 0;
        self.xor_mask = 0;
        self.nodes.clear();
        self.nodes.push(Node::new(usize::MAX));
    }

    pub fn set(&mut self, key: u64, value: M::Agg) {
        self.modify_or_insert(key, |x| *x = value);
    }

    pub fn modify_or_insert(&mut self, key: u64, f: impl FnOnce(&mut M::Agg)) {
        assert!(key <= self.max_key);
        if self.bit_len == 0 {
            if self.is_empty() {
                self.len = 1;
            }
            f(&mut self.nodes[0].agg);
            return;
        }

        let key = key ^ self.xor_mask;
        let mut inserted = false;
        let mut node = 0;
        for d in (0..self.bit_len).rev() {
            self.push_at(node, d + 1);
            let bit = ((key >> d) & 1) as usize;
            if self.nodes[node].child[bit] == usize::MAX {
                inserted = true;
                let next = self.nodes.len();
                self.nodes[node].child[bit] = next;
                self.nodes.push(Node::new(node));
            }
            node = self.nodes[node].child[bit];
        }

        if inserted {
            self.len += 1;
        }
        self.nodes[node].lazy = M::act_unit();
        f(&mut self.nodes[node].agg);
        self.recalc_up(node);
    }