nb-tree 0.2.0-alpha01

//! # Tree
//! A tree structure.
//! ## Data Structure
//! The nb_tree crate provides a [`Tree<N, B>`](crate::tree::Tree) type
//! generic over node and branch data.
//!
//! Trees have an O(n) indexing. More precisely, it retrieves every node
//! on the path from the tree root to the targetted node.
//! Insertion and removal take a Path to target a node, binding their complexity
//! to the one of indexing, thus O(n).
//! Entries can be used to insert or remove at the [Entry](crate::tree::entry::Entry)'s
//! position in the tree, which only takes O(1).
//!
//! Trees can be [built](type@crate::tree::default::TreeBuilder),
//! [navigated and modified](type@crate::tree::entry::Entry),
//! [diffed](type@crate::tree::diff::DiffTree), [combined](type@crate::tree::combine) and [iterated](crate::tree::iter::Iter) on
//! amongst other operations.
//!
//! # Building trees
//! Trees can be built in several ways using (chainable) insertion methods.
//!
//! ## Inserting data
//! Data can be added or overwritten at a specified location via [insert].
//! ```
//! use nb_tree::prelude::Tree;
//! let mut tree: Tree<usize, String> = Tree::new();
//! // Insert at root
//! // (None reflects the creation of a new node
//! //  there is no previous value to return)
//! assert_eq!(tree.insert(&"/".into(), 0), Ok(None));
//! // Insert at various given Paths
//! assert_eq!(tree.insert(&"/a".into(), 1), Ok(None));
//! assert_eq!(tree.insert(&"/b".into(), 2), Ok(None));
//! assert_eq!(tree.insert(&"/b/c".into(), 3), Ok(None));
//! // One can't insert below an inexistent node with `insert`
//! // Use `insert_extend` for this
//! assert_eq!(tree.insert(&"/a/x/z".into(), 12), Err(Some("/a".into())));
//! ```
//! A shorthand exists for chaining insertions
//! ```
//! use nb_tree::prelude::Tree;
//! let mut tree: Tree<usize, String> = Tree::new();
//! tree.i("/", 0)
//!     .i("/a", 1)
//!     .i("/a/b", 2)
//!     .i("/a/c", 3)
//!     .i("/d", 4);
//! ```
//! Note that [i] panics if the insertion fails.
//!
//! For node data types that are [Default], [insert_extend] can be used to build
//! intermediary nodes with default data between the last existing node of the
//! given [Path] in the [Tree] and the one to insert
//! ```
//! use nb_tree::prelude::Tree;
//! let mut tree: Tree<usize, String> = Tree::new();
//! tree.insert_extend(&"/a/b/c/x/y/z".into(), 1000000);
//! assert_eq!(tree.values().len(), 7);
//! // A shorthand for `insert_extend` also exists and can be chained
//! tree.ix("/a/b/i/j/k", 101010)
//!     .ix("/a/u/v/w/i/j/k", 222);
//! assert_eq!(tree.values().len(), 16);
//! ```
//! [`insert_extend`] returns the old value if any.
//! If the node did not exist, it returns the default value of the node type.
//!
//! ### Builder
//! [`TreeBuilder`] is a [`Tree`] wrapping each node data in an `Option`.
//! [`Tree`]s with `Option<N>` node data have a [`try_build()`] method to build
//! a `Tree<N>` from it.
//!
//! ```
//! use nb_tree::prelude::{Tree, TreeBuilder};
//! let mut tree: TreeBuilder<usize, String> = TreeBuilder::new();
//! tree.ix("/a/b/c", Some(3))
//!     .ix("/a/b", Some(2));
//! // The tree can't be built because there are empty nodes ("/" and "/a") left
//! assert_eq!(tree.is_buildable(), false);
//!
//! tree.ix("/", Some(0))
//!     .ix("/a", Some(1));
//! // The tree is now buildable
//! assert_eq!(tree.is_buildable(), true);
//!
//! let mut tree_cmp: Tree<usize, String> = Tree::new();
//! tree_cmp.i("/", 0).i("/a", 1).i("/a/b", 2).i("/a/b/c", 3);
//! assert_eq!(tree.build(), tree_cmp);
//! ```
//!
//! ## Removing data
//! Subtrees can be removed from a tree:
//! [remove_subtree] removes the subtree starting at the given [Path].
//! ```
//! use nb_tree::prelude::Tree;
//! let mut tree: Tree<usize, String> = Tree::new();
//! tree.i("/", 0)
//!     .i("/a", 1)
//!     .i("/a/b", 2)
//!     .i("/a/c", 3);
//! // Removes the subtree at /a
//! tree.remove_subtree(&"/a".into());
//! // Only the root node (of value 0) now remains
//! assert_eq!(tree.values().len(), 1);
//! ```
//! [remove_subtree_trim] also trims out parent nodes containing the default value:
//! ```
//! use nb_tree::prelude::Tree;
//! let mut tree: Tree<Option<usize>, String> = Tree::new();
//! assert!(tree.insert(&"/".into(), Some(0)).is_ok());
//! assert!(tree.insert(&"/a".into(), Some(1)).is_ok());
//! tree.insert_extend(&"/a/b/c/i/j/k/x/y/z".into(), Some(1000000));
//! // `remove_subtree` only removes the subtree
//! tree.remove_subtree(&"/a/b/c/i/j/k".into());
//! assert_eq!(tree.len(), 6);
//! // `remove_subtree_trim` also removes the parent nodes containing `None`
//! tree.remove_subtree_trim(&"/a/b/c".into());
//! // Only the root node and the node at "/a" containing non default data remain
//! assert_eq!(tree.len(), 2);
//! ```
//!
//! ## Navigation and manipulation
//!
//! [Entries](type@crate::tree::entry::Entry) allow for tree navigation and mutation,
//! similarly to HashMaps' entry system.
//! It represents an entry at a given Path.
//! It may lead to a defined node or not.
//! ```
//! use nb_tree::prelude::Tree;
//! let mut tree: Tree<usize, String> = Tree::new();
//! tree.i("/", 0)
//!     .i("/a", 1)
//!     .i("/a/b", 2)
//!     .i("/c", 3)
//!     .i("/f", 4);
//! let mut entry = tree.entry_mut(&"/a".into());
//! // Insert only if there isn't a value already defined
//! // (won't do anything since /a is already set)
//! entry.or_insert(10);
//! // Move down to an other node
//! entry.move_down("/b/w".into());
//! // inserts 12 at /b/w
//! entry.or_insert(12);
//! // `or_insert_extend` is only available if N is Default
//! let mut tree2: Tree<Option<usize>, String> = Tree::new();
//! let mut entry2 = tree2.entry_mut(&"/i/j/k".into());
//! entry2.or_insert_extend(Some(12));
//! assert_eq!(tree2.len(), 4);
//! ```
//! `and_modify` only applies the given function to the node's value if it is defined.
//! ```
//! # use nb_tree::prelude::Tree;
//! # let mut tree: Tree<usize, String> = Tree::new();
//! # tree.i("/", 0)
//! #     .i("/a", 1)
//! #     .i("/a/b", 2)
//! #     .i("/c", 3)
//! #     .i("/f", 4);
//! let mut entry = tree.entry_mut(&"/a/b".into());
//! entry.and_modify(|mut n| *n += 1);
//! ```
//! The previous methods like `insert` and `remove_subtree` are also available
//! for inserting and removing data at entry position.
//!
//! # Differentials
//! ## Diffing
//! Trees can be compared via [`diff`], producing a [`DiffTree`] containing
//! all differing nodes between the compared trees.
//! [`DiffTree`]s are `Tree`s with `DiffNode`s which have the type `(Option(N), Option(N))`.
//! The `Option`s signal the presence (or absence thereof) of the node in the compared trees.
//! The `DiffTree` produced by `diff` only contains data for nodes differing,
//! so the diff tree will be extended with empty nodes (`(None, None)`) to build the tree.
//! ```
//! use nb_tree::prelude::{Tree, DiffTree};
//! let mut tree1: Tree<usize, String> = Tree::new();
//! tree1.i("/", 0)
//!     .i("/a", 1)
//!     .i("/a/b", 2)
//!     .i("/c", 3)
//!     .i("/f", 4);
//!
//! let mut tree2: Tree<usize, String> = Tree::new();
//! tree2.i("/", 9)
//!     .i("/a", 2)
//!     .i("/a/b", 1)
//!     .i("/c", 3)
//!     .i("/c/d", 4);
//!
//! // Create a DiffTree containing the differences between `tree1` and `tree2`
//! let diff = tree1.diff(&tree2);
//!
//! let mut diff_cmp: DiffTree<usize, String> = DiffTree::new();
//! diff_cmp.i("/", (Some(0), Some(9)))
//!     .i("/a", (Some(1), Some(2)))
//!     .i("/a/b", (Some(2), Some(1)))
//!     .i("/f", (Some(4), None))
//!     .ix("/c/d", (None, Some(4)));
//! // "/c/d" node insertion needs a node at "/c"
//! // `ix` will extend the tree with an empty node (`(None, None)`) to allow for that
//! assert_eq!(diff, diff_cmp);
//! ```
//! [`zip`] will combine both trees into a [DiffTree].
//!
//! ## Applying diffs
//!
//! [`DiffTree`]s can be applied to a tree via [`apply`] and [`apply_extend`].
//! ```
//! # use nb_tree::prelude::{Tree, DiffTree};
//! # let mut tree1: Tree<usize, String> = Tree::new();
//! # tree1.i("/", 0)
//! #     .i("/a", 1)
//! #     .i("/a/b", 2)
//! #     .i("/c", 3)
//! #     .i("/f", 4);
//! # let mut tree2: Tree<usize, String> = Tree::new();
//! # tree2.i("/", 9)
//! #     .i("/a", 2)
//! #     .i("/a/b", 1)
//! #     .i("/c", 3)
//! #     .i("/c/d", 4);
//! # let mut diff = tree1.diff(&tree2);
//! // … taking back `tree1`, `tree2` and `diff` from the previous example
//! let tree1_orig = tree1.clone();
//! // Apply the differential between `tree1` and `tree2`
//! tree1.apply(diff.clone());
//! // They are both equal now
//! assert_eq!(tree1, tree2);
//! // Applying the reversed diff will restore tree1
//! diff.rev();
//! tree1.apply(diff);
//! assert_eq!(tree1, tree1_orig);
//! ```
//!
//! Single diff data can be applied via the `apply_diff` method which takes a
//! Path and a `DiffNode` and applies it to the tree.
//! These diffs can be gathered into a `DiffMap` that too can be applied
//! via `apply_map`.
//! ```
//! use nb_tree::prelude::{Tree, DiffMap};
//! use std::collections::HashMap;
//! let mut tree: Tree<usize, String> = Tree::new();
//! tree.i("/", 0)
//!     .i("/a", 1)
//!     .i("/a/b", 2)
//!     .i("/c", 3)
//!     .i("/f", 4);
//! // Changes the value of the node at /c from 3 to 7
//! tree.apply_diff("/c".into(), (Some(3), Some(7)));
//! // Removes the node at /a that had the value 1 and the subtree below it
//! tree.apply_diff("/a".into(), (Some(1), None));
//! // Changes /f from 4 to 0, creates /f/z with value 5
//! let map = HashMap::from([
//!     ("/f".into(), (Some(4), Some(0))),
//!     ("/f/z".into(),
//!     (None, Some(5)))]).into();
//! let mut tree_cmp: Tree<usize, String> = Tree::new();
//! tree.apply_map(map);
//! tree_cmp.i("/", 0)
//!     .i("/c", 7)
//!     .i("/f", 0)
//!     .i("/f/z", 5);
//! assert_eq!(tree, tree_cmp);
//! ```
//! # Combining
//! Combining trees can be done through the `combine()` method.
//! Data present in both trees can be chosen from either tree,
//! data only present in one of them can be kept or discarded.
//! `CombinationMode::Union` and `CombinationMode::Intersection` are available,
//! as well as a `CombinationMode::Free` mode which lets freely select
//! the data to keep during the combination.
//! ```
//! use nb_tree::prelude::{Tree, CombinationMode};
//! let mut tree1: Tree<usize, String> = Tree::new();
//! tree1.i("/", 0)
//!      .i("/a", 1)
//!      .i("/a/b", 11)
//!      .i("/c", 2)
//!      .i("/f", 3);
//!
//! let mut tree2: Tree<usize, String> = Tree::new();
//! tree2.i("/", 500)   // |- overlaping data
//!      .i("/a", 900)  // |
//!      .i("/a/w", 910)// |- new data
//!      .i("/x", 100)  // |
//!      .i("/x/y", 110)// |
//!      .i("/z", 300); // |
//!
//! // tree1 is combined with tree2, keeping tree1's nodes absent from tree2,
//! // growing tree1 with tree2's nodes absent from tree1
//! // and overwriting tree1's data with tree2's for nodes common to both trees.
//! tree1.combine(tree2, CombinationMode::Free{keep: true, grow: true, overwrite: true});
//! // (this is the same as `CombinationMode::Union(true)`)
//!
//! let mut tree_comb: Tree<usize, String> = Tree::new();
//! tree_comb.i("/", 500)   // |- common nodes with tree2's data (overwrite)
//!          .i("/a", 900)  // |
//!          .i("/a/b", 11) // |- tree1's nodes (keep)
//!          .i("/c", 2)    // |
//!          .i("/f", 3)    // |
//!          .i("/a/w", 910)// |- tree2's nodes (grow)
//!          .i("/x", 100)  // |
//!          .i("/x/y", 110)// |
//!          .i("/z", 300); // |
//!
//! assert_eq!(tree1, tree_comb);
//! ```
//! # Iterating
//!
//! The default iteration method is depth first (width first is not yet available)
//! ```
//! use nb_tree::prelude::{Tree, DiffMap};
//! let mut tree1: Tree<usize, String> = Tree::new();
//! tree1.i("/", 0)
//!     .i("/a", 1)
//!     .i("/a/b", 12)
//!     .i("/c", 3)
//!     .i("/f", 4);
//! // Prints each node's branch and value
//! for iter_node in tree1 {
//!     println!("{} at {:?}", iter_node.data(), iter_node.branch());
//! }
//! ```
//! `iter` and `into_iter` are implemented (`iter_mut` is not yet available).
//! The iteration nodes contain information about the position in the tree
//! relative to the previous node.
//! The path to the current node can be built by applying these relative movements to it.
//! ```
//! # use nb_tree::prelude::{Tree, DiffMap};
//! # let mut tree1: Tree<usize, String> = Tree::new();
//! # tree1.i("/", 0)
//! #     .i("/a", 1)
//! #     .i("/a/b", 12)
//! #     .i("/c", 3)
//! #     .i("/f", 4);
//! # use nb_tree::prelude::Path;
//! let mut path = Path::new();
//! for iter_node in tree1 {
//!     path.apply(&iter_node);
//!     println!("{} at {}", iter_node.data(), path);
//! }
//! ```
//! The usual iterator operations are available as well as `absolute` and `skip_below`.
//!
//! `absolute` returns the next value with its Path.
//! ```
//! # use nb_tree::prelude::{Tree, DiffMap};
//! # let mut tree1: Tree<usize, String> = Tree::new();
//! # tree1.i("/", 0)
//! #     .i("/a", 1)
//! #     .i("/a/b", 12)
//! #     .i("/c", 3)
//! #     .i("/f", 4);
//! # use nb_tree::prelude::Path;
//! use itertools::Itertools;
//! use crate::nb_tree::tree::iter::{TreeIterTools, TraversalNode};
//! assert_eq!(
//!     tree1.into_iter().absolute().map(|n| n.path).sorted().collect::<Vec<Path<String>>>(),
//!     vec!["/".into(), "/a".into(), "/a/b".into(), "/c".into(), "/f".into()]
//!     );
//! ```
//!
//! `skip_below` takes a predicate and skips all nodes at and below the current path.
//! ```
//! use nb_tree::prelude::{Tree, DiffMap};
//! let mut tree1: Tree<usize, String> = Tree::new();
//! tree1.i("/", 0)
//!     .i("/a", 1)
//!     .i("/a/b", 12)
//!     .i("/a/b/z", 6)
//!     .i("/c", 3)
//!     .i("/c/d", 7)
//!     .i("/c/d/y", 5)
//!     .i("/f", 11)
//!     .i("/g", 10)
//!     .i("/h", 11)
//!     .i("/i", 19)
//!     .i("/i/w", 18)
//!     .i("/i/w/n", 8)
//!     .i("/k", 15);
//! use itertools::Itertools;
//! use nb_tree::prelude::Path;
//! use crate::nb_tree::tree::iter::TreeIterTools;
//! assert_eq!(
//!     tree1.into_iter().skip_below(|item| {
//!         *item.data() >= 10
//!     }).map(|n| n.data().clone()).sorted().collect::<Vec<usize>>(),
//!     vec![0, 1, 3, 5, 7]
//!     );
//! ```

