tor-browser

TreeTraversal.h (8323B)

---

/* -*- 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
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#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