gfx/layers/TreeTraversal.h

   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