orange_trees/lib.rs
1//! # orange-trees
2//!
3//! [orange-trees](https://github.com/veeso/orange-trees) is a Rust implementation of the Tree data structure
4//!
5//! ## Get Started
6//!
7//! ### Add `orange-trees` to your dependencies
8//!
9//! ```toml
10//! orange-trees = "0.1"
11//! ```
12//!
13//! ### Initialize a tree
14//!
15//! Orange-trees provides three ways to initialize trees:
16//!
17//! 1. using the `node!` macro
18//! 2. Using the `with_child` constructor nested structure
19//! 3. Using `with_children`
20//!
21//! ```rust
22//! # #[macro_use] extern crate orange_trees;
23//! use orange_trees::{Tree, Node};
24//!
25//! // Create a tree using macro
26//! let tree: Tree<&'static str, &'static str> = Tree::new(
27//! node!("/", "/"
28//! , node!("/bin", "bin/"
29//! , node!("/bin/ls", "ls")
30//! , node!("/bin/pwd", "pwd")
31//! )
32//! , node!("/tmp", "tmp/"
33//! , node!("/tmp/dump.txt", "dump.txt")
34//! , node!("/tmp/omar.txt", "omar.txt")
35//! )
36//! )
37//! );
38//!
39//! // Create a tree using constructor
40//! let tree: Tree<&'static str, &'static str> = Tree::new(
41//! Node::new("/", "/")
42//! .with_child(
43//! Node::new("/bin", "bin/")
44//! .with_child(Node::new("/bin/ls", "ls"))
45//! .with_child(Node::new("/bin/pwd", "pwd"))
46//! )
47//! .with_child(
48//! Node::new("/tmp", "tmp/")
49//! .with_child(Node::new("/tmp/dump.txt", "dump.txt"))
50//! .with_child(Node::new("/tmp/omar.txt", "omar.txt"))
51//! .with_child(
52//! Node::new("/tmp/.cache", "cache/")
53//! .with_child(Node::new("/tmp/.cache/xyz.cache", "xyz.cache"))
54//! )
55//! ),
56//! );
57//!
58//! // With-children
59//!
60//! let tree: Tree<String, &str> =
61//! Tree::new(Node::new("a".to_string(), "a").with_children(vec![
62//! Node::new("a1".to_string(), "a1"),
63//! Node::new("a2".to_string(), "a2"),
64//! ]));
65//! ```
66//!
67//! ### Query a tree
68//!
69//! There are many functions to query nodes' attributes, such as their value, their depth and their children.
70//! In addition to these, there are also functions to search nodes by predicate or by id.
71//!
72//! ```rust
73//! use orange_trees::{Node, Tree};
74//!
75//! let tree: Tree<&'static str, &'static str> = Tree::new(
76//! Node::new("/", "/")
77//! .with_child(
78//! Node::new("/bin", "bin/")
79//! .with_child(Node::new("/bin/ls", "ls"))
80//! .with_child(Node::new("/bin/pwd", "pwd"))
81//! )
82//! .with_child(
83//! Node::new("/tmp", "tmp/")
84//! .with_child(Node::new("/tmp/dump.txt", "dump.txt"))
85//! .with_child(Node::new("/tmp/omar.txt", "omar.txt"))
86//! .with_child(
87//! Node::new("/tmp/.cache", "cache/")
88//! .with_child(Node::new("/tmp/.cache/xyz.cache", "xyz.cache"))
89//! )
90//! ),
91//! );
92//! // Query tree
93//! let bin: &Node<&'static str, &'static str> = tree.root().query(&"/bin").unwrap();
94//! assert_eq!(bin.id(), &"/bin");
95//! assert_eq!(bin.value(), &"bin/");
96//! assert_eq!(bin.children().len(), 2);
97//! // Find all txt files
98//! let txt_files: Vec<&Node<&'static str, &'static str>> = tree.root().find(&|x| x.value().ends_with(".txt") && x.is_leaf());
99//! assert_eq!(txt_files.len(), 2);
100//! // Count items
101//! assert_eq!(tree.root().query(&"/bin").unwrap().count(), 3);
102//! // Depth (max depth of the tree)
103//! assert_eq!(tree.root().depth(), 4);
104//! ```
105//!
106//! ### Manipulate trees
107//!
108//! Orange-trees provides a rich set of methods to manipulate nodes, which basically consists in:
109//!
110//! - Adding and removing children
111//! - Sorting node children
112//! - Truncating a node by depth
113//!
114//! ```rust
115//! use orange_trees::{Node, Tree};
116//!
117//! let mut tree: Tree<&'static str, &'static str> = Tree::new(
118//! Node::new("/", "/")
119//! .with_child(
120//! Node::new("/bin", "bin/")
121//! .with_child(Node::new("/bin/ls", "ls"))
122//! .with_child(Node::new("/bin/pwd", "pwd"))
123//! )
124//! .with_child(
125//! Node::new("/tmp", "tmp/")
126//! .with_child(Node::new("/tmp/dump.txt", "dump.txt"))
127//! .with_child(Node::new("/tmp/omar.txt", "omar.txt"))
128//! .with_child(
129//! Node::new("/tmp/.cache", "cache/")
130//! .with_child(Node::new("/tmp/.cache/xyz.cache", "xyz.cache"))
131//! )
132//! ),
133//! );
134//!
135//! // Remove child
136//! tree.root_mut().query_mut(&"/tmp").unwrap().remove_child(&"/tmp/.cache");
137//! assert!(tree.root().query(&"/tmp/.cache").is_none());
138//! // Add child
139//! tree.root_mut().add_child(Node::new("/var", "var/"));
140//! // Clear node
141//! tree.root_mut().query_mut(&"/tmp").unwrap().clear();
142//! assert_eq!(tree.root().query(&"/tmp").unwrap().count(), 1);
143//! // Sort tree
144//! let mut tree: Tree<&'static str, usize> = Tree::new(
145//! Node::new("/", 0)
146//! .with_child(Node::new("8", 8))
147//! .with_child(Node::new("7", 7))
148//! .with_child(Node::new("3", 3))
149//! .with_child(Node::new("1", 1))
150//! .with_child(Node::new("2", 2))
151//! .with_child(Node::new("9", 9))
152//! .with_child(Node::new("5", 5))
153//! .with_child(Node::new("4", 4))
154//! .with_child(Node::new("6", 6)),
155//! );
156//! tree.root_mut()
157//! .sort(|a, b| a.value().partial_cmp(b.value()).unwrap());
158//! let values: Vec<usize> = tree.root().iter().map(|x| *x.value()).collect();
159//! assert_eq!(values, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
160//! ```
161//!
162//! ### Working with routes
163//!
164//! Whenever you want to track the state of the tree (such as tracking opened nodes or selected one), routes come handy to do so.
165//! Routes are basically the path, described by child index, to go from the parent node to the child node.
166//! You can get the route for a node and then the node associated to a route with two simple functions:
167//!
168//! ```rust
169//! use orange_trees::{Node, Tree};
170//!
171//! let tree: Tree<String, &str> = Tree::new(
172//! Node::new("/".to_string(), "/")
173//! .with_child(
174//! Node::new("/bin".to_string(), "bin/")
175//! .with_child(Node::new("/bin/ls".to_string(), "ls"))
176//! .with_child(Node::new("/bin/pwd".to_string(), "pwd")),
177//! )
178//! .with_child(
179//! Node::new("/home".to_string(), "home/").with_child(
180//! Node::new("/home/omar".to_string(), "omar/")
181//! .with_child(Node::new("/home/omar/readme.md".to_string(), "readme.md"))
182//! .with_child(Node::new(
183//! "/home/omar/changelog.md".to_string(),
184//! "changelog.md",
185//! )),
186//! ),
187//! ),
188//! );
189//! // -- node_by_route
190//! assert_eq!(
191//! tree.root().node_by_route(&[1, 0, 1]).unwrap().id(),
192//! "/home/omar/changelog.md"
193//! );
194//! // -- Route by node
195//! assert_eq!(
196//! tree.root()
197//! .route_by_node(&"/home/omar/changelog.md".to_string())
198//! .unwrap(),
199//! vec![1, 0, 1]
200//! );
201//! ```
202//!
203
204#![doc(html_playground_url = "https://play.rust-lang.org")]
205#![doc(
206 html_favicon_url = "https://raw.githubusercontent.com/veeso/orange-trees/main/docs/images/cargo/orange-trees-128.png"
207)]
208#![doc(
209 html_logo_url = "https://raw.githubusercontent.com/veeso/orange-trees/main/docs/images/cargo/orange-trees-512.png"
210)]
211
212// deps
213use std::cmp::Ordering;
214use std::slice::{Iter, IterMut};
215
216/// represent the tree data structure inside the component.
217/// U: is the type for the [`Node`] indentifier (must implement [`PartialEq`])
218/// T: is the type for the [`Node`] value
219#[derive(Clone, Debug, Eq, PartialEq)]
220pub struct Tree<U, T> {
221 root: Node<U, T>,
222}
223
224impl<U: PartialEq, T> Tree<U, T> {
225 /// Instantiates a new [`Tree`]
226 pub fn new(root: Node<U, T>) -> Self {
227 Self { root }
228 }
229
230 /// Returns a reference to the root [`Node`]
231 pub fn root(&self) -> &Node<U, T> {
232 &self.root
233 }
234
235 /// Returns a mutable reference to the root [`Node`]
236 pub fn root_mut(&mut self) -> &mut Node<U, T> {
237 &mut self.root
238 }
239}
240
241/// Describes a node inside the [`Tree`]
242/// U: is the type for the node indentifier (must implement PartialEq)
243/// T: is the type for the node value
244#[derive(Clone, Debug, Eq, PartialEq)]
245pub struct Node<U, T> {
246 /// The node identifier
247 id: U,
248 /// The node value
249 value: T,
250 /// The node children
251 children: Vec<Node<U, T>>,
252}
253
254impl<U: PartialEq, T> Node<U, T> {
255 /// Instantiates a new [`Node`].
256 /// In order to use query methods the ID should be unique for each node in the tree
257 pub fn new(id: U, value: T) -> Self {
258 Self {
259 id,
260 value,
261 children: vec![],
262 }
263 }
264
265 /// Sets [`Node`] children
266 pub fn with_children(mut self, children: Vec<Node<U, T>>) -> Self {
267 // we use `with_child` to ensure that the children are correctly added and with no duplicates
268 self.children = Vec::with_capacity(children.len());
269 children.into_iter().for_each(|x| self.add_child(x));
270 self
271 }
272
273 /// Create a new child in this [`Node`]
274 pub fn with_child(mut self, child: Node<U, T>) -> Self {
275 self.add_child(child);
276 self
277 }
278
279 /// Get reference to id
280 pub fn id(&self) -> &U {
281 &self.id
282 }
283
284 /// Get reference to [`Node`] value
285 pub fn value(&self) -> &T {
286 &self.value
287 }
288
289 /// Set the value of the [`Node`]
290 pub fn set_value(&mut self, value: T) {
291 self.value = value;
292 }
293
294 /// Returns a reference to the [`Node`]'s children
295 pub fn children(&self) -> &[Node<U, T>] {
296 self.children.as_slice()
297 }
298
299 /// Returns an iterator over [`Node`]'s children
300 pub fn iter(&self) -> Iter<'_, Node<U, T>> {
301 self.children.iter()
302 }
303
304 /// Returns a mutable iterator over [`Node`]'s children
305 pub fn iter_mut(&mut self) -> IterMut<'_, Node<U, T>> {
306 self.children.iter_mut()
307 }
308
309 /// Add a child to the [`Node`]
310 ///
311 /// If the child already exists, it will be replaced
312 pub fn add_child(&mut self, child: Node<U, T>) {
313 // Override child if exists
314 if let Some(node) = self.children.iter_mut().find(|x| x.id() == child.id()) {
315 node.set_value(child.value);
316 } else {
317 self.children.push(child);
318 }
319 }
320
321 /// Remove child from [`Node`]
322 pub fn remove_child(&mut self, id: &U) {
323 self.children.retain(|x| x.id() != id);
324 }
325
326 /// Clear [`Node`]'s children
327 pub fn clear(&mut self) {
328 self.children.clear();
329 }
330
331 /// Truncate tree at depth.
332 /// If depth is `0`, [`Node`]'s children will be cleared
333 pub fn truncate(&mut self, depth: usize) {
334 if depth == 0 {
335 self.children.clear();
336 } else {
337 self.children.iter_mut().for_each(|x| x.truncate(depth - 1));
338 }
339 }
340
341 /// Sort node children by predicate
342 pub fn sort<F>(&mut self, compare: F)
343 where
344 F: FnMut(&Node<U, T>, &Node<U, T>) -> Ordering,
345 {
346 self.children.sort_by(compare);
347 }
348
349 /// Returns whether this [`Node`] is a leaf (which means it has no children)
350 pub fn is_leaf(&self) -> bool {
351 self.children.is_empty()
352 }
353
354 /// Search for `id` inside [`Node`] and return a reference to it, if exists
355 pub fn query(&self, id: &U) -> Option<&Self> {
356 if self.id() == id {
357 Some(self)
358 } else {
359 // Recurse search
360 self.children
361 .iter()
362 .map(|x| x.query(id))
363 .filter(|x| x.is_some())
364 .flatten()
365 .next()
366 }
367 }
368
369 /// Search for `id` inside [`Node`] and return a mutable reference to it, if exists
370 pub fn query_mut(&mut self, id: &U) -> Option<&mut Self> {
371 if self.id() == id {
372 Some(self)
373 } else {
374 // Recurse search
375 self.children
376 .iter_mut()
377 .map(|x| x.query_mut(id))
378 .filter(|x| x.is_some())
379 .flatten()
380 .next()
381 }
382 }
383
384 /// Find a node, in this branch, by predicate.
385 pub fn find<P>(&self, predicate: &P) -> Vec<&Self>
386 where
387 P: Fn(&Self) -> bool,
388 {
389 let mut result: Vec<&Self> = Vec::new();
390 if predicate(self) {
391 result.push(self);
392 }
393 // iter children and extend result
394 let children: Vec<Vec<&Self>> = self.iter().map(|x| x.find(predicate)).collect();
395 children.iter().for_each(|x| result.extend(x));
396 result
397 }
398
399 /// Count items in tree (including self)
400 pub fn count(&self) -> usize {
401 self.children.iter().map(|x| x.count()).sum::<usize>() + 1
402 }
403
404 /// Calculate the maximum depth of the tree
405 pub fn depth(&self) -> usize {
406 /// Private recursive call for depth
407 fn depth_r<U, T>(ptr: &Node<U, T>, depth: usize) -> usize {
408 ptr.children
409 .iter()
410 .map(|x| depth_r(x, depth + 1))
411 .max()
412 .unwrap_or(depth)
413 }
414 depth_r(self, 1)
415 }
416
417 /// Get parent [`Node`] of `id`
418 pub fn parent(&self, id: &U) -> Option<&Self> {
419 match self.route_by_node(id) {
420 None => None,
421 Some(route) => {
422 // Get parent
423 if route.is_empty() {
424 None
425 } else {
426 self.node_by_route(&route[0..route.len() - 1])
427 }
428 }
429 }
430 }
431
432 /// Get mutable parent [`Node`] of `id`
433 pub fn parent_mut(&mut self, id: &U) -> Option<&mut Self> {
434 match self.route_by_node(id) {
435 None => None,
436 Some(route) => {
437 // Get parent
438 if route.is_empty() {
439 None
440 } else {
441 self.node_by_route_mut(&route[0..route.len() - 1])
442 }
443 }
444 }
445 }
446
447 /// Get siblings for provided [`Node`]
448 pub fn siblings(&self, id: &U) -> Option<Vec<&U>> {
449 self.parent(id).map(|x| {
450 x.children
451 .iter()
452 .filter(|&x| x.id() != id)
453 .map(|x| x.id())
454 .collect()
455 })
456 }
457
458 /// Given a vector of indexes, returns the node associated to the route
459 pub fn node_by_route(&self, route: &[usize]) -> Option<&Self> {
460 if route.is_empty() {
461 Some(self)
462 } else {
463 let next: &Node<U, T> = self.children.get(route[0])?;
464 let route = &route[1..];
465 next.node_by_route(route)
466 }
467 }
468
469 /// Given a vector of indexes, returns the mutable [`Node`] associated to the route
470 pub fn node_by_route_mut(&mut self, route: &[usize]) -> Option<&mut Self> {
471 if route.is_empty() {
472 Some(self)
473 } else {
474 let next = self.children.get_mut(route[0])?;
475 let route = &route[1..];
476 next.node_by_route_mut(route)
477 }
478 }
479
480 /// Calculate the route of a [`Node`] by its id
481 pub fn route_by_node(&self, id: &U) -> Option<Vec<usize>> {
482 // Recursive function
483 fn route_by_node_r<U: PartialEq, T>(
484 node: &Node<U, T>,
485 id: &U,
486 enumerator: Option<usize>,
487 mut route: Vec<usize>,
488 ) -> Option<Vec<usize>> {
489 if let Some(enumerator) = enumerator {
490 route.push(enumerator);
491 }
492 if node.id() == id {
493 // Found!!!
494 Some(route)
495 } else if node.children.is_empty() {
496 // No more children
497 route.pop(); // Pop previous entry
498 None
499 } else {
500 // Keep searching
501 let mut result: Option<Vec<usize>> = None;
502 node.children.iter().enumerate().for_each(|(i, x)| {
503 let this_route: Vec<usize> = route.clone();
504 if let Some(this_route) = route_by_node_r(x, id, Some(i), this_route) {
505 result = Some(this_route);
506 }
507 });
508 result
509 }
510 }
511 // Call recursive function
512 route_by_node_r(self, id, None, Vec::with_capacity(self.depth()))
513 }
514}
515
516// -- node macro
517
518#[macro_export]
519/// Create a new [`Node`] using a macro
520///
521/// ## Arguments
522///
523/// - `id`: The node identifier
524/// - `value`: The node value
525/// - `more`: [`Node`] children
526///
527/// # Examples
528///
529/// Create a node with no children
530///
531/// ```rust
532/// use orange_trees::{Node, node};
533///
534/// let node: Node<&'static str, usize> = node!("root", 0);
535///```
536///
537/// Create a node with children
538///
539/// ```rust
540/// use orange_trees::{Node, node};
541///
542/// let node: Node<&'static str, usize> = node!("root", 0, node!("a", 1));
543/// ```
544///
545/// Create a nested node structure
546///
547/// ```rust
548/// use orange_trees::{Node, node};
549///
550/// let node: Node<&'static str, usize> = node!("root", 0, node!("a", 1, node!("a1", 3), node!("a2", 4)), node!("b", 0));
551/// ```
552///
553macro_rules! node {
554 ( $id:expr, $value:expr, $( $more:expr ),* ) => {{
555 let mut node = Node::new($id, $value);
556 $(
557 node.add_child($more);
558 )*
559 node
560 }};
561
562 ( $id:expr, $value:expr ) => {
563 Node::new($id, $value)
564 };
565}
566
567// -- tests
568
569#[cfg(test)]
570mod tests {
571
572 use pretty_assertions::assert_eq;
573
574 use super::*;
575
576 #[test]
577 fn test_query() {
578 // -- Build
579 let tree: Tree<String, &str> = Tree::new(
580 Node::new("/".to_string(), "/")
581 .with_child(
582 Node::new("/bin".to_string(), "bin/")
583 .with_child(Node::new("/bin/ls".to_string(), "ls"))
584 .with_child(Node::new("/bin/pwd".to_string(), "pwd")),
585 )
586 .with_child(
587 Node::new("/home".to_string(), "home/").with_child(
588 Node::new("/home/omar".to_string(), "omar/")
589 .with_child(Node::new("/home/omar/readme.md".to_string(), "readme.md"))
590 .with_child(Node::new(
591 "/home/omar/changelog.md".to_string(),
592 "changelog.md",
593 )),
594 ),
595 ),
596 );
597 let root: &Node<String, &str> = tree.root();
598 assert_eq!(root.id(), "/");
599 assert_eq!(root.value(), &"/");
600 assert_eq!(root.children.len(), 2);
601 let bin: &Node<String, &str> = &root.children[0];
602 assert_eq!(bin.id(), "/bin");
603 assert_eq!(bin.value(), &"bin/");
604 assert_eq!(bin.children.len(), 2);
605 let bin_ids: Vec<&String> = bin.children.iter().map(|x| x.id()).collect();
606 assert_eq!(bin_ids, vec!["/bin/ls", "/bin/pwd"]);
607 let home: &Node<String, &str> = &tree.root.children[1];
608 assert_eq!(home.id(), "/home");
609 assert_eq!(home.value(), &"home/");
610 assert_eq!(home.children.len(), 1);
611 let omar_home: &Node<String, &str> = &home.children[0];
612 let omar_home_ids: Vec<&String> = omar_home.children.iter().map(|x| x.id()).collect();
613 assert_eq!(
614 omar_home_ids,
615 vec!["/home/omar/readme.md", "/home/omar/changelog.md"]
616 );
617 // count
618 assert_eq!(root.count(), 8);
619 // depth
620 assert_eq!(root.depth(), 4);
621 // Children
622 assert_eq!(root.children().len(), 2);
623 assert_eq!(root.iter().count(), 2);
624 // -- Query
625 assert_eq!(
626 tree.root()
627 .query(&"/home/omar/changelog.md".to_string())
628 .unwrap()
629 .id(),
630 "/home/omar/changelog.md"
631 );
632 assert!(tree.root().query(&"ommlar".to_string()).is_none());
633 // is leaf
634 assert_eq!(
635 tree.root()
636 .query(&"/home/omar".to_string())
637 .unwrap()
638 .is_leaf(),
639 false
640 );
641 assert_eq!(
642 tree.root()
643 .query(&"/home/omar/changelog.md".to_string())
644 .unwrap()
645 .is_leaf(),
646 true
647 );
648 // parent
649 assert!(tree.root().parent(&"/".to_string()).is_none());
650 assert_eq!(
651 tree.root()
652 .parent(&"/home/omar/changelog.md".to_string())
653 .unwrap()
654 .id(),
655 "/home/omar"
656 );
657 assert!(tree.root().parent(&"/homer".to_string()).is_none());
658 // siblings
659 assert_eq!(
660 tree.root()
661 .siblings(&"/home/omar/changelog.md".to_string())
662 .unwrap(),
663 vec!["/home/omar/readme.md"]
664 );
665 assert_eq!(
666 tree.root()
667 .siblings(&"/home/omar".to_string())
668 .unwrap()
669 .len(),
670 0
671 );
672 assert!(tree.root().siblings(&"/homer".to_string()).is_none());
673 }
674
675 #[test]
676 fn test_should_get_mutable_parent() {
677 let mut tree: Tree<&'static str, &'static str> = Tree::new(
678 Node::new("/", "/")
679 .with_child(
680 Node::new("/bin", "bin/")
681 .with_child(Node::new("/bin/ls", "ls"))
682 .with_child(Node::new("/bin/pwd", "pwd")),
683 )
684 .with_child(
685 Node::new("/home", "home/").with_child(
686 Node::new("/home/omar", "omar/")
687 .with_child(Node::new("/home/omar/readme.md", "readme.md"))
688 .with_child(Node::new("/home/omar/changelog.md", "changelog.md")),
689 ),
690 ),
691 );
692
693 let parent = tree
694 .root_mut()
695 .parent_mut(&"/home/omar/changelog.md")
696 .unwrap();
697
698 parent.set_value("new value");
699 assert_eq!(parent.value(), &"new value");
700 }
701
702 #[test]
703 fn test_tree_manipolation() {
704 let mut tree: Tree<String, &str> = Tree::new(
705 Node::new("/".to_string(), "/")
706 .with_child(
707 Node::new("/bin".to_string(), "bin/")
708 .with_child(Node::new("/bin/ls".to_string(), "ls"))
709 .with_child(Node::new("/bin/pwd".to_string(), "pwd")),
710 )
711 .with_child(
712 Node::new("/home".to_string(), "home/").with_child(
713 Node::new("/home/omar".to_string(), "omar/")
714 .with_child(Node::new("/home/omar/readme.md".to_string(), "readme.md"))
715 .with_child(Node::new(
716 "/home/omar/changelog.md".to_string(),
717 "changelog.md",
718 )),
719 ),
720 ),
721 );
722 // Mutable
723 let root: &mut Node<String, &str> = tree.root_mut();
724 assert_eq!(root.iter_mut().count(), 2);
725 // Push node
726 tree.root_mut()
727 .query_mut(&"/home/omar".to_string())
728 .unwrap()
729 .add_child(Node::new("/home/omar/Cargo.toml".to_string(), "Cargo.toml"));
730 assert_eq!(
731 tree.root()
732 .query(&"/home/omar/Cargo.toml".to_string())
733 .unwrap()
734 .id(),
735 "/home/omar/Cargo.toml"
736 );
737 // Remove
738 tree.root_mut()
739 .query_mut(&"/home/omar".to_string())
740 .unwrap()
741 .add_child(Node::new("/home/omar/Cargo.lock".to_string(), "Cargo.lock"));
742 assert_eq!(
743 tree.root()
744 .query(&"/home/omar/Cargo.lock".to_string())
745 .unwrap()
746 .id(),
747 "/home/omar/Cargo.lock"
748 );
749 tree.root_mut()
750 .query_mut(&"/home/omar".to_string())
751 .unwrap()
752 .remove_child(&String::from("/home/omar/Cargo.lock"));
753 assert!(tree
754 .root()
755 .query(&"/home/omar/Cargo.lock".to_string())
756 .is_none());
757 // Clear node
758 tree.root_mut()
759 .query_mut(&"/home/omar".to_string())
760 .unwrap()
761 .clear();
762 assert_eq!(
763 tree.root()
764 .query(&"/home/omar".to_string())
765 .unwrap()
766 .children
767 .len(),
768 0
769 );
770 // -- truncate
771 let mut tree: Tree<String, &str> = Tree::new(
772 Node::new("/".to_string(), "/")
773 .with_child(
774 Node::new("/bin".to_string(), "bin/")
775 .with_child(Node::new("/bin/ls".to_string(), "ls"))
776 .with_child(Node::new("/bin/pwd".to_string(), "pwd")),
777 )
778 .with_child(
779 Node::new("/home".to_string(), "home/").with_child(
780 Node::new("/home/omar".to_string(), "omar/")
781 .with_child(Node::new("/home/omar/readme.md".to_string(), "readme.md"))
782 .with_child(Node::new(
783 "/home/omar/changelog.md".to_string(),
784 "changelog.md",
785 )),
786 ),
787 ),
788 );
789 let root: &mut Node<String, &str> = &mut tree.root;
790 root.truncate(1);
791 assert_eq!(root.children.len(), 2);
792 assert_eq!(root.children[0].children.len(), 0);
793 assert_eq!(root.children[0].id(), "/bin");
794 assert_eq!(root.children[1].children.len(), 0);
795 assert_eq!(root.children[1].id(), "/home");
796 }
797
798 #[test]
799 fn test_sort() {
800 // Sort
801 let mut tree: Tree<&'static str, usize> = Tree::new(
802 Node::new("/", 0)
803 .with_child(Node::new("8", 8))
804 .with_child(Node::new("7", 7))
805 .with_child(Node::new("3", 3))
806 .with_child(Node::new("1", 1))
807 .with_child(Node::new("2", 2))
808 .with_child(Node::new("9", 9))
809 .with_child(Node::new("5", 5))
810 .with_child(Node::new("4", 4))
811 .with_child(Node::new("6", 6)),
812 );
813 tree.root_mut()
814 .sort(|a, b| a.value().partial_cmp(b.value()).unwrap());
815 let values: Vec<usize> = tree.root().iter().map(|x| *x.value()).collect();
816 assert_eq!(values, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
817 }
818
819 #[test]
820 fn test_with_children() {
821 // -- With children
822 let tree: Tree<String, &str> =
823 Tree::new(Node::new("a".to_string(), "a").with_children(vec![
824 Node::new("a1".to_string(), "a1"),
825 Node::new("a2".to_string(), "a2"),
826 ]));
827 assert!(tree.root().query(&"a".to_string()).is_some());
828 assert!(tree.root().query(&"a1".to_string()).is_some());
829 assert!(tree.root().query(&"a2".to_string()).is_some());
830 }
831
832 #[test]
833 fn test_routes() {
834 let tree: Tree<String, &str> = Tree::new(
835 Node::new("/".to_string(), "/")
836 .with_child(
837 Node::new("/bin".to_string(), "bin/")
838 .with_child(Node::new("/bin/ls".to_string(), "ls"))
839 .with_child(Node::new("/bin/pwd".to_string(), "pwd")),
840 )
841 .with_child(
842 Node::new("/home".to_string(), "home/").with_child(
843 Node::new("/home/omar".to_string(), "omar/")
844 .with_child(Node::new("/home/omar/readme.md".to_string(), "readme.md"))
845 .with_child(Node::new(
846 "/home/omar/changelog.md".to_string(),
847 "changelog.md",
848 )),
849 ),
850 ),
851 );
852 // -- node_by_route
853 assert_eq!(
854 tree.root().node_by_route(&[1, 0, 1]).unwrap().id(),
855 "/home/omar/changelog.md"
856 );
857 assert!(tree.root().node_by_route(&[1, 0, 3]).is_none());
858 // -- Route by node
859 assert_eq!(
860 tree.root()
861 .route_by_node(&"/home/omar/changelog.md".to_string())
862 .unwrap(),
863 vec![1, 0, 1]
864 );
865 assert!(tree
866 .root()
867 .route_by_node(&"ciccio-pasticcio".to_string())
868 .is_none());
869 }
870
871 #[test]
872 fn test_find() {
873 let tree: Tree<&'static str, usize> = Tree::new(
874 Node::new("/", 0)
875 .with_child(Node::new("a", 2))
876 .with_child(Node::new("b", 7))
877 .with_child(Node::new("c", 13))
878 .with_child(Node::new("d", 16))
879 .with_child(
880 Node::new("e", 75)
881 .with_child(Node::new("f", 68))
882 .with_child(Node::new("g", 12))
883 .with_child(Node::new("h", 9))
884 .with_child(Node::new("i", 4)),
885 ),
886 );
887 // Find all even values
888 let even_nodes = tree
889 .root()
890 .find(&|x: &Node<&'static str, usize>| x.value() % 2 == 0);
891 assert_eq!(even_nodes.len(), 6);
892 let values: Vec<usize> = even_nodes.iter().map(|x| *x.value()).collect();
893 assert_eq!(values, vec![0, 2, 16, 68, 12, 4]);
894 }
895
896 #[test]
897 fn test_macro() {
898 // -- Empty node
899 let node: Node<&'static str, usize> = node!("root", 0);
900 assert_eq!(node.id(), &"root");
901 assert_eq!(*node.value(), 0);
902 assert_eq!(node.children().len(), 0);
903 // Node with child
904 let node: Node<&'static str, usize> = node!("root", 0, node!("a", 1));
905 assert_eq!(node.id(), &"root");
906 assert_eq!(*node.value(), 0);
907 assert_eq!(node.children().len(), 1);
908 assert_eq!(*node.query(&"a").unwrap().value(), 1);
909 let node: Node<&'static str, usize> = node!("root", 0, node!("a", 1), node!("b", 0));
910 assert_eq!(node.children().len(), 2);
911 let tree: Tree<&'static str, usize> = Tree::new(node!(
912 "root",
913 0,
914 node!("a", 1, node!("a1", 3), node!("a2", 4)),
915 node!("b", 0)
916 ));
917 assert_eq!(tree.root().count(), 5);
918 }
919
920 #[test]
921 fn test_should_update_node_value() {
922 let mut node = Node::new("root", 0);
923
924 assert_eq!(node.value(), &0);
925 node.set_value(1);
926
927 assert_eq!(node.value(), &1);
928 }
929
930 #[test]
931 fn test_add_child_should_not_duplicate_children_with_same_id() {
932 let mut node = Node::new("root", 0);
933
934 node.add_child(Node::new("child", 1));
935 node.add_child(Node::new("child", 2));
936
937 assert_eq!(node.children().len(), 1);
938 assert_eq!(node.children()[0].value(), &2);
939 }
940}