| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // -*- mode: C++ -*- |
| // |
| // Copyright 2021-2024 Google LLC |
| // |
| // Licensed under the Apache License v2.0 with LLVM Exceptions (the |
| // "License"); you may not use this file except in compliance with the |
| // License. You may obtain a copy of the License at |
| // |
| // https://llvm.org/LICENSE.txt |
| // |
| // 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. |
| // |
| // Author: Giuliano Procida |
| |
| #include "order.h" |
| |
| #include <cstddef> |
| #include <optional> |
| #include <random> |
| #include <sstream> |
| #include <string> |
| #include <tuple> |
| #include <utility> |
| #include <vector> |
| |
| #include <catch2/catch.hpp> |
| |
| namespace Test { |
| |
| // Safe for small k! |
| size_t Factorial(size_t k) { |
| size_t count = 1; |
| for (size_t i = 1; i <= k; ++i) { |
| count *= i; |
| } |
| return count; |
| } |
| |
| TEST_CASE("hand-curated permutation") { |
| std::vector<std::string> data = {"emily", "george", "rose", "ted"}; |
| std::vector<size_t> permutation = {2, 1, 3, 0}; |
| const std::vector<std::string> expected = {"rose", "george", "ted", "emily"}; |
| const std::vector<size_t> identity = {0, 1, 2, 3}; |
| stg::Permute(data, permutation); |
| CHECK(data == expected); |
| CHECK(permutation == identity); |
| } |
| |
| template <typename G> |
| std::vector<size_t> MakePermutation(size_t k, G& gen) { |
| std::vector<size_t> result(k); |
| for (size_t i = 0; i < k; ++i) { |
| result[i] = i; |
| } |
| for (size_t i = 0; i < k; ++i) { |
| // pick one of [i, k) |
| std::uniform_int_distribution<size_t> toss(i, k - 1); |
| auto pick = toss(gen); |
| using std::swap; |
| swap(result[i], result[pick]); |
| } |
| return result; |
| } |
| |
| TEST_CASE("randomly-generated permutations") { |
| std::ranlux48 gen; |
| auto seed = gen(); |
| // NOTES: |
| // Permutations of size 6 are plenty big enough to shake out bugs. |
| /// There are k! permutations of size k. Testing costs are O(k). |
| for (size_t k = 0; k < 7; ++k) { |
| const auto count = Factorial(k); |
| INFO("testing with " << count << " permutations of size " << k); |
| std::vector<size_t> identity(k); |
| for (size_t i = 0; i < k; ++i) { |
| identity[i] = i; |
| } |
| for (size_t n = 0; n < count; ++n, ++seed) { |
| gen.seed(seed); |
| auto permutation = MakePermutation(k, gen); |
| std::ostringstream os; |
| os << "permutation of " << k << " numbers generated using seed " << seed; |
| GIVEN(os.str()) { |
| // NOTE: We could test with something other than [0, k) as the data, but |
| // let's just say "parametric polymorphism" and move on. |
| auto permutation_copy = permutation; |
| auto identity_copy = identity; |
| stg::Permute(identity_copy, permutation_copy); |
| for (size_t i = 0; i < k; ++i) { |
| // permutation_copy should be the identity |
| CHECK(permutation_copy[i] == i); |
| // identity_copy should now be the same as permutation |
| CHECK(identity_copy[i] == permutation[i]); |
| } |
| } |
| } |
| } |
| } |
| |
| TEST_CASE("randomly-generating ordering sequences, fully-matching") { |
| std::ranlux48 gen; |
| auto seed = gen(); |
| // NOTES: |
| // Permutations of size 6 are plenty big enough to shake out bugs. |
| /// There are k! permutations of size k. Testing costs are O(k^2). |
| for (size_t k = 0; k < 7; ++k) { |
| const auto count = Factorial(k); |
| INFO("testing with " << count << " random orderings of size " << k); |
| for (size_t n = 0; n < count; ++n, ++seed) { |
| gen.seed(seed); |
| const auto order1 = MakePermutation(k, gen); |
| const auto order2 = MakePermutation(k, gen); |
| std::ostringstream os; |
| os << "orderings of " << k << " numbers generated using seed " << seed; |
| GIVEN(os.str()) { |
| const auto combined = stg::CombineOrders(order1, order2, k); |
| // combined should be identical to order2 |
| CHECK(combined == order2); |
| } |
| } |
| } |
| } |
| |
| TEST_CASE("randomly-generating ordering sequences, disjoint") { |
| std::ranlux48 gen; |
| auto seed = gen(); |
| // NOTES: |
| // Orderings of size 4 are plenty big enough to shake out bugs. |
| /// There are k! permutations of size k. Testing costs are O(k^2). |
| for (size_t k = 0; k < 5; ++k) { |
| const auto count = Factorial(k); |
| INFO("testing with " << count << " random orderings of size " << k); |
| for (size_t n = 0; n < count; ++n, ++seed) { |
| gen.seed(seed); |
| const auto order1 = MakePermutation(k, gen); |
| auto order2 = MakePermutation(k, gen); |
| for (size_t i = 0; i < k; ++i) { |
| order2[i] += k; |
| } |
| std::ostringstream os; |
| os << "orderings of " << k << " numbers generated using seed " << seed; |
| GIVEN(os.str()) { |
| const auto combined = stg::CombineOrders(order1, order2, 2 * k); |
| for (size_t i = 0; i < k; ++i) { |
| // order1 should appear as the first part |
| CHECK(combined[i] == order1[i]); |
| // order2 should appear as the second part |
| CHECK(combined[i + k] == order2[i]); |
| } |
| } |
| } |
| } |
| } |
| |
| TEST_CASE("randomly-generating ordering sequences, single overlap") { |
| std::ranlux48 gen; |
| auto seed = gen(); |
| // NOTES: |
| // Orderings of size 4 are plenty big enough to shake out bugs. |
| /// There are k! permutations of size k. Testing costs are O(k^2). |
| for (size_t k = 1; k < 5; ++k) { |
| const auto count = Factorial(k); |
| INFO("testing with " << count << " random orderings of size " << k); |
| for (size_t n = 0; n < count; ++n, ++seed) { |
| gen.seed(seed); |
| const auto order1 = MakePermutation(k, gen); |
| auto order2 = MakePermutation(k, gen); |
| for (size_t i = 0; i < k; ++i) { |
| order2[i] += k - 1; |
| } |
| const auto pivot = k - 1; |
| std::ostringstream os; |
| os << "orderings of " << k << " numbers generated using seed " << seed; |
| GIVEN(os.str()) { |
| const auto combined = stg::CombineOrders(order1, order2, 2 * k - 1); |
| CHECK(combined.size() == 2 * k - 1); |
| // order1 pre, order2 pre, pivot, order1 post, order2 post |
| size_t ix = 0; |
| size_t ix1 = 0; |
| size_t ix2 = 0; |
| while (order1[ix1] != pivot) { |
| CHECK(combined[ix++] == order1[ix1++]); |
| } |
| while (order2[ix2] != pivot) { |
| CHECK(combined[ix++] == order2[ix2++]); |
| } |
| ++ix1; |
| ++ix2; |
| CHECK(combined[ix++] == pivot); |
| while (ix1 < k) { |
| CHECK(combined[ix++] == order1[ix1++]); |
| } |
| while (ix2 < k) { |
| CHECK(combined[ix++] == order2[ix2++]); |
| } |
| } |
| } |
| } |
| } |
| |
| TEST_CASE("hand-curated ordering sequences") { |
| using Sequence = std::vector<std::string>; |
| // NOTES: |
| // The output sequence MUST include the second sequence as a subsequence. |
| // The first sequence's ordering is respected as far as possible. |
| std::vector<std::tuple<Sequence, Sequence, Sequence>> cases = { |
| {{"rose", "george", "emily"}, {"george", "ted", "emily"}, |
| {"rose", "george", "ted", "emily"}}, |
| {{}, {}, {}}, |
| {{"a"}, {}, {"a"}}, |
| {{}, {"a"}, {"a"}}, |
| {{"a", "z"}, {}, {"a", "z"}}, |
| {{}, {"a", "z"}, {"a", "z"}}, |
| {{"a", "b", "c"}, {"c", "d"}, {"a", "b", "c", "d"}}, |
| {{"a", "b", "d"}, {"b", "c", "d"}, {"a", "b", "c", "d"}}, |
| {{"a", "c", "d"}, {"a", "b", "c"}, {"a", "b", "c", "d"}}, |
| {{"b", "c", "d"}, {"a", "b"}, {"a", "b", "c", "d"}}, |
| {{"z", "a", "q"}, {"a", "z"}, {"a", "z", "q"}}, |
| }; |
| for (const auto& [order1, order2, expected] : cases) { |
| const auto combined = stg::CombineOrders(order1, order2, expected.size()); |
| CHECK(combined == expected); |
| } |
| } |
| |
| TEST_CASE("hand-curated reorderings with input order randomisation") { |
| using Constraint = std::pair<std::optional<size_t>, std::optional<size_t>>; |
| using Constraints = std::vector<Constraint>; |
| // NOTES: |
| // item removed at position x: {x}, {} |
| // item added at position y: {}, {y} |
| // item modified at positions x and y: {x}, {y} |
| // input item order should be irrelevant to output order |
| std::vector<std::pair<Constraints, Constraints>> cases = { |
| { |
| { |
| {{2}, {2}}, // emily |
| {{1}, {0}}, // george |
| {{0}, {}}, // rose |
| {{}, {1}}, // ted |
| }, |
| { |
| {{0}, {}}, // rose |
| {{1}, {0}}, // george |
| {{}, {1}}, // ted |
| {{2}, {2}}, // emily |
| }, |
| }, |
| {{}, {}}, |
| {{{{0}, {0}}}, {{{0}, {0}}}}, |
| {{{{0}, {}}}, {{{0}, {}}}}, |
| {{{{}, {0}}}, {{{}, {0}}}}, |
| {{{{}, {2}}, {{}, {1}}, {{}, {0}}}, |
| {{{}, {0}}, {{}, {1}}, {{}, {2}}}}, |
| {{{{2}, {}}, {{1}, {}}, {{0}, {}}}, |
| {{{0}, {}}, {{1}, {}}, {{2}, {}}}}, |
| // int b; int c; -> int b; int a; int c |
| {{{{}, {1}}, {{0}, {0}}, {{1}, {2}}}, |
| {{{0}, {0}}, {{}, {1}}, {{1}, {2}}}}, |
| }; |
| std::ranlux48 gen; |
| auto seed = gen(); |
| for (const auto& [given, expected] : cases) { |
| const auto k = given.size(); |
| const auto count = Factorial(k); |
| INFO("testing with " << count << " random input orderings"); |
| for (size_t n = 0; n < count; ++n, ++seed) { |
| gen.seed(seed); |
| std::ostringstream os; |
| os << "permutation of " << k << " items generated using seed " << seed; |
| GIVEN(os.str()) { |
| auto permutation = MakePermutation(k, gen); |
| auto copy = given; |
| stg::Permute(copy, permutation); |
| stg::Reorder(copy); |
| CHECK(copy == expected); |
| } |
| } |
| } |
| } |
| |
| } // namespace Test |