// Copyright 2017-2020 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/vector_tree.h"

#include <cstddef>
#include <ostream>
#include <sstream>
#include <utility>
#include <vector>

#include "absl/strings/str_cat.h"
#include "absl/strings/str_join.h"
#include "absl/strings/string_view.h"
#include "common/util/logging.h"
#include "common/util/tree_operations.h"
#include "common/util/vector_tree_test_util.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"

namespace verible {
namespace {

using ::testing::ElementsAre;
using verible::testing::MakePath;
using verible::testing::NamedInterval;
using verible::testing::VectorTreeTestType;

template <class Tree>
void ExpectPath(const Tree &tree, absl::string_view expect) {
  std::ostringstream stream;
  stream << NodePath(tree);
  EXPECT_EQ(stream.str(), expect);
}

// Test that basic Tree construction works on a singleton node.
TEST(VectorTreeTest, RootOnly) {
  const VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  EXPECT_TRUE(is_leaf(tree));
  EXPECT_EQ(tree.Parent(), nullptr);
  EXPECT_EQ(NumAncestors(tree), 0);
  EXPECT_EQ(BirthRank(tree), 0);  // no parent
  EXPECT_TRUE(IsFirstChild(tree));
  EXPECT_TRUE(IsLastChild(tree));
  EXPECT_EQ(&Root(tree), &tree);

  const auto &value = tree.Value();
  EXPECT_EQ(value.left, 0);
  EXPECT_EQ(value.right, 2);
  EXPECT_EQ(value.name, "root");

  ExpectPath(tree, "{}");
}

TEST(VectorTreeTest, RootOnlyDescendants) {
  VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  EXPECT_EQ(&LeftmostDescendant(tree), &tree);
  EXPECT_EQ(&RightmostDescendant(tree), &tree);
  {  // Test const method variants.
    const auto &ctree(tree);
    EXPECT_EQ(&LeftmostDescendant(ctree), &ctree);
    EXPECT_EQ(&RightmostDescendant(ctree), &ctree);
  }
}

TEST(VectorTreeTest, RootOnlyHasAncestor) {
  VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  EXPECT_FALSE(HasAncestor(tree, nullptr));
  EXPECT_FALSE(HasAncestor(tree, &tree));

  // Separate tree
  VectorTreeTestType tree2(verible::testing::MakeRootOnlyExampleTree());
  EXPECT_FALSE(HasAncestor(tree2, &tree));
  EXPECT_FALSE(HasAncestor(tree, &tree2));
}

TEST(VectorTreeTest, RootOnlyLeafIteration) {
  VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  EXPECT_EQ(NextLeaf(tree), nullptr);
  EXPECT_EQ(PreviousLeaf(tree), nullptr);
  {  // const method variants
    const auto &ctree(tree);
    EXPECT_EQ(NextLeaf(ctree), nullptr);
    EXPECT_EQ(PreviousLeaf(ctree), nullptr);
  }
}

TEST(VectorTreeTest, RootOnlySiblingIteration) {
  VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  EXPECT_EQ(verible::NextSibling(tree), nullptr);
  EXPECT_EQ(verible::PreviousSibling(tree), nullptr);
  {  // const method variants
    const auto &ctree(tree);
    EXPECT_EQ(verible::NextSibling(ctree), nullptr);
    EXPECT_EQ(verible::PreviousSibling(ctree), nullptr);
  }
}

TEST(VectorTreeTest, CopyAssignEmpty) {
  using tree_type = VectorTree<int>;
  const tree_type tree(1);  // Root only tree.
  const tree_type expected(1);
  tree_type tree2(5);
  tree2 = tree;
  {
    const auto result_pair = DeepEqual(tree2, expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {  // verify original copy
    const auto result_pair = DeepEqual(tree, expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
}

TEST(VectorTreeTest, CopyAssignDeep) {
  using tree_type = VectorTree<int>;
  const tree_type tree(1,
                       tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
  const tree_type expected(
      1, tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
  tree_type tree2(6);
  tree2 = tree;
  {
    const auto result_pair = DeepEqual(tree2, expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {  // verify original copy
    const auto result_pair = DeepEqual(tree, expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
}

TEST(VectorTreeTest, CopyInitializeEmpty) {
  using tree_type = VectorTree<int>;
  const tree_type tree(1);  // Root only tree.
  const tree_type expected(1);
  // Specifically testing copy here.
  // clang-format off
  tree_type tree2 = tree;  // NOLINT(performance-unnecessary-copy-initialization)
  // clang-format on
  {
    const auto result_pair = DeepEqual(tree2, expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {  // verify original copy
    const auto result_pair = DeepEqual(tree, expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
}

TEST(VectorTreeTest, CopyInitializeDeep) {
  using tree_type = VectorTree<int>;
  const tree_type tree(1,
                       tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
  const tree_type expected(
      1, tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
  // Specifically testing copy here.
  // clang-format off
  tree_type tree2 = tree;  // NOLINT(performance-unnecessary-copy-initialization)
  // clang-format on
  {
    const auto result_pair = DeepEqual(tree2, expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {  // verify original copy
    const auto result_pair = DeepEqual(tree, expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
}

TEST(VectorTreeTest, MoveInitializeEmpty) {
  using tree_type = VectorTree<int>;
  tree_type tree(1);  // Root only tree.
  const tree_type expected(1);
  tree_type tree2 = std::move(tree);
  const auto result_pair = DeepEqual(tree2, expected);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, MoveInitializeDeep) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
  const tree_type expected(
      1, tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
  tree_type tree2 = std::move(tree);
  const auto result_pair = DeepEqual(tree2, expected);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, MoveAssignEmpty) {
  using tree_type = VectorTree<int>;
  tree_type tree(1);  // Root only tree.
  const tree_type expected(1);
  tree_type tree2(2);
  VLOG(4) << "about to move.";
  tree2 = std::move(tree);
  VLOG(4) << "done moving.";
  const auto result_pair = DeepEqual(tree2, expected);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, MoveAssignDeep) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
  tree_type tree2(7, tree_type(8, tree_type(9)));
  tree2 = std::move(tree);
  const tree_type expected(
      1, tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
  const auto result_pair = DeepEqual(tree2, expected);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, SwapUnrelatedRoots) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
  tree_type tree2(7, tree_type(8, tree_type(9)));
  const tree_type t1_expected(tree2);  // deep-copy
  const tree_type t2_expected(tree);   // deep-copy
  swap(tree, tree2);                   // verible::swap, using ADL
  {
    const auto result_pair = DeepEqual(tree, t1_expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {
    const auto result_pair = DeepEqual(tree2, t2_expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
}

TEST(VectorTreeTest, SwapUnrelatedSubtrees) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
  tree_type tree2(7, tree_type(8, tree_type(9, tree_type(10))));
  swap(tree.Children()[0], tree2.Children()[0]);
  {
    const tree_type expected(1, tree_type(8, tree_type(9, tree_type(10))));
    const auto result_pair = DeepEqual(tree, expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {
    const tree_type expected(
        7, tree_type(2, tree_type(3, tree_type(4, tree_type(5)))));
    const auto result_pair = DeepEqual(tree2, expected);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
}

TEST(VectorTreeTest, SwapSiblings) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,  //
                 tree_type(0),
                 tree_type(2, tree_type(3, tree_type(4, tree_type(5)))),
                 tree_type(7, tree_type(8, tree_type(9))), tree_type(11));
  swap(tree.Children()[2], tree.Children()[1]);

  const tree_type expected(
      1,  //
      tree_type(0), tree_type(7, tree_type(8, tree_type(9))),
      tree_type(2, tree_type(3, tree_type(4, tree_type(5)))), tree_type(11));
  const auto result_pair = DeepEqual(tree, expected);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, SwapDistantCousins) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,  //
                 tree_type(0),
                 tree_type(2, tree_type(3, tree_type(4, tree_type(5)))),
                 tree_type(7, tree_type(8, tree_type(9))), tree_type(11));
  swap(tree.Children()[2], tree.Children()[1].Children()[0]);

  const tree_type expected(
      1,  //
      tree_type(0), tree_type(2, tree_type(7, tree_type(8, tree_type(9)))),
      tree_type(3, tree_type(4, tree_type(5))), tree_type(11));
  const auto result_pair = DeepEqual(tree, expected);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, StructureEqualRootToRoot) {
  const VectorTreeTestType ltree(verible::testing::MakeRootOnlyExampleTree());
  const VectorTreeTestType rtree(verible::testing::MakeRootOnlyExampleTree());
  const auto result_pair = StructureEqual(ltree, rtree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, StructureEqualRootToRootIgnoringValue) {
  VectorTreeTestType ltree(verible::testing::MakeRootOnlyExampleTree());
  VectorTreeTestType rtree(verible::testing::MakeRootOnlyExampleTree());
  ltree.Value().left = 11;
  rtree.Value().left = 34;
  const auto result_pair = StructureEqual(ltree, rtree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, DeepEqualRootToRoot) {
  const VectorTreeTestType ltree(verible::testing::MakeRootOnlyExampleTree());
  const VectorTreeTestType rtree(verible::testing::MakeRootOnlyExampleTree());
  const auto result_pair = DeepEqual(ltree, rtree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, DeepEqualRootToRootValueDifferent) {
  VectorTreeTestType ltree(verible::testing::MakeRootOnlyExampleTree());
  VectorTreeTestType rtree(verible::testing::MakeRootOnlyExampleTree());
  ltree.Value().left = 11;
  rtree.Value().left = 34;
  const auto result_pair = DeepEqual(ltree, rtree);
  EXPECT_EQ(result_pair.left, &ltree);
  EXPECT_EQ(result_pair.right, &rtree);
}

struct NameOnly {
  absl::string_view name;

  explicit NameOnly(const NamedInterval &v) : name(v.name) {}
};

std::ostream &operator<<(std::ostream &stream, const NameOnly &n) {
  return stream << '(' << n.name << ")\n";
}

static NameOnly NameOnlyConverter(const VectorTreeTestType &node) {
  return NameOnly(node.Value());
}

// Heterogeneous comparison.
bool operator==(const NamedInterval &left, const NameOnly &right) {
  return left.name == right.name;
}

TEST(VectorTreeTest, RootOnlyTreeTransformConstruction) {
  const VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  const auto other_tree =
      Transform<VectorTree<NameOnly>>(tree, NameOnlyConverter);
  EXPECT_TRUE(is_leaf(other_tree));
  EXPECT_EQ(other_tree.Parent(), nullptr);
  EXPECT_EQ(NumAncestors(other_tree), 0);
  EXPECT_EQ(BirthRank(other_tree), 0);  // no parent

  const auto &value = other_tree.Value();
  EXPECT_EQ(value.name, "root");
}

TEST(VectorTreeTest, RootOnlyTreeTransformComparisonMatches) {
  const VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  const auto other_tree =
      Transform<VectorTree<NameOnly>>(tree, NameOnlyConverter);
  {
    const auto result_pair = StructureEqual(tree, other_tree);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {
    const auto result_pair = StructureEqual(other_tree, tree);  // swapped
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {
    // Uses hetergeneous value comparison.
    const auto result_pair = DeepEqual(tree, other_tree);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
}

TEST(VectorTreeTest, RootOnlyTreeTransformComparisonDiffer) {
  const VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  auto other_tree = Transform<VectorTree<NameOnly>>(tree, NameOnlyConverter);
  other_tree.Value().name = "groot";
  {
    const auto result_pair = StructureEqual(tree, other_tree);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {
    // Uses hetergeneous value comparison.
    const auto result_pair = DeepEqual(tree, other_tree);
    EXPECT_EQ(result_pair.left, &tree);
    EXPECT_EQ(result_pair.right, &other_tree);
  }
}

TEST(VectorTreeTest, NewChild) {
  VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  {
    tree.Children().emplace_back(NamedInterval(1, 2, "child"));
    auto *child = &tree.Children().back();
    EXPECT_EQ(child->Parent(), &tree);
    EXPECT_EQ(&Root(*child), &tree);
    EXPECT_TRUE(verible::is_leaf(*child));

    const auto &value(child->Value());
    EXPECT_EQ(value.left, 1);
    EXPECT_EQ(value.right, 2);
    EXPECT_EQ(value.name, "child");

    ExpectPath(*child, "{0}");
  }
  {
    tree.Children().emplace_back(NamedInterval(2, 3, "lil-bro"));
    auto *child = &tree.Children().back();
    EXPECT_EQ(child->Parent(), &tree);
    EXPECT_EQ(&Root(*child), &tree);
    EXPECT_TRUE(verible::is_leaf(*child));

    const auto &value(child->Value());
    EXPECT_EQ(value.left, 2);
    EXPECT_EQ(value.right, 3);
    EXPECT_EQ(value.name, "lil-bro");
    // Note: first child may have moved due to realloc

    ExpectPath(*child, "{1}");
  }
}

TEST(VectorTreeTest, NewSibling) {
  VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  {
    tree.Children().emplace_back(NamedInterval(1, 2, "child"));
    auto *first_child = &tree.Children().back();
    ExpectPath(*first_child, "{0}");

    auto &siblings = first_child->Parent()->Children();
    siblings.emplace_back(NamedInterval(2, 3, "lil-bro"));
    auto *second_child = &siblings.back();
    // Recall that emplace_back() may invalidate reference to first_child.
    EXPECT_EQ(second_child->Parent(), &tree);
    EXPECT_EQ(&Root(*second_child), &tree);
    EXPECT_TRUE(verible::is_leaf(*second_child));

    const auto &value(second_child->Value());
    EXPECT_EQ(value.left, 2);
    EXPECT_EQ(value.right, 3);
    EXPECT_EQ(value.name, "lil-bro");

    ExpectPath(*second_child, "{1}");
  }
}

TEST(VectorTreeTest, OneChildPolicy) {
  const auto tree = verible::testing::MakeOneChildPolicyExampleTree();
  EXPECT_EQ(tree.Parent(), nullptr);
  EXPECT_FALSE(is_leaf(tree));

  const auto &value = tree.Value();
  EXPECT_EQ(value.left, 0);
  EXPECT_EQ(value.right, 3);
  EXPECT_EQ(value.name, "root");

  {
    const auto &child = tree.Children().front();
    EXPECT_EQ(child.Parent(), &tree);
    EXPECT_EQ(&Root(child), &tree);
    EXPECT_FALSE(is_leaf(child));
    EXPECT_EQ(NumAncestors(child), 1);
    EXPECT_EQ(BirthRank(child), 0);
    EXPECT_TRUE(IsFirstChild(child));
    EXPECT_TRUE(IsLastChild(child));

    const auto &cvalue = child.Value();
    EXPECT_EQ(cvalue.left, 0);
    EXPECT_EQ(cvalue.right, 3);
    EXPECT_EQ(cvalue.name, "gen1");
    ExpectPath(child, "{0}");

    EXPECT_EQ(verible::NextSibling(child), nullptr);
    EXPECT_EQ(verible::PreviousSibling(child), nullptr);

    // The invoking node need not be a leaf.
    EXPECT_EQ(NextLeaf(child), nullptr);
    EXPECT_EQ(PreviousLeaf(child), nullptr);

    {
      const auto &grandchild = child.Children().front();
      EXPECT_EQ(grandchild.Parent(), &child);
      EXPECT_EQ(&Root(grandchild), &tree);
      EXPECT_TRUE(is_leaf(grandchild));
      EXPECT_EQ(NumAncestors(grandchild), 2);
      EXPECT_EQ(BirthRank(grandchild), 0);
      EXPECT_TRUE(IsFirstChild(grandchild));
      EXPECT_TRUE(IsLastChild(grandchild));

      const auto &gcvalue = grandchild.Value();
      EXPECT_EQ(gcvalue.left, 0);
      EXPECT_EQ(gcvalue.right, 3);
      EXPECT_EQ(gcvalue.name, "gen2");
      ExpectPath(grandchild, "{0,0}");

      // As the ancestry chain is linear, Leftmost == Rightmost.
      EXPECT_EQ(&LeftmostDescendant(child), &grandchild);
      EXPECT_EQ(&RightmostDescendant(child), &grandchild);
      EXPECT_EQ(&LeftmostDescendant(tree), &grandchild);
      EXPECT_EQ(&RightmostDescendant(tree), &grandchild);

      EXPECT_EQ(verible::NextSibling(grandchild), nullptr);
      EXPECT_EQ(verible::PreviousSibling(grandchild), nullptr);

      // There is still only a single leaf in a one-child tree,
      // thus next and previous do not exist.
      EXPECT_EQ(NextLeaf(grandchild), nullptr);
      EXPECT_EQ(PreviousLeaf(grandchild), nullptr);
    }
  }
}

TEST(VectorTreeTest, OneChildPolicyHasAncestor) {
  const auto tree = verible::testing::MakeOneChildPolicyExampleTree();

  {
    const auto &child = tree.Children().front();

    EXPECT_FALSE(HasAncestor(tree, &child));
    EXPECT_TRUE(HasAncestor(child, &tree));

    {
      const auto &grandchild = child.Children().front();

      EXPECT_FALSE(HasAncestor(child, &grandchild));
      EXPECT_TRUE(HasAncestor(grandchild, &child));

      EXPECT_FALSE(HasAncestor(tree, &grandchild));
      EXPECT_TRUE(HasAncestor(grandchild, &tree));
    }
  }
}

TEST(VectorTreeTest, StructureEqualOneChild) {
  const VectorTreeTestType ltree(
      verible::testing::MakeOneChildPolicyExampleTree());
  const VectorTreeTestType rtree(
      verible::testing::MakeOneChildPolicyExampleTree());
  const auto result_pair = StructureEqual(ltree, rtree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, StructureEqualOneChildIgnoreValues) {
  VectorTreeTestType ltree(verible::testing::MakeOneChildPolicyExampleTree());
  VectorTreeTestType rtree(verible::testing::MakeOneChildPolicyExampleTree());
  ltree.Children()[0].Value().right = 32;
  rtree.Children()[0].Value().right = 77;
  const auto result_pair = StructureEqual(ltree, rtree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, DeepEqualOneChild) {
  const VectorTreeTestType ltree(
      verible::testing::MakeOneChildPolicyExampleTree());
  const VectorTreeTestType rtree(
      verible::testing::MakeOneChildPolicyExampleTree());
  const auto result_pair = DeepEqual(ltree, rtree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, DeepEqualOneChildDifferentChildValues) {
  VectorTreeTestType ltree(verible::testing::MakeOneChildPolicyExampleTree());
  VectorTreeTestType rtree(verible::testing::MakeOneChildPolicyExampleTree());
  auto &lchild = ltree.Children()[0];
  auto &rchild = rtree.Children()[0];
  lchild.Value().right = 32;
  rchild.Value().right = 77;
  const auto result_pair = DeepEqual(ltree, rtree);
  EXPECT_EQ(result_pair.left, &lchild);
  EXPECT_EQ(result_pair.right, &rchild);
}

TEST(VectorTreeTest, DeepEqualOneChildDifferentGrandchildValues) {
  VectorTreeTestType ltree(verible::testing::MakeOneChildPolicyExampleTree());
  VectorTreeTestType rtree(verible::testing::MakeOneChildPolicyExampleTree());
  auto &lchild = ltree.Children()[0].Children()[0];  // only grandchild
  auto &rchild = rtree.Children()[0].Children()[0];  // only grandchild
  lchild.Value().right = 32;
  rchild.Value().right = 77;
  const auto result_pair = DeepEqual(ltree, rtree);
  EXPECT_EQ(result_pair.left, &lchild);
  EXPECT_EQ(result_pair.right, &rchild);
}

TEST(VectorTreeTest, DeepEqualOneChildGrandchildValuesHeterogeneous) {
  VectorTreeTestType ltree(verible::testing::MakeOneChildPolicyExampleTree());
  auto rtree = Transform<VectorTree<NameOnly>>(ltree, NameOnlyConverter);
  {  // Match
    const auto result_pair = DeepEqual(ltree, rtree);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {                                          // Mismatch
    const std::vector<size_t> path({0, 0});  // only grandchild
    auto &lchild = DescendPath(ltree, path.begin(), path.end());
    auto &rchild = DescendPath(rtree, path.begin(), path.end());
    lchild.Value().name = "alex";
    rchild.Value().name = "james";
    const auto result_pair = DeepEqual(ltree, rtree);
    EXPECT_EQ(result_pair.left, &lchild);
    EXPECT_EQ(result_pair.right, &rchild);
  }
}

template <typename T>
void VerifyFamilyTree(const VectorTree<T> &tree) {
  EXPECT_EQ(tree.Parent(), nullptr);
  EXPECT_EQ(&Root(tree), &tree);
  EXPECT_FALSE(is_leaf(tree));
  EXPECT_EQ(NumAncestors(tree), 0);
  EXPECT_EQ(BirthRank(tree), 0);

  const auto tree_path = MakePath(tree);
  EXPECT_TRUE(tree_path.empty());
  EXPECT_EQ(&DescendPath(tree, tree_path.begin(), tree_path.end()), &tree);

  for (int i = 0; i < 2; ++i) {
    const auto &child = tree.Children()[i];
    EXPECT_EQ(child.Parent(), &tree);
    EXPECT_EQ(&Root(child), &tree);
    EXPECT_FALSE(is_leaf(child));
    EXPECT_EQ(NumAncestors(child), 1);
    EXPECT_EQ(BirthRank(child), i);
    EXPECT_EQ(IsFirstChild(child), i == 0);
    EXPECT_EQ(IsLastChild(child), i == 1);

    const auto child_path = MakePath(child);
    EXPECT_THAT(child_path, ElementsAre(i));
    EXPECT_EQ(&DescendPath(tree, child_path.begin(), child_path.end()), &child);

    for (int j = 0; j < 2; ++j) {
      const auto &grandchild = child.Children()[j];
      EXPECT_EQ(grandchild.Parent(), &child);
      EXPECT_EQ(&Root(grandchild), &tree);
      EXPECT_TRUE(is_leaf(grandchild));
      EXPECT_EQ(NumAncestors(grandchild), 2);
      EXPECT_EQ(BirthRank(grandchild), j);
      EXPECT_EQ(IsFirstChild(grandchild), j == 0);
      EXPECT_EQ(IsLastChild(grandchild), j == 1);

      const auto grandchild_path = MakePath(grandchild);
      EXPECT_THAT(grandchild_path, ElementsAre(i, j));
      const auto begin = grandchild_path.begin(), end = grandchild_path.end();
      EXPECT_EQ(&DescendPath(tree, begin, end), &grandchild);
      EXPECT_EQ(&DescendPath(child, begin + 1, end), &grandchild);
      ExpectPath(grandchild, absl::StrCat("{", i, ",", j, "}"));
    }
  }
}

// Tests internal consistency of BirthRank and Path properties.
TEST(VectorTreeTest, FamilyTreeMembers) {
  const auto tree = verible::testing::MakeExampleFamilyTree();
  VerifyFamilyTree(tree);
}

// Tests internal consistency and properties of copied tree.
TEST(VectorTreeTest, FamilyTreeCopiedMembers) {
  const auto orig_tree = verible::testing::MakeExampleFamilyTree();
  // Specifically testing copy here.
  // clang-format off
  const auto tree(orig_tree);  // NOLINT(performance-unnecessary-copy-initialization)
  // clang-format on
  VerifyFamilyTree(orig_tree);
  VerifyFamilyTree(tree);

  const auto result_pair = DeepEqual(orig_tree, tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

// Tests internal consistency and properties of moved tree.
TEST(VectorTreeTest, FamilyTreeMovedMembers) {
  auto orig_tree = verible::testing::MakeExampleFamilyTree();
  const auto tree(std::move(orig_tree));  // moved
  VerifyFamilyTree(tree);
}

TEST(VectorTreeTest, FamilyTreeLeftRightmostDescendants) {
  auto tree = verible::testing::MakeExampleFamilyTree();
  const auto left_path = {0, 0};
  const auto right_path = {1, 1};
  {  // Test mutable method variants.
    EXPECT_EQ(&LeftmostDescendant(tree),
              &DescendPath(tree, left_path.begin(), left_path.end()));
    EXPECT_EQ(&RightmostDescendant(tree),
              &DescendPath(tree, right_path.begin(), right_path.end()));
  }
  {  // Test const method variants.
    const auto &ctree(tree);
    EXPECT_EQ(&LeftmostDescendant(ctree),
              &DescendPath(ctree, left_path.begin(), left_path.end()));
    EXPECT_EQ(&RightmostDescendant(ctree),
              &DescendPath(ctree, right_path.begin(), right_path.end()));
  }
}

TEST(VectorTreeTest, FamilyTreeHasAncestor) {
  const auto tree = verible::testing::MakeExampleFamilyTree();
  const auto &child_0 = tree.Children()[0];
  const auto &child_1 = tree.Children()[1];
  const auto &grandchild_00 = child_0.Children()[0];
  const auto &grandchild_01 = child_0.Children()[1];
  const auto &grandchild_10 = child_1.Children()[0];
  const auto &grandchild_11 = child_1.Children()[1];

  EXPECT_FALSE(HasAncestor(tree, &child_0));
  EXPECT_FALSE(HasAncestor(tree, &child_1));
  EXPECT_FALSE(HasAncestor(tree, &grandchild_00));
  EXPECT_FALSE(HasAncestor(tree, &grandchild_01));
  EXPECT_FALSE(HasAncestor(tree, &grandchild_10));
  EXPECT_FALSE(HasAncestor(tree, &grandchild_11));

  EXPECT_TRUE(HasAncestor(child_0, &tree));
  EXPECT_TRUE(HasAncestor(child_1, &tree));
  EXPECT_TRUE(HasAncestor(grandchild_00, &tree));
  EXPECT_TRUE(HasAncestor(grandchild_01, &tree));
  EXPECT_TRUE(HasAncestor(grandchild_10, &tree));
  EXPECT_TRUE(HasAncestor(grandchild_11, &tree));

  EXPECT_FALSE(HasAncestor(child_0, &child_1));
  EXPECT_FALSE(HasAncestor(child_1, &child_0));

  EXPECT_FALSE(HasAncestor(child_0, &grandchild_00));
  EXPECT_FALSE(HasAncestor(child_0, &grandchild_01));
  EXPECT_FALSE(HasAncestor(child_0, &grandchild_10));
  EXPECT_FALSE(HasAncestor(child_0, &grandchild_11));
  EXPECT_FALSE(HasAncestor(child_1, &grandchild_00));
  EXPECT_FALSE(HasAncestor(child_1, &grandchild_01));
  EXPECT_FALSE(HasAncestor(child_1, &grandchild_10));
  EXPECT_FALSE(HasAncestor(child_1, &grandchild_11));

  EXPECT_TRUE(HasAncestor(grandchild_00, &child_0));
  EXPECT_FALSE(HasAncestor(grandchild_00, &child_1));
  EXPECT_TRUE(HasAncestor(grandchild_01, &child_0));
  EXPECT_FALSE(HasAncestor(grandchild_01, &child_1));
  EXPECT_FALSE(HasAncestor(grandchild_10, &child_0));
  EXPECT_TRUE(HasAncestor(grandchild_10, &child_1));
  EXPECT_FALSE(HasAncestor(grandchild_11, &child_0));
  EXPECT_TRUE(HasAncestor(grandchild_11, &child_1));
}

TEST(VectorTreeTest, FamilyTreeNextPreviousSiblings) {
  auto tree = verible::testing::MakeExampleFamilyTree();
  auto &child_0 = tree.Children()[0];
  auto &child_1 = tree.Children()[1];
  auto &grandchild_00 = child_0.Children()[0];
  auto &grandchild_01 = child_0.Children()[1];
  auto &grandchild_10 = child_1.Children()[0];
  auto &grandchild_11 = child_1.Children()[1];

  // Verify child generation.
  EXPECT_EQ(verible::NextSibling(child_0), &child_1);
  EXPECT_EQ(verible::NextSibling(child_1), nullptr);
  EXPECT_EQ(verible::PreviousSibling(child_0), nullptr);
  EXPECT_EQ(verible::PreviousSibling(child_1), &child_0);

  // Verify grandchild generation.
  EXPECT_EQ(verible::NextSibling(grandchild_00), &grandchild_01);
  EXPECT_EQ(verible::NextSibling(grandchild_01), nullptr);
  EXPECT_EQ(verible::NextSibling(grandchild_10), &grandchild_11);
  EXPECT_EQ(verible::NextSibling(grandchild_11), nullptr);
  EXPECT_EQ(verible::PreviousSibling(grandchild_00), nullptr);
  EXPECT_EQ(verible::PreviousSibling(grandchild_01), &grandchild_00);
  EXPECT_EQ(verible::PreviousSibling(grandchild_10), nullptr);
  EXPECT_EQ(verible::PreviousSibling(grandchild_11), &grandchild_10);

  {  // same but testing const method variants.
    const auto &cchild_0(child_0);
    const auto &cchild_1(child_1);
    const auto &cgrandchild_00(grandchild_00);
    const auto &cgrandchild_01(grandchild_01);
    const auto &cgrandchild_10(grandchild_10);
    const auto &cgrandchild_11(grandchild_11);

    // Verify child generation.
    EXPECT_EQ(verible::NextSibling(cchild_0), &cchild_1);
    EXPECT_EQ(verible::NextSibling(cchild_1), nullptr);
    EXPECT_EQ(verible::PreviousSibling(cchild_0), nullptr);
    EXPECT_EQ(verible::PreviousSibling(cchild_1), &cchild_0);

    // Verify grandchild generation.
    EXPECT_EQ(verible::NextSibling(cgrandchild_00), &cgrandchild_01);
    EXPECT_EQ(verible::NextSibling(cgrandchild_01), nullptr);
    EXPECT_EQ(verible::NextSibling(cgrandchild_10), &cgrandchild_11);
    EXPECT_EQ(verible::NextSibling(cgrandchild_11), nullptr);
    EXPECT_EQ(verible::PreviousSibling(cgrandchild_00), nullptr);
    EXPECT_EQ(verible::PreviousSibling(cgrandchild_01), &cgrandchild_00);
    EXPECT_EQ(verible::PreviousSibling(cgrandchild_10), nullptr);
    EXPECT_EQ(verible::PreviousSibling(cgrandchild_11), &cgrandchild_10);
  }
}

TEST(VectorTreeTest, FamilyTreeNextPreviousLeafChain) {
  auto tree = verible::testing::MakeExampleFamilyTree();
  auto &grandchild_00 = tree.Children()[0].Children()[0];
  auto &grandchild_01 = tree.Children()[0].Children()[1];
  auto &grandchild_10 = tree.Children()[1].Children()[0];
  auto &grandchild_11 = tree.Children()[1].Children()[1];

  // Verify forward links.
  EXPECT_EQ(NextLeaf(grandchild_00), &grandchild_01);
  EXPECT_EQ(NextLeaf(grandchild_01), &grandchild_10);
  EXPECT_EQ(NextLeaf(grandchild_10), &grandchild_11);
  EXPECT_EQ(NextLeaf(grandchild_11), nullptr);

  // Verify reverse links.
  EXPECT_EQ(PreviousLeaf(grandchild_00), nullptr);
  EXPECT_EQ(PreviousLeaf(grandchild_01), &grandchild_00);
  EXPECT_EQ(PreviousLeaf(grandchild_10), &grandchild_01);
  EXPECT_EQ(PreviousLeaf(grandchild_11), &grandchild_10);

  {  // same but testing const method variants.
    const auto &cgrandchild_00(grandchild_00);
    const auto &cgrandchild_01(grandchild_01);
    const auto &cgrandchild_10(grandchild_10);
    const auto &cgrandchild_11(grandchild_11);

    // Verify forward links.
    EXPECT_EQ(NextLeaf(cgrandchild_00), &cgrandchild_01);
    EXPECT_EQ(NextLeaf(cgrandchild_01), &cgrandchild_10);
    EXPECT_EQ(NextLeaf(cgrandchild_10), &cgrandchild_11);
    EXPECT_EQ(NextLeaf(cgrandchild_11), nullptr);

    // Verify reverse links.
    EXPECT_EQ(PreviousLeaf(cgrandchild_00), nullptr);
    EXPECT_EQ(PreviousLeaf(cgrandchild_01), &cgrandchild_00);
    EXPECT_EQ(PreviousLeaf(cgrandchild_10), &cgrandchild_01);
    EXPECT_EQ(PreviousLeaf(cgrandchild_11), &cgrandchild_10);
  }
}

TEST(VectorTreeTest, FamilyTreeMembersTransformed) {
  const auto orig_tree = verible::testing::MakeExampleFamilyTree();
  const auto tree =
      Transform<VectorTree<NameOnly>>(orig_tree, NameOnlyConverter);
  VerifyFamilyTree(orig_tree);
  VerifyFamilyTree(tree);

  {
    const auto result_pair = StructureEqual(orig_tree, tree);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }
  {  // Converse comparison.
    const auto result_pair = StructureEqual(tree, orig_tree);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }

  {
    // Uses hetergeneous value comparison.
    const auto result_pair = DeepEqual(orig_tree, tree);
    EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
    EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  }

  // Mutate one grandchild at a time.
  for (size_t i = 0; i < 2; ++i) {
    for (size_t j = 0; j < 2; ++j) {
      auto ltree(orig_tree);  // copy
      auto rtree(tree);       // copy
      const std::vector<size_t> path({i, j});
      auto &lchild = DescendPath(ltree, path.begin(), path.end());
      auto &rchild = DescendPath(rtree, path.begin(), path.end());

      lchild.Value().name = "foo";
      rchild.Value().name = "bar";
      const auto result_pair = DeepEqual(ltree, rtree);
      EXPECT_EQ(result_pair.left, &lchild);
      EXPECT_EQ(result_pair.right, &rchild);
    }
  }
}

TEST(VectorTreeTest, FamilyTreeMembersDifferentStructureExtraGreatGrand) {
  // Mutate grandchildren structure.
  for (size_t i = 0; i < 2; ++i) {
    for (size_t j = 0; j < 2; ++j) {
      auto ltree = verible::testing::MakeExampleFamilyTree();
      auto rtree = verible::testing::MakeExampleFamilyTree();
      const std::vector<size_t> path({i, j});
      auto &lchild = DescendPath(ltree, path.begin(), path.end());
      auto &rchild = DescendPath(rtree, path.begin(), path.end());

      rchild.Children().emplace_back(NamedInterval(8, 9, "black-sheep"));
      const auto result_pair = StructureEqual(ltree, rtree);
      EXPECT_EQ(result_pair.left, &lchild);
      EXPECT_EQ(result_pair.right, &rchild);
    }
  }
}

TEST(VectorTreeTest, FamilyTreeMembersDifferentStructureExtraGrand) {
  // Mutate grandchildren structure.
  for (size_t i = 0; i < 2; ++i) {
    for (size_t j = 0; j < 2; ++j) {
      auto ltree = verible::testing::MakeExampleFamilyTree();
      auto rtree = verible::testing::MakeExampleFamilyTree();
      const std::vector<size_t> path({i, j});
      const auto &lparent = DescendPath(ltree, path.begin(), path.end() - 1);
      const auto &rparent = DescendPath(rtree, path.begin(), path.end() - 1);
      auto &rchild = DescendPath(rtree, path.begin(), path.end());

      rchild.Parent()->Children().emplace_back(
          NamedInterval(8, 9, "black-sheep"));
      // Note: `rchild` may have been moved and invalidated due to realloc.
      const auto result_pair = StructureEqual(ltree, rtree);
      EXPECT_EQ(result_pair.left, &lparent);
      EXPECT_EQ(result_pair.right, &rparent);
    }
  }
}

TEST(VectorTreeTest, FamilyTreeMembersDifferentStructureMissingGrand) {
  // Remove one set of grandchildren.
  for (size_t i = 0; i < 2; ++i) {
    auto ltree = verible::testing::MakeExampleFamilyTree();
    auto rtree = verible::testing::MakeExampleFamilyTree();
    const std::vector<size_t> path({i});
    auto &lchild = DescendPath(ltree, path.begin(), path.end());
    auto &rchild = DescendPath(rtree, path.begin(), path.end());

    lchild.Children().clear();
    const auto result_pair = StructureEqual(ltree, rtree);
    EXPECT_EQ(result_pair.left, &lchild);
    EXPECT_EQ(result_pair.right, &rchild);
  }
}

bool EqualNamedIntervalIgnoreName(const NamedInterval &l,
                                  const NamedInterval &r) {
  return l.left == r.left && l.right == r.right;  // ignore .name
}

TEST(VectorTreeTest, FamilyTreeMembersDeepEqualCustomComparator) {
  // Mutate grandchildren structure.
  for (size_t i = 0; i < 2; ++i) {
    for (size_t j = 0; j < 2; ++j) {
      auto ltree = verible::testing::MakeExampleFamilyTree();
      auto rtree = verible::testing::MakeExampleFamilyTree();
      const std::vector<size_t> path({i, j});
      auto &lchild = DescendPath(ltree, path.begin(), path.end());
      auto &rchild = DescendPath(rtree, path.begin(), path.end());
      lchild.Value().name = "larry";
      rchild.Value().name = "sergey";

      {
        const auto result_pair = DeepEqual(ltree, rtree);
        EXPECT_EQ(result_pair.left, &lchild);
        EXPECT_EQ(result_pair.right, &rchild);
      }
      {
        const auto result_pair =
            DeepEqual(ltree, rtree, EqualNamedIntervalIgnoreName);
        EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
        EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
      }
    }
  }
}

TEST(VectorTreeTest, NearestCommonAncestorNoneMutable) {
  using tree_type = VectorTree<int>;
  tree_type tree1{0}, tree2{0};
  EXPECT_EQ(NearestCommonAncestor(tree1, tree2), nullptr);
  EXPECT_EQ(NearestCommonAncestor(tree2, tree1), nullptr);
}

TEST(VectorTreeTest, NearestCommonAncestorNoneConst) {
  using tree_type = VectorTree<int>;
  const tree_type tree1{0}, tree2{0};
  EXPECT_EQ(NearestCommonAncestor(tree1, tree2), nullptr);
  EXPECT_EQ(NearestCommonAncestor(tree2, tree1), nullptr);
}

TEST(VectorTreeTest, NearestCommonAncestorSameMutable) {
  using tree_type = VectorTree<int>;
  tree_type tree{0};
  EXPECT_EQ(NearestCommonAncestor(tree, tree), &tree);
  EXPECT_EQ(NearestCommonAncestor(tree, tree), &tree);
}

TEST(VectorTreeTest, NearestCommonAncestorSameConst) {
  using tree_type = VectorTree<int>;
  const tree_type tree{0};
  EXPECT_EQ(NearestCommonAncestor(tree, tree), &tree);
  EXPECT_EQ(NearestCommonAncestor(tree, tree), &tree);
}

TEST(VectorTreeTest, NearestCommonAncestorOneIsRootConst) {
  using tree_type = VectorTree<int>;
  const tree_type tree(1,            //
                       tree_type(2,  //
                                 tree_type(4), tree_type(5)),
                       tree_type(3,  //
                                 tree_type(6), tree_type(7)));

  for (int i = 0; i < 2; ++i) {
    {
      const auto path = {i};
      auto &child = DescendPath(tree, path.begin(), path.end());
      EXPECT_EQ(NearestCommonAncestor(tree, child), &tree);
      EXPECT_EQ(NearestCommonAncestor(child, tree), &tree);
    }
    for (int j = 0; j < 2; ++j) {
      const auto path = {i, j};
      auto &grandchild = DescendPath(tree, path.begin(), path.end());
      EXPECT_EQ(NearestCommonAncestor(tree, grandchild), &tree);
      EXPECT_EQ(NearestCommonAncestor(grandchild, tree), &tree);
    }
  }
}

TEST(VectorTreeTest, NearestCommonAncestorNeitherIsRootConst) {
  using tree_type = VectorTree<int>;
  const tree_type tree(1,            //
                       tree_type(2,  //
                                 tree_type(4), tree_type(5)),
                       tree_type(3,  //
                                 tree_type(6), tree_type(7)));
  auto &left = tree.Children()[0];
  auto &right = tree.Children()[1];
  EXPECT_EQ(NearestCommonAncestor(left, right), &tree);
  EXPECT_EQ(NearestCommonAncestor(right, left), &tree);

  for (int i = 0; i < 2; ++i) {
    {
      const auto left_path = {0, i};
      auto &left_grandchild =
          DescendPath(tree, left_path.begin(), left_path.end());
      EXPECT_EQ(NearestCommonAncestor(left, left_grandchild), &left);
      EXPECT_EQ(NearestCommonAncestor(left_grandchild, left), &left);
      EXPECT_EQ(NearestCommonAncestor(right, left_grandchild), &tree);
      EXPECT_EQ(NearestCommonAncestor(left_grandchild, right), &tree);
    }
    {
      const auto right_path = {1, i};
      auto &right_grandchild =
          DescendPath(tree, right_path.begin(), right_path.end());
      EXPECT_EQ(NearestCommonAncestor(right, right_grandchild), &right);
      EXPECT_EQ(NearestCommonAncestor(right_grandchild, right), &right);
      EXPECT_EQ(NearestCommonAncestor(left, right_grandchild), &tree);
      EXPECT_EQ(NearestCommonAncestor(right_grandchild, left), &tree);
    }
  }
}

TEST(VectorTreeTest, ApplyPreOrderPrint) {
  const auto tree = verible::testing::MakeExampleFamilyTree();

  std::ostringstream stream;
  ApplyPreOrder(tree, [&stream](const NamedInterval &interval) {
    IntervalPrinter(&stream, interval);
  });
  EXPECT_EQ(stream.str(), absl::StrJoin(
                              {
                                  "(0, 4, grandparent)",
                                  "(0, 2, parent1)",
                                  "(0, 1, child1)",
                                  "(1, 2, child2)",
                                  "(2, 4, parent2)",
                                  "(2, 3, child3)",
                                  "(3, 4, child4)",
                              },
                              "\n") +
                              "\n");
}

TEST(VectorTreeTest, ApplyPreOrderPrintTransformed) {
  const auto orig_tree = verible::testing::MakeExampleFamilyTree();
  const auto tree =
      Transform<VectorTree<NameOnly>>(orig_tree, NameOnlyConverter);

  std::ostringstream stream;
  ApplyPreOrder(tree, [&stream](const NameOnly &n) { stream << n; });
  EXPECT_EQ(stream.str(), absl::StrJoin(
                              {
                                  "(grandparent)",
                                  "(parent1)",
                                  "(child1)",
                                  "(child2)",
                                  "(parent2)",
                                  "(child3)",
                                  "(child4)",
                              },
                              "\n") +
                              "\n");
}

TEST(VectorTreeTest, ApplyPostOrderPrint) {
  const auto tree = verible::testing::MakeExampleFamilyTree();

  std::ostringstream stream;
  ApplyPostOrder(tree, [&stream](const NamedInterval &interval) {
    IntervalPrinter(&stream, interval);
  });
  EXPECT_EQ(stream.str(), absl::StrJoin(
                              {
                                  "(0, 1, child1)",
                                  "(1, 2, child2)",
                                  "(0, 2, parent1)",
                                  "(2, 3, child3)",
                                  "(3, 4, child4)",
                                  "(2, 4, parent2)",
                                  "(0, 4, grandparent)",
                              },
                              "\n") +
                              "\n");
}

TEST(VectorTreeTest, ApplyPreOrderVerify) {
  const auto tree = verible::testing::MakeExampleFamilyTree();
  // Verify invariant at every node.
  ApplyPreOrder(tree, verible::testing::VerifyInterval);
}

TEST(VectorTreeTest, ApplyPostOrderVerify) {
  const auto tree = verible::testing::MakeExampleFamilyTree();
  // Verify invariant at every node.
  ApplyPostOrder(tree, verible::testing::VerifyInterval);
}

TEST(VectorTreeTest, ApplyPreOrderTransformValue) {
  auto tree = verible::testing::MakeExampleFamilyTree();

  // Transform intervals.
  std::vector<absl::string_view> visit_order;
  const int shift = 2;
  ApplyPreOrder(tree, [=, &visit_order](NamedInterval &interval) {
    visit_order.push_back(interval.name);
    interval.left += shift;
    interval.right += shift;
  });
  EXPECT_THAT(visit_order,
              ElementsAre("grandparent", "parent1", "child1", "child2",
                          "parent2", "child3", "child4"));

  // Print output for verification.
  std::ostringstream stream;
  ApplyPreOrder(tree, [&stream](const NamedInterval &interval) {
    IntervalPrinter(&stream, interval);
  });
  EXPECT_EQ(stream.str(), absl::StrJoin(
                              {
                                  "(2, 6, grandparent)",
                                  "(2, 4, parent1)",
                                  "(2, 3, child1)",
                                  "(3, 4, child2)",
                                  "(4, 6, parent2)",
                                  "(4, 5, child3)",
                                  "(5, 6, child4)",
                              },
                              "\n") +
                              "\n");
}

TEST(VectorTreeTest, ApplyPreOrderTransformNode) {
  auto tree = verible::testing::MakeExampleFamilyTree();

  // Transform intervals.
  std::vector<absl::string_view> visit_order;
  const int shift = 2;
  ApplyPreOrder(tree, [=, &visit_order](VectorTreeTestType &node) {
    auto &interval = node.Value();
    visit_order.push_back(interval.name);
    interval.left += shift;
    interval.right += shift;
  });
  EXPECT_THAT(visit_order,
              ElementsAre("grandparent", "parent1", "child1", "child2",
                          "parent2", "child3", "child4"));

  // Print output for verification.
  std::ostringstream stream;
  ApplyPreOrder(tree, [&stream](const NamedInterval &interval) {
    IntervalPrinter(&stream, interval);
  });
  EXPECT_EQ(stream.str(), absl::StrJoin(
                              {
                                  "(2, 6, grandparent)",
                                  "(2, 4, parent1)",
                                  "(2, 3, child1)",
                                  "(3, 4, child2)",
                                  "(4, 6, parent2)",
                                  "(4, 5, child3)",
                                  "(5, 6, child4)",
                              },
                              "\n") +
                              "\n");
}

TEST(VectorTreeTest, ApplyPostOrderTransformValue) {
  auto tree = verible::testing::MakeExampleFamilyTree();

  // Transform intervals.
  std::vector<absl::string_view> visit_order;
  const int shift = 1;
  ApplyPostOrder(tree, [=, &visit_order](NamedInterval &interval) {
    visit_order.push_back(interval.name);
    interval.left += shift;
    interval.right += shift;
  });
  EXPECT_THAT(visit_order, ElementsAre("child1", "child2", "parent1", "child3",
                                       "child4", "parent2", "grandparent"));

  // Print output for verification.
  std::ostringstream stream;
  ApplyPostOrder(tree, [&stream](const NamedInterval &interval) {
    IntervalPrinter(&stream, interval);
  });
  EXPECT_EQ(stream.str(), absl::StrJoin(
                              {
                                  "(1, 2, child1)",
                                  "(2, 3, child2)",
                                  "(1, 3, parent1)",
                                  "(3, 4, child3)",
                                  "(4, 5, child4)",
                                  "(3, 5, parent2)",
                                  "(1, 5, grandparent)",
                              },
                              "\n") +
                              "\n");
}

TEST(VectorTreeTest, ApplyPostOrderTransformNode) {
  auto tree = verible::testing::MakeExampleFamilyTree();

  // Transform intervals.
  std::vector<absl::string_view> visit_order;
  const int shift = 1;
  ApplyPostOrder(tree, [=, &visit_order](VectorTreeTestType &node) {
    auto &interval = node.Value();
    visit_order.push_back(interval.name);
    interval.left += shift;
    interval.right += shift;
  });
  EXPECT_THAT(visit_order, ElementsAre("child1", "child2", "parent1", "child3",
                                       "child4", "parent2", "grandparent"));

  // Print output for verification.
  std::ostringstream stream;
  ApplyPostOrder(tree, [&stream](const NamedInterval &interval) {
    IntervalPrinter(&stream, interval);
  });
  EXPECT_EQ(stream.str(), absl::StrJoin(
                              {
                                  "(1, 2, child1)",
                                  "(2, 3, child2)",
                                  "(1, 3, parent1)",
                                  "(3, 4, child3)",
                                  "(4, 5, child4)",
                                  "(3, 5, parent2)",
                                  "(1, 5, grandparent)",
                              },
                              "\n") +
                              "\n");
}

TEST(VectorTreeTest, HoistOnlyChildRootOnly) {
  VectorTreeTestType tree(verible::testing::MakeRootOnlyExampleTree());
  // No children, no change.
  EXPECT_FALSE(HoistOnlyChild(tree));

  EXPECT_TRUE(is_leaf(tree));
  EXPECT_EQ(tree.Parent(), nullptr);
  EXPECT_EQ(NumAncestors(tree), 0);
  EXPECT_EQ(BirthRank(tree), 0);  // no parent
  EXPECT_EQ(&Root(tree), &tree);

  const auto &value = tree.Value();
  EXPECT_EQ(value.left, 0);
  EXPECT_EQ(value.right, 2);
  EXPECT_EQ(value.name, "root");

  ExpectPath(tree, "{}");
}

TEST(VectorTreeTest, HoistOnlyChildOneChildTreeGreatestAncestor) {
  VectorTreeTestType tree(verible::testing::MakeOneChildPolicyExampleTree());
  // effectively remove the "root" generation
  EXPECT_TRUE(HoistOnlyChild(tree));
  {
    const auto &child = tree;
    EXPECT_EQ(child.Parent(), nullptr);
    EXPECT_EQ(&Root(child), &tree);
    EXPECT_FALSE(is_leaf(child));
    EXPECT_EQ(NumAncestors(child), 0);
    EXPECT_EQ(BirthRank(child), 0);

    const auto &cvalue = child.Value();
    EXPECT_EQ(cvalue.left, 0);
    EXPECT_EQ(cvalue.right, 3);
    EXPECT_EQ(cvalue.name, "gen1");
    ExpectPath(child, "{}");

    EXPECT_EQ(verible::NextSibling(child), nullptr);
    EXPECT_EQ(verible::PreviousSibling(child), nullptr);

    // The invoking node need not be a leaf.
    EXPECT_EQ(NextLeaf(child), nullptr);
    EXPECT_EQ(PreviousLeaf(child), nullptr);

    {
      const auto &grandchild = child.Children().front();
      EXPECT_EQ(grandchild.Parent(), &child);
      EXPECT_EQ(&Root(grandchild), &tree);
      EXPECT_TRUE(is_leaf(grandchild));
      EXPECT_EQ(NumAncestors(grandchild), 1);
      EXPECT_EQ(BirthRank(grandchild), 0);

      const auto &gcvalue = grandchild.Value();
      EXPECT_EQ(gcvalue.left, 0);
      EXPECT_EQ(gcvalue.right, 3);
      EXPECT_EQ(gcvalue.name, "gen2");
      ExpectPath(grandchild, "{0}");

      // As the ancestry chain is linear, Leftmost == Rightmost.
      EXPECT_EQ(&LeftmostDescendant(child), &grandchild);
      EXPECT_EQ(&RightmostDescendant(child), &grandchild);
      EXPECT_EQ(&LeftmostDescendant(tree), &grandchild);
      EXPECT_EQ(&RightmostDescendant(tree), &grandchild);

      EXPECT_EQ(verible::NextSibling(grandchild), nullptr);
      EXPECT_EQ(verible::PreviousSibling(grandchild), nullptr);

      // There is still only a single leaf in a one-child tree,
      // thus next and previous do not exist.
      EXPECT_EQ(NextLeaf(grandchild), nullptr);
      EXPECT_EQ(PreviousLeaf(grandchild), nullptr);
    }
  }
}

TEST(VectorTreeTest, HoistOnlyChildOneChildTreeMiddleAncestor) {
  VectorTreeTestType tree(verible::testing::MakeOneChildPolicyExampleTree());
  EXPECT_TRUE(HoistOnlyChild(tree.Children().front()));
  {
    const auto &value = tree.Value();
    EXPECT_EQ(value.left, 0);
    EXPECT_EQ(value.right, 3);
    EXPECT_EQ(value.name, "root");

    EXPECT_EQ(verible::NextSibling(tree), nullptr);
    EXPECT_EQ(verible::PreviousSibling(tree), nullptr);

    // The invoking node need not be a leaf.
    EXPECT_EQ(NextLeaf(tree), nullptr);
    EXPECT_EQ(PreviousLeaf(tree), nullptr);

    // The "gen1" node is removed, and now the grandchild is directly linked.
    {
      const auto &grandchild = tree.Children().front();
      EXPECT_EQ(grandchild.Parent(), &tree);
      EXPECT_EQ(&Root(grandchild), &tree);
      EXPECT_TRUE(is_leaf(grandchild));
      EXPECT_EQ(NumAncestors(grandchild), 1);
      EXPECT_EQ(BirthRank(grandchild), 0);

      const auto &gcvalue = grandchild.Value();
      EXPECT_EQ(gcvalue.left, 0);
      EXPECT_EQ(gcvalue.right, 3);
      EXPECT_EQ(gcvalue.name, "gen2");
      ExpectPath(grandchild, "{0}");

      // As the ancestry chain is linear, Leftmost == Rightmost.
      EXPECT_EQ(&LeftmostDescendant(tree), &grandchild);
      EXPECT_EQ(&RightmostDescendant(tree), &grandchild);

      EXPECT_EQ(verible::NextSibling(grandchild), nullptr);
      EXPECT_EQ(verible::PreviousSibling(grandchild), nullptr);

      // There is still only a single leaf in a one-child tree,
      // thus next and previous do not exist.
      EXPECT_EQ(NextLeaf(grandchild), nullptr);
      EXPECT_EQ(PreviousLeaf(grandchild), nullptr);
    }
  }
}

TEST(VectorTreeTest, HoistOnlyChildFamilyTree) {
  VectorTreeTestType tree(verible::testing::MakeExampleFamilyTree());
  // No change because each generation has more than one child.
  EXPECT_FALSE(HoistOnlyChild(tree));
}

// Copy-extract tree values from a node's direct children only.
// TODO(fangism): Adapt this into a public method of VectorTree.
template <typename T>
static std::vector<typename T::value_type> NodeValues(const T &node) {
  std::vector<typename T::value_type> result;
  result.reserve(node.Children().size());
  for (const auto &child : node.Children()) {
    result.emplace_back(child.Value());
  }
  return result;
}

TEST(VectorTreeTest, AdoptSubtreesFromEmptyToEmpty) {
  using tree_type = VectorTree<int>;
  tree_type tree1(1), tree2(2);  // no subtrees
  EXPECT_TRUE(is_leaf(tree1));
  EXPECT_TRUE(is_leaf(tree2));

  AdoptSubtreesFrom(tree1, &tree2);
  EXPECT_TRUE(is_leaf(tree1));
  EXPECT_TRUE(is_leaf(tree2));
}

TEST(VectorTreeTest, AdoptSubtreesFromEmptyToNonempty) {
  using tree_type = VectorTree<int>;
  tree_type tree1(1, tree_type(4)), tree2(2);
  EXPECT_THAT(NodeValues(tree1), ElementsAre(4));
  EXPECT_THAT(NodeValues(tree2), ElementsAre());

  AdoptSubtreesFrom(tree1, &tree2);
  EXPECT_THAT(NodeValues(tree1), ElementsAre(4));
  EXPECT_THAT(NodeValues(tree2), ElementsAre());
}

TEST(VectorTreeTest, AdoptSubtreesFromNonemptyToEmpty) {
  using tree_type = VectorTree<int>;
  tree_type tree1(1), tree2(2, tree_type(5));
  EXPECT_THAT(NodeValues(tree1), ElementsAre());
  EXPECT_THAT(NodeValues(tree2), ElementsAre(5));

  AdoptSubtreesFrom(tree1, &tree2);
  EXPECT_THAT(NodeValues(tree1), ElementsAre(5));
  EXPECT_THAT(NodeValues(tree2), ElementsAre());
}

TEST(VectorTreeTest, AdoptSubtreesFromNonemptyToNonempty) {
  using tree_type = VectorTree<int>;
  tree_type tree1(1, tree_type(3), tree_type(6)),
      tree2(2, tree_type(5), tree_type(8));
  EXPECT_THAT(NodeValues(tree1), ElementsAre(3, 6));
  EXPECT_THAT(NodeValues(tree2), ElementsAre(5, 8));

  AdoptSubtreesFrom(tree1, &tree2);
  EXPECT_THAT(NodeValues(tree1), ElementsAre(3, 6, 5, 8));
  EXPECT_THAT(NodeValues(tree2), ElementsAre());
}

TEST(VectorTreeTest, MergeConsecutiveSiblingsTooFewElements) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2));
  auto adder = [](int *left, const int &right) { *left += right; };
  EXPECT_THAT(NodeValues(tree), ElementsAre(2));
  EXPECT_DEATH(MergeConsecutiveSiblings(tree, 0, adder), "");
}

TEST(VectorTreeTest, MergeConsecutiveSiblingsOutOfBounds) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2), tree_type(3));
  auto adder = [](int *left, const int &right) { *left += right; };
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3));
  EXPECT_DEATH(MergeConsecutiveSiblings(tree, 1, adder), "");
}

TEST(VectorTreeTest, MergeConsecutiveSiblingsAddLeaves) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2), tree_type(3), tree_type(4), tree_type(5));
  auto adder = [](int *left, const int &right) { *left += right; };
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  VLOG(1) << __FUNCTION__ << ": before first merge";

  MergeConsecutiveSiblings(tree, 1, adder);  // combine middle two subtrees
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 7, 5));
  VLOG(1) << __FUNCTION__ << ": after first merge";

  MergeConsecutiveSiblings(tree, 1, adder);  // combine last two subtrees
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 12));
  VLOG(1) << __FUNCTION__ << ": after second merge";

  MergeConsecutiveSiblings(tree, 0, adder);  // combine only two subtrees
  EXPECT_THAT(NodeValues(tree), ElementsAre(14));
  VLOG(1) << __FUNCTION__ << ": after third merge";
}

TEST(VectorTreeTest, MergeConsecutiveSiblingsConcatenateSubtreesOnce) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,            //
                 tree_type(2,  //
                           tree_type(6), tree_type(7)),
                 tree_type(3,  //
                           tree_type(8), tree_type(9)),
                 tree_type(4,  //
                           tree_type(10), tree_type(11)),
                 tree_type(5,  //
                           tree_type(12), tree_type(13)));
  auto subtractor = [](int *left, const int &right) { *left -= right; };
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  MergeConsecutiveSiblings(tree, 1, subtractor);  // combine middle two subtrees
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, /* 3 - 4 */ -1, 5));
  EXPECT_THAT(NodeValues(tree.Children()[1]), ElementsAre(8, 9, 10, 11));
}

TEST(VectorTreeTest, MergeConsecutiveSiblingsConcatenateSubtrees) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,            //
                 tree_type(2,  //
                           tree_type(6), tree_type(7)),
                 tree_type(3,  //
                           tree_type(8), tree_type(9)),
                 tree_type(4,  //
                           tree_type(10), tree_type(11)),
                 tree_type(5,  //
                           tree_type(12), tree_type(13)));
  auto subtractor = [](int *left, const int &right) { *left -= right; };
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  MergeConsecutiveSiblings(tree, 0, subtractor);  // combine first two subtrees
  EXPECT_THAT(NodeValues(tree), ElementsAre(/* 2 - 3 */ -1, 4, 5));
  EXPECT_THAT(NodeValues(tree.Children()[0]), ElementsAre(6, 7, 8, 9));

  MergeConsecutiveSiblings(tree, 1, subtractor);  // combine last two subtrees
  EXPECT_THAT(NodeValues(tree), ElementsAre(-1, /* 4 - 5 */ -1));
  EXPECT_THAT(NodeValues(tree.Children()[1]), ElementsAre(10, 11, 12, 13));

  MergeConsecutiveSiblings(tree, 0, subtractor);  // combine only two subtrees
  EXPECT_THAT(NodeValues(tree), ElementsAre(/* -1 - -1 */ 0));
  EXPECT_THAT(NodeValues(tree.Children()[0]),
              ElementsAre(6, 7, 8, 9, 10, 11, 12, 13));
}

TEST(VectorTreeTest, RemoveSelfFromParentRoot) {
  using tree_type = VectorTree<int>;
  tree_type tree(1);
  EXPECT_DEATH(RemoveSelfFromParent(tree), "");
}

TEST(VectorTreeTest, RemoveSelfFromParentFirstChild) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,             //
                 tree_type(2),  // no grandchildren
                 tree_type(3,   //
                           tree_type(8), tree_type(9)),
                 tree_type(4),  // no grandchildren
                 tree_type(5,   //
                           tree_type(12), tree_type(13)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(1,            //
                                            // tree_type(2),  // deleted
                              tree_type(3,  //
                                        tree_type(8), tree_type(9)),
                              tree_type(4),  // no grandchildren
                              tree_type(5,   //
                                        tree_type(12), tree_type(13)));
  RemoveSelfFromParent(tree.Children().front());
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, RemoveSelfFromParentMiddleChildWithGrandchildren) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,             //
                 tree_type(2),  // no grandchildren
                 tree_type(3,   //
                           tree_type(8), tree_type(9)),
                 tree_type(4),  // no grandchildren
                 tree_type(5,   //
                           tree_type(12), tree_type(13)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(
      1,             //
      tree_type(2),  //
      // tree_type(3, tree_type(8), tree_type(9)),  // deleted
      tree_type(4),  // no grandchildren
      tree_type(5,   //
                tree_type(12), tree_type(13)));
  RemoveSelfFromParent(tree.Children()[1]);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, RemoveSelfFromParentMiddleChildWithoutGrandchildren) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,             //
                 tree_type(2),  // no grandchildren
                 tree_type(3,   //
                           tree_type(8), tree_type(9)),
                 tree_type(4),  // no grandchildren
                 tree_type(5,   //
                           tree_type(12), tree_type(13)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(1,             //
                              tree_type(2),  //
                              tree_type(3,   //
                                        tree_type(8), tree_type(9)),
                              // tree_type(4),  // deleted
                              tree_type(5,  //
                                        tree_type(12), tree_type(13)));
  RemoveSelfFromParent(tree.Children()[2]);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, RemoveSelfFromParentLastChild) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,             //
                 tree_type(2),  // no grandchildren
                 tree_type(3,   //
                           tree_type(8), tree_type(9)),
                 tree_type(4),  // no grandchildren
                 tree_type(5,   //
                           tree_type(12), tree_type(13)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(
      1,             //
      tree_type(2),  //
      tree_type(3,   //
                tree_type(8), tree_type(9)),
      tree_type(4)  // no grandchildren
                    // tree_type(5, tree_type(12), tree_type(13))  // deleted
  );
  RemoveSelfFromParent(tree.Children().back());
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOnceNoChildren) {
  using tree_type = VectorTree<int>;
  tree_type tree(1);
  EXPECT_THAT(NodeValues(tree), ElementsAre());

  const tree_type expect_tree(1);
  FlattenOnce(tree);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOnceNoGrandchildren) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,  // no grandchildren
                 tree_type(2), tree_type(3), tree_type(4), tree_type(5));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(1);
  FlattenOnce(tree);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOnceOneGrandchild) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2, tree_type(3)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2));

  const tree_type expect_tree(1, tree_type(3));
  FlattenOnce(tree);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOnceMixed) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,             //
                 tree_type(2),  // no grandchildren
                 tree_type(3,   //
                           tree_type(8), tree_type(9)),
                 tree_type(4),  // no grandchildren
                 tree_type(5,   //
                           tree_type(12), tree_type(13)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(1,  //
                              tree_type(8), tree_type(9), tree_type(12),
                              tree_type(13));
  FlattenOnce(tree);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOnceAllNonempty) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,            //
                 tree_type(2,  //
                           tree_type(6), tree_type(7)),
                 tree_type(3,  //
                           tree_type(8), tree_type(9)),
                 tree_type(4,  //
                           tree_type(10), tree_type(11)),
                 tree_type(5,  //
                           tree_type(12), tree_type(13)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(1,  //
                              tree_type(6), tree_type(7), tree_type(8),
                              tree_type(9), tree_type(10), tree_type(11),
                              tree_type(12), tree_type(13));
  FlattenOnce(tree);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOnceGreatgrandchildren) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,                      //
                 tree_type(2,            //
                           tree_type(6,  //
                                     tree_type(7))),
                 tree_type(3,            //
                           tree_type(8,  //
                                     tree_type(9))),
                 tree_type(4,             //
                           tree_type(10,  //
                                     tree_type(11))),
                 tree_type(5,             //
                           tree_type(12,  //
                                     tree_type(13))));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(1,            //
                              tree_type(6,  //
                                        tree_type(7)),
                              tree_type(8,  //
                                        tree_type(9)),
                              tree_type(10,  //
                                        tree_type(11)),
                              tree_type(12,  //
                                        tree_type(13)));
  FlattenOnce(tree);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenNoChildren) {
  using tree_type = VectorTree<int>;
  tree_type tree(1);
  EXPECT_THAT(NodeValues(tree), ElementsAre());

  const tree_type expect_tree(1);
  std::vector<size_t> new_offsets;
  FlattenOnlyChildrenWithChildren(tree, &new_offsets);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  EXPECT_TRUE(new_offsets.empty());
}

TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenNoChildrenNoOffsets) {
  using tree_type = VectorTree<int>;
  tree_type tree(1);
  EXPECT_THAT(NodeValues(tree), ElementsAre());

  const tree_type expect_tree(1);
  FlattenOnlyChildrenWithChildren(tree /* no offsets */);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenNoGrandchildren) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,  // no grandchildren
                 tree_type(2), tree_type(3), tree_type(4), tree_type(5));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(1,  // all children preserved
                              tree_type(2), tree_type(3), tree_type(4),
                              tree_type(5));
  std::vector<size_t> new_offsets;
  FlattenOnlyChildrenWithChildren(tree, &new_offsets);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  EXPECT_THAT(new_offsets, ElementsAre(0, 1, 2, 3));
}

TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenOneGrandchild) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2, tree_type(3)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2));

