1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

#[macro_export]
macro_rules! get_tree_type {
    ( $n:ident ) => {
        crate::tpntree::TpnTree<T, $n >
    };
    ( ) => {
        crate::tpntree_dynamic::TpnTree<T>
    };
}

#[macro_export]
macro_rules! impl_depth_first_iterator {
    ( $( $n:ident )? ) => {
            impl<T $(,
                const $n: usize
            )?> $crate::get_tree_type!( $( $n )?) {
                /// Iterate the tree depth first, starting with the root.
                pub fn iter_depth_first(&self) -> DepthFirstIterator<T $(,
                $n
            )?> {
                    DepthFirstIterator::new(self)
                }
            }

            pub struct DepthFirstIterator<'a, T $(,
                const $n: usize
            )?> {
                stack: Vec<&'a $crate::get_tree_type!( $( $n )?)>,
            }

            impl<'a, T $(,
                const $n: usize
            )?> DepthFirstIterator<'a, T $(,
                $n
            )?> {
                fn new(root: &'a $crate::get_tree_type!( $( $n )?)) -> Self {
                    Self { stack: vec![root] }
                }
            }

            impl<'a, T $(,
                const $n: usize
            )?> Iterator for DepthFirstIterator<'a, T $(,
                $n
            )?> {
                type Item = &'a $crate::get_tree_type!( $( $n )?);

                fn next(&mut self) -> Option<Self::Item> {
                    self.stack.pop().map(|tree| {
                        for child in tree.iter_children() {
                            self.stack.push(child);
                        }
                        tree
                    })
                }
        }
    };
}

#[macro_export]
macro_rules! impl_breadth_first_iterator {
    ( $( $n:ident )? ) => {
            impl<T $(,
                const $n: usize
            )?> $crate::get_tree_type!( $( $n )?) {
                /// Iterate the tree breadth first, starting with the root.
                pub fn iter_breadth_first(&self) -> BreadthFirstIterator<T $(,
                $n
            )?> {
                    BreadthFirstIterator::new(self)
                }
            }

            pub struct BreadthFirstIterator<'a, T $(,
                const $n: usize
            )?> {
                queue: std::collections::VecDeque<&'a $crate::get_tree_type!( $( $n )?)>,
            }

            impl<'a, T $(,
                const $n: usize
            )?> BreadthFirstIterator<'a, T $(,
                $n
            )?> {
                fn new(root: &'a $crate::get_tree_type!( $( $n )?)) -> Self {
                    Self {
                        queue: vec![root].into_iter().collect(),
                    }
                }
            }

            impl<'a, T $(,
                const $n: usize
            )?> Iterator for BreadthFirstIterator<'a, T $(,
                $n
            )?> {
                type Item = &'a $crate::get_tree_type!( $( $n )?);

                fn next(&mut self) -> Option<Self::Item> {
                    self.queue.pop_front().map(|tree| {
                        for child in tree.iter_children() {
                            self.queue.push_back(child);
                        }
                        tree
                    })
                }
            }
    };
}