/* -*- 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;
}