  const tree_type expect_tree(1, tree_type(3));
  std::vector<size_t> new_offsets;
  FlattenOnlyChildrenWithChildren(tree, &new_offsets);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  EXPECT_THAT(new_offsets, ElementsAre(0));
}

TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenOneGrandchildNoOffsets) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2, tree_type(3)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2));

  const tree_type expect_tree(1, tree_type(3));
  FlattenOnlyChildrenWithChildren(tree /* no offsets */);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenTwoGrandchildren) {
  using tree_type = VectorTree<int>;
  tree_type tree(1, tree_type(2, tree_type(3), tree_type(7)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2));

  const tree_type expect_tree(1, tree_type(3), tree_type(7));
  std::vector<size_t> new_offsets;
  FlattenOnlyChildrenWithChildren(tree, &new_offsets);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  EXPECT_THAT(new_offsets, ElementsAre(0));
}

TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenMixed) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,             //
                 tree_type(2),  // no grandchildren
                 tree_type(3,   //
                           tree_type(8), tree_type(9)),
                 tree_type(4),  // no grandchildren
                 tree_type(5,   //
                           tree_type(12), tree_type(13)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(1,                           //
                              tree_type(2),                //
                              tree_type(8), tree_type(9),  //
                              tree_type(4),                //
                              tree_type(12), tree_type(13));
  std::vector<size_t> new_offsets;
  FlattenOnlyChildrenWithChildren(tree, &new_offsets);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  EXPECT_THAT(new_offsets, ElementsAre(0, 1, 3, 4));
}

TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenAllNonempty) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,            //
                 tree_type(2,  //
                           tree_type(6), tree_type(7)),
                 tree_type(3,  //
                           tree_type(8), tree_type(9)),
                 tree_type(4,  //
                           tree_type(10), tree_type(11)),
                 tree_type(5,  //
                           tree_type(12), tree_type(13)));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(1,  //
                              tree_type(6), tree_type(7), tree_type(8),
                              tree_type(9), tree_type(10), tree_type(11),
                              tree_type(12), tree_type(13));
  std::vector<size_t> new_offsets;
  FlattenOnlyChildrenWithChildren(tree, &new_offsets);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  EXPECT_THAT(new_offsets, ElementsAre(0, 2, 4, 6));
}

TEST(VectorTreeTest, FlattenOnlyChildrenWithChildrenGreatgrandchildren) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,                      //
                 tree_type(2,            //
                           tree_type(6,  //
                                     tree_type(7))),
                 tree_type(3,            //
                           tree_type(8,  //
                                     tree_type(9))),
                 tree_type(4,             //
                           tree_type(10,  //
                                     tree_type(11))),
                 tree_type(5,             //
                           tree_type(12,  //
                                     tree_type(13))));
  EXPECT_THAT(NodeValues(tree), ElementsAre(2, 3, 4, 5));

  const tree_type expect_tree(1,            //
                              tree_type(6,  //
                                        tree_type(7)),
                              tree_type(8,  //
                                        tree_type(9)),
                              tree_type(10,  //
                                        tree_type(11)),
                              tree_type(12,  //
                                        tree_type(13)));
  std::vector<size_t> new_offsets;
  FlattenOnlyChildrenWithChildren(tree, &new_offsets);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
  EXPECT_THAT(new_offsets, ElementsAre(0, 1, 2, 3));
}

