Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
#ifndef mozilla_layers_TreeTraversal_h
#define mozilla_layers_TreeTraversal_h
#include <queue>
#include <type_traits>
namespace mozilla {
namespace layers {
/*
* Returned by |aPostAction| and |aPreAction| in ForEachNode, indicates
* the behavior to follow either action:
*
* TraversalFlag::Skip - the node's children are not traversed. If this
* flag is returned by |aPreAction|, |aPostAction| is skipped for the
* current node, as well.
* TraversalFlag::Continue - traversal continues normally.
* TraversalFlag::Abort - traversal stops immediately.
*/
enum class TraversalFlag { Skip, Continue, Abort };
/*
* Iterator types to be specified in traversal function calls:
*
* ForwardIterator - for nodes using GetFirstChild() and GetNextSibling()
* ReverseIterator - for nodes using GetLastChild() and GetPrevSibling()
*/
class ForwardIterator {
public:
template <typename Node>
static Node* FirstChild(Node* n) {
return n->GetFirstChild();
}
template <typename Node>
static Node* NextSibling(Node* n) {
return n->GetNextSibling();
}
template <typename Node>
static Node FirstChild(Node n) {
return n.GetFirstChild();
}
template <typename Node>
static Node NextSibling(Node n) {
return n.GetNextSibling();
}
};
class ReverseIterator {
public:
template <typename Node>
static Node* FirstChild(Node* n) {
return n->GetLastChild();
}
template <typename Node>
static Node* NextSibling(Node* n) {
return n->GetPrevSibling();
}
template <typename Node>
static Node FirstChild(Node n) {
return n.GetLastChild();
}
template <typename Node>
static Node NextSibling(Node n) {
return n.GetPrevSibling();
}
};
/*
* Do a depth-first traversal of the tree rooted at |aRoot|, performing
* |aPreAction| before traversal of children and |aPostAction| after.
*
* Returns true if traversal aborted, false if continued normally. If
* TraversalFlag::Skip is returned in |aPreAction|, then |aPostAction|
* is not performed.
*
* |Iterator| should have static methods named NextSibling() and FirstChild()
* that accept an argument of type Node. For convenience, classes
* |ForwardIterator| and |ReverseIterator| are provided which implement these
* methods as GetNextSibling()/GetFirstChild() and
* GetPrevSibling()/GetLastChild(), respectively.
*/
template <typename Iterator, typename Node, typename PreAction,
typename PostAction>
static auto ForEachNode(Node aRoot, const PreAction& aPreAction,
const PostAction& aPostAction)
-> std::enable_if_t<
std::is_same_v<decltype(aPreAction(aRoot)), TraversalFlag> &&
std::is_same_v<decltype(aPostAction(aRoot)), TraversalFlag>,
bool> {
if (!aRoot) {
return false;
}
TraversalFlag result = aPreAction(aRoot);
if (result == TraversalFlag::Abort) {
return true;
}
if (result == TraversalFlag::Continue) {
for (Node child = Iterator::FirstChild(aRoot); child;
child = Iterator::NextSibling(child)) {
bool abort = ForEachNode<Iterator>(child, aPreAction, aPostAction);
if (abort) {
return true;
}
}
result = aPostAction(aRoot);
if (result == TraversalFlag::Abort) {
return true;
}
}
return false;
}
/*
* Do a depth-first traversal of the tree rooted at |aRoot|, performing
* |aPreAction| before traversal of children and |aPostAction| after.
*/
template <typename Iterator, typename Node, typename PreAction,
typename PostAction>
static auto ForEachNode(Node aRoot, const PreAction& aPreAction,
const PostAction& aPostAction)
-> std::enable_if_t<std::is_same_v<decltype(aPreAction(aRoot)), void> &&
std::is_same_v<decltype(aPostAction(aRoot)), void>,
void> {
if (!aRoot) {
return;
}
aPreAction(aRoot);
for (Node child = Iterator::FirstChild(aRoot); child;
child = Iterator::NextSibling(child)) {
ForEachNode<Iterator>(child, aPreAction, aPostAction);
}
aPostAction(aRoot);
}
/*
* ForEachNode pre-order traversal, using TraversalFlag.
*/
template <typename Iterator, typename Node, typename PreAction>
auto ForEachNode(Node aRoot, const PreAction& aPreAction) -> std::enable_if_t<
std::is_same_v<decltype(aPreAction(aRoot)), TraversalFlag>, bool> {
return ForEachNode<Iterator>(
aRoot, aPreAction, [](Node aNode) { return TraversalFlag::Continue; });
}
/*
* ForEachNode pre-order, not using TraversalFlag.
*/
template <typename Iterator, typename Node, typename PreAction>
auto ForEachNode(Node aRoot, const PreAction& aPreAction)
-> std::enable_if_t<std::is_same_v<decltype(aPreAction(aRoot)), void>,
void> {
ForEachNode<Iterator>(aRoot, aPreAction, [](Node aNode) {});
}
/*
* ForEachNode post-order traversal, using TraversalFlag.
*/
template <typename Iterator, typename Node, typename PostAction>
auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction)
-> std::enable_if_t<
std::is_same_v<decltype(aPostAction(aRoot)), TraversalFlag>, bool> {
return ForEachNode<Iterator>(
aRoot, [](Node aNode) { return TraversalFlag::Continue; }, aPostAction);
}
/*
* ForEachNode post-order, not using TraversalFlag.
*/
template <typename Iterator, typename Node, typename PostAction>
auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction)
-> std::enable_if_t<std::is_same_v<decltype(aPostAction(aRoot)), void>,
void> {
ForEachNode<Iterator>(
aRoot, [](Node aNode) {}, aPostAction);
}
/*
* Do a breadth-first search of the tree rooted at |aRoot|, and return the
* first visited node that satisfies |aCondition|, or nullptr if no such node
* was found.
*
* |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
* definition, but in addition to those, |Node| must be able to express a null
* value, returned from Node()
*/
template <typename Iterator, typename Node, typename Condition>
Node BreadthFirstSearch(Node aRoot, const Condition& aCondition) {
if (!aRoot) {
return Node();
}
std::queue<Node> queue;
queue.push(aRoot);
while (!queue.empty()) {
Node node = queue.front();
queue.pop();
if (aCondition(node)) {
return node;
}
for (Node child = Iterator::FirstChild(node); child;
child = Iterator::NextSibling(child)) {
queue.push(child);
}
}
return Node();
}
/*
* Do a pre-order, depth-first search of the tree rooted at |aRoot|, and
* return the first visited node that satisfies |aCondition|, or nullptr
* if no such node was found.
*
* |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
* definition, but in addition to those, |Node| must be able to express a null
* value, returned from Node().
*/
template <typename Iterator, typename Node, typename Condition>
Node DepthFirstSearch(Node aRoot, const Condition& aCondition) {
Node result = Node();
ForEachNode<Iterator>(aRoot, [&aCondition, &result](Node aNode) {
if (aCondition(aNode)) {
result = aNode;
return TraversalFlag::Abort;
}
return TraversalFlag::Continue;
});
return result;
}
/*
* Perform a post-order, depth-first search starting at aRoot.
*
* |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
* definition, but in addition to those, |Node| must be able to express a null
* value, returned from Node().
*/
template <typename Iterator, typename Node, typename Condition>
Node DepthFirstSearchPostOrder(Node aRoot, const Condition& aCondition) {
Node result = Node();
ForEachNodePostOrder<Iterator>(aRoot, [&aCondition, &result](Node aNode) {
if (aCondition(aNode)) {
result = aNode;
return TraversalFlag::Abort;
}
return TraversalFlag::Continue;
});
return result;
}
} // namespace layers
} // namespace mozilla
#endif // mozilla_layers_TreeTraversal_h