// Copyright 2017-2022 The Verible Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "common/util/tree_operations.h"

#include <charconv>
#include <initializer_list>
#include <list>
#include <string>
#include <vector>

#include "absl/strings/str_cat.h"
#include "absl/strings/str_format.h"
#include "absl/strings/str_join.h"
#include "absl/strings/string_view.h"
#include "common/util/spacer.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"

namespace verible {
namespace {

// Recursively verifies two trees.
// Not intended for direct use - use the other VerifyTree with
// EXPECT_PRED_FORMAT2 instead.
template <typename T>
testing::AssertionResult VerifyTree(const T& actual, const T& expected,
                                    const std::vector<size_t>& path) {
  const bool id_ok = actual.id() == expected.id();
  const bool children_count_ok =
      actual.Children().size() == expected.Children().size();
  if (!id_ok || !children_count_ok) {
    auto err = testing::AssertionFailure();
    err << "Node mismatch at path: {"
        << absl::StrJoin(path.begin(), path.end(), ",") << "}\n";

    if (!id_ok) {
      err << "Invalid ID:\n"
          << "  Actual:   \"" << actual.id() << "\"\n"
          << "  Expected: \"" << expected.id() << "\"\n";
    }
    if (!children_count_ok) {
      err << "Invalid Children count:\n"
          << "  Actual:   " << actual.Children().size() << "\n"
          << "  Expected: " << expected.Children().size() << "\n";
    }
    return err;
  }
  if (actual.Children().size() != 0) {
    auto actual_child = actual.Children().begin();
    auto expected_child = expected.Children().begin();
    auto child_path = path;
    child_path.push_back(0);
    for (size_t i = 0; i < actual.Children().size(); ++i) {
      const auto result =
          VerifyTree(*actual_child, *expected_child, child_path);
      if (!result) return result;
      ++actual_child;
      ++expected_child;
      ++child_path.back();
    }
  }
  return testing::AssertionSuccess();
}

// Recursively verifies two trees.
// This verification function is intended for use with EXPECT_PRED_FORMAT2.
template <typename T>
testing::AssertionResult VerifyTree(const char* actual_expr,
                                    const char* expected_expr, const T& actual,
                                    const T& expected) {
  auto result = VerifyTree(actual, expected, {});
  if (!result) {
    result << "\n"
           << "Actual tree:\n"
           << actual << "\n"
           << "Expected tree:\n"
           << expected << "\n";
  }
  return result;
}

// Alias to `ThisType` if `Derived` is void; alias to `Derived` otherwise.
template <class Derived, class ThisType>
using DerivedOrThis =
    std::conditional_t<std::is_void_v<Derived>, ThisType, Derived>;

// Definitions of sample tree node types:

template <template <class...> class Container, class Derived = void>
class SimpleNode {
  using ThisType = DerivedOrThis<Derived, SimpleNode<Container, Derived>>;

 public:
  using ChildrenType = Container<ThisType>;

  SimpleNode(absl::string_view id, ChildrenType&& children = {})
      : children_(std::move(children)), id_(id) {
    Relink();
  }

  ChildrenType& Children() { return children_; }
  const ChildrenType& Children() const { return children_; }

  // Debug/test functions:

  const std::string& id() const { return id_; }

  void set_id(std::string&& new_id) { id_ = new_id; }

  bool operator==(const ThisType& other) const { return this == &other; }

  friend std::ostream& operator<<(std::ostream& stream, const ThisType& self) {
    self.PrintRecursively(stream, 0);
    return stream;
  }

  friend std::ostream& operator<<(std::ostream& stream,
                                  const ThisType* self_ptr) {
    if (self_ptr == nullptr) {
      return stream << "nullptr";
    }
    return stream << absl::StreamFormat("%p (%s; parent=%p)\n", self_ptr,
                                        self_ptr->id_, self_ptr->parent_);
  }

  // Updates parent pointers in children.
  void Relink() {
    for (auto& child : children_) {
      child.Relink();
      child.parent_ = static_cast<ThisType*>(this);
    }
  }

 protected:
  void PrintRecursively(std::ostream& stream, int depth = 0) const {
    stream << verible::Spacer(4 * depth)
           << absl::StreamFormat("@%p (%s; parent=%p)\n",
                                 static_cast<const ThisType*>(this), id_,
                                 parent_);
    for (const auto& child : Children()) {
      child.PrintRecursively(stream, depth + 1);
    }
  }

  ChildrenType children_;
  std::string id_;              // Exposed in subclasses as value
  ThisType* parent_ = nullptr;  // Exposed in subclasses
};

template <template <class...> class Container, class Derived = void>
class NodeWithValue
    : public SimpleNode<
          Container,
          DerivedOrThis<Derived, NodeWithValue<Container, Derived>>> {
  using ThisType = DerivedOrThis<Derived, NodeWithValue>;
  using Base = SimpleNode<Container, ThisType>;

 public:
  using Base::Base;
  using typename Base::ChildrenType;

  std::string& Value() { return this->id_; }
  const std::string& Value() const { return this->id_; }
};

template <template <class...> class Container, class Derived = void>
class NodeWithParent
    : public SimpleNode<
          Container,
          DerivedOrThis<Derived, NodeWithParent<Container, Derived>>> {
  using ThisType = DerivedOrThis<Derived, NodeWithParent>;
  using Base = SimpleNode<Container, ThisType>;

 public:
  using Base::Base;
  using typename Base::ChildrenType;

  ThisType* Parent() { return this->parent_; }
  const ThisType* Parent() const { return this->parent_; }
};

template <template <class...> class Container, class Derived = void>
class NodeWithParentAndValue
    : public NodeWithParent<
          Container,
          DerivedOrThis<Derived, NodeWithParentAndValue<Container, Derived>>> {
  using ThisType = DerivedOrThis<Derived, NodeWithParentAndValue>;
  using Base = NodeWithParent<Container, ThisType>;

 public:
  using Base::Base;
  using typename Base::ChildrenType;

  std::string& Value() { return this->id_; }
  const std::string& Value() const { return this->id_; }
};

// "Other" node type. Has different value type and is not related to other test
// trees.
class IntNode {
 public:
  IntNode() {}
  IntNode(int value, std::initializer_list<IntNode> children = {})
      : value_(value), children_(children) {}

  const int& Value() const { return value_; }

  const std::vector<IntNode>& Children() const { return children_; }
  std::vector<IntNode>& Children() { return children_; }

  const int& id() const { return value_; }

  friend std::ostream& operator<<(std::ostream& stream, const IntNode& self) {
    self.PrintRecursively(stream, 0);
    return stream;
  }

  friend std::ostream& operator<<(std::ostream& stream,
                                  const IntNode* self_ptr) {
    if (self_ptr == nullptr) {
      return stream << "nullptr";
    }
    return stream << absl::StreamFormat("%p (%d)\n", self_ptr,
                                        self_ptr->value_);
  }

 private:
  void PrintRecursively(std::ostream& stream, int depth = 0) const {
    stream << verible::Spacer(4 * depth)
           << absl::StreamFormat("@%p (%d)\n", this, value_);
    for (const auto& child : Children()) {
      child.PrintRecursively(stream, depth + 1);
    }
  }

  int value_;
  std::vector<IntNode> children_;
};

// Test suites:

template <class Node>
class TreeTest : public ::testing::Test {
 public:
  TreeTest() {}

  using N = Node;
  N root = N("root", {N("0"),                                          //
                      N("1", {N("1.0")}),                              //
                      N("2", {N("2.0", {N("2.0.0")}),                  //
                              N("2.1", {N("2.1.0")})}),                //
                      N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                        N("3.0.1", {N("3.0.1.0")})}),  //
                              N("3.1", {N("3.1.0", {N("3.1.0.0")}),    //
                                        N("3.1.1", {N("3.1.1.0")})}),  //
                              N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                        N("3.2.1", {N("3.2.1.0")})})})});

  Node& NodeAt(std::initializer_list<size_t> child_indexes) {
    Node* subnode = &root;
    for (auto index : child_indexes) {
      CHECK_GE(index, 0);
      CHECK_LT(index, subnode->Children().size());
      subnode = &*std::next(subnode->Children().begin(), index);
    }
    return *subnode;
  }
};

template <class Node>
class SimpleNodeTest : public TreeTest<Node> {};

using SimpleNodeTestTypes =
    ::testing::Types<SimpleNode<std::vector>,              //
                     NodeWithValue<std::vector>,           //
                     NodeWithParent<std::vector>,          //
                     NodeWithParentAndValue<std::vector>,  //

                     SimpleNode<std::list>,              //
                     NodeWithValue<std::list>,           //
                     NodeWithParent<std::list>,          //
                     NodeWithParentAndValue<std::list>,  //

                     const SimpleNode<std::vector>,              //
                     const NodeWithValue<std::vector>,           //
                     const NodeWithParent<std::vector>,          //
                     const NodeWithParentAndValue<std::vector>,  //

                     const SimpleNode<std::list>,      //
                     const NodeWithValue<std::list>,   //
                     const NodeWithParent<std::list>,  //
                     const NodeWithParentAndValue<std::list>>;
TYPED_TEST_SUITE(SimpleNodeTest, SimpleNodeTestTypes);

template <class Node>
class NodeWithValueTest : public TreeTest<Node> {};

using NodeWithValueTestTypes =
    ::testing::Types<NodeWithValue<std::vector>,           //
                     NodeWithParentAndValue<std::vector>,  //

                     NodeWithValue<std::list>,           //
                     NodeWithParentAndValue<std::list>,  //

                     const NodeWithValue<std::vector>,           //
                     const NodeWithParentAndValue<std::vector>,  //

                     const NodeWithValue<std::list>,  //
                     const NodeWithParentAndValue<std::list>>;