pub(crate) mod clone;
pub(crate) mod default;
pub use default::TreeBuilder;
pub(crate) mod diff;
pub use diff::{DiffMap, DiffNode, DiffTree};
/// [`Tree`] iteration.
///
/// [`Tree`]: crate::tree::Tree
pub mod iter;
pub(crate) mod node;
use node::TreeNode;
/// [`Tree`] navigation.
///
/// [`Tree`]: crate::tree::Tree
pub mod entry;
pub(crate) mod position;
pub use position::Position;
use replace_with::replace_with_or_abort;

use self::diff::DiffApplyError;
use self::entry::{TreeMutEntry, TREEBOUND};
use self::iter::depth::IntoIter;
use self::{
    entry::{detached::DetachedEntry, node::Node, Entry},
    position::{AttachedPosition, DetachedPosition},
};
use super::path::Path;
use crate::path::PathIDX;

use iter::depth::{Iter, Traversal, TreeIterTarget};
use std::hash::Hash;
use std::mem;
use std::ops::Index;
use std::{fmt::Debug as Dbg, ops::Deref};
use tracing::{debug, error, trace, trace_span};

/// Takes a Result and returns the Some value or returns the given value.
macro_rules! or_return {
    ( $e:expr, $r:expr ) => {
        match $e {
            Some(x) => x,
            None => return $r,
        }
    };
}

