nb_tree/tree/
default.rs

1use replace_with::replace_with_or_abort;
2use std::{hash::Hash, mem};
3use tracing::{debug, error, trace, trace_span};
4
5use crate::path::Path;
6
7use super::{
8    diff::{DiffApplyError, DiffMap, DiffNode},
9    iter::depth::Traversal,
10    CombinationMode, DiffTree, NodeIDX, Tree,
11};
12
13/// A tree with optional data for each node
14pub type TreeBuilder<N, B> = Tree<Option<N>, B>;
15
16impl<N, B> Tree<N, B>
17where
18    N: Default,
19    B: Default + Eq + Hash + Clone,
20{
21    /// Extends the tree branches with the given `path` if it leaves the tree
22    pub(super) fn extend(&mut self, path: &Path<B>, from_idx: Option<NodeIDX>) -> Vec<NodeIDX> {
23        match self.get_idx(path, from_idx) {
24            Ok(idx) => vec![idx],
25            Err(node) => {
26                let mut idxs = Vec::new();
27                let (mut node_idx, path_idx) = node.unwrap_or_else(|| {
28                    //tree is empty. Create a root node
29                    self.insert_root(Default::default());
30                    idxs.push(0);
31                    (0, 0)
32                });
33                for branch in path.iter().skip(path_idx) {
34                    node_idx = self
35                        .insert_at(node_idx, branch.clone(), Default::default())
36                        .1;
37                    idxs.push(node_idx);
38                }
39                idxs
40            }
41        }
42    }
43    /// Inserts the `value` at the given `path`, extending the tree if necessary
44    pub fn insert_extend(&mut self, path: &Path<B>, value: N) -> N {
45        let idx = *self.extend(path, None).last().unwrap();
46        mem::replace(&mut self.nodes[idx].value, value)
47    }
48
49    /// Chainable insertion with extension.
50    ///
51    /// Calls `insert_extend` and returns a mutable reference to self
52    pub fn ix(&mut self, path: impl Into<Path<B>>, value: N) -> &mut Self {
53        let ph: Path<B> = path.into();
54        self.insert_extend(&ph, value);
55        self
56    }
57
58    /// Apply `diff` without checking its validity beforehand
59    /// The tree will grow to include changes outside it.
60    /// All invalid changes will be ignored (see [DiffTree::validate()] for more information).
61    pub fn force_apply_extend(&mut self, diff: DiffTree<N, B>) -> bool {
62        self.force_apply_with(
63            diff,
64            |entry, now| {
65                entry.insert_extend(now);
66                true
67            },
68            |entry| {
69                replace_with_or_abort(entry, |e| e.remove_subtree());
70                true
71            },
72        )
73    }
74}
75
76impl<N, B> Tree<N, B>
77where
78    N: Default + Eq,
79    B: Default + Eq + Hash + Clone,
80{
81    pub fn combine_extend(&mut self, tree: Tree<N, B>, mode: CombinationMode) -> bool {
82        self.combine_with(tree, mode, |entry, now| {
83            entry.insert_extend(now);
84            true
85        })
86    }
87    /// Removes trailing default nodes
88    pub fn trim_default(&mut self) {
89        let mut removable = Vec::new();
90        let mut start = Path::new();
91        let mut path = Path::new();
92        for step in self.iter_on::<&N>() {
93            //TODO: prevent clone per loop
94            let old_path = path.clone();
95            path.apply_deref(&step);
96            if start.len() >= path.len() {
97                // Left the trimmable subtree
98                removable.push(start);
99                start = Path::new();
100            }
101            if **step.data() == N::default() {
102                // Trimmable node
103                if start.is_empty() {
104                    // Trimmable subtree root
105                    start = path.clone();
106                }
107            } else {
108                // Not trimmable node
109                if !start.is_empty() {
110                    // Move trimmable subtree root down
111                    removable.push(old_path.path_to(path.len()));
112                }
113            }
114        }
115
116        // Remove trimmable subtrees
117        for ph in removable {
118            self.remove_subtree(&ph)
119                .unwrap_or_else(|_| unreachable!("Could not trim a trimmable subtree"));
120        }
121    }
122}
123
124impl<N, B> Tree<N, B>
125where
126    N: Default + Eq,
127    B: Default + Eq + Hash + Clone,
128{
129    pub fn apply_extend(&mut self, diff: DiffTree<N, B>) -> Result<bool, DiffApplyError<B>> {
130        // Check diff
131        diff.is_applicable_extend(self)?;
132
133        // Apply diff
134        Ok(self.force_apply_extend(diff))
135    }
136
137    pub fn apply_diff_extend(
138        &mut self,
139        path: Path<B>,
140        diff: DiffNode<N>,
141    ) -> Result<(), DiffApplyError<B>> {
142        self.apply_diff_with(path, diff, |entry, v| {
143            entry.insert_extend(v);
144            Ok(())
145        })
146    }
147
148    pub fn apply_map_extend(&mut self, map: DiffMap<N, B>) -> bool {
149        map.into_iter().fold(true, |mut res, (ph, diff)| {
150            if self.apply_diff_extend(ph, diff).is_err() {
151                res = false;
152            }
153            res
154        })
155    }
156
157    /// Fails if the diff is invalid
158    pub fn remove_subtree_trim(&mut self, path: &Path<B>) -> Result<(), Option<Path<B>>> {
159        let mut path = path.clone();
160        // Remove node and children from tree
161        self.remove_subtree(&path)?;
162
163        // Has parent? (Not root node)
164        if let Some(branch) = path.pop_last() {
165            // Get parent indexes
166            let mut parents = self
167                .get_path_idxs(&path)
168                .map_err(|r| path.path_to(*r.unwrap_or((vec![0], 0)).0.last().unwrap_or(&0)))?;
169
170            // Remove empty parent nodes
171            while let Some(idx) = parents.pop() {
172                if self.nodes[idx].value == Default::default()
173                    && parents.last().map(|&i| self.nodes[i].children.len()) == Some(1)
174                {
175                    self.remove_subtree_at(*parents.last().unwrap(), path.pop_last().unwrap());
176                } else {
177                    break;
178                }
179            }
180
181            // Remove child parent link
182            if !parents.is_empty() {
183                self.nodes[*parents.last().unwrap()]
184                    .children
185                    .remove(&branch);
186            }
187        }
188        Ok(())
189    }
190}
191
192impl<N, B> TreeBuilder<N, B>
193where
194    N: Default,
195    B: Default + Eq + Hash + Clone,
196{
197    pub fn is_buildable(&self) -> bool {
198        // Check for adjacency
199        let mut iter = self.iter_on::<&Option<N>>();
200
201        if let Some(Traversal::Start(Some(_))) = iter.next() {
202            // First node is root and not empty
203        } else {
204            return false;
205        };
206        iter.try_fold(Path::new(), |mut ph, node| {
207            // No Root node and all nodes contain data
208            (ph.apply_deref(&node) && node.take().is_some()).then_some(ph)
209        })
210        .is_some()
211    }
212
213    pub fn build(self) -> Tree<N, B> {
214        // Build Tree
215        self.into_iter()
216            .try_fold((Tree::new(), Path::new()), |(mut tree, mut ph), node| {
217                match node {
218                    Traversal::Start(data) => {
219                        tree.insert_root(data.unwrap());
220                    }
221                    Traversal::Step { up, branch, data } => {
222                        let value = data.unwrap();
223                        let parent_idx = ph.last().map(|(_, idx)| *idx).unwrap_or(0);
224
225                        // Move up
226                        (0..up).for_each(|_| {
227                            ph.pop_last();
228                        });
229                        // Move down
230                        ph.push_last((branch.clone(), tree.insert_at(parent_idx, branch, value).1));
231                    }
232                };
233                Some((tree, ph))
234            })
235            .map(|(tree, _)| tree)
236            .unwrap()
237    }
238}
nb_tree/tree/default.rs

nb_tree/tree/
default.rs
