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 )?) {
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 )?) {
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
})
}
}
};
}