Module veb_tree 

Cache-oblivious van Emde Boas tree layout for widget traversal (bd-xwkon).

Flattens a logical tree into a contiguous Vec using the recursive van Emde Boas (vEB) memory layout. This ensures O(log_B(n)) cache misses per root-to-leaf traversal for any cache line size B, without knowing B at compile time.

Overview

A standard BFS or DFS layout puts sibling nodes far apart in memory for deep trees. The vEB layout recursively stores the top half of the tree followed by each bottom subtree, keeping ancestors and descendants close together in memory.

Usage

use ftui_layout::veb_tree::{VebTree, TreeNode};

// Build a small tree: root with two children
let nodes = vec![
    TreeNode::new(0, "root", vec![1, 2]),
    TreeNode::new(1, "left", vec![]),
    TreeNode::new(2, "right", vec![]),
];
let tree = VebTree::build(nodes);
assert_eq!(tree.len(), 3);
assert_eq!(tree.get(0).unwrap().data, "root");

Structs

TreeNode

A node in the logical tree before vEB layout.

VebEntry

A node stored in the vEB-laid-out flat array.

VebTree

A tree stored in van Emde Boas memory layout for cache-oblivious traversal.