capability-skeleton 0.1.0

// ---------------- [ File: capability-skeleton/src/tree_configuration_complexity_measurer.rs ]
crate::ix!();

impl TreeConfigurationComplexityMeasurer for Skeleton {
    #[instrument(level = "trace", skip(self))]
    fn measure_tree_configuration_complexity(&self) -> Option<DetectedTreeConfigurationComplexity> {
        let nodes = self.nodes();
        let n = nodes.len();
        if n < 2 {
            return None;
        }

        let branching: Vec<&SkeletonNode> = nodes
            .iter()
            .filter(|n| n.child_ids().len() >= 2)
            .collect();

        if branching.is_empty() {
            return Some(DetectedTreeConfigurationComplexity::Linear);
        }

        if branching.len() == 1 {
            let b = branching[0];
            let c = b.child_ids().len();
            if c == n - 1 {
                return Some(DetectedTreeConfigurationComplexity::Star);
            }
        }

        if let Some(sym) = self.measure_tree_balance_symmetry() {
            if (sym - 1.0).abs() < f32::EPSILON {
                return Some(DetectedTreeConfigurationComplexity::Balanced);
            }
        }
        Some(DetectedTreeConfigurationComplexity::Complex)
    }
}

#[cfg(test)]
mod skeleton_configuration_complexity_measurer_assessment {
    use super::*;

    #[traced_test]
    fn empty_skeleton_returns_none() {
        let skel = SkeletonBuilder::default().build().unwrap();
        assert_eq!(skel.measure_tree_configuration_complexity(), None);
    }

    #[traced_test]
    fn single_node_returns_none() {
        let node = SkeletonNodeBuilder::default()
            .id(0_u16)
            .name("solo")
            .original_key("solo")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![node]).root_id(Some(0)).build().unwrap();
        assert_eq!(skel.measure_tree_configuration_complexity(), None);
    }

    #[traced_test]
    fn linear_chain_returns_linear() {
        // 0->1->2
        // We do `.build(NodeKind::Dispatch)` if child_ids is not empty, otherwise LeafHolder
        let n0 = SkeletonNodeBuilder::default()
            .id(0).child_ids(vec![1])
            .name("n0").original_key("n0")
            .build(NodeKind::Dispatch)
            .unwrap();
        let n1 = SkeletonNodeBuilder::default()
            .id(1).child_ids(vec![2])
            .name("n1").original_key("n1")
            .build(NodeKind::Dispatch)
            .unwrap();
        let n2 = SkeletonNodeBuilder::default()
            .id(2).name("n2").original_key("n2")
            .build(NodeKind::LeafHolder)
            .unwrap();

        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1,n2])
            .root_id(Some(0)).build().unwrap();

        assert_eq!(
            skel.measure_tree_configuration_complexity(),
            Some(DetectedTreeConfigurationComplexity::Linear)
        );
    }

    #[traced_test]
    fn star_tree_returns_star() {
        // 0->(1,2,3)
        let children = vec![1,2,3];
        let n0 = SkeletonNodeBuilder::default()
            .id(0_u16).child_ids(children.clone())
            .name("root").original_key("root")
            .build(NodeKind::Dispatch)
            .unwrap();

        let mut nodes = vec![n0];
        for i in children {
            let leaf = SkeletonNodeBuilder::default()
                .id(i)
                .name(format!("n{}", i))
                .original_key(format!("n{}", i))
                .build(NodeKind::LeafHolder)
                .unwrap();
            nodes.push(leaf);
        }
        let skel = SkeletonBuilder::default().nodes(nodes).root_id(Some(0)).build().unwrap();
        assert_eq!(
            skel.measure_tree_configuration_complexity(),
            Some(DetectedTreeConfigurationComplexity::Star)
        );
    }

    #[traced_test]
    fn perfect_binary_is_balanced() {
        // 0->(1,2), 1->(3,4), 2->(5,6), 3->[],4->[],5->[],6->[]
        fn make(id: u16, kids: Vec<u16>) -> SkeletonNode {
            let k = if kids.is_empty() {
                NodeKind::LeafHolder
            } else {
                NodeKind::Dispatch
            };
            SkeletonNodeBuilder::default()
                .id(id).child_ids(kids)
                .name(format!("n{}", id))
                .original_key(format!("n{}", id))
                .build(k)
                .unwrap()
        }

        let mut nodes = Vec::new();
        let n1 = make(1, vec![3,4]);
        let n2 = make(2, vec![5,6]);
        let n0 = make(0, vec![1,2]);
        nodes.push(n0); nodes.push(n1); nodes.push(n2);
        for i in 3..=6 {
            nodes.push(make(i, vec![]));
        }
        let skel = SkeletonBuilder::default().nodes(nodes).root_id(Some(0)).build().unwrap();

        assert_eq!(
            skel.measure_tree_configuration_complexity(),
            Some(DetectedTreeConfigurationComplexity::Balanced)
        );
    }

    #[traced_test]
    fn irregular_tree_is_complex() {
        // 0->(1,2,3), 1->(4), 2->(), 3->(5,6), 5->(7), 4->(),6->(),7->()
        fn mk(id: u16, kids: Vec<u16>) -> SkeletonNode {
            let k = if kids.is_empty() {
                NodeKind::LeafHolder
            } else {
                NodeKind::Dispatch
            };
            SkeletonNodeBuilder::default()
                .id(id).child_ids(kids)
                .name(format!("n{}",id))
                .original_key(format!("n{}",id))
                .build(k)
                .unwrap()
        }
        let n0 = mk(0, vec![1,2,3]);
        let n1 = mk(1, vec![4]);
        let n2 = mk(2, vec![]);
        let n3 = mk(3, vec![5,6]);
        let n4 = mk(4, vec![]);
        let n5 = mk(5, vec![7]);
        let n6 = mk(6, vec![]);
        let n7 = mk(7, vec![]);
        let skel = SkeletonBuilder::default()
            .nodes(vec![n0,n1,n2,n3,n4,n5,n6,n7])
            .root_id(Some(0))
            .build()
            .unwrap();

        assert_eq!(
            skel.measure_tree_configuration_complexity(),
            Some(DetectedTreeConfigurationComplexity::Complex)
        );
    }
}