summaryrefslogtreecommitdiffstats
path: root/gfx/tests/gtest/TestTreeTraversal.cpp
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--gfx/tests/gtest/TestTreeTraversal.cpp1408
1 files changed, 1408 insertions, 0 deletions
diff --git a/gfx/tests/gtest/TestTreeTraversal.cpp b/gfx/tests/gtest/TestTreeTraversal.cpp
new file mode 100644
index 0000000000..7e538ca514
--- /dev/null
+++ b/gfx/tests/gtest/TestTreeTraversal.cpp
@@ -0,0 +1,1408 @@
+/* -*- 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/. */
+
+#include <vector>
+#include "mozilla/RefPtr.h"
+#include "gtest/gtest.h"
+#include "nsRegion.h"
+#include "nsRect.h"
+#include "TreeTraversal.h"
+#include <stack>
+#include <queue>
+
+using namespace mozilla::layers;
+using namespace mozilla;
+
+enum class SearchNodeType { Needle, Hay };
+enum class ForEachNodeType { Continue, Skip };
+
+template <class T>
+class TestNodeBase {
+ public:
+ NS_INLINE_DECL_REFCOUNTING(TestNodeBase<T>);
+ explicit TestNodeBase(T aType, int aExpectedTraversalRank = -1);
+ explicit TestNodeBase();
+ void SetActualTraversalRank(int aRank);
+ void SetValue(int aValue);
+ void SetType(T aType);
+ void SetRegion(nsRegion aRegion);
+ int GetExpectedTraversalRank();
+ int GetActualTraversalRank();
+ int GetValue();
+ T GetType();
+ nsRegion GetRegion();
+ virtual bool IsLeaf() = 0;
+
+ private:
+ MOZ_INIT_OUTSIDE_CTOR int mExpectedTraversalRank;
+ MOZ_INIT_OUTSIDE_CTOR int mActualTraversalRank;
+ MOZ_INIT_OUTSIDE_CTOR int mValue;
+ MOZ_INIT_OUTSIDE_CTOR nsRegion mRegion;
+ MOZ_INIT_OUTSIDE_CTOR T mType;
+
+ protected:
+ virtual ~TestNodeBase() = default;
+};
+
+template <class T>
+class TestNodeReverse : public TestNodeBase<T> {
+ public:
+ explicit TestNodeReverse(T aType, int aExpectedTraversalRank = -1);
+ explicit TestNodeReverse();
+ void AddChild(RefPtr<TestNodeReverse<T>> aNode);
+ TestNodeReverse<T>* GetLastChild();
+ TestNodeReverse<T>* GetPrevSibling();
+ bool IsLeaf();
+
+ private:
+ void SetPrevSibling(RefPtr<TestNodeReverse<T>> aNode);
+ void SetLastChild(RefPtr<TestNodeReverse<T>> aNode);
+ RefPtr<TestNodeReverse<T>> mSiblingNode;
+ RefPtr<TestNodeReverse<T>> mLastChildNode;
+ ~TestNodeReverse() = default;
+};
+
+template <class T>
+class TestNodeForward : public TestNodeBase<T> {
+ public:
+ explicit TestNodeForward(T aType, int aExpectedTraversalRank = -1);
+ explicit TestNodeForward();
+ void AddChild(RefPtr<TestNodeForward<T>> aNode);
+ TestNodeForward<T>* GetFirstChild();
+ TestNodeForward<T>* GetNextSibling();
+ bool IsLeaf();
+
+ private:
+ void SetNextSibling(RefPtr<TestNodeForward<T>> aNode);
+ void SetLastChild(RefPtr<TestNodeForward<T>> aNode);
+ void SetFirstChild(RefPtr<TestNodeForward<T>> aNode);
+ RefPtr<TestNodeForward<T>> mSiblingNode = nullptr;
+ RefPtr<TestNodeForward<T>> mFirstChildNode = nullptr;
+ // Track last child to facilitate appending children
+ RefPtr<TestNodeForward<T>> mLastChildNode = nullptr;
+ ~TestNodeForward() = default;
+};
+
+template <class T>
+TestNodeReverse<T>::TestNodeReverse(T aType, int aExpectedTraversalRank)
+ : TestNodeBase<T>(aType, aExpectedTraversalRank) {}
+
+template <class T>
+TestNodeReverse<T>::TestNodeReverse() : TestNodeBase<T>() {}
+
+template <class T>
+void TestNodeReverse<T>::SetLastChild(RefPtr<TestNodeReverse<T>> aNode) {
+ mLastChildNode = aNode;
+}
+
+template <class T>
+void TestNodeReverse<T>::AddChild(RefPtr<TestNodeReverse<T>> aNode) {
+ aNode->SetPrevSibling(mLastChildNode);
+ SetLastChild(aNode);
+}
+
+template <class T>
+void TestNodeReverse<T>::SetPrevSibling(RefPtr<TestNodeReverse<T>> aNode) {
+ mSiblingNode = aNode;
+}
+
+template <class T>
+TestNodeReverse<T>* TestNodeReverse<T>::GetLastChild() {
+ return mLastChildNode;
+}
+
+template <class T>
+TestNodeReverse<T>* TestNodeReverse<T>::GetPrevSibling() {
+ return mSiblingNode;
+}
+
+template <class T>
+bool TestNodeReverse<T>::IsLeaf() {
+ return !mLastChildNode;
+}
+
+template <class T>
+TestNodeForward<T>::TestNodeForward(T aType, int aExpectedTraversalRank)
+ : TestNodeBase<T>(aType, aExpectedTraversalRank) {}
+
+template <class T>
+TestNodeForward<T>::TestNodeForward() : TestNodeBase<T>() {}
+
+template <class T>
+void TestNodeForward<T>::AddChild(RefPtr<TestNodeForward<T>> aNode) {
+ if (mFirstChildNode == nullptr) {
+ SetFirstChild(aNode);
+ SetLastChild(aNode);
+ } else {
+ mLastChildNode->SetNextSibling(aNode);
+ SetLastChild(aNode);
+ }
+}
+
+template <class T>
+void TestNodeForward<T>::SetLastChild(RefPtr<TestNodeForward<T>> aNode) {
+ mLastChildNode = aNode;
+}
+
+template <class T>
+void TestNodeForward<T>::SetFirstChild(RefPtr<TestNodeForward<T>> aNode) {
+ mFirstChildNode = aNode;
+}
+
+template <class T>
+void TestNodeForward<T>::SetNextSibling(RefPtr<TestNodeForward<T>> aNode) {
+ mSiblingNode = aNode;
+}
+
+template <class T>
+bool TestNodeForward<T>::IsLeaf() {
+ return !mFirstChildNode;
+}
+
+template <class T>
+TestNodeForward<T>* TestNodeForward<T>::GetFirstChild() {
+ return mFirstChildNode;
+}
+
+template <class T>
+TestNodeForward<T>* TestNodeForward<T>::GetNextSibling() {
+ return mSiblingNode;
+}
+
+template <class T>
+TestNodeBase<T>::TestNodeBase(T aType, int aExpectedTraversalRank)
+ : mExpectedTraversalRank(aExpectedTraversalRank),
+ mActualTraversalRank(-1),
+ mType(aType) {}
+
+template <class T>
+TestNodeBase<T>::TestNodeBase() = default;
+
+template <class T>
+int TestNodeBase<T>::GetActualTraversalRank() {
+ return mActualTraversalRank;
+}
+
+template <class T>
+void TestNodeBase<T>::SetActualTraversalRank(int aRank) {
+ mActualTraversalRank = aRank;
+}
+
+template <class T>
+int TestNodeBase<T>::GetExpectedTraversalRank() {
+ return mExpectedTraversalRank;
+}
+
+template <class T>
+T TestNodeBase<T>::GetType() {
+ return mType;
+}
+
+template <class T>
+void TestNodeBase<T>::SetType(T aType) {
+ mType = aType;
+}
+
+template <class T>
+nsRegion TestNodeBase<T>::GetRegion() {
+ return mRegion;
+}
+
+template <class T>
+void TestNodeBase<T>::SetRegion(nsRegion aRegion) {
+ mRegion = aRegion;
+}
+
+template <class T>
+int TestNodeBase<T>::GetValue() {
+ return mValue;
+}
+
+template <class T>
+void TestNodeBase<T>::SetValue(int aValue) {
+ mValue = aValue;
+}
+
+typedef TestNodeBase<SearchNodeType> SearchTestNode;
+typedef TestNodeBase<ForEachNodeType> ForEachTestNode;
+typedef TestNodeReverse<SearchNodeType> SearchTestNodeReverse;
+typedef TestNodeReverse<ForEachNodeType> ForEachTestNodeReverse;
+typedef TestNodeForward<SearchNodeType> SearchTestNodeForward;
+typedef TestNodeForward<ForEachNodeType> ForEachTestNodeForward;
+
+TEST(TreeTraversal, DepthFirstSearchNull)
+{
+ RefPtr<SearchTestNodeReverse> nullNode;
+ RefPtr<SearchTestNodeReverse> result =
+ DepthFirstSearch<layers::ReverseIterator>(
+ nullNode.get(), [](SearchTestNodeReverse* aNode) {
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+ ASSERT_EQ(result.get(), nullptr)
+ << "Null root did not return null search result.";
+}
+
+TEST(TreeTraversal, DepthFirstSearchValueExists)
+{
+ int visitCount = 0;
+ size_t expectedNeedleTraversalRank = 7;
+ RefPtr<SearchTestNodeForward> needleNode;
+ std::vector<RefPtr<SearchTestNodeForward>> nodeList;
+ nodeList.reserve(10);
+ for (size_t i = 0; i < 10; i++) {
+ if (i == expectedNeedleTraversalRank) {
+ needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
+ nodeList.push_back(needleNode);
+ } else if (i < expectedNeedleTraversalRank) {
+ nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
+ } else {
+ nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
+ }
+ }
+
+ RefPtr<SearchTestNodeForward> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[0]->AddChild(nodeList[4]);
+ nodeList[1]->AddChild(nodeList[2]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[4]->AddChild(nodeList[5]);
+ nodeList[4]->AddChild(nodeList[6]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[8]);
+ nodeList[7]->AddChild(nodeList[9]);
+
+ RefPtr<SearchTestNodeForward> foundNode =
+ DepthFirstSearch<layers::ForwardIterator>(
+ root.get(), [&visitCount](SearchTestNodeForward* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
+ ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
+ << "Returned node does not match expected value (something odd "
+ "happened).";
+}
+
+TEST(TreeTraversal, DepthFirstSearchValueExistsReverse)
+{
+ int visitCount = 0;
+ size_t expectedNeedleTraversalRank = 7;
+ RefPtr<SearchTestNodeReverse> needleNode;
+ std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+ nodeList.reserve(10);
+ for (size_t i = 0; i < 10; i++) {
+ if (i == expectedNeedleTraversalRank) {
+ needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
+ nodeList.push_back(needleNode);
+ } else if (i < expectedNeedleTraversalRank) {
+ nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+ } else {
+ nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
+ }
+ }
+
+ RefPtr<SearchTestNodeReverse> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[4]);
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[1]->AddChild(nodeList[2]);
+ nodeList[4]->AddChild(nodeList[6]);
+ nodeList[4]->AddChild(nodeList[5]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[9]);
+ nodeList[7]->AddChild(nodeList[8]);
+
+ RefPtr<SearchTestNodeReverse> foundNode =
+ DepthFirstSearch<layers::ReverseIterator>(
+ root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
+ ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
+ << "Returned node does not match expected value (something odd "
+ "happened).";
+}
+
+TEST(TreeTraversal, DepthFirstSearchRootIsNeedle)
+{
+ RefPtr<SearchTestNodeReverse> root =
+ new SearchTestNodeReverse(SearchNodeType::Needle, 0);
+ RefPtr<SearchTestNodeReverse> childNode1 =
+ new SearchTestNodeReverse(SearchNodeType::Hay);
+ RefPtr<SearchTestNodeReverse> childNode2 =
+ new SearchTestNodeReverse(SearchNodeType::Hay);
+ int visitCount = 0;
+ RefPtr<SearchTestNodeReverse> result =
+ DepthFirstSearch<layers::ReverseIterator>(
+ root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+ ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
+ ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
+ << "Search starting at needle did not return needle.";
+ ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
+ childNode1->GetActualTraversalRank())
+ << "Search starting at needle continued past needle.";
+ ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
+ childNode2->GetActualTraversalRank())
+ << "Search starting at needle continued past needle.";
+}
+
+TEST(TreeTraversal, DepthFirstSearchValueDoesNotExist)
+{
+ int visitCount = 0;
+ std::vector<RefPtr<SearchTestNodeForward>> nodeList;
+ nodeList.reserve(10);
+ for (int i = 0; i < 10; i++) {
+ nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
+ }
+
+ RefPtr<SearchTestNodeForward> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[0]->AddChild(nodeList[4]);
+ nodeList[1]->AddChild(nodeList[2]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[4]->AddChild(nodeList[5]);
+ nodeList[4]->AddChild(nodeList[6]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[8]);
+ nodeList[7]->AddChild(nodeList[9]);
+
+ RefPtr<SearchTestNodeForward> foundNode =
+ DepthFirstSearch<layers::ForwardIterator>(
+ root.get(), [&visitCount](SearchTestNodeForward* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (int i = 0; i < 10; i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode.get(), nullptr)
+ << "Search found something that should not exist.";
+}
+
+TEST(TreeTraversal, DepthFirstSearchValueDoesNotExistReverse)
+{
+ int visitCount = 0;
+ std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+ nodeList.reserve(10);
+ for (int i = 0; i < 10; i++) {
+ nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+ }
+
+ RefPtr<SearchTestNodeReverse> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[4]);
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[1]->AddChild(nodeList[2]);
+ nodeList[4]->AddChild(nodeList[6]);
+ nodeList[4]->AddChild(nodeList[5]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[9]);
+ nodeList[7]->AddChild(nodeList[8]);
+
+ RefPtr<SearchTestNodeReverse> foundNode =
+ DepthFirstSearch<layers::ReverseIterator>(
+ root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (int i = 0; i < 10; i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode.get(), nullptr)
+ << "Search found something that should not exist.";
+}
+
+TEST(TreeTraversal, DepthFirstSearchPostOrderNull)
+{
+ RefPtr<SearchTestNodeReverse> nullNode;
+ RefPtr<SearchTestNodeReverse> result =
+ DepthFirstSearchPostOrder<layers::ReverseIterator>(
+ nullNode.get(), [](SearchTestNodeReverse* aNode) {
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+ ASSERT_EQ(result.get(), nullptr)
+ << "Null root did not return null search result.";
+}
+
+TEST(TreeTraversal, DepthFirstSearchPostOrderValueExists)
+{
+ int visitCount = 0;
+ size_t expectedNeedleTraversalRank = 7;
+ RefPtr<SearchTestNodeForward> needleNode;
+ std::vector<RefPtr<SearchTestNodeForward>> nodeList;
+ for (size_t i = 0; i < 10; i++) {
+ if (i == expectedNeedleTraversalRank) {
+ needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
+ nodeList.push_back(needleNode);
+ } else if (i < expectedNeedleTraversalRank) {
+ nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
+ } else {
+ nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
+ }
+ }
+
+ RefPtr<SearchTestNodeForward> root = nodeList[9];
+ nodeList[9]->AddChild(nodeList[2]);
+ nodeList[9]->AddChild(nodeList[8]);
+ nodeList[2]->AddChild(nodeList[0]);
+ nodeList[2]->AddChild(nodeList[1]);
+ nodeList[8]->AddChild(nodeList[6]);
+ nodeList[8]->AddChild(nodeList[7]);
+ nodeList[6]->AddChild(nodeList[5]);
+ nodeList[5]->AddChild(nodeList[3]);
+ nodeList[5]->AddChild(nodeList[4]);
+
+ RefPtr<SearchTestNodeForward> foundNode =
+ DepthFirstSearchPostOrder<layers::ForwardIterator>(
+ root.get(), [&visitCount](SearchTestNodeForward* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
+ ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
+ << "Returned node does not match expected value (something odd "
+ "happened).";
+}
+
+TEST(TreeTraversal, DepthFirstSearchPostOrderValueExistsReverse)
+{
+ int visitCount = 0;
+ size_t expectedNeedleTraversalRank = 7;
+ RefPtr<SearchTestNodeReverse> needleNode;
+ std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+ for (size_t i = 0; i < 10; i++) {
+ if (i == expectedNeedleTraversalRank) {
+ needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
+ nodeList.push_back(needleNode);
+ } else if (i < expectedNeedleTraversalRank) {
+ nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+ } else {
+ nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
+ }
+ }
+
+ RefPtr<SearchTestNodeReverse> root = nodeList[9];
+ nodeList[9]->AddChild(nodeList[8]);
+ nodeList[9]->AddChild(nodeList[2]);
+ nodeList[2]->AddChild(nodeList[1]);
+ nodeList[2]->AddChild(nodeList[0]);
+ nodeList[8]->AddChild(nodeList[7]);
+ nodeList[8]->AddChild(nodeList[6]);
+ nodeList[6]->AddChild(nodeList[5]);
+ nodeList[5]->AddChild(nodeList[4]);
+ nodeList[5]->AddChild(nodeList[3]);
+
+ RefPtr<SearchTestNodeReverse> foundNode =
+ DepthFirstSearchPostOrder<layers::ReverseIterator>(
+ root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
+ ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
+ << "Returned node does not match expected value (something odd "
+ "happened).";
+}
+
+TEST(TreeTraversal, DepthFirstSearchPostOrderRootIsNeedle)
+{
+ RefPtr<SearchTestNodeReverse> root =
+ new SearchTestNodeReverse(SearchNodeType::Needle, 0);
+ RefPtr<SearchTestNodeReverse> childNode1 =
+ new SearchTestNodeReverse(SearchNodeType::Hay);
+ RefPtr<SearchTestNodeReverse> childNode2 =
+ new SearchTestNodeReverse(SearchNodeType::Hay);
+ int visitCount = 0;
+ RefPtr<SearchTestNodeReverse> result =
+ DepthFirstSearchPostOrder<layers::ReverseIterator>(
+ root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+ ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
+ ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
+ << "Search starting at needle did not return needle.";
+ ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
+ childNode1->GetActualTraversalRank())
+ << "Search starting at needle continued past needle.";
+ ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
+ childNode2->GetActualTraversalRank())
+ << "Search starting at needle continued past needle.";
+}
+
+TEST(TreeTraversal, DepthFirstSearchPostOrderValueDoesNotExist)
+{
+ int visitCount = 0;
+ std::vector<RefPtr<SearchTestNodeForward>> nodeList;
+ nodeList.reserve(10);
+ for (int i = 0; i < 10; i++) {
+ nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
+ }
+
+ RefPtr<SearchTestNodeForward> root = nodeList[9];
+ nodeList[9]->AddChild(nodeList[2]);
+ nodeList[9]->AddChild(nodeList[8]);
+ nodeList[2]->AddChild(nodeList[0]);
+ nodeList[2]->AddChild(nodeList[1]);
+ nodeList[8]->AddChild(nodeList[6]);
+ nodeList[8]->AddChild(nodeList[7]);
+ nodeList[6]->AddChild(nodeList[5]);
+ nodeList[5]->AddChild(nodeList[3]);
+ nodeList[5]->AddChild(nodeList[4]);
+
+ RefPtr<SearchTestNodeForward> foundNode =
+ DepthFirstSearchPostOrder<layers::ForwardIterator>(
+ root.get(), [&visitCount](SearchTestNodeForward* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (int i = 0; i < 10; i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode.get(), nullptr)
+ << "Search found something that should not exist.";
+}
+
+TEST(TreeTraversal, DepthFirstSearchPostOrderValueDoesNotExistReverse)
+{
+ int visitCount = 0;
+ std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+ nodeList.reserve(10);
+ for (int i = 0; i < 10; i++) {
+ nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+ }
+
+ RefPtr<SearchTestNodeReverse> root = nodeList[9];
+ nodeList[9]->AddChild(nodeList[8]);
+ nodeList[9]->AddChild(nodeList[2]);
+ nodeList[2]->AddChild(nodeList[1]);
+ nodeList[2]->AddChild(nodeList[0]);
+ nodeList[8]->AddChild(nodeList[7]);
+ nodeList[8]->AddChild(nodeList[6]);
+ nodeList[6]->AddChild(nodeList[5]);
+ nodeList[5]->AddChild(nodeList[4]);
+ nodeList[5]->AddChild(nodeList[3]);
+
+ RefPtr<SearchTestNodeReverse> foundNode =
+ DepthFirstSearchPostOrder<layers::ReverseIterator>(
+ root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (int i = 0; i < 10; i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode.get(), nullptr)
+ << "Search found something that should not exist.";
+}
+
+TEST(TreeTraversal, BreadthFirstSearchNull)
+{
+ RefPtr<SearchTestNodeReverse> nullNode;
+ RefPtr<SearchTestNodeReverse> result =
+ BreadthFirstSearch<layers::ReverseIterator>(
+ nullNode.get(), [](SearchTestNodeReverse* aNode) {
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+ ASSERT_EQ(result.get(), nullptr)
+ << "Null root did not return null search result.";
+}
+
+TEST(TreeTraversal, BreadthFirstSearchRootIsNeedle)
+{
+ RefPtr<SearchTestNodeReverse> root =
+ new SearchTestNodeReverse(SearchNodeType::Needle, 0);
+ RefPtr<SearchTestNodeReverse> childNode1 =
+ new SearchTestNodeReverse(SearchNodeType::Hay);
+ RefPtr<SearchTestNodeReverse> childNode2 =
+ new SearchTestNodeReverse(SearchNodeType::Hay);
+ int visitCount = 0;
+ RefPtr<SearchTestNodeReverse> result =
+ BreadthFirstSearch<layers::ReverseIterator>(
+ root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+ ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
+ ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
+ << "Search starting at needle did not return needle.";
+ ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
+ childNode1->GetActualTraversalRank())
+ << "Search starting at needle continued past needle.";
+ ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
+ childNode2->GetActualTraversalRank())
+ << "Search starting at needle continued past needle.";
+}
+
+TEST(TreeTraversal, BreadthFirstSearchValueExists)
+{
+ int visitCount = 0;
+ size_t expectedNeedleTraversalRank = 7;
+ RefPtr<SearchTestNodeForward> needleNode;
+ std::vector<RefPtr<SearchTestNodeForward>> nodeList;
+ nodeList.reserve(10);
+ for (size_t i = 0; i < 10; i++) {
+ if (i == expectedNeedleTraversalRank) {
+ needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
+ nodeList.push_back(needleNode);
+ } else if (i < expectedNeedleTraversalRank) {
+ nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
+ } else {
+ nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
+ }
+ }
+
+ RefPtr<SearchTestNodeForward> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[0]->AddChild(nodeList[2]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[1]->AddChild(nodeList[4]);
+ nodeList[2]->AddChild(nodeList[5]);
+ nodeList[2]->AddChild(nodeList[6]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[8]);
+ nodeList[7]->AddChild(nodeList[9]);
+
+ RefPtr<SearchTestNodeForward> foundNode =
+ BreadthFirstSearch<layers::ForwardIterator>(
+ root.get(), [&visitCount](SearchTestNodeForward* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
+ ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
+ << "Returned node does not match expected value (something odd "
+ "happened).";
+}
+
+TEST(TreeTraversal, BreadthFirstSearchValueExistsReverse)
+{
+ int visitCount = 0;
+ size_t expectedNeedleTraversalRank = 7;
+ RefPtr<SearchTestNodeReverse> needleNode;
+ std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+ nodeList.reserve(10);
+ for (size_t i = 0; i < 10; i++) {
+ if (i == expectedNeedleTraversalRank) {
+ needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
+ nodeList.push_back(needleNode);
+ } else if (i < expectedNeedleTraversalRank) {
+ nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+ } else {
+ nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
+ }
+ }
+
+ RefPtr<SearchTestNodeReverse> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[2]);
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[1]->AddChild(nodeList[4]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[2]->AddChild(nodeList[6]);
+ nodeList[2]->AddChild(nodeList[5]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[9]);
+ nodeList[7]->AddChild(nodeList[8]);
+
+ RefPtr<SearchTestNodeReverse> foundNode =
+ BreadthFirstSearch<layers::ReverseIterator>(
+ root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
+ ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
+ << "Returned node does not match expected value (something odd "
+ "happened).";
+}
+
+TEST(TreeTraversal, BreadthFirstSearchValueDoesNotExist)
+{
+ int visitCount = 0;
+ std::vector<RefPtr<SearchTestNodeForward>> nodeList;
+ nodeList.reserve(10);
+ for (int i = 0; i < 10; i++) {
+ nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
+ }
+
+ RefPtr<SearchTestNodeForward> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[0]->AddChild(nodeList[2]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[1]->AddChild(nodeList[4]);
+ nodeList[2]->AddChild(nodeList[5]);
+ nodeList[2]->AddChild(nodeList[6]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[8]);
+ nodeList[7]->AddChild(nodeList[9]);
+
+ RefPtr<SearchTestNodeForward> foundNode =
+ BreadthFirstSearch<layers::ForwardIterator>(
+ root.get(), [&visitCount](SearchTestNodeForward* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode.get(), nullptr)
+ << "Search found something that should not exist.";
+}
+
+TEST(TreeTraversal, BreadthFirstSearchValueDoesNotExistReverse)
+{
+ int visitCount = 0;
+ std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+ nodeList.reserve(10);
+ for (int i = 0; i < 10; i++) {
+ nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+ }
+
+ RefPtr<SearchTestNodeReverse> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[2]);
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[1]->AddChild(nodeList[4]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[2]->AddChild(nodeList[6]);
+ nodeList[2]->AddChild(nodeList[5]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[9]);
+ nodeList[7]->AddChild(nodeList[8]);
+
+ RefPtr<SearchTestNodeReverse> foundNode =
+ BreadthFirstSearch<layers::ReverseIterator>(
+ root.get(), [&visitCount](SearchTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == SearchNodeType::Needle;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ ASSERT_EQ(foundNode.get(), nullptr)
+ << "Search found something that should not exist.";
+}
+
+TEST(TreeTraversal, ForEachNodeNullStillRuns)
+{
+ RefPtr<ForEachTestNodeReverse> nullNode;
+ ForEachNode<layers::ReverseIterator>(
+ nullNode.get(),
+ [](ForEachTestNodeReverse* aNode) { return TraversalFlag::Continue; });
+}
+
+TEST(TreeTraversal, ForEachNodeAllEligible)
+{
+ std::vector<RefPtr<ForEachTestNodeForward>> nodeList;
+ int visitCount = 0;
+ nodeList.reserve(10);
+ for (int i = 0; i < 10; i++) {
+ nodeList.push_back(
+ new ForEachTestNodeForward(ForEachNodeType::Continue, i));
+ }
+
+ RefPtr<ForEachTestNodeForward> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[0]->AddChild(nodeList[4]);
+ nodeList[1]->AddChild(nodeList[2]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[4]->AddChild(nodeList[5]);
+ nodeList[4]->AddChild(nodeList[6]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[8]);
+ nodeList[7]->AddChild(nodeList[9]);
+
+ ForEachNode<layers::ForwardIterator>(
+ root.get(), [&visitCount](ForEachTestNodeForward* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == ForEachNodeType::Continue
+ ? TraversalFlag::Continue
+ : TraversalFlag::Skip;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+}
+
+TEST(TreeTraversal, ForEachNodeAllEligibleReverse)
+{
+ std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
+ int visitCount = 0;
+ nodeList.reserve(10);
+ for (int i = 0; i < 10; i++) {
+ nodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Continue, i));
+ }
+
+ RefPtr<ForEachTestNodeReverse> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[4]);
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[1]->AddChild(nodeList[2]);
+ nodeList[4]->AddChild(nodeList[6]);
+ nodeList[4]->AddChild(nodeList[5]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[9]);
+ nodeList[7]->AddChild(nodeList[8]);
+
+ ForEachNode<layers::ReverseIterator>(
+ root.get(), [&visitCount](ForEachTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == ForEachNodeType::Continue
+ ? TraversalFlag::Continue
+ : TraversalFlag::Skip;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+}
+
+TEST(TreeTraversal, ForEachNodeSomeIneligibleNodes)
+{
+ std::vector<RefPtr<ForEachTestNodeForward>> expectedVisitedNodeList;
+ std::vector<RefPtr<ForEachTestNodeForward>> expectedSkippedNodeList;
+ int visitCount = 0;
+
+ expectedVisitedNodeList.push_back(
+ new ForEachTestNodeForward(ForEachNodeType::Continue, 0));
+ expectedVisitedNodeList.push_back(
+ new ForEachTestNodeForward(ForEachNodeType::Skip, 1));
+ expectedVisitedNodeList.push_back(
+ new ForEachTestNodeForward(ForEachNodeType::Continue, 2));
+ expectedVisitedNodeList.push_back(
+ new ForEachTestNodeForward(ForEachNodeType::Skip, 3));
+
+ expectedSkippedNodeList.push_back(
+ new ForEachTestNodeForward(ForEachNodeType::Continue));
+ expectedSkippedNodeList.push_back(
+ new ForEachTestNodeForward(ForEachNodeType::Continue));
+ expectedSkippedNodeList.push_back(
+ new ForEachTestNodeForward(ForEachNodeType::Skip));
+ expectedSkippedNodeList.push_back(
+ new ForEachTestNodeForward(ForEachNodeType::Skip));
+
+ RefPtr<ForEachTestNodeForward> root = expectedVisitedNodeList[0];
+ expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[1]);
+ expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[2]);
+ expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[0]);
+ expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[1]);
+ expectedVisitedNodeList[2]->AddChild(expectedVisitedNodeList[3]);
+ expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[2]);
+ expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[3]);
+
+ ForEachNode<layers::ForwardIterator>(
+ root.get(), [&visitCount](ForEachTestNodeForward* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == ForEachNodeType::Continue
+ ? TraversalFlag::Continue
+ : TraversalFlag::Skip;
+ });
+
+ for (size_t i = 0; i < expectedVisitedNodeList.size(); i++) {
+ ASSERT_EQ(expectedVisitedNodeList[i]->GetExpectedTraversalRank(),
+ expectedVisitedNodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ for (size_t i = 0; i < expectedSkippedNodeList.size(); i++) {
+ ASSERT_EQ(expectedSkippedNodeList[i]->GetExpectedTraversalRank(),
+ expectedSkippedNodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << "was not expected to be hit.";
+ }
+}
+
+TEST(TreeTraversal, ForEachNodeSomeIneligibleNodesReverse)
+{
+ std::vector<RefPtr<ForEachTestNodeReverse>> expectedVisitedNodeList;
+ std::vector<RefPtr<ForEachTestNodeReverse>> expectedSkippedNodeList;
+ int visitCount = 0;
+
+ expectedVisitedNodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Continue, 0));
+ expectedVisitedNodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Skip, 1));
+ expectedVisitedNodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Continue, 2));
+ expectedVisitedNodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Skip, 3));
+
+ expectedSkippedNodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Continue));
+ expectedSkippedNodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Continue));
+ expectedSkippedNodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Skip));
+ expectedSkippedNodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Skip));
+
+ RefPtr<ForEachTestNodeReverse> root = expectedVisitedNodeList[0];
+ expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[2]);
+ expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[1]);
+ expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[1]);
+ expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[0]);
+ expectedVisitedNodeList[2]->AddChild(expectedVisitedNodeList[3]);
+ expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[3]);
+ expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[2]);
+
+ ForEachNode<layers::ReverseIterator>(
+ root.get(), [&visitCount](ForEachTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == ForEachNodeType::Continue
+ ? TraversalFlag::Continue
+ : TraversalFlag::Skip;
+ });
+
+ for (size_t i = 0; i < expectedVisitedNodeList.size(); i++) {
+ ASSERT_EQ(expectedVisitedNodeList[i]->GetExpectedTraversalRank(),
+ expectedVisitedNodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+
+ for (size_t i = 0; i < expectedSkippedNodeList.size(); i++) {
+ ASSERT_EQ(expectedSkippedNodeList[i]->GetExpectedTraversalRank(),
+ expectedSkippedNodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << "was not expected to be hit.";
+ }
+}
+
+TEST(TreeTraversal, ForEachNodeIneligibleRoot)
+{
+ int visitCount = 0;
+
+ RefPtr<ForEachTestNodeReverse> root =
+ new ForEachTestNodeReverse(ForEachNodeType::Skip, 0);
+ RefPtr<ForEachTestNodeReverse> childNode1 =
+ new ForEachTestNodeReverse(ForEachNodeType::Continue);
+ RefPtr<ForEachTestNodeReverse> chlidNode2 =
+ new ForEachTestNodeReverse(ForEachNodeType::Skip);
+
+ ForEachNode<layers::ReverseIterator>(
+ root.get(), [&visitCount](ForEachTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == ForEachNodeType::Continue
+ ? TraversalFlag::Continue
+ : TraversalFlag::Skip;
+ });
+
+ ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
+ << "Root was hit out of order.";
+ ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
+ childNode1->GetActualTraversalRank())
+ << "Eligible child was still hit.";
+ ASSERT_EQ(chlidNode2->GetExpectedTraversalRank(),
+ chlidNode2->GetActualTraversalRank())
+ << "Ineligible child was still hit.";
+}
+
+TEST(TreeTraversal, ForEachNodeLeavesIneligible)
+{
+ std::vector<RefPtr<ForEachTestNodeForward>> nodeList;
+ nodeList.reserve(10);
+ int visitCount = 0;
+ for (int i = 0; i < 10; i++) {
+ if (i == 1 || i == 9) {
+ nodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip, i));
+ } else {
+ nodeList.push_back(
+ new ForEachTestNodeForward(ForEachNodeType::Continue, i));
+ }
+ }
+
+ RefPtr<ForEachTestNodeForward> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[0]->AddChild(nodeList[2]);
+ nodeList[2]->AddChild(nodeList[3]);
+ nodeList[2]->AddChild(nodeList[4]);
+ nodeList[4]->AddChild(nodeList[5]);
+ nodeList[4]->AddChild(nodeList[6]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[8]);
+ nodeList[7]->AddChild(nodeList[9]);
+
+ ForEachNode<layers::ForwardIterator>(
+ root.get(), [&visitCount](ForEachTestNodeForward* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == ForEachNodeType::Continue
+ ? TraversalFlag::Continue
+ : TraversalFlag::Skip;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+}
+
+TEST(TreeTraversal, ForEachNodeLeavesIneligibleReverse)
+{
+ std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
+ nodeList.reserve(10);
+ int visitCount = 0;
+ for (int i = 0; i < 10; i++) {
+ if (i == 1 || i == 9) {
+ nodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip, i));
+ } else {
+ nodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Continue, i));
+ }
+ }
+
+ RefPtr<ForEachTestNodeReverse> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[2]);
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[2]->AddChild(nodeList[4]);
+ nodeList[2]->AddChild(nodeList[3]);
+ nodeList[4]->AddChild(nodeList[6]);
+ nodeList[4]->AddChild(nodeList[5]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[9]);
+ nodeList[7]->AddChild(nodeList[8]);
+
+ ForEachNode<layers::ReverseIterator>(
+ root.get(), [&visitCount](ForEachTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ return aNode->GetType() == ForEachNodeType::Continue
+ ? TraversalFlag::Continue
+ : TraversalFlag::Skip;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+}
+
+TEST(TreeTraversal, ForEachNodeLambdaReturnsVoid)
+{
+ std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
+ nodeList.reserve(10);
+ int visitCount = 0;
+ for (int i = 0; i < 10; i++) {
+ nodeList.push_back(
+ new ForEachTestNodeReverse(ForEachNodeType::Continue, i));
+ }
+
+ RefPtr<ForEachTestNodeReverse> root = nodeList[0];
+ nodeList[0]->AddChild(nodeList[4]);
+ nodeList[0]->AddChild(nodeList[1]);
+ nodeList[1]->AddChild(nodeList[3]);
+ nodeList[1]->AddChild(nodeList[2]);
+ nodeList[4]->AddChild(nodeList[6]);
+ nodeList[4]->AddChild(nodeList[5]);
+ nodeList[6]->AddChild(nodeList[7]);
+ nodeList[7]->AddChild(nodeList[9]);
+ nodeList[7]->AddChild(nodeList[8]);
+
+ ForEachNode<layers::ReverseIterator>(
+ root.get(), [&visitCount](ForEachTestNodeReverse* aNode) {
+ aNode->SetActualTraversalRank(visitCount);
+ visitCount++;
+ });
+
+ for (size_t i = 0; i < nodeList.size(); i++) {
+ ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+ nodeList[i]->GetActualTraversalRank())
+ << "Node at index " << i << " was hit out of order.";
+ }
+}
+
+struct AssignSearchNodeTypesWithLastLeafAsNeedle {
+ RefPtr<SearchTestNodeForward>& node;
+ void operator()(SearchTestNodeForward* aNode) {
+ aNode->SetType(SearchNodeType::Hay);
+ if (aNode->IsLeaf()) {
+ node = aNode;
+ }
+ }
+};
+
+struct AssignSearchNodeTypesAllHay {
+ void operator()(SearchTestNode* aNode) {
+ aNode->SetType(SearchNodeType::Hay);
+ }
+};
+
+struct AssignSearchNodeTypesWithFirstLeafAsNeedle {
+ RefPtr<SearchTestNodeReverse>& needleNode;
+ void operator()(SearchTestNodeReverse* aNode) {
+ if (!needleNode && aNode->IsLeaf()) {
+ needleNode = aNode;
+ }
+ aNode->SetType(SearchNodeType::Hay);
+ }
+};
+
+struct AssignSearchNodeValuesAllFalseValuesReverse {
+ int falseValue;
+ RefPtr<SearchTestNodeReverse>& needleNode;
+ void operator()(SearchTestNodeReverse* aNode) {
+ aNode->SetValue(falseValue);
+ if (!needleNode && aNode->IsLeaf()) {
+ needleNode = aNode;
+ }
+ }
+};
+
+struct AssignSearchNodeValuesAllFalseValuesForward {
+ int falseValue;
+ RefPtr<SearchTestNodeForward>& needleNode;
+ void operator()(SearchTestNodeForward* aNode) {
+ aNode->SetValue(falseValue);
+ needleNode = aNode;
+ }
+};
+
+struct AllocateUnitRegionsToLeavesOnly {
+ int& xWrap;
+ int& squareCount;
+ void operator()(ForEachTestNode* aNode) {
+ if (aNode->IsLeaf()) {
+ int x = squareCount % xWrap;
+ int y = squareCount / xWrap;
+ aNode->SetRegion(nsRegion(nsRect(x, y, 1, 1)));
+ squareCount++;
+ }
+ }
+};
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchForwardRecursive(RefPtr<Node> aNode) {
+ if (aNode->GetType() == SearchNodeType::Needle) {
+ return aNode;
+ }
+ for (RefPtr<Node> node = aNode->GetFirstChild(); node != nullptr;
+ node = node->GetNextSibling()) {
+ if (RefPtr<Node> foundNode = DepthFirstSearchForwardRecursive(node)) {
+ return foundNode;
+ }
+ }
+ return nullptr;
+}
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchCaptureVariablesForwardRecursive(
+ RefPtr<Node> aNode, int a, int b, int c, int d, int e, int f, int g, int h,
+ int i, int j, int k, int l, int m, int& n, int& o, int& p, int& q, int& r,
+ int& s, int& t, int& u, int& v, int& w, int& x, int& y, int& z) {
+ if (aNode->GetValue() == a + b + c + d + e + f + g + h + i + j + k + l + m +
+ n + o + p + q + r + s + t + u + v + w + x + y +
+ z) {
+ return aNode;
+ }
+ for (RefPtr<Node> node = aNode->GetFirstChild(); node != nullptr;
+ node = node->GetNextSibling()) {
+ if (RefPtr<Node> foundNode =
+ DepthFirstSearchCaptureVariablesForwardRecursive(
+ node, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s,
+ t, u, v, w, x, y, z)) {
+ return foundNode;
+ }
+ }
+ return nullptr;
+}
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchPostOrderForwardRecursive(
+ RefPtr<Node> aNode) {
+ for (RefPtr<Node> node = aNode->GetFirstChild(); node != nullptr;
+ node = node->GetNextSibling()) {
+ if (RefPtr<Node> foundNode =
+ DepthFirstSearchPostOrderForwardRecursive(node)) {
+ return foundNode;
+ }
+ }
+ if (aNode->GetType() == SearchNodeType::Needle) {
+ return aNode;
+ }
+ return nullptr;
+}
+
+template <typename Node>
+static RefPtr<Node> BreadthFirstSearchForwardQueue(RefPtr<Node> aNode) {
+ std::queue<RefPtr<Node>> nodes;
+ nodes.push(aNode);
+ while (!nodes.empty()) {
+ RefPtr<Node> node = nodes.front();
+ nodes.pop();
+ if (node->GetType() == SearchNodeType::Needle) {
+ return node;
+ }
+ for (RefPtr<Node> childNode = node->GetFirstChild(); childNode != nullptr;
+ childNode = childNode->GetNextSibling()) {
+ nodes.push(childNode);
+ }
+ }
+ return nullptr;
+}
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchReverseRecursive(RefPtr<Node> aNode) {
+ if (aNode->GetType() == SearchNodeType::Needle) {
+ return aNode;
+ }
+ for (RefPtr<Node> node = aNode->GetLastChild(); node != nullptr;
+ node = node->GetPrevSibling()) {
+ if (RefPtr<Node> foundNode = DepthFirstSearchReverseRecursive(node)) {
+ return foundNode;
+ }
+ }
+ return nullptr;
+}
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchCaptureVariablesReverseRecursive(
+ RefPtr<Node> aNode, int a, int b, int c, int d, int e, int f, int g, int h,
+ int i, int j, int k, int l, int m, int& n, int& o, int& p, int& q, int& r,
+ int& s, int& t, int& u, int& v, int& w, int& x, int& y, int& z) {
+ if (aNode->GetValue() == a + b + c + d + e + f + g + h + i + j + k + l + m +
+ n + o + p + q + r + s + t + u + v + w + x + y +
+ z) {
+ return aNode;
+ }
+ for (RefPtr<Node> node = aNode->GetLastChild(); node != nullptr;
+ node = node->GetPrevSibling()) {
+ if (RefPtr<Node> foundNode =
+ DepthFirstSearchCaptureVariablesReverseRecursive(
+ node, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s,
+ t, u, v, w, x, y, z)) {
+ return foundNode;
+ }
+ }
+ return nullptr;
+}
+
+template <typename Node>
+static RefPtr<Node> DepthFirstSearchPostOrderReverseRecursive(
+ RefPtr<Node> aNode) {
+ for (RefPtr<Node> node = aNode->GetLastChild(); node != nullptr;
+ node = node->GetPrevSibling()) {
+ if (RefPtr<Node> foundNode =
+ DepthFirstSearchPostOrderReverseRecursive(node)) {
+ return foundNode;
+ }
+ }
+ if (aNode->GetType() == SearchNodeType::Needle) {
+ return aNode;
+ }
+ return nullptr;
+}
+
+template <typename Node>
+static RefPtr<Node> BreadthFirstSearchReverseQueue(RefPtr<Node> aNode) {
+ std::queue<RefPtr<Node>> nodes;
+ nodes.push(aNode);
+ while (!nodes.empty()) {
+ RefPtr<Node> node = nodes.front();
+ nodes.pop();
+ if (node->GetType() == SearchNodeType::Needle) {
+ return node;
+ }
+ for (RefPtr<Node> childNode = node->GetLastChild(); childNode != nullptr;
+ childNode = childNode->GetPrevSibling()) {
+ nodes.push(childNode);
+ }
+ }
+ return nullptr;
+}