blob: 7e7398c3f008901c48000c2e5d77899af341e48c (
plain)
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
|
// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef APP_TREE_NODE_ITERATOR_H_
#define APP_TREE_NODE_ITERATOR_H_
#include <stack>
#include "base/basictypes.h"
#include "base/logging.h"
// Iterator that iterates over the descendants of a node. The iteration does
// not include the node itself, only the descendants. The following illustrates
// typical usage:
// while (iterator.has_next()) {
// Node* node = iterator.Next();
// // do something with node.
// }
template <class NodeType>
class TreeNodeIterator {
public:
explicit TreeNodeIterator(NodeType* node) {
if (node->GetChildCount() > 0)
positions_.push(Position<NodeType>(node, 0));
}
// Returns true if there are more descendants.
bool has_next() const { return !positions_.empty(); }
// Returns the next descendant.
NodeType* Next() {
if (!has_next()) {
NOTREACHED();
return NULL;
}
NodeType* result = positions_.top().node->GetChild(positions_.top().index);
// Make sure we don't attempt to visit result again.
positions_.top().index++;
// Iterate over result's children.
positions_.push(Position<NodeType>(result, 0));
// Advance to next position.
while (!positions_.empty() && positions_.top().index >=
positions_.top().node->GetChildCount()) {
positions_.pop();
}
return result;
}
private:
template <class PositionNodeType>
struct Position {
Position(PositionNodeType* node, int index) : node(node), index(index) {}
Position() : node(NULL), index(-1) {}
PositionNodeType* node;
int index;
};
std::stack<Position<NodeType> > positions_;
DISALLOW_COPY_AND_ASSIGN(TreeNodeIterator);
};
#endif // APP_TREE_NODE_ITERATOR_H_
|
