From 7e117284029bfbfc2b638caa53335e1b2c53490e Mon Sep 17 00:00:00 2001 From: Thomas Lively Date: Fri, 6 Sep 2024 17:57:18 -0700 Subject: [NFC] Rename topological_orders.h to topological_sort.h (#6915) Now that the header includes topological sort utilities in addition to the utility that iterates over all topological orders, it makes more sense for it to be named topological_sort.h --- test/gtest/CMakeLists.txt | 2 +- test/gtest/topological-orders.cpp | 154 -------------------------------------- test/gtest/topological-sort.cpp | 154 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 155 insertions(+), 155 deletions(-) delete mode 100644 test/gtest/topological-orders.cpp create mode 100644 test/gtest/topological-sort.cpp (limited to 'test/gtest') diff --git a/test/gtest/CMakeLists.txt b/test/gtest/CMakeLists.txt index 17e880a4e..7ef72db13 100644 --- a/test/gtest/CMakeLists.txt +++ b/test/gtest/CMakeLists.txt @@ -13,7 +13,7 @@ set(unittest_SOURCES scc.cpp stringify.cpp suffix_tree.cpp - topological-orders.cpp + topological-sort.cpp type-builder.cpp wat-lexer.cpp validator.cpp diff --git a/test/gtest/topological-orders.cpp b/test/gtest/topological-orders.cpp deleted file mode 100644 index 67c56cbdb..000000000 --- a/test/gtest/topological-orders.cpp +++ /dev/null @@ -1,154 +0,0 @@ -/* - * Copyright 2024 WebAssembly Community Group participants - * - * 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 -#include -#include - -#include "support/topological_orders.h" -#include "gtest/gtest.h" - -using namespace wasm; - -using Graph = TopologicalSort::Graph; - -TEST(TopologicalSortTest, Empty) { - Graph graph; - TopologicalOrders orders(graph); - EXPECT_EQ(orders.begin(), orders.end()); -} - -TEST(TopologicalSortTest, Singleton) { - Graph graph(1); - TopologicalOrders orders(graph); - auto it = orders.begin(); - ASSERT_NE(it, orders.end()); - EXPECT_EQ(*it, std::vector{0}); - ++it; - EXPECT_EQ(it, orders.end()); -} - -TEST(TopologicalSortTest, Permutations) { - Graph graph(3); - TopologicalOrders orders(graph); - std::set> results(orders.begin(), orders.end()); - std::set> expected{ - {0, 1, 2}, - {0, 2, 1}, - {1, 0, 2}, - {1, 2, 0}, - {2, 0, 1}, - {2, 1, 0}, - }; - EXPECT_EQ(results, expected); -} - -TEST(TopologicalSortTest, Chain) { - constexpr Index n = 10; - Graph graph(n); - for (Index i = 1; i < n; ++i) { - graph[i].push_back(i - 1); - } - TopologicalOrders orders(graph); - std::set> results(orders.begin(), orders.end()); - std::set> expected{{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}}; - EXPECT_EQ(results, expected); -} - -TEST(TopologicalSortTest, TwoChains) { - Graph graph(4); - graph[0].push_back(2); - graph[1].push_back(3); - TopologicalOrders orders(graph); - std::set> results(orders.begin(), orders.end()); - std::set> expected{ - {0, 1, 2, 3}, - {0, 1, 3, 2}, - {0, 2, 1, 3}, - {1, 0, 2, 3}, - {1, 0, 3, 2}, - {1, 3, 0, 2}, - }; - EXPECT_EQ(results, expected); -} - -TEST(TopologicalSortTest, Diamond) { - Graph graph(4); - graph[0].push_back(1); - graph[0].push_back(2); - graph[1].push_back(3); - graph[2].push_back(3); - TopologicalOrders orders(graph); - std::set> results(orders.begin(), orders.end()); - std::set> expected{ - {0, 1, 2, 3}, - {0, 2, 1, 3}, - }; - EXPECT_EQ(results, expected); -} - -TEST(MinTopologicalSortTest, SortStrings) { - std::map> graph{ - {"animal", {"mammal"}}, - {"cat", {}}, - {"dog", {}}, - {"mammal", {"cat", "dog"}}}; - std::vector expected{"animal", "mammal", "cat", "dog"}; - EXPECT_EQ(TopologicalSort::sortOf(graph.begin(), graph.end()), expected); -} - -TEST(MinTopologicalSortTest, EmptyMinSort) { - Graph graph(0); - EXPECT_EQ(TopologicalSort::minSort<>(graph), std::vector{}); -} - -TEST(MinTopologicalSortTest, UnconstrainedMinSort) { - Graph graph(3); - std::vector expected{0, 1, 2}; - EXPECT_EQ(TopologicalSort::minSort(graph), expected); -} - -TEST(MinTopologicalSortTest, ReversedMinSort) { - Graph graph(3); - graph[2].push_back(1); - graph[1].push_back(0); - std::vector expected{2, 1, 0}; - EXPECT_EQ(TopologicalSort::minSort(graph), expected); -} - -TEST(MinTopologicalSortTest, OneBeforeZeroMinSort) { - Graph graph(3); - graph[1].push_back(0); - // 2 last because it is greater than 1 and 0 - std::vector expected{1, 0, 2}; - EXPECT_EQ(TopologicalSort::minSort(graph), expected); -} - -TEST(MinTopologicalSortTest, TwoBeforeOneMinSort) { - Graph graph(3); - graph[2].push_back(1); - // 0 first because it is less than 2 and 1 - std::vector expected{0, 2, 1}; - EXPECT_EQ(TopologicalSort::minSort(graph), expected); -} - -TEST(MinTopologicalSortTest, TwoBeforeZeroMinSort) { - Graph graph(3); - graph[2].push_back(0); - // 1 first because it is less than 2 and zero is not eligible. - std::vector expected{1, 2, 0}; - EXPECT_EQ(TopologicalSort::minSort(graph), expected); -} diff --git a/test/gtest/topological-sort.cpp b/test/gtest/topological-sort.cpp new file mode 100644 index 000000000..6a04a71ff --- /dev/null +++ b/test/gtest/topological-sort.cpp @@ -0,0 +1,154 @@ +/* + * Copyright 2024 WebAssembly Community Group participants + * + * 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 +#include +#include + +#include "support/topological_sort.h" +#include "gtest/gtest.h" + +using namespace wasm; + +using Graph = TopologicalSort::Graph; + +TEST(TopologicalSortTest, Empty) { + Graph graph; + TopologicalOrders orders(graph); + EXPECT_EQ(orders.begin(), orders.end()); +} + +TEST(TopologicalSortTest, Singleton) { + Graph graph(1); + TopologicalOrders orders(graph); + auto it = orders.begin(); + ASSERT_NE(it, orders.end()); + EXPECT_EQ(*it, std::vector{0}); + ++it; + EXPECT_EQ(it, orders.end()); +} + +TEST(TopologicalSortTest, Permutations) { + Graph graph(3); + TopologicalOrders orders(graph); + std::set> results(orders.begin(), orders.end()); + std::set> expected{ + {0, 1, 2}, + {0, 2, 1}, + {1, 0, 2}, + {1, 2, 0}, + {2, 0, 1}, + {2, 1, 0}, + }; + EXPECT_EQ(results, expected); +} + +TEST(TopologicalSortTest, Chain) { + constexpr Index n = 10; + Graph graph(n); + for (Index i = 1; i < n; ++i) { + graph[i].push_back(i - 1); + } + TopologicalOrders orders(graph); + std::set> results(orders.begin(), orders.end()); + std::set> expected{{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}}; + EXPECT_EQ(results, expected); +} + +TEST(TopologicalSortTest, TwoChains) { + Graph graph(4); + graph[0].push_back(2); + graph[1].push_back(3); + TopologicalOrders orders(graph); + std::set> results(orders.begin(), orders.end()); + std::set> expected{ + {0, 1, 2, 3}, + {0, 1, 3, 2}, + {0, 2, 1, 3}, + {1, 0, 2, 3}, + {1, 0, 3, 2}, + {1, 3, 0, 2}, + }; + EXPECT_EQ(results, expected); +} + +TEST(TopologicalSortTest, Diamond) { + Graph graph(4); + graph[0].push_back(1); + graph[0].push_back(2); + graph[1].push_back(3); + graph[2].push_back(3); + TopologicalOrders orders(graph); + std::set> results(orders.begin(), orders.end()); + std::set> expected{ + {0, 1, 2, 3}, + {0, 2, 1, 3}, + }; + EXPECT_EQ(results, expected); +} + +TEST(MinTopologicalSortTest, SortStrings) { + std::map> graph{ + {"animal", {"mammal"}}, + {"cat", {}}, + {"dog", {}}, + {"mammal", {"cat", "dog"}}}; + std::vector expected{"animal", "mammal", "cat", "dog"}; + EXPECT_EQ(TopologicalSort::sortOf(graph.begin(), graph.end()), expected); +} + +TEST(MinTopologicalSortTest, EmptyMinSort) { + Graph graph(0); + EXPECT_EQ(TopologicalSort::minSort<>(graph), std::vector{}); +} + +TEST(MinTopologicalSortTest, UnconstrainedMinSort) { + Graph graph(3); + std::vector expected{0, 1, 2}; + EXPECT_EQ(TopologicalSort::minSort(graph), expected); +} + +TEST(MinTopologicalSortTest, ReversedMinSort) { + Graph graph(3); + graph[2].push_back(1); + graph[1].push_back(0); + std::vector expected{2, 1, 0}; + EXPECT_EQ(TopologicalSort::minSort(graph), expected); +} + +TEST(MinTopologicalSortTest, OneBeforeZeroMinSort) { + Graph graph(3); + graph[1].push_back(0); + // 2 last because it is greater than 1 and 0 + std::vector expected{1, 0, 2}; + EXPECT_EQ(TopologicalSort::minSort(graph), expected); +} + +TEST(MinTopologicalSortTest, TwoBeforeOneMinSort) { + Graph graph(3); + graph[2].push_back(1); + // 0 first because it is less than 2 and 1 + std::vector expected{0, 2, 1}; + EXPECT_EQ(TopologicalSort::minSort(graph), expected); +} + +TEST(MinTopologicalSortTest, TwoBeforeZeroMinSort) { + Graph graph(3); + graph[2].push_back(0); + // 1 first because it is less than 2 and zero is not eligible. + std::vector expected{1, 2, 0}; + EXPECT_EQ(TopologicalSort::minSort(graph), expected); +} -- cgit v1.2.3