/// The index of a node in the tree.
///
/// Since these can change, they cannot be used as node identifiers
/// and should not be exposed in the API.
pub(crate) type NodeIDX = usize;

/// Tree structure with generic node and branch data.
///
/// For more information about Trees and their usage,
/// see the [module level documentation](self).
///
/// Each node aside from the root node has a parent to which it is linked via a branch.
/// Nodes as well as branches have a value, which allows for giving names and wheights
/// to branches.
///
/// # Examples
/// A quick way to build a tree is by using the chainable version of `insert()` called `i()`
/// ```
/// use nb_tree::prelude::Tree;
/// let mut tree: Tree<usize, String> = Tree::new();
///
/// tree.i("/", 0)
///     .i("/a", 1)
///     .i("/a/b", 2)
///     .i("/a/b/z", 6)
///     .i("/c", 3)
///     .i("/c/d", 7);
/// ```
/// The resulting tree looks like this:
/// ```text
/// ╱┬→ 0
///  ├a┬→ 1
///  │ └b┬→ 2
///  │   └z─→ 6
///  └c┬→ 3
///    └d─→ 7
/// ```
/// # Data management
///
/// Removing a node from the tree also removes its children recursively.
/// Removal is done in constant time, since the nodes are only unlinked
/// from their parent and marked as removed.
/// Since the nodes are stored in a Vec, shifting the ones succeeding
/// the removed node would be costful and removing the whole subtree
/// would take O(n) given n the number of nodes in that subtree.
#[derive(Debug, Clone)]
pub struct Tree<N, B> {
    /// Nodes are added and removed through `insert()` and `remove()` only.
    nodes: Vec<TreeNode<N, B>>,
    /// Nodes removed from the tree.
    /// These indexes will be reused later upon inserting new nodes
    /// via `insert()`.
    /// `remove()` adds them to the vec.
    removed: Vec<NodeIDX>,
}

impl<N, B> Default for Tree<N, B> {
    fn default() -> Self {
        Self {
            nodes: Vec::default(),
            removed: Vec::default(),
        }
    }
}

impl<N, B> Index<&Path<B>> for Tree<N, B>
where
    B: Eq + Hash + Clone,
{
    type Output = N;
    fn index(&self, index: &Path<B>) -> &Self::Output {
        self.get(index)
            .unwrap_or_else(|_| panic!("Could not index into the tree with the given path"))
    }
}

impl<N, B> PartialEq for Tree<N, B>
where
    N: Eq,
    B: Eq + Hash,
{
    fn eq(&self, other: &Self) -> bool {
        (self.is_empty() && other.is_empty())
            || (!self.is_empty()
                && !other.is_empty()
                && self.is_subtree_eq(
                    self.get_root_idx().unwrap(),
                    other,
                    other.get_root_idx().unwrap(),
                ))
    }
}

impl<N, B> Eq for Tree<N, B>
where
    N: Eq,
    B: Eq + Hash,
{
}

impl<N, B> Tree<N, B> {
    /// Creates a new empty generic tree over node data (`N`)
    /// and branch data (`B`) types.
    ///
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let tree: Tree<usize, String> = Tree::new();
    /// ```
    pub fn new() -> Self {
        Default::default()
    }

    /// Creates a new empty tree with at least the given capacity.
    pub fn with_capacity(capacity: usize) -> Self {
        Self {
            nodes: Vec::with_capacity(capacity),
            ..Default::default()
        }
    }

    /// Reserves space for at least the given additional amount of nodes in the tree.
    pub fn reserve(&mut self, additional: usize) {
        self.nodes.reserve(additional)
    }

    /// Returns the value of the root node if there is one, returns None otherwise.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<String, String> = Tree::new();
    /// // The tree is empty
    /// assert_eq!(tree.get_root(), None);
    /// tree.i("/", "a".to_string());
    ///
    /// assert_eq!(tree.get_root(), Some(&"a".to_string()));
    /// ```
    pub fn get_root(&self) -> Option<&N> {
        if self.is_empty() {
            None
        } else {
            Some(&self.nodes[0].value)
        }
    }

    /// Returns the index of the root node if there is one, returns None otherwise.
    ///
    /// There is no guaranty that the root node will always be 0.
    fn get_root_idx(&self) -> Option<NodeIDX> {
        (!self.is_empty()).then_some(0)
    }

    /// Inserts a value at the root and returns the previous value if there is one.
    ///
    /// # Examples
    /// ```rust
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<String, String> = Tree::new();
    /// assert_eq!(tree.insert_root("a".to_string()), None);
    /// assert_eq!(tree.insert_root("b".to_string()), Some("a".to_string()));
    /// ```
    pub fn insert_root(&mut self, value: N) -> Option<N> {
        if self.nodes.is_empty() {
            // Initialize the tree with a root node
            self.nodes.push(value.into());
            None
        } else if self.removed.last() == Some(&0) {
            // Reinsert the removed node
            self.removed.pop();
            self.removed
                .append(&mut self.nodes[0].children.values().cloned().collect());
            self.nodes[0] = value.into();
            self.nodes[0].children = Default::default();
            None
        } else {
            // The root should not have been removed
            debug_assert!(
                !self.removed.contains(&0),
                "Root has been removed but is not the most recent deletion"
            );
            // Replace the current value
            Some(mem::replace(&mut self.nodes[0].value, value))
        }
    }

    /// Removes all nodes from the tree.
    fn clear(&mut self) {
        *self = Tree::default();
        /* Alternative not removing any node
        if self.removed.last().map_or(true, |l| *l != 0) {
            self.removed.push(0);
        }*/
    }

    /// Returns true is the tree has no nodes.
    ///
    /// # Examples
    /// ```rust
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<String, String> = Tree::new();
    /// assert!(tree.is_empty());
    /// tree.insert_root("a".to_string());
    /// assert!(!tree.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty() || self.removed.last() == Some(&0)
    }

    /// Return the number of nodes in the tree.
    ///
    /// # Examples
    /// ```rust
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// assert_eq!(tree.len(), 0);
    /// tree.i("/", 10);
    /// assert_eq!(tree.len(), 1);
    /// tree.i("/a", 20)
    ///     .i("/a/b", 30)
    ///     .i("/a/b/z", 40)
    ///     .i("/c", 50)
    ///     .i("/c/d", 60);
    /// assert_eq!(tree.len(), 6);
    /// ```
    pub fn len(&self) -> usize {
        self.iter_on::<()>().count()
    }

    /// Returns a vector of references to the tree's node values in arbitrary order.
    ///
    /// # Examples
    /// ```rust
    /// use std::collections::HashSet;
    /// use std::iter::FromIterator;
    /// use nb_tree::prelude::Tree;
    ///
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// tree.i("/", 0)
    ///     .i("/a", 1)
    ///     .i("/a/b", 2);
    /// let values: HashSet<usize> = HashSet::from_iter(vec![0,1,2].into_iter());
    /// let tree_values: HashSet<usize> = HashSet::from_iter(tree.values().into_iter().cloned());
    /// assert_eq!(
    ///     tree_values,
    ///     values);
    /// ```
    pub fn values(&self) -> Vec<&N> {
        self.iter().map(|n| n.take()).collect()
    }

    /// Returns an iterator over [TreeIterTarget] data from each thee node
    /// relatively to one another.
    ///
    /// The iterator returns [`Traversal`]s containing
    /// the associated TreeIterTarget.
    fn iter_on<'a, T: TreeIterTarget<'a, N, B>>(&'a self) -> Iter<'a, N, B, T> {
        Iter::new(self)
    }

    /// Returns an depth first iterator over the tree's node data relatively to one another.
    ///
    /// The iterator returns [`Traversal`]s containing the associated node data.
    /// If the tree is not empty, the first item is a [`Root`] node
    /// containing a reference to the root node's data.
    /// All subsequent items are [`Node`]s containing their position
    /// relative to the previous item and a reference to the node's data.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use nb_tree::prelude::{iter::depth::Traversal, Path, Tree};
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// tree.i("/", 0)
    ///     .i("/a", 1)
    ///     .i("/a/B", 10)
    ///     .i("/a/B/i", 100)
    ///     .i("/a/B/j", 200)
    ///     .i("/a/C", 11)
    ///     .i("/a/C/x", 111)
    ///     .i("/a/C/y", 222);
    /// let mut iter = tree.iter();
    /// if let Traversal::Start(data) = iter.next().expect("Root node expected") {
    ///     // The root node's data is 0
    ///     assert_eq!(*data, 0);
    /// } else {
    ///     panic!("Expected a Root node");
    /// }
    /// if let Traversal::Step { up, branch, data } =
    ///     iter.next().expect("Root child Node expected")
    /// {
    ///     // The node is below the root node
    ///     assert_eq!(up, 0);
    ///     // The node is at branch "a"
    ///     assert_eq!(*branch, "a");
    ///     // The node's data is 1
    ///     assert_eq!(*data, 1);
    /// } else {
    ///     panic!("Expected a non Root node");
    /// }
    /// let mut path = Path::new();
    /// for iter_node in tree {
    ///     // Move up the path
    ///     if iter_node.up() > 0 {
    ///         for _ in 0..iter_node.up() {
    ///             path.pop_last();
    ///         }
    ///         //
    ///         println!(
    ///             "{}╭{}┘ up",
    ///             " ".repeat(path.to_string().len()),
    ///             "──".repeat(iter_node.up()-1)
    ///         );
    ///     }
    ///     // Get the branch if any (there is none for the Root)
    ///     if let Some(branch) = iter_node.branch() {
    ///         path.push_last(branch.clone());
    ///     }
    ///     // Get the data
    ///     println!("{}: {}", path, iter_node.data());
    /// }
    /// ```
    /// One possible output would be:
    /// ```text
    ///     /: 0
    ///     /a: 1
    ///     /a/B: 10
    ///     /a/B/i: 100
    ///         ╭┘ up
    ///     /a/B/j: 200
    ///       ╭──┘ up
    ///     /a/C: 11
    ///     /a/C/x: 111
    ///         ╭┘ up
    ///     /a/C/y: 222
    /// ```
    /// As the iteration order of children of a node is unknown,
    /// "/a/C" can be visited before "/a/B", as can "/a/B/j" and "/a/B/i"
    /// as well as "/a/C/y" and "/a/C/x".
    pub fn iter(&self) -> Iter<N, B, &N> {
        self.iter_on()
    }
}

