nb_tree/tree/
mod.rs

1//! # Tree
2//! A tree structure.
3//! ## Data Structure
4//! The nb_tree crate provides a [`Tree<N, B>`](crate::tree::Tree) type
5//! generic over node and branch data.
6//!
7//! Trees have an O(n) indexing. More precisely, it retrieves every node
8//! on the path from the tree root to the targetted node.
9//! Insertion and removal take a Path to target a node, binding their complexity
10//! to the one of indexing, thus O(n).
11//! Entries can be used to insert or remove at the [Entry](crate::tree::entry::Entry)'s
12//! position in the tree, which only takes O(1).
13//!
14//! Trees can be [built](type@crate::tree::default::TreeBuilder),
15//! [navigated and modified](type@crate::tree::entry::Entry),
16//! [diffed](type@crate::tree::diff::DiffTree), [combined](type@crate::tree::combine) and [iterated](crate::tree::iter::Iter) on
17//! amongst other operations.
18//!
19//! # Building trees
20//! Trees can be built in several ways using (chainable) insertion methods.
21//!
22//! ## Inserting data
23//! Data can be added or overwritten at a specified location via [insert].
24//! ```
25//! use nb_tree::prelude::Tree;
26//! let mut tree: Tree<usize, String> = Tree::new();
27//! // Insert at root
28//! // (None reflects the creation of a new node
29//! //  there is no previous value to return)
30//! assert_eq!(tree.insert(&"/".into(), 0), Ok(None));
31//! // Insert at various given Paths
32//! assert_eq!(tree.insert(&"/a".into(), 1), Ok(None));
33//! assert_eq!(tree.insert(&"/b".into(), 2), Ok(None));
34//! assert_eq!(tree.insert(&"/b/c".into(), 3), Ok(None));
35//! // One can't insert below an inexistent node with `insert`
36//! // Use `insert_extend` for this
37//! assert_eq!(tree.insert(&"/a/x/z".into(), 12), Err(Some("/a".into())));
38//! ```
39//! A shorthand exists for chaining insertions
40//! ```
41//! use nb_tree::prelude::Tree;
42//! let mut tree: Tree<usize, String> = Tree::new();
43//! tree.i("/", 0)
44//!     .i("/a", 1)
45//!     .i("/a/b", 2)
46//!     .i("/a/c", 3)
47//!     .i("/d", 4);
48//! ```
49//! Note that [i] panics if the insertion fails.
50//!
51//! For node data types that are [Default], [insert_extend] can be used to build
52//! intermediary nodes with default data between the last existing node of the
53//! given [Path] in the [Tree] and the one to insert
54//! ```
55//! use nb_tree::prelude::Tree;
56//! let mut tree: Tree<usize, String> = Tree::new();
57//! tree.insert_extend(&"/a/b/c/x/y/z".into(), 1000000);
58//! assert_eq!(tree.values().len(), 7);
59//! // A shorthand for `insert_extend` also exists and can be chained
60//! tree.ix("/a/b/i/j/k", 101010)
61//!     .ix("/a/u/v/w/i/j/k", 222);
62//! assert_eq!(tree.values().len(), 16);
63//! ```
64//! [`insert_extend`] returns the old value if any.
65//! If the node did not exist, it returns the default value of the node type.
66//!
67//! ### Builder
68//! [`TreeBuilder`] is a [`Tree`] wrapping each node data in an `Option`.
69//! [`Tree`]s with `Option<N>` node data have a [`try_build()`] method to build
70//! a `Tree<N>` from it.
71//!
72//! ```
73//! use nb_tree::prelude::{Tree, TreeBuilder};
74//! let mut tree: TreeBuilder<usize, String> = TreeBuilder::new();
75//! tree.ix("/a/b/c", Some(3))
76//!     .ix("/a/b", Some(2));
77//! // The tree can't be built because there are empty nodes ("/" and "/a") left
78//! assert_eq!(tree.is_buildable(), false);
79//!
80//! tree.ix("/", Some(0))
81//!     .ix("/a", Some(1));
82//! // The tree is now buildable
83//! assert_eq!(tree.is_buildable(), true);
84//!
85//! let mut tree_cmp: Tree<usize, String> = Tree::new();
86//! tree_cmp.i("/", 0).i("/a", 1).i("/a/b", 2).i("/a/b/c", 3);
87//! assert_eq!(tree.build(), tree_cmp);
88//! ```
89//!
90//! ## Removing data
91//! Subtrees can be removed from a tree:
92//! [remove_subtree] removes the subtree starting at the given [Path].
93//! ```
94//! use nb_tree::prelude::Tree;
95//! let mut tree: Tree<usize, String> = Tree::new();
96//! tree.i("/", 0)
97//!     .i("/a", 1)
98//!     .i("/a/b", 2)
99//!     .i("/a/c", 3);
100//! // Removes the subtree at /a
101//! tree.remove_subtree(&"/a".into());
102//! // Only the root node (of value 0) now remains
103//! assert_eq!(tree.values().len(), 1);
104//! ```
105//! [remove_subtree_trim] also trims out parent nodes containing the default value:
106//! ```
107//! use nb_tree::prelude::Tree;
108//! let mut tree: Tree<Option<usize>, String> = Tree::new();
109//! assert!(tree.insert(&"/".into(), Some(0)).is_ok());
110//! assert!(tree.insert(&"/a".into(), Some(1)).is_ok());
111//! tree.insert_extend(&"/a/b/c/i/j/k/x/y/z".into(), Some(1000000));
112//! // `remove_subtree` only removes the subtree
113//! tree.remove_subtree(&"/a/b/c/i/j/k".into());
114//! assert_eq!(tree.len(), 6);
115//! // `remove_subtree_trim` also removes the parent nodes containing `None`
116//! tree.remove_subtree_trim(&"/a/b/c".into());
117//! // Only the root node and the node at "/a" containing non default data remain
118//! assert_eq!(tree.len(), 2);
119//! ```
120//!
121//! ## Navigation and manipulation
122//!
123//! [Entries](type@crate::tree::entry::Entry) allow for tree navigation and mutation,
124//! similarly to HashMaps' entry system.
125//! It represents an entry at a given Path.
126//! It may lead to a defined node or not.
127//! ```
128//! use nb_tree::prelude::Tree;
129//! let mut tree: Tree<usize, String> = Tree::new();
130//! tree.i("/", 0)
131//!     .i("/a", 1)
132//!     .i("/a/b", 2)
133//!     .i("/c", 3)
134//!     .i("/f", 4);
135//! let mut entry = tree.entry_mut(&"/a".into());
136//! // Insert only if there isn't a value already defined
137//! // (won't do anything since /a is already set)
138//! entry.or_insert(10);
139//! // Move down to an other node
140//! entry.move_down("/b/w".into());
141//! // inserts 12 at /b/w
142//! entry.or_insert(12);
143//! // `or_insert_extend` is only available if N is Default
144//! let mut tree2: Tree<Option<usize>, String> = Tree::new();
145//! let mut entry2 = tree2.entry_mut(&"/i/j/k".into());
146//! entry2.or_insert_extend(Some(12));
147//! assert_eq!(tree2.len(), 4);
148//! ```
149//! `and_modify` only applies the given function to the node's value if it is defined.
150//! ```
151//! # use nb_tree::prelude::Tree;
152//! # let mut tree: Tree<usize, String> = Tree::new();
153//! # tree.i("/", 0)
154//! #     .i("/a", 1)
155//! #     .i("/a/b", 2)
156//! #     .i("/c", 3)
157//! #     .i("/f", 4);
158//! let mut entry = tree.entry_mut(&"/a/b".into());
159//! entry.and_modify(|mut n| *n += 1);
160//! ```
161//! The previous methods like `insert` and `remove_subtree` are also available
162//! for inserting and removing data at entry position.
163//!
164//! # Differentials
165//! ## Diffing
166//! Trees can be compared via [`diff`], producing a [`DiffTree`] containing
167//! all differing nodes between the compared trees.
168//! [`DiffTree`]s are `Tree`s with `DiffNode`s which have the type `(Option(N), Option(N))`.
169//! The `Option`s signal the presence (or absence thereof) of the node in the compared trees.
170//! The `DiffTree` produced by `diff` only contains data for nodes differing,
171//! so the diff tree will be extended with empty nodes (`(None, None)`) to build the tree.
172//! ```
173//! use nb_tree::prelude::{Tree, DiffTree};
174//! let mut tree1: Tree<usize, String> = Tree::new();
175//! tree1.i("/", 0)
176//!     .i("/a", 1)
177//!     .i("/a/b", 2)
178//!     .i("/c", 3)
179//!     .i("/f", 4);
180//!
181//! let mut tree2: Tree<usize, String> = Tree::new();
182//! tree2.i("/", 9)
183//!     .i("/a", 2)
184//!     .i("/a/b", 1)
185//!     .i("/c", 3)
186//!     .i("/c/d", 4);
187//!
188//! // Create a DiffTree containing the differences between `tree1` and `tree2`
189//! let diff = tree1.diff(&tree2);
190//!
191//! let mut diff_cmp: DiffTree<usize, String> = DiffTree::new();
192//! diff_cmp.i("/", (Some(0), Some(9)))
193//!     .i("/a", (Some(1), Some(2)))
194//!     .i("/a/b", (Some(2), Some(1)))
195//!     .i("/f", (Some(4), None))
196//!     .ix("/c/d", (None, Some(4)));
197//! // "/c/d" node insertion needs a node at "/c"
198//! // `ix` will extend the tree with an empty node (`(None, None)`) to allow for that
199//! assert_eq!(diff, diff_cmp);
200//! ```
201//! [`zip`] will combine both trees into a [DiffTree].
202//!
203//! ## Applying diffs
204//!
205//! [`DiffTree`]s can be applied to a tree via [`apply`] and [`apply_extend`].
206//! ```
207//! # use nb_tree::prelude::{Tree, DiffTree};
208//! # let mut tree1: Tree<usize, String> = Tree::new();
209//! # tree1.i("/", 0)
210//! #     .i("/a", 1)
211//! #     .i("/a/b", 2)
212//! #     .i("/c", 3)
213//! #     .i("/f", 4);
214//! # let mut tree2: Tree<usize, String> = Tree::new();
215//! # tree2.i("/", 9)
216//! #     .i("/a", 2)
217//! #     .i("/a/b", 1)
218//! #     .i("/c", 3)
219//! #     .i("/c/d", 4);
220//! # let mut diff = tree1.diff(&tree2);
221//! // … taking back `tree1`, `tree2` and `diff` from the previous example
222//! let tree1_orig = tree1.clone();
223//! // Apply the differential between `tree1` and `tree2`
224//! tree1.apply(diff.clone());
225//! // They are both equal now
226//! assert_eq!(tree1, tree2);
227//! // Applying the reversed diff will restore tree1
228//! diff.rev();
229//! tree1.apply(diff);
230//! assert_eq!(tree1, tree1_orig);
231//! ```
232//!
233//! Single diff data can be applied via the `apply_diff` method which takes a
234//! Path and a `DiffNode` and applies it to the tree.
235//! These diffs can be gathered into a `DiffMap` that too can be applied
236//! via `apply_map`.
237//! ```
238//! use nb_tree::prelude::{Tree, DiffMap};
239//! use std::collections::HashMap;
240//! let mut tree: Tree<usize, String> = Tree::new();
241//! tree.i("/", 0)
242//!     .i("/a", 1)
243//!     .i("/a/b", 2)
244//!     .i("/c", 3)
245//!     .i("/f", 4);
246//! // Changes the value of the node at /c from 3 to 7
247//! tree.apply_diff("/c".into(), (Some(3), Some(7)));
248//! // Removes the node at /a that had the value 1 and the subtree below it
249//! tree.apply_diff("/a".into(), (Some(1), None));
250//! // Changes /f from 4 to 0, creates /f/z with value 5
251//! let map = HashMap::from([
252//!     ("/f".into(), (Some(4), Some(0))),
253//!     ("/f/z".into(),
254//!     (None, Some(5)))]).into();
255//! let mut tree_cmp: Tree<usize, String> = Tree::new();
256//! tree.apply_map(map);
257//! tree_cmp.i("/", 0)
258//!     .i("/c", 7)
259//!     .i("/f", 0)
260//!     .i("/f/z", 5);
261//! assert_eq!(tree, tree_cmp);
262//! ```
263//! # Combining
264//! Combining trees can be done through the `combine()` method.
265//! Data present in both trees can be chosen from either tree,
266//! data only present in one of them can be kept or discarded.
267//! `CombinationMode::Union` and `CombinationMode::Intersection` are available,
268//! as well as a `CombinationMode::Free` mode which lets freely select
269//! the data to keep during the combination.
270//! ```
271//! use nb_tree::prelude::{Tree, CombinationMode};
272//! let mut tree1: Tree<usize, String> = Tree::new();
273//! tree1.i("/", 0)
274//!      .i("/a", 1)
275//!      .i("/a/b", 11)
276//!      .i("/c", 2)
277//!      .i("/f", 3);
278//!
279//! let mut tree2: Tree<usize, String> = Tree::new();
280//! tree2.i("/", 500)   // |- overlaping data
281//!      .i("/a", 900)  // |
282//!      .i("/a/w", 910)// |- new data
283//!      .i("/x", 100)  // |
284//!      .i("/x/y", 110)// |
285//!      .i("/z", 300); // |
286//!
287//! // tree1 is combined with tree2, keeping tree1's nodes absent from tree2,
288//! // growing tree1 with tree2's nodes absent from tree1
289//! // and overwriting tree1's data with tree2's for nodes common to both trees.
290//! tree1.combine(tree2, CombinationMode::Free{keep: true, grow: true, overwrite: true});
291//! // (this is the same as `CombinationMode::Union(true)`)
292//!
293//! let mut tree_comb: Tree<usize, String> = Tree::new();
294//! tree_comb.i("/", 500)   // |- common nodes with tree2's data (overwrite)
295//!          .i("/a", 900)  // |
296//!          .i("/a/b", 11) // |- tree1's nodes (keep)
297//!          .i("/c", 2)    // |
298//!          .i("/f", 3)    // |
299//!          .i("/a/w", 910)// |- tree2's nodes (grow)
300//!          .i("/x", 100)  // |
301//!          .i("/x/y", 110)// |
302//!          .i("/z", 300); // |
303//!
304//! assert_eq!(tree1, tree_comb);
305//! ```
306//! # Iterating
307//!
308//! The default iteration method is depth first (width first is not yet available)
309//! ```
310//! use nb_tree::prelude::{Tree, DiffMap};
311//! let mut tree1: Tree<usize, String> = Tree::new();
312//! tree1.i("/", 0)
313//!     .i("/a", 1)
314//!     .i("/a/b", 12)
315//!     .i("/c", 3)
316//!     .i("/f", 4);
317//! // Prints each node's branch and value
318//! for iter_node in tree1 {
319//!     println!("{} at {:?}", iter_node.data(), iter_node.branch());
320//! }
321//! ```
322//! `iter` and `into_iter` are implemented (`iter_mut` is not yet available).
323//! The iteration nodes contain information about the position in the tree
324//! relative to the previous node.
325//! The path to the current node can be built by applying these relative movements to it.
326//! ```
327//! # use nb_tree::prelude::{Tree, DiffMap};
328//! # let mut tree1: Tree<usize, String> = Tree::new();
329//! # tree1.i("/", 0)
330//! #     .i("/a", 1)
331//! #     .i("/a/b", 12)
332//! #     .i("/c", 3)
333//! #     .i("/f", 4);
334//! # use nb_tree::prelude::Path;
335//! let mut path = Path::new();
336//! for iter_node in tree1 {
337//!     path.apply(&iter_node);
338//!     println!("{} at {}", iter_node.data(), path);
339//! }
340//! ```
341//! The usual iterator operations are available as well as `absolute` and `skip_below`.
342//!
343//! `absolute` returns the next value with its Path.
344//! ```
345//! # use nb_tree::prelude::{Tree, DiffMap};
346//! # let mut tree1: Tree<usize, String> = Tree::new();
347//! # tree1.i("/", 0)
348//! #     .i("/a", 1)
349//! #     .i("/a/b", 12)
350//! #     .i("/c", 3)
351//! #     .i("/f", 4);
352//! # use nb_tree::prelude::Path;
353//! use itertools::Itertools;
354//! use crate::nb_tree::tree::iter::{TreeIterTools, TraversalNode};
355//! assert_eq!(
356//!     tree1.into_iter().absolute().map(|n| n.path).sorted().collect::<Vec<Path<String>>>(),
357//!     vec!["/".into(), "/a".into(), "/a/b".into(), "/c".into(), "/f".into()]
358//!     );
359//! ```
360//!
361//! `skip_below` takes a predicate and skips all nodes at and below the current path.
362//! ```
363//! use nb_tree::prelude::{Tree, DiffMap};
364//! let mut tree1: Tree<usize, String> = Tree::new();
365//! tree1.i("/", 0)
366//!     .i("/a", 1)
367//!     .i("/a/b", 12)
368//!     .i("/a/b/z", 6)
369//!     .i("/c", 3)
370//!     .i("/c/d", 7)
371//!     .i("/c/d/y", 5)
372//!     .i("/f", 11)
373//!     .i("/g", 10)
374//!     .i("/h", 11)
375//!     .i("/i", 19)
376//!     .i("/i/w", 18)
377//!     .i("/i/w/n", 8)
378//!     .i("/k", 15);
379//! use itertools::Itertools;
380//! use nb_tree::prelude::Path;
381//! use crate::nb_tree::tree::iter::TreeIterTools;
382//! assert_eq!(
383//!     tree1.into_iter().skip_below(|item| {
384//!         *item.data() >= 10
385//!     }).map(|n| n.data().clone()).sorted().collect::<Vec<usize>>(),
386//!     vec![0, 1, 3, 5, 7]
387//!     );
388//! ```
389
390pub(crate) mod clone;
391pub(crate) mod default;
392pub use default::TreeBuilder;
393pub(crate) mod diff;
394pub use diff::{DiffMap, DiffNode, DiffTree};
395/// [`Tree`] iteration.
396///
397/// [`Tree`]: crate::tree::Tree
398pub mod iter;
399pub(crate) mod node;
400use node::TreeNode;
401/// [`Tree`] navigation.
402///
403/// [`Tree`]: crate::tree::Tree
404pub mod entry;
405pub(crate) mod position;
406pub use position::Position;
407use replace_with::replace_with_or_abort;
408
409use self::diff::DiffApplyError;
410use self::entry::{TreeMutEntry, TREEBOUND};
411use self::iter::depth::IntoIter;
412use self::{
413    entry::{detached::DetachedEntry, node::Node, Entry},
414    position::{AttachedPosition, DetachedPosition},
415};
416use super::path::Path;
417use crate::path::PathIDX;
418
419use iter::depth::{Iter, Traversal, TreeIterTarget};
420use std::hash::Hash;
421use std::mem;
422use std::ops::Index;
423use std::{fmt::Debug as Dbg, ops::Deref};
424use tracing::{debug, error, trace, trace_span};
425
426/// Takes a Result and returns the Some value or returns the given value.
427macro_rules! or_return {
428    ( $e:expr, $r:expr ) => {
429        match $e {
430            Some(x) => x,
431            None => return $r,
432        }
433    };
434}
435
436/// The index of a node in the tree.
437///
438/// Since these can change, they cannot be used as node identifiers
439/// and should not be exposed in the API.
440pub(crate) type NodeIDX = usize;
441
442/// Tree structure with generic node and branch data.
443///
444/// For more information about Trees and their usage,
445/// see the [module level documentation](self).
446///
447/// Each node aside from the root node has a parent to which it is linked via a branch.
448/// Nodes as well as branches have a value, which allows for giving names and wheights
449/// to branches.
450///
451/// # Examples
452/// A quick way to build a tree is by using the chainable version of `insert()` called `i()`
453/// ```
454/// use nb_tree::prelude::Tree;
455/// let mut tree: Tree<usize, String> = Tree::new();
456///
457/// tree.i("/", 0)
458///     .i("/a", 1)
459///     .i("/a/b", 2)
460///     .i("/a/b/z", 6)
461///     .i("/c", 3)
462///     .i("/c/d", 7);
463/// ```
464/// The resulting tree looks like this:
465/// ```text
466/// ╱┬→ 0
467///  ├a┬→ 1
468///  │ └b┬→ 2
469///  │   └z─→ 6
470///  └c┬→ 3
471///    └d─→ 7
472/// ```
473/// # Data management
474///
475/// Removing a node from the tree also removes its children recursively.
476/// Removal is done in constant time, since the nodes are only unlinked
477/// from their parent and marked as removed.
478/// Since the nodes are stored in a Vec, shifting the ones succeeding
479/// the removed node would be costful and removing the whole subtree
480/// would take O(n) given n the number of nodes in that subtree.
481#[derive(Debug, Clone)]
482pub struct Tree<N, B> {
483    /// Nodes are added and removed through `insert()` and `remove()` only.
484    nodes: Vec<TreeNode<N, B>>,
485    /// Nodes removed from the tree.
486    /// These indexes will be reused later upon inserting new nodes
487    /// via `insert()`.
488    /// `remove()` adds them to the vec.
489    removed: Vec<NodeIDX>,
490}
491
492impl<N, B> Default for Tree<N, B> {
493    fn default() -> Self {
494        Self {
495            nodes: Vec::default(),
496            removed: Vec::default(),
497        }
498    }
499}
500
501impl<N, B> Index<&Path<B>> for Tree<N, B>
502where
503    B: Eq + Hash + Clone,
504{
505    type Output = N;
506    fn index(&self, index: &Path<B>) -> &Self::Output {
507        self.get(index)
508            .unwrap_or_else(|_| panic!("Could not index into the tree with the given path"))
509    }
510}
511
512impl<N, B> PartialEq for Tree<N, B>
513where
514    N: Eq,
515    B: Eq + Hash,
516{
517    fn eq(&self, other: &Self) -> bool {
518        (self.is_empty() && other.is_empty())
519            || (!self.is_empty()
520                && !other.is_empty()
521                && self.is_subtree_eq(
522                    self.get_root_idx().unwrap(),
523                    other,
524                    other.get_root_idx().unwrap(),
525                ))
526    }
527}
528
529impl<N, B> Eq for Tree<N, B>
530where
531    N: Eq,
532    B: Eq + Hash,
533{
534}
535
536impl<N, B> Tree<N, B> {
537    /// Creates a new empty generic tree over node data (`N`)
538    /// and branch data (`B`) types.
539    ///
540    /// # Examples
541    /// ```
542    /// use nb_tree::prelude::Tree;
543    /// let tree: Tree<usize, String> = Tree::new();
544    /// ```
545    pub fn new() -> Self {
546        Default::default()
547    }
548
549    /// Creates a new empty tree with at least the given capacity.
550    pub fn with_capacity(capacity: usize) -> Self {
551        Self {
552            nodes: Vec::with_capacity(capacity),
553            ..Default::default()
554        }
555    }
556
557    /// Reserves space for at least the given additional amount of nodes in the tree.
558    pub fn reserve(&mut self, additional: usize) {
559        self.nodes.reserve(additional)
560    }
561
562    /// Returns the value of the root node if there is one, returns None otherwise.
563    ///
564    /// # Examples
565    ///
566    /// ```rust
567    /// use nb_tree::prelude::Tree;
568    /// let mut tree: Tree<String, String> = Tree::new();
569    /// // The tree is empty
570    /// assert_eq!(tree.get_root(), None);
571    /// tree.i("/", "a".to_string());
572    ///
573    /// assert_eq!(tree.get_root(), Some(&"a".to_string()));
574    /// ```
575    pub fn get_root(&self) -> Option<&N> {
576        if self.is_empty() {
577            None
578        } else {
579            Some(&self.nodes[0].value)
580        }
581    }
582
583    /// Returns the index of the root node if there is one, returns None otherwise.
584    ///
585    /// There is no guaranty that the root node will always be 0.
586    fn get_root_idx(&self) -> Option<NodeIDX> {
587        (!self.is_empty()).then_some(0)
588    }
589
590    /// Inserts a value at the root and returns the previous value if there is one.
591    ///
592    /// # Examples
593    /// ```rust
594    /// use nb_tree::prelude::Tree;
595    /// let mut tree: Tree<String, String> = Tree::new();
596    /// assert_eq!(tree.insert_root("a".to_string()), None);
597    /// assert_eq!(tree.insert_root("b".to_string()), Some("a".to_string()));
598    /// ```
599    pub fn insert_root(&mut self, value: N) -> Option<N> {
600        if self.nodes.is_empty() {
601            // Initialize the tree with a root node
602            self.nodes.push(value.into());
603            None
604        } else if self.removed.last() == Some(&0) {
605            // Reinsert the removed node
606            self.removed.pop();
607            self.removed
608                .append(&mut self.nodes[0].children.values().cloned().collect());
609            self.nodes[0] = value.into();
610            self.nodes[0].children = Default::default();
611            None
612        } else {
613            // The root should not have been removed
614            debug_assert!(
615                !self.removed.contains(&0),
616                "Root has been removed but is not the most recent deletion"
617            );
618            // Replace the current value
619            Some(mem::replace(&mut self.nodes[0].value, value))
620        }
621    }
622
623    /// Removes all nodes from the tree.
624    fn clear(&mut self) {
625        *self = Tree::default();
626        /* Alternative not removing any node
627        if self.removed.last().map_or(true, |l| *l != 0) {
628            self.removed.push(0);
629        }*/
630    }
631
632    /// Returns true is the tree has no nodes.
633    ///
634    /// # Examples
635    /// ```rust
636    /// use nb_tree::prelude::Tree;
637    /// let mut tree: Tree<String, String> = Tree::new();
638    /// assert!(tree.is_empty());
639    /// tree.insert_root("a".to_string());
640    /// assert!(!tree.is_empty());
641    /// ```
642    pub fn is_empty(&self) -> bool {
643        self.nodes.is_empty() || self.removed.last() == Some(&0)
644    }
645
646    /// Return the number of nodes in the tree.
647    ///
648    /// # Examples
649    /// ```rust
650    /// use nb_tree::prelude::Tree;
651    /// let mut tree: Tree<usize, String> = Tree::new();
652    /// assert_eq!(tree.len(), 0);
653    /// tree.i("/", 10);
654    /// assert_eq!(tree.len(), 1);
655    /// tree.i("/a", 20)
656    ///     .i("/a/b", 30)
657    ///     .i("/a/b/z", 40)
658    ///     .i("/c", 50)
659    ///     .i("/c/d", 60);
660    /// assert_eq!(tree.len(), 6);
661    /// ```
662    pub fn len(&self) -> usize {
663        self.iter_on::<()>().count()
664    }
665
666    /// Returns a vector of references to the tree's node values in arbitrary order.
667    ///
668    /// # Examples
669    /// ```rust
670    /// use std::collections::HashSet;
671    /// use std::iter::FromIterator;
672    /// use nb_tree::prelude::Tree;
673    ///
674    /// let mut tree: Tree<usize, String> = Tree::new();
675    /// tree.i("/", 0)
676    ///     .i("/a", 1)
677    ///     .i("/a/b", 2);
678    /// let values: HashSet<usize> = HashSet::from_iter(vec![0,1,2].into_iter());
679    /// let tree_values: HashSet<usize> = HashSet::from_iter(tree.values().into_iter().cloned());
680    /// assert_eq!(
681    ///     tree_values,
682    ///     values);
683    /// ```
684    pub fn values(&self) -> Vec<&N> {
685        self.iter().map(|n| n.take()).collect()
686    }
687
688    /// Returns an iterator over [TreeIterTarget] data from each thee node
689    /// relatively to one another.
690    ///
691    /// The iterator returns [`Traversal`]s containing
692    /// the associated TreeIterTarget.
693    fn iter_on<'a, T: TreeIterTarget<'a, N, B>>(&'a self) -> Iter<'a, N, B, T> {
694        Iter::new(self)
695    }
696
697    /// Returns an depth first iterator over the tree's node data relatively to one another.
698    ///
699    /// The iterator returns [`Traversal`]s containing the associated node data.
700    /// If the tree is not empty, the first item is a [`Root`] node
701    /// containing a reference to the root node's data.
702    /// All subsequent items are [`Node`]s containing their position
703    /// relative to the previous item and a reference to the node's data.
704    ///
705    /// # Examples
706    ///
707    /// ```rust
708    /// use nb_tree::prelude::{iter::depth::Traversal, Path, Tree};
709    /// let mut tree: Tree<usize, String> = Tree::new();
710    /// tree.i("/", 0)
711    ///     .i("/a", 1)
712    ///     .i("/a/B", 10)
713    ///     .i("/a/B/i", 100)
714    ///     .i("/a/B/j", 200)
715    ///     .i("/a/C", 11)
716    ///     .i("/a/C/x", 111)
717    ///     .i("/a/C/y", 222);
718    /// let mut iter = tree.iter();
719    /// if let Traversal::Start(data) = iter.next().expect("Root node expected") {
720    ///     // The root node's data is 0
721    ///     assert_eq!(*data, 0);
722    /// } else {
723    ///     panic!("Expected a Root node");
724    /// }
725    /// if let Traversal::Step { up, branch, data } =
726    ///     iter.next().expect("Root child Node expected")
727    /// {
728    ///     // The node is below the root node
729    ///     assert_eq!(up, 0);
730    ///     // The node is at branch "a"
731    ///     assert_eq!(*branch, "a");
732    ///     // The node's data is 1
733    ///     assert_eq!(*data, 1);
734    /// } else {
735    ///     panic!("Expected a non Root node");
736    /// }
737    /// let mut path = Path::new();
738    /// for iter_node in tree {
739    ///     // Move up the path
740    ///     if iter_node.up() > 0 {
741    ///         for _ in 0..iter_node.up() {
742    ///             path.pop_last();
743    ///         }
744    ///         //
745    ///         println!(
746    ///             "{}╭{}┘ up",
747    ///             " ".repeat(path.to_string().len()),
748    ///             "──".repeat(iter_node.up()-1)
749    ///         );
750    ///     }
751    ///     // Get the branch if any (there is none for the Root)
752    ///     if let Some(branch) = iter_node.branch() {
753    ///         path.push_last(branch.clone());
754    ///     }
755    ///     // Get the data
756    ///     println!("{}: {}", path, iter_node.data());
757    /// }
758    /// ```
759    /// One possible output would be:
760    /// ```text
761    ///     /: 0
762    ///     /a: 1
763    ///     /a/B: 10
764    ///     /a/B/i: 100
765    ///         ╭┘ up
766    ///     /a/B/j: 200
767    ///       ╭──┘ up
768    ///     /a/C: 11
769    ///     /a/C/x: 111
770    ///         ╭┘ up
771    ///     /a/C/y: 222
772    /// ```
773    /// As the iteration order of children of a node is unknown,
774    /// "/a/C" can be visited before "/a/B", as can "/a/B/j" and "/a/B/i"
775    /// as well as "/a/C/y" and "/a/C/x".
776    pub fn iter(&self) -> Iter<N, B, &N> {
777        self.iter_on()
778    }
779}
780
781impl<N, B> Tree<N, B>
782where
783    B: Eq + Hash,
784{
785    /// Returns the index of the node pointed to by the given [path].
786    ///
787    /// If the node doesn't exist, it returns the index of the closest
788    /// existing node in the tree and the index of the inexistent child in [path].
789    /// If the tree is empty, None is returned.
790    fn get_idx(
791        &self,
792        path: &Path<B>,
793        from_idx: Option<NodeIDX>,
794    ) -> Result<NodeIDX, Option<(NodeIDX, PathIDX)>> {
795        let root_idx = if let Some(idx) = self.get_root_idx() {
796            idx
797        } else {
798            return Err(None);
799        };
800        path.iter().enumerate().try_fold(
801            from_idx.unwrap_or(root_idx),
802            |node_idx, (path_idx, branch)| {
803                self.nodes[node_idx]
804                    .children
805                    .get(branch)
806                    .cloned()
807                    .ok_or(Some((node_idx, path_idx)))
808            },
809        )
810    }
811
812    /// Returns a vector of the index of every node along the given [path].
813    ///
814    /// If a node doesn't exist, the index vector up until this node is returned
815    /// as well as the index of the inexistent child in [path].
816    /// If the tree is empty, None is returned.
817    fn get_path_idxs(&self, path: &Path<B>) -> Result<Vec<NodeIDX>, Option<(Vec<NodeIDX>, usize)>> {
818        let root_idx = if let Some(idx) = self.get_root_idx() {
819            idx
820        } else {
821            return Err(None);
822        };
823        path.iter()
824            .enumerate()
825            .try_fold(vec![root_idx], |mut node_idx, (path_idx, branch)| {
826                node_idx.push(
827                    self.nodes[*node_idx.last().unwrap()]
828                        .children
829                        .get(branch)
830                        .cloned()
831                        //NOTE: No way to do without the cloning? (E0505)
832                        .ok_or(Some((node_idx.clone(), path_idx)))?,
833                );
834                Ok(node_idx)
835            })
836    }
837
838    /// Inserts a value as the [child] node of the given parent.
839    ///
840    /// # Warning
841    /// Does not check the validity of [parent_idx].
842    fn insert_at(&mut self, parent_idx: NodeIDX, child: B, value: N) -> (Option<N>, NodeIDX) {
843        // Child exists?
844        if let Some(child_idx) = self.nodes[parent_idx].children.get(&child).cloned() {
845            (
846                Some(mem::replace(&mut self.nodes[child_idx].value, value)),
847                child_idx,
848            )
849        } else {
850            // Get a node
851            let idx = if let Some(idx) = self.removed.pop() {
852                // Use a removed one
853                self.removed
854                    .append(&mut self.nodes[idx].children.values().cloned().collect());
855                self.nodes[idx] = From::from(value);
856                self.nodes[parent_idx].children.insert(child, idx);
857                idx
858            } else {
859                let idx = self.nodes.len();
860                // Extend the vec
861                self.nodes.push(From::from(value));
862                //NOTE: Any way to do without the variable? (E0502)
863                self.nodes[parent_idx].children.insert(child, idx);
864                idx
865            };
866
867            (None, idx)
868        }
869    }
870
871    /// Removes the subtree at the [child] of the given parent node.
872    ///
873    /// # Warning
874    /// Does not check [parent_idx]'s validity
875    fn remove_subtree_at(&mut self, parent_idx: NodeIDX, child: B) -> Option<NodeIDX> {
876        let idx = self.nodes[parent_idx].children.remove(&child)?;
877        self.remove_subtree_idx(idx)
878    }
879
880    /// Adds the subtree at the given [idx] to the `removed` array.
881    ///
882    /// # Warning
883    /// Does not check [idx]'s validity
884    fn remove_subtree_idx(&mut self, idx: NodeIDX) -> Option<NodeIDX> {
885        self.removed.push(idx);
886        Some(idx)
887    }
888}
889
890impl<N, B> Tree<N, B>
891where
892    B: Eq + Hash + Clone,
893{
894    /// Returns a reference to the value of the node at the given [path].
895    /// If the path leaves the tree, the path to the last node in the tree on the given path is returned, or None if the tree is empty.
896    /// # Examples
897    /// ```
898    /// use nb_tree::prelude::Tree;
899    /// let mut tree: Tree<usize, String> = Tree::new();
900    /// // Can't get any node from an empty node
901    /// assert_eq!(tree.get(&"/a/b/w".into()), Err(None));
902    /// tree.i("/", 0)
903    ///     .i("/a", 1)
904    ///     .i("/a/b", 2)
905    ///     .i("/c", 3);
906    /// // Get a reference to the node data at "/a"
907    /// assert_eq!(tree.get(&"/a".into()), Ok(&1));
908    /// // "/a/b/w" is out of the tree, "/a/b" being the last node in the tree of the path
909    /// assert_eq!(tree.get(&"/a/b/w".into()), Err(Some("/a/b".into())));
910    /// ```
911    pub fn get(&self, path: &Path<B>) -> Result<&N, Option<Path<B>>> {
912        Ok(&self.nodes[self
913            .get_idx(path, None)
914            .map_err(|r| r.map(|(_, i)| path.path_to(i)))?]
915        .value)
916    }
917
918    /// Returns a mutable reference to the value of the node at the given [path].
919    /// If the path leaves the tree, the path to the last node in the tree on the given path is returned, or None if the tree is empty.
920    /// # Examples
921    /// ```
922    /// use nb_tree::prelude::Tree;
923    /// let mut tree: Tree<usize, String> = Tree::new();
924    /// // Can't get any node from an empty node
925    /// assert_eq!(tree.get(&"/a/b/w".into()), Err(None));
926    /// tree.i("/", 0)
927    ///     .i("/a", 1)
928    ///     .i("/a/b", 2)
929    ///     .i("/c", 3);
930    /// // Get a reference to the node data at "/a"
931    /// assert_eq!(tree.get_mut(&"/a".into()), Ok(&mut 1));
932    /// // "/a/b/w" is out of the tree, "/a/b" being the last node in the tree of the path
933    /// assert_eq!(tree.get_mut(&"/a/b/w".into()), Err(Some("/a/b".into())));
934    /// ```
935    pub fn get_mut(&mut self, path: &Path<B>) -> Result<&mut N, Option<Path<B>>> {
936        let idx = self
937            .get_idx(path, None)
938            .map_err(|r| r.map(|(_, i)| path.path_to(i)))?;
939        Ok(&mut self.nodes[idx].value)
940    }
941
942    /// Returns an [Entry] with read only access to the root node's position.
943    ///
944    /// # Examples
945    /// ```
946    /// use nb_tree::prelude::Tree;
947    /// let mut tree: Tree<usize, String> = Tree::new();
948    /// let entry = tree.root_entry();
949    /// assert!(!entry.is_node());
950    /// tree.i("/", 7)
951    ///     .i("/c1", 1);
952    /// let mut entry = tree.root_entry();
953    /// assert_eq!(entry.value(), Some(&7));
954    /// entry.move_down_branch("c1".into());
955    /// assert_eq!(entry.value(), Some(&1));
956    /// ```
957    pub fn root_entry(&self) -> Entry<&Self, N, B, TREEBOUND> {
958        match self.get_root_idx() {
959            Some(root) => {
960                Node::from(self, AttachedPosition::from(Path::new(), Path::with(root))).into()
961            }
962            None => {
963                DetachedEntry::from(self, DetachedPosition::from(Path::new(), Path::new())).into()
964            }
965        }
966    }
967
968    /// Returns an [Entry] with mutable access to the root node's position.
969    ///
970    /// # Examples
971    /// ```
972    /// use nb_tree::prelude::Tree;
973    /// let mut tree: Tree<usize, String> = Tree::new();
974    /// let mut entry = tree.root_entry_mut();
975    /// assert!(!entry.is_node());
976    /// assert_eq!(entry.or_insert(5), &mut 5);
977    /// entry.move_down_branch("c1".into());
978    /// assert_eq!(entry.or_insert(1), &mut 1);
979    /// ```
980    pub fn root_entry_mut(&mut self) -> Entry<&mut Self, N, B, TREEBOUND> {
981        match self.get_root_idx() {
982            Some(root) => {
983                Node::from(self, AttachedPosition::from(Path::new(), Path::with(root))).into()
984            }
985            None => {
986                DetachedEntry::from(self, DetachedPosition::from(Path::new(), Path::new())).into()
987            }
988        }
989    }
990
991    /// Returns an [Entry] with read only access to the given position in the tree.
992    ///
993    /// # Examples
994    /// ```
995    /// use nb_tree::prelude::Tree;
996    /// let mut tree: Tree<usize, String> = Tree::new();
997    /// tree.i("/", 0)
998    ///     .i("/a", 1)
999    ///     .i("/a/b", 2)
1000    ///     .i("/c", 3);
1001    /// let entry = tree.entry(&"/a/b".into());
1002    /// assert_eq!(entry.value(), Some(&2));
1003    /// ```
1004    pub fn entry(&self, path: &Path<B>) -> Entry<&Self, N, B, TREEBOUND> {
1005        Self::get_entry(self, path)
1006    }
1007
1008    /// Returns an [Entry] with mutable access to the given position in the tree.
1009    ///
1010    /// # Examples
1011    /// ```
1012    /// use nb_tree::prelude::Tree;
1013    /// let mut tree: Tree<usize, String> = Tree::new();
1014    /// tree.i("/", 0)
1015    ///     .i("/a", 1)
1016    ///     .i("/a/b", 2)
1017    ///     .i("/c", 3);
1018    /// let mut entry = tree.entry_mut(&"/a/b/d".into());
1019    /// assert_eq!(entry.or_insert(4), &mut 4);
1020    /// ```
1021    pub fn entry_mut(&mut self, path: &Path<B>) -> Entry<&mut Self, N, B, TREEBOUND> {
1022        Self::get_entry(self, path)
1023    }
1024
1025    /// Returns an Entry to the given position in the given tree.
1026    fn get_entry<R: Deref<Target = Tree<N, B>>>(s: R, path: &Path<B>) -> Entry<R, N, B, TREEBOUND> {
1027        match s.get_path_idxs(path) {
1028            Ok(idxs) => Node::from(s, AttachedPosition::from(path.clone(), idxs.into())).into(),
1029            Err(e) => DetachedEntry::from(
1030                s,
1031                DetachedPosition::from(
1032                    path.clone(),
1033                    e.map(|(idxs, _)| idxs.into()).unwrap_or_default(),
1034                ),
1035            )
1036            .into(),
1037        }
1038    }
1039
1040    /// Inserts a value at the given [path].
1041    /// Returns the existing value if any.
1042    /// Insertions can be done on any existing node ([path] points to an existing node)
1043    /// or on children of existing nodes ([path] points to
1044    /// an inexistent immediate child of an existing node).
1045    /// Insertions cannot be done if [path] points to a node further away
1046    /// from the existing tree as it cannot close the gap between the last
1047    /// existing node and the new one to insert.
1048    /// In this case the operation will fail and the [Path] to the closest
1049    /// existing node will be returned.
1050    ///
1051    /// # Examples
1052    ///
1053    /// ```
1054    /// use nb_tree::prelude::Tree;
1055    /// let mut tree: Tree<_, String> = Tree::new();
1056    /// // Set root
1057    /// assert_eq!(tree.insert(&"/".into(), 0), Ok(None));
1058    /// // Append node
1059    /// assert_eq!(tree.insert(&"/a".into(), 1), Ok(None));
1060    /// // Overwrite existing node
1061    /// assert_eq!(tree.insert(&"/a".into(), 2), Ok(Some(1)));
1062    /// // Leave tree
1063    /// assert_eq!(tree.insert(&"/a/b/c".into(), 2), Err(Some("/a".into())));
1064    /// ```
1065    pub fn insert(&mut self, path: &Path<B>, value: N) -> Result<Option<N>, Option<Path<B>>> {
1066        let mut path = path.clone();
1067        if let Some(child) = path.pop_last() {
1068            Ok(self
1069                .insert_at(
1070                    self.get_idx(&path, None)
1071                        .map_err(|r| r.map(|(_, i)| path.path_to(i)))?,
1072                    child,
1073                    value,
1074                )
1075                .0)
1076        } else {
1077            Ok(self.insert_root(value))
1078        }
1079    }
1080
1081    //TODO: Remove the nodes immediately and return the nodes as a Tree
1082    /// Removes the subtree at the given [path] from the tree
1083    /// If the root node is not found, it returns the path to the closest
1084    /// existing node, or None if the tree is empty.
1085    /// # Examples
1086    /// ```
1087    /// use nb_tree::prelude::Tree;
1088    /// let mut tree1: Tree<usize, String> = Tree::new();
1089    /// tree1.insert(&"/".into(), 0);
1090    /// tree1.insert(&"/a".into(), 1);
1091    /// tree1.insert(&"/a".into(), 2);
1092    /// tree1.insert(&"/b".into(), 3);
1093    /// let mut tree2 = tree1.clone();
1094    ///
1095    /// // Add a branch to tree2
1096    /// tree2.insert(&"/c".into(), 4);
1097    /// tree2.insert(&"/c/d".into(), 5);
1098    ///
1099    /// // Remove the branch
1100    /// tree2.remove_subtree(&"/c".into());
1101    /// assert_eq!(tree1, tree2);
1102    /// ```
1103    pub fn remove_subtree(&mut self, path: &Path<B>) -> Result<(), Option<Path<B>>> {
1104        let mut path = path.clone();
1105        if self.is_empty() {
1106            Err(None)
1107        } else if let Some(child) = path.pop_last() {
1108            // Remove a node
1109            let parent_idx = self
1110                .get_idx(&path, None)
1111                .map_err(|r| r.map(|(_, i)| path.path_to(i)))?;
1112            self.remove_subtree_at(parent_idx, child)
1113                .map(|_| ())
1114                .ok_or(Some(path))
1115        } else {
1116            // Root is being removed
1117            self.nodes.clear();
1118            self.removed.clear();
1119            Ok(())
1120        }
1121    }
1122
1123    /// Applies the differential to the tree without checking its validity beforehand
1124    ///
1125    /// Nodes that can't be added or removed are skipped.
1126    ///
1127    /// # Examples
1128    /// ```
1129    /// use nb_tree::prelude::{Tree, DiffTree};
1130    /// let mut tree1: Tree<usize, String> = Tree::new();
1131    /// tree1.i("/", 0)
1132    ///     .i("/a", 1)
1133    ///     .i("/a/b", 2)
1134    ///     .i("/c", 3);
1135    /// let mut diff: DiffTree<usize, String> = DiffTree::new();
1136    /// diff.i("/", (Some(0), Some(9)))
1137    ///     .i("/a", (Some(1), Some(2)))
1138    ///     .i("/a/w", (Some(2), Some(100)))
1139    ///     .i("/x", (Some(40), None))
1140    ///     .i("/z", (None, Some(200)))
1141    ///     .i("/c", (None, Some(4)));
1142    /// tree1.force_apply(diff);
1143    ///
1144    /// let mut tree_applied: Tree<usize, String> = Tree::new();
1145    /// tree_applied.i("/", 9)
1146    ///     .i("/a", 2)
1147    ///     .i("/a/b", 2)
1148    ///     .i("/a/w", 100)
1149    ///     .i("/z", 200)
1150    ///     .i("/c", 4);
1151    /// assert_eq!(tree1, tree_applied);
1152    /// ```
1153    pub fn force_apply(&mut self, diff: DiffTree<N, B>) -> bool {
1154        self.force_apply_with(
1155            diff,
1156            |entry, now| entry.insert(now).is_some(),
1157            |entry| {
1158                replace_with_or_abort(entry, |e| e.remove_subtree());
1159                true
1160            },
1161        )
1162    }
1163    pub fn force_apply_with<'a>(
1164        &'a mut self,
1165        diff: DiffTree<N, B>,
1166        insert: InsertWith<&'a mut Tree<N, B>, N, B, false>,
1167        delete: DeleteWith<&'a mut Tree<N, B>, N, B, false>,
1168    ) -> bool {
1169        let mut apply_success = true;
1170        let mut diff = diff.into_iter();
1171        // Manage the root
1172        let mut entry = self.entry_mut(&Path::new());
1173        let mut deleted = None;
1174        match diff.next() {
1175            Some(Traversal::Start((b, n))) => {
1176                if let Some(now) = n {
1177                    // New or change node
1178                    apply_success = insert(&mut entry, now);
1179                } else if b.is_some() {
1180                    // Remove node
1181                    // Deleted root prevents any further change
1182                    delete(&mut entry);
1183                    return diff.next().is_none();
1184                }
1185            }
1186            None => {
1187                // Empty diff
1188                return true;
1189            }
1190            Some(_) => {
1191                unreachable!("Tree iteration should always start with a Root node");
1192            }
1193        };
1194
1195        for d in diff {
1196            entry.apply_move(&d);
1197            if let Some(d) = deleted {
1198                // Remove if at the same path level (the targetted node
1199                // will thus have changed)
1200                if d >= entry.path().len() {
1201                    deleted = None;
1202                }
1203            }
1204            let (b, n) = d.take();
1205
1206            if let Some(now) = n {
1207                // New or change node
1208                if deleted.is_some() {
1209                    apply_success = false;
1210                } else if !insert(&mut entry, now) {
1211                    // Extend needed
1212                    apply_success = false;
1213                }
1214            } else if b.is_some() {
1215                // Remove node
1216                if deleted.is_none() {
1217                    deleted = Some(entry.path().len());
1218                    if entry.is_node() {
1219                        delete(&mut entry);
1220                    } else {
1221                        apply_success = false;
1222                    }
1223                } // else if a parent has been deleted, no further deleting is necessary
1224            }
1225        }
1226        apply_success
1227    }
1228
1229    /// Combines two trees together following a given mode
1230    ///
1231    /// The mode specifies whether to :
1232    ///     - keep the nodes only present in the initial tree
1233    ///     - grow the tree with nodes only present in the other tree
1234    ///     - overwrite the nodes' data with the ones of the other tree
1235    ///
1236    /// # Examples
1237    /// ```
1238    /// use nb_tree::prelude::Tree;
1239    /// use nb_tree::tree::CombinationMode;
1240    /// let mut tree1: Tree<usize, String> = Tree::new();
1241    /// tree1.i("/", 0)
1242    ///     .i("/a", 1)
1243    ///     .i("/a/b", 2)
1244    ///     .i("/c", 3);
1245    ///
1246    /// let mut tree2: Tree<usize, String> = Tree::new();
1247    /// tree2.i("/", 10)
1248    ///      .i("/a", 11)
1249    ///      .i("/a/d", 7);
1250    ///
1251    /// tree1.combine(tree2, CombinationMode::Free{keep: true, grow: true, overwrite: true});
1252    /// let mut tree_res = Tree::new();
1253    /// tree_res.i("/", 10)
1254    ///         .i("/a", 11)
1255    ///         .i("/a/d", 7)
1256    ///         .i("/a/b", 2)
1257    ///         .i("/c", 3);
1258    ///
1259    /// assert_eq!(tree1, tree_res);
1260    /// ```
1261    pub fn combine(&mut self, tree: Tree<N, B>, mode: CombinationMode) -> bool {
1262        self.combine_with(tree, mode, |entry, now| entry.insert(now).is_some())
1263    }
1264
1265    pub(crate) fn combine_with<'a>(
1266        &'a mut self,
1267        tree: Tree<N, B>,
1268        mode: CombinationMode,
1269        grow: InsertWith<&'a mut Tree<N, B>, N, B, false>,
1270    ) -> bool {
1271        let mut entry = self.root_entry_mut();
1272        let iter: IntoIter<N, B, TreeNode<N, B>> = IntoIter::new(tree);
1273
1274        for step in iter {
1275            // check if above root node
1276            if entry.apply_move(&step).is_err() {
1277                // left the (sub)tree
1278                // return before iteration end
1279                return false;
1280            }
1281            if let Some(node) = entry.node_mut() {
1282                // remove ignored if not kept
1283                if !mode.keep() {
1284                    node.remove_child_subtrees(
1285                        node.children()
1286                            .into_iter()
1287                            .filter(|&c| step.data().children.contains_key(c))
1288                            .cloned()
1289                            .collect(),
1290                    );
1291                }
1292                if mode.overwrite() {
1293                    // overwrite
1294                    node.insert(step.take().value);
1295                }
1296            } else if mode.grow() {
1297                // grow
1298                grow(&mut entry, step.take().value);
1299            }
1300        }
1301        true
1302    }
1303}
1304
1305type InsertWith<R, N, B, const BND: bool> = fn(&mut Entry<R, N, B, BND>, N) -> bool;
1306type DeleteWith<R, N, B, const BND: bool> = fn(&mut Entry<R, N, B, BND>) -> bool;
1307
1308/// Description of how two trees will be combinedthe way the way
1309pub enum CombinationMode {
1310    /// Keeps and grows the tree, overwriting the data if the boolean is set to true
1311    Union(bool),
1312    /// Only keeps nodes common to both trees, overwriting the data if the boolean is set to true
1313    Intersection(bool),
1314    /// Specify manually the data to be kept and removed
1315    Free {
1316        /// Keep nodes only present in the first tree
1317        keep: bool,
1318        /// Keep nodes only present in the second tree
1319        grow: bool,
1320        /// Overwrites data in nodes common to both trees
1321        overwrite: bool,
1322    },
1323}
1324
1325impl CombinationMode {
1326    pub fn keep(&self) -> bool {
1327        use CombinationMode::*;
1328        match self {
1329            Union(_) => true,
1330            Intersection(_) => false,
1331            Free { keep, .. } => *keep,
1332        }
1333    }
1334    pub fn grow(&self) -> bool {
1335        use CombinationMode::*;
1336        match self {
1337            Union(_) => true,
1338            Intersection(_) => false,
1339            Free { grow, .. } => *grow,
1340        }
1341    }
1342    pub fn overwrite(&self) -> bool {
1343        use CombinationMode::*;
1344        match self {
1345            Union(overwrite) => *overwrite,
1346            Intersection(overwrite) => *overwrite,
1347            Free { overwrite, .. } => *overwrite,
1348        }
1349    }
1350}
1351
1352impl<N, B> Tree<N, B>
1353where
1354    B: Eq + Hash + Clone + Dbg,
1355{
1356    /// Chainable insertion
1357    /// Calls `insert` and returns a mutable reference to self
1358    /// # Panics
1359    /// Panics if the insertion fails
1360    pub fn i(&mut self, path: impl Into<Path<B>>, value: N) -> &mut Self {
1361        let ph: Path<B> = path.into();
1362        self.insert(&ph, value)
1363            .unwrap_or_else(|_| panic!("Could not insert into the tree at {:?}", &ph));
1364        self
1365    }
1366}
1367
1368impl<N, B> Tree<N, B>
1369where
1370    N: Eq,
1371    B: Eq + Hash,
1372{
1373    /// # Warning
1374    /// It does not check for index validity.
1375    fn is_subtree_eq(&self, idx_s: usize, o: &Self, idx_o: usize) -> bool {
1376        let ns = &self.nodes[idx_s];
1377        let no = &o.nodes[idx_o];
1378        ns.value == no.value
1379            && ns.children.len() == no.children.len()
1380            && !ns.children.keys().any(|branch| {
1381                !self.is_subtree_eq(
1382                    *or_return!(ns.children.get(branch), false),
1383                    o,
1384                    *or_return!(no.children.get(branch), false),
1385                )
1386            })
1387    }
1388}
1389impl<N, B> Tree<N, B>
1390where
1391    N: Eq,
1392    B: Eq + Hash + Clone,
1393{
1394    /// Applies the differential to the tree if it is valid
1395    ///
1396    /// # Examples
1397    /// ```
1398    /// use nb_tree::prelude::Tree;
1399    /// let mut tree1: Tree<usize, String> = Tree::new();
1400    /// tree1.i("/", 0)
1401    ///     .i("/a", 1)
1402    ///     .i("/a/b", 2)
1403    ///     .i("/c", 3)
1404    ///     .i("/f", 4)
1405    ///     .i("/f/d", 5);
1406    /// let mut tree2: Tree<usize, String> = Tree::new();
1407    /// tree2
1408    ///     .i("/", 9)
1409    ///     .i("/a", 2)
1410    ///     .i("/a/b", 1)
1411    ///     .i("/c", 3)
1412    ///     .i("/c/d", 4)
1413    ///     .i("/c/d/e", 2);
1414    /// let mut diff = tree1.diff(&tree2);
1415    /// // taking back `tree1`, `tree2` and `diff` from the previous example
1416    /// let tree1_orig = tree1.clone();
1417    /// // Apply the differential between `tree1` and `tree2`
1418    /// tree1.apply(diff.clone()).unwrap();
1419    /// // They are both equal now
1420    /// assert_eq!(tree1, tree2, "Both trees are not equal");
1421    /// // Applying the reversed diff will restore tree1
1422    /// diff.rev();
1423    /// tree1.apply(diff).unwrap();
1424    /// assert_eq!(tree1, tree1_orig);
1425    /// ```
1426    pub fn apply(&mut self, diff: DiffTree<N, B>) -> Result<bool, DiffApplyError<B>> {
1427        // Check diff
1428        diff.is_applicable(self)?;
1429
1430        // Apply diff
1431        Ok(self.force_apply(diff))
1432    }
1433
1434    /// Applies a DiffNode at the given Path in the tree
1435    ///
1436    /// # Examples
1437    /// ```
1438    /// use nb_tree::prelude::Tree;
1439    /// let mut tree1: Tree<usize, String> = Tree::new();
1440    /// tree1.i("/", 0)
1441    ///     .i("/a", 1)
1442    ///     .i("/a/b", 2)
1443    ///     .i("/c", 3);
1444    /// let mut tree2 = tree1.clone();
1445    /// tree2.i("/a/b/d", 7);
1446    /// tree1.apply_diff("/a/b/d".into(), (None, Some(7)));
1447    /// assert_eq!(tree1, tree2);
1448    /// ```
1449    pub fn apply_diff(
1450        &mut self,
1451        path: Path<B>,
1452        diff: DiffNode<N>,
1453    ) -> Result<(), DiffApplyError<B>> {
1454        self.apply_diff_with(path, diff, |entry, v| {
1455            if entry.offshoot_len() <= 1 {
1456                entry.insert(v);
1457                Ok(())
1458            } else {
1459                Err(DiffApplyError::Other("Expected Parent".to_string()))
1460            }
1461        })
1462    }
1463
1464    /// Applies the DiffNode at the given Path according to the given insertion function
1465    fn apply_diff_with(
1466        &mut self,
1467        path: Path<B>,
1468        diff: DiffNode<N>,
1469        insert: fn(&mut TreeMutEntry<N, B, TREEBOUND>, N) -> Result<(), DiffApplyError<B>>,
1470    ) -> Result<(), DiffApplyError<B>> {
1471        let mut entry = self.entry_mut(&path);
1472        if diff.0.is_some() {
1473            if entry.is_detached() {
1474                return Err(DiffApplyError::Expected(path));
1475            }
1476            if let Some(value) = diff.1 {
1477                // Change
1478                entry.insert(value);
1479                Ok(())
1480            } else {
1481                // Delete
1482                entry.remove_subtree();
1483                Ok(())
1484            }
1485        } else if let Some(value) = diff.1 {
1486            // New or change
1487            insert(&mut entry, value)
1488        } else {
1489            Ok(())
1490        }
1491    }
1492
1493    /// Applies a DiffMap to the tree
1494    ///
1495    /// Returns true if all diffs have been applied, and false otherwise
1496    pub fn apply_map(&mut self, map: DiffMap<N, B>) -> bool {
1497        map.into_iter().fold(true, |mut res, (ph, diff)| {
1498            if self.apply_diff(ph, diff).is_err() {
1499                res = false;
1500            }
1501            res
1502        })
1503    }
1504}
1505
1506#[cfg(test)]
1507mod tests {
1508    use std::collections::{HashMap, HashSet};
1509
1510    use test_log::test;
1511    use tracing::{debug, trace};
1512
1513    use crate::prelude::{iter::depth::Traversal, DiffTree, Tree};
1514
1515    fn new_tree() -> Tree<usize, String> {
1516        let mut tree: Tree<usize, String> = Tree::new();
1517        tree.i("/", 0)
1518            .i("/a", 1)
1519            .i("/a/b", 2)
1520            .i("/c", 3)
1521            .i("/f", 4)
1522            .i("/f/d", 5);
1523        tree
1524    }
1525
1526    #[test]
1527    fn index() {
1528        let mut tree1 = new_tree();
1529        assert_eq!(tree1[&"/".into()], 0);
1530        assert_eq!(tree1[&"/a".into()], 1);
1531        assert_eq!(tree1[&"/f/d".into()], 5);
1532        tree1.i("/z", 2);
1533        assert_eq!(tree1[&"/z".into()], 2);
1534    }
1535
1536    #[test]
1537    #[should_panic]
1538    fn index_inexistent1() {
1539        let tree1 = new_tree();
1540        tree1[&"/w".into()];
1541    }
1542
1543    #[test]
1544    #[should_panic]
1545    fn index_inexistent2() {
1546        let tree1 = new_tree();
1547        tree1[&"/f/d/z".into()];
1548    }
1549
1550    #[test]
1551    #[should_panic]
1552    fn index_inexistent3() {
1553        let tree1 = new_tree();
1554        tree1[&"/f/a".into()];
1555    }
1556
1557    #[test]
1558    fn eq_tree() {
1559        let tree1 = new_tree();
1560        // Same
1561        assert_eq!(tree1, new_tree());
1562        // Empty
1563        assert_eq!(Tree::<usize, usize>::new(), Tree::<usize, usize>::new());
1564        // Different branch
1565        let mut tree_branch = new_tree();
1566        tree_branch.i("/w", 7);
1567        assert_ne!(tree1, tree_branch);
1568        // Different value
1569        let mut tree_value = new_tree();
1570        tree_value.i("/a", 7);
1571        assert_ne!(tree1, tree_value);
1572        // One is empty
1573        assert_ne!(tree1, Tree::<usize, String>::new());
1574    }
1575
1576    #[test]
1577    fn new() {
1578        let tree1: Tree<usize, String> = Tree::new();
1579        assert!(tree1.is_empty());
1580    }
1581
1582    #[test]
1583    fn get_root() {
1584        let mut tree1: Tree<usize, String> = Tree::new();
1585        assert!(tree1.get_root().is_none());
1586        tree1.i("/", 5);
1587        assert_eq!(tree1.get_root(), Some(&5));
1588    }
1589
1590    #[test]
1591    fn get_root_idx() {
1592        let mut tree1: Tree<usize, String> = Tree::new();
1593        assert!(tree1.get_root().is_none());
1594        tree1.i("/", 5);
1595        assert!(tree1.get_root().is_some());
1596    }
1597
1598    #[test]
1599    fn insert_root() {
1600        let mut tree1: Tree<usize, String> = Tree::new();
1601        assert_eq!(tree1.insert_root(0), None);
1602        assert_eq!(tree1.len(), 1);
1603        assert_eq!(tree1.insert_root(1), Some(0));
1604        assert_eq!(tree1.insert_root(1), Some(1));
1605        assert_eq!(tree1.insert_root(2), Some(1));
1606        assert_eq!(tree1.insert_root(3), Some(2));
1607        tree1.clear();
1608        assert_eq!(tree1.insert_root(1), None);
1609        assert_eq!(tree1.insert_root(3), Some(1));
1610        tree1.i("/branch", 7);
1611        assert_eq!(tree1.len(), 2);
1612        assert_eq!(tree1.insert_root(5), Some(3));
1613        assert_eq!(tree1.len(), 2);
1614        assert_eq!(tree1.get_root(), Some(&5));
1615    }
1616
1617    #[test]
1618    fn clear() {
1619        let mut tree1: Tree<usize, String> = new_tree();
1620        tree1.clear();
1621        assert_eq!(tree1, Tree::new());
1622        tree1.i("/", 1);
1623        let mut small_tree = Tree::new();
1624        small_tree.i("/", 1);
1625        assert_eq!(tree1, small_tree);
1626        tree1.clear();
1627        assert_eq!(tree1, Tree::new());
1628        tree1.i("/", 1);
1629        tree1.i("/i", 2);
1630        tree1.i("/v", 2);
1631        tree1.i("/c", 5);
1632        tree1.i("/c/d", 3);
1633        tree1.remove_subtree(&"/c".into()).unwrap();
1634        tree1.remove_subtree(&"/i".into()).unwrap();
1635        tree1.remove_subtree(&"/v".into()).unwrap();
1636        assert_eq!(tree1, small_tree);
1637        tree1.clear();
1638        assert_eq!(tree1, Tree::new());
1639    }
1640
1641    #[test]
1642    fn is_empty() {
1643        let mut tree1: Tree<usize, String> = Tree::new();
1644        assert!(tree1.is_empty());
1645        tree1.i("/", 0);
1646        assert!(!tree1.is_empty());
1647        tree1.clear();
1648        assert!(tree1.is_empty());
1649        tree1.ix("/a", 1);
1650        assert!(!tree1.is_empty());
1651    }
1652
1653    #[test]
1654    fn len() {
1655        let mut tree1: Tree<usize, String> = Tree::new();
1656        assert_eq!(tree1.len(), 0);
1657        tree1.i("/", 1);
1658        assert_eq!(tree1.len(), 1);
1659        tree1.i("/a", 5);
1660        assert_eq!(tree1.len(), 2);
1661        tree1.i("/", 3);
1662        assert_eq!(tree1.len(), 2);
1663        tree1.i("/a/c", 6);
1664        assert_eq!(tree1.len(), 3);
1665        tree1.i("/a/c/d", 4);
1666        assert_eq!(tree1.len(), 4);
1667        tree1.i("/b", 8);
1668        assert_eq!(tree1.len(), 5);
1669        tree1.i("/b/e", 9);
1670        assert_eq!(tree1.len(), 6);
1671        tree1.remove_subtree(&"/a".into()).unwrap();
1672        assert_eq!(tree1.len(), 3);
1673        tree1.ix("/a/c", 1);
1674        assert_eq!(tree1.len(), 5);
1675        tree1.insert_root(10);
1676        assert_eq!(tree1.len(), 5);
1677        tree1.clear();
1678        assert_eq!(tree1.len(), 0);
1679        tree1.insert_root(100);
1680        assert_eq!(tree1.len(), 1);
1681    }
1682
1683    #[test]
1684    fn values() {
1685        let mut tree1 = new_tree();
1686        tree1.i("/z", 2);
1687        let values: HashSet<usize> = HashSet::from_iter([0, 1, 2, 3, 4, 5, 2].into_iter());
1688        let tree_values: HashSet<usize> = HashSet::from_iter(tree1.values().into_iter().cloned());
1689        assert_eq!(tree_values, values);
1690    }
1691
1692    #[test]
1693    fn iter_iter_on() {
1694        let tree1 = new_tree();
1695        let mut iter = tree1.iter_on::<()>();
1696
1697        match iter.next().expect("Root node expected") {
1698            Traversal::Start(()) => (),
1699            _ => panic!("Expected a Root node"),
1700        }
1701        match iter.next().expect("Root child Node expected") {
1702            Traversal::Step {
1703                up,
1704                branch,
1705                data: (),
1706            } => {
1707                assert_eq!(up, 0);
1708                // The node is at branch "a"
1709                assert!(["a", "c", "f"].contains(&branch.as_str()));
1710            }
1711            _ => panic!("Expected Root child node"),
1712        }
1713
1714        let mut tree2: Tree<Option<usize>, String> = Tree::new();
1715        tree2
1716            .i("/", Some(0))
1717            .i("/a", Some(1))
1718            .i("/a/b", Some(2))
1719            .i("/c", Some(3))
1720            .i("/f", Some(4))
1721            .i("/f/d", Some(5));
1722        let mut entry = tree2.root_entry_mut();
1723        let mut iter = tree1.iter();
1724        if let Traversal::Start(root) = iter.next().unwrap() {
1725            assert_eq!(entry.value().unwrap(), &Some(*root));
1726            entry.insert(None);
1727        } else {
1728            panic!("Expected a Root node")
1729        }
1730        for item in iter {
1731            if let Traversal::Step { up, branch, data } = item {
1732                entry.move_up(up);
1733                entry.move_down_branch(branch.clone());
1734                assert_eq!(
1735                    entry
1736                        .value()
1737                        .expect("Node inexistent")
1738                        .expect("Node already visited"),
1739                    *data
1740                );
1741                entry.insert(None);
1742            } else {
1743                panic!("Expected a Node")
1744            }
1745        }
1746        assert!(!tree2.iter().any(|item| item.data().is_some()));
1747    }
1748
1749    #[test]
1750    fn get_idx_path_idxs() {
1751        let mut tree1 = new_tree();
1752        let mut map = HashMap::new();
1753        map.insert("/", tree1.get_idx(&"/".into(), None).unwrap());
1754        map.insert("/a", tree1.get_idx(&"/a".into(), None).unwrap());
1755        map.insert("/a/b", tree1.get_idx(&"/a/b".into(), None).unwrap());
1756        map.insert("/c", tree1.get_idx(&"/c".into(), None).unwrap());
1757        map.insert("/f", tree1.get_idx(&"/f".into(), None).unwrap());
1758        map.insert("/f/d", tree1.get_idx(&"/f/d".into(), None).unwrap());
1759        let values: HashSet<usize> = HashSet::from_iter(map.values().copied());
1760        assert_eq!(values.len(), 6);
1761        assert_eq!(tree1.get_idx(&"/b".into(), None), Err(Some((map["/"], 0))));
1762        assert_eq!(tree1.get_idx(&"/w".into(), None), Err(Some((map["/"], 0))));
1763        assert_eq!(
1764            tree1.get_idx(&"/b/a".into(), None),
1765            Err(Some((map["/"], 0)))
1766        );
1767        assert_eq!(
1768            tree1.get_idx(&"/x/y/z".into(), None),
1769            Err(Some((map["/"], 0)))
1770        );
1771        assert_eq!(
1772            tree1.get_idx(&"/a/d".into(), None),
1773            Err(Some((map["/a"], 1)))
1774        );
1775        assert_eq!(
1776            tree1.get_idx(&"/a/b/x".into(), None),
1777            Err(Some((map["/a/b"], 2)))
1778        );
1779
1780        assert_eq!(
1781            Tree::<usize, String>::new().get_idx(&"/a".into(), None),
1782            Err(None)
1783        );
1784
1785        assert_eq!(
1786            tree1.get_path_idxs(&"/a/b".into()),
1787            Ok(vec![map["/"], map["/a"], map["/a/b"]])
1788        );
1789        assert_eq!(
1790            tree1.get_path_idxs(&"/f/d".into()),
1791            Ok(vec![map["/"], map["/f"], map["/f/d"]])
1792        );
1793        assert_eq!(
1794            tree1.get_path_idxs(&"/a/b/w".into()),
1795            Err(Some((vec![map["/"], map["/a"], map["/a/b"]], 2)))
1796        );
1797        assert_eq!(
1798            Tree::<usize, String>::new().get_path_idxs(&"/a/b/w".into()),
1799            Err(None)
1800        );
1801    }
1802
1803    #[test]
1804    fn insert_at() {
1805        let mut tree1 = Tree::new();
1806        assert_eq!(tree1.len(), 0);
1807        tree1.insert_root(0);
1808        assert_eq!(tree1.len(), 1);
1809        let (_, a_idx) = tree1.insert_at(tree1.get_root_idx().unwrap(), "a".to_string(), 1);
1810        assert_eq!(tree1.len(), 2);
1811        tree1.insert_at(a_idx, "b".to_string(), 2);
1812        assert_eq!(tree1.len(), 3);
1813        tree1.insert_at(tree1.get_root_idx().unwrap(), "c".to_string(), 3);
1814        assert_eq!(tree1.len(), 4);
1815        let (_, f_idx) = tree1.insert_at(tree1.get_root_idx().unwrap(), "f".to_string(), 4);
1816        assert_eq!(tree1.len(), 5);
1817        tree1.insert_at(f_idx, "d".to_string(), 5);
1818        assert_eq!(tree1.len(), 6);
1819        assert_eq!(tree1, new_tree());
1820        tree1.insert_at(tree1.get_root_idx().unwrap(), "a".to_string(), 1);
1821        assert_eq!(tree1.len(), 6);
1822        assert_eq!(tree1, new_tree());
1823    }
1824
1825    #[test]
1826    #[should_panic]
1827    fn insert_at_panic_parent() {
1828        new_tree().insert_at(7, "P".to_string(), 2);
1829    }
1830
1831    #[test]
1832    fn remove_subtree_at() {
1833        let mut tree1 = new_tree();
1834        tree1.remove_subtree_at(tree1.get_root_idx().unwrap(), "a".to_string());
1835        assert_eq!(tree1.len(), 4);
1836        tree1.remove_subtree_at(tree1.get_root_idx().unwrap(), "c".to_string());
1837        assert_eq!(tree1.len(), 3);
1838        tree1.remove_subtree_at(tree1.get_idx(&"/f".into(), None).unwrap(), "d".to_string());
1839        assert_eq!(tree1.len(), 2);
1840        tree1.remove_subtree_at(tree1.get_root_idx().unwrap(), "f".to_string());
1841        assert_eq!(tree1.len(), 1);
1842    }
1843
1844    #[test]
1845    fn get() {
1846        let mut tree1: Tree<usize, String> = Tree::new();
1847        // Can't get any node from an empty node
1848        assert_eq!(tree1.get(&"/a/b/w".into()), Err(None));
1849        tree1 = new_tree();
1850        // Get a reference to the node data at "/a"
1851        assert_eq!(tree1.get(&"/a".into()), Ok(&1));
1852        assert_eq!(tree1.get(&"/a/b".into()), Ok(&2));
1853        // "/a/b/w" is out of the tree, "/a/b" being the last node in the tree of the path
1854        assert_eq!(tree1.get(&"/a/b/w".into()), Err(Some("/a/b".into())));
1855        assert_eq!(tree1.get(&"/b/a".into()), Err(Some("/".into())));
1856    }
1857
1858    #[test]
1859    fn get_mut() {
1860        let mut tree1: Tree<usize, String> = Tree::new();
1861        // Can't get any node from an empty node
1862        assert_eq!(tree1.get_mut(&"/a/b/w".into()), Err(None));
1863        tree1 = new_tree();
1864        // Get a reference to the node data at "/a"
1865        assert_eq!(tree1.get_mut(&"/a".into()), Ok(&mut 1));
1866        assert_eq!(tree1.get_mut(&"/a/b".into()), Ok(&mut 2));
1867        // "/a/b/w" is out of the tree, "/a/b" being the last node in the tree of the path
1868        assert_eq!(tree1.get_mut(&"/a/b/w".into()), Err(Some("/a/b".into())));
1869        assert_eq!(tree1.get_mut(&"/b/a".into()), Err(Some("/".into())));
1870    }
1871
1872    #[test]
1873    fn root_entry() {
1874        let mut tree1: Tree<usize, String> = Tree::new();
1875        let entry = tree1.root_entry();
1876        assert!(!entry.is_node());
1877        tree1.i("/", 7).i("/c1", 1);
1878        let mut entry = tree1.root_entry();
1879        assert_eq!(entry.value(), Some(&7));
1880        entry.move_down_branch("c1".into());
1881        assert_eq!(entry.value(), Some(&1));
1882        tree1.clear();
1883        let entry = tree1.root_entry();
1884        assert!(!entry.is_node());
1885    }
1886
1887    #[test]
1888    fn root_entry_mut() {
1889        let mut tree1: Tree<usize, String> = Tree::new();
1890        let mut entry = tree1.root_entry_mut();
1891        assert!(!entry.is_node());
1892        assert_eq!(entry.or_insert(5), &mut 5);
1893        entry.move_down_branch("c1".into());
1894        assert_eq!(entry.or_insert(1), &mut 1);
1895        entry.move_up(1);
1896        assert!(entry.is_node());
1897    }
1898
1899    #[test]
1900    fn entry() {
1901        let mut tree1: Tree<usize, String> = Tree::new();
1902        tree1.i("/", 0).i("/a", 1).i("/a/b", 2).i("/c", 3);
1903        let mut entry = tree1.entry(&"/a/b".into());
1904        assert_eq!(entry.value(), Some(&2));
1905        entry.move_up(1);
1906        assert_eq!(entry.value(), Some(&1));
1907        entry.move_up(1);
1908        assert_eq!(entry.value(), Some(&0));
1909    }
1910
1911    #[test]
1912    fn entry_mut() {
1913        let mut tree1: Tree<usize, String> = Tree::new();
1914        tree1.i("/", 0).i("/a", 1).i("/a/b", 2).i("/c", 3);
1915        let mut entry = tree1.entry_mut(&"/a/b".into());
1916        assert_eq!(entry.or_insert(4), &mut 2);
1917        entry.move_up(2);
1918        entry.move_down_branch("f".into());
1919        assert_eq!(entry.or_insert(4), &mut 4);
1920        entry.move_down_branch("e".into());
1921        assert_eq!(entry.or_insert(5), &mut 5);
1922        assert_eq!(tree1, new_tree());
1923    }
1924
1925    /*
1926    #[test]
1927    fn get_entry() {
1928    }*/
1929
1930    #[test]
1931    fn insert() {
1932        let mut tree1: Tree<_, String> = Tree::new();
1933        assert_eq!(tree1.insert(&"/".into(), 0), Ok(None));
1934        assert_eq!(tree1.insert(&"/a".into(), 2), Ok(None));
1935        assert_eq!(tree1.insert(&"/a".into(), 1), Ok(Some(2)));
1936        assert_eq!(tree1.insert(&"/a/b/c".into(), 2), Err(Some("/a".into())));
1937        assert_eq!(tree1.insert(&"/a/b".into(), 2), Ok(None));
1938        assert_eq!(tree1.insert(&"/c".into(), 3), Ok(None));
1939        assert_eq!(tree1.insert(&"/f".into(), 4), Ok(None));
1940        assert_eq!(tree1.insert(&"/f/e".into(), 5), Ok(None));
1941        assert_eq!(tree1, new_tree());
1942        tree1.clear();
1943        assert_eq!(tree1.len(), 0);
1944        assert_eq!(tree1.insert(&"/a/b/c".into(), 2), Err(None));
1945        assert_eq!(tree1.insert(&"/".into(), 7), Ok(None));
1946        assert_eq!(tree1.len(), 1);
1947        assert_eq!(tree1[&"/".into()], 7);
1948    }
1949
1950    #[test]
1951    fn remove_subtree() {
1952        let mut tree1: Tree<usize, String> = Tree::new();
1953        tree1.insert(&"/".into(), 0).unwrap();
1954        tree1.insert(&"/a".into(), 1).unwrap();
1955        tree1.insert(&"/a".into(), 2).unwrap();
1956        tree1.insert(&"/b".into(), 3).unwrap();
1957        let mut tree2 = tree1.clone();
1958
1959        // Add a branch to tree2
1960        tree2.insert(&"/c".into(), 4).unwrap();
1961        tree2.insert(&"/c/d".into(), 5).unwrap();
1962
1963        // Remove the branch
1964        tree2.remove_subtree(&"/c".into()).unwrap();
1965        assert_eq!(tree1, tree2);
1966    }
1967
1968    #[test]
1969    fn force_apply() {
1970        let mut tree1 = new_tree();
1971        let mut diff = Tree::new();
1972        let mut tree_res = Tree::new();
1973
1974        diff.i("/", (Some(0), Some(9)))
1975            .i("/a", (None, None))
1976            .i("/a/b", (Some(2), Some(8)))
1977            .i("/f", (Some(4), None))
1978            .i("/f/g", (Some(1000), Some(14))) // wrong initial value and change below deletion
1979            .i("/c", (None, Some(12))) // wrong initial value
1980            .i("/c/e", (None, Some(11)));
1981        assert!(!tree1.force_apply(diff.clone()));
1982
1983        tree_res
1984            .i("/", 9)
1985            .i("/a", 1)
1986            .i("/a/b", 8)
1987            .i("/c", 12)
1988            .i("/c/e", 11);
1989
1990        assert_eq!(tree1, tree_res, "Both trees are not equal");
1991    }
1992
1993    #[test]
1994    fn combine() {}
1995
1996    #[test]
1997    fn i() {}
1998
1999    #[test]
2000    fn is_subtree_eq() {}
2001
2002    #[test]
2003    fn apply() {
2004        let mut tree1 = new_tree();
2005        let mut tree_diff = DiffTree::new();
2006        tree_diff
2007            .i("/", (None, None))
2008            .i("/a", (Some(1), None))
2009            .i("/c", (Some(3), Some(10)))
2010            .i("/c/f", (None, Some(11)))
2011            .i("/c/f/g", (None, Some(12)));
2012
2013        let mut tree_res: Tree<usize, String> = Tree::new();
2014        tree_res
2015            .i("/", 0)
2016            .i("/c", 10)
2017            .i("/c/f", 11)
2018            .i("/c/f/g", 12)
2019            .i("/f", 4)
2020            .i("/f/d", 5);
2021        // Apply the differential between `tree1` and `tree2`
2022        tree1.apply(tree_diff).unwrap();
2023        // They are both equal now
2024        assert_eq!(tree1, tree_res, "Both trees are not equal");
2025    }
2026
2027    #[test]
2028    fn apply_diff() {}
2029
2030    #[test]
2031    fn apply_diff_with() {}
2032
2033    #[test]
2034    fn apply_map() {}
2035}
2036
2037/*
2038pub fn move_subtree(
2039    &mut self,
2040    from: Path<B>,
2041    to: Path<B>,
2042    destination: Option<&mut Tree<N, B>>,
2043) -> Result<(), Path<B>> {
2044    let path_idxs = self
2045        .get_path_idxs(path)
2046        .map_err(|(_, idx)| path.path_to(idx))?;
2047
2048    //remove children
2049    self.move_subtree(path_idxs.pop().unwrap());
2050    let mut attr = path.pop_leaf();
2051
2052    //remove empty parent nodes
2053    while !path_idxs.is_empty() && self.nodes[path_idxs.last()].children.len() == 1 {
2054        self.nodes.remove(path_idxs.pop().unwrap());
2055        attr = path.pop_leaf();
2056    }
2057
2058    //remove child link of parent
2059    if !path_idxs.is_empty() {
2060        self.nodes[path_idxs].children.remove(attr);
2061    }
2062    Ok(())
2063}*/
2064//fn move_subtree(&mut self, from: NodeIDX, to: NodeIDX, tree: &mut Tree<N, B>) {
2065//      tree.nodes[to].children.insert(attr, tree.nodes.len());
2066//      tree.nodes.push(TreeNode {})
2067//      self.remove_subtree(idx, );