TYPED_TEST_SUITE(NodeWithValueTest, NodeWithValueTestTypes);

template <class Node>
class NodeWithParentTest : public TreeTest<Node> {};

using NodeWithParentTestTypes =
    ::testing::Types<NodeWithParent<std::vector>,          //
                     NodeWithParentAndValue<std::vector>,  //

                     NodeWithParent<std::list>,          //
                     NodeWithParentAndValue<std::list>,  //

                     const NodeWithParent<std::vector>,          //
                     const NodeWithParentAndValue<std::vector>,  //

                     const NodeWithParent<std::list>,  //
                     const NodeWithParentAndValue<std::list>>;
TYPED_TEST_SUITE(NodeWithParentTest, NodeWithParentTestTypes);

template <class Node>
class NodeWithParentAndValueTest : public TreeTest<Node> {};

using NodeWithParentAndValueTestTypes =
    ::testing::Types<NodeWithParentAndValue<std::vector>,        //
                     NodeWithParentAndValue<std::list>,          //
                     const NodeWithParentAndValue<std::vector>,  //
                     const NodeWithParentAndValue<std::list>>;
TYPED_TEST_SUITE(NodeWithParentAndValueTest, NodeWithParentAndValueTestTypes);

// Tests:

TEST(Misc, TreeNodeTraits) {
  struct NodeWithCustomContainerType {
    using subnodes_type = std::initializer_list<NodeWithCustomContainerType>;

    const std::vector<NodeWithCustomContainerType>& Children() const {
      return children_;
    }

   private:
    std::vector<NodeWithCustomContainerType> children_;
  };

  {
    using Traits = TreeNodeTraits<NodeWithCustomContainerType>;
    static_assert(Traits::available == true);
    static_assert(Traits::Children::available == true);

    static_assert(
        std::is_same_v<typename Traits::Children::container_type,
                       std::initializer_list<NodeWithCustomContainerType>>);
  }
  {
    using Traits = TreeNodeTraits<const NodeWithCustomContainerType>;
    static_assert(Traits::available == true);
    static_assert(Traits::Children::available == true);

    static_assert(
        std::is_same_v<typename Traits::Children::container_type,
                       std::initializer_list<NodeWithCustomContainerType>>);
  }
}

TYPED_TEST(SimpleNodeTest, TreeNodeTraits) {
  // This test passes if it compiles without errors.
  using Traits = TreeNodeTraits<TypeParam>;

  static_assert(Traits::available == true);
  static_assert(Traits::Children::available == true);

  static_assert(std::is_same_v<typename Traits::Children::container_type,
                               typename TypeParam::ChildrenType>);
}

TYPED_TEST(NodeWithValueTest, TreeNodeTraits) {
  // This test passes if it compiles without errors.
  using Traits = TreeNodeTraits<TypeParam>;

  static_assert(Traits::Value::available == true);

  static_assert(std::is_same_v<typename Traits::Value::type, std::string>);
  static_assert(
      std::is_same_v<typename Traits::Value::reference,
                     verible::match_const_t<std::string, TypeParam>&>);
  static_assert(std::is_same_v<typename Traits::Value::const_reference,
                               const std::string&>);
}

TYPED_TEST(NodeWithParentTest, TreeNodeTraits) {
  // This test passes if it compiles without errors.
  using Traits = TreeNodeTraits<TypeParam>;

  static_assert(Traits::Parent::available == true);
}

TYPED_TEST(SimpleNodeTest, is_leaf) {
  EXPECT_FALSE(is_leaf(this->root));
  EXPECT_TRUE(is_leaf(this->NodeAt({0})));
  EXPECT_FALSE(is_leaf(this->NodeAt({1})));
  EXPECT_TRUE(is_leaf(this->NodeAt({1, 0})));
  EXPECT_FALSE(is_leaf(this->NodeAt({2})));
  EXPECT_FALSE(is_leaf(this->NodeAt({2, 0})));
  EXPECT_TRUE(is_leaf(this->NodeAt({2, 0, 0})));
  EXPECT_FALSE(is_leaf(this->NodeAt({2, 1})));
  EXPECT_TRUE(is_leaf(this->NodeAt({2, 1, 0})));
  EXPECT_FALSE(is_leaf(this->NodeAt({3})));
  EXPECT_FALSE(is_leaf(this->NodeAt({3, 0})));
  EXPECT_FALSE(is_leaf(this->NodeAt({3, 0, 0})));
  EXPECT_TRUE(is_leaf(this->NodeAt({3, 0, 0, 0})));
  EXPECT_FALSE(is_leaf(this->NodeAt({3, 0, 1})));
  EXPECT_TRUE(is_leaf(this->NodeAt({3, 0, 1, 0})));
}

TYPED_TEST(SimpleNodeTest, DescendPath) {
  {
    const std::vector<size_t> path = {0};
    EXPECT_EQ(DescendPath(this->root, path.begin(), path.end()),
              this->NodeAt({0}));
  }
  {
    const std::vector<size_t> path = {1, 0};
    EXPECT_EQ(DescendPath(this->root, path.begin(), path.end()),
              this->NodeAt({1, 0}));
  }
  {
    const std::vector<size_t> path = {1};
    EXPECT_EQ(DescendPath(this->NodeAt({2}), path.begin(), path.end()),
              this->NodeAt({2, 1}));
  }
}

TYPED_TEST(SimpleNodeTest, LeftmostDescendant) {
  EXPECT_EQ(LeftmostDescendant(this->root), this->root.Children().front());
  EXPECT_EQ(LeftmostDescendant(this->root.Children().back()),
            this->NodeAt({3, 0, 0, 0}));
  EXPECT_EQ(LeftmostDescendant(this->NodeAt({2, 1, 0})),
            this->NodeAt({2, 1, 0}));
}

TYPED_TEST(SimpleNodeTest, RightmostDescendant) {
  EXPECT_EQ(RightmostDescendant(this->root), this->NodeAt({3, 2, 1, 0}));
  EXPECT_EQ(RightmostDescendant(this->root.Children().back()),
            this->NodeAt({3, 2, 1, 0}));
  EXPECT_EQ(RightmostDescendant(this->NodeAt({2, 1, 0})),
            this->NodeAt({2, 1, 0}));
}

TYPED_TEST(SimpleNodeTest, ApplyPreOrderWithNode) {
  using NodeRef = std::add_lvalue_reference_t<TypeParam>;
  {
    static const std::vector<std::string> expected_visited_values = {
        "root",    "0",       "1",     "1.0",     "2",     "2.0",     "2.0.0",
        "2.1",     "2.1.0",   "3",     "3.0",     "3.0.0", "3.0.0.0", "3.0.1",
        "3.0.1.0", "3.1",     "3.1.0", "3.1.0.0", "3.1.1", "3.1.1.0", "3.2",
        "3.2.0",   "3.2.0.0", "3.2.1", "3.2.1.0"};
    std::vector<std::string> visited_values;
    ApplyPreOrder(this->root,
                  [&](NodeRef node) { visited_values.push_back(node.id()); });
    EXPECT_EQ(visited_values, expected_visited_values);
  }

  // Test for mutable nodes only
  if constexpr (!std::is_const_v<TypeParam>) {
    // Modify
    ApplyPreOrder(this->root, [&](NodeRef node) {
      node.set_id(absl::StrCat(node.id(), "-new"));
    });
    // Verify
    static const std::vector<std::string> expected_visited_values = {
        "root-new", "0-new",     "1-new",       "1.0-new",   "2-new",
        "2.0-new",  "2.0.0-new", "2.1-new",     "2.1.0-new", "3-new",
        "3.0-new",  "3.0.0-new", "3.0.0.0-new", "3.0.1-new", "3.0.1.0-new",
        "3.1-new",  "3.1.0-new", "3.1.0.0-new", "3.1.1-new", "3.1.1.0-new",
        "3.2-new",  "3.2.0-new", "3.2.0.0-new", "3.2.1-new", "3.2.1.0-new"};
    std::vector<std::string> visited_values;
    ApplyPreOrder(this->root,
                  [&](NodeRef node) { visited_values.push_back(node.id()); });

    EXPECT_EQ(visited_values, expected_visited_values);
  }
}

TYPED_TEST(SimpleNodeTest, ApplyPostOrderWithNode) {
  using NodeRef = std::add_lvalue_reference_t<TypeParam>;
  {
    static const std::vector<std::string> expected_visited_values = {
        "0",     "1.0",     "1",     "2.0.0",   "2.0",     "2.1.0", "2.1",
        "2",     "3.0.0.0", "3.0.0", "3.0.1.0", "3.0.1",   "3.0",   "3.1.0.0",
        "3.1.0", "3.1.1.0", "3.1.1", "3.1",     "3.2.0.0", "3.2.0", "3.2.1.0",
        "3.2.1", "3.2",     "3",     "root"};
    std::vector<std::string> visited_values;
    ApplyPostOrder(this->root,
                   [&](NodeRef node) { visited_values.push_back(node.id()); });
    EXPECT_EQ(visited_values, expected_visited_values);
  }
  // Test for mutable nodes only
  if constexpr (!std::is_const_v<TypeParam>) {
    // Modify
    ApplyPostOrder(this->root, [&](NodeRef node) {
      node.set_id(absl::StrCat(node.id(), "-new"));
    });
    // Verify
    static const std::vector<std::string> expected_visited_values = {
        "0-new",       "1.0-new",   "1-new",   "2.0.0-new",   "2.0-new",
        "2.1.0-new",   "2.1-new",   "2-new",   "3.0.0.0-new", "3.0.0-new",
        "3.0.1.0-new", "3.0.1-new", "3.0-new", "3.1.0.0-new", "3.1.0-new",
        "3.1.1.0-new", "3.1.1-new", "3.1-new", "3.2.0.0-new", "3.2.0-new",
        "3.2.1.0-new", "3.2.1-new", "3.2-new", "3-new",       "root-new"};
    std::vector<std::string> visited_values;
    ApplyPostOrder(this->root,
                   [&](NodeRef node) { visited_values.push_back(node.id()); });

    EXPECT_EQ(visited_values, expected_visited_values);
  }
}

