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 */
| |