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
|
// Copyright 2011 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef UI_BASE_MODELS_TREE_NODE_ITERATOR_H_
#define UI_BASE_MODELS_TREE_NODE_ITERATOR_H_
#include <algorithm>
#include "base/check.h"
#include "base/containers/stack.h"
#include "base/functional/callback.h"
#include "base/memory/raw_ptr.h"
namespace ui {
// 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:
typedef base::RepeatingCallback<bool(NodeType*)> PruneCallback;
// This constructor accepts an optional filter function |prune| which could be
// used to prune complete branches of the tree. The filter function will be
// evaluated on each tree node and if it evaluates to true the node and all
// its descendants will be skipped by the iterator.
TreeNodeIterator(NodeType* node, const PruneCallback& prune)
: prune_(prune) {
// Move forward through the children list until the first non prunable node.
// This is to satisfy the iterator invariant that the current index in the
// Position at the top of the _positions list must point to a node the
// iterator will be returning.
const auto i =
std::ranges::find_if(node->children(), [prune](const auto& child) {
return prune.is_null() || !prune.Run(child.get());
});
if (i != node->children().cend())
positions_.emplace(node, i - node->children().cbegin());
}
explicit TreeNodeIterator(NodeType* node) {
if (!node->children().empty())
positions_.emplace(node, 0);
}
TreeNodeIterator(const TreeNodeIterator&) = delete;
TreeNodeIterator& operator=(const TreeNodeIterator&) = delete;
// Returns true if there are more descendants.
bool has_next() const { return !positions_.empty(); }
// Returns the next descendant.
NodeType* Next() {
DCHECK(has_next());
// There must always be a valid node in the current Position index.
NodeType* result =
positions_.top().node->children()[positions_.top().index].get();
// Make sure we don't attempt to visit result again.
++positions_.top().index;
// Iterate over result's children.
positions_.emplace(result, 0);
// Advance to next valid node by skipping over the pruned nodes and the
// empty Positions. At the end of this loop two cases are possible:
// - the current index of the top() Position points to a valid node
// - the _position list is empty, the iterator has_next() will return false.
while (!positions_.empty()) {
auto& top = positions_.top();
if (top.index >= top.node->children().size())
positions_.pop(); // This Position is all processed, move to the next.
else if (!prune_.is_null() &&
prune_.Run(top.node->children()[top.index].get()))
++top.index; // Prune the branch.
else
break; // Now positioned at the next node to be returned.
}
return result;
}
private:
template <class PositionNodeType>
struct Position {
Position(PositionNodeType* node, size_t index) : node(node), index(index) {}
raw_ptr<PositionNodeType> node;
size_t index;
};
base::stack<Position<NodeType>> positions_;
PruneCallback prune_;
};
} // namespace ui
#endif // UI_BASE_MODELS_TREE_NODE_ITERATOR_H_
|