TYPED_TEST(NodeWithValueTest, ApplyPreOrderWithValue) {
  {
    static const std::vector<std::string> expected_visited_values = {
        "root",    "0",       "1",     "1.0",     "2",     "2.0",     "2.0.0",
        "2.1",     "2.1.0",   "3",     "3.0",     "3.0.0", "3.0.0.0", "3.0.1",
        "3.0.1.0", "3.1",     "3.1.0", "3.1.0.0", "3.1.1", "3.1.1.0", "3.2",
        "3.2.0",   "3.2.0.0", "3.2.1", "3.2.1.0"};
    std::vector<std::string> visited_values;
    ApplyPreOrder(this->root, [&](const std::string& value) {
      visited_values.push_back(value);
    });
    EXPECT_EQ(visited_values, expected_visited_values);
  }

  // Test for mutable nodes only
  if constexpr (!std::is_const_v<TypeParam>) {
    // Modify
    ApplyPreOrder(this->root,
                  [&](std::string& value) { absl::StrAppend(&value, "-new"); });
    // Verify
    static const std::vector<std::string> expected_visited_values = {
        "root-new", "0-new",     "1-new",       "1.0-new",   "2-new",
        "2.0-new",  "2.0.0-new", "2.1-new",     "2.1.0-new", "3-new",
        "3.0-new",  "3.0.0-new", "3.0.0.0-new", "3.0.1-new", "3.0.1.0-new",
        "3.1-new",  "3.1.0-new", "3.1.0.0-new", "3.1.1-new", "3.1.1.0-new",
        "3.2-new",  "3.2.0-new", "3.2.0.0-new", "3.2.1-new", "3.2.1.0-new"};
    std::vector<std::string> visited_values;
    ApplyPreOrder(this->root, [&](const std::string& value) {
      visited_values.push_back(value);
    });

    EXPECT_EQ(visited_values, expected_visited_values);
  }
}

TYPED_TEST(NodeWithValueTest, ApplyPostOrderWithValue) {
  {
    static const std::vector<std::string> expected_visited_values = {
        "0",     "1.0",     "1",     "2.0.0",   "2.0",     "2.1.0", "2.1",
        "2",     "3.0.0.0", "3.0.0", "3.0.1.0", "3.0.1",   "3.0",   "3.1.0.0",
        "3.1.0", "3.1.1.0", "3.1.1", "3.1",     "3.2.0.0", "3.2.0", "3.2.1.0",
        "3.2.1", "3.2",     "3",     "root"};
    std::vector<std::string> visited_values;
    ApplyPostOrder(this->root, [&](const std::string& value) {
      visited_values.push_back(value);
    });
    EXPECT_EQ(visited_values, expected_visited_values);
  }

  // Test for mutable nodes only
  if constexpr (!std::is_const_v<TypeParam>) {
    // Modify
    ApplyPostOrder(this->root, [&](std::string& value) {
      absl::StrAppend(&value, "-new");
    });
    // Verify
    static const std::vector<std::string> expected_visited_values = {
        "0-new",       "1.0-new",   "1-new",   "2.0.0-new",   "2.0-new",
        "2.1.0-new",   "2.1-new",   "2-new",   "3.0.0.0-new", "3.0.0-new",
        "3.0.1.0-new", "3.0.1-new", "3.0-new", "3.1.0.0-new", "3.1.0-new",
        "3.1.1.0-new", "3.1.1-new", "3.1-new", "3.2.0.0-new", "3.2.0-new",
        "3.2.1.0-new", "3.2.1-new", "3.2-new", "3-new",       "root-new"};
    std::vector<std::string> visited_values;
    ApplyPostOrder(this->root, [&](const std::string& value) {
      visited_values.push_back(value);
    });

    EXPECT_EQ(visited_values, expected_visited_values);
  }
}

TYPED_TEST(NodeWithParentTest, BirthRank) {
  EXPECT_EQ(BirthRank(this->root), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({1})), 1);
  EXPECT_EQ(BirthRank(this->NodeAt({1, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({2})), 2);
  EXPECT_EQ(BirthRank(this->NodeAt({2, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({2, 0, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({2, 1})), 1);
  EXPECT_EQ(BirthRank(this->NodeAt({2, 1, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({3})), 3);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 0, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 0, 0, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 0, 1})), 1);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 0, 1, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 1})), 1);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 1, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 1, 0, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 1, 1})), 1);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 1, 1, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 2})), 2);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 2, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 2, 0, 0})), 0);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 2, 1})), 1);
  EXPECT_EQ(BirthRank(this->NodeAt({3, 2, 1, 0})), 0);
}

TYPED_TEST(NodeWithParentTest, NumAncestors) {
  EXPECT_EQ(NumAncestors(this->root), 0);
  EXPECT_EQ(NumAncestors(this->NodeAt({0})), 1);
  EXPECT_EQ(NumAncestors(this->NodeAt({1})), 1);
  EXPECT_EQ(NumAncestors(this->NodeAt({1, 0})), 2);
  EXPECT_EQ(NumAncestors(this->NodeAt({2})), 1);
  EXPECT_EQ(NumAncestors(this->NodeAt({2, 0})), 2);
  EXPECT_EQ(NumAncestors(this->NodeAt({2, 0, 0})), 3);
  EXPECT_EQ(NumAncestors(this->NodeAt({2, 1})), 2);
  EXPECT_EQ(NumAncestors(this->NodeAt({2, 1, 0})), 3);
  EXPECT_EQ(NumAncestors(this->NodeAt({3})), 1);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 0})), 2);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 0, 0})), 3);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 0, 0, 0})), 4);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 0, 1})), 3);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 0, 1, 0})), 4);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 1})), 2);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 1, 0})), 3);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 1, 0, 0})), 4);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 1, 1})), 3);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 1, 1, 0})), 4);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 2})), 2);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 2, 0})), 3);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 2, 0, 0})), 4);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 2, 1})), 3);
  EXPECT_EQ(NumAncestors(this->NodeAt({3, 2, 1, 0})), 4);
}

TYPED_TEST(NodeWithParentTest, Root) {
  EXPECT_EQ(Root(this->root), this->root);
  EXPECT_EQ(Root(this->NodeAt({0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({1})), this->root);
  EXPECT_EQ(Root(this->NodeAt({1, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({2})), this->root);
  EXPECT_EQ(Root(this->NodeAt({2, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({2, 0, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({2, 1})), this->root);
  EXPECT_EQ(Root(this->NodeAt({2, 1, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 0, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 0, 0, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 0, 1})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 0, 1, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 1})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 1, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 1, 0, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 1, 1})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 1, 1, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 2})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 2, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 2, 0, 0})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 2, 1})), this->root);
  EXPECT_EQ(Root(this->NodeAt({3, 2, 1, 0})), this->root);
}

TYPED_TEST(NodeWithParentTest, IsFirstChild) {
  EXPECT_TRUE(IsFirstChild(this->root));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({0})));
  EXPECT_FALSE(IsFirstChild(this->NodeAt({1})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({1, 0})));
  EXPECT_FALSE(IsFirstChild(this->NodeAt({2})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({2, 0})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({2, 0, 0})));
  EXPECT_FALSE(IsFirstChild(this->NodeAt({2, 1})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({2, 1, 0})));
  EXPECT_FALSE(IsFirstChild(this->NodeAt({3})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({3, 0})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({3, 0, 0})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({3, 0, 0, 0})));
  EXPECT_FALSE(IsFirstChild(this->NodeAt({3, 0, 1})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({3, 0, 1, 0})));
  EXPECT_FALSE(IsFirstChild(this->NodeAt({3, 1})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({3, 1, 0})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({3, 1, 0, 0})));
  EXPECT_FALSE(IsFirstChild(this->NodeAt({3, 1, 1})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({3, 1, 1, 0})));
  EXPECT_FALSE(IsFirstChild(this->NodeAt({3, 2})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({3, 2, 0})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({3, 2, 0, 0})));
  EXPECT_FALSE(IsFirstChild(this->NodeAt({3, 2, 1})));
  EXPECT_TRUE(IsFirstChild(this->NodeAt({3, 2, 1, 0})));
}

TYPED_TEST(NodeWithParentTest, IsLastChild) {
  EXPECT_TRUE(IsLastChild(this->root));
  EXPECT_FALSE(IsLastChild(this->NodeAt({0})));
  EXPECT_FALSE(IsLastChild(this->NodeAt({1})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({1, 0})));
  EXPECT_FALSE(IsLastChild(this->NodeAt({2})));
  EXPECT_FALSE(IsLastChild(this->NodeAt({2, 0})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({2, 0, 0})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({2, 1})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({2, 1, 0})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3})));
  EXPECT_FALSE(IsLastChild(this->NodeAt({3, 0})));
  EXPECT_FALSE(IsLastChild(this->NodeAt({3, 0, 0})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3, 0, 0, 0})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3, 0, 1})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3, 0, 1, 0})));
  EXPECT_FALSE(IsLastChild(this->NodeAt({3, 1})));
  EXPECT_FALSE(IsLastChild(this->NodeAt({3, 1, 0})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3, 1, 0, 0})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3, 1, 1})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3, 1, 1, 0})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3, 2})));
  EXPECT_FALSE(IsLastChild(this->NodeAt({3, 2, 0})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3, 2, 0, 0})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3, 2, 1})));
  EXPECT_TRUE(IsLastChild(this->NodeAt({3, 2, 1, 0})));
}

