diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -82,8 +82,8 @@ Permutation,push_heap,Konstantin Varlamov,`D128115 `_,✅ Permutation,pop_heap,Konstantin Varlamov,`D128115 `_,✅ Permutation,sort_heap,Konstantin Varlamov,`D128115 `_,✅ -Permutation,prev_permutation,Not assigned,n/a,Not started -Permutation,next_permutation,Not assigned,n/a,Not started +Permutation,next_permutation,Nikolas Klauser and Konstantin Varlamov,`D129859 `_,✅ +Permutation,prev_permutation,Nikolas Klauser and Konstantin Varlamov,`D129859 `_,✅ Uninitialised memory,uninitialized_copy,Konstantin Varlamov,`D116023 `_,✅ Uninitialised memory,uninitialized_copy_n,Konstantin Varlamov,`D116023 `_,✅ Uninitialised memory,uninitialized_fill,Konstantin Varlamov,`D115626 `_,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -113,6 +113,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.h @@ -121,6 +122,7 @@ __algorithm/ranges_partition_copy.h __algorithm/ranges_partition_point.h __algorithm/ranges_pop_heap.h + __algorithm/ranges_prev_permutation.h __algorithm/ranges_push_heap.h __algorithm/ranges_remove.h __algorithm/ranges_remove_copy.h diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h --- a/libcxx/include/__algorithm/iterator_operations.h +++ b/libcxx/include/__algorithm/iterator_operations.h @@ -10,6 +10,7 @@ #define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H #include <__algorithm/iter_swap.h> +#include <__algorithm/ranges_iterator_concept.h> #include <__config> #include <__iterator/advance.h> #include <__iterator/distance.h> @@ -40,6 +41,9 @@ template using __value_type = iter_value_t<_Iter>; + template + using __iterator_category = decltype(ranges::__iterator_concept<_Iter>()); + static constexpr auto advance = ranges::advance; static constexpr auto distance = ranges::distance; static constexpr auto __iter_move = ranges::iter_move; @@ -58,6 +62,9 @@ template using __value_type = typename iterator_traits<_Iter>::value_type; + template + using __iterator_category = typename iterator_traits<_Iter>::iterator_category; + // advance template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 diff --git a/libcxx/include/__algorithm/next_permutation.h b/libcxx/include/__algorithm/next_permutation.h --- a/libcxx/include/__algorithm/next_permutation.h +++ b/libcxx/include/__algorithm/next_permutation.h @@ -11,10 +11,12 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/reverse.h> #include <__config> #include <__iterator/iterator_traits.h> -#include <__utility/swap.h> +#include <__utility/move.h> +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -22,29 +24,34 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 bool -__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 +pair<_BidirectionalIterator, bool> +__next_permutation(_BidirectionalIterator __first, _Sentinel __last, _Compare&& __comp) { - _BidirectionalIterator __i = __last; + using _Result = pair<_BidirectionalIterator, bool>; + + _BidirectionalIterator __last_iter = _IterOps<_AlgPolicy>::next(__first, __last); + _BidirectionalIterator __i = __last_iter; if (__first == __last || __first == --__i) - return false; + return _Result(std::move(__last_iter), false); + while (true) { _BidirectionalIterator __ip1 = __i; if (__comp(*--__i, *__ip1)) { - _BidirectionalIterator __j = __last; + _BidirectionalIterator __j = __last_iter; while (!__comp(*__i, *--__j)) ; - swap(*__i, *__j); - _VSTD::reverse(__ip1, __last); - return true; + _IterOps<_AlgPolicy>::iter_swap(__i, __j); + std::__reverse<_AlgPolicy>(__ip1, __last_iter); + return _Result(std::move(__last_iter), true); } if (__i == __first) { - _VSTD::reverse(__first, __last); - return false; + std::__reverse<_AlgPolicy>(__first, __last_iter); + return _Result(std::move(__last_iter), false); } } } @@ -54,8 +61,9 @@ bool next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp); + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + return std::__next_permutation<_ClassicAlgPolicy>( + std::move(__first), std::move(__last), static_cast<_Comp_ref>(__comp)).second; } template diff --git a/libcxx/include/__algorithm/prev_permutation.h b/libcxx/include/__algorithm/prev_permutation.h --- a/libcxx/include/__algorithm/prev_permutation.h +++ b/libcxx/include/__algorithm/prev_permutation.h @@ -11,10 +11,12 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/reverse.h> #include <__config> #include <__iterator/iterator_traits.h> -#include <__utility/swap.h> +#include <__utility/move.h> +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -22,29 +24,34 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 bool -__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 +pair<_BidirectionalIterator, bool> +__prev_permutation(_BidirectionalIterator __first, _Sentinel __last, _Compare&& __comp) { - _BidirectionalIterator __i = __last; + using _Result = pair<_BidirectionalIterator, bool>; + + _BidirectionalIterator __last_iter = _IterOps<_AlgPolicy>::next(__first, __last); + _BidirectionalIterator __i = __last_iter; if (__first == __last || __first == --__i) - return false; + return _Result(std::move(__last_iter), false); + while (true) { _BidirectionalIterator __ip1 = __i; if (__comp(*__ip1, *--__i)) { - _BidirectionalIterator __j = __last; + _BidirectionalIterator __j = __last_iter; while (!__comp(*--__j, *__i)) ; - swap(*__i, *__j); - _VSTD::reverse(__ip1, __last); - return true; + _IterOps<_AlgPolicy>::iter_swap(__i, __j); + std::__reverse<_AlgPolicy>(__ip1, __last_iter); + return _Result(std::move(__last_iter), true); } if (__i == __first) { - _VSTD::reverse(__first, __last); - return false; + std::__reverse<_AlgPolicy>(__first, __last_iter); + return _Result(std::move(__last_iter), false); } } } @@ -54,8 +61,9 @@ bool prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__prev_permutation<_Comp_ref>(__first, __last, __comp); + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + return std::__prev_permutation<_ClassicAlgPolicy>( + std::move(__first), std::move(__last), static_cast<_Comp_ref>(__comp)).second; } template 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,72 @@ +//===----------------------------------------------------------------------===// +// +// 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/iterator_operations.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/next_permutation.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.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 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 __result = std::__next_permutation<_RangeAlgPolicy>( + std::move(__first), std::move(__last), std::__make_projected(__comp, __proj)); + return {std::move(__result.first), std::move(__result.second)}; + } + + template + requires sortable, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr next_permutation_result> + operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const { + auto __result = std::__next_permutation<_RangeAlgPolicy>( + ranges::begin(__range), ranges::end(__range), std::__make_projected(__comp, __proj)); + return {std::move(__result.first), std::move(__result.second)}; + } +}; + +} // 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,75 @@ +//===----------------------------------------------------------------------===// +// +// 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/iterator_operations.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/prev_permutation.h> +#include <__config> +#include <__functional/identity.h> +#include <__iterator/concepts.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.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>; + +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 { + auto __result = std::__prev_permutation<_RangeAlgPolicy>( + std::move(__first), std::move(__last), std::__make_projected(__comp, __proj)); + return {std::move(__result.first), std::move(__result.second)}; + } + + template + requires sortable, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr prev_permutation_result> + operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const { + auto __result = std::__prev_permutation<_RangeAlgPolicy>( + ranges::begin(__range), ranges::end(__range), std::__make_projected(__comp, __proj)); + return {std::move(__result.first), std::move(__result.second)}; + } + +}; + +} // 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/reverse.h b/libcxx/include/__algorithm/reverse.h --- a/libcxx/include/__algorithm/reverse.h +++ b/libcxx/include/__algorithm/reverse.h @@ -10,8 +10,10 @@ #define _LIBCPP___ALGORITHM_REVERSE_H #include <__algorithm/iter_swap.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -19,28 +21,35 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void -__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag) +__reverse_impl(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag) { while (__first != __last) { if (__first == --__last) break; - _VSTD::iter_swap(__first, __last); + _IterOps<_AlgPolicy>::iter_swap(__first, __last); ++__first; } } -template +template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void -__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag) +__reverse_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag) { if (__first != __last) for (; __first < --__last; ++__first) - _VSTD::iter_swap(__first, __last); + _IterOps<_AlgPolicy>::iter_swap(__first, __last); +} + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void __reverse(_BidirectionalIterator __first, _Sentinel __last) { + using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_BidirectionalIterator>; + std::__reverse_impl<_AlgPolicy>(std::move(__first), std::move(__last), _IterCategory()); } template @@ -48,7 +57,7 @@ void reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) { - _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category()); + std::__reverse<_ClassicAlgPolicy>(std::move(__first), std::move(__last)); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -912,8 +912,40 @@ indirectly_copyable_storable, O>) constexpr unique_copy_result, O> unique_copy(R&& r, O result, C comp = {}, Proj proj = {}); // Since C++20 -} + template + using prev_permutation_result = in_found_result; // 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 + using next_permutation_result = in_found_result; // 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 + + } + +template constexpr bool // constexpr in C++20 all_of(InputIterator first, InputIterator last, Predicate pred); @@ -1684,6 +1716,7 @@ #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_partial_sort.h> @@ -1692,6 +1725,7 @@ #include <__algorithm/ranges_partition_copy.h> #include <__algorithm/ranges_partition_point.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/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -150,6 +150,7 @@ #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}} #include <__algorithm/ranges_move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move.h'}} #include <__algorithm/ranges_move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}} +#include <__algorithm/ranges_next_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_next_permutation.h'}} #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}} #include <__algorithm/ranges_nth_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_nth_element.h'}} #include <__algorithm/ranges_partial_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partial_sort.h'}} @@ -158,6 +159,7 @@ #include <__algorithm/ranges_partition_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partition_copy.h'}} #include <__algorithm/ranges_partition_point.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partition_point.h'}} #include <__algorithm/ranges_pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_pop_heap.h'}} +#include <__algorithm/ranges_prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_prev_permutation.h'}} #include <__algorithm/ranges_push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_push_heap.h'}} #include <__algorithm/ranges_remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove.h'}} #include <__algorithm/ranges_remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_copy.h'}} 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,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 +// +//===----------------------------------------------------------------------===// + +// + +// 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) { + std::array memoized = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; + return memoized[i]; +} + +template +constexpr bool run_next_permutation(Func call_next_permutation, Range permuted, Range previous) { + using Result = std::ranges::next_permutation_result; + + std::same_as 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 +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(call_next_permutation, current_subrange, previous_subrange); + } + + assert(count == factorial(i)); + } +} + +template +constexpr void test_all_permutations() { + test_next_permutations([](auto&& range) { + return std::ranges::next_permutation(range.begin(), range.end()); + }); + + test_next_permutations([](auto&& range) { + return std::ranges::next_permutation(range); + }); +} + +template +constexpr void test_one(const std::array input, bool expected_found, std::array expected) { + using Result = std::ranges::next_permutation_result; + + { // (iterator, sentinel) overload. + auto in = input; + auto begin = Iter(in.data()); + auto end = Sent(Iter(in.data() + in.size())); + + std::same_as 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 decltype(auto) result = std::ranges::next_permutation(range); + assert(result.found == expected_found); + assert(result.in == end); + assert(in == expected); + } +} + +template +constexpr void test_iter_sent() { + test_all_permutations(); + + // Empty range. + test_one({}, false, {}); + // 1-element range. + test_one({1}, false, {1}); + // 2-element range. + test_one({1, 2}, true, {2, 1}); + test_one({2, 1}, false, {1, 2}); + // Longer sequence. + test_one({1, 2, 3, 4, 5, 6, 7, 8}, true, {1, 2, 3, 4, 5, 6, 8, 7}); + // Longer sequence, permutations exhausted. + test_one({8, 7, 6, 5, 4, 3, 2, 1}, false, {1, 2, 3, 4, 5, 6, 7, 8}); +} + +template +constexpr void test_iter() { + test_iter_sent(); + test_iter_sent>(); + test_iter_sent>(); +} + +constexpr void test_iterators() { + test_iter>(); + test_iter>(); + test_iter>(); + test_iter(); +} + +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 --- /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 +// +//===----------------------------------------------------------------------===// + +// + +// 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) { + std::array memoized = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; + return memoized[i]; +} + +template +constexpr bool run_prev_permutation(Func call_prev_permutation, Range permuted, Range previous) { + using Result = std::ranges::prev_permutation_result; + + std::same_as 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 +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(call_prev_permutation, current_subrange, previous_subrange); + } + + assert(count == factorial(i)); + } +} + +template +constexpr void test_all_permutations() { + test_prev_permutations([](auto&& range) { + return std::ranges::prev_permutation(range.begin(), range.end()); + }); + + test_prev_permutations([](auto&& range) { + return std::ranges::prev_permutation(range); + }); +} + +template +constexpr void test_one(const std::array input, bool expected_found, std::array expected) { + using Result = std::ranges::prev_permutation_result; + + { // (iterator, sentinel) overload. + auto in = input; + auto begin = Iter(in.data()); + auto end = Sent(Iter(in.data() + in.size())); + + std::same_as 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 decltype(auto) result = std::ranges::prev_permutation(range); + assert(result.found == expected_found); + assert(result.in == end); + assert(in == expected); + } +} + +template +constexpr void test_iter_sent() { + test_all_permutations(); + + // Empty range. + test_one({}, false, {}); + // 1-element range. + test_one({1}, false, {1}); + // 2-element range. + test_one({1, 2}, false, {2, 1}); + test_one({2, 1}, true, {1, 2}); + // Longer sequence. + test_one({8, 7, 6, 5, 4, 3, 2, 1}, true, {8, 7, 6, 5, 4, 3, 1, 2}); + // Longer sequence, permutations exhausted. + test_one({1, 2, 3, 4, 5, 6, 7, 8}, false, {8, 7, 6, 5, 4, 3, 2, 1}); +} + +template +constexpr void test_iter() { + test_iter_sent(); + test_iter_sent>(); + test_iter_sent>(); +} + +constexpr void test_iterators() { + test_iter>(); + test_iter>(); + test_iter>(); + test_iter(); +} + +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 --- 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.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp --- 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 @@ 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 --- 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 @@ 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; } 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);