diff options
Diffstat (limited to 'libcxx/test/std')
5 files changed, 550 insertions, 6 deletions
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp new file mode 100644 index 000000000000..5f412eced4a3 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp @@ -0,0 +1,272 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// <algorithm> + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less, +// class Proj = identity> +// requires sortable<I, Comp, Proj> +// constexpr ranges::next_permutation_result<I> +// ranges::next_permutation(I first, S last, Comp comp = {}, Proj proj = {}); +// template<bidirectional_range R, class Comp = ranges::less, +// class Proj = identity> +// requires sortable<iterator_t<R>, Comp, Proj> +// constexpr ranges::next_permutation_result<borrowed_iterator_t<R>> +// ranges::next_permutation(R&& r, Comp comp = {}, Proj proj = {}); + +#include <algorithm> +#include <array> +#include <cassert> +#include <cstddef> +#include <ranges> + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template <class Iter, class Sent = sentinel_wrapper<Iter>> +concept HasNextPermutationIt = requires(Iter first, Sent last) { std::ranges::next_permutation(first, last); }; + +static_assert(HasNextPermutationIt<int*>); +static_assert(!HasNextPermutationIt<BidirectionalIteratorNotDerivedFrom>); +static_assert(!HasNextPermutationIt<BidirectionalIteratorNotDecrementable>); +static_assert(!HasNextPermutationIt<int*, SentinelForNotSemiregular>); +static_assert(!HasNextPermutationIt<int*, SentinelForNotWeaklyEqualityComparableWith>); +static_assert(!HasNextPermutationIt<const int*>); // not sortable + +template <class Range> +concept HasNextPermutationR = requires(Range range) { std::ranges::next_permutation(range); }; + +static_assert(HasNextPermutationR<UncheckedRange<int*>>); +static_assert(!HasNextPermutationR<BidirectionalRangeNotDerivedFrom>); +static_assert(!HasNextPermutationR<BidirectionalRangeNotDecrementable>); +static_assert(!HasNextPermutationR<BidirectionalRangeNotSentinelSemiregular>); +static_assert(!HasNextPermutationR<BidirectionalRangeNotSentinelWeaklyEqualityComparableWith>); +static_assert(!HasNextPermutationR<UncheckedRange<const int*>>); // not sortable + +constexpr size_t factorial(size_t i) { + std::array memoized = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; + return memoized[i]; +} + +template <class Iter, class Range, class Func> +constexpr bool run_next_permutation(Func call_next_permutation, Range permuted, Range previous) { + using Result = std::ranges::next_permutation_result<Iter>; + + std::same_as<Result> decltype(auto) ret = call_next_permutation(permuted); + assert(ret.in == permuted.end()); + bool next_found = ret.found; + + if (std::ranges::distance(permuted) > 1) { + if (next_found) { + assert(std::ranges::lexicographical_compare(previous, permuted)); + } else { + assert(std::ranges::lexicographical_compare(permuted, previous)); + assert(std::ranges::is_sorted(permuted)); + } + } + + return next_found; +} + +template <class Iter, class Sent, class Func> +constexpr void test_next_permutations(Func call_next_permutation) { + std::array input = {1, 2, 3, 4}; + auto current_permutation = input; + auto previous_permutation = current_permutation; + + // For all subarrays of `input` from `[0, 0]` to `[0, N - 1]`, call `next_permutation` until no next permutation + // exists. + // The number of permutations must equal `N!`. `run_next_permutation` checks that each next permutation is + // lexicographically greater than the previous. If these two conditions hold (the number of permutations is `N!`, and + // each permutation is lexicographically greater than the previous one), it follows that the + // `ranges::next_permutation` algorithm works correctly. + for (size_t i = 0; i <= current_permutation.size(); ++i) { + size_t count = 0; + bool next_found = true; + + while (next_found) { + ++count; + previous_permutation = current_permutation; + + auto current_subrange = std::ranges::subrange( + Iter(current_permutation.data()), Sent(Iter(current_permutation.data() + i))); + auto previous_subrange = std::ranges::subrange( + Iter(previous_permutation.data()), Sent(Iter(previous_permutation.data() + i))); + + next_found = run_next_permutation<Iter>(call_next_permutation, current_subrange, previous_subrange); + } + + assert(count == factorial(i)); + } +} + +template <class Iter, class Sent> +constexpr void test_all_permutations() { + test_next_permutations<Iter, Sent>([](auto&& range) { + return std::ranges::next_permutation(range.begin(), range.end()); + }); + + test_next_permutations<Iter, Sent>([](auto&& range) { + return std::ranges::next_permutation(range); + }); +} + +template <class Iter, class Sent, int N> +constexpr void test_one(const std::array<int, N> input, bool expected_found, std::array<int, N> expected) { + using Result = std::ranges::next_permutation_result<Iter>; + + { // (iterator, sentinel) overload. + auto in = input; + auto begin = Iter(in.data()); + auto end = Sent(Iter(in.data() + in.size())); + + std::same_as<Result> decltype(auto) result = std::ranges::next_permutation(begin, end); + assert(result.found == expected_found); + assert(result.in == end); + assert(in == expected); + } + + { // (range) overload. + auto in = input; + auto begin = Iter(in.data()); + auto end = Sent(Iter(in.data() + in.size())); + auto range = std::ranges::subrange(begin, end); + + std::same_as<Result> decltype(auto) result = std::ranges::next_permutation(range); + assert(result.found == expected_found); + assert(result.in == end); + assert(in == expected); + } +} + +template <class Iter, class Sent> +constexpr void test_iter_sent() { + test_all_permutations<Iter, Sent>(); + + // Empty range. + test_one<Iter, Sent, 0>({}, false, {}); + // 1-element range. + test_one<Iter, Sent, 1>({1}, false, {1}); + // 2-element range. + test_one<Iter, Sent, 2>({1, 2}, true, {2, 1}); + test_one<Iter, Sent, 2>({2, 1}, false, {1, 2}); + // Longer sequence. + test_one<Iter, Sent, 8>({1, 2, 3, 4, 5, 6, 7, 8}, true, {1, 2, 3, 4, 5, 6, 8, 7}); + // Longer sequence, permutations exhausted. + test_one<Iter, Sent, 8>({8, 7, 6, 5, 4, 3, 2, 1}, false, {1, 2, 3, 4, 5, 6, 7, 8}); +} + +template <class Iter> +constexpr void test_iter() { + test_iter_sent<Iter, Iter>(); + test_iter_sent<Iter, sentinel_wrapper<Iter>>(); + test_iter_sent<Iter, sized_sentinel<Iter>>(); +} + +constexpr void test_iterators() { + test_iter<bidirectional_iterator<int*>>(); + test_iter<random_access_iterator<int*>>(); + test_iter<contiguous_iterator<int*>>(); + test_iter<int*>(); +} + +constexpr bool test() { + test_iterators(); + + { // A custom predicate works. + struct A { + int i; + constexpr bool comp(const A& rhs) const { return i > rhs.i; } + constexpr bool operator==(const A&) const = default; + }; + const std::array input = {A{1}, A{2}, A{3}, A{4}, A{5}}; + std::array expected = {A{5}, A{4}, A{3}, A{2}, A{1}}; + + { // (iterator, sentinel) overload. + auto in = input; + auto result = std::ranges::next_permutation(in.begin(), in.end(), &A::comp); + + assert(result.found == false); + assert(result.in == in.end()); + assert(in == expected); + } + + { // (range) overload. + auto in = input; + auto result = std::ranges::next_permutation(in, &A::comp); + + assert(result.found == false); + assert(result.in == in.end()); + assert(in == expected); + } + } + + { // A custom projection works. + struct A { + int i; + constexpr A negate() const { return A{i * -1}; } + constexpr auto operator<=>(const A&) const = default; + }; + const std::array input = {A{1}, A{2}, A{3}, A{4}, A{5}}; + std::array expected = {A{5}, A{4}, A{3}, A{2}, A{1}}; + + { // (iterator, sentinel) overload. + auto in = input; + auto result = std::ranges::next_permutation(in.begin(), in.end(), {}, &A::negate); + + assert(result.found == false); + assert(result.in == in.end()); + assert(in == expected); + } + + { // (range) overload. + auto in = input; + auto result = std::ranges::next_permutation(in, {}, &A::negate); + + assert(result.found == false); + assert(result.in == in.end()); + assert(in == expected); + } + } + + { // Complexity: At most `(last - first) / 2` swaps. + const std::array input = {1, 2, 3, 4, 5, 6}; + + { // (iterator, sentinel) overload. + auto in = input; + int swaps_count = 0; + auto begin = adl::Iterator::TrackSwaps(in.data(), swaps_count); + auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps_count); + + std::ranges::next_permutation(begin, end); + assert(swaps_count <= (base(end) - base(begin) + 1) / 2); + } + + { // (range) overload. + auto in = input; + int swaps_count = 0; + auto begin = adl::Iterator::TrackSwaps(in.data(), swaps_count); + auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps_count); + + std::ranges::next_permutation(std::ranges::subrange(begin, end)); + assert(swaps_count <= (base(end) - base(begin) + 1) / 2); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp new file mode 100644 index 000000000000..17db20279a3b --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp @@ -0,0 +1,272 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// <algorithm> + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less, +// class Proj = identity> +// requires sortable<I, Comp, Proj> +// constexpr ranges::prev_permutation_result<I> +// ranges::prev_permutation(I first, S last, Comp comp = {}, Proj proj = {}); +// template<bidirectional_range R, class Comp = ranges::less, +// class Proj = identity> +// requires sortable<iterator_t<R>, Comp, Proj> +// constexpr ranges::prev_permutation_result<borrowed_iterator_t<R>> +// ranges::prev_permutation(R&& r, Comp comp = {}, Proj proj = {}); + +#include <algorithm> +#include <array> +#include <cassert> +#include <cstddef> +#include <ranges> + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template <class Iter, class Sent = sentinel_wrapper<Iter>> +concept HasPrevPermutationIt = requires(Iter first, Sent last) { std::ranges::prev_permutation(first, last); }; + +static_assert(HasPrevPermutationIt<int*>); +static_assert(!HasPrevPermutationIt<BidirectionalIteratorNotDerivedFrom>); +static_assert(!HasPrevPermutationIt<BidirectionalIteratorNotDecrementable>); +static_assert(!HasPrevPermutationIt<int*, SentinelForNotSemiregular>); +static_assert(!HasPrevPermutationIt<int*, SentinelForNotWeaklyEqualityComparableWith>); +static_assert(!HasPrevPermutationIt<const int*>); // not sortable + +template <class Range> +concept HasPrevPermutationR = requires(Range range) { std::ranges::prev_permutation(range); }; + +static_assert(HasPrevPermutationR<UncheckedRange<int*>>); +static_assert(!HasPrevPermutationR<BidirectionalRangeNotDerivedFrom>); +static_assert(!HasPrevPermutationR<BidirectionalRangeNotDecrementable>); +static_assert(!HasPrevPermutationR<BidirectionalRangeNotSentinelSemiregular>); +static_assert(!HasPrevPermutationR<BidirectionalRangeNotSentinelWeaklyEqualityComparableWith>); +static_assert(!HasPrevPermutationR<UncheckedRange<const int*>>); // not sortable + +constexpr size_t factorial(size_t i) { + std::array memoized = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; + return memoized[i]; +} + +template <class Iter, class Range, class Func> +constexpr bool run_prev_permutation(Func call_prev_permutation, Range permuted, Range previous) { + using Result = std::ranges::prev_permutation_result<Iter>; + + std::same_as<Result> decltype(auto) ret = call_prev_permutation(permuted); + assert(ret.in == permuted.end()); + bool next_found = ret.found; + + if (std::ranges::distance(permuted) > 1) { + if (next_found) { + assert(std::ranges::lexicographical_compare(permuted, previous)); + } else { + assert(std::ranges::lexicographical_compare(previous, permuted)); + assert(std::ranges::is_sorted(permuted, std::ranges::greater{})); + } + } + + return next_found; +} + +template <class Iter, class Sent, class Func> +constexpr void test_prev_permutations(Func call_prev_permutation) { + std::array input = {4, 3, 2, 1}; + auto current_permutation = input; + auto previous_permutation = current_permutation; + + // For all subarrays of `input` from `[0, 0]` to `[0, N - 1]`, call `prev_permutation` until no previous permutation + // exists. + // The number of permutations must equal `N!`. `run_prev_permutation` checks that each previous permutation is + // lexicographically less than the previous. If these two conditions hold (the number of permutations is `N!`, and + // each permutation is lexicographically less than the previous one), it follows that the `ranges::prev_permutation` + // algorithm works correctly. + for (size_t i = 0; i <= current_permutation.size(); ++i) { + size_t count = 0; + bool next_found = true; + + while (next_found) { + ++count; + previous_permutation = current_permutation; + + auto current_subrange = std::ranges::subrange( + Iter(current_permutation.data()), Sent(Iter(current_permutation.data() + i))); + auto previous_subrange = std::ranges::subrange( + Iter(previous_permutation.data()), Sent(Iter(previous_permutation.data() + i))); + + next_found = run_prev_permutation<Iter>(call_prev_permutation, current_subrange, previous_subrange); + } + + assert(count == factorial(i)); + } +} + +template <class Iter, class Sent> +constexpr void test_all_permutations() { + test_prev_permutations<Iter, Sent>([](auto&& range) { + return std::ranges::prev_permutation(range.begin(), range.end()); + }); + + test_prev_permutations<Iter, Sent>([](auto&& range) { + return std::ranges::prev_permutation(range); + }); +} + +template <class Iter, class Sent, int N> +constexpr void test_one(const std::array<int, N> input, bool expected_found, std::array<int, N> expected) { + using Result = std::ranges::prev_permutation_result<Iter>; + + { // (iterator, sentinel) overload. + auto in = input; + auto begin = Iter(in.data()); + auto end = Sent(Iter(in.data() + in.size())); + + std::same_as<Result> decltype(auto) result = std::ranges::prev_permutation(begin, end); + assert(result.found == expected_found); + assert(result.in == end); + assert(in == expected); + } + + { // (range) overload. + auto in = input; + auto begin = Iter(in.data()); + auto end = Sent(Iter(in.data() + in.size())); + auto range = std::ranges::subrange(begin, end); + + std::same_as<Result> decltype(auto) result = std::ranges::prev_permutation(range); + assert(result.found == expected_found); + assert(result.in == end); + assert(in == expected); + } +} + +template <class Iter, class Sent> +constexpr void test_iter_sent() { + test_all_permutations<Iter, Sent>(); + + // Empty range. + test_one<Iter, Sent, 0>({}, false, {}); + // 1-element range. + test_one<Iter, Sent, 1>({1}, false, {1}); + // 2-element range. + test_one<Iter, Sent, 2>({1, 2}, false, {2, 1}); + test_one<Iter, Sent, 2>({2, 1}, true, {1, 2}); + // Longer sequence. + test_one<Iter, Sent, 8>({8, 7, 6, 5, 4, 3, 2, 1}, true, {8, 7, 6, 5, 4, 3, 1, 2}); + // Longer sequence, permutations exhausted. + test_one<Iter, Sent, 8>({1, 2, 3, 4, 5, 6, 7, 8}, false, {8, 7, 6, 5, 4, 3, 2, 1}); +} + +template <class Iter> +constexpr void test_iter() { + test_iter_sent<Iter, Iter>(); + test_iter_sent<Iter, sentinel_wrapper<Iter>>(); + test_iter_sent<Iter, sized_sentinel<Iter>>(); +} + +constexpr void test_iterators() { + test_iter<bidirectional_iterator<int*>>(); + test_iter<random_access_iterator<int*>>(); + test_iter<contiguous_iterator<int*>>(); + test_iter<int*>(); +} + +constexpr bool test() { + test_iterators(); + + { // A custom predicate works. + struct A { + int i; + constexpr bool comp(const A& rhs) const { return i > rhs.i; } + constexpr bool operator==(const A&) const = default; + }; + const std::array input = {A{5}, A{4}, A{3}, A{2}, A{1}}; + std::array expected = {A{1}, A{2}, A{3}, A{4}, A{5}}; + + { // (iterator, sentinel) overload. + auto in = input; + auto result = std::ranges::prev_permutation(in.begin(), in.end(), &A::comp); + + assert(result.found == false); + assert(result.in == in.end()); + assert(in == expected); + } + + { // (range) overload. + auto in = input; + auto result = std::ranges::prev_permutation(in, &A::comp); + + assert(result.found == false); + assert(result.in == in.end()); + assert(in == expected); + } + } + + { // A custom projection works. + struct A { + int i; + constexpr A negate() const { return A{i * -1}; } + constexpr auto operator<=>(const A&) const = default; + }; + const std::array input = {A{5}, A{4}, A{3}, A{2}, A{1}}; + std::array expected = {A{1}, A{2}, A{3}, A{4}, A{5}}; + + { // (iterator, sentinel) overload. + auto in = input; + auto result = std::ranges::prev_permutation(in.begin(), in.end(), {}, &A::negate); + + assert(result.found == false); + assert(result.in == in.end()); + assert(in == expected); + } + + { // (range) overload. + auto in = input; + auto result = std::ranges::prev_permutation(in, {}, &A::negate); + + assert(result.found == false); + assert(result.in == in.end()); + assert(in == expected); + } + } + + { // Complexity: At most `(last - first) / 2` swaps. + const std::array input = {6, 5, 4, 3, 2, 1}; + + { // (iterator, sentinel) overload. + auto in = input; + int swaps_count = 0; + auto begin = adl::Iterator::TrackSwaps(in.data(), swaps_count); + auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps_count); + + std::ranges::prev_permutation(begin, end); + assert(swaps_count <= (base(end) - base(begin) + 1) / 2); + } + + { // (range) overload. + auto in = input; + int swaps_count = 0; + auto begin = adl::Iterator::TrackSwaps(in.data(), swaps_count); + auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps_count); + + std::ranges::prev_permutation(std::ranges::subrange(begin, end)); + assert(swaps_count <= (base(end) - base(begin) + 1) / 2); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp index 5c8a1031997a..953fc72f18de 100644 --- a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp @@ -57,7 +57,7 @@ static_assert(std::is_same_v<in_out_out_result<int, long, char>, partition_copy_ static_assert(std::is_same_v<min_max_result<int>, minmax_result<int>>); static_assert(std::is_same_v<min_max_result<int>, minmax_element_result<int>>); -// static_assert(std::is_same_v<in_found_result<int>, next_permutation_result<int>>); -// static_assert(std::is_same_v<in_found_result<int>, prev_permutation_result<int>>); +static_assert(std::is_same_v<in_found_result<int>, next_permutation_result<int>>); +static_assert(std::is_same_v<in_found_result<int>, prev_permutation_result<int>>); // static_assert(std::is_same_v<out_value_result<int>, iota_result<int>>); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp index 9ad1273880e1..222b45fd2e27 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp @@ -139,8 +139,8 @@ constexpr bool test_all() { test(std::ranges::push_heap, in, binary_pred); test(std::ranges::pop_heap, in, binary_pred); test(std::ranges::sort_heap, in, binary_pred); - //test(std::ranges::prev_permutation, in, binary_pred); - //test(std::ranges::next_permutation, in, binary_pred); + test(std::ranges::prev_permutation, in, binary_pred); + test(std::ranges::next_permutation, in, binary_pred); return true; } diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp index 013b6d7984dd..a82002659a29 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp @@ -168,8 +168,8 @@ constexpr bool test_all() { test(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val); test(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val); test(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val); - //test(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val); - //test(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val); return true; } |