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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

use std::{fmt::Debug, hash::Hash, mem};

use crate::path::Path;

use super::{iter::Iter, node::TreeNode, DiffTree, NodeIDX, Tree};

impl<N, B> Tree<N, B>
where
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
    N: Debug + PartialEq,
{
    pub fn iter(&self) -> Iter<'_, N, B> {
        Iter::new(self)
    }
}

impl<N, B> Tree<N, B>
where
    B: Clone + Debug + Default + PartialEq + Eq + PartialOrd + Ord + Hash,
    N: Debug + Default + PartialEq,
{
    /// Extends the tree branches with the given path if it leaves the tree
    pub(super) fn extend(&mut self, path: &Path<B>, from_idx: Option<NodeIDX>) -> NodeIDX {
        match self.get_idx(path, from_idx) {
            Ok(idx) => idx,
            Err(node) => {
                let (mut node_idx, path_idx) = node.unwrap_or_else(|| {
                    //tree is empty. Create a root node
                    self.insert_root(Default::default());
                    (0, 0)
                });
                for attr in path.path_from(path_idx) {
                    let node_idx_new = self.nodes.len();
                    self.nodes.push(TreeNode::default());
                    self.nodes[node_idx].children.insert(attr, node_idx_new);
                    node_idx = node_idx_new;
                }
                node_idx
            }
        }
    }

    /// Inserts the [value] at the given [path], extending the tree if necessary
    pub fn insert_extend(&mut self, path: &Path<B>, value: N) -> N {
        let idx = self.extend(path, None);
        mem::replace(&mut self.nodes[idx].value, value)
    }

    pub fn overwrite_extend(&mut self, diff: DiffTree<N, B>) {
        // Apply diff without checking its validity behorehand
        // TODO: IntoIter
        for (ph, d) in diff {
            if let Some(now) = d.1 {
                // New or change node
                self.insert_extend(&ph, now);
            } else if d.0.is_some() {
                // Remove node
                self.remove_sub_tree(&ph);
            }
        }
    }

    pub fn apply_extend(&mut self, diff: DiffTree<N, B>) -> Result<(), Path<B>> {
        // Diff validity check
        for (ph, d) in diff.iter() {
            if let Some(before) = &d.0 {
                // Change or delete node
                // Corresponding node in tree?
                let node_idx = self
                    .get_idx(&ph, None)
                    .map_err(|r| ph.path_to(r.unwrap_or((0, 0)).1))?;
                // Diff corresponds to node value?
                if &self.nodes[node_idx].value != before {
                    return Err(ph);
                }
            } else if d.1.is_some() {
                // New node
                //TODO: clean
                let mut ph = ph.clone();
                ph.pop_leaf();
                self.get_idx(&ph, None)
                    .map_err(|r| ph.path_to(r.unwrap_or((0, 0)).1))?;
            }
        }

        // Apply diff
        self.overwrite_extend(diff);
        Ok(())
    }

    pub fn remove_sub_tree_trim(&mut self, path: &Path<B>) -> Result<(), Option<Path<B>>> {
        let mut path = path.clone();
        // Remove node and children from tree
        self.remove_sub_tree(&path)?;

        // Has parent? (Not root node)
        if let Some(mut branch) = path.pop_leaf() {
            let mut parents = self
                .get_path_idxs(&path)
                .map_err(|r| path.path_to(*r.unwrap_or((vec![0], 0)).0.last().unwrap_or(&0)))?;

            // Remove empty parent nodes
            while !parents.is_empty() {
                let parent = &mut self.nodes[*parents.last().unwrap()];
                if parent.children.len() == 1 && parent.value == Default::default() {
                    self.nodes.remove(parents.pop().unwrap());
                    branch = path.pop_leaf().unwrap();
                }
            }
            //debug_assert!(self.nodes[path_idxs.last()].children.len());

            // Remove child parent link
            if !parents.is_empty() {
                self.nodes[*parents.last().unwrap()]
                    .children
                    .remove(&branch);
            }
        }
        Ok(())
    }

    pub fn try_build(self) -> Option<Tree<N, B>> {
        self.into_iter()
            .try_fold(Tree::new(), |mut tree, (path, value)| {
                tree.insert(&path, value).map(|_| tree).ok()
            })
    }
}