Source code

Revision control

Other Tools

1
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
3
/* This Source Code Form is subject to the terms of the Mozilla Public
4
* License, v. 2.0. If a copy of the MPL was not distributed with this
5
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7
#ifndef mozilla_layers_TreeTraversal_h
8
#define mozilla_layers_TreeTraversal_h
9
10
#include <queue>
11
#include <type_traits>
12
13
namespace mozilla {
14
namespace layers {
15
16
/*
17
* Returned by |aPostAction| and |aPreAction| in ForEachNode, indicates
18
* the behavior to follow either action:
19
*
20
* TraversalFlag::Skip - the node's children are not traversed. If this
21
* flag is returned by |aPreAction|, |aPostAction| is skipped for the
22
* current node, as well.
23
* TraversalFlag::Continue - traversal continues normally.
24
* TraversalFlag::Abort - traversal stops immediately.
25
*/
26
enum class TraversalFlag { Skip, Continue, Abort };
27
28
/*
29
* Iterator types to be specified in traversal function calls:
30
*
31
* ForwardIterator - for nodes using GetFirstChild() and GetNextSibling()
32
* ReverseIterator - for nodes using GetLastChild() and GetPrevSibling()
33
*/
34
class ForwardIterator {
35
public:
36
template <typename Node>
37
static Node* FirstChild(Node* n) {
38
return n->GetFirstChild();
39
}
40
template <typename Node>
41
static Node* NextSibling(Node* n) {
42
return n->GetNextSibling();
43
}
44
template <typename Node>
45
static Node FirstChild(Node n) {
46
return n.GetFirstChild();
47
}
48
template <typename Node>
49
static Node NextSibling(Node n) {
50
return n.GetNextSibling();
51
}
52
};
53
class ReverseIterator {
54
public:
55
template <typename Node>
56
static Node* FirstChild(Node* n) {
57
return n->GetLastChild();
58
}
59
template <typename Node>
60
static Node* NextSibling(Node* n) {
61
return n->GetPrevSibling();
62
}
63
template <typename Node>
64
static Node FirstChild(Node n) {
65
return n.GetLastChild();
66
}
67
template <typename Node>
68
static Node NextSibling(Node n) {
69
return n.GetPrevSibling();
70
}
71
};
72
73
/*
74
* Do a depth-first traversal of the tree rooted at |aRoot|, performing
75
* |aPreAction| before traversal of children and |aPostAction| after.
76
*
77
* Returns true if traversal aborted, false if continued normally. If
78
* TraversalFlag::Skip is returned in |aPreAction|, then |aPostAction|
79
* is not performed.
80
*
81
* |Iterator| should have static methods named NextSibling() and FirstChild()
82
* that accept an argument of type Node. For convenience, classes
83
* |ForwardIterator| and |ReverseIterator| are provided which implement these
84
* methods as GetNextSibling()/GetFirstChild() and
85
* GetPrevSibling()/GetLastChild(), respectively.
86
*/
87
template <typename Iterator, typename Node, typename PreAction,
88
typename PostAction>
89
static auto ForEachNode(Node aRoot, const PreAction& aPreAction,
90
const PostAction& aPostAction)
91
-> std::enable_if_t<
92
std::is_same_v<decltype(aPreAction(aRoot)), TraversalFlag> &&
93
std::is_same_v<decltype(aPostAction(aRoot)), TraversalFlag>,
94
bool> {
95
if (!aRoot) {
96
return false;
97
}
98
99
TraversalFlag result = aPreAction(aRoot);
100
101
if (result == TraversalFlag::Abort) {
102
return true;
103
}
104
105
if (result == TraversalFlag::Continue) {
106
for (Node child = Iterator::FirstChild(aRoot); child;
107
child = Iterator::NextSibling(child)) {
108
bool abort = ForEachNode<Iterator>(child, aPreAction, aPostAction);
109
if (abort) {
110
return true;
111
}
112
}
113
114
result = aPostAction(aRoot);
115
116
if (result == TraversalFlag::Abort) {
117
return true;
118
}
119
}
120
121
return false;
122
}
123
124
/*
125
* Do a depth-first traversal of the tree rooted at |aRoot|, performing
126
* |aPreAction| before traversal of children and |aPostAction| after.
127
*/
128
template <typename Iterator, typename Node, typename PreAction,
129
typename PostAction>
130
static auto ForEachNode(Node aRoot, const PreAction& aPreAction,
131
const PostAction& aPostAction)
132
-> std::enable_if_t<std::is_same_v<decltype(aPreAction(aRoot)), void> &&
133
std::is_same_v<decltype(aPostAction(aRoot)), void>,
134
void> {
135
if (!aRoot) {
136
return;
137
}
138
139
aPreAction(aRoot);
140
141
for (Node child = Iterator::FirstChild(aRoot); child;
142
child = Iterator::NextSibling(child)) {
143
ForEachNode<Iterator>(child, aPreAction, aPostAction);
144
}
145
146
aPostAction(aRoot);
147
}
148
149
/*
150
* ForEachNode pre-order traversal, using TraversalFlag.
151
*/
152
template <typename Iterator, typename Node, typename PreAction>
153
auto ForEachNode(Node aRoot, const PreAction& aPreAction) -> std::enable_if_t<
154
std::is_same_v<decltype(aPreAction(aRoot)), TraversalFlag>, bool> {
155
return ForEachNode<Iterator>(
156
aRoot, aPreAction, [](Node aNode) { return TraversalFlag::Continue; });
157
}
158
159
/*
160
* ForEachNode pre-order, not using TraversalFlag.
161
*/
162
template <typename Iterator, typename Node, typename PreAction>
163
auto ForEachNode(Node aRoot, const PreAction& aPreAction)
164
-> std::enable_if_t<std::is_same_v<decltype(aPreAction(aRoot)), void>,
165
void> {
166
ForEachNode<Iterator>(aRoot, aPreAction, [](Node aNode) {});
167
}
168
169
/*
170
* ForEachNode post-order traversal, using TraversalFlag.
171
*/
172
template <typename Iterator, typename Node, typename PostAction>
173
auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction)
174
-> std::enable_if_t<
175
std::is_same_v<decltype(aPostAction(aRoot)), TraversalFlag>, bool> {
176
return ForEachNode<Iterator>(
177
aRoot, [](Node aNode) { return TraversalFlag::Continue; }, aPostAction);
178
}
179
180
/*
181
* ForEachNode post-order, not using TraversalFlag.
182
*/
183
template <typename Iterator, typename Node, typename PostAction>
184
auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction)
185
-> std::enable_if_t<std::is_same_v<decltype(aPostAction(aRoot)), void>,
186
void> {
187
ForEachNode<Iterator>(
188
aRoot, [](Node aNode) {}, aPostAction);
189
}
190
191
/*
192
* Do a breadth-first search of the tree rooted at |aRoot|, and return the
193
* first visited node that satisfies |aCondition|, or nullptr if no such node
194
* was found.
195
*
196
* |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
197
* definition, but in addition to those, |Node| must be able to express a null
198
* value, returned from Node()
199
*/
200
template <typename Iterator, typename Node, typename Condition>
201
Node BreadthFirstSearch(Node aRoot, const Condition& aCondition) {
202
if (!aRoot) {
203
return Node();
204
}
205
206
std::queue<Node> queue;
207
queue.push(aRoot);
208
while (!queue.empty()) {
209
Node node = queue.front();
210
queue.pop();
211
212
if (aCondition(node)) {
213
return node;
214
}
215
216
for (Node child = Iterator::FirstChild(node); child;
217
child = Iterator::NextSibling(child)) {
218
queue.push(child);
219
}
220
}
221
222
return Node();
223
}
224
225
/*
226
* Do a pre-order, depth-first search of the tree rooted at |aRoot|, and
227
* return the first visited node that satisfies |aCondition|, or nullptr
228
* if no such node was found.
229
*
230
* |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
231
* definition, but in addition to those, |Node| must be able to express a null
232
* value, returned from Node().
233
*/
234
template <typename Iterator, typename Node, typename Condition>
235
Node DepthFirstSearch(Node aRoot, const Condition& aCondition) {
236
Node result = Node();
237
238
ForEachNode<Iterator>(aRoot, [&aCondition, &result](Node aNode) {
239
if (aCondition(aNode)) {
240
result = aNode;
241
return TraversalFlag::Abort;
242
}
243
244
return TraversalFlag::Continue;
245
});
246
247
return result;
248
}
249
250
/*
251
* Perform a post-order, depth-first search starting at aRoot.
252
*
253
* |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
254
* definition, but in addition to those, |Node| must be able to express a null
255
* value, returned from Node().
256
*/
257
template <typename Iterator, typename Node, typename Condition>
258
Node DepthFirstSearchPostOrder(Node aRoot, const Condition& aCondition) {
259
Node result = Node();
260
261
ForEachNodePostOrder<Iterator>(aRoot, [&aCondition, &result](Node aNode) {
262
if (aCondition(aNode)) {
263
result = aNode;
264
return TraversalFlag::Abort;
265
}
266
267
return TraversalFlag::Continue;
268
});
269
270
return result;
271
}
272
273
} // namespace layers
274
} // namespace mozilla
275
276
#endif // mozilla_layers_TreeTraversal_h