nb_tree/tree/
clone.rs

1use std::hash::Hash;
2
3use super::{diff::DiffTree, NodeIDX, Tree};
4use crate::path::Path;
5
6impl<N, B> Tree<N, B>
7where
8    N: Clone + Eq,
9    B: Clone + Eq + Hash,
10{
11    fn diff_rec(
12        &self,
13        diff: &mut DiffTree<N, B>,
14        other: &Tree<N, B>,
15        idx_d: NodeIDX,
16        idx_s: NodeIDX,
17        idx_o: NodeIDX,
18    ) {
19        let mut branches_o = other.nodes[idx_o].children.clone();
20        // Get children of self
21        for (branch, &c_idx_s) in &self.nodes[idx_s].children {
22            // Get corresponding child in other
23            if let Some(c_idx_o) = branches_o.remove(branch) {
24                let value_s = &self.nodes[c_idx_s].value;
25                let value_o = &other.nodes[c_idx_o].value;
26                // Create a child node in diff
27                let c_idx_d = diff
28                    .insert_at(
29                        idx_d,
30                        branch.clone(),
31                        if value_s != value_o {
32                            // Save differing values
33                            (Some(value_s.clone()), Some(value_o.clone()))
34                        } else {
35                            // Ignore node
36                            //TODO: don't create trailing empty nodes
37                            Default::default()
38                        },
39                    )
40                    .1;
41                self.diff_rec(diff, other, c_idx_d, c_idx_s, c_idx_o);
42            } else {
43                // Create a child node in diff
44                let c_idx_d = diff.insert_at(idx_d, branch.clone(), Default::default()).1;
45                diff.mirror_subtree_at(self, c_idx_d, c_idx_s, false);
46            }
47        }
48        // Get remaining children of other
49        for (branch, c_idx_o) in branches_o {
50            // Create a child node in diff
51            let c_idx_d = diff.insert_at(idx_d, branch.clone(), Default::default()).1;
52            diff.mirror_subtree_at(other, c_idx_d, c_idx_o, true);
53        }
54    }
55}
56
57impl<N, B> Tree<N, B>
58where
59    N: Clone + Default + Eq,
60    B: Clone + Default + Eq + Hash,
61{
62    pub fn diff(&mut self, other: &Tree<N, B>) -> DiffTree<N, B> {
63        // Check if one of the trees is empty
64        let mut diff = DiffTree::new();
65        if other.nodes.is_empty() {
66            diff.mirror_subtree(self, &Path::new(), false);
67            return diff;
68        }
69        if self.nodes.is_empty() {
70            diff.mirror_subtree(other, &Path::new(), true);
71            return diff;
72        }
73
74        // Set the root node
75        if self.nodes[0].value == other.nodes[0].value {
76            // values are identical, no difference to save
77            diff.insert_root((None, None));
78        } else {
79            diff.insert_root((
80                Some(self.nodes[0].value.clone()),
81                Some(other.nodes[0].value.clone()),
82            ));
83        }
84
85        // Check and set the child nodes
86        self.diff_rec(&mut diff, other, 0, 0, 0);
87        diff
88    }
89
90    pub fn zip(&mut self, other: &Tree<N, B>) -> DiffTree<N, B> {
91        let mut diff = DiffTree::new();
92        diff.mirror_subtree(self, &Path::new(), false);
93        diff.mirror_subtree(other, &Path::new(), true);
94        diff
95    }
96}
nb_tree/tree/clone.rs

nb_tree/tree/
clone.rs