impl<N, B> Tree<N, B>
where
    B: Eq + Hash,
{
    /// Returns the index of the node pointed to by the given [path].
    ///
    /// If the node doesn't exist, it returns the index of the closest
    /// existing node in the tree and the index of the inexistent child in [path].
    /// If the tree is empty, None is returned.
    fn get_idx(
        &self,
        path: &Path<B>,
        from_idx: Option<NodeIDX>,
    ) -> Result<NodeIDX, Option<(NodeIDX, PathIDX)>> {
        let root_idx = if let Some(idx) = self.get_root_idx() {
            idx
        } else {
            return Err(None);
        };
        path.iter().enumerate().try_fold(
            from_idx.unwrap_or(root_idx),
            |node_idx, (path_idx, branch)| {
                self.nodes[node_idx]
                    .children
                    .get(branch)
                    .cloned()
                    .ok_or(Some((node_idx, path_idx)))
            },
        )
    }

    /// Returns a vector of the index of every node along the given [path].
    ///
    /// If a node doesn't exist, the index vector up until this node is returned
    /// as well as the index of the inexistent child in [path].
    /// If the tree is empty, None is returned.
    fn get_path_idxs(&self, path: &Path<B>) -> Result<Vec<NodeIDX>, Option<(Vec<NodeIDX>, usize)>> {
        let root_idx = if let Some(idx) = self.get_root_idx() {
            idx
        } else {
            return Err(None);
        };
        path.iter()
            .enumerate()
            .try_fold(vec![root_idx], |mut node_idx, (path_idx, branch)| {
                node_idx.push(
                    self.nodes[*node_idx.last().unwrap()]
                        .children
                        .get(branch)
                        .cloned()
                        //NOTE: No way to do without the cloning? (E0505)
                        .ok_or(Some((node_idx.clone(), path_idx)))?,
                );
                Ok(node_idx)
            })
    }

    /// Inserts a value as the [child] node of the given parent.
    ///
    /// # Warning
    /// Does not check the validity of [parent_idx].
    fn insert_at(&mut self, parent_idx: NodeIDX, child: B, value: N) -> (Option<N>, NodeIDX) {
        // Child exists?
        if let Some(child_idx) = self.nodes[parent_idx].children.get(&child).cloned() {
            (
                Some(mem::replace(&mut self.nodes[child_idx].value, value)),
                child_idx,
            )
        } else {
            // Get a node
            let idx = if let Some(idx) = self.removed.pop() {
                // Use a removed one
                self.removed
                    .append(&mut self.nodes[idx].children.values().cloned().collect());
                self.nodes[idx] = From::from(value);
                self.nodes[parent_idx].children.insert(child, idx);
                idx
            } else {
                let idx = self.nodes.len();
                // Extend the vec
                self.nodes.push(From::from(value));
                //NOTE: Any way to do without the variable? (E0502)
                self.nodes[parent_idx].children.insert(child, idx);
                idx
            };

            (None, idx)
        }
    }

    /// Removes the subtree at the [child] of the given parent node.
    ///
    /// # Warning
    /// Does not check [parent_idx]'s validity
    fn remove_subtree_at(&mut self, parent_idx: NodeIDX, child: B) -> Option<NodeIDX> {
        let idx = self.nodes[parent_idx].children.remove(&child)?;
        self.remove_subtree_idx(idx)
    }

    /// Adds the subtree at the given [idx] to the `removed` array.
    ///
    /// # Warning
    /// Does not check [idx]'s validity
    fn remove_subtree_idx(&mut self, idx: NodeIDX) -> Option<NodeIDX> {
        self.removed.push(idx);
        Some(idx)
    }
}