TYPED_TEST(NodeWithParentTest, HasAncestor) {
  EXPECT_FALSE(HasAncestor(this->root, &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({1}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({1, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({2}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({2, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({2, 0, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({2, 1}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({2, 1, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 0, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 0, 0, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 0, 1}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 0, 1, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 1}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 1, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 1, 0, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 1, 1}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 1, 1, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 2}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 2, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 2, 0, 0}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 2, 1}), &this->root));
  EXPECT_TRUE(HasAncestor(this->NodeAt({3, 2, 1, 0}), &this->root));

  EXPECT_FALSE(HasAncestor(this->root, &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({1}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({1, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({2}), &this->NodeAt({2})));
  EXPECT_TRUE(HasAncestor(this->NodeAt({2, 0}), &this->NodeAt({2})));
  EXPECT_TRUE(HasAncestor(this->NodeAt({2, 0, 0}), &this->NodeAt({2})));
  EXPECT_TRUE(HasAncestor(this->NodeAt({2, 1}), &this->NodeAt({2})));
  EXPECT_TRUE(HasAncestor(this->NodeAt({2, 1, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 0, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 0, 0, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 0, 1}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 0, 1, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 1}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 1, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 1, 0, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 1, 1}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 1, 1, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 2}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 2, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 2, 0, 0}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 2, 1}), &this->NodeAt({2})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 2, 1, 0}), &this->NodeAt({2})));

  EXPECT_FALSE(HasAncestor(this->root, &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({1}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({1, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({2}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({2, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({2, 0, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({2, 1}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({2, 1, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 0, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 0, 0, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 0, 1}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 0, 1, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 1}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 1, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 1, 0, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 1, 1}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 1, 1, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 2}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 2, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 2, 0, 0}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 2, 1}), &this->NodeAt({1, 0})));
  EXPECT_FALSE(HasAncestor(this->NodeAt({3, 2, 1, 0}), &this->NodeAt({1, 0})));
}

template <class TestSuite>
void TestPath(TestSuite* test_suite, std::initializer_list<size_t> node_path) {
  auto& node = test_suite->NodeAt(node_path);
  {
    std::vector<size_t> calculated_path;
    Path(node, calculated_path);
    EXPECT_THAT(calculated_path, ::testing::ElementsAreArray(node_path))
        << "Path container: std::vector<size_t>";
  }
  {
    std::list<size_t> calculated_path;
    Path(node, calculated_path);
    EXPECT_THAT(calculated_path, ::testing::ElementsAreArray(node_path))
        << "Path container: std::list<size_t>";
  }
}

TYPED_TEST(NodeWithParentTest, Path) {
  TestPath(this, {});
  TestPath(this, {0});
  TestPath(this, {1});
  TestPath(this, {1, 0});
  TestPath(this, {2});
  TestPath(this, {2, 0});
  TestPath(this, {2, 0, 0});
  TestPath(this, {2, 1});
  TestPath(this, {2, 1, 0});
  TestPath(this, {3});
  TestPath(this, {3, 0});
  TestPath(this, {3, 0, 0});
  TestPath(this, {3, 0, 0, 0});
  TestPath(this, {3, 0, 1});
  TestPath(this, {3, 0, 1, 0});
  TestPath(this, {3, 1});
  TestPath(this, {3, 1, 0});
  TestPath(this, {3, 1, 0, 0});
  TestPath(this, {3, 1, 1});
  TestPath(this, {3, 1, 1, 0});
  TestPath(this, {3, 2});
  TestPath(this, {3, 2, 0});
  TestPath(this, {3, 2, 0, 0});
  TestPath(this, {3, 2, 1});
  TestPath(this, {3, 2, 1, 0});
}

template <class TestSuite>
void TestNodePath(TestSuite* test_suite,
                  std::initializer_list<size_t> node_path,
                  absl::string_view expected_string) {
  auto& node = test_suite->NodeAt(node_path);
  std::ostringstream output;
  output << NodePath(node);
  EXPECT_EQ(output.str(), expected_string);
}

TYPED_TEST(NodeWithParentTest, NodePath) {
  TestNodePath(this, {}, "{}");
  TestNodePath(this, {0}, "{0}");
  TestNodePath(this, {1}, "{1}");
  TestNodePath(this, {1, 0}, "{1,0}");
  TestNodePath(this, {2}, "{2}");
  TestNodePath(this, {2, 0}, "{2,0}");
  TestNodePath(this, {2, 0, 0}, "{2,0,0}");
  TestNodePath(this, {2, 1}, "{2,1}");
  TestNodePath(this, {2, 1, 0}, "{2,1,0}");
  TestNodePath(this, {3}, "{3}");
  TestNodePath(this, {3, 0}, "{3,0}");
  TestNodePath(this, {3, 0, 0}, "{3,0,0}");
  TestNodePath(this, {3, 0, 0, 0}, "{3,0,0,0}");
  TestNodePath(this, {3, 0, 1}, "{3,0,1}");
  TestNodePath(this, {3, 0, 1, 0}, "{3,0,1,0}");
  TestNodePath(this, {3, 1}, "{3,1}");
  TestNodePath(this, {3, 1, 0}, "{3,1,0}");
  TestNodePath(this, {3, 1, 0, 0}, "{3,1,0,0}");
  TestNodePath(this, {3, 1, 1}, "{3,1,1}");
  TestNodePath(this, {3, 1, 1, 0}, "{3,1,1,0}");
  TestNodePath(this, {3, 2}, "{3,2}");
  TestNodePath(this, {3, 2, 0}, "{3,2,0}");
  TestNodePath(this, {3, 2, 0, 0}, "{3,2,0,0}");
  TestNodePath(this, {3, 2, 1}, "{3,2,1}");
  TestNodePath(this, {3, 2, 1, 0}, "{3,2,1,0}");
}

TYPED_TEST(NodeWithValueTest, PrintTreeWithCustomPrinter) {
  {
    std::ostringstream output;
    PrintTree(
        this->root, &output,
        [](std::ostream& stream, const std::string& value) -> std::ostream& {
          return stream << "value=" << value;
        });
    static const absl::string_view expected_output =
        "{ (value=root)\n"
        "  { (value=0) }\n"
        "  { (value=1)\n"
        "    { (value=1.0) }\n"
        "  }\n"
        "  { (value=2)\n"
        "    { (value=2.0)\n"
        "      { (value=2.0.0) }\n"
        "    }\n"
        "    { (value=2.1)\n"
        "      { (value=2.1.0) }\n"
        "    }\n"
        "  }\n"
        "  { (value=3)\n"
        "    { (value=3.0)\n"
        "      { (value=3.0.0)\n"
        "        { (value=3.0.0.0) }\n"
        "      }\n"
        "      { (value=3.0.1)\n"
        "        { (value=3.0.1.0) }\n"
        "      }\n"
        "    }\n"
        "    { (value=3.1)\n"
        "      { (value=3.1.0)\n"
        "        { (value=3.1.0.0) }\n"
        "      }\n"
        "      { (value=3.1.1)\n"
        "        { (value=3.1.1.0) }\n"
        "      }\n"
        "    }\n"
        "    { (value=3.2)\n"
        "      { (value=3.2.0)\n"
        "        { (value=3.2.0.0) }\n"
        "      }\n"
        "      { (value=3.2.1)\n"
        "        { (value=3.2.1.0) }\n"
        "      }\n"
        "    }\n"
        "  }\n"
        "}";
    EXPECT_EQ(output.str(), expected_output);
  }
  {
    std::ostringstream output;
    PrintTree(
        this->NodeAt({3, 1}), &output,
        [](std::ostream& stream, const std::string& value) -> std::ostream& {
          return stream << "value=" << value;
        });
    static const absl::string_view expected_output =
        "{ (value=3.1)\n"
        "  { (value=3.1.0)\n"
        "    { (value=3.1.0.0) }\n"
        "  }\n"
        "  { (value=3.1.1)\n"
        "    { (value=3.1.1.0) }\n"
        "  }\n"
        "}";
    EXPECT_EQ(output.str(), expected_output);
  }
}

TYPED_TEST(NodeWithValueTest, PrintTree) {
  {
    std::ostringstream output;
    PrintTree(this->root, &output);
    static const absl::string_view expected_output =
        "{ (root)\n"
        "  { (0) }\n"
        "  { (1)\n"
        "    { (1.0) }\n"
        "  }\n"
        "  { (2)\n"
        "    { (2.0)\n"
        "      { (2.0.0) }\n"
        "    }\n"
        "    { (2.1)\n"
        "      { (2.1.0) }\n"
        "    }\n"
        "  }\n"
        "  { (3)\n"
        "    { (3.0)\n"
        "      { (3.0.0)\n"
        "        { (3.0.0.0) }\n"
        "      }\n"
        "      { (3.0.1)\n"
        "        { (3.0.1.0) }\n"
        "      }\n"
        "    }\n"
        "    { (3.1)\n"
        "      { (3.1.0)\n"
        "        { (3.1.0.0) }\n"
        "      }\n"
        "      { (3.1.1)\n"
        "        { (3.1.1.0) }\n"
        "      }\n"
        "    }\n"
        "    { (3.2)\n"
        "      { (3.2.0)\n"
        "        { (3.2.0.0) }\n"
        "      }\n"
        "      { (3.2.1)\n"
        "        { (3.2.1.0) }\n"
        "      }\n"
        "    }\n"
        "  }\n"
        "}";
    EXPECT_EQ(output.str(), expected_output);
  }
  {
    std::ostringstream output;
    PrintTree(this->NodeAt({3, 1}), &output);
    static const absl::string_view expected_output =
        "{ (3.1)\n"
        "  { (3.1.0)\n"
        "    { (3.1.0.0) }\n"
        "  }\n"
        "  { (3.1.1)\n"
        "    { (3.1.1.0) }\n"
        "  }\n"
        "}";
    EXPECT_EQ(output.str(), expected_output);
  }
}

TYPED_TEST(NodeWithParentTest, NextSibling) {
  EXPECT_EQ(NextSibling(this->root), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({0})), &this->NodeAt({1}));
  EXPECT_EQ(NextSibling(this->NodeAt({1})), &this->NodeAt({2}));
  EXPECT_EQ(NextSibling(this->NodeAt({1, 0})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({2})), &this->NodeAt({3}));
  EXPECT_EQ(NextSibling(this->NodeAt({2, 0})), &this->NodeAt({2, 1}));
  EXPECT_EQ(NextSibling(this->NodeAt({2, 0, 0})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({2, 1})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({2, 1, 0})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3, 0})), &this->NodeAt({3, 1}));
  EXPECT_EQ(NextSibling(this->NodeAt({3, 0, 0})), &this->NodeAt({3, 0, 1}));
  EXPECT_EQ(NextSibling(this->NodeAt({3, 0, 0, 0})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3, 0, 1})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3, 0, 1, 0})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3, 1})), &this->NodeAt({3, 2}));
  EXPECT_EQ(NextSibling(this->NodeAt({3, 1, 0})), &this->NodeAt({3, 1, 1}));
  EXPECT_EQ(NextSibling(this->NodeAt({3, 1, 0, 0})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3, 1, 1})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3, 1, 1, 0})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3, 2})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3, 2, 0})), &this->NodeAt({3, 2, 1}));
  EXPECT_EQ(NextSibling(this->NodeAt({3, 2, 0, 0})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3, 2, 1})), nullptr);
  EXPECT_EQ(NextSibling(this->NodeAt({3, 2, 1, 0})), nullptr);
}

