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 @@ -68,7 +68,7 @@ Permutation,remove,Nikolas Klauser,`D128618 `_,✅ Permutation,remove_if,Nikolas Klauser,`D128618 `_,✅ Permutation,reverse,Nikolas Klauser,`D125752 `_,✅ -Permutation,rotate,Nikolas Klauser,`D124122 `_,Under review +Permutation,rotate,Konstantin Varlamov and Nikolas Klauser,`D130758 `_,✅ Permutation,shuffle,Konstantin Varlamov,`D130321 `_,✅ Permutation,unique,Hui Xie,`D130404 `_,✅ Permutation,partition,Konstantin Varlamov,`D129624 `_,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -1,6 +1,5 @@ set(files __algorithm/adjacent_find.h - __algorithm/algorithm_family.h __algorithm/all_of.h __algorithm/any_of.h __algorithm/binary_search.h @@ -134,6 +133,7 @@ __algorithm/ranges_replace_if.h __algorithm/ranges_reverse.h __algorithm/ranges_reverse_copy.h + __algorithm/ranges_rotate.h __algorithm/ranges_rotate_copy.h __algorithm/ranges_sample.h __algorithm/ranges_search.h diff --git a/libcxx/include/__algorithm/algorithm_family.h b/libcxx/include/__algorithm/algorithm_family.h deleted file mode 100644 --- a/libcxx/include/__algorithm/algorithm_family.h +++ /dev/null @@ -1,52 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// 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_ALGORITHM_FAMILY_H -#define _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H - -#include <__algorithm/iterator_operations.h> -#include <__algorithm/move.h> -#include <__algorithm/ranges_move.h> -#include <__config> -#include <__utility/move.h> - -#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -# pragma GCC system_header -#endif - -_LIBCPP_BEGIN_NAMESPACE_STD - -template -struct _AlgFamily; - -#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) - -template <> -struct _AlgFamily<_RangeAlgPolicy> { - static constexpr auto __move = ranges::move; -}; - -#endif - -template <> -struct _AlgFamily<_ClassicAlgPolicy> { - - // move - template - _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 static _OutputIterator - __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return std::move( - std::move(__first), - std::move(__last), - std::move(__result)); - } -}; - -_LIBCPP_END_NAMESPACE_STD - -#endif // _LIBCPP___ALGORITHM_ALGORITHM_FAMILY_H diff --git a/libcxx/include/__algorithm/inplace_merge.h b/libcxx/include/__algorithm/inplace_merge.h --- a/libcxx/include/__algorithm/inplace_merge.h +++ b/libcxx/include/__algorithm/inplace_merge.h @@ -9,7 +9,6 @@ #ifndef _LIBCPP___ALGORITHM_INPLACE_MERGE_H #define _LIBCPP___ALGORITHM_INPLACE_MERGE_H -#include <__algorithm/algorithm_family.h> #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/iterator_operations.h> @@ -65,7 +64,7 @@ { if (__first2 == __last2) { - _AlgFamily<_AlgPolicy>::__move(__first1, __last1, __result); + std::__move<_AlgPolicy>(__first1, __last1, __result); return; } @@ -185,8 +184,7 @@ difference_type __len22 = __len2 - __len21; // distance(__m2, __last) // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) // swap middle two partitions - // TODO(alg-policy): pass `_AlgPolicy` once it's supported by `rotate`. - __middle = _VSTD::rotate(__m1, __middle, __m2); + __middle = std::__rotate<_AlgPolicy>(__m1, __middle, __m2).first; // __len12 and __len21 now have swapped meanings // merge smaller range with recursive call and larger with tail recursion elimination if (__len11 + __len21 < __len12 + __len22) 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 @@ -19,6 +19,7 @@ #include <__iterator/iter_swap.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> +#include <__iterator/prev.h> #include <__iterator/readable_traits.h> #include <__utility/declval.h> #include <__utility/forward.h> @@ -53,6 +54,7 @@ static constexpr auto __iter_move = ranges::iter_move; static constexpr auto iter_swap = ranges::iter_swap; static constexpr auto next = ranges::next; + static constexpr auto prev = ranges::prev; static constexpr auto __advance_to = ranges::advance; }; @@ -146,10 +148,18 @@ template _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 __uncvref_t<_Iter> next(_Iter&& __it, - typename iterator_traits<__uncvref_t<_Iter> >::difference_type __n = 1){ + typename iterator_traits<__uncvref_t<_Iter> >::difference_type __n = 1) { return std::next(std::forward<_Iter>(__it), __n); } + // prev + template + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 + __uncvref_t<_Iter> prev(_Iter&& __iter, + typename iterator_traits<__uncvref_t<_Iter> >::difference_type __n = 1) { + return std::prev(std::forward<_Iter>(__iter), __n); + } + template _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void __advance_to(_Iter& __first, _Iter __last) { diff --git a/libcxx/include/__algorithm/move.h b/libcxx/include/__algorithm/move.h --- a/libcxx/include/__algorithm/move.h +++ b/libcxx/include/__algorithm/move.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_H #define _LIBCPP___ALGORITHM_MOVE_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/unwrap_iter.h> #include <__config> #include <__iterator/iterator_traits.h> @@ -26,18 +27,19 @@ // move -template +template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 pair<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { while (__first != __last) { - *__result = std::move(*__first); + *__result = _IterOps<_AlgPolicy>::__iter_move(__first); ++__first; ++__result; } return std::make_pair(std::move(__first), std::move(__result)); } -template ::type, _OutType>::value && is_trivially_move_assignable<_OutType>::value> > @@ -49,7 +51,7 @@ && !is_trivially_copyable<_InType>::value #endif ) - return std::__move_impl<_InType*, _InType*, _OutType*>(__first, __last, __result); + return std::__move_impl<_AlgPolicy, _InType*, _InType*, _OutType*>(__first, __last, __result); const size_t __n = static_cast(__last - __first); ::__builtin_memmove(__result, __first, __n * sizeof(_OutType)); return std::make_pair(__first + __n, __result + __n); @@ -65,7 +67,8 @@ struct __is_trivially_move_assignable_unwrapped : __is_trivially_move_assignable_unwrapped_impl(std::declval<_Iter>()))> {}; -template ::value_type>::type, typename iterator_traits<_OutIter>::value_type>::value @@ -81,33 +84,34 @@ auto __last_base = std::__unwrap_iter(__last.base()); auto __result_base = std::__unwrap_iter(__result.base()); auto __result_first = __result_base - (__first_base - __last_base); - std::__move_impl(__last_base, __first_base, __result_first); + std::__move_impl<_AlgPolicy>(__last_base, __first_base, __result_first); return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first))); } -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 __enable_if_t::value && is_copy_constructible<_Sent>::value && is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> > __move(_InIter __first, _Sent __last, _OutIter __result) { - auto __ret = std::__move_impl(std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result)); + auto __ret = std::__move_impl<_AlgPolicy>( + std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result)); return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); } -template +template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 __enable_if_t::value || !is_copy_constructible<_Sent>::value || !is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> > __move(_InIter __first, _Sent __last, _OutIter __result) { - return std::__move_impl(std::move(__first), std::move(__last), std::move(__result)); + return std::__move_impl<_AlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); } template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return std::__move(__first, __last, __result).second; + return std::__move<_ClassicAlgPolicy>(__first, __last, __result).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/move_backward.h b/libcxx/include/__algorithm/move_backward.h --- a/libcxx/include/__algorithm/move_backward.h +++ b/libcxx/include/__algorithm/move_backward.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_BACKWARD_H #define _LIBCPP___ALGORITHM_MOVE_BACKWARD_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/unwrap_iter.h> #include <__config> #include <__utility/move.h> @@ -21,25 +22,25 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 _OutputIterator __move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { while (__first != __last) - *--__result = _VSTD::move(*--__last); + *--__result = _IterOps<_AlgPolicy>::__iter_move(--__last); return __result; } -template +template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 _OutputIterator -__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result) +__move_backward_impl(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { - return _VSTD::__move_backward_constexpr(__first, __last, __result); + return _VSTD::__move_backward_constexpr<_AlgPolicy>(__first, __last, __result); } -template +template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 typename enable_if < @@ -47,7 +48,7 @@ is_trivially_move_assignable<_Up>::value, _Up* >::type -__move_backward(_Tp* __first, _Tp* __last, _Up* __result) +__move_backward_impl(_Tp* __first, _Tp* __last, _Up* __result) { const size_t __n = static_cast(__last - __first); if (__n > 0) @@ -58,22 +59,31 @@ return __result; } -template +template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator2 -move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, - _BidirectionalIterator2 __result) +__move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, + _BidirectionalIterator2 __result) { if (__libcpp_is_constant_evaluated()) { - return _VSTD::__move_backward_constexpr(__first, __last, __result); + return _VSTD::__move_backward_constexpr<_AlgPolicy>(__first, __last, __result); } else { return _VSTD::__rewrap_iter(__result, - _VSTD::__move_backward(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result))); + _VSTD::__move_backward_impl<_AlgPolicy>(_VSTD::__unwrap_iter(__first), + _VSTD::__unwrap_iter(__last), + _VSTD::__unwrap_iter(__result))); } } +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_BidirectionalIterator2 +move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, + _BidirectionalIterator2 __result) +{ + return std::__move_backward<_ClassicAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); +} + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ALGORITHM_MOVE_BACKWARD_H diff --git a/libcxx/include/__algorithm/ranges_move.h b/libcxx/include/__algorithm/ranges_move.h --- a/libcxx/include/__algorithm/ranges_move.h +++ b/libcxx/include/__algorithm/ranges_move.h @@ -10,6 +10,7 @@ #define _LIBCPP___ALGORITHM_RANGES_MOVE_H #include <__algorithm/in_out_result.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/move.h> #include <__config> #include <__iterator/concepts.h> @@ -36,24 +37,12 @@ struct __fn { template - requires __iter_move::__move_deref<_InIter> // check that we are allowed to std::move() the value _LIBCPP_HIDE_FROM_ABI constexpr static move_result<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { - auto __ret = std::__move(std::move(__first), std::move(__last), std::move(__result)); + auto __ret = std::__move<_RangeAlgPolicy>(std::move(__first), std::move(__last), std::move(__result)); return {std::move(__ret.first), std::move(__ret.second)}; } - template - _LIBCPP_HIDE_FROM_ABI constexpr static - move_result<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { - while (__first != __last) { - *__result = ranges::iter_move(__first); - ++__first; - ++__result; - } - return {std::move(__first), std::move(__result)}; - } - template _Sent, weakly_incrementable _OutIter> requires indirectly_movable<_InIter, _OutIter> _LIBCPP_HIDE_FROM_ABI constexpr diff --git a/libcxx/include/__algorithm/ranges_rotate.h b/libcxx/include/__algorithm/ranges_rotate.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_rotate.h @@ -0,0 +1,71 @@ +//===----------------------------------------------------------------------===// +// +// 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_ROTATE_H +#define _LIBCPP___ALGORITHM_RANGES_ROTATE_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/ranges_iterator_concept.h> +#include <__algorithm/rotate.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/permutable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/subrange.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __rotate { + +struct __fn { + + template + _LIBCPP_HIDE_FROM_ABI constexpr + static subrange<_Iter> __rotate_fn_impl(_Iter __first, _Iter __middle, _Sent __last) { + auto __ret = std::__rotate<_RangeAlgPolicy>( + std::move(__first), std::move(__middle), std::move(__last)); + return {std::move(__ret.first), std::move(__ret.second)}; + } + + template _Sent> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter> operator()(_Iter __first, _Iter __middle, _Sent __last) const { + return __rotate_fn_impl(std::move(__first), std::move(__middle), std::move(__last)); + } + + template + requires permutable> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, iterator_t<_Range> __middle) const { + return __rotate_fn_impl(ranges::begin(__range), std::move(__middle), ranges::end(__range)); + } + +}; + +} // namespace __rotate + +inline namespace __cpo { + inline constexpr auto rotate = __rotate::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_ROTATE_H diff --git a/libcxx/include/__algorithm/ranges_swap_ranges.h b/libcxx/include/__algorithm/ranges_swap_ranges.h --- a/libcxx/include/__algorithm/ranges_swap_ranges.h +++ b/libcxx/include/__algorithm/ranges_swap_ranges.h @@ -10,6 +10,8 @@ #define _LIBCPP___ALGORITHM_RANGES_SWAP_RANGES_H #include <__algorithm/in_in_result.h> +#include <__algorithm/iterator_operations.h> +#include <__algorithm/swap_ranges.h> #include <__config> #include <__iterator/concepts.h> #include <__iterator/iter_swap.h> @@ -38,12 +40,9 @@ requires indirectly_swappable<_I1, _I2> _LIBCPP_HIDE_FROM_ABI constexpr swap_ranges_result<_I1, _I2> operator()(_I1 __first1, _S1 __last1, _I2 __first2, _S2 __last2) const { - while (__first1 != __last1 && __first2 != __last2) { - ranges::iter_swap(__first1, __first2); - ++__first1; - ++__first2; - } - return {_VSTD::move(__first1), _VSTD::move(__first2)}; + auto __ret = std::__swap_ranges<_RangeAlgPolicy>( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2)); + return {std::move(__ret.first), std::move(__ret.second)}; } template diff --git a/libcxx/include/__algorithm/rotate.h b/libcxx/include/__algorithm/rotate.h --- a/libcxx/include/__algorithm/rotate.h +++ b/libcxx/include/__algorithm/rotate.h @@ -15,10 +15,8 @@ #include <__algorithm/swap_ranges.h> #include <__config> #include <__iterator/iterator_traits.h> -#include <__iterator/next.h> -#include <__iterator/prev.h> #include <__utility/move.h> -#include <__utility/swap.h> +#include <__utility/pair.h> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -32,9 +30,11 @@ __rotate_left(_ForwardIterator __first, _ForwardIterator __last) { typedef typename iterator_traits<_ForwardIterator>::value_type value_type; - value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__first); - // TODO(ranges): pass `_AlgPolicy` to `move`. - _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first); + using _Ops = _IterOps<_AlgPolicy>; + + value_type __tmp = _Ops::__iter_move(__first); + _ForwardIterator __lm1 = std::__move<_AlgPolicy>( + _Ops::next(__first), __last, __first).second; *__lm1 = _VSTD::move(__tmp); return __lm1; } @@ -44,11 +44,11 @@ __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last) { typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; - // TODO(ranges): pass `_AlgPolicy` to `prev`. - _BidirectionalIterator __lm1 = _VSTD::prev(__last); - value_type __tmp = _IterOps<_AlgPolicy>::__iter_move(__lm1); - // TODO(ranges): pass `_AlgPolicy` to `move_backward`. - _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last); + using _Ops = _IterOps<_AlgPolicy>; + + _BidirectionalIterator __lm1 = _Ops::prev(__last); + value_type __tmp = _Ops::__iter_move(__lm1); + _BidirectionalIterator __fp1 = std::__move_backward<_AlgPolicy>(__first, __lm1, std::move(__last)); *__first = _VSTD::move(__tmp); return __fp1; } @@ -108,26 +108,26 @@ { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; + using _Ops = _IterOps<_AlgPolicy>; const difference_type __m1 = __middle - __first; - const difference_type __m2 = __last - __middle; + const difference_type __m2 = _Ops::distance(__middle, __last); if (__m1 == __m2) { - // TODO(ranges): pass `_AlgPolicy` to `swap_ranges`. - _VSTD::swap_ranges(__first, __middle, __middle); + std::__swap_ranges<_AlgPolicy>(__first, __middle, __middle, __last); return __middle; } const difference_type __g = _VSTD::__algo_gcd(__m1, __m2); for (_RandomAccessIterator __p = __first + __g; __p != __first;) { - value_type __t(_IterOps<_AlgPolicy>::__iter_move(--__p)); + value_type __t(_Ops::__iter_move(--__p)); _RandomAccessIterator __p1 = __p; _RandomAccessIterator __p2 = __p1 + __m1; do { - *__p1 = _IterOps<_AlgPolicy>::__iter_move(__p2); + *__p1 = _Ops::__iter_move(__p2); __p1 = __p2; - const difference_type __d = __last - __p2; + const difference_type __d = _Ops::distance(__p2, __last); if (__m1 < __d) __p2 += __m1; else @@ -188,16 +188,23 @@ return std::__rotate_forward<_AlgPolicy>(__first, __middle, __last); } -template +template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -_RandomAccessIterator __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, - _RandomAccessIterator __last, _IterCategory __iter_category) { +pair<_Iterator, _Iterator> +__rotate(_Iterator __first, _Iterator __middle, _Sentinel __last) { + using _Ret = pair<_Iterator, _Iterator>; + _Iterator __last_iter = _IterOps<_AlgPolicy>::next(__middle, __last); + if (__first == __middle) - return __last; + return _Ret(__last_iter, __last_iter); if (__middle == __last) - return __first; + return _Ret(std::move(__first), std::move(__last_iter)); + + using _IterCategory = typename _IterOps<_AlgPolicy>::template __iterator_category<_Iterator>; + auto __result = std::__rotate_impl<_AlgPolicy>( + std::move(__first), std::move(__middle), __last_iter, _IterCategory()); - return std::__rotate_impl<_AlgPolicy>(std::move(__first), std::move(__middle), std::move(__last), __iter_category); + return _Ret(std::move(__result), std::move(__last_iter)); } template @@ -205,8 +212,8 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last) { - return std::__rotate<_ClassicAlgPolicy>(__first, __middle, __last, - typename iterator_traits<_ForwardIterator>::iterator_category()); + return std::__rotate<_ClassicAlgPolicy>( + std::move(__first), std::move(__middle), std::move(__last)).first; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/stable_partition.h b/libcxx/include/__algorithm/stable_partition.h --- a/libcxx/include/__algorithm/stable_partition.h +++ b/libcxx/include/__algorithm/stable_partition.h @@ -108,7 +108,7 @@ __second_half_done: // TTTFFFFFTTTTTFFFFF // f ff m sf l - return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false, __fit); + return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first; // TTTTTTTTFFFFFFFFFF // | } @@ -253,7 +253,7 @@ __second_half_done: // TTTFFFFFTTTTTFFFFF // f ff m sf l - return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false, __bit); + return std::__rotate<_AlgPolicy>(__first_false, __m, __second_false).first; // TTTTTTTTFFFFFFFFFF // | } diff --git a/libcxx/include/__algorithm/swap_ranges.h b/libcxx/include/__algorithm/swap_ranges.h --- a/libcxx/include/__algorithm/swap_ranges.h +++ b/libcxx/include/__algorithm/swap_ranges.h @@ -9,8 +9,10 @@ #ifndef _LIBCPP___ALGORITHM_SWAP_RANGES_H #define _LIBCPP___ALGORITHM_SWAP_RANGES_H +#include <__algorithm/iterator_operations.h> #include <__config> -#include <__utility/swap.h> +#include <__utility/move.h> +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -18,12 +20,39 @@ _LIBCPP_BEGIN_NAMESPACE_STD +// 2+2 iterators: the shorter size will be used. +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +pair<_ForwardIterator1, _ForwardIterator2> +__swap_ranges(_ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2, _Sentinel2 __last2) { + while (__first1 != __last1 && __first2 != __last2) { + _IterOps<_AlgPolicy>::iter_swap(__first1, __first2); + ++__first1; + ++__first2; + } + + return pair<_ForwardIterator1, _ForwardIterator2>(std::move(__first1), std::move(__first2)); +} + +// 2+1 iterators: size2 >= size1. +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +pair<_ForwardIterator1, _ForwardIterator2> +__swap_ranges(_ForwardIterator1 __first1, _Sentinel1 __last1, _ForwardIterator2 __first2) { + while (__first1 != __last1) { + _IterOps<_AlgPolicy>::iter_swap(__first1, __first2); + ++__first1; + ++__first2; + } + + return pair<_ForwardIterator1, _ForwardIterator2>(std::move(__first1), std::move(__first2)); +} + template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) { - for (; __first1 != __last1; ++__first1, (void)++__first2) - swap(*__first1, *__first2); - return __first2; + return std::__swap_ranges<_ClassicAlgPolicy>( + std::move(__first1), std::move(__last1), std::move(__first2)).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__iterator/reverse_iterator.h b/libcxx/include/__iterator/reverse_iterator.h --- a/libcxx/include/__iterator/reverse_iterator.h +++ b/libcxx/include/__iterator/reverse_iterator.h @@ -363,7 +363,7 @@ _Iter __iter_; public: - static_assert(__is_cpp17_bidirectional_iterator<_Iter>::value); + static_assert(__is_cpp17_bidirectional_iterator<_Iter>::value || bidirectional_iterator<_Iter>); using iterator_type = _Iter; using iterator_category = @@ -391,6 +391,14 @@ } } + _LIBCPP_HIDE_FROM_ABI friend constexpr + iter_rvalue_reference_t<_Iter> iter_move(const __unconstrained_reverse_iterator& __i) + noexcept(is_nothrow_copy_constructible_v<_Iter> && + noexcept(ranges::iter_move(--declval<_Iter&>()))) { + auto __tmp = __i.base(); + return ranges::iter_move(--__tmp); + } + _LIBCPP_HIDE_FROM_ABI constexpr __unconstrained_reverse_iterator& operator++() { --__iter_; return *this; diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -745,6 +745,13 @@ constexpr ranges::reverse_copy_result, O> ranges::reverse_copy(R&& r, O result); // since C++20 + template S> + constexpr subrange rotate(I first, I middle, S last); // since C++20 + + template + requires permutable> + constexpr borrowed_subrange_t rotate(R&& r, iterator_t middle); // Since C++20 + template using rotate_copy_result = in_out_result<_InIter, _OutIter>; // since C++20 @@ -1817,6 +1824,7 @@ #include <__algorithm/ranges_replace_if.h> #include <__algorithm/ranges_reverse.h> #include <__algorithm/ranges_reverse_copy.h> +#include <__algorithm/ranges_rotate.h> #include <__algorithm/ranges_rotate_copy.h> #include <__algorithm/ranges_sample.h> #include <__algorithm/ranges_search.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -239,7 +239,6 @@ module __algorithm { module adjacent_find { private header "__algorithm/adjacent_find.h" } - module algorithm_family { private header "__algorithm/algorithm_family.h" } module all_of { private header "__algorithm/all_of.h" } module any_of { private header "__algorithm/any_of.h" } module binary_search { private header "__algorithm/binary_search.h" } @@ -373,6 +372,7 @@ module ranges_replace_if { private header "__algorithm/ranges_replace_if.h" } module ranges_reverse { private header "__algorithm/ranges_reverse.h" } module ranges_reverse_copy { private header "__algorithm/ranges_reverse_copy.h" } + module ranges_rotate { private header "__algorithm/ranges_rotate.h" } module ranges_rotate_copy { private header "__algorithm/ranges_rotate_copy.h" } module ranges_sample { private header "__algorithm/ranges_sample.h" } module ranges_search { private header "__algorithm/ranges_search.h" } 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 @@ -37,7 +37,6 @@ // DO NOT MANUALLY EDIT ANYTHING BETWEEN THE MARKERS BELOW // GENERATED-MARKER #include <__algorithm/adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/adjacent_find.h'}} -#include <__algorithm/algorithm_family.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/algorithm_family.h'}} #include <__algorithm/all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/all_of.h'}} #include <__algorithm/any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/any_of.h'}} #include <__algorithm/binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/binary_search.h'}} @@ -171,6 +170,7 @@ #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}} #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}} #include <__algorithm/ranges_reverse_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse_copy.h'}} +#include <__algorithm/ranges_rotate.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_rotate.h'}} #include <__algorithm/ranges_rotate_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_rotate_copy.h'}} #include <__algorithm/ranges_sample.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sample.h'}} #include <__algorithm/ranges_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search.h'}} diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges_rotate.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges_rotate.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/ranges_rotate.pass.cpp @@ -0,0 +1,191 @@ +//===----------------------------------------------------------------------===// +// +// 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> +// constexpr subrange rotate(I first, I middle, S last); // since C++20 +// +// template +// requires permutable> +// constexpr borrowed_subrange_t rotate(R&& r, iterator_t middle); // Since C++20 + +#include +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +// Test constraints of the (iterator, sentinel) overload. +// ====================================================== + +template +concept HasRotateIter = + requires(Iter&& iter, Sent&& sent) { + std::ranges::rotate(std::forward(iter), std::forward(iter), std::forward(sent)); + }; + +static_assert(HasRotateIter); + +// !permutable +static_assert(!HasRotateIter); +static_assert(!HasRotateIter); + +// !sentinel_for +static_assert(!HasRotateIter); +static_assert(!HasRotateIter); + +// Test constraints of the (range) overload. +// ========================================= + +template +concept HasRotateRange = + requires(Range&& range, std::ranges::iterator_t iter) { + std::ranges::rotate(std::forward(range), iter); + }; + +template +using R = UncheckedRange; + +static_assert(HasRotateRange>); + +// !forward_range +static_assert(!HasRotateRange); +static_assert(!HasRotateRange); +static_assert(!HasRotateRange); +static_assert(!HasRotateRange); + +// !permutable> +static_assert(!HasRotateRange); +static_assert(!HasRotateRange); + +template +constexpr void test_one(const std::array input, size_t mid_index, std::array expected) { + assert(mid_index <= N); + + { // (iterator, sentinel) overload. + auto in = input; + auto begin = Iter(in.data()); + auto mid = Iter(in.data() + mid_index); + auto end = Sent(Iter(in.data() + in.size())); + + std::same_as> decltype(auto) result = std::ranges::rotate(begin, mid, end); + assert(base(result.begin()) == in.data() + in.size() - mid_index); + assert(base(result.end()) == in.data() + in.size()); + assert(in == expected); + } + + { // (range) overload. + auto in = input; + auto begin = Iter(in.data()); + auto mid = Iter(in.data() + mid_index); + auto end = Sent(Iter(in.data() + in.size())); + auto range = std::ranges::subrange(std::move(begin), std::move(end)); + + std::same_as> decltype(auto) result = std::ranges::rotate(range, mid); + assert(base(result.begin()) == in.data() + in.size() - mid_index); + assert(base(result.end()) == in.data() + in.size()); + assert(in == expected); + } +} + +template +constexpr void test_iter_sent() { + // Empty sequence. + test_one({}, 0, {}); + + // 1-element sequence. + test_one({1}, 0, {1}); + + // 2-element sequence. + test_one({1, 2}, 1, {2, 1}); + + // 3-element sequence. + test_one({1, 2, 3}, 1, {2, 3, 1}); + test_one({1, 2, 3}, 2, {3, 1, 2}); + + // Longer sequence. + test_one({1, 2, 3, 4, 5, 6, 7}, 2, {3, 4, 5, 6, 7, 1, 2}); + + // Rotate around the middle. + test_one({1, 2, 3, 4, 5, 6, 7}, 3, {4, 5, 6, 7, 1, 2, 3}); + + // Rotate around the 1st element (no-op). + test_one({1, 2, 3, 4, 5, 6, 7}, 0, {1, 2, 3, 4, 5, 6, 7}); + + // Rotate around the 2nd element. + test_one({1, 2, 3, 4, 5, 6, 7}, 1, {2, 3, 4, 5, 6, 7, 1}); + + // Rotate around the last element. + test_one({1, 2, 3, 4, 5, 6, 7}, 6, {7, 1, 2, 3, 4, 5, 6}); + + // Pass `end()` as `mid` (no-op). + test_one({1, 2, 3, 4, 5, 6, 7}, 7, {1, 2, 3, 4, 5, 6, 7}); +} + +template +constexpr void test_iter() { + test_iter_sent(); + test_iter_sent>(); +} + +constexpr void test_iterators() { + test_iter>(); + test_iter>(); + test_iter>(); + test_iter>(); + test_iter(); +} + +constexpr bool test() { + test_iterators(); + + { // Complexity: at most `last - first` swaps. + const std::array input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; + auto expected = static_cast(input.size()); + + { + auto in = input; + int swaps = 0; + auto begin = adl::Iterator::TrackSwaps(in.data(), swaps); + auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps); + + for (size_t mid = 0; mid != input.size(); ++mid) { + std::ranges::rotate(begin, begin + mid, end); + assert(swaps <= expected); + } + } + + { + auto in = input; + int swaps = 0; + auto begin = adl::Iterator::TrackSwaps(in.data(), swaps); + auto end = adl::Iterator::TrackSwaps(in.data() + in.size(), swaps); + auto range = std::ranges::subrange(begin, end); + + for (size_t mid = 0; mid != input.size(); ++mid) { + std::ranges::rotate(range, begin + mid); + assert(swaps <= expected); + } + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp @@ -181,7 +181,7 @@ dangling_1st(std::ranges::remove, in, x); dangling_1st(std::ranges::remove_if, in, unary_pred); dangling_1st(std::ranges::reverse, in); - //dangling_1st(std::ranges::rotate, in, mid); + dangling_1st(std::ranges::rotate, in, mid); if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`. dangling_1st(std::ranges::shuffle, in, rand_gen()); dangling_1st(std::ranges::unique, in); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -147,7 +147,7 @@ test(std::ranges::remove, in, x); test(std::ranges::remove_if, in, unary_pred); test(std::ranges::reverse, in); - //test_mid(std::ranges::rotate, in, mid); + test_mid(std::ranges::rotate, in, mid); if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`. test(std::ranges::shuffle, in, rand_gen()); if (!std::is_constant_evaluated()) { @@ -156,18 +156,15 @@ } test(std::ranges::unique, in); test(std::ranges::partition, in, unary_pred); - // TODO(ranges): `stable_partition` requires `ranges::rotate` to be implemented. - //if (!std::is_constant_evaluated()) - // test(std::ranges::stable_partition, in, unary_pred); + if (!std::is_constant_evaluated()) + test(std::ranges::stable_partition, in, unary_pred); test(std::ranges::sort, in); - // TODO(ranges): `stable_sort` requires `ranges::rotate` to be implemented. - //if (!std::is_constant_evaluated()) - // test(std::ranges::stable_sort, in); + if (!std::is_constant_evaluated()) + test(std::ranges::stable_sort, in); test_mid(std::ranges::partial_sort, in, mid); test_mid(std::ranges::nth_element, in, mid); - // TODO(ranges): `inplace_merge` requires `ranges::rotate` to be implemented. - //if (!std::is_constant_evaluated()) - // test_mid(std::ranges::inplace_merge, in, mid); + if (!std::is_constant_evaluated()) + test_mid(std::ranges::inplace_merge, in, mid); test(std::ranges::make_heap, in); test(std::ranges::push_heap, in); test(std::ranges::pop_heap, in); diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -128,7 +128,7 @@ static_assert(test(std::ranges::replace_if, a, odd, 43)); static_assert(test(std::ranges::reverse, a)); static_assert(test(std::ranges::reverse_copy, a, a)); -//static_assert(test(std::ranges::rotate, a, a+5)); +static_assert(test(std::ranges::rotate, a, a+5)); static_assert(test(std::ranges::rotate_copy, a, a+5, a)); static_assert(test(std::ranges::sample, a, a, 5, g)); static_assert(test(std::ranges::search, a, a));