tree_ds/tree/
mod.rs

1use crate::lib::*;
2
3#[cfg(feature = "async")]
4pub use async_tree::Tree;
5#[cfg(not(feature = "async"))]
6pub use sync_tree::Tree;
7
8#[cfg(feature = "async")]
9mod async_tree;
10
11#[cfg(not(feature = "async"))]
12mod sync_tree;
13
14/// The strategy to use when removing a node from the tree.
15///
16/// This enum represents the strategy to use when removing a node from the tree. The `RetainChildren`
17/// strategy retains the children of the node when the node is removed. The `RemoveNodeAndChildren`
18/// strategy removes the node and its children when the node is removed.
19#[derive(Clone, Debug, Copy)]
20pub enum NodeRemovalStrategy {
21    /// Retain the children of the node. This means that the children of the node are attached to the
22    /// parent of the node when the node is removed. So the children of the node become children of the
23    /// parent of the node.
24    RetainChildren,
25    /// Remove the node and all subsequent children. This means that the node and its children are
26    /// removed from the tree when the node is removed. All the subsequent grand children of the node are
27    /// removed from the tree.
28    RemoveNodeAndChildren,
29}
30
31/// The strategy to use when traversing the tree.
32///
33/// This enum represents the strategy to use when traversing the tree.
34#[allow(clippy::enum_variant_names)]
35#[derive(Clone, Debug, Copy)]
36pub enum TraversalStrategy {
37    /// Traverse the tree in pre-order. This means that the root node is visited first, then the left
38    /// child, and then the right child.
39    PreOrder,
40    /// Traverse the tree in post-order. This means that the left child is visited first, then the right
41    /// child, and then the root node.
42    PostOrder,
43    /// Traverse the tree in in-order. This means that the left child is visited first, then the root node,
44    /// and then the right child.
45    InOrder,
46}
47
48/// A subtree of a tree.
49///
50/// This struct represents a subtree of a tree. A subtree is a tree that is a part of a larger tree.
51pub type SubTree<Q, T> = Tree<Q, T>;
52
53#[cfg(test)]
54mod tests {
55    use crate::error::Error::{InvalidOperation, NodeNotFound, RootNodeAlreadyPresent};
56    use crate::lib::*;
57    #[allow(deprecated)]
58    #[cfg(feature = "no_std")]
59    use core::hash::SipHasher as DefaultHasher;
60    #[cfg(not(feature = "no_std"))]
61    use std::hash::DefaultHasher;
62
63    use super::*;
64    use crate::prelude::{Node, Result};
65
66    #[test]
67    fn test_tree_new() {
68        let tree = Tree::<u32, u32>::new(Some("Sample Tree"));
69        assert_eq!(tree.get_nodes().len(), 0);
70    }
71
72    #[test]
73    fn test_tree_add_node() -> Result<()> {
74        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
75        let node_id = tree.add_node(Node::new(1, Some(2)), None)?;
76        assert_eq!(tree.get_nodes().len(), 1);
77        assert_eq!(node_id, 1);
78        let node_id_2 = tree.add_node(Node::new(2, Some(3)), Some(&1))?;
79        assert_eq!(tree.get_nodes().len(), 2);
80        assert_eq!(node_id_2, 2);
81        let node_2 = tree.get_node_by_id(&2).unwrap();
82        assert_eq!(node_2.get_parent_id()?.unwrap(), 1);
83        Ok(())
84    }
85
86    #[test]
87    fn test_tree_add_more_than_one_root_node() {
88        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
89        let result = tree.add_node(Node::new(1, Some(2)), None);
90        assert!(result.is_ok());
91        let node_id = result.unwrap();
92        assert_eq!(tree.get_nodes().len(), 1);
93        assert_eq!(node_id, 1);
94        let result = tree.add_node(Node::new(2, Some(3)), None);
95        assert!(result.is_err());
96        assert_eq!(result.unwrap_err(), RootNodeAlreadyPresent);
97    }
98
99    #[test]
100    fn test_tree_get_node() {
101        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
102        let node = Node::new(1, Some(2));
103        tree.add_node(node.clone(), None).unwrap();
104        assert_eq!(tree.get_node_by_id(&1), Some(node));
105        assert_eq!(tree.get_node_by_id(&2), None);
106    }
107
108    #[test]
109    fn test_tree_get_no_existent_node() {
110        let tree = Tree::<u32, u32>::new(Some("Sample Tree"));
111        assert_eq!(tree.get_node_by_id(&1), None);
112    }
113
114    #[test]
115    fn test_tree_get_nodes() {
116        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
117        let node1 = Node::new(1, Some(2));
118        let node2 = Node::new(2, Some(4));
119        let node3 = Node::new(3, Some(7));
120        let node1_id = tree.add_node(node1.clone(), None).unwrap();
121        let node2_id = tree.add_node(node2.clone(), Some(&node1_id)).unwrap();
122        let _ = tree.add_node(node3.clone(), Some(&node2_id)).unwrap();
123        assert_eq!(tree.get_nodes().len(), 3);
124    }
125
126    #[test]
127    fn test_tree_get_root_node() {
128        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
129        let node = Node::new(1, Some(2));
130        tree.add_node(node.clone(), None).unwrap();
131        assert_eq!(tree.get_root_node(), Some(node));
132    }
133
134    #[test]
135    fn test_tree_get_node_height() {
136        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
137        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
138        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
139        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
140        assert_eq!(tree.get_node_height(&node_1).unwrap(), 2);
141        assert_eq!(tree.get_node_height(&node_2).unwrap(), 1);
142        assert_eq!(tree.get_node_height(&node_3).unwrap(), 0);
143    }
144
145    #[test]
146    fn test_tree_get_node_height_no_existent_node() {
147        let tree = Tree::<u32, u32>::new(Some("Sample Tree"));
148        let result = tree.get_node_height(&1);
149        assert!(result.is_err());
150        assert_eq!(result.unwrap_err(), NodeNotFound("1".to_string()));
151    }
152
153    #[test]
154    fn test_tree_get_node_depth() {
155        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
156        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
157        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
158        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
159        assert_eq!(tree.get_node_depth(&node_3).unwrap(), 2);
160        assert_eq!(tree.get_node_depth(&node_2).unwrap(), 1);
161        assert_eq!(tree.get_node_depth(&node_1).unwrap(), 0);
162    }
163
164    #[test]
165    fn test_tree_get_ancestor_ids() {
166        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
167        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
168        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
169        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
170        let node_4 = tree.add_node(Node::new(4, Some(5)), Some(&node_2)).unwrap();
171        assert_eq!(tree.get_ancestor_ids(&node_4).unwrap(), vec![2, 1]);
172        assert_eq!(tree.get_ancestor_ids(&node_3).unwrap(), vec![2, 1]);
173        assert_eq!(tree.get_ancestor_ids(&node_2).unwrap(), vec![1]);
174        assert_eq!(tree.get_ancestor_ids(&node_1).unwrap(), Vec::<u32>::new());
175    }
176
177    #[test]
178    fn test_tree_get_node_ancestor_ids_no_existent_node() {
179        let tree = Tree::<u32, u32>::new(Some("Sample Tree"));
180        let result = tree.get_ancestor_ids(&1);
181        assert!(result.is_err());
182        assert_eq!(result.unwrap_err(), NodeNotFound("1".to_string()));
183    }
184
185    #[test]
186    fn test_tree_get_node_depth_no_existent_node() {
187        let tree = Tree::<u32, u32>::new(Some("Sample Tree"));
188        let result = tree.get_node_depth(&1);
189        assert!(result.is_err());
190        assert_eq!(result.unwrap_err(), NodeNotFound("1".to_string()));
191    }
192
193    #[test]
194    fn test_tree_get_height() {
195        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
196        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
197        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
198        tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
199        assert_eq!(tree.get_height().unwrap(), 2);
200    }
201
202    #[test]
203    fn test_tree_get_height_no_root_node() {
204        let tree = Tree::<u32, u32>::new(Some("Sample Tree"));
205        let result = tree.get_height();
206        assert!(result.is_err());
207        assert_eq!(
208            result.unwrap_err(),
209            InvalidOperation("Tree has no root node".to_string())
210        );
211    }
212
213    #[test]
214    fn test_tree_get_node_degree() {
215        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
216        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
217        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
218        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_1)).unwrap();
219        assert_eq!(tree.get_node_degree(&node_1).unwrap(), 2);
220        assert_eq!(tree.get_node_degree(&node_2).unwrap(), 0);
221        assert_eq!(tree.get_node_degree(&node_3).unwrap(), 0);
222    }
223
224    #[test]
225    fn test_tree_get_node_degree_no_existent_node() {
226        let tree = Tree::<u32, u32>::new(Some("Sample Tree"));
227        let result = tree.get_node_degree(&1);
228        assert!(result.is_err());
229        assert_eq!(result.unwrap_err(), NodeNotFound("1".to_string()));
230    }
231
232    #[test]
233    fn test_tree_remove_node() -> Result<()> {
234        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
235        let node = Node::new(1, Some(2));
236        tree.add_node(node.clone(), None)?;
237        let node_2 = Node::new(2, Some(3));
238        tree.add_node(node_2.clone(), Some(&1))?;
239        let node_3 = Node::new(3, Some(6));
240        tree.add_node(node_3.clone(), Some(&2))?;
241        tree.remove_node(&2, NodeRemovalStrategy::RetainChildren)?;
242        assert_eq!(tree.get_nodes().len(), 2);
243        let node_4 = Node::new(4, Some(5));
244        let node_5 = Node::new(5, Some(12));
245        tree.add_node(node_4.clone(), Some(&3))?;
246        tree.add_node(node_5.clone(), Some(&3))?;
247        tree.remove_node(&3, NodeRemovalStrategy::RemoveNodeAndChildren)?;
248        assert_eq!(tree.get_nodes().len(), 1);
249        Ok(())
250    }
251
252    #[test]
253    fn test_tree_remove_node_no_existent_node() {
254        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
255        let result = tree.remove_node(&1, NodeRemovalStrategy::RetainChildren);
256        assert!(result.is_err());
257        assert_eq!(result.unwrap_err(), NodeNotFound("1".to_string()));
258    }
259
260    #[test]
261    fn test_tree_remove_node_no_root_node() {
262        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
263        tree.add_node(Node::new(1, Some(2)), None).unwrap();
264        let result = tree.remove_node(&1, NodeRemovalStrategy::RetainChildren);
265        assert!(result.is_err());
266        assert_eq!(
267            result.unwrap_err(),
268            InvalidOperation("Cannot remove root node with RetainChildren strategy".to_string())
269        );
270    }
271
272    #[test]
273    fn test_tree_get_subsection() {
274        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
275        let node = Node::new(1, Some(2));
276        tree.add_node(node.clone(), None).unwrap();
277        let node_2 = Node::new(2, Some(3));
278        tree.add_node(node_2.clone(), Some(&1)).unwrap();
279        let node_3 = Node::new(3, Some(6));
280        tree.add_node(node_3.clone(), Some(&2)).unwrap();
281        let node_4 = Node::new(4, Some(5));
282        tree.add_node(node_4.clone(), Some(&2)).unwrap();
283        let node_5 = Node::new(5, Some(6));
284        tree.add_node(node_5.clone(), Some(&3)).unwrap();
285        let subsection = tree.get_subtree(&2, None).unwrap();
286        assert_eq!(subsection.get_name(), Some("2"));
287        assert_eq!(subsection.get_nodes().len(), 4);
288        let subsection = tree.get_subtree(&2, Some(0)).unwrap();
289        assert_eq!(subsection.get_nodes().len(), 1);
290        let subsection = tree.get_subtree(&2, Some(1)).unwrap();
291        assert_eq!(subsection.get_nodes().len(), 3);
292    }
293
294    #[test]
295    fn test_tree_get_subsection_no_existent_node() {
296        let tree = Tree::<u32, u32>::new(Some("Sample Tree"));
297        let result = tree.get_subtree(&1, None);
298        assert!(result.is_err());
299        assert_eq!(result.unwrap_err(), NodeNotFound("1".to_string()));
300    }
301
302    #[test]
303    fn get_siblings() {
304        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
305        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
306        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
307        tree.add_node(Node::new(3, Some(6)), Some(&node_1)).unwrap();
308        tree.add_node(Node::new(4, Some(7)), Some(&node_1)).unwrap();
309        let siblings = tree.get_sibling_ids(&node_2, false).unwrap();
310        assert_eq!(siblings.len(), 2);
311        let siblings = tree.get_sibling_ids(&node_2, true).unwrap();
312        assert_eq!(siblings.len(), 3);
313    }
314
315    #[test]
316    fn test_tree_get_siblings_no_existent_node() {
317        let tree = Tree::<u32, u32>::new(Some("Sample Tree"));
318        let result = tree.get_sibling_ids(&1, false);
319        assert!(result.is_err());
320        assert_eq!(result.unwrap_err(), NodeNotFound("1".to_string()));
321    }
322
323    #[test]
324    fn test_tree_add_subsection() {
325        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
326        let node_id = tree.add_node(Node::new(1, Some(2)), None).unwrap();
327        let mut subtree = SubTree::<u32, u32>::new(Some("Sample Tree"));
328        let node_2 = subtree.add_node(Node::new(2, Some(3)), None).unwrap();
329        subtree
330            .add_node(Node::new(3, Some(6)), Some(&node_2))
331            .unwrap();
332        tree.add_subtree(&node_id, subtree).unwrap();
333        assert_eq!(tree.get_nodes().len(), 3);
334    }
335
336    #[test]
337    fn test_tree_add_subsection_no_attaching_node() {
338        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
339        let mut subtree = SubTree::<u32, u32>::new(Some("Sample Tree"));
340        let node_2 = subtree.add_node(Node::new(2, Some(3)), None).unwrap();
341        subtree
342            .add_node(Node::new(3, Some(6)), Some(&node_2))
343            .unwrap();
344        let result = tree.add_subtree(&1, subtree);
345        assert!(result.is_err());
346        assert_eq!(result.unwrap_err(), NodeNotFound("1".to_string()));
347    }
348
349    #[test]
350    fn test_tree_add_subsection_with_no_root_node() -> Result<()> {
351        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
352        let node_id = tree.add_node(Node::new(1, Some(2)), None)?;
353        let mut subtree = SubTree::<u32, u32>::new(Some("Sample Tree"));
354        let node_2 = Node::new(2, Some(3));
355        let result = subtree.add_node(Node::new(3, Some(3)), Some(&node_2.get_node_id()?));
356        assert!(result.is_err());
357        assert_eq!(result.unwrap_err(), NodeNotFound("2".to_string()));
358        let result = tree.add_subtree(&node_id, subtree);
359        assert!(result.is_err());
360        assert_eq!(
361            result.unwrap_err(),
362            InvalidOperation("Subtree has no root node.".to_string())
363        );
364        Ok(())
365    }
366
367    #[test]
368    fn test_tree_display() {
369        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
370        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
371        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
372        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
373        tree.add_node(Node::new(4, Some(5)), Some(&node_2)).unwrap();
374        tree.add_node(Node::new(5, Some(6)), Some(&node_3)).unwrap();
375        #[cfg(feature = "print_node_id")]
376		let expected_str = "Sample Tree\n***********\n1: 2\n└── 2: 3\n    ├── 3: 6\n    │   └── 5: 6\n    └── 4: 5\n";
377        #[cfg(not(feature = "print_node_id"))]
378        let expected_str =
379            "Sample Tree\n***********\n2\n└── 3\n    ├── 6\n    │   └── 6\n    └── 5\n";
380
381        assert_eq!(tree.to_string(), expected_str);
382    }
383
384    #[test]
385    fn compare_tree() {
386        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
387        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
388        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
389        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
390        tree.add_node(Node::new(4, Some(5)), Some(&node_2)).unwrap();
391        tree.add_node(Node::new(5, Some(6)), Some(&node_3)).unwrap();
392        let mut tree_2 = Tree::<u32, u32>::new(Some("Sample Tree"));
393        let node_1 = tree_2.add_node(Node::new(1, Some(2)), None).unwrap();
394        let node_2 = tree_2
395            .add_node(Node::new(2, Some(3)), Some(&node_1))
396            .unwrap();
397        let node_3 = tree_2
398            .add_node(Node::new(3, Some(6)), Some(&node_2))
399            .unwrap();
400        tree_2
401            .add_node(Node::new(4, Some(5)), Some(&node_2))
402            .unwrap();
403        tree_2
404            .add_node(Node::new(5, Some(6)), Some(&node_3))
405            .unwrap();
406        assert_eq!(tree, tree_2);
407        let tree_3 = Tree::<u32, u32>::new(Some("Sample Tree"));
408        assert_ne!(tree, tree_3);
409    }
410
411    #[test]
412    fn test_tree_traverse() {
413        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
414        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
415        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
416        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_1)).unwrap();
417        let node_4 = tree.add_node(Node::new(4, Some(5)), Some(&node_2)).unwrap();
418        let node_5 = tree.add_node(Node::new(5, Some(6)), Some(&node_2)).unwrap();
419        let node_6 = tree.add_node(Node::new(6, Some(7)), Some(&node_3)).unwrap();
420        let preorder_nodes = tree.traverse(&node_1, TraversalStrategy::PreOrder).unwrap();
421        let expected_preorder = vec![node_1, node_2, node_4, node_5, node_3, node_6];
422        assert_eq!(preorder_nodes, expected_preorder);
423
424        let in_order_nodes = tree.traverse(&node_1, TraversalStrategy::InOrder).unwrap();
425        let expected_in_order = vec![node_4, node_2, node_5, node_1, node_3, node_6];
426        assert_eq!(in_order_nodes, expected_in_order);
427
428        let post_order_nodes = tree
429            .traverse(&node_1, TraversalStrategy::PostOrder)
430            .unwrap();
431        let expected_post_order = vec![node_4, node_5, node_2, node_6, node_3, node_1];
432        assert_eq!(post_order_nodes, expected_post_order);
433    }
434
435    #[allow(deprecated)] // This is solely for testing hashing in no_std.
436    #[test]
437    fn test_hashing() {
438        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
439        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
440        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
441        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
442        tree.add_node(Node::new(4, Some(5)), Some(&node_2)).unwrap();
443        tree.add_node(Node::new(5, Some(6)), Some(&node_3)).unwrap();
444        let mut tree_2 = Tree::<u32, u32>::new(Some("Sample Tree"));
445        let node_1 = tree_2.add_node(Node::new(1, Some(2)), None).unwrap();
446        let node_2 = tree_2
447            .add_node(Node::new(2, Some(3)), Some(&node_1))
448            .unwrap();
449        let node_3 = tree_2
450            .add_node(Node::new(3, Some(6)), Some(&node_2))
451            .unwrap();
452        tree_2
453            .add_node(Node::new(4, Some(5)), Some(&node_2))
454            .unwrap();
455        tree_2
456            .add_node(Node::new(5, Some(6)), Some(&node_3))
457            .unwrap();
458        assert_eq!(tree, tree_2);
459        let mut hasher = DefaultHasher::new();
460        tree.hash(&mut hasher);
461        let tree_hash = hasher.finish();
462        let mut hasher = DefaultHasher::new();
463        tree_2.hash(&mut hasher);
464        let tree_2_hash = hasher.finish();
465        assert_eq!(tree_hash, tree_2_hash);
466    }
467
468    #[test]
469    fn test_sort_children_by_height() -> Result<()> {
470        let mut tree = Tree::<u32, u32>::new(Some("Sample Tree"));
471        let node_1 = tree.add_node(Node::new(1, Some(1)), None)?;
472        let _node_2 = tree.add_node(Node::new(2, Some(2)), Some(&node_1))?;
473        let node_3 = tree.add_node(Node::new(3, Some(3)), Some(&node_1))?;
474        let node_4 = tree.add_node(Node::new(4, Some(4)), Some(&node_3))?;
475        let _node_5 = tree.add_node(Node::new(5, Some(5)), Some(&node_4))?;
476
477        let root = tree.get_node_by_id(&node_1).unwrap();
478        root.sort_children(|a, b| {
479            let a_height = tree.get_node_height(a).unwrap();
480            let b_height = tree.get_node_height(b).unwrap();
481            a_height.cmp(&b_height).reverse()
482        })?;
483
484        assert_eq!(
485            tree.get_node_by_id(&node_1).unwrap().get_children_ids()?,
486            vec![3, 2]
487        );
488        Ok(())
489    }
490}
491
492#[cfg(all(test, feature = "serde"))]
493mod serde_tests {
494    use crate::prelude::Node;
495
496    use super::*;
497
498    #[test]
499    fn test_tree_serialize_and_deserialize() {
500        let mut tree = Tree::new(None);
501        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
502        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
503        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
504        tree.add_node(Node::new(4, Some(5)), Some(&node_2)).unwrap();
505        tree.add_node(Node::new(5, Some(6)), Some(&node_3)).unwrap();
506        let serialized = serde_json::to_string(&tree).unwrap();
507        let expected = r#"{"nodes":[{"node_id":1,"value":2,"parent":null,"children":[2]},{"node_id":2,"value":3,"parent":1,"children":[3,4]},{"node_id":3,"value":6,"parent":2,"children":[5]},{"node_id":4,"value":5,"parent":2,"children":[]},{"node_id":5,"value":6,"parent":3,"children":[]}]}"#;
508        let deserialized: Tree<u32, u32> = serde_json::from_str(&serialized).unwrap();
509        let expected_tree: Tree<u32, u32> = serde_json::from_str(expected).unwrap();
510        assert_eq!(deserialized, expected_tree);
511    }
512
513    #[test]
514    #[cfg_attr(not(feature = "compact_serde"), ignore)]
515    fn test_tree_compact_serialize() {
516        let mut tree = Tree::new(None);
517        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
518        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
519        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
520        tree.add_node(Node::new(4, Some(5)), Some(&node_2)).unwrap();
521        tree.add_node(Node::new(5, Some(6)), Some(&node_3)).unwrap();
522        let serialized = serde_json::to_string(&tree).unwrap();
523        let expected = r#"{"nodes":[{"node_id":1,"value":2,"parent":null},{"node_id":2,"value":3,"parent":1},{"node_id":3,"value":6,"parent":2},{"node_id":4,"value":5,"parent":2},{"node_id":5,"value":6,"parent":3}]}"#;
524        assert_eq!(serialized, expected);
525    }
526
527    #[test]
528    #[cfg_attr(not(feature = "compact_serde"), ignore)]
529    fn test_tree_compact_deserialize() {
530        let tree_str = r#"{"nodes":[{"node_id":1,"value":2,"parent":null},{"node_id":2,"value":3,"parent":1},{"node_id":3,"value":6,"parent":2},{"node_id":4,"value":5,"parent":2},{"node_id":5,"value":6,"parent":3}]}"#;
531        let deserialized: Tree<u32, u32> = serde_json::from_str(tree_str).unwrap();
532        let mut tree = Tree::new(None);
533        let node_1 = tree.add_node(Node::new(1, Some(2)), None).unwrap();
534        let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1)).unwrap();
535        let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_2)).unwrap();
536        tree.add_node(Node::new(4, Some(5)), Some(&node_2)).unwrap();
537        tree.add_node(Node::new(5, Some(6)), Some(&node_3)).unwrap();
538        assert_eq!(deserialized, tree);
539    }
540
541    #[cfg(feature = "auto_id")]
542    #[test]
543    fn test_tree_serialize_and_deserialize_with_auto_id_ensuring_uniqueness() {
544        let mut tree = Tree::<crate::prelude::AutomatedId, i32>::new(Some("Sample Tree"));
545        let root = tree
546            .add_node(Node::new_with_auto_id(Some(2)), None)
547            .unwrap();
548        let child_1 = tree
549            .add_node(Node::new_with_auto_id(Some(3)), Some(&root))
550            .unwrap();
551        let child_2 = tree
552            .add_node(Node::new_with_auto_id(Some(4)), Some(&child_1))
553            .unwrap();
554        let child_3 = tree
555            .add_node(Node::new_with_auto_id(Some(5)), Some(&child_2))
556            .unwrap();
557        let serialized_tree = serde_json::to_string(&tree).unwrap();
558        let mut deserialized_tree: Tree<crate::prelude::AutomatedId, i32> =
559            serde_json::from_str(&serialized_tree).unwrap();
560        deserialized_tree
561            .add_node(Node::new_with_auto_id(Some(6)), Some(&child_3))
562            .unwrap();
563        let mut node_ids = deserialized_tree
564            .get_nodes()
565            .iter()
566            .map(|node| node.get_node_id().unwrap())
567            .collect::<Vec<_>>();
568        node_ids.sort();
569        node_ids.dedup();
570        assert_eq!(node_ids.len(), deserialized_tree.get_nodes().len());
571    }
572
573    #[cfg(feature = "auto_id")]
574    #[test]
575    #[cfg_attr(feature = "no_std", ignore)]
576    fn test_tree_deserialize_from_disk_with_auto_id_ensuring_uniqueness() {
577        let tree_str = serde_json::json!({"name":"Sample Tree","nodes":[{"node_id":3,"value":2,"children":[4],"parent":null},{"node_id":4,"value":3,"children":[5],"parent":3},{"node_id":5,"value":4,"children":[6],"parent":4},{"node_id":6,"value":5,"children":[],"parent":5}]});
578        let mut deserialized_tree =
579            serde_json::from_value::<Tree<crate::prelude::AutomatedId, i32>>(tree_str).unwrap();
580        deserialized_tree
581            .add_node(Node::new_with_auto_id(Some(6)), Some(&6))
582            .unwrap();
583        let mut node_ids = deserialized_tree
584            .get_nodes()
585            .iter()
586            .map(|node| node.get_node_id().unwrap())
587            .collect::<Vec<_>>();
588        node_ids.sort();
589        node_ids.dedup();
590        assert_eq!(node_ids.len(), deserialized_tree.get_nodes().len());
591    }
592}
tree_ds/tree/mod.rs

tree_ds/tree/
mod.rs
