| // 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 |