capability_skeleton/
tree_depth_measurer.rs

1// ---------------- [ File: capability-skeleton/src/tree_depth_measurer.rs ]
2crate::ix!();
3
4impl TreeDepthMeasurer for Skeleton {
5    fn measure_tree_depth(&self) -> u8 {
6        trace!("Computing skeleton depth using BFS/DFS approach with cycle detection.");
7
8        let root_id = match self.root_id() {
9            Some(rid) => rid,
10            None => {
11                trace!("No root_id found => depth=0");
12                return 0;
13            }
14        };
15
16        // We find the actual root node:
17        let root_node = match self.nodes().iter().find(|n| n.id() == *root_id) {
18            Some(r) => r,
19            None => {
20                trace!("root_id is invalid => depth=0");
21                return 0;
22            }
23        };
24
25        use std::collections::HashSet;
26        let mut visited = HashSet::new();
27
28        let mut stack = vec![(root_node.id(), 1u8)];
29        let mut max_depth = 1;
30
31        let index_of = |id: u16| -> Option<usize> {
32            self.nodes().iter().position(|n| n.id() == id)
33        };
34
35        while let Some((nid, lvl)) = stack.pop() {
36            if !visited.insert(nid) {
37                trace!("Node {} already visited => skipping", nid);
38                continue;
39            }
40            if lvl > max_depth {
41                max_depth = lvl;
42            }
43            let node_idx = match index_of(nid) {
44                Some(idx) => idx,
45                None => {
46                    trace!("Node {} not found => skipping children", nid);
47                    continue;
48                }
49            };
50            let node = &self.nodes()[node_idx];
51
52            for &child_id in node.child_ids() {
53                let next_level = match lvl.checked_add(1) {
54                    Some(l) => l,
55                    None => {
56                        trace!("Overflow in level => capping at 255");
57                        return 255;
58                    }
59                };
60                stack.push((child_id, next_level));
61            }
62        }
63
64        max_depth
65    }
66}
67
68#[cfg(test)]
69mod skeleton_depth_measurer_assessment {
70    use super::*;
71
72    #[traced_test]
73    fn check_empty_skeleton_produces_depth_zero() {
74        trace!("Creating an empty Skeleton (no nodes)...");
75        let skel = SkeletonBuilder::default()
76            .build()
77            .expect("Should build empty Skeleton");
78
79        trace!("Measuring tree depth on the empty Skeleton...");
80        let depth = skel.measure_tree_depth();
81        info!("Measured depth: {}", depth);
82
83        assert_eq!(depth, 0, "Depth should be 0 for an empty Skeleton");
84    }
85
86    #[traced_test]
87    fn check_linear_chain_skeleton_produces_correct_depth() {
88        trace!("Constructing a simple linear chain: 0 -> 1 -> 2 => depth=3");
89
90        let n0 = SkeletonNodeBuilder::default()
91            .id(0_u16)
92            .child_ids(vec![1_u16])
93            .name("root")
94            .original_key("root")
95            .build(NodeKind::Dispatch)
96            .unwrap();
97        let n1 = SkeletonNodeBuilder::default()
98            .id(1_u16)
99            .child_ids(vec![2_u16])
100            .name("child")
101            .original_key("child")
102            .build(NodeKind::Dispatch)
103            .unwrap();
104        let n2 = SkeletonNodeBuilder::default()
105            .id(2_u16)
106            .name("grandchild")
107            .original_key("grandchild")
108            .build(NodeKind::LeafHolder)
109            .unwrap();
110
111        let skel = SkeletonBuilder::default()
112            .nodes(vec![n0, n1, n2])
113            .root_id(Some(0_u16))
114            .build()
115            .unwrap();
116
117        trace!("Measuring depth...");
118        let depth = skel.measure_tree_depth();
119        info!("Measured depth: {}", depth);
120
121        assert_eq!(depth, 3, "Expected depth=3 in a linear chain of three nodes");
122    }
123
124    #[traced_test]
125    fn test_compute_skeleton_depth() {
126        // Simple example: root( id=0 ) -> child(1 ) -> grandchild(2 ) => depth=3
127        let root = SkeletonNodeBuilder::default()
128            .id(0_u16)
129            .child_ids(vec![1])
130            .name("root")
131            .original_key("root")
132            .build(NodeKind::Dispatch)
133            .unwrap();
134
135        let child = SkeletonNodeBuilder::default()
136            .id(1_u16)
137            .child_ids(vec![2])
138            .name("child")
139            .original_key("child")
140            .build(NodeKind::Dispatch)
141            .unwrap();
142
143        let grandchild = SkeletonNodeBuilder::default()
144            .id(2_u16)
145            .name("grandchild")
146            .original_key("grandchild")
147            .build(NodeKind::LeafHolder)
148            .unwrap();
149
150        let skeleton = SkeletonBuilder::default()
151            .nodes(vec![root, child, grandchild])
152            .root_id(Some(0))
153            .build()
154            .unwrap();
155
156        let depth = skeleton.measure_tree_depth();
157        assert_eq!(depth, 3, "Expect depth=3");
158    }
159
160    /// Helper to create a SkeletonNode with minimal syntax.
161    /// e.g., `make_node(10, Some(5), &[11,12], 2, "my node")`
162    fn make_node(
163        id: u16,
164        parent_id: Option<u16>,
165        child_ids: &[u16],
166        leaf_count: u16,
167        name: &str
168    ) -> SkeletonNode {
169        // We pick NodeKind based on whether child_ids is empty
170        let k = if child_ids.is_empty() {
171            NodeKind::LeafHolder
172        } else {
173            NodeKind::Dispatch
174        };
175        SkeletonNodeBuilder::default()
176            .id(id)
177            .parent_id(parent_id)
178            .child_ids(child_ids.to_vec())
179            .leaf_count(leaf_count)
180            .name(name.to_string())
181            .original_key(name.to_string())
182            .build(k)
183            .unwrap()
184    }
185
186    fn make_skeleton(nodes: Vec<SkeletonNode>, root_id: Option<u16>) -> Skeleton {
187        SkeletonBuilder::default()
188            .nodes(nodes)
189            .root_id(root_id)
190            .build()
191            .unwrap()
192    }
193
194    #[traced_test]
195    fn test_depth_no_nodes() {
196        let skeleton = make_skeleton(vec![], None);
197        let depth = skeleton.measure_tree_depth();
198        assert_eq!(depth, 0, "No nodes => depth=0");
199    }
200
201    #[traced_test]
202    fn test_depth_no_root_id() {
203        // no root => depth=0
204        let n1 = make_node(1, None, &[], 0, "n1");
205        let skeleton = make_skeleton(vec![n1], None);
206        let depth = skeleton.measure_tree_depth();
207        assert_eq!(depth, 0, "Missing root_id => depth=0");
208    }
209
210    #[traced_test]
211    fn test_depth_invalid_root_id() {
212        let n0 = make_node(0, None, &[], 0, "RootButNotActuallyUsed");
213        let skeleton = make_skeleton(vec![n0], Some(999));
214        let depth = skeleton.measure_tree_depth();
215        assert_eq!(depth, 0, "Invalid root => depth=0");
216    }
217
218    #[traced_test]
219    fn test_depth_single_node() {
220        let root_node = make_node(10, None, &[], 0, "SingleNode");
221        let skeleton = make_skeleton(vec![root_node], Some(10));
222        let depth = skeleton.measure_tree_depth();
223        assert_eq!(depth, 1, "A single root node => depth=1");
224    }
225
226    #[traced_test]
227    fn test_depth_linear_chain_three() {
228        let root = make_node(0, None, &[1], 0, "root");
229        let child = make_node(1, Some(0), &[2], 0, "child");
230        let grandchild = make_node(2, Some(1), &[], 0, "grandchild");
231
232        let skeleton = make_skeleton(vec![root, child, grandchild], Some(0));
233        let depth = skeleton.measure_tree_depth();
234        assert_eq!(depth, 3, "Expect depth=3 for linear chain root->child->grandchild");
235    }
236
237    #[traced_test]
238    fn test_depth_multiple_branches() {
239        // root(0)->[1,2], 1->[3], 2->[4,5], 3->[], 4->[6], 5->[], 6->[]
240
241        let n0 = make_node(0, None, &[1,2], 0, "root");
242        let n1 = make_node(1, Some(0), &[3], 0, "branchA");
243        let n2 = make_node(2, Some(0), &[4,5], 0, "branchB");
244        let n3 = make_node(3, Some(1), &[], 0, "leafA");
245        let n4 = make_node(4, Some(2), &[6], 0, "midNode");
246        let n5 = make_node(5, Some(2), &[], 0, "leafB");
247        let n6 = make_node(6, Some(4), &[], 0, "deepLeafC");
248
249        let skeleton = make_skeleton(vec![n0,n1,n2,n3,n4,n5,n6], Some(0));
250        let depth = skeleton.measure_tree_depth();
251        assert_eq!(depth, 4, "Deepest path is root->2->4->6 => 4 levels");
252    }
253
254    #[traced_test]
255    fn test_depth_with_cycle() {
256        // root(0)->[1], node(1)->[0]
257        let n0 = make_node(0, None, &[1], 0, "root");
258        let n1 = make_node(1, Some(0), &[0], 0, "childWithCycle");
259
260        let skeleton = make_skeleton(vec![n0, n1], Some(0));
261        let depth = skeleton.measure_tree_depth();
262        eprintln!("Depth with cycle => {}", depth);
263        assert!(depth > 0, "At least root => depth≥1 in cyc case if we break");
264    }
265
266    #[traced_test]
267    fn test_depth_with_invalid_child_id() {
268        let root = make_node(0, None, &[1,999], 0, "root");
269        let child = make_node(1, Some(0), &[], 0, "validChild");
270        let skeleton = make_skeleton(vec![root, child], Some(0));
271        let depth = skeleton.measure_tree_depth();
272        assert_eq!(depth, 2, "root->child => depth=2, ignoring child=999");
273    }
274
275    #[traced_test]
276    fn test_depth_with_leaf_count() {
277        let root = SkeletonNodeBuilder::default()
278            .id(0_u16)
279            .child_ids(vec![1])
280            .leaf_count(5_u16)
281            .name("root")
282            .original_key("root")
283            .build(NodeKind::Dispatch)
284            .unwrap();
285        let child = SkeletonNodeBuilder::default()
286            .id(1_u16)
287            .leaf_count(3_u16)
288            .name("child")
289            .original_key("child")
290            .build(NodeKind::LeafHolder)
291            .unwrap();
292
293        let skeleton = SkeletonBuilder::default()
294            .nodes(vec![root, child])
295            .root_id(Some(0))
296            .build()
297            .unwrap();
298
299        let depth = skeleton.measure_tree_depth();
300        assert_eq!(depth, 2, "leaf_count is irrelevant to structural BFS => depth=2");
301    }
302
303    #[traced_test]
304    fn test_depth_multi_root_scenario() {
305        let n0 = make_node(0, None, &[], 0, "primaryRoot");
306        let n10 = make_node(10, None, &[], 0, "secondaryRootIgnored");
307        let skeleton = make_skeleton(vec![n0, n10], Some(0));
308        let depth = skeleton.measure_tree_depth();
309        assert_eq!(depth, 1, "We only measure from root_id=0 => ignoring node(10) as root");
310    }
311
312    #[traced_test]
313    fn check_branching_skeleton_produces_correct_depth() {
314        // root -> [childA, childB], childA->[grandchild], childB->[], grandchild->[]
315        let root_node = SkeletonNodeBuilder::default()
316            .id(0_u16)
317            .child_ids(vec![1, 2])
318            .name("root")
319            .original_key("root")
320            .build(NodeKind::Dispatch)
321            .unwrap();
322        let child_a = SkeletonNodeBuilder::default()
323            .id(1_u16)
324            .child_ids(vec![3])
325            .name("childA")
326            .original_key("childA")
327            .build(NodeKind::Dispatch)
328            .unwrap();
329        let child_b = SkeletonNodeBuilder::default()
330            .id(2_u16)
331            .name("childB")
332            .original_key("childB")
333            .build(NodeKind::LeafHolder)
334            .unwrap();
335        let grandchild = SkeletonNodeBuilder::default()
336            .id(3_u16)
337            .name("grandchild")
338            .original_key("grandchild")
339            .build(NodeKind::LeafHolder)
340            .unwrap();
341
342        let skel = SkeletonBuilder::default()
343            .nodes(vec![root_node, child_a, child_b, grandchild])
344            .root_id(Some(0))
345            .build()
346            .unwrap();
347
348        let depth = skel.measure_tree_depth();
349        debug!("Measured depth: {}", depth);
350        assert_eq!(depth, 3, "root -> childA -> grandchild => 3 levels deep");
351    }
352}
capability_skeleton/tree_depth_measurer.rs

capability_skeleton/
tree_depth_measurer.rs