impl<N, B> Tree<N, B>
where
    B: Eq + Hash + Clone,
{
    /// Returns a reference to the value of the node at the given [path].
    /// 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.
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// // Can't get any node from an empty node
    /// assert_eq!(tree.get(&"/a/b/w".into()), Err(None));
    /// tree.i("/", 0)
    ///     .i("/a", 1)
    ///     .i("/a/b", 2)
    ///     .i("/c", 3);
    /// // Get a reference to the node data at "/a"
    /// assert_eq!(tree.get(&"/a".into()), Ok(&1));
    /// // "/a/b/w" is out of the tree, "/a/b" being the last node in the tree of the path
    /// assert_eq!(tree.get(&"/a/b/w".into()), Err(Some("/a/b".into())));
    /// ```
    pub fn get(&self, path: &Path<B>) -> Result<&N, Option<Path<B>>> {
        Ok(&self.nodes[self
            .get_idx(path, None)
            .map_err(|r| r.map(|(_, i)| path.path_to(i)))?]
        .value)
    }

    /// Returns a mutable reference to the value of the node at the given [path].
    /// 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.
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// // Can't get any node from an empty node
    /// assert_eq!(tree.get(&"/a/b/w".into()), Err(None));
    /// tree.i("/", 0)
    ///     .i("/a", 1)
    ///     .i("/a/b", 2)
    ///     .i("/c", 3);
    /// // Get a reference to the node data at "/a"
    /// assert_eq!(tree.get_mut(&"/a".into()), Ok(&mut 1));
    /// // "/a/b/w" is out of the tree, "/a/b" being the last node in the tree of the path
    /// assert_eq!(tree.get_mut(&"/a/b/w".into()), Err(Some("/a/b".into())));
    /// ```
    pub fn get_mut(&mut self, path: &Path<B>) -> Result<&mut N, Option<Path<B>>> {
        let idx = self
            .get_idx(path, None)
            .map_err(|r| r.map(|(_, i)| path.path_to(i)))?;
        Ok(&mut self.nodes[idx].value)
    }

    /// Returns an [Entry] with read only access to the root node's position.
    ///
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// let entry = tree.root_entry();
    /// assert!(!entry.is_node());
    /// tree.i("/", 7)
    ///     .i("/c1", 1);
    /// let mut entry = tree.root_entry();
    /// assert_eq!(entry.value(), Some(&7));
    /// entry.move_down_branch("c1".into());
    /// assert_eq!(entry.value(), Some(&1));
    /// ```
    pub fn root_entry(&self) -> Entry<&Self, N, B, TREEBOUND> {
        match self.get_root_idx() {
            Some(root) => {
                Node::from(self, AttachedPosition::from(Path::new(), Path::with(root))).into()
            }
            None => {
                DetachedEntry::from(self, DetachedPosition::from(Path::new(), Path::new())).into()
            }
        }
    }

    /// Returns an [Entry] with mutable access to the root node's position.
    ///
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// let mut entry = tree.root_entry_mut();
    /// assert!(!entry.is_node());
    /// assert_eq!(entry.or_insert(5), &mut 5);
    /// entry.move_down_branch("c1".into());
    /// assert_eq!(entry.or_insert(1), &mut 1);
    /// ```
    pub fn root_entry_mut(&mut self) -> Entry<&mut Self, N, B, TREEBOUND> {
        match self.get_root_idx() {
            Some(root) => {
                Node::from(self, AttachedPosition::from(Path::new(), Path::with(root))).into()
            }
            None => {
                DetachedEntry::from(self, DetachedPosition::from(Path::new(), Path::new())).into()
            }
        }
    }

    /// Returns an [Entry] with read only access to the given position in the tree.
    ///
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// tree.i("/", 0)
    ///     .i("/a", 1)
    ///     .i("/a/b", 2)
    ///     .i("/c", 3);
    /// let entry = tree.entry(&"/a/b".into());
    /// assert_eq!(entry.value(), Some(&2));
    /// ```
    pub fn entry(&self, path: &Path<B>) -> Entry<&Self, N, B, TREEBOUND> {
        Self::get_entry(self, path)
    }

    /// Returns an [Entry] with mutable access to the given position in the tree.
    ///
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<usize, String> = Tree::new();
    /// tree.i("/", 0)
    ///     .i("/a", 1)
    ///     .i("/a/b", 2)
    ///     .i("/c", 3);
    /// let mut entry = tree.entry_mut(&"/a/b/d".into());
    /// assert_eq!(entry.or_insert(4), &mut 4);
    /// ```
    pub fn entry_mut(&mut self, path: &Path<B>) -> Entry<&mut Self, N, B, TREEBOUND> {
        Self::get_entry(self, path)
    }

    /// Returns an Entry to the given position in the given tree.
    fn get_entry<R: Deref<Target = Tree<N, B>>>(s: R, path: &Path<B>) -> Entry<R, N, B, TREEBOUND> {
        match s.get_path_idxs(path) {
            Ok(idxs) => Node::from(s, AttachedPosition::from(path.clone(), idxs.into())).into(),
            Err(e) => DetachedEntry::from(
                s,
                DetachedPosition::from(
                    path.clone(),
                    e.map(|(idxs, _)| idxs.into()).unwrap_or_default(),
                ),
            )
            .into(),
        }
    }

    /// Inserts a value at the given [path].
    /// Returns the existing value if any.
    /// Insertions can be done on any existing node ([path] points to an existing node)
    /// or on children of existing nodes ([path] points to
    /// an inexistent immediate child of an existing node).
    /// Insertions cannot be done if [path] points to a node further away
    /// from the existing tree as it cannot close the gap between the last
    /// existing node and the new one to insert.
    /// In this case the operation will fail and the [Path] to the closest
    /// existing node will be returned.
    ///
    /// # Examples
    ///
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let mut tree: Tree<_, String> = Tree::new();
    /// // Set root
    /// assert_eq!(tree.insert(&"/".into(), 0), Ok(None));
    /// // Append node
    /// assert_eq!(tree.insert(&"/a".into(), 1), Ok(None));
    /// // Overwrite existing node
    /// assert_eq!(tree.insert(&"/a".into(), 2), Ok(Some(1)));
    /// // Leave tree
    /// assert_eq!(tree.insert(&"/a/b/c".into(), 2), Err(Some("/a".into())));
    /// ```
    pub fn insert(&mut self, path: &Path<B>, value: N) -> Result<Option<N>, Option<Path<B>>> {
        let mut path = path.clone();
        if let Some(child) = path.pop_last() {
            Ok(self
                .insert_at(
                    self.get_idx(&path, None)
                        .map_err(|r| r.map(|(_, i)| path.path_to(i)))?,
                    child,
                    value,
                )
                .0)
        } else {
            Ok(self.insert_root(value))
        }
    }

    //TODO: Remove the nodes immediately and return the nodes as a Tree
    /// Removes the subtree at the given [path] from the tree
    /// If the root node is not found, it returns the path to the closest
    /// existing node, or None if the tree is empty.
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let mut tree1: Tree<usize, String> = Tree::new();
    /// tree1.insert(&"/".into(), 0);
    /// tree1.insert(&"/a".into(), 1);
    /// tree1.insert(&"/a".into(), 2);
    /// tree1.insert(&"/b".into(), 3);
    /// let mut tree2 = tree1.clone();
    ///
    /// // Add a branch to tree2
    /// tree2.insert(&"/c".into(), 4);
    /// tree2.insert(&"/c/d".into(), 5);
    ///
    /// // Remove the branch
    /// tree2.remove_subtree(&"/c".into());
    /// assert_eq!(tree1, tree2);
    /// ```
    pub fn remove_subtree(&mut self, path: &Path<B>) -> Result<(), Option<Path<B>>> {
        let mut path = path.clone();
        if self.is_empty() {
            Err(None)
        } else if let Some(child) = path.pop_last() {
            // Remove a node
            let parent_idx = self
                .get_idx(&path, None)
                .map_err(|r| r.map(|(_, i)| path.path_to(i)))?;
            self.remove_subtree_at(parent_idx, child)
                .map(|_| ())
                .ok_or(Some(path))
        } else {
            // Root is being removed
            self.nodes.clear();
            self.removed.clear();
            Ok(())
        }
    }

    /// Applies the differential to the tree without checking its validity beforehand
    ///
    /// Nodes that can't be added or removed are skipped.
    ///
    /// # Examples
    /// ```
    /// use nb_tree::prelude::{Tree, DiffTree};
    /// let mut tree1: Tree<usize, String> = Tree::new();
    /// tree1.i("/", 0)
    ///     .i("/a", 1)
    ///     .i("/a/b", 2)
    ///     .i("/c", 3);
    /// let mut diff: DiffTree<usize, String> = DiffTree::new();
    /// diff.i("/", (Some(0), Some(9)))
    ///     .i("/a", (Some(1), Some(2)))
    ///     .i("/a/w", (Some(2), Some(100)))
    ///     .i("/x", (Some(40), None))
    ///     .i("/z", (None, Some(200)))
    ///     .i("/c", (None, Some(4)));
    /// tree1.force_apply(diff);
    ///
    /// let mut tree_applied: Tree<usize, String> = Tree::new();
    /// tree_applied.i("/", 9)
    ///     .i("/a", 2)
    ///     .i("/a/b", 2)
    ///     .i("/a/w", 100)
    ///     .i("/z", 200)
    ///     .i("/c", 4);
    /// assert_eq!(tree1, tree_applied);
    /// ```
    pub fn force_apply(&mut self, diff: DiffTree<N, B>) -> bool {
        self.force_apply_with(
            diff,
            |entry, now| entry.insert(now).is_some(),
            |entry| {
                replace_with_or_abort(entry, |e| e.remove_subtree());
                true
            },
        )
    }
    pub fn force_apply_with<'a>(
        &'a mut self,
        diff: DiffTree<N, B>,
        insert: InsertWith<&'a mut Tree<N, B>, N, B, false>,
        delete: DeleteWith<&'a mut Tree<N, B>, N, B, false>,
    ) -> bool {
        let mut apply_success = true;
        let mut diff = diff.into_iter();
        // Manage the root
        let mut entry = self.entry_mut(&Path::new());
        let mut deleted = None;
        match diff.next() {
            Some(Traversal::Start((b, n))) => {
                if let Some(now) = n {
                    // New or change node
                    apply_success = insert(&mut entry, now);
                } else if b.is_some() {
                    // Remove node
                    // Deleted root prevents any further change
                    delete(&mut entry);
                    return diff.next().is_none();
                }
            }
            None => {
                // Empty diff
                return true;
            }
            Some(_) => {
                unreachable!("Tree iteration should always start with a Root node");
            }
        };

        for d in diff {
            entry.apply_move(&d);
            if let Some(d) = deleted {
                // Remove if at the same path level (the targetted node
                // will thus have changed)
                if d >= entry.path().len() {
                    deleted = None;
                }
            }
            let (b, n) = d.take();

            if let Some(now) = n {
                // New or change node
                if deleted.is_some() {
                    apply_success = false;
                } else if !insert(&mut entry, now) {
                    // Extend needed
                    apply_success = false;
                }
            } else if b.is_some() {
                // Remove node
                if deleted.is_none() {
                    deleted = Some(entry.path().len());
                    if entry.is_node() {
                        delete(&mut entry);
                    } else {
                        apply_success = false;
                    }
                } // else if a parent has been deleted, no further deleting is necessary
            }
        }
        apply_success
    }

    /// Combines two trees together following a given mode
    ///
    /// The mode specifies whether to :
    ///     - keep the nodes only present in the initial tree
    ///     - grow the tree with nodes only present in the other tree
    ///     - overwrite the nodes' data with the ones of the other tree
    ///
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// use nb_tree::tree::CombinationMode;
    /// let mut tree1: Tree<usize, String> = Tree::new();
    /// tree1.i("/", 0)
    ///     .i("/a", 1)
    ///     .i("/a/b", 2)
    ///     .i("/c", 3);
    ///
    /// let mut tree2: Tree<usize, String> = Tree::new();
    /// tree2.i("/", 10)
    ///      .i("/a", 11)
    ///      .i("/a/d", 7);
    ///
    /// tree1.combine(tree2, CombinationMode::Free{keep: true, grow: true, overwrite: true});
    /// let mut tree_res = Tree::new();
    /// tree_res.i("/", 10)
    ///         .i("/a", 11)
    ///         .i("/a/d", 7)
    ///         .i("/a/b", 2)
    ///         .i("/c", 3);
    ///
    /// assert_eq!(tree1, tree_res);
    /// ```
    pub fn combine(&mut self, tree: Tree<N, B>, mode: CombinationMode) -> bool {
        self.combine_with(tree, mode, |entry, now| entry.insert(now).is_some())
    }

    pub(crate) fn combine_with<'a>(
        &'a mut self,
        tree: Tree<N, B>,
        mode: CombinationMode,
        grow: InsertWith<&'a mut Tree<N, B>, N, B, false>,
    ) -> bool {
        let mut entry = self.root_entry_mut();
        let iter: IntoIter<N, B, TreeNode<N, B>> = IntoIter::new(tree);

        for step in iter {
            // check if above root node
            if entry.apply_move(&step).is_err() {
                // left the (sub)tree
                // return before iteration end
                return false;
            }
            if let Some(node) = entry.node_mut() {
                // remove ignored if not kept
                if !mode.keep() {
                    node.remove_child_subtrees(
                        node.children()
                            .into_iter()
                            .filter(|&c| step.data().children.contains_key(c))
                            .cloned()
                            .collect(),
                    );
                }
                if mode.overwrite() {
                    // overwrite
                    node.insert(step.take().value);
                }
            } else if mode.grow() {
                // grow
                grow(&mut entry, step.take().value);
            }
        }
        true
    }
}

