nb-tree 0.2.0-alpha01

Very simple tree structure with generic node and branch data.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

use std::hash::Hash;

use super::{diff::DiffTree, NodeIDX, Tree};
use crate::path::Path;

impl<N, B> Tree<N, B>
where
    N: Clone + Eq,
    B: Clone + Eq + Hash,
{
    fn diff_rec(
        &self,
        diff: &mut DiffTree<N, B>,
        other: &Tree<N, B>,
        idx_d: NodeIDX,
        idx_s: NodeIDX,
        idx_o: NodeIDX,
    ) {
        let mut branches_o = other.nodes[idx_o].children.clone();
        // Get children of self
        for (branch, &c_idx_s) in &self.nodes[idx_s].children {
            // Get corresponding child in other
            if let Some(c_idx_o) = branches_o.remove(branch) {
                let value_s = &self.nodes[c_idx_s].value;
                let value_o = &other.nodes[c_idx_o].value;
                // Create a child node in diff
                let c_idx_d = diff
                    .insert_at(
                        idx_d,
                        branch.clone(),
                        if value_s != value_o {
                            // Save differing values
                            (Some(value_s.clone()), Some(value_o.clone()))
                        } else {
                            // Ignore node
                            //TODO: don't create trailing empty nodes
                            Default::default()
                        },
                    )
                    .1;
                self.diff_rec(diff, other, c_idx_d, c_idx_s, c_idx_o);
            } else {
                // Create a child node in diff
                let c_idx_d = diff.insert_at(idx_d, branch.clone(), Default::default()).1;
                diff.mirror_subtree_at(self, c_idx_d, c_idx_s, false);
            }
        }
        // Get remaining children of other
        for (branch, c_idx_o) in branches_o {
            // Create a child node in diff
            let c_idx_d = diff.insert_at(idx_d, branch.clone(), Default::default()).1;
            diff.mirror_subtree_at(other, c_idx_d, c_idx_o, true);
        }
    }
}

impl<N, B> Tree<N, B>
where
    N: Clone + Default + Eq,
    B: Clone + Default + Eq + Hash,
{
    pub fn diff(&mut self, other: &Tree<N, B>) -> DiffTree<N, B> {
        // Check if one of the trees is empty
        let mut diff = DiffTree::new();
        if other.nodes.is_empty() {
            diff.mirror_subtree(self, &Path::new(), false);
            return diff;
        }
        if self.nodes.is_empty() {
            diff.mirror_subtree(other, &Path::new(), true);
            return diff;
        }

        // Set the root node
        if self.nodes[0].value == other.nodes[0].value {
            // values are identical, no difference to save
            diff.insert_root((None, None));
        } else {
            diff.insert_root((
                Some(self.nodes[0].value.clone()),
                Some(other.nodes[0].value.clone()),
            ));
        }

        // Check and set the child nodes
        self.diff_rec(&mut diff, other, 0, 0, 0);
        diff
    }

    pub fn zip(&mut self, other: &Tree<N, B>) -> DiffTree<N, B> {
        let mut diff = DiffTree::new();
        diff.mirror_subtree(self, &Path::new(), false);
        diff.mirror_subtree(other, &Path::new(), true);
        diff
    }
}