xml_3dm/diff/
bfs_index.rs

1//! BFS index for node enumeration.
2//!
3//! Assigns sequential IDs to nodes using breadth-first search traversal.
4//! Adjacent nodes in the tree get consecutive IDs, enabling run-length encoding
5//! in the diff output.
6
7use std::collections::{HashMap, VecDeque};
8
9use crate::node::NodeRef;
10
11/// Index that maps nodes to sequential IDs using BFS order.
12///
13/// This allows the diff algorithm to use run-length encoding for
14/// consecutive copies, as adjacent siblings will have sequential IDs.
15#[derive(Debug)]
16pub struct BfsIndex {
17    /// Maps node IDs to their BFS index.
18    node_to_id: HashMap<u64, u64>,
19    /// Maps BFS index back to node.
20    id_to_node: HashMap<u64, NodeRef>,
21    /// The root node's ID.
22    root_id: u64,
23}
24
25impl BfsIndex {
26    /// Creates a new BFS index for the given tree.
27    pub fn new(root: &NodeRef) -> Self {
28        let mut node_to_id = HashMap::new();
29        let mut id_to_node = HashMap::new();
30        let mut queue = VecDeque::new();
31        let mut id: u64 = 0;
32
33        queue.push_back(root.clone());
34
35        while let Some(node) = queue.pop_front() {
36            let node_id = node.borrow().id();
37            node_to_id.insert(node_id, id);
38            id_to_node.insert(id, node.clone());
39
40            // Add children to queue
41            let borrowed = node.borrow();
42            for child in borrowed.children() {
43                queue.push_back(child.clone());
44            }
45
46            id += 1;
47        }
48
49        let root_id = *node_to_id.get(&root.borrow().id()).unwrap_or(&0);
50
51        BfsIndex {
52            node_to_id,
53            id_to_node,
54            root_id,
55        }
56    }
57
58    /// Gets the BFS index for a node.
59    pub fn get_id(&self, node: &NodeRef) -> Option<u64> {
60        let node_id = node.borrow().id();
61        self.node_to_id.get(&node_id).copied()
62    }
63
64    /// Looks up a node by its BFS index.
65    pub fn lookup(&self, id: u64) -> Option<NodeRef> {
66        self.id_to_node.get(&id).cloned()
67    }
68
69    /// Looks up a node by its string ID.
70    pub fn lookup_str(&self, id: &str) -> Option<NodeRef> {
71        id.parse::<u64>().ok().and_then(|n| self.lookup(n))
72    }
73
74    /// Returns the root node's BFS ID.
75    pub fn root_id(&self) -> u64 {
76        self.root_id
77    }
78
79    /// Checks if two nodes are adjacent in BFS order.
80    pub fn appends(&self, tail: &NodeRef, next: &NodeRef) -> bool {
81        match (self.get_id(tail), self.get_id(next)) {
82            (Some(tail_id), Some(next_id)) => next_id == tail_id + 1,
83            _ => false,
84        }
85    }
86}
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91    use crate::node::{new_base_node, NodeInner, XmlContent, XmlElement, XmlText};
92    use std::collections::HashMap;
93
94    fn create_test_tree() -> NodeRef {
95        // Create tree:
96        //     root
97        //    /    \
98        //  child1  child2
99        //   |
100        // grandchild
101        let root = new_base_node(Some(XmlContent::Element(XmlElement::new(
102            "root".to_string(),
103            HashMap::new(),
104        ))));
105        let child1 = new_base_node(Some(XmlContent::Element(XmlElement::new(
106            "child1".to_string(),
107            HashMap::new(),
108        ))));
109        let child2 = new_base_node(Some(XmlContent::Element(XmlElement::new(
110            "child2".to_string(),
111            HashMap::new(),
112        ))));
113        let grandchild = new_base_node(Some(XmlContent::Text(XmlText::new("text"))));
114
115        // Build tree
116        NodeInner::add_child_to_ref(&child1, grandchild);
117        NodeInner::add_child_to_ref(&root, child1);
118        NodeInner::add_child_to_ref(&root, child2);
119
120        root
121    }
122
123    #[test]
124    fn test_bfs_index_creation() {
125        let root = create_test_tree();
126        let index = BfsIndex::new(&root);
127
128        // BFS order: root(0), child1(1), child2(2), grandchild(3)
129        assert_eq!(index.root_id(), 0);
130        assert_eq!(index.get_id(&root), Some(0));
131    }
132
133    #[test]
134    fn test_bfs_lookup() {
135        let root = create_test_tree();
136        let index = BfsIndex::new(&root);
137
138        // Lookup root
139        let found = index.lookup(0).unwrap();
140        assert_eq!(found.borrow().id(), root.borrow().id());
141
142        // Lookup by string
143        let found_str = index.lookup_str("0").unwrap();
144        assert_eq!(found_str.borrow().id(), root.borrow().id());
145    }
146
147    #[test]
148    fn test_bfs_appends() {
149        let root = create_test_tree();
150        let index = BfsIndex::new(&root);
151
152        let child1 = index.lookup(1).unwrap();
153        let child2 = index.lookup(2).unwrap();
154
155        // child1 (1) and child2 (2) are adjacent
156        assert!(index.appends(&child1, &child2));
157
158        // root (0) and child2 (2) are not adjacent
159        assert!(!index.appends(&root, &child2));
160    }
161}
xml_3dm/diff/bfs_index.rs

xml_3dm/diff/
bfs_index.rs