type InsertWith<R, N, B, const BND: bool> = fn(&mut Entry<R, N, B, BND>, N) -> bool;
type DeleteWith<R, N, B, const BND: bool> = fn(&mut Entry<R, N, B, BND>) -> bool;

/// Description of how two trees will be combinedthe way the way
pub enum CombinationMode {
    /// Keeps and grows the tree, overwriting the data if the boolean is set to true
    Union(bool),
    /// Only keeps nodes common to both trees, overwriting the data if the boolean is set to true
    Intersection(bool),
    /// Specify manually the data to be kept and removed
    Free {
        /// Keep nodes only present in the first tree
        keep: bool,
        /// Keep nodes only present in the second tree
        grow: bool,
        /// Overwrites data in nodes common to both trees
        overwrite: bool,
    },
}

impl CombinationMode {
    pub fn keep(&self) -> bool {
        use CombinationMode::*;
        match self {
            Union(_) => true,
            Intersection(_) => false,
            Free { keep, .. } => *keep,
        }
    }
    pub fn grow(&self) -> bool {
        use CombinationMode::*;
        match self {
            Union(_) => true,
            Intersection(_) => false,
            Free { grow, .. } => *grow,
        }
    }
    pub fn overwrite(&self) -> bool {
        use CombinationMode::*;
        match self {
            Union(overwrite) => *overwrite,
            Intersection(overwrite) => *overwrite,
            Free { overwrite, .. } => *overwrite,
        }
    }
}

impl<N, B> Tree<N, B>
where
    B: Eq + Hash + Clone + Dbg,
{
    /// Chainable insertion
    /// Calls `insert` and returns a mutable reference to self
    /// # Panics
    /// Panics if the insertion fails
    pub fn i(&mut self, path: impl Into<Path<B>>, value: N) -> &mut Self {
        let ph: Path<B> = path.into();
        self.insert(&ph, value)
            .unwrap_or_else(|_| panic!("Could not insert into the tree at {:?}", &ph));
        self
    }
}

impl<N, B> Tree<N, B>
where
    N: Eq,
    B: Eq + Hash,
{
    /// # Warning
    /// It does not check for index validity.
    fn is_subtree_eq(&self, idx_s: usize, o: &Self, idx_o: usize) -> bool {
        let ns = &self.nodes[idx_s];
        let no = &o.nodes[idx_o];
        ns.value == no.value
            && ns.children.len() == no.children.len()
            && !ns.children.keys().any(|branch| {
                !self.is_subtree_eq(
                    *or_return!(ns.children.get(branch), false),
                    o,
                    *or_return!(no.children.get(branch), false),
                )
            })
    }
}
impl<N, B> Tree<N, B>
where
    N: Eq,
    B: Eq + Hash + Clone,
{
    /// Applies the differential to the tree if it is valid
    ///
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let mut tree1: Tree<usize, String> = Tree::new();
    /// tree1.i("/", 0)
    ///     .i("/a", 1)
    ///     .i("/a/b", 2)
    ///     .i("/c", 3)
    ///     .i("/f", 4)
    ///     .i("/f/d", 5);
    /// let mut tree2: Tree<usize, String> = Tree::new();
    /// tree2
    ///     .i("/", 9)
    ///     .i("/a", 2)
    ///     .i("/a/b", 1)
    ///     .i("/c", 3)
    ///     .i("/c/d", 4)
    ///     .i("/c/d/e", 2);
    /// let mut diff = tree1.diff(&tree2);
    /// // taking back `tree1`, `tree2` and `diff` from the previous example
    /// let tree1_orig = tree1.clone();
    /// // Apply the differential between `tree1` and `tree2`
    /// tree1.apply(diff.clone()).unwrap();
    /// // They are both equal now
    /// assert_eq!(tree1, tree2, "Both trees are not equal");
    /// // Applying the reversed diff will restore tree1
    /// diff.rev();
    /// tree1.apply(diff).unwrap();
    /// assert_eq!(tree1, tree1_orig);
    /// ```
    pub fn apply(&mut self, diff: DiffTree<N, B>) -> Result<bool, DiffApplyError<B>> {
        // Check diff
        diff.is_applicable(self)?;

        // Apply diff
        Ok(self.force_apply(diff))
    }

    /// Applies a DiffNode at the given Path in the tree
    ///
    /// # Examples
    /// ```
    /// use nb_tree::prelude::Tree;
    /// let mut tree1: Tree<usize, String> = Tree::new();
    /// tree1.i("/", 0)
    ///     .i("/a", 1)
    ///     .i("/a/b", 2)
    ///     .i("/c", 3);
    /// let mut tree2 = tree1.clone();
    /// tree2.i("/a/b/d", 7);
    /// tree1.apply_diff("/a/b/d".into(), (None, Some(7)));
    /// assert_eq!(tree1, tree2);
    /// ```
    pub fn apply_diff(
        &mut self,
        path: Path<B>,
        diff: DiffNode<N>,
    ) -> Result<(), DiffApplyError<B>> {
        self.apply_diff_with(path, diff, |entry, v| {
            if entry.offshoot_len() <= 1 {
                entry.insert(v);
                Ok(())
            } else {
                Err(DiffApplyError::Other("Expected Parent".to_string()))
            }
        })
    }

    /// Applies the DiffNode at the given Path according to the given insertion function
    fn apply_diff_with(
        &mut self,
        path: Path<B>,
        diff: DiffNode<N>,
        insert: fn(&mut TreeMutEntry<N, B, TREEBOUND>, N) -> Result<(), DiffApplyError<B>>,
    ) -> Result<(), DiffApplyError<B>> {
        let mut entry = self.entry_mut(&path);
        if diff.0.is_some() {
            if entry.is_detached() {
                return Err(DiffApplyError::Expected(path));
            }
            if let Some(value) = diff.1 {
                // Change
                entry.insert(value);
                Ok(())
            } else {
                // Delete
                entry.remove_subtree();
                Ok(())
            }
        } else if let Some(value) = diff.1 {
            // New or change
            insert(&mut entry, value)
        } else {
            Ok(())
        }
    }

    /// Applies a DiffMap to the tree
    ///
    /// Returns true if all diffs have been applied, and false otherwise
    pub fn apply_map(&mut self, map: DiffMap<N, B>) -> bool {
        map.into_iter().fold(true, |mut res, (ph, diff)| {
            if self.apply_diff(ph, diff).is_err() {
                res = false;
            }
            res
        })
    }
}

#[cfg(test)]
mod tests {
    use std::collections::{HashMap, HashSet};

    use test_log::test;
    use tracing::{debug, trace};

    use crate::prelude::{iter::depth::Traversal, DiffTree, Tree};

    fn new_tree() -> Tree<usize, String> {
        let mut tree: Tree<usize, String> = Tree::new();
        tree.i("/", 0)
            .i("/a", 1)
            .i("/a/b", 2)
            .i("/c", 3)
            .i("/f", 4)
            .i("/f/d", 5);
        tree
    }

    #[test]
    fn index() {
        let mut tree1 = new_tree();
        assert_eq!(tree1[&"/".into()], 0);
        assert_eq!(tree1[&"/a".into()], 1);
        assert_eq!(tree1[&"/f/d".into()], 5);
        tree1.i("/z", 2);
        assert_eq!(tree1[&"/z".into()], 2);
    }

    #[test]
    #[should_panic]
    fn index_inexistent1() {
        let tree1 = new_tree();
        tree1[&"/w".into()];
    }

    #[test]
    #[should_panic]
    fn index_inexistent2() {
        let tree1 = new_tree();
        tree1[&"/f/d/z".into()];
    }

    #[test]
    #[should_panic]
    fn index_inexistent3() {
        let tree1 = new_tree();
        tree1[&"/f/a".into()];
    }

    #[test]
    fn eq_tree() {
        let tree1 = new_tree();
        // Same
        assert_eq!(tree1, new_tree());
        // Empty
        assert_eq!(Tree::<usize, usize>::new(), Tree::<usize, usize>::new());
        // Different branch
        let mut tree_branch = new_tree();
        tree_branch.i("/w", 7);
        assert_ne!(tree1, tree_branch);
        // Different value
        let mut tree_value = new_tree();
        tree_value.i("/a", 7);
        assert_ne!(tree1, tree_value);
        // One is empty
        assert_ne!(tree1, Tree::<usize, String>::new());
    }

    #[test]
    fn new() {
        let tree1: Tree<usize, String> = Tree::new();
        assert!(tree1.is_empty());
    }

    #[test]
    fn get_root() {
        let mut tree1: Tree<usize, String> = Tree::new();
        assert!(tree1.get_root().is_none());
        tree1.i("/", 5);
        assert_eq!(tree1.get_root(), Some(&5));
    }

