darkfi_sdk/dark_tree.rs
1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2025 Dyne.org foundation
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Affero General Public License as
7 * published by the Free Software Foundation, either version 3 of the
8 * License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU Affero General Public License for more details.
14 *
15 * You should have received a copy of the GNU Affero General Public License
16 * along with this program. If not, see <https://www.gnu.org/licenses/>.
17 */
18
19use std::{clone::Clone, collections::VecDeque, iter::FusedIterator, mem};
20
21#[cfg(feature = "async")]
22use darkfi_serial::async_trait;
23use darkfi_serial::{SerialDecodable, SerialEncodable};
24
25use crate::error::{DarkTreeError, DarkTreeResult};
26
27/// Struct representing the information hold by a [`DarkTreeLeaf`].
28///
29/// This includes its data, along with positional
30/// indexes information, based on tree's traversal order.
31/// These indexes are only here to enable referencing
32/// connected nodes, and are *not* used as pointers by the
33/// tree. Creator must ensure they are properly setup.
34#[derive(Clone, Debug, Eq, PartialEq, SerialEncodable, SerialDecodable)]
35pub struct DarkLeaf<T>
36where
37 T: Clone + Send + Sync,
38{
39 /// Data holded by this leaf
40 pub data: T,
41 /// Index showcasing this leaf's parent tree, when all
42 /// leafs are in order. None indicates that this leaf
43 /// has no parent.
44 pub parent_index: Option<usize>,
45 /// Vector of indexes showcasing this leaf's children
46 /// positions, when all leafs are in order. If vector
47 /// is empty, it indicates that this leaf has no children.
48 pub children_indexes: Vec<usize>,
49}
50
51/// This struct represents a Leaf of a [`DarkTree`],
52/// holding this tree node data, along with its positional
53/// index, based on tree's traversal order.
54#[derive(Clone, Debug, PartialEq)]
55pub struct DarkTreeLeaf<T>
56where
57 T: Clone + Send + Sync,
58{
59 /// Index showcasing this leaf's position, when all
60 /// leafs are in order.
61 index: usize,
62 /// Leaf's data, along with its parent and children
63 /// indexes information.
64 info: DarkLeaf<T>,
65}
66
67impl<T: Clone + Send + Sync> DarkTreeLeaf<T> {
68 /// Every [`DarkTreeLeaf`] is initiated using default indexes.
69 fn new(data: T) -> DarkTreeLeaf<T> {
70 Self { index: 0, info: DarkLeaf { data, parent_index: None, children_indexes: vec![] } }
71 }
72
73 /// Set [`DarkTreeLeaf`]'s index
74 fn set_index(&mut self, index: usize) {
75 self.index = index;
76 }
77
78 /// Set [`DarkTreeLeaf`]'s parent index
79 fn set_parent_index(&mut self, parent_index: Option<usize>) {
80 self.info.parent_index = parent_index;
81 }
82
83 /// Set [`DarkTreeLeaf`]'s children index
84 fn set_children_indexes(&mut self, children_indexes: Vec<usize>) {
85 self.info.children_indexes = children_indexes;
86 }
87}
88
89/// This struct represents a DFS post-order traversal Tree.
90///
91/// When we iterate through the tree, we first process tree
92/// node's children, and then the node itself, recursively.
93/// Based on this, initial tree node (leaf), known as the root,
94/// will always show up at the end of iteration. It is advised
95/// to always execute .build() after finishing setting up the
96/// Tree, to properly index it and check its integrity.
97#[derive(Clone, Debug, PartialEq)]
98pub struct DarkTree<T: Clone + Send + Sync> {
99 /// This tree's leaf information, along with its data
100 leaf: DarkTreeLeaf<T>,
101 /// Vector containing all tree's branches(children tree)
102 children: Vec<DarkTree<T>>,
103 /// Min capacity of the tree, including all children nodes
104 /// recursively from the root. Since root is always present,
105 /// min capacity must always be >= 1. This is enforced by
106 /// the root, so children nodes don't have to set it up.
107 /// If children nodes children(recursively) make us not exceed
108 /// that min capacity, we will be able to catch it using
109 /// .check_min_capacity() or .integrity_check().
110 min_capacity: usize,
111 /// Optional max capacity of the tree, including all children
112 /// nodes recursively from the root. None indicates no
113 /// capacity restrictions. This is enforced by the root,
114 /// so children nodes don't have to set it up. If children
115 /// nodes children(recursively) make us exceed that capacity,
116 /// we will be able to catch it using .check_max_capacity() or
117 /// .integrity_check().
118 max_capacity: Option<usize>,
119}
120
121impl<T: Clone + Send + Sync> DarkTree<T> {
122 /// Initialize a [`DarkTree`], using provided data to
123 /// generate its root.
124 pub fn new(
125 data: T,
126 children: Vec<DarkTree<T>>,
127 min_capacity: Option<usize>,
128 max_capacity: Option<usize>,
129 ) -> DarkTree<T> {
130 // Setup min capacity
131 let min_capacity = if let Some(min_capacity) = min_capacity {
132 if min_capacity == 0 {
133 1
134 } else {
135 min_capacity
136 }
137 } else {
138 1
139 };
140 let leaf = DarkTreeLeaf::new(data);
141 Self { leaf, children, min_capacity, max_capacity }
142 }
143
144 /// Build the [`DarkTree`] indexes and perform an
145 /// integrity check on them. This should be used
146 /// after we have appended all child nodes, so we
147 /// don't have to call .index() and .integrity_check()
148 /// manually.
149 pub fn build(&mut self) -> DarkTreeResult<()> {
150 self.index();
151 self.integrity_check()
152 }
153
154 /// Build the [`DarkTree`] using .build() and
155 /// then produce a flattened vector containing
156 /// all the leafs in DFS post-order traversal order.
157 pub fn build_vec(&mut self) -> DarkTreeResult<Vec<DarkLeaf<T>>> {
158 self.build()?;
159 Ok(self.iter().cloned().map(|x| x.info).collect())
160 }
161
162 /// Return the count of all [`DarkTree`] leafs.
163 fn len(&self) -> usize {
164 self.iter().count()
165 }
166
167 /// Check if configured min capacity have not been exceeded.
168 fn check_min_capacity(&self) -> DarkTreeResult<()> {
169 if self.len() < self.min_capacity {
170 return Err(DarkTreeError::MinCapacityNotExceeded)
171 }
172
173 Ok(())
174 }
175
176 /// Check if configured max capacity have been exceeded.
177 fn check_max_capacity(&self) -> DarkTreeResult<()> {
178 if let Some(max_capacity) = self.max_capacity {
179 if self.len() > max_capacity {
180 return Err(DarkTreeError::MaxCapacityExceeded)
181 }
182 }
183
184 Ok(())
185 }
186
187 /// Append a new child node to the [`DarkTree`],
188 /// if max capacity has not been exceeded. This call
189 /// doesn't update the indexes, so either .index()
190 /// or .build() must be called after it.
191 pub fn append(&mut self, child: DarkTree<T>) -> DarkTreeResult<()> {
192 // Check current max capacity
193 if let Some(max_capacity) = self.max_capacity {
194 if self.len() + 1 > max_capacity {
195 return Err(DarkTreeError::MaxCapacityExceeded)
196 }
197 }
198
199 // Append the new child
200 self.children.push(child);
201
202 Ok(())
203 }
204
205 /// Set [`DarkTree`]'s leaf parent and children indexes,
206 /// and trigger the setup of its children indexes.
207 fn set_parent_children_indexes(&mut self, parent_index: Option<usize>) {
208 // Set our leafs parent index
209 self.leaf.set_parent_index(parent_index);
210
211 // Now recursively, we setup nodes children indexes and keep
212 // their index in our own children index list
213 let mut children_indexes = vec![];
214 for child in &mut self.children {
215 child.set_parent_children_indexes(Some(self.leaf.index));
216 children_indexes.push(child.leaf.index);
217 }
218
219 // Set our leafs children indexes
220 self.leaf.set_children_indexes(children_indexes);
221 }
222
223 /// Setup [`DarkTree`]'s leafs indexes, based on DFS post-order
224 /// traversal order. This call assumes it was triggered for the
225 /// root of the tree, which has no parent index.
226 fn index(&mut self) {
227 // First we setup each leafs index
228 for (index, leaf) in self.iter_mut().enumerate() {
229 leaf.set_index(index);
230 }
231
232 // Now we trigger recursion to setup each nodes rest indexes
233 self.set_parent_children_indexes(None);
234 }
235
236 /// Verify [`DarkTree`]'s leaf parent and children indexes validity,
237 /// and trigger the check of its children indexes.
238 fn check_parent_children_indexes(&self, parent_index: Option<usize>) -> DarkTreeResult<()> {
239 // Check our leafs parent index
240 if self.leaf.info.parent_index != parent_index {
241 return Err(DarkTreeError::InvalidLeafParentIndex(self.leaf.index))
242 }
243
244 // Now recursively, we check nodes children indexes and keep
245 // their index in our own children index list
246 let mut children_indexes = vec![];
247 for child in &self.children {
248 child.check_parent_children_indexes(Some(self.leaf.index))?;
249 children_indexes.push(child.leaf.index);
250 }
251
252 // Check our leafs children indexes
253 if self.leaf.info.children_indexes != children_indexes {
254 return Err(DarkTreeError::InvalidLeafChildrenIndexes(self.leaf.index))
255 }
256
257 Ok(())
258 }
259
260 /// Verify current [`DarkTree`]'s leafs indexes validity,
261 /// based on DFS post-order traversal order. Additionally,
262 /// check that min and max capacities have been properly
263 /// configured, min capacity has been exceeded and max
264 /// capacity has not. This call assumes it was triggered
265 /// for the root of the tree, which has no parent index.
266 fn integrity_check(&self) -> DarkTreeResult<()> {
267 // Check current min capacity is valid
268 if self.min_capacity < 1 {
269 return Err(DarkTreeError::InvalidMinCapacity(self.min_capacity))
270 }
271
272 // Check currect max capacity is not less than
273 // current min capacity
274 if let Some(max_capacity) = self.max_capacity {
275 if self.min_capacity > max_capacity {
276 return Err(DarkTreeError::InvalidMaxCapacity(max_capacity, self.min_capacity))
277 }
278 }
279
280 // Check current min capacity
281 self.check_min_capacity()?;
282
283 // Check current max capacity
284 self.check_max_capacity()?;
285
286 // Check each leaf index
287 for (index, leaf) in self.iter().enumerate() {
288 if index != leaf.index {
289 return Err(DarkTreeError::InvalidLeafIndex(leaf.index, index))
290 }
291 }
292
293 // Trigger recursion to check each nodes rest indexes
294 self.check_parent_children_indexes(None)
295 }
296
297 /// Immutably iterate through the tree, using DFS post-order
298 /// traversal.
299 fn iter(&self) -> DarkTreeIter<'_, T> {
300 DarkTreeIter { children: std::slice::from_ref(self), parent: None }
301 }
302
303 /// Mutably iterate through the tree, using DFS post-order
304 /// traversal.
305 fn iter_mut(&mut self) -> DarkTreeIterMut<'_, T> {
306 DarkTreeIterMut { children: std::slice::from_mut(self), parent: None, parent_leaf: None }
307 }
308}
309
310/// Immutable iterator of a [`DarkTree`], performing DFS post-order
311/// traversal on the Tree leafs.
312pub struct DarkTreeIter<'a, T: Clone + Send + Sync> {
313 children: &'a [DarkTree<T>],
314 parent: Option<Box<DarkTreeIter<'a, T>>>,
315}
316
317impl<T: Clone + Send + Sync> Default for DarkTreeIter<'_, T> {
318 fn default() -> Self {
319 DarkTreeIter { children: &[], parent: None }
320 }
321}
322
323impl<'a, T: Clone + Send + Sync> Iterator for DarkTreeIter<'a, T> {
324 type Item = &'a DarkTreeLeaf<T>;
325
326 /// Grab next item iterator visits and return
327 /// its immutable reference, or recursively
328 /// create and continue iteration on current
329 /// leaf's children.
330 fn next(&mut self) -> Option<Self::Item> {
331 match self.children.first() {
332 None => match self.parent.take() {
333 Some(parent) => {
334 // Grab parent's leaf
335 *self = *parent;
336 // Its safe to unwrap here as we effectively returned
337 // to this tree after "pushing" it after its children
338 let leaf = &self.children.first().unwrap().leaf;
339 self.children = &self.children[1..];
340 Some(leaf)
341 }
342 None => None,
343 },
344 Some(leaf) => {
345 // Iterate over tree's children/sub-trees
346 *self = DarkTreeIter {
347 children: leaf.children.as_slice(),
348 parent: Some(Box::new(mem::take(self))),
349 };
350 self.next()
351 }
352 }
353 }
354}
355
356impl<T: Clone + Send + Sync> FusedIterator for DarkTreeIter<'_, T> {}
357
358/// Define fusion iteration behavior, allowing
359/// us to use the [`DarkTreeIter`] iterator in
360/// loops directly, without using .iter() method
361/// of [`DarkTree`].
362impl<'a, T: Clone + Send + Sync> IntoIterator for &'a DarkTree<T> {
363 type Item = &'a DarkTreeLeaf<T>;
364
365 type IntoIter = DarkTreeIter<'a, T>;
366
367 fn into_iter(self) -> Self::IntoIter {
368 self.iter()
369 }
370}
371
372/// Mutable iterator of a [`DarkTree`], performing DFS post-order
373/// traversal on the Tree leafs.
374pub struct DarkTreeIterMut<'a, T: Clone + Send + Sync> {
375 children: &'a mut [DarkTree<T>],
376 parent: Option<Box<DarkTreeIterMut<'a, T>>>,
377 parent_leaf: Option<&'a mut DarkTreeLeaf<T>>,
378}
379
380impl<T: Clone + Send + Sync> Default for DarkTreeIterMut<'_, T> {
381 fn default() -> Self {
382 DarkTreeIterMut { children: &mut [], parent: None, parent_leaf: None }
383 }
384}
385
386impl<'a, T: Clone + Send + Sync> Iterator for DarkTreeIterMut<'a, T> {
387 type Item = &'a mut DarkTreeLeaf<T>;
388
389 /// Grab next item iterator visits and return
390 /// its mutable reference, or recursively
391 /// create and continue iteration on current
392 /// leaf's children.
393 fn next(&mut self) -> Option<Self::Item> {
394 let children = mem::take(&mut self.children);
395 match children.split_first_mut() {
396 None => match self.parent.take() {
397 Some(parent) => {
398 // Grab parent's leaf
399 let parent_leaf = mem::take(&mut self.parent_leaf);
400 *self = *parent;
401 parent_leaf
402 }
403 None => None,
404 },
405 Some((first, rest)) => {
406 // Setup simplings iteration
407 self.children = rest;
408
409 // Iterate over tree's children/sub-trees
410 *self = DarkTreeIterMut {
411 children: first.children.as_mut_slice(),
412 parent: Some(Box::new(mem::take(self))),
413 parent_leaf: Some(&mut first.leaf),
414 };
415 self.next()
416 }
417 }
418 }
419}
420
421/// Define fusion iteration behavior, allowing
422/// us to use the [`DarkTreeIterMut`] iterator
423/// in loops directly, without using .iter_mut()
424/// method of [`DarkTree`].
425impl<'a, T: Clone + Send + Sync> IntoIterator for &'a mut DarkTree<T> {
426 type Item = &'a mut DarkTreeLeaf<T>;
427
428 type IntoIter = DarkTreeIterMut<'a, T>;
429
430 fn into_iter(self) -> Self::IntoIter {
431 self.iter_mut()
432 }
433}
434
435/// Special iterator of a [`DarkTree`], performing DFS post-order
436/// traversal on the Tree leafs, consuming each leaf. Since this
437/// iterator consumes the tree, it becomes unusable after it's moved.
438pub struct DarkTreeIntoIter<T: Clone + Send + Sync> {
439 children: VecDeque<DarkTree<T>>,
440 parent: Option<Box<DarkTreeIntoIter<T>>>,
441}
442
443impl<T: Clone + Send + Sync> Default for DarkTreeIntoIter<T> {
444 fn default() -> Self {
445 DarkTreeIntoIter { children: Default::default(), parent: None }
446 }
447}
448
449impl<T: Clone + Send + Sync> Iterator for DarkTreeIntoIter<T> {
450 type Item = DarkTreeLeaf<T>;
451
452 /// Move next item iterator visits from the tree
453 /// to the iterator consumer, if it has no children.
454 /// Otherwise recursively create and continue iteration
455 /// on current leaf's children, and moving it after them.
456 fn next(&mut self) -> Option<Self::Item> {
457 match self.children.pop_front() {
458 None => match self.parent.take() {
459 Some(parent) => {
460 // Continue iteration on parent's simplings
461 *self = *parent;
462 self.next()
463 }
464 None => None,
465 },
466 Some(mut leaf) => {
467 // If leaf has no children, return it
468 if leaf.children.is_empty() {
469 return Some(leaf.leaf)
470 }
471
472 // Push leaf after its children
473 let mut children: VecDeque<DarkTree<T>> = leaf.children.into();
474 leaf.children = Default::default();
475 children.push_back(leaf);
476
477 // Iterate over tree's children/sub-trees
478 *self = DarkTreeIntoIter { children, parent: Some(Box::new(mem::take(self))) };
479 self.next()
480 }
481 }
482 }
483}
484
485impl<T: Clone + Send + Sync> FusedIterator for DarkTreeIntoIter<T> {}
486
487/// Define fusion iteration behavior, allowing
488/// us to use the [`DarkTreeIntoIter`] .into_iter()
489/// method, to consume the [`DarkTree`] and iterate
490/// over it.
491impl<T: Clone + Send + Sync> IntoIterator for DarkTree<T> {
492 type Item = DarkTreeLeaf<T>;
493
494 type IntoIter = DarkTreeIntoIter<T>;
495
496 fn into_iter(self) -> Self::IntoIter {
497 let mut children = VecDeque::with_capacity(1);
498 children.push_back(self);
499
500 DarkTreeIntoIter { children, parent: None }
501 }
502}
503
504/// Auxiliary function to verify provided [`DarkLeaf`] slice is
505/// properly bounded and its members indexes are valid.
506/// Optionally, an offset can be provided in case leaf indexes
507/// are known to be shifted.
508pub fn dark_leaf_vec_integrity_check<T: Clone + Send + Sync>(
509 leafs: &[DarkLeaf<T>],
510 min_capacity: Option<usize>,
511 max_capacity: Option<usize>,
512 offset: Option<usize>,
513) -> DarkTreeResult<()> {
514 // Setup min capacity
515 let min_capacity = if let Some(min_capacity) = min_capacity {
516 if min_capacity == 0 {
517 1
518 } else {
519 min_capacity
520 }
521 } else {
522 1
523 };
524
525 // Check currect max capacity is not less than
526 // current min capacity
527 if let Some(max_capacity) = max_capacity {
528 if min_capacity > max_capacity {
529 return Err(DarkTreeError::InvalidMaxCapacity(max_capacity, min_capacity))
530 }
531 }
532
533 // Check if min capacity have been not exceeded
534 if leafs.len() < min_capacity {
535 return Err(DarkTreeError::MinCapacityNotExceeded)
536 }
537
538 // Check if max capacity have been exceeded
539 if let Some(max_capacity) = max_capacity {
540 if leafs.len() > max_capacity {
541 return Err(DarkTreeError::MaxCapacityExceeded)
542 }
543 }
544
545 // Setup offset
546 let offset = offset.unwrap_or_default();
547
548 // Grab root index
549 let root_index = leafs.len() - 1 + offset;
550
551 // Check each leaf indexes exluding root(last)
552 let mut checked_indexes = Vec::with_capacity(leafs.len());
553 for (mut index, leaf) in leafs[..leafs.len() - 1].iter().enumerate() {
554 // Shift index by offset
555 index += offset;
556
557 // Check parent index exists
558 let Some(parent_index) = leaf.parent_index else {
559 return Err(DarkTreeError::InvalidLeafParentIndex(index))
560 };
561
562 // Parent index is not out of bounds
563 if parent_index > root_index {
564 return Err(DarkTreeError::InvalidLeafParentIndex(index))
565 }
566
567 // Our index must be less than our parent index
568 if index >= parent_index {
569 return Err(DarkTreeError::InvalidLeafParentIndex(index))
570 }
571
572 // Parent must have our index in their children
573 if !leafs[parent_index - offset].children_indexes.contains(&index) {
574 return Err(DarkTreeError::InvalidLeafChildrenIndexes(parent_index))
575 }
576
577 // Check children indexes validity
578 check_children(leafs, &index, leaf, &checked_indexes, &offset)?;
579
580 checked_indexes.push(index);
581 }
582
583 // It's safe to unwrap here since we enforced min capacity of 1
584 let root = leafs.last().unwrap();
585
586 // Root must not contain a parent
587 if root.parent_index.is_some() {
588 return Err(DarkTreeError::InvalidLeafParentIndex(root_index))
589 }
590
591 // Check its children
592 check_children(leafs, &root_index, root, &checked_indexes, &offset)
593}
594
595/// Check `DarkLeaf` children indexes validity
596fn check_children<T: Clone + Send + Sync>(
597 leafs: &[DarkLeaf<T>],
598 index: &usize,
599 leaf: &DarkLeaf<T>,
600 checked_indexes: &[usize],
601 offset: &usize,
602) -> DarkTreeResult<()> {
603 let mut children_vec = Vec::with_capacity(leaf.children_indexes.len());
604 for child_index in &leaf.children_indexes {
605 // Child index is not out of bounds
606 if child_index < offset {
607 return Err(DarkTreeError::InvalidLeafChildrenIndexes(*index))
608 }
609
610 // Children vector must be sorted and don't contain duplicates
611 if let Some(last) = children_vec.last() {
612 if child_index <= last {
613 return Err(DarkTreeError::InvalidLeafChildrenIndexes(*index))
614 }
615 }
616
617 // We must have already checked that child
618 if !checked_indexes.contains(child_index) {
619 return Err(DarkTreeError::InvalidLeafChildrenIndexes(*index))
620 }
621
622 // Our index must be greater than our child index
623 if index <= child_index {
624 return Err(DarkTreeError::InvalidLeafChildrenIndexes(*index))
625 }
626
627 // Children must have its parent set to us
628 match leafs[*child_index - offset].parent_index {
629 Some(parent_index) => {
630 if parent_index != *index {
631 return Err(DarkTreeError::InvalidLeafParentIndex(*child_index))
632 }
633 }
634 None => return Err(DarkTreeError::InvalidLeafParentIndex(*child_index)),
635 }
636
637 children_vec.push(*child_index);
638 }
639
640 Ok(())
641}
642
643/// This struct represents a Forest of [`DarkTree`].
644/// It is advised to always execute .build() after finishing
645/// setting up the Forest, to properly index it and check
646/// its integrity.
647#[derive(Debug, PartialEq)]
648pub struct DarkForest<T: Clone + Send + Sync> {
649 /// Vector containing all forest's trees
650 trees: Vec<DarkTree<T>>,
651 /// Optional min capacity of the forest, including all tree
652 /// leafs. If tree leafs make us not exceed that min capacity,
653 /// we will be able to catch it using .check_min_capacity()
654 /// or .integrity_check().
655 min_capacity: Option<usize>,
656 /// Optional max capacity of the forest, including all tree
657 /// leafs. None indicates no capacity restrictions. If tree
658 /// leafs make us exceed that capacity, we will be able to
659 /// catch it using .check_max_capacity() or .integrity_check().
660 max_capacity: Option<usize>,
661}
662
663impl<T: Clone + Send + Sync> DarkForest<T> {
664 /// Initialize a [`DarkTree`], using provided data to
665 /// generate its root.
666 pub fn new(min_capacity: Option<usize>, max_capacity: Option<usize>) -> DarkForest<T> {
667 Self { trees: vec![], min_capacity, max_capacity }
668 }
669
670 /// Build each individual [`DarkTree`] indexes and
671 // perform an integrity check on them. This should
672 /// be used after we have appended all trees, so we
673 /// don't have to call .index() and .integrity_check()
674 /// manually.
675 pub fn build(&mut self) -> DarkTreeResult<()> {
676 self.index();
677 self.integrity_check()
678 }
679
680 /// Build each individual [`DarkTree`] using .build()
681 /// and then produce a flattened vector containing,
682 /// all the leafs in DFS post-order traversal order,
683 /// updating their indexes to correspond to the tree
684 /// position in the forest.
685 pub fn build_vec(&mut self) -> DarkTreeResult<Vec<DarkLeaf<T>>> {
686 self.build()?;
687 let mut forest_leafs = vec![];
688 for tree in &self.trees {
689 let mut tree_leafs: Vec<DarkLeaf<T>> = tree.iter().cloned().map(|x| x.info).collect();
690 // Shift leafs indexes by current forest leafs length
691 let shift = forest_leafs.len();
692 for tree_leaf in &mut tree_leafs {
693 if let Some(parent) = &mut tree_leaf.parent_index {
694 *parent += shift;
695 }
696 for child_index in &mut tree_leaf.children_indexes {
697 *child_index += shift;
698 }
699 }
700 forest_leafs.extend(tree_leafs);
701 }
702 Ok(forest_leafs)
703 }
704
705 /// Return the count of all [`DarkForest`] leafs.
706 fn len(&self) -> usize {
707 let mut len = 0;
708 for tree in &self.trees {
709 len += tree.iter().count()
710 }
711 len
712 }
713
714 /// Check if configured min capacity have not been exceeded.
715 fn check_min_capacity(&self) -> DarkTreeResult<()> {
716 if let Some(min_capacity) = self.min_capacity {
717 if self.len() < min_capacity {
718 return Err(DarkTreeError::MinCapacityNotExceeded)
719 }
720 }
721
722 Ok(())
723 }
724
725 /// Check if configured max capacity have been exceeded.
726 fn check_max_capacity(&self) -> DarkTreeResult<()> {
727 if let Some(max_capacity) = self.max_capacity {
728 if self.len() > max_capacity {
729 return Err(DarkTreeError::MaxCapacityExceeded)
730 }
731 }
732
733 Ok(())
734 }
735
736 /// Append a new [`DarkTree`] to the [`DarkForest`],
737 /// if max capacity has not been exceeded. This call
738 /// doesn't update the indexes, so either .index()
739 /// or .build() must be called after it.
740 pub fn append(&mut self, tree: DarkTree<T>) -> DarkTreeResult<()> {
741 // Check current max capacity
742 if let Some(max_capacity) = self.max_capacity {
743 if self.len() + tree.len() > max_capacity {
744 return Err(DarkTreeError::MaxCapacityExceeded)
745 }
746 }
747
748 // Append the new tree
749 self.trees.push(tree);
750
751 Ok(())
752 }
753
754 /// Setup each individual [`DarkTree`]'s leafs indexes.
755 fn index(&mut self) {
756 for tree in &mut self.trees {
757 tree.index();
758 }
759 }
760
761 /// Verify each individual [`DarkTree`]'s leafs indexes validity,
762 /// based on DFS post-order traversal order. Additionally,
763 /// check that min and max capacities have been properly
764 /// configured, min capacity has been exceeded and max
765 /// capacity has not.
766 fn integrity_check(&self) -> DarkTreeResult<()> {
767 // Check currect max capacity is not less than
768 // current min capacity
769 if let Some(min_capacity) = self.min_capacity {
770 if let Some(max_capacity) = self.max_capacity {
771 if min_capacity > max_capacity {
772 return Err(DarkTreeError::InvalidMaxCapacity(max_capacity, min_capacity))
773 }
774 }
775 }
776
777 // Check current min capacity
778 self.check_min_capacity()?;
779
780 // Check current max capacity
781 self.check_max_capacity()?;
782
783 // Check each tree integrity
784 for tree in &self.trees {
785 tree.integrity_check()?;
786 }
787
788 Ok(())
789 }
790}
791
792/// Auxiliary function to verify provided [`DarkLeaf`] slice,
793/// representing the leafs of a [`DarkForest`], is properly
794/// bounded and its members indexes are valid. Slice must
795/// contain at least 1 leaf.
796pub fn dark_forest_leaf_vec_integrity_check<T: Clone + Send + Sync>(
797 leafs: &[DarkLeaf<T>],
798 min_capacity: Option<usize>,
799 max_capacity: Option<usize>,
800) -> DarkTreeResult<()> {
801 // Setup min capacity
802 let min_capacity = if let Some(min_capacity) = min_capacity {
803 if min_capacity == 0 {
804 1
805 } else {
806 min_capacity
807 }
808 } else {
809 1
810 };
811
812 // Check currect max capacity is not less than
813 // current min capacity
814 if let Some(max_capacity) = max_capacity {
815 if min_capacity > max_capacity {
816 return Err(DarkTreeError::InvalidMaxCapacity(max_capacity, min_capacity))
817 }
818 }
819
820 // Check if min capacity have been not exceeded
821 if leafs.len() < min_capacity {
822 return Err(DarkTreeError::MinCapacityNotExceeded)
823 }
824
825 // Check if max capacity have been exceeded
826 if let Some(max_capacity) = max_capacity {
827 if leafs.len() > max_capacity {
828 return Err(DarkTreeError::MaxCapacityExceeded)
829 }
830 }
831
832 // Identify each individual [`DarkTree`]'s leafs and verify
833 // their slice. We identiy each tree root as it will be the
834 // first leaf in the sequence without a parent.
835 let mut tree_leafs = vec![];
836 let mut offset = 0;
837 for leaf in leafs {
838 tree_leafs.push(leaf.clone());
839 if leaf.parent_index.is_none() {
840 dark_leaf_vec_integrity_check(&tree_leafs, None, None, Some(offset))?;
841 offset = tree_leafs.len();
842 tree_leafs = vec![];
843 }
844 }
845
846 if !tree_leafs.is_empty() {
847 return Err(DarkTreeError::InvalidLeafParentIndex(leafs.len() - 1))
848 }
849
850 Ok(())
851}
852
853#[cfg(test)]
854mod tests {
855 use super::*;
856
857 /// Gereate a predefined [`DarkTree`] along with its
858 /// expected traversal order.
859 ///
860 /// Tree structure:
861 /// 22
862 /// / | \
863 /// 10 14 21
864 /// / / \ \ / \ / | \
865 /// 2 4 6 9 12 13 17 18 20
866 /// / \ | | / \ | / \ |
867 /// 0 1 3 5 7 8 11 15 16 19
868 ///
869 /// Expected traversal order is indicated by each leaf's number
870 fn generate_tree() -> DarkTreeResult<(DarkTree<i32>, Vec<i32>)> {
871 let mut tree = DarkTree::new(
872 22,
873 vec![
874 DarkTree::new(
875 10,
876 vec![
877 DarkTree::new(
878 2,
879 vec![
880 DarkTree::new(0, vec![], None, None),
881 DarkTree::new(1, vec![], None, None),
882 ],
883 None,
884 None,
885 ),
886 DarkTree::new(4, vec![DarkTree::new(3, vec![], None, None)], None, None),
887 DarkTree::new(6, vec![DarkTree::new(5, vec![], None, None)], None, None),
888 DarkTree::new(
889 9,
890 vec![
891 DarkTree::new(7, vec![], None, None),
892 DarkTree::new(8, vec![], None, None),
893 ],
894 None,
895 None,
896 ),
897 ],
898 None,
899 None,
900 ),
901 DarkTree::new(
902 14,
903 vec![
904 DarkTree::new(12, vec![DarkTree::new(11, vec![], None, None)], None, None),
905 DarkTree::new(13, vec![], None, None),
906 ],
907 None,
908 None,
909 ),
910 DarkTree::new(
911 21,
912 vec![
913 DarkTree::new(
914 17,
915 vec![
916 DarkTree::new(15, vec![], None, None),
917 DarkTree::new(16, vec![], None, None),
918 ],
919 None,
920 None,
921 ),
922 DarkTree::new(18, vec![], None, None),
923 DarkTree::new(20, vec![DarkTree::new(19, vec![], None, None)], None, None),
924 ],
925 None,
926 None,
927 ),
928 ],
929 None,
930 None,
931 );
932
933 tree.build()?;
934
935 let traversal_order = (0..23).collect();
936
937 Ok((tree, traversal_order))
938 }
939
940 #[test]
941 fn test_darktree_iterator() -> DarkTreeResult<()> {
942 let (tree, traversal_order) = generate_tree()?;
943
944 // Use [`DarkTree`] iterator to collect current
945 // data, in order
946 let nums: Vec<i32> = tree.iter().map(|x| x.info.data).collect();
947
948 // Verify iterator collected the data in the expected
949 // traversal order.
950 assert_eq!(nums, traversal_order);
951
952 // Verify using iterator indexing methods to retrieve
953 // data from it, returns the expected one, as per
954 // expected traversal order.
955 assert_eq!(tree.iter().nth(1).unwrap().info.data, traversal_order[1]);
956
957 // Thanks for reading
958 Ok(())
959 }
960
961 #[test]
962 fn test_darktree_traversal_order() -> DarkTreeResult<()> {
963 let (mut tree, traversal_order) = generate_tree()?;
964
965 // Loop using the fusion immutable iterator,
966 // verifying we grab the correct [`DarkTreeLeaf`]
967 // immutable reference, as per expected
968 // traversal order.
969 let mut index = 0;
970 for leaf in &tree {
971 assert_eq!(leaf.info.data, traversal_order[index]);
972 index += 1;
973 }
974
975 // Loop using the fusion mutable iterator,
976 // verifying we grab the correct [`DarkTreeLeaf`]
977 // mutable reference, as per expected traversal
978 // order.
979 index = 0;
980 for leaf in &mut tree {
981 assert_eq!(leaf.info.data, traversal_order[index]);
982 index += 1;
983 }
984
985 // Loop using [`DarkTree`] .iter_mut() mutable
986 // iterator, verifying we grab the correct [`DarkTreeLeaf`]
987 // mutable reference, as per expected traversal
988 // order.
989 for (index, leaf) in tree.iter_mut().enumerate() {
990 assert_eq!(leaf.info.data, traversal_order[index]);
991 }
992
993 // Loop using [`DarkTree`] .iter() immutable
994 // iterator, verifying we grab the correct [`DarkTreeLeaf`]
995 // immutable reference, as per expected traversal
996 // order.
997 for (index, leaf) in tree.iter().enumerate() {
998 assert_eq!(leaf.info.data, traversal_order[index]);
999 }
1000
1001 // Loop using [`DarkTree`] .into_iter() iterator,
1002 // which consumes (moves) the tree, verifying we
1003 // collect the correct [`DarkTreeLeaf`], as per expected
1004 // traversal order.
1005 for (index, leaf) in tree.into_iter().enumerate() {
1006 assert_eq!(leaf.info.data, traversal_order[index]);
1007 }
1008
1009 // Thanks for reading
1010 Ok(())
1011 }
1012
1013 #[test]
1014 fn test_darktree_mut_iterator() -> DarkTreeResult<()> {
1015 let (mut tree, _) = generate_tree()?;
1016
1017 // Loop using [`DarkTree`] .iter_mut() mutable
1018 // iterator, grabing a mutable reference over a
1019 // [`DarkTreeLeaf`], and mutating its inner data.
1020 for leaf in tree.iter_mut() {
1021 leaf.info.data += 1;
1022 }
1023
1024 // Loop using the fusion mutable iterator,
1025 // grabing a mutable reference over a
1026 // [`DarkTreeLeaf`], and mutating its inner data.
1027 for leaf in &mut tree {
1028 leaf.info.data += 1;
1029 }
1030
1031 // Verify performed mutation actually happened
1032 // on original tree. Additionally we verify all
1033 // indexes are the expected ones.
1034 assert_eq!(
1035 tree,
1036 DarkTree {
1037 leaf: DarkTreeLeaf {
1038 index: 22,
1039 info: DarkLeaf {
1040 data: 24,
1041 parent_index: None,
1042 children_indexes: vec![10, 14, 21]
1043 },
1044 },
1045 children: vec![
1046 DarkTree {
1047 leaf: DarkTreeLeaf {
1048 index: 10,
1049 info: DarkLeaf {
1050 data: 12,
1051 parent_index: Some(22),
1052 children_indexes: vec![2, 4, 6, 9],
1053 },
1054 },
1055 children: vec![
1056 DarkTree {
1057 leaf: DarkTreeLeaf {
1058 index: 2,
1059 info: DarkLeaf {
1060 data: 4,
1061 parent_index: Some(10),
1062 children_indexes: vec![0, 1],
1063 },
1064 },
1065 children: vec![
1066 DarkTree {
1067 leaf: DarkTreeLeaf {
1068 index: 0,
1069 info: DarkLeaf {
1070 data: 2,
1071 parent_index: Some(2),
1072 children_indexes: vec![],
1073 },
1074 },
1075 children: vec![],
1076 min_capacity: 1,
1077 max_capacity: None,
1078 },
1079 DarkTree {
1080 leaf: DarkTreeLeaf {
1081 index: 1,
1082 info: DarkLeaf {
1083 data: 3,
1084 parent_index: Some(2),
1085 children_indexes: vec![],
1086 },
1087 },
1088 children: vec![],
1089 min_capacity: 1,
1090 max_capacity: None,
1091 },
1092 ],
1093 min_capacity: 1,
1094 max_capacity: None,
1095 },
1096 DarkTree {
1097 leaf: DarkTreeLeaf {
1098 index: 4,
1099 info: DarkLeaf {
1100 data: 6,
1101 parent_index: Some(10),
1102 children_indexes: vec![3],
1103 },
1104 },
1105 children: vec![DarkTree {
1106 leaf: DarkTreeLeaf {
1107 index: 3,
1108 info: DarkLeaf {
1109 data: 5,
1110 parent_index: Some(4),
1111 children_indexes: vec![],
1112 },
1113 },
1114 children: vec![],
1115 min_capacity: 1,
1116 max_capacity: None,
1117 },],
1118 min_capacity: 1,
1119 max_capacity: None,
1120 },
1121 DarkTree {
1122 leaf: DarkTreeLeaf {
1123 index: 6,
1124 info: DarkLeaf {
1125 data: 8,
1126 parent_index: Some(10),
1127 children_indexes: vec![5],
1128 },
1129 },
1130 children: vec![DarkTree {
1131 leaf: DarkTreeLeaf {
1132 index: 5,
1133 info: DarkLeaf {
1134 data: 7,
1135 parent_index: Some(6),
1136 children_indexes: vec![],
1137 },
1138 },
1139 children: vec![],
1140 min_capacity: 1,
1141 max_capacity: None,
1142 },],
1143 min_capacity: 1,
1144 max_capacity: None,
1145 },
1146 DarkTree {
1147 leaf: DarkTreeLeaf {
1148 index: 9,
1149 info: DarkLeaf {
1150 data: 11,
1151 parent_index: Some(10),
1152 children_indexes: vec![7, 8],
1153 },
1154 },
1155 children: vec![
1156 DarkTree {
1157 leaf: DarkTreeLeaf {
1158 index: 7,
1159 info: DarkLeaf {
1160 data: 9,
1161 parent_index: Some(9),
1162 children_indexes: vec![],
1163 },
1164 },
1165 children: vec![],
1166 min_capacity: 1,
1167 max_capacity: None,
1168 },
1169 DarkTree {
1170 leaf: DarkTreeLeaf {
1171 index: 8,
1172 info: DarkLeaf {
1173 data: 10,
1174 parent_index: Some(9),
1175 children_indexes: vec![],
1176 },
1177 },
1178 children: vec![],
1179 min_capacity: 1,
1180 max_capacity: None,
1181 },
1182 ],
1183 min_capacity: 1,
1184 max_capacity: None,
1185 },
1186 ],
1187 min_capacity: 1,
1188 max_capacity: None,
1189 },
1190 DarkTree {
1191 leaf: DarkTreeLeaf {
1192 index: 14,
1193 info: DarkLeaf {
1194 data: 16,
1195 parent_index: Some(22),
1196 children_indexes: vec![12, 13],
1197 },
1198 },
1199 children: vec![
1200 DarkTree {
1201 leaf: DarkTreeLeaf {
1202 index: 12,
1203 info: DarkLeaf {
1204 data: 14,
1205 parent_index: Some(14),
1206 children_indexes: vec![11],
1207 },
1208 },
1209 children: vec![DarkTree {
1210 leaf: DarkTreeLeaf {
1211 index: 11,
1212 info: DarkLeaf {
1213 data: 13,
1214 parent_index: Some(12),
1215 children_indexes: vec![],
1216 },
1217 },
1218 children: vec![],
1219 min_capacity: 1,
1220 max_capacity: None,
1221 },],
1222 min_capacity: 1,
1223 max_capacity: None,
1224 },
1225 DarkTree {
1226 leaf: DarkTreeLeaf {
1227 index: 13,
1228 info: DarkLeaf {
1229 data: 15,
1230 parent_index: Some(14),
1231 children_indexes: vec![],
1232 },
1233 },
1234 children: vec![],
1235 min_capacity: 1,
1236 max_capacity: None,
1237 },
1238 ],
1239 min_capacity: 1,
1240 max_capacity: None,
1241 },
1242 DarkTree {
1243 leaf: DarkTreeLeaf {
1244 index: 21,
1245 info: DarkLeaf {
1246 data: 23,
1247 parent_index: Some(22),
1248 children_indexes: vec![17, 18, 20],
1249 },
1250 },
1251 children: vec![
1252 DarkTree {
1253 leaf: DarkTreeLeaf {
1254 index: 17,
1255 info: DarkLeaf {
1256 data: 19,
1257 parent_index: Some(21),
1258 children_indexes: vec![15, 16],
1259 },
1260 },
1261 children: vec![
1262 DarkTree {
1263 leaf: DarkTreeLeaf {
1264 index: 15,
1265 info: DarkLeaf {
1266 data: 17,
1267 parent_index: Some(17),
1268 children_indexes: vec![],
1269 },
1270 },
1271 children: vec![],
1272 min_capacity: 1,
1273 max_capacity: None,
1274 },
1275 DarkTree {
1276 leaf: DarkTreeLeaf {
1277 index: 16,
1278 info: DarkLeaf {
1279 data: 18,
1280 parent_index: Some(17),
1281 children_indexes: vec![],
1282 },
1283 },
1284 children: vec![],
1285 min_capacity: 1,
1286 max_capacity: None,
1287 },
1288 ],
1289 min_capacity: 1,
1290 max_capacity: None,
1291 },
1292 DarkTree {
1293 leaf: DarkTreeLeaf {
1294 index: 18,
1295 info: DarkLeaf {
1296 data: 20,
1297 parent_index: Some(21),
1298 children_indexes: vec![],
1299 },
1300 },
1301 children: vec![],
1302 min_capacity: 1,
1303 max_capacity: None,
1304 },
1305 DarkTree {
1306 leaf: DarkTreeLeaf {
1307 index: 20,
1308 info: DarkLeaf {
1309 data: 22,
1310 parent_index: Some(21),
1311 children_indexes: vec![19]
1312 },
1313 },
1314 children: vec![DarkTree {
1315 leaf: DarkTreeLeaf {
1316 index: 19,
1317 info: DarkLeaf {
1318 data: 21,
1319 parent_index: Some(20),
1320 children_indexes: vec![],
1321 },
1322 },
1323 children: vec![],
1324 min_capacity: 1,
1325 max_capacity: None,
1326 },],
1327 min_capacity: 1,
1328 max_capacity: None,
1329 },
1330 ],
1331 min_capacity: 1,
1332 max_capacity: None,
1333 },
1334 ],
1335 min_capacity: 1,
1336 max_capacity: None,
1337 }
1338 );
1339
1340 let traversal_order: Vec<i32> = (2..25).collect();
1341
1342 // Use [`DarkTree`] iterator to collect current
1343 // data, in order
1344 let nums: Vec<i32> = tree.iter().map(|x| x.info.data).collect();
1345
1346 // Verify iterator collected the data in the expected
1347 // traversal order.
1348 assert_eq!(nums, traversal_order);
1349
1350 // Thanks for reading
1351 Ok(())
1352 }
1353
1354 #[test]
1355 fn test_darktree_min_capacity() -> DarkTreeResult<()> {
1356 // Generate a new [`DarkTree`] with min capacity 0
1357 let mut tree = DarkTree::new(0, vec![], Some(0), None);
1358
1359 // Verify that min capacity was properly setup to 1
1360 assert_eq!(
1361 tree,
1362 DarkTree {
1363 leaf: DarkTreeLeaf {
1364 index: 0,
1365 info: DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1366 },
1367 children: vec![],
1368 min_capacity: 1,
1369 max_capacity: None
1370 }
1371 );
1372
1373 // Verify that building it will succeed, as capacity
1374 // would have ben setup to 1
1375 assert!(tree.build().is_ok());
1376
1377 // Generate a new [`DarkTree`] manually with
1378 // min capacity 0
1379 let mut tree = DarkTree {
1380 leaf: DarkTreeLeaf {
1381 index: 0,
1382 info: DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1383 },
1384 children: vec![],
1385 min_capacity: 0,
1386 max_capacity: None,
1387 };
1388
1389 // Verify that building it will fail
1390 assert!(tree.build().is_err());
1391
1392 // Thanks for reading
1393 Ok(())
1394 }
1395
1396 #[test]
1397 fn test_darktree_max_capacity() -> DarkTreeResult<()> {
1398 // Generate a new [`DarkTree`] with max capacity 2
1399 let mut tree = DarkTree::new(0, vec![], None, Some(2));
1400
1401 // Append a new node
1402 tree.append(DarkTree::new(1, vec![], None, None))?;
1403
1404 // Try to append a new node
1405 assert!(tree.append(DarkTree::new(2, vec![], None, None)).is_err());
1406
1407 // Verify tree builds
1408 tree.build()?;
1409
1410 // Generate a new [`DarkTree`] with max capacity 2
1411 let mut new_tree = DarkTree::new(3, vec![], None, Some(2));
1412
1413 // Append the previous tree as a new node
1414 new_tree.append(tree)?;
1415
1416 // Check that max capacity has been exceeded
1417 assert!(new_tree.check_max_capacity().is_err());
1418
1419 // Generate a new [`DarkTree`] manually with
1420 // max capacity 1
1421 let mut tree = DarkTree {
1422 leaf: DarkTreeLeaf {
1423 index: 0,
1424 info: DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1425 },
1426 children: vec![
1427 DarkTree {
1428 leaf: DarkTreeLeaf {
1429 index: 0,
1430 info: DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1431 },
1432 children: vec![],
1433 min_capacity: 1,
1434 max_capacity: None,
1435 },
1436 DarkTree {
1437 leaf: DarkTreeLeaf {
1438 index: 0,
1439 info: DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1440 },
1441 children: vec![],
1442 min_capacity: 1,
1443 max_capacity: None,
1444 },
1445 DarkTree {
1446 leaf: DarkTreeLeaf {
1447 index: 0,
1448 info: DarkLeaf { data: 0, parent_index: None, children_indexes: vec![0] },
1449 },
1450 children: vec![],
1451 min_capacity: 1,
1452 max_capacity: None,
1453 },
1454 ],
1455 min_capacity: 1,
1456 max_capacity: Some(1),
1457 };
1458
1459 // Verify that building it will fail
1460 assert!(tree.build().is_err());
1461
1462 // Generate a new [`DarkTree`] with max capacity 0,
1463 // which is less that current min capacity 1
1464 let mut tree = DarkTree::new(0, vec![], None, Some(0));
1465
1466 // Verify that building it will fail
1467 assert!(tree.build().is_err());
1468
1469 // Thanks for reading
1470 Ok(())
1471 }
1472
1473 #[test]
1474 fn test_darktree_flattened_vec() -> DarkTreeResult<()> {
1475 let (mut tree, traversal_order) = generate_tree()?;
1476
1477 // Build the flattened vector
1478 let vec = tree.build_vec()?;
1479
1480 // Verify vector integrity
1481 dark_leaf_vec_integrity_check(&vec, Some(23), Some(23), None)?;
1482
1483 // Verify vector integrity will fail using different bounds:
1484 // 1. Leafs less that min capacity
1485 assert!(dark_leaf_vec_integrity_check(&vec, Some(24), None, None).is_err());
1486 // 2. Leafs more than max capacity
1487 assert!(dark_leaf_vec_integrity_check(&vec, None, Some(22), None).is_err());
1488 // 3. Max capacity less than min capacity
1489 assert!(dark_leaf_vec_integrity_check(&vec, Some(23), Some(22), None).is_err());
1490
1491 // Loop the vector to verify it follows expected
1492 // traversal order.
1493 for (index, leaf) in vec.iter().enumerate() {
1494 assert_eq!(leaf.data, traversal_order[index]);
1495 }
1496
1497 // Verify the tree is still intact
1498 let (new_tree, _) = generate_tree()?;
1499 assert_eq!(tree, new_tree);
1500
1501 // Generate a new [`DarkLeaf`] vector manually,
1502 // corresponding to a [`DarkTree`] with a 2 children,
1503 // with erroneous indexes
1504 let vec = vec![
1505 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1506 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1507 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![0, 2] },
1508 ];
1509
1510 // Verify vector integrity will fail
1511 assert!(dark_leaf_vec_integrity_check(&vec, None, None, None).is_err());
1512
1513 // Generate a new [`DarkLeaf`] vector manually,
1514 // corresponding to a [`DarkTree`] with out of bound parent index.
1515 let vec = vec![DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] }];
1516
1517 // Verify vector integrity will fail
1518 assert!(dark_leaf_vec_integrity_check(&vec, None, None, None).is_err());
1519
1520 // Generate a new [`DarkLeaf`] vector manually,
1521 // corresponding to a [`DarkTree`] with out of bound children indexes
1522 let vec = vec![DarkLeaf { data: 0, parent_index: None, children_indexes: vec![1] }];
1523
1524 // Verify vector integrity will fail
1525 assert!(dark_leaf_vec_integrity_check(&vec, None, None, None).is_err());
1526
1527 // Generate a new [`DarkLeaf`] vector manually,
1528 // corresponding to a [`DarkTree`] with duplicate children indexes
1529 let vec = vec![
1530 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1531 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1532 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![1, 1, 2] },
1533 ];
1534
1535 // Verify vector integrity will fail
1536 assert!(dark_leaf_vec_integrity_check(&vec, None, None, None).is_err());
1537
1538 // Generate a new [`DarkLeaf`] vector manually,
1539 // corresponding to a [`DarkTree`] with children after parent
1540 let vec = vec![
1541 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![1, 2] },
1542 DarkLeaf { data: 0, parent_index: Some(0), children_indexes: vec![] },
1543 DarkLeaf { data: 0, parent_index: Some(0), children_indexes: vec![] },
1544 ];
1545
1546 // Verify vector integrity will fail
1547 assert!(dark_leaf_vec_integrity_check(&vec, None, None, None).is_err());
1548
1549 // Generate a new [`DarkLeaf`] vector manually,
1550 // corresponding to a [`DarkTree`] with nothing indexed
1551 let vec = vec![
1552 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1553 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1554 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1555 ];
1556
1557 // Verify vector integrity will fail
1558 assert!(dark_leaf_vec_integrity_check(&vec, None, None, None).is_err());
1559
1560 // Thanks for reading
1561 Ok(())
1562 }
1563
1564 #[test]
1565 fn test_darktree_forest_flattened_vec() -> DarkTreeResult<()> {
1566 let (tree, mut traversal_order) = generate_tree()?;
1567
1568 // Duplicate traversal order
1569 traversal_order.extend(traversal_order.clone());
1570
1571 // Generate a new [`DarkForest`] and append trees
1572 let mut forest = DarkForest::new(Some(23), Some(46));
1573 forest.append(tree.clone())?;
1574 forest.append(tree.clone())?;
1575
1576 // Verify appending another tree will fail
1577 assert!(forest.append(tree).is_err());
1578
1579 // Build the flattened vector
1580 let vec = forest.build_vec()?;
1581
1582 // Verify vector integrity
1583 dark_forest_leaf_vec_integrity_check(&vec, Some(23), Some(46))?;
1584
1585 // Verify vector integrity will fail using different bounds:
1586 // 1. Leafs less that min capacity
1587 assert!(dark_forest_leaf_vec_integrity_check(&vec, Some(47), None).is_err());
1588 // 2. Leafs more than max capacity
1589 assert!(dark_forest_leaf_vec_integrity_check(&vec, None, Some(45)).is_err());
1590 // 3. Max capacity less than min capacity
1591 assert!(dark_forest_leaf_vec_integrity_check(&vec, Some(23), Some(22)).is_err());
1592
1593 // Loop the vector to verify it follows expected
1594 // traversal order.
1595 for (index, leaf) in vec.iter().enumerate() {
1596 assert_eq!(leaf.data, traversal_order[index]);
1597 }
1598
1599 // Generate a new [`DarkLeaf`] vector manually,
1600 // corresponding to a [`DarkForest`] with a 2 trees,
1601 // with erroneous indexes
1602 let vec = vec![
1603 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1604 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1605 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![0, 1] },
1606 DarkLeaf { data: 0, parent_index: Some(5), children_indexes: vec![] },
1607 DarkLeaf { data: 0, parent_index: Some(5), children_indexes: vec![] },
1608 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![0, 1] },
1609 ];
1610
1611 // Verify vector integrity will fail
1612 assert!(dark_forest_leaf_vec_integrity_check(&vec, None, None).is_err());
1613
1614 // Generate a new [`DarkLeaf`] vector manually,
1615 // corresponding to a [`DarkForest`] with out of bound parent index.
1616 let vec = vec![DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] }];
1617
1618 // Verify vector integrity will fail
1619 assert!(dark_forest_leaf_vec_integrity_check(&vec, None, None).is_err());
1620
1621 // Generate a new [`DarkLeaf`] empty vector
1622 let vec: Vec<DarkLeaf<i32>> = vec![];
1623
1624 // Verify vector integrity will fail
1625 assert!(dark_forest_leaf_vec_integrity_check(&vec, None, None).is_err());
1626
1627 // Generate a new [`DarkLeaf`] vector manually,
1628 // corresponding to a [`DarkForest`] with out of bound children indexes
1629 let vec = vec![
1630 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1631 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1632 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![3, 4] },
1633 DarkLeaf { data: 0, parent_index: Some(5), children_indexes: vec![] },
1634 DarkLeaf { data: 0, parent_index: Some(5), children_indexes: vec![] },
1635 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![3, 4] },
1636 ];
1637
1638 // Verify vector integrity will fail
1639 assert!(dark_forest_leaf_vec_integrity_check(&vec, None, None).is_err());
1640
1641 // Generate a new [`DarkLeaf`] vector manually,
1642 // corresponding to a [`DarkForest`] with duplicate children indexes
1643 let vec = vec![
1644 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1645 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1646 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![0, 1] },
1647 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1648 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1649 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![3, 3, 4] },
1650 ];
1651
1652 // Verify vector integrity will fail
1653 assert!(dark_forest_leaf_vec_integrity_check(&vec, None, None).is_err());
1654
1655 // Generate a new [`DarkLeaf`] vector manually,
1656 // corresponding to a [`DarkForest`] with children after parent
1657 let vec = vec![
1658 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1659 DarkLeaf { data: 0, parent_index: Some(2), children_indexes: vec![] },
1660 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![0, 1] },
1661 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![4, 5] },
1662 DarkLeaf { data: 0, parent_index: Some(3), children_indexes: vec![] },
1663 DarkLeaf { data: 0, parent_index: Some(3), children_indexes: vec![] },
1664 ];
1665
1666 // Verify vector integrity will fail
1667 assert!(dark_forest_leaf_vec_integrity_check(&vec, None, None).is_err());
1668
1669 // Generate a new [`DarkLeaf`] vector manually,
1670 // corresponding to a [`DarkForest`] with 3 single leaf trees
1671 let vec = vec![
1672 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1673 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1674 DarkLeaf { data: 0, parent_index: None, children_indexes: vec![] },
1675 ];
1676
1677 // Verify vector integrity
1678 dark_forest_leaf_vec_integrity_check(&vec, None, None)?;
1679
1680 // Thanks for reading
1681 Ok(())
1682 }
1683}