TYPED_TEST(NodeWithParentTest, PreviousSibling) {
  EXPECT_EQ(PreviousSibling(this->root), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({1})), &this->NodeAt({0}));
  EXPECT_EQ(PreviousSibling(this->NodeAt({1, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({2})), &this->NodeAt({1}));
  EXPECT_EQ(PreviousSibling(this->NodeAt({2, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({2, 0, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({2, 1})), &this->NodeAt({2, 0}));
  EXPECT_EQ(PreviousSibling(this->NodeAt({2, 1, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({3})), &this->NodeAt({2}));
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 0, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 0, 0, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 0, 1})), &this->NodeAt({3, 0, 0}));
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 0, 1, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 1})), &this->NodeAt({3, 0}));
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 1, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 1, 0, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 1, 1})), &this->NodeAt({3, 1, 0}));
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 1, 1, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 2})), &this->NodeAt({3, 1}));
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 2, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 2, 0, 0})), nullptr);
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 2, 1})), &this->NodeAt({3, 2, 0}));
  EXPECT_EQ(PreviousSibling(this->NodeAt({3, 2, 1, 0})), nullptr);
}

TYPED_TEST(NodeWithParentTest, NextLeaf) {
  EXPECT_EQ(NextLeaf(this->root), nullptr);
  EXPECT_EQ(NextLeaf(this->NodeAt({0})), &this->NodeAt({1, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({1})), &this->NodeAt({2, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({1, 0})), &this->NodeAt({2, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({2})), &this->NodeAt({3, 0, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({2, 0})), &this->NodeAt({2, 1, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({2, 0, 0})), &this->NodeAt({2, 1, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({2, 1})), &this->NodeAt({3, 0, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({2, 1, 0})), &this->NodeAt({3, 0, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3})), nullptr);
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 0})), &this->NodeAt({3, 1, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 0, 0})), &this->NodeAt({3, 0, 1, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 0, 0, 0})), &this->NodeAt({3, 0, 1, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 0, 1})), &this->NodeAt({3, 1, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 0, 1, 0})), &this->NodeAt({3, 1, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 1})), &this->NodeAt({3, 2, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 1, 0})), &this->NodeAt({3, 1, 1, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 1, 0, 0})), &this->NodeAt({3, 1, 1, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 1, 1})), &this->NodeAt({3, 2, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 1, 1, 0})), &this->NodeAt({3, 2, 0, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 2})), nullptr);
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 2, 0})), &this->NodeAt({3, 2, 1, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 2, 0, 0})), &this->NodeAt({3, 2, 1, 0}));
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 2, 1})), nullptr);
  EXPECT_EQ(NextLeaf(this->NodeAt({3, 2, 1, 0})), nullptr);
}

TYPED_TEST(NodeWithParentTest, PreviousLeaf) {
  EXPECT_EQ(PreviousLeaf(this->root), nullptr);
  EXPECT_EQ(PreviousLeaf(this->NodeAt({0})), nullptr);
  EXPECT_EQ(PreviousLeaf(this->NodeAt({1})), &this->NodeAt({0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({1, 0})), &this->NodeAt({0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({2})), &this->NodeAt({1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({2, 0})), &this->NodeAt({1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({2, 0, 0})), &this->NodeAt({1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({2, 1})), &this->NodeAt({2, 0, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({2, 1, 0})), &this->NodeAt({2, 0, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3})), &this->NodeAt({2, 1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 0})), &this->NodeAt({2, 1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 0, 0})), &this->NodeAt({2, 1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 0, 0, 0})), &this->NodeAt({2, 1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 0, 1})), &this->NodeAt({3, 0, 0, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 0, 1, 0})),
            &this->NodeAt({3, 0, 0, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 1})), &this->NodeAt({3, 0, 1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 1, 0})), &this->NodeAt({3, 0, 1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 1, 0, 0})),
            &this->NodeAt({3, 0, 1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 1, 1})), &this->NodeAt({3, 1, 0, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 1, 1, 0})),
            &this->NodeAt({3, 1, 0, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 2})), &this->NodeAt({3, 1, 1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 2, 0})), &this->NodeAt({3, 1, 1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 2, 0, 0})),
            &this->NodeAt({3, 1, 1, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 2, 1})), &this->NodeAt({3, 2, 0, 0}));
  EXPECT_EQ(PreviousLeaf(this->NodeAt({3, 2, 1, 0})),
            &this->NodeAt({3, 2, 0, 0}));
}

TYPED_TEST(NodeWithParentTest, RemoveSelfFromParent) {
  using N = TypeParam;
  // Const nodes are not supported
  if constexpr (!std::is_const_v<TypeParam>) {
    RemoveSelfFromParent(this->NodeAt({2}));
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                          //
                   N("1", {N("1.0")}),                              //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                     N("3.0.1", {N("3.0.1.0")})}),  //
                           N("3.1", {N("3.1.0", {N("3.1.0.0")}),    //
                                     N("3.1.1", {N("3.1.1.0")})}),  //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                     N("3.2.1", {N("3.2.1.0")})})})}));
    this->root.Relink();
    RemoveSelfFromParent(this->NodeAt({2, 1}));
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                          //
                   N("1", {N("1.0")}),                              //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                     N("3.0.1", {N("3.0.1.0")})}),  //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                     N("3.2.1", {N("3.2.1.0")})})})}));
    this->root.Relink();
    RemoveSelfFromParent(this->NodeAt({0}));
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("1", {N("1.0")}),                              //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                     N("3.0.1", {N("3.0.1.0")})}),  //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                     N("3.2.1", {N("3.2.1.0")})})})}));
  }
}

TYPED_TEST(SimpleNodeTest, HoistOnlyChild) {
  using N = TypeParam;
  // Const nodes are not supported
  if constexpr (!std::is_const_v<TypeParam>) {
    HoistOnlyChild(this->NodeAt({2, 0}));
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                          //
                   N("1", {N("1.0")}),                              //
                   N("2", {N("2.0.0"),                              //
                           N("2.1", {N("2.1.0")})}),                //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                     N("3.0.1", {N("3.0.1.0")})}),  //
                           N("3.1", {N("3.1.0", {N("3.1.0.0")}),    //
                                     N("3.1.1", {N("3.1.1.0")})}),  //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                     N("3.2.1", {N("3.2.1.0")})})})}));

    HoistOnlyChild(this->NodeAt({3}));
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                          //
                   N("1", {N("1.0")}),                              //
                   N("2", {N("2.0.0"),                              //
                           N("2.1", {N("2.1.0")})}),                //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                     N("3.0.1", {N("3.0.1.0")})}),  //
                           N("3.1", {N("3.1.0", {N("3.1.0.0")}),    //
                                     N("3.1.1", {N("3.1.1.0")})}),  //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                     N("3.2.1", {N("3.2.1.0")})})})}));

    // remove "3.1" and "3.2"
    this->NodeAt({3}).Children().erase(
        std::next(this->NodeAt({3}).Children().begin(), 1),
        this->NodeAt({3}).Children().end());
    // remove "3.0.1"
    this->NodeAt({3, 0}).Children().erase(
        std::next(this->NodeAt({3, 0}).Children().begin(), 1));

    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                            //
                   N("1", {N("1.0")}),                //
                   N("2", {N("2.0.0"),                //
                           N("2.1", {N("2.1.0")})}),  //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")})})})}));

    HoistOnlyChild(this->NodeAt({3}));
    EXPECT_PRED_FORMAT2(VerifyTree, this->root,
                        N("root", {N("0"),                            //
                                   N("1", {N("1.0")}),                //
                                   N("2", {N("2.0.0"),                //
                                           N("2.1", {N("2.1.0")})}),  //
                                   N("3.0", {N("3.0.0", {N("3.0.0.0")})})}));

    HoistOnlyChild(this->NodeAt({3}));
    EXPECT_PRED_FORMAT2(VerifyTree, this->root,
                        N("root", {N("0"),                            //
                                   N("1", {N("1.0")}),                //
                                   N("2", {N("2.0.0"),                //
                                           N("2.1", {N("2.1.0")})}),  //
                                   N("3.0.0", {N("3.0.0.0")})}));

    HoistOnlyChild(this->NodeAt({3}));
    EXPECT_PRED_FORMAT2(VerifyTree, this->root,
                        N("root", {N("0"),                            //
                                   N("1", {N("1.0")}),                //
                                   N("2", {N("2.0.0"),                //
                                           N("2.1", {N("2.1.0")})}),  //
                                   N("3.0.0.0")}));
  }
}

