crate::ix!();
impl TreeDepthMeasurer for Skeleton {
fn measure_tree_depth(&self) -> u8 {
trace!("Computing skeleton depth using BFS/DFS approach with cycle detection.");
let root_id = match self.root_id() {
Some(rid) => rid,
None => {
trace!("No root_id found => depth=0");
return 0;
}
};
let root_node = match self.nodes().iter().find(|n| n.id() == *root_id) {
Some(r) => r,
None => {
trace!("root_id is invalid => depth=0");
return 0;
}
};
use std::collections::HashSet;
let mut visited = HashSet::new();
let mut stack = vec![(root_node.id(), 1u8)];
let mut max_depth = 1;
let index_of = |id: u16| -> Option<usize> {
self.nodes().iter().position(|n| n.id() == id)
};
while let Some((nid, lvl)) = stack.pop() {
if !visited.insert(nid) {
trace!("Node {} already visited => skipping", nid);
continue;
}
if lvl > max_depth {
max_depth = lvl;
}
let node_idx = match index_of(nid) {
Some(idx) => idx,
None => {
trace!("Node {} not found => skipping children", nid);
continue;
}
};
let node = &self.nodes()[node_idx];
for &child_id in node.child_ids() {
let next_level = match lvl.checked_add(1) {
Some(l) => l,
None => {
trace!("Overflow in level => capping at 255");
return 255;
}
};
stack.push((child_id, next_level));
}
}
max_depth
}
}
#[cfg(test)]
mod skeleton_depth_measurer_assessment {
use super::*;
#[traced_test]
fn check_empty_skeleton_produces_depth_zero() {
trace!("Creating an empty Skeleton (no nodes)...");
let skel = SkeletonBuilder::default()
.build()
.expect("Should build empty Skeleton");
trace!("Measuring tree depth on the empty Skeleton...");
let depth = skel.measure_tree_depth();
info!("Measured depth: {}", depth);
assert_eq!(depth, 0, "Depth should be 0 for an empty Skeleton");
}
#[traced_test]
fn check_linear_chain_skeleton_produces_correct_depth() {
trace!("Constructing a simple linear chain: 0 -> 1 -> 2 => depth=3");
let n0 = SkeletonNodeBuilder::default()
.id(0_u16)
.child_ids(vec![1_u16])
.name("root")
.original_key("root")
.build(NodeKind::Dispatch)
.unwrap();
let n1 = SkeletonNodeBuilder::default()
.id(1_u16)
.child_ids(vec![2_u16])
.name("child")
.original_key("child")
.build(NodeKind::Dispatch)
.unwrap();
let n2 = SkeletonNodeBuilder::default()
.id(2_u16)
.name("grandchild")
.original_key("grandchild")
.build(NodeKind::LeafHolder)
.unwrap();
let skel = SkeletonBuilder::default()
.nodes(vec![n0, n1, n2])
.root_id(Some(0_u16))
.build()
.unwrap();
trace!("Measuring depth...");
let depth = skel.measure_tree_depth();
info!("Measured depth: {}", depth);
assert_eq!(depth, 3, "Expected depth=3 in a linear chain of three nodes");
}
#[traced_test]
fn test_compute_skeleton_depth() {
let root = SkeletonNodeBuilder::default()
.id(0_u16)
.child_ids(vec![1])
.name("root")
.original_key("root")
.build(NodeKind::Dispatch)
.unwrap();
let child = SkeletonNodeBuilder::default()
.id(1_u16)
.child_ids(vec![2])
.name("child")
.original_key("child")
.build(NodeKind::Dispatch)
.unwrap();
let grandchild = SkeletonNodeBuilder::default()
.id(2_u16)
.name("grandchild")
.original_key("grandchild")
.build(NodeKind::LeafHolder)
.unwrap();
let skeleton = SkeletonBuilder::default()
.nodes(vec![root, child, grandchild])
.root_id(Some(0))
.build()
.unwrap();
let depth = skeleton.measure_tree_depth();
assert_eq!(depth, 3, "Expect depth=3");
}
fn make_node(
id: u16,
parent_id: Option<u16>,
child_ids: &[u16],
leaf_count: u16,
name: &str
) -> SkeletonNode {
let k = if child_ids.is_empty() {
NodeKind::LeafHolder
} else {
NodeKind::Dispatch
};
SkeletonNodeBuilder::default()
.id(id)
.parent_id(parent_id)
.child_ids(child_ids.to_vec())
.leaf_count(leaf_count)
.name(name.to_string())
.original_key(name.to_string())
.build(k)
.unwrap()
}
fn make_skeleton(nodes: Vec<SkeletonNode>, root_id: Option<u16>) -> Skeleton {
SkeletonBuilder::default()
.nodes(nodes)
.root_id(root_id)
.build()
.unwrap()
}
#[traced_test]
fn test_depth_no_nodes() {
let skeleton = make_skeleton(vec![], None);
let depth = skeleton.measure_tree_depth();
assert_eq!(depth, 0, "No nodes => depth=0");
}
#[traced_test]
fn test_depth_no_root_id() {
let n1 = make_node(1, None, &[], 0, "n1");
let skeleton = make_skeleton(vec![n1], None);
let depth = skeleton.measure_tree_depth();
assert_eq!(depth, 0, "Missing root_id => depth=0");
}
#[traced_test]
fn test_depth_invalid_root_id() {
let n0 = make_node(0, None, &[], 0, "RootButNotActuallyUsed");
let skeleton = make_skeleton(vec![n0], Some(999));
let depth = skeleton.measure_tree_depth();
assert_eq!(depth, 0, "Invalid root => depth=0");
}
#[traced_test]
fn test_depth_single_node() {
let root_node = make_node(10, None, &[], 0, "SingleNode");
let skeleton = make_skeleton(vec![root_node], Some(10));
let depth = skeleton.measure_tree_depth();
assert_eq!(depth, 1, "A single root node => depth=1");
}
#[traced_test]
fn test_depth_linear_chain_three() {
let root = make_node(0, None, &[1], 0, "root");
let child = make_node(1, Some(0), &[2], 0, "child");
let grandchild = make_node(2, Some(1), &[], 0, "grandchild");
let skeleton = make_skeleton(vec![root, child, grandchild], Some(0));
let depth = skeleton.measure_tree_depth();
assert_eq!(depth, 3, "Expect depth=3 for linear chain root->child->grandchild");
}
#[traced_test]
fn test_depth_multiple_branches() {
let n0 = make_node(0, None, &[1,2], 0, "root");
let n1 = make_node(1, Some(0), &[3], 0, "branchA");
let n2 = make_node(2, Some(0), &[4,5], 0, "branchB");
let n3 = make_node(3, Some(1), &[], 0, "leafA");
let n4 = make_node(4, Some(2), &[6], 0, "midNode");
let n5 = make_node(5, Some(2), &[], 0, "leafB");
let n6 = make_node(6, Some(4), &[], 0, "deepLeafC");
let skeleton = make_skeleton(vec![n0,n1,n2,n3,n4,n5,n6], Some(0));
let depth = skeleton.measure_tree_depth();
assert_eq!(depth, 4, "Deepest path is root->2->4->6 => 4 levels");
}
#[traced_test]
fn test_depth_with_cycle() {
let n0 = make_node(0, None, &[1], 0, "root");
let n1 = make_node(1, Some(0), &[0], 0, "childWithCycle");
let skeleton = make_skeleton(vec![n0, n1], Some(0));
let depth = skeleton.measure_tree_depth();
eprintln!("Depth with cycle => {}", depth);
assert!(depth > 0, "At least root => depth≥1 in cyc case if we break");
}
#[traced_test]
fn test_depth_with_invalid_child_id() {
let root = make_node(0, None, &[1,999], 0, "root");
let child = make_node(1, Some(0), &[], 0, "validChild");
let skeleton = make_skeleton(vec![root, child], Some(0));
let depth = skeleton.measure_tree_depth();
assert_eq!(depth, 2, "root->child => depth=2, ignoring child=999");
}
#[traced_test]
fn test_depth_with_leaf_count() {
let root = SkeletonNodeBuilder::default()
.id(0_u16)
.child_ids(vec![1])
.leaf_count(5_u16)
.name("root")
.original_key("root")
.build(NodeKind::Dispatch)
.unwrap();
let child = SkeletonNodeBuilder::default()
.id(1_u16)
.leaf_count(3_u16)
.name("child")
.original_key("child")
.build(NodeKind::LeafHolder)
.unwrap();
let skeleton = SkeletonBuilder::default()
.nodes(vec![root, child])
.root_id(Some(0))
.build()
.unwrap();
let depth = skeleton.measure_tree_depth();
assert_eq!(depth, 2, "leaf_count is irrelevant to structural BFS => depth=2");
}
#[traced_test]
fn test_depth_multi_root_scenario() {
let n0 = make_node(0, None, &[], 0, "primaryRoot");
let n10 = make_node(10, None, &[], 0, "secondaryRootIgnored");
let skeleton = make_skeleton(vec![n0, n10], Some(0));
let depth = skeleton.measure_tree_depth();
assert_eq!(depth, 1, "We only measure from root_id=0 => ignoring node(10) as root");
}
#[traced_test]
fn check_branching_skeleton_produces_correct_depth() {
let root_node = SkeletonNodeBuilder::default()
.id(0_u16)
.child_ids(vec![1, 2])
.name("root")
.original_key("root")
.build(NodeKind::Dispatch)
.unwrap();
let child_a = SkeletonNodeBuilder::default()
.id(1_u16)
.child_ids(vec![3])
.name("childA")
.original_key("childA")
.build(NodeKind::Dispatch)
.unwrap();
let child_b = SkeletonNodeBuilder::default()
.id(2_u16)
.name("childB")
.original_key("childB")
.build(NodeKind::LeafHolder)
.unwrap();
let grandchild = SkeletonNodeBuilder::default()
.id(3_u16)
.name("grandchild")
.original_key("grandchild")
.build(NodeKind::LeafHolder)
.unwrap();
let skel = SkeletonBuilder::default()
.nodes(vec![root_node, child_a, child_b, grandchild])
.root_id(Some(0))
.build()
.unwrap();
let depth = skel.measure_tree_depth();
debug!("Measured depth: {}", depth);
assert_eq!(depth, 3, "root -> childA -> grandchild => 3 levels deep");
}
}