    #[test]
    fn get_root_idx() {
        let mut tree1: Tree<usize, String> = Tree::new();
        assert!(tree1.get_root().is_none());
        tree1.i("/", 5);
        assert!(tree1.get_root().is_some());
    }

    #[test]
    fn insert_root() {
        let mut tree1: Tree<usize, String> = Tree::new();
        assert_eq!(tree1.insert_root(0), None);
        assert_eq!(tree1.len(), 1);
        assert_eq!(tree1.insert_root(1), Some(0));
        assert_eq!(tree1.insert_root(1), Some(1));
        assert_eq!(tree1.insert_root(2), Some(1));
        assert_eq!(tree1.insert_root(3), Some(2));
        tree1.clear();
        assert_eq!(tree1.insert_root(1), None);
        assert_eq!(tree1.insert_root(3), Some(1));
        tree1.i("/branch", 7);
        assert_eq!(tree1.len(), 2);
        assert_eq!(tree1.insert_root(5), Some(3));
        assert_eq!(tree1.len(), 2);
        assert_eq!(tree1.get_root(), Some(&5));
    }

    #[test]
    fn clear() {
        let mut tree1: Tree<usize, String> = new_tree();
        tree1.clear();
        assert_eq!(tree1, Tree::new());
        tree1.i("/", 1);
        let mut small_tree = Tree::new();
        small_tree.i("/", 1);
        assert_eq!(tree1, small_tree);
        tree1.clear();
        assert_eq!(tree1, Tree::new());
        tree1.i("/", 1);
        tree1.i("/i", 2);
        tree1.i("/v", 2);
        tree1.i("/c", 5);
        tree1.i("/c/d", 3);
        tree1.remove_subtree(&"/c".into()).unwrap();
        tree1.remove_subtree(&"/i".into()).unwrap();
        tree1.remove_subtree(&"/v".into()).unwrap();
        assert_eq!(tree1, small_tree);
        tree1.clear();
        assert_eq!(tree1, Tree::new());
    }

    #[test]
    fn is_empty() {
        let mut tree1: Tree<usize, String> = Tree::new();
        assert!(tree1.is_empty());
        tree1.i("/", 0);
        assert!(!tree1.is_empty());
        tree1.clear();
        assert!(tree1.is_empty());
        tree1.ix("/a", 1);
        assert!(!tree1.is_empty());
    }

    #[test]
    fn len() {
        let mut tree1: Tree<usize, String> = Tree::new();
        assert_eq!(tree1.len(), 0);
        tree1.i("/", 1);
        assert_eq!(tree1.len(), 1);
        tree1.i("/a", 5);
        assert_eq!(tree1.len(), 2);
        tree1.i("/", 3);
        assert_eq!(tree1.len(), 2);
        tree1.i("/a/c", 6);
        assert_eq!(tree1.len(), 3);
        tree1.i("/a/c/d", 4);
        assert_eq!(tree1.len(), 4);
        tree1.i("/b", 8);
        assert_eq!(tree1.len(), 5);
        tree1.i("/b/e", 9);
        assert_eq!(tree1.len(), 6);
        tree1.remove_subtree(&"/a".into()).unwrap();
        assert_eq!(tree1.len(), 3);
        tree1.ix("/a/c", 1);
        assert_eq!(tree1.len(), 5);
        tree1.insert_root(10);
        assert_eq!(tree1.len(), 5);
        tree1.clear();
        assert_eq!(tree1.len(), 0);
        tree1.insert_root(100);
        assert_eq!(tree1.len(), 1);
    }

    #[test]
    fn values() {
        let mut tree1 = new_tree();
        tree1.i("/z", 2);
        let values: HashSet<usize> = HashSet::from_iter([0, 1, 2, 3, 4, 5, 2].into_iter());
        let tree_values: HashSet<usize> = HashSet::from_iter(tree1.values().into_iter().cloned());
        assert_eq!(tree_values, values);
    }

    #[test]
    fn iter_iter_on() {
        let tree1 = new_tree();
        let mut iter = tree1.iter_on::<()>();

        match iter.next().expect("Root node expected") {
            Traversal::Start(()) => (),
            _ => panic!("Expected a Root node"),
        }
        match iter.next().expect("Root child Node expected") {
            Traversal::Step {
                up,
                branch,
                data: (),
            } => {
                assert_eq!(up, 0);
                // The node is at branch "a"
                assert!(["a", "c", "f"].contains(&branch.as_str()));
            }
            _ => panic!("Expected Root child node"),
        }

        let mut tree2: Tree<Option<usize>, String> = Tree::new();
        tree2
            .i("/", Some(0))
            .i("/a", Some(1))
            .i("/a/b", Some(2))
            .i("/c", Some(3))
            .i("/f", Some(4))
            .i("/f/d", Some(5));
        let mut entry = tree2.root_entry_mut();
        let mut iter = tree1.iter();
        if let Traversal::Start(root) = iter.next().unwrap() {
            assert_eq!(entry.value().unwrap(), &Some(*root));
            entry.insert(None);
        } else {
            panic!("Expected a Root node")
        }
        for item in iter {
            if let Traversal::Step { up, branch, data } = item {
                entry.move_up(up);
                entry.move_down_branch(branch.clone());
                assert_eq!(
                    entry
                        .value()
                        .expect("Node inexistent")
                        .expect("Node already visited"),
                    *data
                );
                entry.insert(None);
            } else {
                panic!("Expected a Node")
            }
        }
        assert!(!tree2.iter().any(|item| item.data().is_some()));
    }

    #[test]
    fn get_idx_path_idxs() {
        let mut tree1 = new_tree();
        let mut map = HashMap::new();
        map.insert("/", tree1.get_idx(&"/".into(), None).unwrap());
        map.insert("/a", tree1.get_idx(&"/a".into(), None).unwrap());
        map.insert("/a/b", tree1.get_idx(&"/a/b".into(), None).unwrap());
        map.insert("/c", tree1.get_idx(&"/c".into(), None).unwrap());
        map.insert("/f", tree1.get_idx(&"/f".into(), None).unwrap());
        map.insert("/f/d", tree1.get_idx(&"/f/d".into(), None).unwrap());
        let values: HashSet<usize> = HashSet::from_iter(map.values().copied());
        assert_eq!(values.len(), 6);
        assert_eq!(tree1.get_idx(&"/b".into(), None), Err(Some((map["/"], 0))));
        assert_eq!(tree1.get_idx(&"/w".into(), None), Err(Some((map["/"], 0))));
        assert_eq!(
            tree1.get_idx(&"/b/a".into(), None),
            Err(Some((map["/"], 0)))
        );
        assert_eq!(
            tree1.get_idx(&"/x/y/z".into(), None),
            Err(Some((map["/"], 0)))
        );
        assert_eq!(
            tree1.get_idx(&"/a/d".into(), None),
            Err(Some((map["/a"], 1)))
        );
        assert_eq!(
            tree1.get_idx(&"/a/b/x".into(), None),
            Err(Some((map["/a/b"], 2)))
        );

        assert_eq!(
            Tree::<usize, String>::new().get_idx(&"/a".into(), None),
            Err(None)
        );

        assert_eq!(
            tree1.get_path_idxs(&"/a/b".into()),
            Ok(vec![map["/"], map["/a"], map["/a/b"]])
        );
        assert_eq!(
            tree1.get_path_idxs(&"/f/d".into()),
            Ok(vec![map["/"], map["/f"], map["/f/d"]])
        );
        assert_eq!(
            tree1.get_path_idxs(&"/a/b/w".into()),
            Err(Some((vec![map["/"], map["/a"], map["/a/b"]], 2)))
        );
        assert_eq!(
            Tree::<usize, String>::new().get_path_idxs(&"/a/b/w".into()),
            Err(None)
        );
    }

    #[test]
    fn insert_at() {
        let mut tree1 = Tree::new();
        assert_eq!(tree1.len(), 0);
        tree1.insert_root(0);
        assert_eq!(tree1.len(), 1);
        let (_, a_idx) = tree1.insert_at(tree1.get_root_idx().unwrap(), "a".to_string(), 1);
        assert_eq!(tree1.len(), 2);
        tree1.insert_at(a_idx, "b".to_string(), 2);
        assert_eq!(tree1.len(), 3);
        tree1.insert_at(tree1.get_root_idx().unwrap(), "c".to_string(), 3);
        assert_eq!(tree1.len(), 4);
        let (_, f_idx) = tree1.insert_at(tree1.get_root_idx().unwrap(), "f".to_string(), 4);
        assert_eq!(tree1.len(), 5);
        tree1.insert_at(f_idx, "d".to_string(), 5);
        assert_eq!(tree1.len(), 6);
        assert_eq!(tree1, new_tree());
        tree1.insert_at(tree1.get_root_idx().unwrap(), "a".to_string(), 1);
        assert_eq!(tree1.len(), 6);
        assert_eq!(tree1, new_tree());
    }

    #[test]
    #[should_panic]
    fn insert_at_panic_parent() {
        new_tree().insert_at(7, "P".to_string(), 2);
    }

