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, );