tree_iter/
traversal_order.rs

1/// Marker struct representing breadth-first traversal order.
2///
3/// Breadth-first traversal visits all nodes at the same depth level before moving to the next level.
4/// This is implemented using a queue where children are added to the back of the queue.
5pub struct BreadthFirst;
6
7/// Marker struct representing depth-first traversal order.
8///
9/// Depth-first traversal explores as far down a branch as possible before backtracking.
10/// This is implemented by adding children to the front of the queue or using a stack.
11pub struct DepthFirst;
12
13/// Private module to implement the sealed trait pattern.
14///
15/// This prevents external crates from implementing the `TraversalOrder` trait,
16/// allowing us to maintain control over the possible traversal orders.
17mod seal {
18    pub trait Sealed {}
19    impl Sealed for super::DepthFirst {}
20    impl Sealed for super::BreadthFirst {}
21}
22
23/// Trait for tree traversal order strategies.
24///
25/// This trait is sealed (cannot be implemented outside this crate) and is used as
26/// a marker for different traversal strategies that can be used with tree iterators.
27pub trait TraversalOrder: seal::Sealed {}
28impl TraversalOrder for BreadthFirst {}
29impl TraversalOrder for DepthFirst {}
30
31#[cfg(test)]
32mod tests {
33    use super::*;
34    use crate::iter::TreeNode;
35    use std::collections::VecDeque;
36    use std::marker::PhantomData;
37
38    // Simple test structure to verify trait bounds
39    #[allow(dead_code)]
40    struct TestNode<T> {
41        value: T,
42        children: Vec<TestNode<T>>,
43    }
44
45    impl<T> TreeNode for TestNode<T> {
46        fn children(&self) -> impl DoubleEndedIterator<Item = &Self> + '_ {
47            self.children.iter()
48        }
49    }
50
51    // Basic struct to test traversal order trait bounds
52    #[allow(dead_code)]
53    struct TestTreeIter<'a, N, T> {
54        nodes: VecDeque<&'a N>,
55        _order: PhantomData<T>,
56    }
57
58    impl<'a, N, T: TraversalOrder> TestTreeIter<'a, N, T> {
59        fn new(roots: impl IntoIterator<Item = &'a N>) -> Self {
60            Self {
61                nodes: roots.into_iter().collect(),
62                _order: PhantomData,
63            }
64        }
65    }
66
67    // Test that we can create iterators with different traversal orders
68    #[test]
69    fn test_traversal_order_trait_bounds() {
70        let node = TestNode {
71            value: 1,
72            children: vec![],
73        };
74
75        // These should compile successfully if the trait bounds are correctly set up
76        let _df_iter = TestTreeIter::<_, DepthFirst>::new([&node]);
77        let _bf_iter = TestTreeIter::<_, BreadthFirst>::new([&node]);
78    }
79
80    // Test that the sealed trait pattern prevents outside implementation
81    #[test]
82    fn test_sealed_trait() {
83        // This test doesn't actually assert anything at runtime
84        // But it verifies that the code below doesn't compile (would fail at compile time)
85        // The test passes if the following code remains commented out:
86
87        // This would fail because CustomOrder doesn't implement the sealed Sealed trait
88        // struct CustomOrder;
89        // impl TraversalOrder for CustomOrder {}
90    }
91}
tree_iter/traversal_order.rs

tree_iter/
traversal_order.rs