    #[test]
    fn remove_subtree_at() {
        let mut tree1 = new_tree();
        tree1.remove_subtree_at(tree1.get_root_idx().unwrap(), "a".to_string());
        assert_eq!(tree1.len(), 4);
        tree1.remove_subtree_at(tree1.get_root_idx().unwrap(), "c".to_string());
        assert_eq!(tree1.len(), 3);
        tree1.remove_subtree_at(tree1.get_idx(&"/f".into(), None).unwrap(), "d".to_string());
        assert_eq!(tree1.len(), 2);
        tree1.remove_subtree_at(tree1.get_root_idx().unwrap(), "f".to_string());
        assert_eq!(tree1.len(), 1);
    }

    #[test]
    fn get() {
        let mut tree1: Tree<usize, String> = Tree::new();
        // Can't get any node from an empty node
        assert_eq!(tree1.get(&"/a/b/w".into()), Err(None));
        tree1 = new_tree();
        // Get a reference to the node data at "/a"
        assert_eq!(tree1.get(&"/a".into()), Ok(&1));
        assert_eq!(tree1.get(&"/a/b".into()), Ok(&2));
        // "/a/b/w" is out of the tree, "/a/b" being the last node in the tree of the path
        assert_eq!(tree1.get(&"/a/b/w".into()), Err(Some("/a/b".into())));
        assert_eq!(tree1.get(&"/b/a".into()), Err(Some("/".into())));
    }

    #[test]
    fn get_mut() {
        let mut tree1: Tree<usize, String> = Tree::new();
        // Can't get any node from an empty node
        assert_eq!(tree1.get_mut(&"/a/b/w".into()), Err(None));
        tree1 = new_tree();
        // Get a reference to the node data at "/a"
        assert_eq!(tree1.get_mut(&"/a".into()), Ok(&mut 1));
        assert_eq!(tree1.get_mut(&"/a/b".into()), Ok(&mut 2));
        // "/a/b/w" is out of the tree, "/a/b" being the last node in the tree of the path
        assert_eq!(tree1.get_mut(&"/a/b/w".into()), Err(Some("/a/b".into())));
        assert_eq!(tree1.get_mut(&"/b/a".into()), Err(Some("/".into())));
    }

    #[test]
    fn root_entry() {
        let mut tree1: Tree<usize, String> = Tree::new();
        let entry = tree1.root_entry();
        assert!(!entry.is_node());
        tree1.i("/", 7).i("/c1", 1);
        let mut entry = tree1.root_entry();
        assert_eq!(entry.value(), Some(&7));
        entry.move_down_branch("c1".into());
        assert_eq!(entry.value(), Some(&1));
        tree1.clear();
        let entry = tree1.root_entry();
        assert!(!entry.is_node());
    }

    #[test]
    fn root_entry_mut() {
        let mut tree1: Tree<usize, String> = Tree::new();
        let mut entry = tree1.root_entry_mut();
        assert!(!entry.is_node());
        assert_eq!(entry.or_insert(5), &mut 5);
        entry.move_down_branch("c1".into());
        assert_eq!(entry.or_insert(1), &mut 1);
        entry.move_up(1);
        assert!(entry.is_node());
    }

    #[test]
    fn entry() {
        let mut tree1: Tree<usize, String> = Tree::new();
        tree1.i("/", 0).i("/a", 1).i("/a/b", 2).i("/c", 3);
        let mut entry = tree1.entry(&"/a/b".into());
        assert_eq!(entry.value(), Some(&2));
        entry.move_up(1);
        assert_eq!(entry.value(), Some(&1));
        entry.move_up(1);
        assert_eq!(entry.value(), Some(&0));
    }

    #[test]
    fn entry_mut() {
        let mut tree1: Tree<usize, String> = Tree::new();
        tree1.i("/", 0).i("/a", 1).i("/a/b", 2).i("/c", 3);
        let mut entry = tree1.entry_mut(&"/a/b".into());
        assert_eq!(entry.or_insert(4), &mut 2);
        entry.move_up(2);
        entry.move_down_branch("f".into());
        assert_eq!(entry.or_insert(4), &mut 4);
        entry.move_down_branch("e".into());
        assert_eq!(entry.or_insert(5), &mut 5);
        assert_eq!(tree1, new_tree());
    }

    /*
    #[test]
    fn get_entry() {
    }*/

    #[test]
    fn insert() {
        let mut tree1: Tree<_, String> = Tree::new();
        assert_eq!(tree1.insert(&"/".into(), 0), Ok(None));
        assert_eq!(tree1.insert(&"/a".into(), 2), Ok(None));
        assert_eq!(tree1.insert(&"/a".into(), 1), Ok(Some(2)));
        assert_eq!(tree1.insert(&"/a/b/c".into(), 2), Err(Some("/a".into())));
        assert_eq!(tree1.insert(&"/a/b".into(), 2), Ok(None));
        assert_eq!(tree1.insert(&"/c".into(), 3), Ok(None));
        assert_eq!(tree1.insert(&"/f".into(), 4), Ok(None));
        assert_eq!(tree1.insert(&"/f/e".into(), 5), Ok(None));
        assert_eq!(tree1, new_tree());
        tree1.clear();
        assert_eq!(tree1.len(), 0);
        assert_eq!(tree1.insert(&"/a/b/c".into(), 2), Err(None));
        assert_eq!(tree1.insert(&"/".into(), 7), Ok(None));
        assert_eq!(tree1.len(), 1);
        assert_eq!(tree1[&"/".into()], 7);
    }

    #[test]
    fn remove_subtree() {
        let mut tree1: Tree<usize, String> = Tree::new();
        tree1.insert(&"/".into(), 0).unwrap();
        tree1.insert(&"/a".into(), 1).unwrap();
        tree1.insert(&"/a".into(), 2).unwrap();
        tree1.insert(&"/b".into(), 3).unwrap();
        let mut tree2 = tree1.clone();

        // Add a branch to tree2
        tree2.insert(&"/c".into(), 4).unwrap();
        tree2.insert(&"/c/d".into(), 5).unwrap();

        // Remove the branch
        tree2.remove_subtree(&"/c".into()).unwrap();
        assert_eq!(tree1, tree2);
    }

    #[test]
    fn force_apply() {
        let mut tree1 = new_tree();
        let mut diff = Tree::new();
        let mut tree_res = Tree::new();

        diff.i("/", (Some(0), Some(9)))
            .i("/a", (None, None))
            .i("/a/b", (Some(2), Some(8)))
            .i("/f", (Some(4), None))
            .i("/f/g", (Some(1000), Some(14))) // wrong initial value and change below deletion
            .i("/c", (None, Some(12))) // wrong initial value
            .i("/c/e", (None, Some(11)));
        assert!(!tree1.force_apply(diff.clone()));

        tree_res
            .i("/", 9)
            .i("/a", 1)
            .i("/a/b", 8)
            .i("/c", 12)
            .i("/c/e", 11);

        assert_eq!(tree1, tree_res, "Both trees are not equal");
    }

    #[test]
    fn combine() {}

    #[test]
    fn i() {}

    #[test]
    fn is_subtree_eq() {}

    #[test]
    fn apply() {
        let mut tree1 = new_tree();
        let mut tree_diff = DiffTree::new();
        tree_diff
            .i("/", (None, None))
            .i("/a", (Some(1), None))
            .i("/c", (Some(3), Some(10)))
            .i("/c/f", (None, Some(11)))
            .i("/c/f/g", (None, Some(12)));

        let mut tree_res: Tree<usize, String> = Tree::new();
        tree_res
            .i("/", 0)
            .i("/c", 10)
            .i("/c/f", 11)
            .i("/c/f/g", 12)
            .i("/f", 4)
            .i("/f/d", 5);
        // Apply the differential between `tree1` and `tree2`
        tree1.apply(tree_diff).unwrap();
        // They are both equal now
        assert_eq!(tree1, tree_res, "Both trees are not equal");
    }

    #[test]
    fn apply_diff() {}

    #[test]
    fn apply_diff_with() {}

    #[test]
    fn apply_map() {}
}

/*
pub fn move_subtree(
    &mut self,
    from: Path<B>,
    to: Path<B>,
    destination: Option<&mut Tree<N, B>>,
) -> Result<(), Path<B>> {
    let path_idxs = self
        .get_path_idxs(path)
        .map_err(|(_, idx)| path.path_to(idx))?;

    //remove children
    self.move_subtree(path_idxs.pop().unwrap());
    let mut attr = path.pop_leaf();

    //remove empty parent nodes
    while !path_idxs.is_empty() && self.nodes[path_idxs.last()].children.len() == 1 {
        self.nodes.remove(path_idxs.pop().unwrap());
        attr = path.pop_leaf();
    }

    //remove child link of parent
    if !path_idxs.is_empty() {
        self.nodes[path_idxs].children.remove(attr);
    }
    Ok(())
}*/
//fn move_subtree(&mut self, from: NodeIDX, to: NodeIDX, tree: &mut Tree<N, B>) {
//      tree.nodes[to].children.insert(attr, tree.nodes.len());
//      tree.nodes.push(TreeNode {})
//      self.remove_subtree(idx, );