TYPED_TEST(SimpleNodeTest, FlattenOnce) {
  using N = TypeParam;
  // Const nodes are not supported
  if constexpr (!std::is_const_v<TypeParam>) {
    FlattenOnce(this->NodeAt({3}));
    EXPECT_PRED_FORMAT2(VerifyTree, this->root,
                        N("root", {N("0"),                              //
                                   N("1", {N("1.0")}),                  //
                                   N("2", {N("2.0", {N("2.0.0")}),      //
                                           N("2.1", {N("2.1.0")})}),    //
                                   N("3", {N("3.0.0", {N("3.0.0.0")}),  //
                                           N("3.0.1", {N("3.0.1.0")}),  //
                                           N("3.1.0", {N("3.1.0.0")}),  //
                                           N("3.1.1", {N("3.1.1.0")}),  //
                                           N("3.2.0", {N("3.2.0.0")}),  //
                                           N("3.2.1", {N("3.2.1.0")})})}));

    // This should change nothing
    FlattenOnce(this->NodeAt({0}));
    EXPECT_PRED_FORMAT2(VerifyTree, this->root,
                        N("root", {N("0"),                              //
                                   N("1", {N("1.0")}),                  //
                                   N("2", {N("2.0", {N("2.0.0")}),      //
                                           N("2.1", {N("2.1.0")})}),    //
                                   N("3", {N("3.0.0", {N("3.0.0.0")}),  //
                                           N("3.0.1", {N("3.0.1.0")}),  //
                                           N("3.1.0", {N("3.1.0.0")}),  //
                                           N("3.1.1", {N("3.1.1.0")}),  //
                                           N("3.2.0", {N("3.2.0.0")}),  //
                                           N("3.2.1", {N("3.2.1.0")})})}));

    FlattenOnce(this->root);
    EXPECT_PRED_FORMAT2(VerifyTree, this->root,
                        N("root", {                             //
                                   N("1.0"),                    //
                                   N("2.0", {N("2.0.0")}),      //
                                   N("2.1", {N("2.1.0")}),      //
                                   N("3.0.0", {N("3.0.0.0")}),  //
                                   N("3.0.1", {N("3.0.1.0")}),  //
                                   N("3.1.0", {N("3.1.0.0")}),  //
                                   N("3.1.1", {N("3.1.1.0")}),  //
                                   N("3.2.0", {N("3.2.0.0")}),  //
                                   N("3.2.1", {N("3.2.1.0")})}));
  }
}

TYPED_TEST(SimpleNodeTest, FlattenOnlyChildrenWithChildren) {
  using N = TypeParam;
  // Const nodes are not supported
  if constexpr (!std::is_const_v<TypeParam>) {
    FlattenOnlyChildrenWithChildren(this->root);
    EXPECT_PRED_FORMAT2(VerifyTree, this->root,
                        N("root", {N("0"),                                  //
                                   N("1.0"),                                //
                                   N("2.0", {N("2.0.0")}),                  //
                                   N("2.1", {N("2.1.0")}),                  //
                                   N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                             N("3.0.1", {N("3.0.1.0")})}),  //
                                   N("3.1", {N("3.1.0", {N("3.1.0.0")}),    //
                                             N("3.1.1", {N("3.1.1.0")})}),  //
                                   N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                             N("3.2.1", {N("3.2.1.0")})})}));

    // This should change nothing
    FlattenOnlyChildrenWithChildren(this->NodeAt({0}));
    EXPECT_PRED_FORMAT2(VerifyTree, this->root,
                        N("root", {N("0"),                                  //
                                   N("1.0"),                                //
                                   N("2.0", {N("2.0.0")}),                  //
                                   N("2.1", {N("2.1.0")}),                  //
                                   N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                             N("3.0.1", {N("3.0.1.0")})}),  //
                                   N("3.1", {N("3.1.0", {N("3.1.0.0")}),    //
                                             N("3.1.1", {N("3.1.1.0")})}),  //
                                   N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                             N("3.2.1", {N("3.2.1.0")})})}));

    FlattenOnlyChildrenWithChildren(this->root);
    EXPECT_PRED_FORMAT2(VerifyTree, this->root,
                        N("root", {N("0"),                      //
                                   N("1.0"),                    //
                                   N("2.0.0"),                  //
                                   N("2.1.0"),                  //
                                   N("3.0.0", {N("3.0.0.0")}),  //
                                   N("3.0.1", {N("3.0.1.0")}),  //
                                   N("3.1.0", {N("3.1.0.0")}),  //
                                   N("3.1.1", {N("3.1.1.0")}),  //
                                   N("3.2.0", {N("3.2.0.0")}),  //
                                   N("3.2.1", {N("3.2.1.0")})}));
  }
}

TYPED_TEST(SimpleNodeTest, FlattenOneChild) {
  using N = TypeParam;
  // Const nodes are not supported
  if constexpr (!std::is_const_v<TypeParam>) {
    FlattenOneChild(this->NodeAt({3}), 1);
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                          //
                   N("1", {N("1.0")}),                              //
                   N("2", {N("2.0", {N("2.0.0")}),                  //
                           N("2.1", {N("2.1.0")})}),                //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                     N("3.0.1", {N("3.0.1.0")})}),  //
                           N("3.1.0", {N("3.1.0.0")}),              //
                           N("3.1.1", {N("3.1.1.0")}),              //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                     N("3.2.1", {N("3.2.1.0")})})})}));

    FlattenOneChild(this->NodeAt({1}), 0);
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                          //
                   N("1"),                                          //
                   N("2", {N("2.0", {N("2.0.0")}),                  //
                           N("2.1", {N("2.1.0")})}),                //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                     N("3.0.1", {N("3.0.1.0")})}),  //
                           N("3.1.0", {N("3.1.0.0")}),              //
                           N("3.1.1", {N("3.1.1.0")}),              //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                     N("3.2.1", {N("3.2.1.0")})})})}));
  }
}

TYPED_TEST(NodeWithValueTest, MergeConsecutiveSiblings) {
  using N = TypeParam;
  // Const nodes are not supported
  if constexpr (!std::is_const_v<TypeParam>) {
    MergeConsecutiveSiblings(this->NodeAt({3}), 1,
                             [](std::string* v0, const std::string& v1) {
                               absl::StrAppend(v0, "+", v1);
                             });
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                            //
                   N("1", {N("1.0")}),                                //
                   N("2", {N("2.0", {N("2.0.0")}),                    //
                           N("2.1", {N("2.1.0")})}),                  //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),      //
                                     N("3.0.1", {N("3.0.1.0")})}),    //
                           N("3.1+3.2", {N("3.1.0", {N("3.1.0.0")}),  //
                                         N("3.1.1", {N("3.1.1.0")}),  //
                                         N("3.2.0", {N("3.2.0.0")}),  //
                                         N("3.2.1", {N("3.2.1.0")})})})}));

    MergeConsecutiveSiblings(this->NodeAt({3}), 0,
                             [](std::string* v0, const std::string& v1) {
                               absl::StrAppend(v0, "+", v1);
                             });
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                                //
                   N("1", {N("1.0")}),                                    //
                   N("2", {N("2.0", {N("2.0.0")}),                        //
                           N("2.1", {N("2.1.0")})}),                      //
                   N("3", {N("3.0+3.1+3.2", {N("3.0.0", {N("3.0.0.0")}),  //
                                             N("3.0.1", {N("3.0.1.0")}),  //
                                             N("3.1.0", {N("3.1.0.0")}),  //
                                             N("3.1.1", {N("3.1.1.0")}),  //
                                             N("3.2.0", {N("3.2.0.0")}),  //
                                             N("3.2.1", {N("3.2.1.0")})})})}));

    MergeConsecutiveSiblings(this->root, 0,
                             [](std::string* v0, const std::string& v1) {
                               absl::StrAppend(v0, "+", v1);
                             });
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0+1", {N("1.0")}),                                  //
                   N("2", {N("2.0", {N("2.0.0")}),                        //
                           N("2.1", {N("2.1.0")})}),                      //
                   N("3", {N("3.0+3.1+3.2", {N("3.0.0", {N("3.0.0.0")}),  //
                                             N("3.0.1", {N("3.0.1.0")}),  //
                                             N("3.1.0", {N("3.1.0.0")}),  //
                                             N("3.1.1", {N("3.1.1.0")}),  //
                                             N("3.2.0", {N("3.2.0.0")}),  //
                                             N("3.2.1", {N("3.2.1.0")})})})}));
  }
}

