[ tor-browser ].git.dasho

TestTreeTraversal.cpp (48622B)
      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 #include <vector>
      8 #include "mozilla/RefPtr.h"
      9 #include "gtest/gtest.h"
     10 #include "nsRegion.h"
     11 #include "nsRect.h"
     12 #include "TreeTraversal.h"
     13 #include <stack>
     14 #include <queue>
     15 
     16 using namespace mozilla::layers;
     17 using namespace mozilla;
     18 
     19 enum class SearchNodeType { Needle, Hay };
     20 enum class ForEachNodeType { Continue, Skip };
     21 
     22 template <class T>
     23 class TestNodeBase {
     24 public:
     25  NS_INLINE_DECL_REFCOUNTING(TestNodeBase<T>);
     26  explicit TestNodeBase(T aType, int aExpectedTraversalRank = -1);
     27  explicit TestNodeBase();
     28  void SetActualTraversalRank(int aRank);
     29  void SetValue(int aValue);
     30  void SetType(T aType);
     31  void SetRegion(nsRegion aRegion);
     32  int GetExpectedTraversalRank();
     33  int GetActualTraversalRank();
     34  int GetValue();
     35  T GetType();
     36  nsRegion GetRegion();
     37  virtual bool IsLeaf() = 0;
     38 
     39 private:
     40  MOZ_INIT_OUTSIDE_CTOR int mExpectedTraversalRank;
     41  MOZ_INIT_OUTSIDE_CTOR int mActualTraversalRank;
     42  MOZ_INIT_OUTSIDE_CTOR int mValue;
     43  MOZ_INIT_OUTSIDE_CTOR nsRegion mRegion;
     44  MOZ_INIT_OUTSIDE_CTOR T mType;
     45 
     46 protected:
     47  virtual ~TestNodeBase() = default;
     48 };
     49 
     50 template <class T>
     51 class TestNodeReverse : public TestNodeBase<T> {
     52 public:
     53  explicit TestNodeReverse(T aType, int aExpectedTraversalRank = -1);
     54  explicit TestNodeReverse();
     55  void AddChild(RefPtr<TestNodeReverse<T>> aNode);
     56  TestNodeReverse<T>* GetLastChild();
     57  TestNodeReverse<T>* GetPrevSibling();
     58  bool IsLeaf();
     59 
     60 private:
     61  void SetPrevSibling(RefPtr<TestNodeReverse<T>> aNode);
     62  void SetLastChild(RefPtr<TestNodeReverse<T>> aNode);
     63  RefPtr<TestNodeReverse<T>> mSiblingNode;
     64  RefPtr<TestNodeReverse<T>> mLastChildNode;
     65  ~TestNodeReverse() = default;
     66 };
     67 
     68 template <class T>
     69 class TestNodeForward : public TestNodeBase<T> {
     70 public:
     71  explicit TestNodeForward(T aType, int aExpectedTraversalRank = -1);
     72  explicit TestNodeForward();
     73  void AddChild(RefPtr<TestNodeForward<T>> aNode);
     74  TestNodeForward<T>* GetFirstChild();
     75  TestNodeForward<T>* GetNextSibling();
     76  bool IsLeaf();
     77 
     78 private:
     79  void SetNextSibling(RefPtr<TestNodeForward<T>> aNode);
     80  void SetLastChild(RefPtr<TestNodeForward<T>> aNode);
     81  void SetFirstChild(RefPtr<TestNodeForward<T>> aNode);
     82  RefPtr<TestNodeForward<T>> mSiblingNode = nullptr;
     83  RefPtr<TestNodeForward<T>> mFirstChildNode = nullptr;
     84  // Track last child to facilitate appending children
     85  RefPtr<TestNodeForward<T>> mLastChildNode = nullptr;
     86  ~TestNodeForward() = default;
     87 };
     88 
     89 template <class T>
     90 TestNodeReverse<T>::TestNodeReverse(T aType, int aExpectedTraversalRank)
     91    : TestNodeBase<T>(aType, aExpectedTraversalRank) {}
     92 
     93 template <class T>
     94 TestNodeReverse<T>::TestNodeReverse() : TestNodeBase<T>() {}
     95 
     96 template <class T>
     97 void TestNodeReverse<T>::SetLastChild(RefPtr<TestNodeReverse<T>> aNode) {
     98  mLastChildNode = aNode;
     99 }
    100 
    101 template <class T>
    102 void TestNodeReverse<T>::AddChild(RefPtr<TestNodeReverse<T>> aNode) {
    103  aNode->SetPrevSibling(mLastChildNode);
    104  SetLastChild(aNode);
    105 }
    106 
    107 template <class T>
    108 void TestNodeReverse<T>::SetPrevSibling(RefPtr<TestNodeReverse<T>> aNode) {
    109  mSiblingNode = aNode;
    110 }
    111 
    112 template <class T>
    113 TestNodeReverse<T>* TestNodeReverse<T>::GetLastChild() {
    114  return mLastChildNode;
    115 }
    116 
    117 template <class T>
    118 TestNodeReverse<T>* TestNodeReverse<T>::GetPrevSibling() {
    119  return mSiblingNode;
    120 }
    121 
    122 template <class T>
    123 bool TestNodeReverse<T>::IsLeaf() {
    124  return !mLastChildNode;
    125 }
    126 
    127 template <class T>
    128 TestNodeForward<T>::TestNodeForward(T aType, int aExpectedTraversalRank)
    129    : TestNodeBase<T>(aType, aExpectedTraversalRank) {}
    130 
    131 template <class T>
    132 TestNodeForward<T>::TestNodeForward() : TestNodeBase<T>() {}
    133 
    134 template <class T>
    135 void TestNodeForward<T>::AddChild(RefPtr<TestNodeForward<T>> aNode) {
    136  if (mFirstChildNode == nullptr) {
    137    SetFirstChild(aNode);
    138    SetLastChild(aNode);
    139  } else {
    140    mLastChildNode->SetNextSibling(aNode);
    141    SetLastChild(aNode);
    142  }
    143 }
    144 
    145 template <class T>
    146 void TestNodeForward<T>::SetLastChild(RefPtr<TestNodeForward<T>> aNode) {
    147  mLastChildNode = aNode;
    148 }
    149 
    150 template <class T>
    151 void TestNodeForward<T>::SetFirstChild(RefPtr<TestNodeForward<T>> aNode) {
    152  mFirstChildNode = aNode;
    153 }
    154 
    155 template <class T>
    156 void TestNodeForward<T>::SetNextSibling(RefPtr<TestNodeForward<T>> aNode) {
    157  mSiblingNode = aNode;
    158 }
    159 
    160 template <class T>
    161 bool TestNodeForward<T>::IsLeaf() {
    162  return !mFirstChildNode;
    163 }
    164 
    165 template <class T>
    166 TestNodeForward<T>* TestNodeForward<T>::GetFirstChild() {
    167  return mFirstChildNode;
    168 }
    169 
    170 template <class T>
    171 TestNodeForward<T>* TestNodeForward<T>::GetNextSibling() {
    172  return mSiblingNode;
    173 }
    174 
    175 template <class T>
    176 TestNodeBase<T>::TestNodeBase(T aType, int aExpectedTraversalRank)
    177    : mExpectedTraversalRank(aExpectedTraversalRank),
    178      mActualTraversalRank(-1),
    179      mType(aType) {}
    180 
    181 template <class T>
    182 TestNodeBase<T>::TestNodeBase() = default;
    183 
    184 template <class T>
    185 int TestNodeBase<T>::GetActualTraversalRank() {
    186  return mActualTraversalRank;
    187 }
    188 
    189 template <class T>
    190 void TestNodeBase<T>::SetActualTraversalRank(int aRank) {
    191  mActualTraversalRank = aRank;
    192 }
    193 
    194 template <class T>
    195 int TestNodeBase<T>::GetExpectedTraversalRank() {
    196  return mExpectedTraversalRank;
    197 }
    198 
    199 template <class T>
    200 T TestNodeBase<T>::GetType() {
    201  return mType;
    202 }
    203 
    204 template <class T>
    205 void TestNodeBase<T>::SetType(T aType) {
    206  mType = aType;
    207 }
    208 
    209 template <class T>
    210 nsRegion TestNodeBase<T>::GetRegion() {
    211  return mRegion;
    212 }
    213 
    214 template <class T>
    215 void TestNodeBase<T>::SetRegion(nsRegion aRegion) {
    216  mRegion = aRegion;
    217 }
    218 
    219 template <class T>
    220 int TestNodeBase<T>::GetValue() {
    221  return mValue;
    222 }
    223 
    224 template <class T>
    225 void TestNodeBase<T>::SetValue(int aValue) {
    226  mValue = aValue;
    227 }
    228 
    229 typedef TestNodeBase<SearchNodeType> SearchTestNode;
    230 typedef TestNodeBase<ForEachNodeType> ForEachTestNode;
    231 typedef TestNodeReverse<SearchNodeType> SearchTestNodeReverse;
    232 typedef TestNodeReverse<ForEachNodeType> ForEachTestNodeReverse;
    233 typedef TestNodeForward<SearchNodeType> SearchTestNodeForward;
    234 typedef TestNodeForward<ForEachNodeType> ForEachTestNodeForward;
    235 
    236 TEST(TreeTraversal, DepthFirstSearchNull)
    237 {
    238  RefPtr<SearchTestNodeReverse> nullNode;
    239  RefPtr<SearchTestNodeReverse> result =
    240      DepthFirstSearch<layers::ReverseIterator>(
    241          nullNode.get(), [](SearchTestNodeReverse* aNode) {
    242            return aNode->GetType() == SearchNodeType::Needle;
    243          });
    244  ASSERT_EQ(result.get(), nullptr)
    245      << "Null root did not return null search result.";
    246 }
    247 
    248 TEST(TreeTraversal, DepthFirstSearchValueExists)
    249 {
    250  int visitCount = 0;
    251  size_t expectedNeedleTraversalRank = 7;
    252  RefPtr<SearchTestNodeForward> needleNode;
    253  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
    254  nodeList.reserve(10);
    255  for (size_t i = 0; i < 10; i++) {
    256    if (i == expectedNeedleTraversalRank) {
    257      needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
    258      nodeList.push_back(needleNode);
    259    } else if (i < expectedNeedleTraversalRank) {
    260      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
    261    } else {
    262      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
    263    }
    264  }
    265 
    266  RefPtr<SearchTestNodeForward> root = nodeList[0];
    267  nodeList[0]->AddChild(nodeList[1]);
    268  nodeList[0]->AddChild(nodeList[4]);
    269  nodeList[1]->AddChild(nodeList[2]);
    270  nodeList[1]->AddChild(nodeList[3]);
    271  nodeList[4]->AddChild(nodeList[5]);
    272  nodeList[4]->AddChild(nodeList[6]);
    273  nodeList[6]->AddChild(nodeList[7]);
    274  nodeList[7]->AddChild(nodeList[8]);
    275  nodeList[7]->AddChild(nodeList[9]);
    276 
    277  RefPtr<SearchTestNodeForward> foundNode =
    278      DepthFirstSearch<layers::ForwardIterator>(
    279          root.get(), [&visitCount](SearchTestNodeForward* aNode) {
    280            aNode->SetActualTraversalRank(visitCount);
    281            visitCount++;
    282            return aNode->GetType() == SearchNodeType::Needle;
    283          });
    284 
    285  for (size_t i = 0; i < nodeList.size(); i++) {
    286    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    287              nodeList[i]->GetActualTraversalRank())
    288        << "Node at index " << i << " was hit out of order.";
    289  }
    290 
    291  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
    292  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
    293      << "Returned node does not match expected value (something odd "
    294         "happened).";
    295 }
    296 
    297 TEST(TreeTraversal, DepthFirstSearchValueExistsReverse)
    298 {
    299  int visitCount = 0;
    300  size_t expectedNeedleTraversalRank = 7;
    301  RefPtr<SearchTestNodeReverse> needleNode;
    302  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
    303  nodeList.reserve(10);
    304  for (size_t i = 0; i < 10; i++) {
    305    if (i == expectedNeedleTraversalRank) {
    306      needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
    307      nodeList.push_back(needleNode);
    308    } else if (i < expectedNeedleTraversalRank) {
    309      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
    310    } else {
    311      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
    312    }
    313  }
    314 
    315  RefPtr<SearchTestNodeReverse> root = nodeList[0];
    316  nodeList[0]->AddChild(nodeList[4]);
    317  nodeList[0]->AddChild(nodeList[1]);
    318  nodeList[1]->AddChild(nodeList[3]);
    319  nodeList[1]->AddChild(nodeList[2]);
    320  nodeList[4]->AddChild(nodeList[6]);
    321  nodeList[4]->AddChild(nodeList[5]);
    322  nodeList[6]->AddChild(nodeList[7]);
    323  nodeList[7]->AddChild(nodeList[9]);
    324  nodeList[7]->AddChild(nodeList[8]);
    325 
    326  RefPtr<SearchTestNodeReverse> foundNode =
    327      DepthFirstSearch<layers::ReverseIterator>(
    328          root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
    329            aNode->SetActualTraversalRank(visitCount);
    330            visitCount++;
    331            return aNode->GetType() == SearchNodeType::Needle;
    332          });
    333 
    334  for (size_t i = 0; i < nodeList.size(); i++) {
    335    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    336              nodeList[i]->GetActualTraversalRank())
    337        << "Node at index " << i << " was hit out of order.";
    338  }
    339 
    340  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
    341  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
    342      << "Returned node does not match expected value (something odd "
    343         "happened).";
    344 }
    345 
    346 TEST(TreeTraversal, DepthFirstSearchRootIsNeedle)
    347 {
    348  RefPtr<SearchTestNodeReverse> root =
    349      new SearchTestNodeReverse(SearchNodeType::Needle, 0);
    350  RefPtr<SearchTestNodeReverse> childNode1 =
    351      new SearchTestNodeReverse(SearchNodeType::Hay);
    352  RefPtr<SearchTestNodeReverse> childNode2 =
    353      new SearchTestNodeReverse(SearchNodeType::Hay);
    354  int visitCount = 0;
    355  RefPtr<SearchTestNodeReverse> result =
    356      DepthFirstSearch<layers::ReverseIterator>(
    357          root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
    358            aNode->SetActualTraversalRank(visitCount);
    359            visitCount++;
    360            return aNode->GetType() == SearchNodeType::Needle;
    361          });
    362  ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
    363  ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
    364      << "Search starting at needle did not return needle.";
    365  ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
    366            childNode1->GetActualTraversalRank())
    367      << "Search starting at needle continued past needle.";
    368  ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
    369            childNode2->GetActualTraversalRank())
    370      << "Search starting at needle continued past needle.";
    371 }
    372 
    373 TEST(TreeTraversal, DepthFirstSearchValueDoesNotExist)
    374 {
    375  int visitCount = 0;
    376  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
    377  nodeList.reserve(10);
    378  for (int i = 0; i < 10; i++) {
    379    nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
    380  }
    381 
    382  RefPtr<SearchTestNodeForward> root = nodeList[0];
    383  nodeList[0]->AddChild(nodeList[1]);
    384  nodeList[0]->AddChild(nodeList[4]);
    385  nodeList[1]->AddChild(nodeList[2]);
    386  nodeList[1]->AddChild(nodeList[3]);
    387  nodeList[4]->AddChild(nodeList[5]);
    388  nodeList[4]->AddChild(nodeList[6]);
    389  nodeList[6]->AddChild(nodeList[7]);
    390  nodeList[7]->AddChild(nodeList[8]);
    391  nodeList[7]->AddChild(nodeList[9]);
    392 
    393  RefPtr<SearchTestNodeForward> foundNode =
    394      DepthFirstSearch<layers::ForwardIterator>(
    395          root.get(), [&visitCount](SearchTestNodeForward* aNode) {
    396            aNode->SetActualTraversalRank(visitCount);
    397            visitCount++;
    398            return aNode->GetType() == SearchNodeType::Needle;
    399          });
    400 
    401  for (int i = 0; i < 10; i++) {
    402    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    403              nodeList[i]->GetActualTraversalRank())
    404        << "Node at index " << i << " was hit out of order.";
    405  }
    406 
    407  ASSERT_EQ(foundNode.get(), nullptr)
    408      << "Search found something that should not exist.";
    409 }
    410 
    411 TEST(TreeTraversal, DepthFirstSearchValueDoesNotExistReverse)
    412 {
    413  int visitCount = 0;
    414  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
    415  nodeList.reserve(10);
    416  for (int i = 0; i < 10; i++) {
    417    nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
    418  }
    419 
    420  RefPtr<SearchTestNodeReverse> root = nodeList[0];
    421  nodeList[0]->AddChild(nodeList[4]);
    422  nodeList[0]->AddChild(nodeList[1]);
    423  nodeList[1]->AddChild(nodeList[3]);
    424  nodeList[1]->AddChild(nodeList[2]);
    425  nodeList[4]->AddChild(nodeList[6]);
    426  nodeList[4]->AddChild(nodeList[5]);
    427  nodeList[6]->AddChild(nodeList[7]);
    428  nodeList[7]->AddChild(nodeList[9]);
    429  nodeList[7]->AddChild(nodeList[8]);
    430 
    431  RefPtr<SearchTestNodeReverse> foundNode =
    432      DepthFirstSearch<layers::ReverseIterator>(
    433          root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
    434            aNode->SetActualTraversalRank(visitCount);
    435            visitCount++;
    436            return aNode->GetType() == SearchNodeType::Needle;
    437          });
    438 
    439  for (int i = 0; i < 10; i++) {
    440    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    441              nodeList[i]->GetActualTraversalRank())
    442        << "Node at index " << i << " was hit out of order.";
    443  }
    444 
    445  ASSERT_EQ(foundNode.get(), nullptr)
    446      << "Search found something that should not exist.";
    447 }
    448 
    449 TEST(TreeTraversal, DepthFirstSearchPostOrderNull)
    450 {
    451  RefPtr<SearchTestNodeReverse> nullNode;
    452  RefPtr<SearchTestNodeReverse> result =
    453      DepthFirstSearchPostOrder<layers::ReverseIterator>(
    454          nullNode.get(), [](SearchTestNodeReverse* aNode) {
    455            return aNode->GetType() == SearchNodeType::Needle;
    456          });
    457  ASSERT_EQ(result.get(), nullptr)
    458      << "Null root did not return null search result.";
    459 }
    460 
    461 TEST(TreeTraversal, DepthFirstSearchPostOrderValueExists)
    462 {
    463  int visitCount = 0;
    464  size_t expectedNeedleTraversalRank = 7;
    465  RefPtr<SearchTestNodeForward> needleNode;
    466  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
    467  for (size_t i = 0; i < 10; i++) {
    468    if (i == expectedNeedleTraversalRank) {
    469      needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
    470      nodeList.push_back(needleNode);
    471    } else if (i < expectedNeedleTraversalRank) {
    472      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
    473    } else {
    474      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
    475    }
    476  }
    477 
    478  RefPtr<SearchTestNodeForward> root = nodeList[9];
    479  nodeList[9]->AddChild(nodeList[2]);
    480  nodeList[9]->AddChild(nodeList[8]);
    481  nodeList[2]->AddChild(nodeList[0]);
    482  nodeList[2]->AddChild(nodeList[1]);
    483  nodeList[8]->AddChild(nodeList[6]);
    484  nodeList[8]->AddChild(nodeList[7]);
    485  nodeList[6]->AddChild(nodeList[5]);
    486  nodeList[5]->AddChild(nodeList[3]);
    487  nodeList[5]->AddChild(nodeList[4]);
    488 
    489  RefPtr<SearchTestNodeForward> foundNode =
    490      DepthFirstSearchPostOrder<layers::ForwardIterator>(
    491          root.get(), [&visitCount](SearchTestNodeForward* aNode) {
    492            aNode->SetActualTraversalRank(visitCount);
    493            visitCount++;
    494            return aNode->GetType() == SearchNodeType::Needle;
    495          });
    496 
    497  for (size_t i = 0; i < nodeList.size(); i++) {
    498    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    499              nodeList[i]->GetActualTraversalRank())
    500        << "Node at index " << i << " was hit out of order.";
    501  }
    502 
    503  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
    504  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
    505      << "Returned node does not match expected value (something odd "
    506         "happened).";
    507 }
    508 
    509 TEST(TreeTraversal, DepthFirstSearchPostOrderValueExistsReverse)
    510 {
    511  int visitCount = 0;
    512  size_t expectedNeedleTraversalRank = 7;
    513  RefPtr<SearchTestNodeReverse> needleNode;
    514  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
    515  for (size_t i = 0; i < 10; i++) {
    516    if (i == expectedNeedleTraversalRank) {
    517      needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
    518      nodeList.push_back(needleNode);
    519    } else if (i < expectedNeedleTraversalRank) {
    520      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
    521    } else {
    522      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
    523    }
    524  }
    525 
    526  RefPtr<SearchTestNodeReverse> root = nodeList[9];
    527  nodeList[9]->AddChild(nodeList[8]);
    528  nodeList[9]->AddChild(nodeList[2]);
    529  nodeList[2]->AddChild(nodeList[1]);
    530  nodeList[2]->AddChild(nodeList[0]);
    531  nodeList[8]->AddChild(nodeList[7]);
    532  nodeList[8]->AddChild(nodeList[6]);
    533  nodeList[6]->AddChild(nodeList[5]);
    534  nodeList[5]->AddChild(nodeList[4]);
    535  nodeList[5]->AddChild(nodeList[3]);
    536 
    537  RefPtr<SearchTestNodeReverse> foundNode =
    538      DepthFirstSearchPostOrder<layers::ReverseIterator>(
    539          root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
    540            aNode->SetActualTraversalRank(visitCount);
    541            visitCount++;
    542            return aNode->GetType() == SearchNodeType::Needle;
    543          });
    544 
    545  for (size_t i = 0; i < nodeList.size(); i++) {
    546    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    547              nodeList[i]->GetActualTraversalRank())
    548        << "Node at index " << i << " was hit out of order.";
    549  }
    550 
    551  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
    552  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
    553      << "Returned node does not match expected value (something odd "
    554         "happened).";
    555 }
    556 
    557 TEST(TreeTraversal, DepthFirstSearchPostOrderRootIsNeedle)
    558 {
    559  RefPtr<SearchTestNodeReverse> root =
    560      new SearchTestNodeReverse(SearchNodeType::Needle, 0);
    561  RefPtr<SearchTestNodeReverse> childNode1 =
    562      new SearchTestNodeReverse(SearchNodeType::Hay);
    563  RefPtr<SearchTestNodeReverse> childNode2 =
    564      new SearchTestNodeReverse(SearchNodeType::Hay);
    565  int visitCount = 0;
    566  RefPtr<SearchTestNodeReverse> result =
    567      DepthFirstSearchPostOrder<layers::ReverseIterator>(
    568          root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
    569            aNode->SetActualTraversalRank(visitCount);
    570            visitCount++;
    571            return aNode->GetType() == SearchNodeType::Needle;
    572          });
    573  ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
    574  ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
    575      << "Search starting at needle did not return needle.";
    576  ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
    577            childNode1->GetActualTraversalRank())
    578      << "Search starting at needle continued past needle.";
    579  ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
    580            childNode2->GetActualTraversalRank())
    581      << "Search starting at needle continued past needle.";
    582 }
    583 
    584 TEST(TreeTraversal, DepthFirstSearchPostOrderValueDoesNotExist)
    585 {
    586  int visitCount = 0;
    587  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
    588  nodeList.reserve(10);
    589  for (int i = 0; i < 10; i++) {
    590    nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
    591  }
    592 
    593  RefPtr<SearchTestNodeForward> root = nodeList[9];
    594  nodeList[9]->AddChild(nodeList[2]);
    595  nodeList[9]->AddChild(nodeList[8]);
    596  nodeList[2]->AddChild(nodeList[0]);
    597  nodeList[2]->AddChild(nodeList[1]);
    598  nodeList[8]->AddChild(nodeList[6]);
    599  nodeList[8]->AddChild(nodeList[7]);
    600  nodeList[6]->AddChild(nodeList[5]);
    601  nodeList[5]->AddChild(nodeList[3]);
    602  nodeList[5]->AddChild(nodeList[4]);
    603 
    604  RefPtr<SearchTestNodeForward> foundNode =
    605      DepthFirstSearchPostOrder<layers::ForwardIterator>(
    606          root.get(), [&visitCount](SearchTestNodeForward* aNode) {
    607            aNode->SetActualTraversalRank(visitCount);
    608            visitCount++;
    609            return aNode->GetType() == SearchNodeType::Needle;
    610          });
    611 
    612  for (int i = 0; i < 10; i++) {
    613    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    614              nodeList[i]->GetActualTraversalRank())
    615        << "Node at index " << i << " was hit out of order.";
    616  }
    617 
    618  ASSERT_EQ(foundNode.get(), nullptr)
    619      << "Search found something that should not exist.";
    620 }
    621 
    622 TEST(TreeTraversal, DepthFirstSearchPostOrderValueDoesNotExistReverse)
    623 {
    624  int visitCount = 0;
    625  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
    626  nodeList.reserve(10);
    627  for (int i = 0; i < 10; i++) {
    628    nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
    629  }
    630 
    631  RefPtr<SearchTestNodeReverse> root = nodeList[9];
    632  nodeList[9]->AddChild(nodeList[8]);
    633  nodeList[9]->AddChild(nodeList[2]);
    634  nodeList[2]->AddChild(nodeList[1]);
    635  nodeList[2]->AddChild(nodeList[0]);
    636  nodeList[8]->AddChild(nodeList[7]);
    637  nodeList[8]->AddChild(nodeList[6]);
    638  nodeList[6]->AddChild(nodeList[5]);
    639  nodeList[5]->AddChild(nodeList[4]);
    640  nodeList[5]->AddChild(nodeList[3]);
    641 
    642  RefPtr<SearchTestNodeReverse> foundNode =
    643      DepthFirstSearchPostOrder<layers::ReverseIterator>(
    644          root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
    645            aNode->SetActualTraversalRank(visitCount);
    646            visitCount++;
    647            return aNode->GetType() == SearchNodeType::Needle;
    648          });
    649 
    650  for (int i = 0; i < 10; i++) {
    651    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    652              nodeList[i]->GetActualTraversalRank())
    653        << "Node at index " << i << " was hit out of order.";
    654  }
    655 
    656  ASSERT_EQ(foundNode.get(), nullptr)
    657      << "Search found something that should not exist.";
    658 }
    659 
    660 TEST(TreeTraversal, BreadthFirstSearchNull)
    661 {
    662  RefPtr<SearchTestNodeReverse> nullNode;
    663  RefPtr<SearchTestNodeReverse> result =
    664      BreadthFirstSearch<layers::ReverseIterator>(
    665          nullNode.get(), [](SearchTestNodeReverse* aNode) {
    666            return aNode->GetType() == SearchNodeType::Needle;
    667          });
    668  ASSERT_EQ(result.get(), nullptr)
    669      << "Null root did not return null search result.";
    670 }
    671 
    672 TEST(TreeTraversal, BreadthFirstSearchRootIsNeedle)
    673 {
    674  RefPtr<SearchTestNodeReverse> root =
    675      new SearchTestNodeReverse(SearchNodeType::Needle, 0);
    676  RefPtr<SearchTestNodeReverse> childNode1 =
    677      new SearchTestNodeReverse(SearchNodeType::Hay);
    678  RefPtr<SearchTestNodeReverse> childNode2 =
    679      new SearchTestNodeReverse(SearchNodeType::Hay);
    680  int visitCount = 0;
    681  RefPtr<SearchTestNodeReverse> result =
    682      BreadthFirstSearch<layers::ReverseIterator>(
    683          root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
    684            aNode->SetActualTraversalRank(visitCount);
    685            visitCount++;
    686            return aNode->GetType() == SearchNodeType::Needle;
    687          });
    688  ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
    689  ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
    690      << "Search starting at needle did not return needle.";
    691  ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
    692            childNode1->GetActualTraversalRank())
    693      << "Search starting at needle continued past needle.";
    694  ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
    695            childNode2->GetActualTraversalRank())
    696      << "Search starting at needle continued past needle.";
    697 }
    698 
    699 TEST(TreeTraversal, BreadthFirstSearchValueExists)
    700 {
    701  int visitCount = 0;
    702  size_t expectedNeedleTraversalRank = 7;
    703  RefPtr<SearchTestNodeForward> needleNode;
    704  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
    705  nodeList.reserve(10);
    706  for (size_t i = 0; i < 10; i++) {
    707    if (i == expectedNeedleTraversalRank) {
    708      needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
    709      nodeList.push_back(needleNode);
    710    } else if (i < expectedNeedleTraversalRank) {
    711      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
    712    } else {
    713      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
    714    }
    715  }
    716 
    717  RefPtr<SearchTestNodeForward> root = nodeList[0];
    718  nodeList[0]->AddChild(nodeList[1]);
    719  nodeList[0]->AddChild(nodeList[2]);
    720  nodeList[1]->AddChild(nodeList[3]);
    721  nodeList[1]->AddChild(nodeList[4]);
    722  nodeList[2]->AddChild(nodeList[5]);
    723  nodeList[2]->AddChild(nodeList[6]);
    724  nodeList[6]->AddChild(nodeList[7]);
    725  nodeList[7]->AddChild(nodeList[8]);
    726  nodeList[7]->AddChild(nodeList[9]);
    727 
    728  RefPtr<SearchTestNodeForward> foundNode =
    729      BreadthFirstSearch<layers::ForwardIterator>(
    730          root.get(), [&visitCount](SearchTestNodeForward* aNode) {
    731            aNode->SetActualTraversalRank(visitCount);
    732            visitCount++;
    733            return aNode->GetType() == SearchNodeType::Needle;
    734          });
    735 
    736  for (size_t i = 0; i < nodeList.size(); i++) {
    737    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    738              nodeList[i]->GetActualTraversalRank())
    739        << "Node at index " << i << " was hit out of order.";
    740  }
    741 
    742  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
    743  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
    744      << "Returned node does not match expected value (something odd "
    745         "happened).";
    746 }
    747 
    748 TEST(TreeTraversal, BreadthFirstSearchValueExistsReverse)
    749 {
    750  int visitCount = 0;
    751  size_t expectedNeedleTraversalRank = 7;
    752  RefPtr<SearchTestNodeReverse> needleNode;
    753  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
    754  nodeList.reserve(10);
    755  for (size_t i = 0; i < 10; i++) {
    756    if (i == expectedNeedleTraversalRank) {
    757      needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
    758      nodeList.push_back(needleNode);
    759    } else if (i < expectedNeedleTraversalRank) {
    760      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
    761    } else {
    762      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
    763    }
    764  }
    765 
    766  RefPtr<SearchTestNodeReverse> root = nodeList[0];
    767  nodeList[0]->AddChild(nodeList[2]);
    768  nodeList[0]->AddChild(nodeList[1]);
    769  nodeList[1]->AddChild(nodeList[4]);
    770  nodeList[1]->AddChild(nodeList[3]);
    771  nodeList[2]->AddChild(nodeList[6]);
    772  nodeList[2]->AddChild(nodeList[5]);
    773  nodeList[6]->AddChild(nodeList[7]);
    774  nodeList[7]->AddChild(nodeList[9]);
    775  nodeList[7]->AddChild(nodeList[8]);
    776 
    777  RefPtr<SearchTestNodeReverse> foundNode =
    778      BreadthFirstSearch<layers::ReverseIterator>(
    779          root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
    780            aNode->SetActualTraversalRank(visitCount);
    781            visitCount++;
    782            return aNode->GetType() == SearchNodeType::Needle;
    783          });
    784 
    785  for (size_t i = 0; i < nodeList.size(); i++) {
    786    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    787              nodeList[i]->GetActualTraversalRank())
    788        << "Node at index " << i << " was hit out of order.";
    789  }
    790 
    791  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
    792  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
    793      << "Returned node does not match expected value (something odd "
    794         "happened).";
    795 }
    796 
    797 TEST(TreeTraversal, BreadthFirstSearchValueDoesNotExist)
    798 {
    799  int visitCount = 0;
    800  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
    801  nodeList.reserve(10);
    802  for (int i = 0; i < 10; i++) {
    803    nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
    804  }
    805 
    806  RefPtr<SearchTestNodeForward> root = nodeList[0];
    807  nodeList[0]->AddChild(nodeList[1]);
    808  nodeList[0]->AddChild(nodeList[2]);
    809  nodeList[1]->AddChild(nodeList[3]);
    810  nodeList[1]->AddChild(nodeList[4]);
    811  nodeList[2]->AddChild(nodeList[5]);
    812  nodeList[2]->AddChild(nodeList[6]);
    813  nodeList[6]->AddChild(nodeList[7]);
    814  nodeList[7]->AddChild(nodeList[8]);
    815  nodeList[7]->AddChild(nodeList[9]);
    816 
    817  RefPtr<SearchTestNodeForward> foundNode =
    818      BreadthFirstSearch<layers::ForwardIterator>(
    819          root.get(), [&visitCount](SearchTestNodeForward* aNode) {
    820            aNode->SetActualTraversalRank(visitCount);
    821            visitCount++;
    822            return aNode->GetType() == SearchNodeType::Needle;
    823          });
    824 
    825  for (size_t i = 0; i < nodeList.size(); i++) {
    826    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    827              nodeList[i]->GetActualTraversalRank())
    828        << "Node at index " << i << " was hit out of order.";
    829  }
    830 
    831  ASSERT_EQ(foundNode.get(), nullptr)
    832      << "Search found something that should not exist.";
    833 }
    834 
    835 TEST(TreeTraversal, BreadthFirstSearchValueDoesNotExistReverse)
    836 {
    837  int visitCount = 0;
    838  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
    839  nodeList.reserve(10);
    840  for (int i = 0; i < 10; i++) {
    841    nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
    842  }
    843 
    844  RefPtr<SearchTestNodeReverse> root = nodeList[0];
    845  nodeList[0]->AddChild(nodeList[2]);
    846  nodeList[0]->AddChild(nodeList[1]);
    847  nodeList[1]->AddChild(nodeList[4]);
    848  nodeList[1]->AddChild(nodeList[3]);
    849  nodeList[2]->AddChild(nodeList[6]);
    850  nodeList[2]->AddChild(nodeList[5]);
    851  nodeList[6]->AddChild(nodeList[7]);
    852  nodeList[7]->AddChild(nodeList[9]);
    853  nodeList[7]->AddChild(nodeList[8]);
    854 
    855  RefPtr<SearchTestNodeReverse> foundNode =
    856      BreadthFirstSearch<layers::ReverseIterator>(
    857          root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
    858            aNode->SetActualTraversalRank(visitCount);
    859            visitCount++;
    860            return aNode->GetType() == SearchNodeType::Needle;
    861          });
    862 
    863  for (size_t i = 0; i < nodeList.size(); i++) {
    864    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    865              nodeList[i]->GetActualTraversalRank())
    866        << "Node at index " << i << " was hit out of order.";
    867  }
    868 
    869  ASSERT_EQ(foundNode.get(), nullptr)
    870      << "Search found something that should not exist.";
    871 }
    872 
    873 TEST(TreeTraversal, ForEachNodeNullStillRuns)
    874 {
    875  RefPtr<ForEachTestNodeReverse> nullNode;
    876  ForEachNode<layers::ReverseIterator>(
    877      nullNode.get(),
    878      [](ForEachTestNodeReverse* aNode) { return TraversalFlag::Continue; });
    879 }
    880 
    881 TEST(TreeTraversal, ForEachNodeAllEligible)
    882 {
    883  std::vector<RefPtr<ForEachTestNodeForward>> nodeList;
    884  int visitCount = 0;
    885  nodeList.reserve(10);
    886  for (int i = 0; i < 10; i++) {
    887    nodeList.push_back(
    888        new ForEachTestNodeForward(ForEachNodeType::Continue, i));
    889  }
    890 
    891  RefPtr<ForEachTestNodeForward> root = nodeList[0];
    892  nodeList[0]->AddChild(nodeList[1]);
    893  nodeList[0]->AddChild(nodeList[4]);
    894  nodeList[1]->AddChild(nodeList[2]);
    895  nodeList[1]->AddChild(nodeList[3]);
    896  nodeList[4]->AddChild(nodeList[5]);
    897  nodeList[4]->AddChild(nodeList[6]);
    898  nodeList[6]->AddChild(nodeList[7]);
    899  nodeList[7]->AddChild(nodeList[8]);
    900  nodeList[7]->AddChild(nodeList[9]);
    901 
    902  ForEachNode<layers::ForwardIterator>(
    903      root.get(), [&visitCount](ForEachTestNodeForward* aNode) {
    904        aNode->SetActualTraversalRank(visitCount);
    905        visitCount++;
    906        return aNode->GetType() == ForEachNodeType::Continue
    907                   ? TraversalFlag::Continue
    908                   : TraversalFlag::Skip;
    909      });
    910 
    911  for (size_t i = 0; i < nodeList.size(); i++) {
    912    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    913              nodeList[i]->GetActualTraversalRank())
    914        << "Node at index " << i << " was hit out of order.";
    915  }
    916 }
    917 
    918 TEST(TreeTraversal, ForEachNodeAllEligibleReverse)
    919 {
    920  std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
    921  int visitCount = 0;
    922  nodeList.reserve(10);
    923  for (int i = 0; i < 10; i++) {
    924    nodeList.push_back(
    925        new ForEachTestNodeReverse(ForEachNodeType::Continue, i));
    926  }
    927 
    928  RefPtr<ForEachTestNodeReverse> root = nodeList[0];
    929  nodeList[0]->AddChild(nodeList[4]);
    930  nodeList[0]->AddChild(nodeList[1]);
    931  nodeList[1]->AddChild(nodeList[3]);
    932  nodeList[1]->AddChild(nodeList[2]);
    933  nodeList[4]->AddChild(nodeList[6]);
    934  nodeList[4]->AddChild(nodeList[5]);
    935  nodeList[6]->AddChild(nodeList[7]);
    936  nodeList[7]->AddChild(nodeList[9]);
    937  nodeList[7]->AddChild(nodeList[8]);
    938 
    939  ForEachNode<layers::ReverseIterator>(
    940      root.get(), [&visitCount](ForEachTestNodeReverse* aNode) {
    941        aNode->SetActualTraversalRank(visitCount);
    942        visitCount++;
    943        return aNode->GetType() == ForEachNodeType::Continue
    944                   ? TraversalFlag::Continue
    945                   : TraversalFlag::Skip;
    946      });
    947 
    948  for (size_t i = 0; i < nodeList.size(); i++) {
    949    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
    950              nodeList[i]->GetActualTraversalRank())
    951        << "Node at index " << i << " was hit out of order.";
    952  }
    953 }
    954 
    955 TEST(TreeTraversal, ForEachNodeSomeIneligibleNodes)
    956 {
    957  std::vector<RefPtr<ForEachTestNodeForward>> expectedVisitedNodeList;
    958  std::vector<RefPtr<ForEachTestNodeForward>> expectedSkippedNodeList;
    959  int visitCount = 0;
    960 
    961  expectedVisitedNodeList.push_back(
    962      new ForEachTestNodeForward(ForEachNodeType::Continue, 0));
    963  expectedVisitedNodeList.push_back(
    964      new ForEachTestNodeForward(ForEachNodeType::Skip, 1));
    965  expectedVisitedNodeList.push_back(
    966      new ForEachTestNodeForward(ForEachNodeType::Continue, 2));
    967  expectedVisitedNodeList.push_back(
    968      new ForEachTestNodeForward(ForEachNodeType::Skip, 3));
    969 
    970  expectedSkippedNodeList.push_back(
    971      new ForEachTestNodeForward(ForEachNodeType::Continue));
    972  expectedSkippedNodeList.push_back(
    973      new ForEachTestNodeForward(ForEachNodeType::Continue));
    974  expectedSkippedNodeList.push_back(
    975      new ForEachTestNodeForward(ForEachNodeType::Skip));
    976  expectedSkippedNodeList.push_back(
    977      new ForEachTestNodeForward(ForEachNodeType::Skip));
    978 
    979  RefPtr<ForEachTestNodeForward> root = expectedVisitedNodeList[0];
    980  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[1]);
    981  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[2]);
    982  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[0]);
    983  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[1]);
    984  expectedVisitedNodeList[2]->AddChild(expectedVisitedNodeList[3]);
    985  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[2]);
    986  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[3]);
    987 
    988  ForEachNode<layers::ForwardIterator>(
    989      root.get(), [&visitCount](ForEachTestNodeForward* aNode) {
    990        aNode->SetActualTraversalRank(visitCount);
    991        visitCount++;
    992        return aNode->GetType() == ForEachNodeType::Continue
    993                   ? TraversalFlag::Continue
    994                   : TraversalFlag::Skip;
    995      });
    996 
    997  for (size_t i = 0; i < expectedVisitedNodeList.size(); i++) {
    998    ASSERT_EQ(expectedVisitedNodeList[i]->GetExpectedTraversalRank(),
    999              expectedVisitedNodeList[i]->GetActualTraversalRank())
   1000        << "Node at index " << i << " was hit out of order.";
   1001  }
   1002 
   1003  for (size_t i = 0; i < expectedSkippedNodeList.size(); i++) {
   1004    ASSERT_EQ(expectedSkippedNodeList[i]->GetExpectedTraversalRank(),
   1005              expectedSkippedNodeList[i]->GetActualTraversalRank())
   1006        << "Node at index " << i << "was not expected to be hit.";
   1007  }
   1008 }
   1009 
   1010 TEST(TreeTraversal, ForEachNodeSomeIneligibleNodesReverse)
   1011 {
   1012  std::vector<RefPtr<ForEachTestNodeReverse>> expectedVisitedNodeList;
   1013  std::vector<RefPtr<ForEachTestNodeReverse>> expectedSkippedNodeList;
   1014  int visitCount = 0;
   1015 
   1016  expectedVisitedNodeList.push_back(
   1017      new ForEachTestNodeReverse(ForEachNodeType::Continue, 0));
   1018  expectedVisitedNodeList.push_back(
   1019      new ForEachTestNodeReverse(ForEachNodeType::Skip, 1));
   1020  expectedVisitedNodeList.push_back(
   1021      new ForEachTestNodeReverse(ForEachNodeType::Continue, 2));
   1022  expectedVisitedNodeList.push_back(
   1023      new ForEachTestNodeReverse(ForEachNodeType::Skip, 3));
   1024 
   1025  expectedSkippedNodeList.push_back(
   1026      new ForEachTestNodeReverse(ForEachNodeType::Continue));
   1027  expectedSkippedNodeList.push_back(
   1028      new ForEachTestNodeReverse(ForEachNodeType::Continue));
   1029  expectedSkippedNodeList.push_back(
   1030      new ForEachTestNodeReverse(ForEachNodeType::Skip));
   1031  expectedSkippedNodeList.push_back(
   1032      new ForEachTestNodeReverse(ForEachNodeType::Skip));
   1033 
   1034  RefPtr<ForEachTestNodeReverse> root = expectedVisitedNodeList[0];
   1035  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[2]);
   1036  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[1]);
   1037  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[1]);
   1038  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[0]);
   1039  expectedVisitedNodeList[2]->AddChild(expectedVisitedNodeList[3]);
   1040  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[3]);
   1041  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[2]);
   1042 
   1043  ForEachNode<layers::ReverseIterator>(
   1044      root.get(), [&visitCount](ForEachTestNodeReverse* aNode) {
   1045        aNode->SetActualTraversalRank(visitCount);
   1046        visitCount++;
   1047        return aNode->GetType() == ForEachNodeType::Continue
   1048                   ? TraversalFlag::Continue
   1049                   : TraversalFlag::Skip;
   1050      });
   1051 
   1052  for (size_t i = 0; i < expectedVisitedNodeList.size(); i++) {
   1053    ASSERT_EQ(expectedVisitedNodeList[i]->GetExpectedTraversalRank(),
   1054              expectedVisitedNodeList[i]->GetActualTraversalRank())
   1055        << "Node at index " << i << " was hit out of order.";
   1056  }
   1057 
   1058  for (size_t i = 0; i < expectedSkippedNodeList.size(); i++) {
   1059    ASSERT_EQ(expectedSkippedNodeList[i]->GetExpectedTraversalRank(),
   1060              expectedSkippedNodeList[i]->GetActualTraversalRank())
   1061        << "Node at index " << i << "was not expected to be hit.";
   1062  }
   1063 }
   1064 
   1065 TEST(TreeTraversal, ForEachNodeIneligibleRoot)
   1066 {
   1067  int visitCount = 0;
   1068 
   1069  RefPtr<ForEachTestNodeReverse> root =
   1070      new ForEachTestNodeReverse(ForEachNodeType::Skip, 0);
   1071  RefPtr<ForEachTestNodeReverse> childNode1 =
   1072      new ForEachTestNodeReverse(ForEachNodeType::Continue);
   1073  RefPtr<ForEachTestNodeReverse> chlidNode2 =
   1074      new ForEachTestNodeReverse(ForEachNodeType::Skip);
   1075 
   1076  ForEachNode<layers::ReverseIterator>(
   1077      root.get(), [&visitCount](ForEachTestNodeReverse* aNode) {
   1078        aNode->SetActualTraversalRank(visitCount);
   1079        visitCount++;
   1080        return aNode->GetType() == ForEachNodeType::Continue
   1081                   ? TraversalFlag::Continue
   1082                   : TraversalFlag::Skip;
   1083      });
   1084 
   1085  ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
   1086      << "Root was hit out of order.";
   1087  ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
   1088            childNode1->GetActualTraversalRank())
   1089      << "Eligible child was still hit.";
   1090  ASSERT_EQ(chlidNode2->GetExpectedTraversalRank(),
   1091            chlidNode2->GetActualTraversalRank())
   1092      << "Ineligible child was still hit.";
   1093 }
   1094 
   1095 TEST(TreeTraversal, ForEachNodeLeavesIneligible)
   1096 {
   1097  std::vector<RefPtr<ForEachTestNodeForward>> nodeList;
   1098  nodeList.reserve(10);
   1099  int visitCount = 0;
   1100  for (int i = 0; i < 10; i++) {
   1101    if (i == 1 || i == 9) {
   1102      nodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip, i));
   1103    } else {
   1104      nodeList.push_back(
   1105          new ForEachTestNodeForward(ForEachNodeType::Continue, i));
   1106    }
   1107  }
   1108 
   1109  RefPtr<ForEachTestNodeForward> root = nodeList[0];
   1110  nodeList[0]->AddChild(nodeList[1]);
   1111  nodeList[0]->AddChild(nodeList[2]);
   1112  nodeList[2]->AddChild(nodeList[3]);
   1113  nodeList[2]->AddChild(nodeList[4]);
   1114  nodeList[4]->AddChild(nodeList[5]);
   1115  nodeList[4]->AddChild(nodeList[6]);
   1116  nodeList[6]->AddChild(nodeList[7]);
   1117  nodeList[7]->AddChild(nodeList[8]);
   1118  nodeList[7]->AddChild(nodeList[9]);
   1119 
   1120  ForEachNode<layers::ForwardIterator>(
   1121      root.get(), [&visitCount](ForEachTestNodeForward* aNode) {
   1122        aNode->SetActualTraversalRank(visitCount);
   1123        visitCount++;
   1124        return aNode->GetType() == ForEachNodeType::Continue
   1125                   ? TraversalFlag::Continue
   1126                   : TraversalFlag::Skip;
   1127      });
   1128 
   1129  for (size_t i = 0; i < nodeList.size(); i++) {
   1130    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
   1131              nodeList[i]->GetActualTraversalRank())
   1132        << "Node at index " << i << " was hit out of order.";
   1133  }
   1134 }
   1135 
   1136 TEST(TreeTraversal, ForEachNodeLeavesIneligibleReverse)
   1137 {
   1138  std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
   1139  nodeList.reserve(10);
   1140  int visitCount = 0;
   1141  for (int i = 0; i < 10; i++) {
   1142    if (i == 1 || i == 9) {
   1143      nodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip, i));
   1144    } else {
   1145      nodeList.push_back(
   1146          new ForEachTestNodeReverse(ForEachNodeType::Continue, i));
   1147    }
   1148  }
   1149 
   1150  RefPtr<ForEachTestNodeReverse> root = nodeList[0];
   1151  nodeList[0]->AddChild(nodeList[2]);
   1152  nodeList[0]->AddChild(nodeList[1]);
   1153  nodeList[2]->AddChild(nodeList[4]);
   1154  nodeList[2]->AddChild(nodeList[3]);
   1155  nodeList[4]->AddChild(nodeList[6]);
   1156  nodeList[4]->AddChild(nodeList[5]);
   1157  nodeList[6]->AddChild(nodeList[7]);
   1158  nodeList[7]->AddChild(nodeList[9]);
   1159  nodeList[7]->AddChild(nodeList[8]);
   1160 
   1161  ForEachNode<layers::ReverseIterator>(
   1162      root.get(), [&visitCount](ForEachTestNodeReverse* aNode) {
   1163        aNode->SetActualTraversalRank(visitCount);
   1164        visitCount++;
   1165        return aNode->GetType() == ForEachNodeType::Continue
   1166                   ? TraversalFlag::Continue
   1167                   : TraversalFlag::Skip;
   1168      });
   1169 
   1170  for (size_t i = 0; i < nodeList.size(); i++) {
   1171    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
   1172              nodeList[i]->GetActualTraversalRank())
   1173        << "Node at index " << i << " was hit out of order.";
   1174  }
   1175 }
   1176 
   1177 TEST(TreeTraversal, ForEachNodeLambdaReturnsVoid)
   1178 {
   1179  std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
   1180  nodeList.reserve(10);
   1181  int visitCount = 0;
   1182  for (int i = 0; i < 10; i++) {
   1183    nodeList.push_back(
   1184        new ForEachTestNodeReverse(ForEachNodeType::Continue, i));
   1185  }
   1186 
   1187  RefPtr<ForEachTestNodeReverse> root = nodeList[0];
   1188  nodeList[0]->AddChild(nodeList[4]);
   1189  nodeList[0]->AddChild(nodeList[1]);
   1190  nodeList[1]->AddChild(nodeList[3]);
   1191  nodeList[1]->AddChild(nodeList[2]);
   1192  nodeList[4]->AddChild(nodeList[6]);
   1193  nodeList[4]->AddChild(nodeList[5]);
   1194  nodeList[6]->AddChild(nodeList[7]);
   1195  nodeList[7]->AddChild(nodeList[9]);
   1196  nodeList[7]->AddChild(nodeList[8]);
   1197 
   1198  ForEachNode<layers::ReverseIterator>(
   1199      root.get(), [&visitCount](ForEachTestNodeReverse* aNode) {
   1200        aNode->SetActualTraversalRank(visitCount);
   1201        visitCount++;
   1202      });
   1203 
   1204  for (size_t i = 0; i < nodeList.size(); i++) {
   1205    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
   1206              nodeList[i]->GetActualTraversalRank())
   1207        << "Node at index " << i << " was hit out of order.";
   1208  }
   1209 }
   1210 
   1211 struct AssignSearchNodeTypesWithLastLeafAsNeedle {
   1212  RefPtr<SearchTestNodeForward>& node;
   1213  void operator()(SearchTestNodeForward* aNode) {
   1214    aNode->SetType(SearchNodeType::Hay);
   1215    if (aNode->IsLeaf()) {
   1216      node = aNode;
   1217    }
   1218  }
   1219 };
   1220 
   1221 struct AssignSearchNodeTypesAllHay {
   1222  void operator()(SearchTestNode* aNode) {
   1223    aNode->SetType(SearchNodeType::Hay);
   1224  }
   1225 };
   1226 
   1227 struct AssignSearchNodeTypesWithFirstLeafAsNeedle {
   1228  RefPtr<SearchTestNodeReverse>& needleNode;
   1229  void operator()(SearchTestNodeReverse* aNode) {
   1230    if (!needleNode && aNode->IsLeaf()) {
   1231      needleNode = aNode;
   1232    }
   1233    aNode->SetType(SearchNodeType::Hay);
   1234  }
   1235 };
   1236 
   1237 struct AssignSearchNodeValuesAllFalseValuesReverse {
   1238  int falseValue;
   1239  RefPtr<SearchTestNodeReverse>& needleNode;
   1240  void operator()(SearchTestNodeReverse* aNode) {
   1241    aNode->SetValue(falseValue);
   1242    if (!needleNode && aNode->IsLeaf()) {
   1243      needleNode = aNode;
   1244    }
   1245  }
   1246 };
   1247 
   1248 struct AssignSearchNodeValuesAllFalseValuesForward {
   1249  int falseValue;
   1250  RefPtr<SearchTestNodeForward>& needleNode;
   1251  void operator()(SearchTestNodeForward* aNode) {
   1252    aNode->SetValue(falseValue);
   1253    needleNode = aNode;
   1254  }
   1255 };
   1256 
   1257 struct AllocateUnitRegionsToLeavesOnly {
   1258  int& xWrap;
   1259  int& squareCount;
   1260  void operator()(ForEachTestNode* aNode) {
   1261    if (aNode->IsLeaf()) {
   1262      int x = squareCount % xWrap;
   1263      int y = squareCount / xWrap;
   1264      aNode->SetRegion(nsRegion(nsRect(x, y, 1, 1)));
   1265      squareCount++;
   1266    }
   1267  }
   1268 };
   1269 
   1270 template <typename Node>
   1271 static RefPtr<Node> DepthFirstSearchForwardRecursive(RefPtr<Node> aNode) {
   1272  if (aNode->GetType() == SearchNodeType::Needle) {
   1273    return aNode;
   1274  }
   1275  for (RefPtr<Node> node = aNode->GetFirstChild(); node != nullptr;
   1276       node = node->GetNextSibling()) {
   1277    if (RefPtr<Node> foundNode = DepthFirstSearchForwardRecursive(node)) {
   1278      return foundNode;
   1279    }
   1280  }
   1281  return nullptr;
   1282 }
   1283 
   1284 template <typename Node>
   1285 static RefPtr<Node> DepthFirstSearchCaptureVariablesForwardRecursive(
   1286    RefPtr<Node> aNode, int a, int b, int c, int d, int e, int f, int g, int h,
   1287    int i, int j, int k, int l, int m, int& n, int& o, int& p, int& q, int& r,
   1288    int& s, int& t, int& u, int& v, int& w, int& x, int& y, int& z) {
   1289  if (aNode->GetValue() == a + b + c + d + e + f + g + h + i + j + k + l + m +
   1290                               n + o + p + q + r + s + t + u + v + w + x + y +
   1291                               z) {
   1292    return aNode;
   1293  }
   1294  for (RefPtr<Node> node = aNode->GetFirstChild(); node != nullptr;
   1295       node = node->GetNextSibling()) {
   1296    if (RefPtr<Node> foundNode =
   1297            DepthFirstSearchCaptureVariablesForwardRecursive(
   1298                node, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s,
   1299                t, u, v, w, x, y, z)) {
   1300      return foundNode;
   1301    }
   1302  }
   1303  return nullptr;
   1304 }
   1305 
   1306 template <typename Node>
   1307 static RefPtr<Node> DepthFirstSearchPostOrderForwardRecursive(
   1308    RefPtr<Node> aNode) {
   1309  for (RefPtr<Node> node = aNode->GetFirstChild(); node != nullptr;
   1310       node = node->GetNextSibling()) {
   1311    if (RefPtr<Node> foundNode =
   1312            DepthFirstSearchPostOrderForwardRecursive(node)) {
   1313      return foundNode;
   1314    }
   1315  }
   1316  if (aNode->GetType() == SearchNodeType::Needle) {
   1317    return aNode;
   1318  }
   1319  return nullptr;
   1320 }
   1321 
   1322 template <typename Node>
   1323 static RefPtr<Node> BreadthFirstSearchForwardQueue(RefPtr<Node> aNode) {
   1324  std::queue<RefPtr<Node>> nodes;
   1325  nodes.push(aNode);
   1326  while (!nodes.empty()) {
   1327    RefPtr<Node> node = nodes.front();
   1328    nodes.pop();
   1329    if (node->GetType() == SearchNodeType::Needle) {
   1330      return node;
   1331    }
   1332    for (RefPtr<Node> childNode = node->GetFirstChild(); childNode != nullptr;
   1333         childNode = childNode->GetNextSibling()) {
   1334      nodes.push(childNode);
   1335    }
   1336  }
   1337  return nullptr;
   1338 }
   1339 
   1340 template <typename Node>
   1341 static RefPtr<Node> DepthFirstSearchReverseRecursive(RefPtr<Node> aNode) {
   1342  if (aNode->GetType() == SearchNodeType::Needle) {
   1343    return aNode;
   1344  }
   1345  for (RefPtr<Node> node = aNode->GetLastChild(); node != nullptr;
   1346       node = node->GetPrevSibling()) {
   1347    if (RefPtr<Node> foundNode = DepthFirstSearchReverseRecursive(node)) {
   1348      return foundNode;
   1349    }
   1350  }
   1351  return nullptr;
   1352 }
   1353 
   1354 template <typename Node>
   1355 static RefPtr<Node> DepthFirstSearchCaptureVariablesReverseRecursive(
   1356    RefPtr<Node> aNode, int a, int b, int c, int d, int e, int f, int g, int h,
   1357    int i, int j, int k, int l, int m, int& n, int& o, int& p, int& q, int& r,
   1358    int& s, int& t, int& u, int& v, int& w, int& x, int& y, int& z) {
   1359  if (aNode->GetValue() == a + b + c + d + e + f + g + h + i + j + k + l + m +
   1360                               n + o + p + q + r + s + t + u + v + w + x + y +
   1361                               z) {
   1362    return aNode;
   1363  }
   1364  for (RefPtr<Node> node = aNode->GetLastChild(); node != nullptr;
   1365       node = node->GetPrevSibling()) {
   1366    if (RefPtr<Node> foundNode =
   1367            DepthFirstSearchCaptureVariablesReverseRecursive(
   1368                node, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s,
   1369                t, u, v, w, x, y, z)) {
   1370      return foundNode;
   1371    }
   1372  }
   1373  return nullptr;
   1374 }
   1375 
   1376 template <typename Node>
   1377 static RefPtr<Node> DepthFirstSearchPostOrderReverseRecursive(
   1378    RefPtr<Node> aNode) {
   1379  for (RefPtr<Node> node = aNode->GetLastChild(); node != nullptr;
   1380       node = node->GetPrevSibling()) {
   1381    if (RefPtr<Node> foundNode =
   1382            DepthFirstSearchPostOrderReverseRecursive(node)) {
   1383      return foundNode;
   1384    }
   1385  }
   1386  if (aNode->GetType() == SearchNodeType::Needle) {
   1387    return aNode;
   1388  }
   1389  return nullptr;
   1390 }
   1391 
   1392 template <typename Node>
   1393 static RefPtr<Node> BreadthFirstSearchReverseQueue(RefPtr<Node> aNode) {
   1394  std::queue<RefPtr<Node>> nodes;
   1395  nodes.push(aNode);
   1396  while (!nodes.empty()) {
   1397    RefPtr<Node> node = nodes.front();
   1398    nodes.pop();
   1399    if (node->GetType() == SearchNodeType::Needle) {
   1400      return node;
   1401    }
   1402    for (RefPtr<Node> childNode = node->GetLastChild(); childNode != nullptr;
   1403         childNode = childNode->GetPrevSibling()) {
   1404      nodes.push(childNode);
   1405    }
   1406  }
   1407  return nullptr;
   1408 }
	tor-browser The Tor Browser
	git clone https://git.dasho.dev/tor-browser.git
	Log \| Files \| Refs \| README \| LICENSE