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
|
/**
* An universal template to traverse complex trees non-recursive
*
* (c) 2012 Heiko Schäfer <heiko@rangun.de>
*
* This templates contain non-recursive functions to traverse n-trees
*
* Distribution of this file is only allowed if author is mentioned. Modifications of
* the algorithm have to be reported to the author.
*
**/
#ifndef HGL_NR_TRAVERSER_H
#define HGL_NR_TRAVERSER_H
#include <stack>
namespace HGL {
namespace Algorithm {
/**
* @brief A condition on how to proceed before traversing child nodes
*
**/
typedef enum {
/// Continue traversing the children of the current node
CONTINUE,
/// Discard all children of the current node
DISCARD,
/// Break, i.e. stop traversing at this point
BREAK
} COND;
template < typename Iterator, typename Type, typename Begin, typename End, typename Top,
typename Middle, typename Bottom >
/**
* @brief Traverses a n-tree (i.e. a tree with 0-n children on every node), performing actions on
* every node
*
* @note This algorithm works non-recusive.
*
* The middle functor takes a node as argument:
* @code
* void middle(const HGL::IType *);
* @endcode
*
* The top functor additionally returns Algorithm::COND:
* @code
* Algorithm::COND top(const HGL::IType *);
* @endcode
*
* The function should be called with the type of iterator as template parameter:
* @code
* Algorithm::traverse<MYTYPE::iterator>(node, begin, end, top, middle, bottom);
* @endcode
*
* @param root Node to start traversing
* @param getBeginIterator functor to get the begin iterator to the children of the current node
* @param getEndIterator functor to get the end iterator to the children of the current node
* @param top functor called before traversing child nodes
* @param middle functor called after completely traversing all children of current node
* @param bottom functor called after traversing a node
*
* @author Heiko Schäfer <heiko@rangun.de>
**/
void traverse(Type root, Begin &getBeginIterator, End &getEndIterator, Top &top, Middle &middle,
Bottom &bottom) {
std::stack<std::pair<Type, Iterator> > stack;
stack.push(std::make_pair(root, getBeginIterator(root)));
while(!stack.empty()) {
const COND &c = top(stack.top().first);
if(c == CONTINUE) {
while(!stack.empty()) {
Iterator iter = stack.top().second;
if(stack.top().second != getEndIterator(stack.top().first)) {
++(stack.top().second);
stack.push(std::make_pair(*iter, getBeginIterator(*iter)));
break;
} else {
middle(stack.top().first);
stack.pop();
}
}
bottom();
}
if(c == BREAK) break;
}
}
}
}
#endif /* HGL_NR_TRAVERSER_H */
| |
