diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -111,6 +111,7 @@ __algorithm/ranges_mismatch.h __algorithm/ranges_move.h __algorithm/ranges_move_backward.h + __algorithm/ranges_next_permutation.h __algorithm/ranges_none_of.h __algorithm/ranges_nth_element.h __algorithm/ranges_partial_sort_copy.h @@ -119,6 +120,7 @@ __algorithm/ranges_partition_point.h __algorithm/ranges_pop_heap.h __algorithm/ranges_push_heap.h + __algorithm/ranges_prev_permutation.h __algorithm/ranges_remove.h __algorithm/ranges_remove_copy.h __algorithm/ranges_remove_copy_if.h diff --git a/libcxx/include/__algorithm/ranges_next_permutation.h b/libcxx/include/__algorithm/ranges_next_permutation.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_next_permutation.h @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_NEXT_PERMUTATION_H +#define _LIBCPP___ALGORITHM_RANGES_NEXT_PERMUTATION_H + +#include <__algorithm/in_found_result.h> +#include <__algorithm/ranges_prev_permutation.h> +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +namespace ranges { + +template +using next_permutation_result = in_found_result<_InIter>; + +namespace __next_permutation { + +struct __fn { + template _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr next_permutation_result<_Iter> + operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + auto __comp_reverse_args = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); }; + return ranges::__prev_permutation_impl(__first, __last, __comp_reverse_args, __proj); + } + + template + requires sortable, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr next_permutation_result> + operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const { + auto __comp_reverse_args = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); }; + return ranges::__prev_permutation_impl(ranges::begin(__range), ranges::end(__range), __comp_reverse_args, __proj); + } +}; + +} // namespace __next_permutation + +inline namespace __cpo { +constexpr inline auto next_permutation = __next_permutation::__fn{}; +} // namespace __cpo +} // namespace ranges + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_RANGES_NEXT_PERMUTATION_H diff --git a/libcxx/include/__algorithm/ranges_prev_permutation.h b/libcxx/include/__algorithm/ranges_prev_permutation.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_prev_permutation.h @@ -0,0 +1,92 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_PREV_PERMUTATION_H +#define _LIBCPP___ALGORITHM_RANGES_PREV_PERMUTATION_H + +#include <__algorithm/in_found_result.h> +#include <__algorithm/ranges_reverse.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iter_swap.h> +#include <__iterator/next.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +namespace ranges { + +template +using prev_permutation_result = in_found_result<_InIter>; + +template +_LIBCPP_HIDE_FROM_ABI constexpr prev_permutation_result<_Iter> +__prev_permutation_impl(_Iter __first, _Sent __sent, _Comp& __comp, _Proj& __proj) { + auto __last = ranges::next(__first, __sent); + auto __i = __last; + if (__first == __last || __first == --__i) + return {__last, false}; + while (true) { + auto __ip1 = __i; + --__i; + if (std::invoke(__comp, std::invoke(__proj, *__ip1), std::invoke(__proj, *__i))) { + auto __j = __last; + do { + --__j; + } while (!std::invoke(__comp, std::invoke(__proj, *__j), std::invoke(__proj, *__i))); + ranges::iter_swap(__i, __j); + ranges::reverse(__ip1, __last); + return {__last, true}; + } + if (__i == __first) { + ranges::reverse(__first, __last); + return {__last, false}; + } + } +} + +namespace __prev_permutation { + +struct __fn { + template _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr prev_permutation_result<_Iter> + operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return ranges::__prev_permutation_impl(__first, __last, __comp, __proj); + } + + template + requires sortable, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr prev_permutation_result> + operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const { + return ranges::__prev_permutation_impl(ranges::begin(__range), ranges::end(__range), __comp, __proj); + } +}; +} // namespace __prev_permutation + +inline namespace __cpo { +constexpr inline auto prev_permutation = __prev_permutation::__fn{}; +} // namespace __cpo +} // namespace ranges + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_RANGES_PREV_PERMUTATION_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -703,7 +703,7 @@ set_symmetric_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - + template requires mergeable, iterator_t, O, Comp, Proj1, Proj2> @@ -711,7 +711,7 @@ borrowed_iterator_t, O> set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - + template using set_union_result = in_in_out_result; // since C++20 @@ -729,6 +729,31 @@ constexpr set_union_result, borrowed_iterator_t, O> set_union(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + constexpr ranges::prev_permutation_result + ranges::prev_permutation(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 + + template + requires sortable, Comp, Proj> + constexpr ranges::prev_permutation_result> + ranges::prev_permutation(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + + template S, class Comp = ranges::less, + class Proj = identity> + requires sortable + constexpr ranges::next_permutation_result + ranges::next_permutation(I first, S last, Comp comp = {}, Proj proj = {}); // since C++20 + + template + requires sortable, Comp, Proj> + constexpr ranges::next_permutation_result> + ranges::next_permutation(R&& r, Comp comp = {}, Proj proj = {}); // since C++20 + } constexpr bool // constexpr in C++20 @@ -1494,9 +1519,11 @@ #include <__algorithm/ranges_mismatch.h> #include <__algorithm/ranges_move.h> #include <__algorithm/ranges_move_backward.h> +#include <__algorithm/ranges_next_permutation.h> #include <__algorithm/ranges_none_of.h> #include <__algorithm/ranges_nth_element.h> #include <__algorithm/ranges_pop_heap.h> +#include <__algorithm/ranges_prev_permutation.h> #include <__algorithm/ranges_push_heap.h> #include <__algorithm/ranges_remove.h> #include <__algorithm/ranges_remove_if.h> diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -165,8 +165,8 @@ (void)std::ranges::minmax_element(a, Less(&copies)); assert(copies == 0); (void)std::ranges::mismatch(first, last, first2, last2, Equal(&copies)); assert(copies == 0); (void)std::ranges::mismatch(a, b, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::next_permutation(first, last, Less(&copies)); assert(copies == 0); - //(void)std::ranges::next_permutation(a, Less(&copies)); assert(copies == 0); + (void)std::ranges::next_permutation(first, last, Less(&copies)); assert(copies == 0); + (void)std::ranges::next_permutation(a, Less(&copies)); assert(copies == 0); (void)std::ranges::none_of(first, last, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::none_of(a, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::nth_element(first, mid, last, Less(&copies)); assert(copies == 0); @@ -183,8 +183,8 @@ //(void)std::ranges::partition_point(a, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0); (void)std::ranges::pop_heap(a, Less(&copies)); assert(copies == 0); - //(void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0); - //(void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0); + (void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0); + (void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0); (void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0); (void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0); //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -148,8 +148,8 @@ (void)std::ranges::minmax_element(a, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::mismatch(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); (void)std::ranges::mismatch(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::next_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::next_permutation(a, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::next_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::next_permutation(a, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::none_of(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::none_of(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::nth_element(first, mid, last, Less(), Proj(&copies)); assert(copies == 0); @@ -166,8 +166,8 @@ //(void)std::ranges::partition_point(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::pop_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::pop_heap(a, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::push_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::push_heap(a, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::remove_copy(first, last, first2, value, Proj(&copies)); assert(copies == 0); 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 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.next_permutation.pass.cpp @@ -0,0 +1,140 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S, class Comp = ranges::less, +// class Proj = identity> +// requires sortable +// constexpr ranges::next_permutation_result +// ranges::next_permutation(I first, S last, Comp comp = {}, Proj proj = {}); +// template +// requires sortable, Comp, Proj> +// constexpr ranges::next_permutation_result> +// ranges::next_permutation(R&& r, Comp comp = {}, Proj proj = {}); + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template > +concept HasNextPermutationIt = requires(Iter first, Sent last) { std::ranges::next_permutation(first, last); }; + +static_assert(HasNextPermutationIt); +static_assert(!HasNextPermutationIt); +static_assert(!HasNextPermutationIt); +static_assert(!HasNextPermutationIt); +static_assert(!HasNextPermutationIt); +static_assert(!HasNextPermutationIt); // not sortable + +template +concept HasNextPermutationR = requires(Range range) { std::ranges::next_permutation(range); }; + +static_assert(HasNextPermutationR>); +static_assert(!HasNextPermutationR); +static_assert(!HasNextPermutationR); +static_assert(!HasNextPermutationR); +static_assert(!HasNextPermutationR); +static_assert(!HasNextPermutationR>); // not sortable + +constexpr size_t factorial(size_t i) { + size_t result = 1; + for (; i != 0; --i) + result *= i; + return result; +} + +template +void test_permutations() { + auto test_prev_permutations = [](auto call_prev_permutation) { + auto input = std::array{1, 2, 3, 4, 5, 6}; + std::array last_permutation; + for (size_t i = 0; i <= input.size(); ++i) { + size_t count = 0; + + bool found_permutation = true; + while (found_permutation) { + last_permutation = input; + std::same_as> decltype(auto) ret = + call_prev_permutation(Iter(input.data()), Sent(Iter(input.data() + i))); + found_permutation = ret.found; + assert(base(ret.in) == input.data() + i); + if (i > 1) { + auto input_subrange = input | std::views::take(i); + auto last_permutation_subrange = last_permutation | std::views::take(i); + if (found_permutation) + assert(std::ranges::lexicographical_compare(last_permutation_subrange, input_subrange)); + else + assert(std::ranges::lexicographical_compare(input_subrange, last_permutation_subrange)); + } + ++count; + } + assert(count == factorial(i)); + } + return true; + }; + + auto iterator_overload = [](auto&& first, auto&& last) { return std::ranges::next_permutation(first, last); }; + auto range_overload = [](auto&& first, auto&& last) { + auto range = std::ranges::subrange(first, last); + return std::ranges::next_permutation(range); + }; + + if constexpr (std::is_same_v) { + auto iterator_overload_counted = + [](auto first, auto last) -> std::ranges::prev_permutation_result { + int count = 0; + auto ret = std::ranges::next_permutation(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count)); + assert(count <= (base(last) - base(first) + 1) / 2); + return ret; + }; + + auto range_overload_counted = [](auto first, auto last) -> std::ranges::prev_permutation_result { + int count = 0; + auto range = std::ranges::subrange(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count)); + auto ret = std::ranges::next_permutation(range); + assert(count <= (base(last) - base(first) + 1) / 2); + return ret; + }; + + test_prev_permutations(iterator_overload_counted); + static_assert(test_prev_permutations(iterator_overload_counted)); + test_prev_permutations(range_overload_counted); + static_assert(test_prev_permutations(range_overload_counted)); + } + + test_prev_permutations(iterator_overload); + static_assert(test_prev_permutations(iterator_overload)); + test_prev_permutations(range_overload); + static_assert(test_prev_permutations(range_overload)); +} + +template +void test_sentinels() { + test_permutations(); + test_permutations>(); + test_permutations>(); +} + +void test() { + test_sentinels>(); + test_sentinels>(); + test_sentinels>(); + test_sentinels(); +} + +int main(int, char**) { test(); } 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 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.permutation.generators/ranges.prev_permutation.pass.cpp @@ -0,0 +1,140 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S, class Comp = ranges::less, +// class Proj = identity> +// requires sortable +// constexpr ranges::prev_permutation_result +// ranges::prev_permutation(I first, S last, Comp comp = {}, Proj proj = {}); +// template +// requires sortable, Comp, Proj> +// constexpr ranges::prev_permutation_result> +// ranges::prev_permutation(R&& r, Comp comp = {}, Proj proj = {}); + +#include +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template > +concept HasPrevPermutationIt = requires(Iter first, Sent last) { std::ranges::prev_permutation(first, last); }; + +static_assert(HasPrevPermutationIt); +static_assert(!HasPrevPermutationIt); +static_assert(!HasPrevPermutationIt); +static_assert(!HasPrevPermutationIt); +static_assert(!HasPrevPermutationIt); +static_assert(!HasPrevPermutationIt); // not sortable + +template +concept HasPrevPermutationR = requires(Range range) { std::ranges::prev_permutation(range); }; + +static_assert(HasPrevPermutationR>); +static_assert(!HasPrevPermutationR); +static_assert(!HasPrevPermutationR); +static_assert(!HasPrevPermutationR); +static_assert(!HasPrevPermutationR); +static_assert(!HasPrevPermutationR>); // not sortable + +constexpr size_t factorial(size_t i) { + size_t result = 1; + for (; i != 0; --i) + result *= i; + return result; +} + +template +void test_permutations() { + auto test_prev_permutations = [](auto call_prev_permutation) { + auto input = std::array{6, 5, 4, 3, 2, 1}; + std::array last_permutation; + for (size_t i = 0; i <= input.size(); ++i) { + size_t count = 0; + + bool found_permutation = true; + while (found_permutation) { + last_permutation = input; + std::same_as> decltype(auto) ret = + call_prev_permutation(Iter(input.data()), Sent(Iter(input.data() + i))); + found_permutation = ret.found; + assert(base(ret.in) == input.data() + i); + if (i > 1) { + auto input_subrange = input | std::views::take(i); + auto last_permutation_subrange = last_permutation | std::views::take(i); + if (found_permutation) + assert(std::ranges::lexicographical_compare(input_subrange, last_permutation_subrange)); + else + assert(std::ranges::lexicographical_compare(last_permutation_subrange, input_subrange)); + } + ++count; + } + assert(count == factorial(i)); + } + return true; + }; + + auto iterator_overload = [](auto&& first, auto&& last) { return std::ranges::prev_permutation(first, last); }; + auto range_overload = [](auto&& first, auto&& last) { + auto range = std::ranges::subrange(first, last); + return std::ranges::prev_permutation(range); + }; + + if constexpr (std::is_same_v) { + auto iterator_overload_counted = + [](auto first, auto last) -> std::ranges::prev_permutation_result { + int count = 0; + auto ret = std::ranges::prev_permutation(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count)); + assert(count <= (base(last) - base(first) + 1) / 2); + return ret; + }; + + auto range_overload_counted = [](auto first, auto last) -> std::ranges::prev_permutation_result { + int count = 0; + auto range = std::ranges::subrange(SwapCountingIterator(first, &count), SwapCountingIterator(last, &count)); + auto ret = std::ranges::prev_permutation(range); + assert(count <= (base(last) - base(first) + 1) / 2); + return ret; + }; + + test_prev_permutations(iterator_overload_counted); + static_assert(test_prev_permutations(iterator_overload_counted)); + test_prev_permutations(range_overload_counted); + static_assert(test_prev_permutations(range_overload_counted)); + } + + test_prev_permutations(iterator_overload); + static_assert(test_prev_permutations(iterator_overload)); + test_prev_permutations(range_overload); + static_assert(test_prev_permutations(range_overload)); +} + +template +void test_sentinels() { + test_permutations(); + test_permutations>(); + test_permutations>(); +} + +void test() { + test_sentinels>(); + test_sentinels>(); + test_sentinels>(); + test_sentinels(); +} + +int main(int, char**) { test(); } 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 --- a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp @@ -56,7 +56,7 @@ static_assert(std::is_same_v, minmax_result>); static_assert(std::is_same_v, minmax_element_result>); -// static_assert(std::is_same_v, next_permutation_result>); -// static_assert(std::is_same_v, prev_permutation_result>); +static_assert(std::is_same_v, next_permutation_result>); +static_assert(std::is_same_v, prev_permutation_result>); // static_assert(std::is_same_v, iota_result>); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp @@ -167,6 +167,6 @@ in_pred(std::ranges::push_heap, in, binary_pred); in_pred(std::ranges::pop_heap, in, binary_pred); in_pred(std::ranges::sort_heap, in, binary_pred); - //in_pred(std::ranges::prev_permutation, in, binary_pred); - //in_pred(std::ranges::next_permutation, in, binary_pred); + in_pred(std::ranges::prev_permutation, in, binary_pred); + in_pred(std::ranges::next_permutation, in, binary_pred); } diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp @@ -212,6 +212,6 @@ in_pred(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val); in_pred(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val); in_pred(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val); - //in_pred(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val); - //in_pred(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val); + in_pred(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val); + in_pred(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val); } diff --git a/libcxx/test/support/almost_satisfies_types.h b/libcxx/test/support/almost_satisfies_types.h --- a/libcxx/test/support/almost_satisfies_types.h +++ b/libcxx/test/support/almost_satisfies_types.h @@ -202,6 +202,10 @@ }; using BidirectionalRangeNotDerivedFrom = UncheckedRange; +using BidirectionalRangeNotSentinelSemiregular = + UncheckedRange, SentinelForNotSemiregular>; +using BidirectionalRangeNotSentinelWeaklyEqualityComparableWith = + UncheckedRange, SentinelForNotWeaklyEqualityComparableWith>; static_assert(std::forward_iterator); static_assert(!std::bidirectional_iterator); diff --git a/libcxx/test/support/test_iterators.h b/libcxx/test/support/test_iterators.h --- a/libcxx/test/support/test_iterators.h +++ b/libcxx/test/support/test_iterators.h @@ -726,6 +726,140 @@ difference_type stride_displacement_ = 0; }; +template +consteval auto get_iterator_concept() { + if constexpr (std::contiguous_iterator) { + return std::contiguous_iterator_tag(); + } else if constexpr (std::random_access_iterator) { + return std::random_access_iterator_tag{}; + } else if constexpr (std::bidirectional_iterator) { + return std::bidirectional_iterator_tag{}; + } else if constexpr (std::forward_iterator) { + return std::forward_iterator_tag{}; + } else { + return std::input_iterator_tag{}; + } +} + +template +using iter_concept_t = decltype(get_iterator_concept()); + +template +struct SwapCountingIterator { + using difference_type = std::iter_difference_t; + using value_type = std::iter_value_t; + using iterator_concept = iter_concept_t; + + Iter iter_; + int* counter_; + SwapCountingIterator() = default; + constexpr SwapCountingIterator(const Iter& iter, int* counter) : iter_(iter), counter_(counter) {} + + constexpr friend void iter_swap(SwapCountingIterator& lhs, SwapCountingIterator& rhs) { + std::ranges::iter_swap(lhs.iter_, rhs.iter_); + ++*lhs.counter_; + } + + constexpr SwapCountingIterator& operator++() { + ++iter_; + return *this; + } + + constexpr SwapCountingIterator operator++(int) { + auto tmp = *this; + ++*this; + return tmp; + } + + constexpr SwapCountingIterator& operator--() { + --iter_; + return *this; + } + + constexpr SwapCountingIterator operator--(int) { + auto tmp = *this; + ++*this; + return tmp; + } + + constexpr auto base() { return base(iter_); } + + constexpr decltype(auto) operator*() const { return *iter_; } + + friend bool operator==(const SwapCountingIterator& lhs, const SwapCountingIterator& rhs) = default; + + constexpr operator Iter() { + return iter_; + } + + // to satisfy random_access_iterator + constexpr SwapCountingIterator& operator+=(difference_type n) + requires std::random_access_iterator { + iter_ += n; + return *this; + } + + constexpr SwapCountingIterator& operator-=(difference_type n) + requires std::random_access_iterator { + iter_ -= n; + return *this; + } + + constexpr decltype(auto) operator[](difference_type n) const + requires std::random_access_iterator { + return iter_[n]; + } + + friend constexpr bool operator<(const SwapCountingIterator& x, const SwapCountingIterator& y) + requires std::random_access_iterator { + return x.iter_ < y.iter_; + } + + friend constexpr bool operator>(const SwapCountingIterator& x, const SwapCountingIterator& y) + requires std::random_access_iterator { + return x.iter_ > y.iter_; + } + + friend constexpr bool operator<=(const SwapCountingIterator& x, const SwapCountingIterator& y) + requires std::random_access_iterator { + return x.iter_ <= y.iter_; + } + + friend constexpr bool operator>=(const SwapCountingIterator& x, const SwapCountingIterator& y) + requires std::random_access_iterator { + return x.iter_ >= y.iter_; + } + + friend constexpr auto operator<=>(const SwapCountingIterator& x, const SwapCountingIterator& y) + requires(std::random_access_iterator && std::three_way_comparable) { + return x.iter_ <=> y.iter_; + } + + friend constexpr SwapCountingIterator operator+(const SwapCountingIterator& x, difference_type n) + requires std::random_access_iterator { + return SwapCountingIterator{x.iter_ + n}; + } + + friend constexpr SwapCountingIterator operator+(difference_type n, const SwapCountingIterator& x) + requires std::random_access_iterator { + return SwapCountingIterator{n + x.iter_}; + } + + friend constexpr SwapCountingIterator operator-(const SwapCountingIterator& x, difference_type n) + requires std::random_access_iterator { + return SwapCountingIterator{x.iter_ - n}; + } + + friend constexpr difference_type operator-(const SwapCountingIterator& x, const SwapCountingIterator& y) + requires std::random_access_iterator { + return x.iter_ - y.iter_; + } + +}; + +static_assert(std::bidirectional_iterator>>); +static_assert(std::random_access_iterator>>); + #endif // TEST_STD_VER > 17 #if TEST_STD_VER > 17 @@ -827,12 +961,12 @@ // ====================================================================== // Proxy that can wrap a value or a reference. It simulates C++23's tuple // but simplified to just hold one argument. -// Note that unlike tuple, this class deliberately doesn't have special handling -// of swap to cause a compilation error if it's used in an algorithm that relies +// Note that unlike tuple, this class deliberately doesn't have special handling +// of swap to cause a compilation error if it's used in an algorithm that relies // on plain swap instead of ranges::iter_swap. // This class is useful for testing that if algorithms support proxy iterator // properly, i.e. calling ranges::iter_swap and ranges::iter_move instead of -// plain swap and std::move +// plain swap and std::move template struct Proxy; @@ -920,29 +1054,16 @@ template requires std::derived_from< typename std::iterator_traits::iterator_category, - std::input_iterator_tag> + std::input_iterator_tag> struct ProxyIteratorBase { using iterator_category = std::input_iterator_tag; }; -template -consteval auto get_iterator_concept() { - if constexpr (std::random_access_iterator) { - return std::random_access_iterator_tag{}; - } else if constexpr (std::bidirectional_iterator) { - return std::bidirectional_iterator_tag{}; - } else if constexpr (std::forward_iterator) { - return std::forward_iterator_tag{}; - } else { - return std::input_iterator_tag{}; - } -} - template struct ProxyIterator : ProxyIteratorBase { Base base_; - using iterator_concept = decltype(get_iterator_concept()); + using iterator_concept = iter_concept_t; using value_type = Proxy>; using difference_type = std::iter_difference_t; @@ -951,8 +1072,8 @@ = default; constexpr ProxyIterator(Base base) : base_{std::move(base)} {} - - template + + template requires std::constructible_from constexpr ProxyIterator(T&& t) : base_{std::forward(t)} {}