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