diff options
Diffstat (limited to 'gfx/tests/gtest/TestTreeTraversal.cpp')
| -rw-r--r-- | gfx/tests/gtest/TestTreeTraversal.cpp | 1413 |
1 files changed, 1413 insertions, 0 deletions
diff --git a/gfx/tests/gtest/TestTreeTraversal.cpp b/gfx/tests/gtest/TestTreeTraversal.cpp new file mode 100644 index 0000000000..215baeebf4 --- /dev/null +++ b/gfx/tests/gtest/TestTreeTraversal.cpp @@ -0,0 +1,1413 @@ +/* -*- 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> + +const int PERFORMANCE_TREE_DEPTH = 20; +const int PERFORMANCE_TREE_CHILD_COUNT = 2; +const int PERFORMANCE_TREE_LEAF_COUNT = 1048576; // 2 ** 20 +const int PERFORMANCE_REGION_XWRAP = 1024; + +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<T>() = 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<T>() = 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<T>() = 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; +} |