Struct radarbase::binarytree::BinarytreeBuilder

pub(crate) struct BinarytreeBuilder {
    pairs: Vec<(u64, Vec<u8>, Vec<u8>)>,
}

Fields

pairs: Vec<(u64, Vec<u8>, Vec<u8>)>

Implementations

impl BinarytreeBuilder

pub(crate) fn new() -> BinarytreeBuilder

pub(crate) fn add(&mut self, table: u64, key: &[u8], value: &[u8])

pub(crate) fn build<K: RadbKey + ?Sized>(self) -> Node

Builds a balanced binary tree from the provided key-value pairs.

This function operates by first sorting the pairs by key to ensure balance, then constructs the tree by creating leaves from pairs of elements and combining them into internal nodes. If there is an odd number of elements, the last one is handled separately.

The tree is built in a bottom-up manner, i.e., leaves are created first and then internal nodes are created by combining these leaves. This process continues until we have a single node, which is the root of the tree.

A critical part of this function is the maybe_previous_node variable. This variable is used to hold a node from the previous iteration of the loop, effectively serving as a ‘buffer’. This buffering is essential because, for each internal (non-leaf) node, we need two child nodes. However, we’re processing the nodes one at a time. So after processing one node, we store it in maybe_previous_node until we process the next node. After the second node is processed, we can then create an internal node with maybe_previous_node and the second node as its children.

The use of maybe_previous_node is similar to a state machine. After every two nodes are processed, the state is reset (by creating an internal node and clearing maybe_previous_node), and the process starts over for the next pair of nodes. This continues until we only have one node left, which is the root of the tree.

Panics

This function will panic if the pairs vector is empty, as it’s not possible to build a tree without any nodes.

It will also panic in case a duplicate key is encountered during tree building, as it currently does not support overwriting existing keys.

Returns

This function returns the root Node of the constructed tree.