TYPED_TEST(NodeWithParentTest, NearestCommonAncestor) {
  EXPECT_EQ(NearestCommonAncestor(  //
                this->NodeAt({0}),  //
                this->NodeAt({1})),
            &this->NodeAt({}));

  EXPECT_EQ(NearestCommonAncestor(     //
                this->NodeAt({3, 1}),  //
                this->NodeAt({3, 2, 1, 0})),
            &this->NodeAt({3}));

  EXPECT_EQ(NearestCommonAncestor(     //
                this->NodeAt({3, 1}),  //
                this->NodeAt({3, 1, 1, 0})),
            &this->NodeAt({3, 1}));

  EXPECT_EQ(NearestCommonAncestor(        //
                this->NodeAt({2, 0, 0}),  //
                this->NodeAt({3, 2, 1, 0})),
            &this->NodeAt({}));

  EXPECT_EQ(NearestCommonAncestor(  //
                this->NodeAt({}),   //
                this->NodeAt({3, 2, 1, 0})),
            &this->NodeAt({}));

  using N = TypeParam;
  N other_tree = N("", {N("A"),                                    //
                        N("C", {N("CA")}),                         //
                        N("G", {N("GA", {N("GAA")}),               //
                                N("GC", {N("GCA")})}),             //
                        N("T", {N("TA", {N("TAA", {N("TAAA")}),    //
                                         N("TAC", {N("TACA")})}),  //
                                N("TC", {N("TCA", {N("TCAA")}),    //
                                         N("TCC", {N("TCCA")})}),  //
                                N("TG", {N("TGA", {N("TGAA")}),    //
                                         N("TGC", {N("TGCA")})})})});

  EXPECT_EQ(NearestCommonAncestor(              //
                other_tree.Children().front(),  //
                this->NodeAt({0})),
            nullptr);
}

TYPED_TEST(SimpleNodeTest, AdoptSubtree) {
  using N = TypeParam;
  // Const nodes are not supported
  if constexpr (!std::is_const_v<TypeParam>) {
    AdoptSubtree(this->NodeAt({2}), N("2.2"));
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                          //
                   N("1", {N("1.0")}),                              //
                   N("2", {N("2.0", {N("2.0.0")}),                  //
                           N("2.1", {N("2.1.0")}),                  //
                           N("2.2")}),                              //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                     N("3.0.1", {N("3.0.1.0")})}),  //
                           N("3.1", {N("3.1.0", {N("3.1.0.0")}),    //
                                     N("3.1.1", {N("3.1.1.0")})}),  //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                     N("3.2.1", {N("3.2.1.0")})})})}));

    AdoptSubtree(this->NodeAt({2}), N("2.3", {N("2.3.0"), N("2.3.1")}),
                 N("2.4"));
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                          //
                   N("1", {N("1.0")}),                              //
                   N("2", {N("2.0", {N("2.0.0")}),                  //
                           N("2.1", {N("2.1.0")}),                  //
                           N("2.2"),                                //
                           N("2.3", {N("2.3.0"), N("2.3.1")}),      //
                           N("2.4")}),                              //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                     N("3.0.1", {N("3.0.1.0")})}),  //
                           N("3.1", {N("3.1.0", {N("3.1.0.0")}),    //
                                     N("3.1.1", {N("3.1.1.0")})}),  //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                     N("3.2.1", {N("3.2.1.0")})})})}));

    N other_tree = N("", {N("A"),                                    //
                          N("C", {N("CA")}),                         //
                          N("G", {N("GA", {N("GAA")}),               //
                                  N("GC", {N("GCA")})}),             //
                          N("T", {N("TA", {N("TAA", {N("TAAA")}),    //
                                           N("TAC", {N("TACA")})}),  //
                                  N("TC", {N("TCA", {N("TCAA")}),    //
                                           N("TCC", {N("TCCA")})}),  //
                                  N("TG", {N("TGA", {N("TGAA")}),    //
                                           N("TGC", {N("TGCA")})})})});

    AdoptSubtree(this->root, std::move(other_tree));
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                            //
                   N("1", {N("1.0")}),                                //
                   N("2", {N("2.0", {N("2.0.0")}),                    //
                           N("2.1", {N("2.1.0")}),                    //
                           N("2.2"),                                  //
                           N("2.3", {N("2.3.0"), N("2.3.1")}),        //
                           N("2.4")}),                                //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),      //
                                     N("3.0.1", {N("3.0.1.0")})}),    //
                           N("3.1", {N("3.1.0", {N("3.1.0.0")}),      //
                                     N("3.1.1", {N("3.1.1.0")})}),    //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),      //
                                     N("3.2.1", {N("3.2.1.0")})})}),  //
                   N("", {N("A"),                                     //
                          N("C", {N("CA")}),                          //
                          N("G", {N("GA", {N("GAA")}),                //
                                  N("GC", {N("GCA")})}),              //
                          N("T", {N("TA", {N("TAA", {N("TAAA")}),     //
                                           N("TAC", {N("TACA")})}),   //
                                  N("TC", {N("TCA", {N("TCAA")}),     //
                                           N("TCC", {N("TCCA")})}),   //
                                  N("TG", {N("TGA", {N("TGAA")}),     //
                                           N("TGC", {N("TGCA")})})})})}));
  }
}

TYPED_TEST(SimpleNodeTest, AdoptSubtreesFrom) {
  using N = TypeParam;
  // Const nodes are not supported
  if constexpr (!std::is_const_v<TypeParam>) {
    N other_tree = N("", {N("A"),                                    //
                          N("C", {N("CA")}),                         //
                          N("G", {N("GA", {N("GAA")}),               //
                                  N("GC", {N("GCA")})}),             //
                          N("T", {N("TA", {N("TAA", {N("TAAA")}),    //
                                           N("TAC", {N("TACA")})}),  //
                                  N("TC", {N("TCA", {N("TCAA")}),    //
                                           N("TCC", {N("TCCA")})}),  //
                                  N("TG", {N("TGA", {N("TGAA")}),    //
                                           N("TGC", {N("TGCA")})})})});

    AdoptSubtreesFrom(this->root, &other_tree);
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                            //
                   N("1", {N("1.0")}),                                //
                   N("2", {N("2.0", {N("2.0.0")}),                    //
                           N("2.1", {N("2.1.0")})}),                  //
                   N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),      //
                                     N("3.0.1", {N("3.0.1.0")})}),    //
                           N("3.1", {N("3.1.0", {N("3.1.0.0")}),      //
                                     N("3.1.1", {N("3.1.1.0")})}),    //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),      //
                                     N("3.2.1", {N("3.2.1.0")})})}),  //
                   N("A"),                                            //
                   N("C", {N("CA")}),                                 //
                   N("G", {N("GA", {N("GAA")}),                       //
                           N("GC", {N("GCA")})}),                     //
                   N("T", {N("TA", {N("TAA", {N("TAAA")}),            //
                                    N("TAC", {N("TACA")})}),          //
                           N("TC", {N("TCA", {N("TCAA")}),            //
                                    N("TCC", {N("TCCA")})}),          //
                           N("TG", {N("TGA", {N("TGAA")}),            //
                                    N("TGC", {N("TGCA")})})})}));
    EXPECT_PRED_FORMAT2(VerifyTree, other_tree, N(""));

    AdoptSubtreesFrom(this->NodeAt({1, 0}), &this->NodeAt({3, 0}));
    EXPECT_PRED_FORMAT2(
        VerifyTree, this->root,
        N("root", {N("0"),                                            //
                   N("1", {N("1.0", {N("3.0.0", {N("3.0.0.0")}),      //
                                     N("3.0.1", {N("3.0.1.0")})})}),  //
                   N("2", {N("2.0", {N("2.0.0")}),                    //
                           N("2.1", {N("2.1.0")})}),                  //
                   N("3", {N("3.0"),                                  //
                           N("3.1", {N("3.1.0", {N("3.1.0.0")}),      //
                                     N("3.1.1", {N("3.1.1.0")})}),    //
                           N("3.2", {N("3.2.0", {N("3.2.0.0")}),      //
                                     N("3.2.1", {N("3.2.1.0")})})}),  //
                   N("A"),                                            //
                   N("C", {N("CA")}),                                 //
                   N("G", {N("GA", {N("GAA")}),                       //
                           N("GC", {N("GCA")})}),                     //
                   N("T", {N("TA", {N("TAA", {N("TAAA")}),            //
                                    N("TAC", {N("TACA")})}),          //
                           N("TC", {N("TCA", {N("TCAA")}),            //
                                    N("TCC", {N("TCCA")})}),          //
                           N("TG", {N("TGA", {N("TGAA")}),            //
                                    N("TGC", {N("TGCA")})})})}));
  }
}

TYPED_TEST(SimpleNodeTest, Transform) {
  using N = TypeParam;

  IntNode id_lengths_tree = Transform<IntNode>(
      this->root, [](const N& node) -> int { return node.id().size(); });

  EXPECT_PRED_FORMAT2(
      VerifyTree, id_lengths_tree,
      IntNode(4, {IntNode(1),                                          //
                  IntNode(1, {IntNode(3)}),                            //
                  IntNode(1, {IntNode(3, {IntNode(5)}),                //
                              IntNode(3, {IntNode(5)})}),              //
                  IntNode(1, {IntNode(3, {IntNode(5, {IntNode(7)}),    //
                                          IntNode(5, {IntNode(7)})}),  //
                              IntNode(3, {IntNode(5, {IntNode(7)}),    //
                                          IntNode(5, {IntNode(7)})}),  //
                              IntNode(3, {IntNode(5, {IntNode(7)}),    //
                                          IntNode(5, {IntNode(7)})})})}));

  N censored_id_tree = Transform<std::remove_const_t<N>>(
      id_lengths_tree, [](const IntNode& node) -> std::string {
        return std::string(node.id(), 'x');
      });
  EXPECT_PRED_FORMAT2(
      VerifyTree, censored_id_tree,
      N("xxxx", {N("x"),                                          //
                 N("x", {N("xxx")}),                              //
                 N("x", {N("xxx", {N("xxxxx")}),                  //
                         N("xxx", {N("xxxxx")})}),                //
                 N("x", {N("xxx", {N("xxxxx", {N("xxxxxxx")}),    //
                                   N("xxxxx", {N("xxxxxxx")})}),  //
                         N("xxx", {N("xxxxx", {N("xxxxxxx")}),    //
                                   N("xxxxx", {N("xxxxxxx")})}),  //
                         N("xxx", {N("xxxxx", {N("xxxxxxx")}),    //
                                   N("xxxxx", {N("xxxxxxx")})})})}));
}