TEST(VectorTreeTest, FlattenOneChildEmpty) {
  using tree_type = VectorTree<int>;
  tree_type tree(4);  // no children
  EXPECT_DEATH(FlattenOneChild(tree, 0), "");
}

TEST(VectorTreeTest, FlattenOneChildOnlyChildNoGrandchildren) {
  using tree_type = VectorTree<int>;
  tree_type tree(4, tree_type(2));  // no grandchildren
  const tree_type expect_tree(4);
  FlattenOneChild(tree, 0);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOneChildOnlyChildOneGrandchild) {
  using tree_type = VectorTree<int>;
  tree_type tree(4, tree_type(2, tree_type(11)));  // with grandchild
  const tree_type expect_tree(4, tree_type(11));
  FlattenOneChild(tree, 0);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOneChildFirstChildInFamilyTree) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,            //
                 tree_type(2,  //
                           tree_type(6), tree_type(7)),
                 tree_type(3,  //
                           tree_type(8), tree_type(9)),
                 tree_type(4,  //
                           tree_type(10), tree_type(11)),
                 tree_type(5,  //
                           tree_type(12), tree_type(13)));
  const tree_type expect_tree(1,             //
                              tree_type(6),  //
                              tree_type(7),  //
                              tree_type(3,   //
                                        tree_type(8), tree_type(9)),
                              tree_type(4,  //
                                        tree_type(10), tree_type(11)),
                              tree_type(5,  //
                                        tree_type(12), tree_type(13)));
  FlattenOneChild(tree, 0);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOneChildMiddleChildInFamilyTree) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,            //
                 tree_type(2,  //
                           tree_type(6), tree_type(7)),
                 tree_type(3,  //
                           tree_type(8), tree_type(9)),
                 tree_type(4,  //
                           tree_type(10), tree_type(11)),
                 tree_type(5,  //
                           tree_type(12), tree_type(13)));
  const tree_type expect_tree(1,            //
                              tree_type(2,  //
                                        tree_type(6), tree_type(7)),
                              tree_type(8),  //
                              tree_type(9),  //
                              tree_type(4,   //
                                        tree_type(10), tree_type(11)),
                              tree_type(5,  //
                                        tree_type(12), tree_type(13)));
  FlattenOneChild(tree, 1);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, FlattenOneChildLastChildInFamilyTree) {
  using tree_type = VectorTree<int>;
  tree_type tree(1,            //
                 tree_type(2,  //
                           tree_type(6), tree_type(7)),
                 tree_type(3,  //
                           tree_type(8), tree_type(9)),
                 tree_type(4,  //
                           tree_type(10), tree_type(11)),
                 tree_type(5,  //
                           tree_type(12), tree_type(13)));
  const tree_type expect_tree(1,            //
                              tree_type(2,  //
                                        tree_type(6), tree_type(7)),
                              tree_type(3,  //
                                        tree_type(8), tree_type(9)),
                              tree_type(4,  //
                                        tree_type(10), tree_type(11)),
                              tree_type(12),  //
                              tree_type(13));
  FlattenOneChild(tree, 3);
  const auto result_pair = DeepEqual(tree, expect_tree);
  EXPECT_EQ(result_pair.left, nullptr) << *result_pair.left;
  EXPECT_EQ(result_pair.right, nullptr) << *result_pair.right;
}

TEST(VectorTreeTest, PrintTree) {
  const auto tree = verible::testing::MakeExampleFamilyTree();
  std::ostringstream stream;
  stream << tree;
  EXPECT_EQ(stream.str(), R"({ ((0, 4, grandparent))
  { ((0, 2, parent1))
    { ((0, 1, child1)) }
    { ((1, 2, child2)) }
  }
  { ((2, 4, parent2))
    { ((2, 3, child3)) }
    { ((3, 4, child4)) }
  }
})");
}

TEST(VectorTreeTest, PrintTreeCustom) {
  const auto tree = verible::testing::MakeExampleFamilyTree();
  std::ostringstream stream;
  PrintTree(tree, &stream,
            [](std::ostream &s,
               const decltype(tree)::value_type &value) -> std::ostream & {
              return s << value.name;  // print only the name field
            });
  EXPECT_EQ(stream.str(), R"({ (grandparent)
  { (parent1)
    { (child1) }
    { (child2) }
  }
  { (parent2)
    { (child3) }
    { (child4) }
  }
})");
}

TEST(VectorTreeTest, ChildrenManipulation) {
  VectorTreeTestType tree(verible::testing::MakeExampleFamilyTree());

  auto &children_gp = tree.Children();

  children_gp.push_back(VectorTreeTestType(NamedInterval(4, 6, "parent3")));

  EXPECT_EQ(tree.Children().size(), 3);
  EXPECT_EQ(tree.Children().back().Value(), NamedInterval(4, 6, "parent3"));
  EXPECT_EQ(tree.Children().back().Parent(), &tree);

  auto &p3 = tree.Children().back();
  auto &children_p3 = p3.Children();

  children_p3.push_back(VectorTreeTestType(NamedInterval(4, 5, "child5")));
  children_p3.emplace_back(NamedInterval(5, 6, "child6"));

  EXPECT_EQ(p3.Children().size(), 2);

  EXPECT_EQ(p3.Children().at(0).Value(), NamedInterval(4, 5, "child5"));
  EXPECT_EQ(p3.Children().at(0).Parent(), &p3);

  EXPECT_EQ(p3.Children().at(1).Value(), NamedInterval(5, 6, "child6"));
  EXPECT_EQ(p3.Children().at(1).Parent(), &p3);

  auto &p2 = tree.Children().at(1);

  const NamedInterval original_p2_children[] = {
      p2.Children().at(0).Value(),
      p2.Children().at(1).Value(),
  };

  children_p3.insert(children_p3.begin(), p2.Children().begin(),
                     p2.Children().end());

  EXPECT_EQ(p3.Children().size(), 4);

  EXPECT_EQ(p3.Children().at(0).Value(), original_p2_children[0]);
  EXPECT_EQ(p3.Children().at(0).Parent(), &p3);

  EXPECT_EQ(p3.Children().at(1).Value(), original_p2_children[1]);
  EXPECT_EQ(p3.Children().at(1).Parent(), &p3);

  EXPECT_EQ(p3.Children().at(2).Value(), NamedInterval(4, 5, "child5"));
  EXPECT_EQ(p3.Children().at(2).Parent(), &p3);

  EXPECT_EQ(p3.Children().at(3).Value(), NamedInterval(5, 6, "child6"));
  EXPECT_EQ(p3.Children().at(3).Parent(), &p3);

  EXPECT_EQ(p2.Children().size(), 2);

  EXPECT_EQ(p2.Children().at(0).Value(), original_p2_children[0]);
  EXPECT_EQ(p2.Children().at(0).Parent(), &p2);

  EXPECT_EQ(p2.Children().at(1).Value(), original_p2_children[1]);
  EXPECT_EQ(p2.Children().at(1).Parent(), &p2);

  p2.Children().clear();

  EXPECT_EQ(p2.Children().size(), 0);

  p2.Children().assign({
      VectorTreeTestType(NamedInterval(0, 1, "foo")),
      VectorTreeTestType(NamedInterval(1, 2, "bar")),
      VectorTreeTestType(NamedInterval(2, 3, "baz")),
  });

  EXPECT_EQ(p2.Children().size(), 3);

  EXPECT_EQ(p2.Children().at(0).Value(), NamedInterval(0, 1, "foo"));
  EXPECT_EQ(p2.Children().at(0).Parent(), &p2);

  EXPECT_EQ(p2.Children().at(1).Value(), NamedInterval(1, 2, "bar"));
  EXPECT_EQ(p2.Children().at(1).Parent(), &p2);

  EXPECT_EQ(p2.Children().at(2).Value(), NamedInterval(2, 3, "baz"));
  EXPECT_EQ(p2.Children().at(2).Parent(), &p2);

  tree.Children().clear();
  EXPECT_TRUE(tree.Children().empty());
}

}  // namespace
}  // namespace verible