TYPED_TEST(NodeWithValueTest, DeepEqual) {
  using N = TypeParam;

  {
    N copy = this->root;
    const auto diff = DeepEqual(this->root, copy);
    EXPECT_EQ(diff.left, nullptr);
    EXPECT_EQ(diff.right, nullptr);
  }
  {
    N censored_id_tree =
        N("xxxx", {N("x"),                                          //
                   N("x", {N("xxx")}),                              //
                   N("x", {N("xxx", {N("xxxxx")}),                  //
                           N("xxx", {N("xxxxx")})}),                //
                   N("x", {N("xxx", {N("xxxxx", {N("xxxxxxx")}),    //
                                     N("xxxxx", {N("xxxxxxx")})}),  //
                           N("xxx", {N("xxxxx", {N("xxxxxxx")}),    //
                                     N("xxxxx", {N("xxxxxxx")})}),  //
                           N("xxx", {N("xxxxx", {N("xxxxxxx")}),    //
                                     N("xxxxx", {N("xxxxxxx")})})})});
    const auto diff = DeepEqual(this->root, censored_id_tree,
                                [](const std::string& l, const std::string& r) {
                                  return l.size() == r.size();
                                });
    EXPECT_EQ(diff.left, nullptr);
    EXPECT_EQ(diff.right, nullptr);
  }
  {
    IntNode id_lengths_tree =
        IntNode(4, {IntNode(1),                                          //
                    IntNode(1, {IntNode(3)}),                            //
                    IntNode(1, {IntNode(3, {IntNode(5)}),                //
                                IntNode(3, {IntNode(5)})}),              //
                    IntNode(1, {IntNode(3, {IntNode(5, {IntNode(7)}),    //
                                            IntNode(5, {IntNode(7)})}),  //
                                IntNode(3, {IntNode(5, {IntNode(7)}),    //
                                            IntNode(5, {IntNode(7)})}),  //
                                IntNode(3, {IntNode(5, {IntNode(7)}),    //
                                            IntNode(5, {IntNode(7)})})})});
    const auto diff = DeepEqual(this->root, id_lengths_tree,
                                [](const std::string& l, const int& r) {
                                  return static_cast<int>(l.size()) == r;
                                });
    EXPECT_EQ(diff.left, nullptr);
    EXPECT_EQ(diff.right, nullptr);
  }
  {
    std::remove_const_t<N> copy = this->root;
    auto n2 = std::next(copy.Children().begin(), 2);
    auto n21 = std::next(n2->Children().begin(), 1);
    auto n3 = std::next(copy.Children().begin(), 3);
    auto n31 = std::next(n3->Children().begin(), 1);
    n21->set_id("foo");
    n31->set_id("bar");
    const auto diff = DeepEqual(this->root, copy);
    EXPECT_EQ(diff.left, &this->NodeAt({2, 1}));
    EXPECT_EQ(diff.right, &*n21);
  }
  {
    N censored_id_tree =
        N("xxxx", {N("x"),                                          //
                   N("x", {N("xxx")}),                              //
                   N("x", {N("xxx", {N("xxxxx")}),                  //
                           N("xxx", {N("xxxxx")})}),                //
                   N("x", {N("xxx", {N("xxxxx", {N("xxxxxxx")}),    //
                                     N("xxxxx", {N("xxxxxxx")})}),  //
                           N("xxx", {N("xxxxx", {N("xxxxxxx")}),    //
                                     N("xxxxx", {N("xxxxxxx")})}),  //
                           N("xxx", {N("xxxxx", {N("xxxxxxx")}),    //
                                     N("xxxxx", {N("WRONG")})})})});
    auto n3 = std::next(censored_id_tree.Children().begin(), 3);
    auto n32 = std::next(n3->Children().begin(), 2);
    auto n321 = std::next(n32->Children().begin(), 1);
    auto n3210 = n321->Children().begin();
    const auto diff = DeepEqual(this->root, censored_id_tree,
                                [](const std::string& l, const std::string& r) {
                                  return l.size() == r.size();
                                });
    EXPECT_EQ(diff.left, &this->NodeAt({3, 2, 1, 0}));
    EXPECT_EQ(diff.right, &*n3210);
  }
  {
    IntNode id_lengths_tree =
        IntNode(4, {IntNode(42),                                            //
                    IntNode(1, {IntNode(3)}),                               //
                    IntNode(1, {IntNode(3, {IntNode(5)}),                   //
                                IntNode(3, {IntNode(5)})}),                 //
                    IntNode(1, {IntNode(3, {IntNode(5, {IntNode(7)}),       //
                                            IntNode(5, {IntNode(7)})}),     //
                                IntNode(3, {IntNode(5, {IntNode(7)}),       //
                                            IntNode(5, {IntNode(9999)})}),  //
                                IntNode(3, {IntNode(5, {IntNode(7)}),       //
                                            IntNode(999, {IntNode(7)})})})});
    const auto diff = DeepEqual(this->root, id_lengths_tree,
                                [](const std::string& l, const int& r) {
                                  return static_cast<int>(l.size()) == r;
                                });
    EXPECT_EQ(diff.left, &this->NodeAt({0}));
    EXPECT_EQ(diff.right, &*id_lengths_tree.Children().begin());
  }
  {
    N other = N("root", {N("0"),              //
                         N("1", {N("1.0")}),  //
                         // Missing subtree:
                         // N("2", {N("2.0", {N("2.0.0")}),
                         //         N("2.1", {N("2.1.0")})}),
                         N("3", {N("3.0", {N("3.0.0", {N("3.0.0.0")}),    //
                                           N("3.0.1", {N("3.0.1.0")})}),  //
                                 N("3.1", {N("3.1.0", {N("3.1.0.0")}),    //
                                           N("3.1.1", {N("3.1.1.0")})}),  //
                                 N("3.2", {N("3.2.0", {N("3.2.0.0")}),    //
                                           N("3.2.1", {N("3.2.1.0")})})})});
    const auto diff = DeepEqual(this->root, other);
    EXPECT_EQ(diff.left, &this->root);
    EXPECT_EQ(diff.right, &other);
  }
}

TYPED_TEST(NodeWithValueTest, StructureEqual) {
  using N = IntNode;
  {
    static const IntNode matching_tree =
        N(0, {N(1),                              //
              N(2, {N(21)}),                     //
              N(3, {N(31, {N(311)}),             //
                    N(32, {N(321)})}),           //
              N(4, {N(41, {N(411, {N(4111)}),    //
                           N(412, {N(4121)})}),  //
                    N(42, {N(421, {N(4211)}),    //
                           N(422, {N(4221)})}),  //
                    N(43, {N(431, {N(4311)}),    //
                           N(432, {N(4321)})})})});

    auto result = StructureEqual(this->root, matching_tree);
    EXPECT_EQ(result.left, nullptr);
    EXPECT_EQ(result.right, nullptr);
  }
  {
    static const IntNode matching_tree =
        N(0, {N(1),                              //
              N(2, {N(21)}),                     //
              N(3, {N(31, {N(311)}),             //
                    N(32, {N(321)})}),           //
              N(4, {N(41, {N(411, {N(4111)}),    //
                           N(412, {N(4121)})}),  //
                    // Missing subtree:
                    // N(42, {N(421, {N(4211)}),
                    //        N(422, {N(4221)})}),
                    N(43, {N(431, {N(4311)}),  //
                           N(432, {N(4321)})})})});

    auto result = StructureEqual(this->root, matching_tree);
    EXPECT_EQ(result.left, &this->NodeAt({3}));
    EXPECT_EQ(result.right, &matching_tree.Children()[3]);
  }
  {
    static const IntNode matching_tree =
        N(0, {N(1),                   //
              N(2, {N(21)}),          //
              N(3, {N(31, {N(311)}),  //
                    N(32, {N(321)}),  //
                    // Extra subtree:
                    N(33, {N(331)})}),           //
              N(4, {N(41, {N(411, {N(4111)}),    //
                           N(412, {N(4121)})}),  //
                    N(42, {N(421, {N(4211)}),    //
                           N(422, {N(4221)})}),  //
                    N(43, {N(431, {N(4311)}),    //
                           N(432, {N(4321)})})})});

    auto result = StructureEqual(this->root, matching_tree);
    EXPECT_EQ(result.left, &this->NodeAt({2}));
    EXPECT_EQ(result.right, &matching_tree.Children()[2]);
  }
  {
    static const IntNode matching_tree =
        N(0, {N(1),                   //
              N(2, {N(21)}),          //
              N(3, {N(31, {N(311)}),  //
                    N(32, {N(321)}),  //
                    // Extra subtree:
                    N(33, {N(331)})}),           //
              N(4, {N(41, {N(411, {N(4111)}),    //
                           N(412, {N(4121)})}),  //
                    // Missing subtree:
                    // N(42, {N(421, {N(4211)}),
                    //        N(422, {N(4221)})}),
                    N(43, {N(431, {N(4311)}),  //
                           N(432, {N(4321)})})})});

    auto result = StructureEqual(this->root, matching_tree);
    EXPECT_EQ(result.left, &this->NodeAt({2}));
    EXPECT_EQ(result.right, &matching_tree.Children()[2]);
  }
}

}  // namespace
}  // namespace verible