diff options
author | Hui Xie <hui.xie1990@gmail.com> | 2022-07-23 01:44:25 +0100 |
---|---|---|
committer | Tom Stellard <tstellar@redhat.com> | 2022-08-02 21:48:48 -0700 |
commit | 62f1e6638158d8848777a29d9d142bb5481c7b67 (patch) | |
tree | edcb0531ef2a04c1ad5f60d4cb276cc526738420 | |
parent | 6ba660d17410d02f5fa71d878ac49e2fdee4169f (diff) |
[libc++][ranges] implement `std::ranges::unique{_copy}`
implement `std::ranges::unique` and `std::ranges::unique_copy`
Differential Revision: https://reviews.llvm.org/D130404
(cherry picked from commit 72f57e3a30d597346feec74cf626796b0055680f)
19 files changed, 889 insertions, 174 deletions
diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv index 3ae87225c3eb..176ece9ae047 100644 --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -57,7 +57,7 @@ Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅ Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅ Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅ Write,sample,Not assigned,n/a,Not started -Write,unique_copy,Not assigned,n/a,Not started +Write,unique_copy,Hui Xie,`D130404 <https://llvm.org/D130404>`,✅ Write,partition_copy,Konstantin Varlamov,`D130070 <https://llvm.org/D130070>`_,✅ Write,partial_sort_copy,Konstantin Varlamov,n/a,In progress Merge,merge,Hui Xie,`D128611 <https://llvm.org/D128611>`_,✅ @@ -70,7 +70,7 @@ Permutation,remove_if,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅ Permutation,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅ Permutation,rotate,Nikolas Klauser,`D124122 <https://llvm.org/D124122>`_,Under review Permutation,shuffle,Konstantin Varlamov,`D130321 <https://llvm.org/D130321>`_,✅ -Permutation,unique,Not assigned,n/a,Not started +Permutation,unique,Hui Xie,`D130404 <https://llvm.org/D130404>`,✅ Permutation,partition,Konstantin Varlamov,`D129624 <https://llvm.org/D129624>`_,✅ Permutation,stable_partition,Konstantin Varlamov,`D129624 <https://llvm.org/D129624>`_,✅ Permutation,sort,Konstantin Varlamov,`D127557 <https://llvm.org/D127557>`_,✅ diff --git a/libcxx/include/__algorithm/adjacent_find.h b/libcxx/include/__algorithm/adjacent_find.h index 83d8c260f27a..1089bb20d5b2 100644 --- a/libcxx/include/__algorithm/adjacent_find.h +++ b/libcxx/include/__algorithm/adjacent_find.h @@ -11,8 +11,10 @@ #define _LIBCPP___ALGORITHM_ADJACENT_FIND_H #include <__algorithm/comp.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 @@ -20,25 +22,31 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template <class _Iter, class _Sent, class _BinaryPredicate> +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter +__adjacent_find(_Iter __first, _Sent __last, _BinaryPredicate&& __pred) { + if (__first == __last) + return __first; + _Iter __i = __first; + while (++__i != __last) { + if (__pred(*__first, *__i)) + return __first; + __first = __i; + } + return __i; +} + template <class _ForwardIterator, class _BinaryPredicate> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) { - if (__first != __last) { - _ForwardIterator __i = __first; - while (++__i != __last) { - if (__pred(*__first, *__i)) - return __first; - __first = __i; - } - } - return __last; + return std::__adjacent_find(std::move(__first), std::move(__last), __pred); } template <class _ForwardIterator> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator adjacent_find(_ForwardIterator __first, _ForwardIterator __last) { typedef typename iterator_traits<_ForwardIterator>::value_type __v; - return _VSTD::adjacent_find(__first, __last, __equal_to<__v>()); + return std::adjacent_find(std::move(__first), std::move(__last), __equal_to<__v>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h index 6ac5170b4a0e..e060574652d4 100644 --- a/libcxx/include/__algorithm/iterator_operations.h +++ b/libcxx/include/__algorithm/iterator_operations.h @@ -17,6 +17,7 @@ #include <__iterator/iter_swap.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> +#include <__iterator/readable_traits.h> #include <__utility/declval.h> #include <__utility/forward.h> #include <__utility/move.h> @@ -35,6 +36,10 @@ struct _RangeAlgPolicy {}; template <> struct _IterOps<_RangeAlgPolicy> { + + template <class _Iter> + using __value_type = iter_value_t<_Iter>; + static constexpr auto advance = ranges::advance; static constexpr auto distance = ranges::distance; static constexpr auto __iter_move = ranges::iter_move; @@ -50,6 +55,9 @@ struct _ClassicAlgPolicy {}; template <> struct _IterOps<_ClassicAlgPolicy> { + template <class _Iter> + using __value_type = typename iterator_traits<_Iter>::value_type; + // advance template <class _Iter, class _Distance> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 diff --git a/libcxx/include/__algorithm/ranges_unique.h b/libcxx/include/__algorithm/ranges_unique.h index bdf755e9406e..85185280724b 100644 --- a/libcxx/include/__algorithm/ranges_unique.h +++ b/libcxx/include/__algorithm/ranges_unique.h @@ -9,6 +9,7 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_UNIQUE_H #define _LIBCPP___ALGORITHM_RANGES_UNIQUE_H +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__algorithm/unique.h> #include <__config> @@ -37,28 +38,31 @@ _LIBCPP_BEGIN_NAMESPACE_STD namespace ranges { namespace __unique { -struct __fn { + struct __fn { + template < + permutable _Iter, + sentinel_for<_Iter> _Sent, + class _Proj = identity, + indirect_equivalence_relation<projected<_Iter, _Proj>> _Comp = ranges::equal_to> + _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter> + operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + auto __ret = std::__unique<_RangeAlgPolicy>( + std::move(__first), std::move(__last), ranges::__make_projected_comp(__comp, __proj)); + return {std::move(__ret.first), std::move(__ret.second)}; + } - template <permutable _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity, - indirect_equivalence_relation<projected<_Iter, _Proj>> _Comp = ranges::equal_to> - _LIBCPP_HIDE_FROM_ABI constexpr - subrange<_Iter> operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { - // TODO: implement - (void)__first; (void)__last; (void)__comp; (void)__proj; - return {}; - } - - template <forward_range _Range, class _Proj = identity, - indirect_equivalence_relation<projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to> - requires permutable<iterator_t<_Range>> - _LIBCPP_HIDE_FROM_ABI constexpr - borrowed_subrange_t<_Range> operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__comp; (void)__proj; - return {}; - } - -}; + template < + forward_range _Range, + class _Proj = identity, + indirect_equivalence_relation<projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to> + requires permutable<iterator_t<_Range>> + _LIBCPP_HIDE_FROM_ABI constexpr borrowed_subrange_t<_Range> + operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const { + auto __ret = std::__unique<_RangeAlgPolicy>( + ranges::begin(__range), ranges::end(__range), ranges::__make_projected_comp(__comp, __proj)); + return {std::move(__ret.first), std::move(__ret.second)}; + } + }; } // namespace __unique diff --git a/libcxx/include/__algorithm/ranges_unique_copy.h b/libcxx/include/__algorithm/ranges_unique_copy.h index 56361aa8ae2f..d047b444aa5e 100644 --- a/libcxx/include/__algorithm/ranges_unique_copy.h +++ b/libcxx/include/__algorithm/ranges_unique_copy.h @@ -10,6 +10,7 @@ #define _LIBCPP___ALGORITHM_RANGES_UNIQUE_COPY_H #include <__algorithm/in_out_result.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/make_projected.h> #include <__algorithm/unique_copy.h> #include <__concepts/same_as.h> @@ -19,8 +20,8 @@ #include <__functional/ranges_operations.h> #include <__iterator/concepts.h> #include <__iterator/iterator_traits.h> -#include <__iterator/readable_traits.h> #include <__iterator/projected.h> +#include <__iterator/readable_traits.h> #include <__ranges/access.h> #include <__ranges/concepts.h> #include <__ranges/dangling.h> @@ -42,42 +43,68 @@ using unique_copy_result = in_out_result<_InIter, _OutIter>; namespace __unique_copy { +template <class _InIter, class _OutIter> +concept __can_reread_from_output = (input_iterator<_OutIter> && same_as<iter_value_t<_InIter>, iter_value_t<_OutIter>>); + struct __fn { + template <class _InIter, class _OutIter> + static consteval auto __get_algo_tag() { + if constexpr (forward_iterator<_InIter>) { + return __unique_copy_tags::__reread_from_input_tag{}; + } else if constexpr (__can_reread_from_output<_InIter, _OutIter>) { + return __unique_copy_tags::__reread_from_output_tag{}; + } else if constexpr (indirectly_copyable_storable<_InIter, _OutIter>) { + return __unique_copy_tags::__read_from_tmp_value_tag{}; + } + } + + template <class _InIter, class _OutIter> + using __algo_tag_t = decltype(__get_algo_tag<_InIter, _OutIter>()); - template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter, class _Proj = identity, + template <input_iterator _InIter, + sentinel_for<_InIter> _Sent, + weakly_incrementable _OutIter, + class _Proj = identity, indirect_equivalence_relation<projected<_InIter, _Proj>> _Comp = ranges::equal_to> - requires indirectly_copyable<_InIter, _OutIter> && - (forward_iterator<_InIter> || - (input_iterator<_OutIter> && same_as<iter_value_t<_InIter>, iter_value_t<_OutIter>>) || - indirectly_copyable_storable<_InIter, _OutIter>) - _LIBCPP_HIDE_FROM_ABI constexpr - unique_copy_result<_InIter, _OutIter> + requires indirectly_copyable<_InIter, _OutIter> && + (forward_iterator<_InIter> || + (input_iterator<_OutIter> && same_as<iter_value_t<_InIter>, iter_value_t<_OutIter>>) || + indirectly_copyable_storable<_InIter, _OutIter>) + _LIBCPP_HIDE_FROM_ABI constexpr unique_copy_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result, _Comp __comp = {}, _Proj __proj = {}) const { - // TODO: implement - (void)__first; (void)__last; (void)__result; (void)__comp; (void)__proj; - return {}; + auto __ret = std::__unique_copy<_RangeAlgPolicy>( + std::move(__first), + std::move(__last), + std::move(__result), + __make_projected_comp(__comp, __proj), + __algo_tag_t<_InIter, _OutIter>()); + return {std::move(__ret.first), std::move(__ret.second)}; } - template <input_range _Range, weakly_incrementable _OutIter, class _Proj = identity, + template <input_range _Range, + weakly_incrementable _OutIter, + class _Proj = identity, indirect_equivalence_relation<projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to> - requires indirectly_copyable<iterator_t<_Range>, _OutIter> && - (forward_iterator<iterator_t<_Range>> || - (input_iterator<_OutIter> && same_as<range_value_t<_Range>, iter_value_t<_OutIter>>) || - indirectly_copyable_storable<iterator_t<_Range>, _OutIter>) - _LIBCPP_HIDE_FROM_ABI constexpr - unique_copy_result<borrowed_iterator_t<_Range>, _OutIter> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> && + (forward_iterator<iterator_t<_Range>> || + (input_iterator<_OutIter> && same_as<range_value_t<_Range>, iter_value_t<_OutIter>>) || + indirectly_copyable_storable<iterator_t<_Range>, _OutIter>) + _LIBCPP_HIDE_FROM_ABI constexpr unique_copy_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __range, _OutIter __result, _Comp __comp = {}, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__result; (void)__comp; (void)__proj; - return {}; + auto __ret = std::__unique_copy<_RangeAlgPolicy>( + ranges::begin(__range), + ranges::end(__range), + std::move(__result), + __make_projected_comp(__comp, __proj), + __algo_tag_t<iterator_t<_Range>, _OutIter>()); + return {std::move(__ret.first), std::move(__ret.second)}; } - }; } // namespace __unique_copy inline namespace __cpo { - inline constexpr auto unique_copy = __unique_copy::__fn{}; +inline constexpr auto unique_copy = __unique_copy::__fn{}; } // namespace __cpo } // namespace ranges diff --git a/libcxx/include/__algorithm/unique.h b/libcxx/include/__algorithm/unique.h index 264d727d93c8..1727225a91cd 100644 --- a/libcxx/include/__algorithm/unique.h +++ b/libcxx/include/__algorithm/unique.h @@ -11,9 +11,11 @@ #include <__algorithm/adjacent_find.h> #include <__algorithm/comp.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/iterator_traits.h> #include <__utility/move.h> +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -23,32 +25,34 @@ _LIBCPP_BEGIN_NAMESPACE_STD // unique +template <class _AlgPolicy, class _Iter, class _Sent, class _BinaryPredicate> +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 std::pair<_Iter, _Iter> +__unique(_Iter __first, _Sent __last, _BinaryPredicate&& __pred) { + __first = std::__adjacent_find(__first, __last, __pred); + if (__first != __last) { + // ... a a ? ... + // f i + _Iter __i = __first; + for (++__i; ++__i != __last;) + if (!__pred(*__first, *__i)) + *++__first = _IterOps<_AlgPolicy>::__iter_move(__i); + ++__first; + return std::pair<_Iter, _Iter>(std::move(__first), std::move(__i)); + } + return std::pair<_Iter, _Iter>(__first, __first); +} + template <class _ForwardIterator, class _BinaryPredicate> -_LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) -{ - __first = _VSTD::adjacent_find<_ForwardIterator, _BinaryPredicate&>(__first, __last, __pred); - if (__first != __last) - { - // ... a a ? ... - // f i - _ForwardIterator __i = __first; - for (++__i; ++__i != __last;) - if (!__pred(*__first, *__i)) - *++__first = _VSTD::move(*__i); - ++__first; - } - return __first; +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) { + return std::__unique<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __pred).first; } template <class _ForwardIterator> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator -unique(_ForwardIterator __first, _ForwardIterator __last) -{ - typedef typename iterator_traits<_ForwardIterator>::value_type __v; - return _VSTD::unique(__first, __last, __equal_to<__v>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +unique(_ForwardIterator __first, _ForwardIterator __last) { + typedef typename iterator_traits<_ForwardIterator>::value_type __v; + return std::unique(__first, __last, __equal_to<__v>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/unique_copy.h b/libcxx/include/__algorithm/unique_copy.h index f58517749f51..c7c8d8e9d8fd 100644 --- a/libcxx/include/__algorithm/unique_copy.h +++ b/libcxx/include/__algorithm/unique_copy.h @@ -10,8 +10,14 @@ #define _LIBCPP___ALGORITHM_UNIQUE_COPY_H #include <__algorithm/comp.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__type_traits/conditional.h> +#include <__type_traits/is_base_of.h> +#include <__type_traits/is_same.h> +#include <__utility/move.h> +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -19,88 +25,99 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _BinaryPredicate, class _InputIterator, class _OutputIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -__unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred, - input_iterator_tag, output_iterator_tag) -{ - if (__first != __last) - { - typename iterator_traits<_InputIterator>::value_type __t(*__first); +namespace __unique_copy_tags { + +struct __reread_from_input_tag {}; +struct __reread_from_output_tag {}; +struct __read_from_tmp_value_tag {}; + +} // namespace __unique_copy_tags + +template <class _AlgPolicy, class _BinaryPredicate, class _InputIterator, class _Sent, class _OutputIterator> +_LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _OutputIterator> +__unique_copy(_InputIterator __first, + _Sent __last, + _OutputIterator __result, + _BinaryPredicate&& __pred, + __unique_copy_tags::__read_from_tmp_value_tag) { + if (__first != __last) { + typename _IterOps<_AlgPolicy>::template __value_type<_InputIterator> __t(*__first); + *__result = __t; + ++__result; + while (++__first != __last) { + if (!__pred(__t, *__first)) { + __t = *__first; *__result = __t; ++__result; - while (++__first != __last) - { - if (!__pred(__t, *__first)) - { - __t = *__first; - *__result = __t; - ++__result; - } - } + } } - return __result; + } + return pair<_InputIterator, _OutputIterator>(std::move(__first), std::move(__result)); } -template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -__unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred, - forward_iterator_tag, output_iterator_tag) -{ - if (__first != __last) - { - _ForwardIterator __i = __first; - *__result = *__i; +template <class _AlgPolicy, class _BinaryPredicate, class _ForwardIterator, class _Sent, class _OutputIterator> +_LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI pair<_ForwardIterator, _OutputIterator> +__unique_copy(_ForwardIterator __first, + _Sent __last, + _OutputIterator __result, + _BinaryPredicate&& __pred, + __unique_copy_tags::__reread_from_input_tag) { + if (__first != __last) { + _ForwardIterator __i = __first; + *__result = *__i; + ++__result; + while (++__first != __last) { + if (!__pred(*__i, *__first)) { + *__result = *__first; ++__result; - while (++__first != __last) - { - if (!__pred(*__i, *__first)) - { - *__result = *__first; - ++__result; - __i = __first; - } - } + __i = __first; + } } - return __result; + } + return pair<_ForwardIterator, _OutputIterator>(std::move(__first), std::move(__result)); } -template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred, - input_iterator_tag, forward_iterator_tag) -{ - if (__first != __last) - { - *__result = *__first; - while (++__first != __last) - if (!__pred(*__result, *__first)) - *++__result = *__first; - ++__result; - } - return __result; +template <class _AlgPolicy, class _BinaryPredicate, class _InputIterator, class _Sent, class _InputAndOutputIterator> +_LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _InputAndOutputIterator> +__unique_copy(_InputIterator __first, + _Sent __last, + _InputAndOutputIterator __result, + _BinaryPredicate&& __pred, + __unique_copy_tags::__reread_from_output_tag) { + if (__first != __last) { + *__result = *__first; + while (++__first != __last) + if (!__pred(*__result, *__first)) + *++__result = *__first; + ++__result; + } + return pair<_InputIterator, _InputAndOutputIterator>(std::move(__first), std::move(__result)); } template <class _InputIterator, class _OutputIterator, class _BinaryPredicate> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred) -{ - return _VSTD::__unique_copy<_BinaryPredicate&>(__first, __last, __result, __pred, - typename iterator_traits<_InputIterator>::iterator_category(), - typename iterator_traits<_OutputIterator>::iterator_category()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator +unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred) { + using __algo_tag = typename conditional< + is_base_of<forward_iterator_tag, typename iterator_traits<_InputIterator>::iterator_category>::value, + __unique_copy_tags::__reread_from_input_tag, + typename conditional< + is_base_of<forward_iterator_tag, typename iterator_traits<_OutputIterator>::iterator_category>::value && + is_same< typename iterator_traits<_InputIterator>::value_type, + typename iterator_traits<_OutputIterator>::value_type>::value, + __unique_copy_tags::__reread_from_output_tag, + __unique_copy_tags::__read_from_tmp_value_tag>::type >::type; + return std::__unique_copy<_ClassicAlgPolicy>( + std::move(__first), std::move(__last), std::move(__result), __pred, __algo_tag()) + .second; } template <class _InputIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - typedef typename iterator_traits<_InputIterator>::value_type __v; - return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator +unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { + typedef typename iterator_traits<_InputIterator>::value_type __v; + return std::unique_copy(std::move(__first), std::move(__last), std::move(__result), __equal_to<__v>()); } - _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ALGORITHM_UNIQUE_COPY_H diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 4fc353a8ce5d..7b510b5096af 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -865,6 +865,34 @@ namespace ranges { borrowed_iterator_t<R> inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {}); // Since C++20 + + template<permutable I, sentinel_for<I> S, class Proj = identity, + indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to> + constexpr subrange<I> unique(I first, S last, C comp = {}, Proj proj = {}); // Since C++20 + + template<forward_range R, class Proj = identity, + indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to> + requires permutable<iterator_t<R>> + constexpr borrowed_subrange_t<R> + unique(R&& r, C comp = {}, Proj proj = {}); // Since C++20 + + template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity, + indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to> + requires indirectly_copyable<I, O> && + (forward_iterator<I> || + (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) || + indirectly_copyable_storable<I, O>) + constexpr unique_copy_result<I, O> + unique_copy(I first, S last, O result, C comp = {}, Proj proj = {}); // Since C++20 + + template<input_range R, weakly_incrementable O, class Proj = identity, + indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to> + requires indirectly_copyable<iterator_t<R>, O> && + (forward_iterator<iterator_t<R>> || + (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) || + indirectly_copyable_storable<iterator_t<R>, O>) + constexpr unique_copy_result<borrowed_iterator_t<R>, O> + unique_copy(R&& r, O result, C comp = {}, Proj proj = {}); // Since C++20 } constexpr bool // constexpr in C++20 @@ -1665,6 +1693,8 @@ template <class BidirectionalIterator, class Compare> #include <__algorithm/ranges_stable_sort.h> #include <__algorithm/ranges_swap_ranges.h> #include <__algorithm/ranges_transform.h> +#include <__algorithm/ranges_unique.h> +#include <__algorithm/ranges_unique_copy.h> #include <__algorithm/ranges_upper_bound.h> #include <__algorithm/remove.h> #include <__algorithm/remove_copy.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 index 669fa9c1842e..b4328006539f 100644 --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -222,10 +222,10 @@ constexpr bool all_the_algorithms() (void)std::ranges::transform(a, first2, UnaryTransform(&copies)); assert(copies == 0); (void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(&copies)); assert(copies == 0); (void)std::ranges::transform(a, b, first2, BinaryTransform(&copies)); assert(copies == 0); - //(void)std::ranges::unique(first, last, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::unique(a, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::unique_copy(first, last, first2, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::unique_copy(a, first2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::unique(first, last, Equal(&copies)); assert(copies == 0); + (void)std::ranges::unique(a, Equal(&copies)); assert(copies == 0); + (void)std::ranges::unique_copy(first, last, first2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::unique_copy(a, first2, Equal(&copies)); assert(copies == 0); (void)std::ranges::upper_bound(first, last, value, Less(&copies)); assert(copies == 0); (void)std::ranges::upper_bound(a, value, Less(&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 index 22fdf09888af..4eadbcc97a65 100644 --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -213,10 +213,10 @@ constexpr bool all_the_algorithms() (void)std::ranges::transform(a, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0); (void)std::ranges::transform(first, mid, mid, last, first2, BinaryTransform(), Proj(&copies), Proj(&copies)); assert(copies == 0); (void)std::ranges::transform(a, b, first2, BinaryTransform(), Proj(&copies), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::unique(first, last, Equal(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::unique(a, Equal(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::unique_copy(first, last, first2, Equal(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::unique_copy(a, first2, Equal(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::unique(first, last, Equal(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::unique(a, Equal(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::unique_copy(first, last, first2, Equal(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::unique_copy(a, first2, Equal(), Proj(&copies)); assert(copies == 0); (void)std::ranges::upper_bound(first, last, value, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::upper_bound(a, value, Less(), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique.pass.cpp index 216ae6a1b98e..bb60109e7735 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique.pass.cpp @@ -28,14 +28,214 @@ #include <ranges> #include "almost_satisfies_types.h" +#include "counting_predicates.h" +#include "counting_projection.h" #include "test_iterators.h" -// TODO: SFINAE tests. +template <class Iter = int*, class Sent = int*, class Comp = std::ranges::equal_to, class Proj = std::identity> +concept HasUniqueIter = + requires(Iter&& iter, Sent&& sent, Comp&& comp, Proj&& proj) { + std::ranges::unique( + std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Comp>(comp), std::forward<Proj>(proj)); + }; + +static_assert(HasUniqueIter<int*, int*>); + +// !permutable<I> +static_assert(!HasUniqueIter<PermutableNotForwardIterator>); +static_assert(!HasUniqueIter<PermutableNotSwappable>); + +// !sentinel_for<S, I> +static_assert(!HasUniqueIter<int*, SentinelForNotSemiregular>); + +// !indirect_equivalence_relation<Comp, projected<I, Proj>> +static_assert(!HasUniqueIter<int*, int*, ComparatorNotCopyable<int>>); + +template <class Range, class Comp = std::ranges::equal_to, class Proj = std::identity> +concept HasUniqueRange = + requires(Range&& range, Comp&& comp, Proj&& proj) { + std::ranges::unique(std::forward<Range>(range), std::forward<Comp>(comp), std::forward<Proj>(proj)); + }; + +template <class T> +using R = UncheckedRange<T>; + +static_assert(HasUniqueRange<R<int*>>); + +// !forward_range<R> +static_assert(!HasUniqueRange<ForwardRangeNotDerivedFrom>); +static_assert(!HasUniqueRange<ForwardRangeNotIncrementable>); + +// permutable<ranges::iterator_t<R>> +static_assert(!HasUniqueRange<R<PermutableNotForwardIterator>>); +static_assert(!HasUniqueRange<R<PermutableNotSwappable>>); + +// !indirect_equivalence_relation<Comp, projected<ranges::iterator_t<R>, Proj>> +static_assert(!HasUniqueRange<R<int*>, ComparatorNotCopyable<int>>); + +template <class Iter, template <class> class SentWrapper, std::size_t N1, std::size_t N2> +constexpr void testUniqueImpl(std::array<int, N1> input, std::array<int, N2> expected) { + using Sent = SentWrapper<Iter>; + + // iterator overload + { + auto in = input; + std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = + std::ranges::unique(Iter{in.data()}, Sent{Iter{in.data() + in.size()}}); + assert(std::ranges::equal(std::ranges::subrange<Iter>{Iter{in.data()}, result.begin()}, expected)); + assert(base(result.end()) == in.data() + in.size()); + } + + // range overload + { + auto in = input; + std::ranges::subrange r{Iter{in.data()}, Sent{Iter{in.data() + in.size()}}}; + std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::unique(r); + assert(std::ranges::equal(std::ranges::subrange<Iter>{Iter{in.data()}, result.begin()}, expected)); + assert(base(result.end()) == in.data() + in.size()); + } +} + +template <class Iter, template <class> class SentWrapper> +constexpr void testImpl() { + // no consecutive elements + { + std::array in{1, 2, 3, 2, 1}; + std::array expected{1, 2, 3, 2, 1}; + testUniqueImpl<Iter, SentWrapper>(in, expected); + } + + // one group of consecutive elements + { + std::array in{2, 3, 3, 3, 4, 3}; + std::array expected{2, 3, 4, 3}; + testUniqueImpl<Iter, SentWrapper>(in, expected); + } + + // multiple groups of consecutive elements + { + std::array in{2, 3, 3, 3, 4, 3, 3, 5, 5, 5}; + std::array expected{2, 3, 4, 3, 5}; + testUniqueImpl<Iter, SentWrapper>(in, expected); + } + + // all the same + { + std::array in{1, 1, 1, 1, 1, 1}; + std::array expected{1}; + testUniqueImpl<Iter, SentWrapper>(in, expected); + } + + // empty range + { + std::array<int, 0> in{}; + std::array<int, 0> expected{}; + testUniqueImpl<Iter, SentWrapper>(in, expected); + } + + // single element range + std::array in{1}; + std::array expected{1}; + testUniqueImpl<Iter, SentWrapper>(in, expected); +} + +template <template <class> class SentWrapper> +constexpr void withAllPermutationsOfIter() { + testImpl<forward_iterator<int*>, SentWrapper>(); + testImpl<bidirectional_iterator<int*>, SentWrapper>(); + testImpl<random_access_iterator<int*>, SentWrapper>(); + testImpl<contiguous_iterator<int*>, SentWrapper>(); + testImpl<int*, SentWrapper>(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + withAllPermutationsOfIter<std::type_identity_t>(); + withAllPermutationsOfIter<sentinel_wrapper>(); + + struct Data { + int data; + }; + + // Test custom comparator + { + std::array input{Data{4}, Data{8}, Data{8}, Data{8}}; + std::array expected{Data{4}, Data{8}}; + const auto comp = [](const Data& x, const Data& y) { return x.data == y.data; }; + + // iterator overload + { + auto in = input; + auto result = std::ranges::unique(in.begin(), in.end(), comp); + assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), comp)); + assert(base(result.end()) == in.end()); + } + + // range overload + { + auto in = input; + auto result = std::ranges::unique(in, comp); + assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), comp)); + assert(base(result.end()) == in.end()); + } + } + + // Test custom projection + { + std::array input{Data{4}, Data{8}, Data{8}, Data{8}}; + std::array expected{Data{4}, Data{8}}; + + const auto proj = &Data::data; + + // iterator overload + { + auto in = input; + auto result = std::ranges::unique(in.begin(), in.end(), {}, proj); + assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), {}, proj, proj)); + assert(base(result.end()) == in.end()); + } + + // range overload + { + auto in = input; + auto result = std::ranges::unique(in, {}, proj); + assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), {}, proj, proj)); + assert(base(result.end()) == in.end()); + } + } + + // Complexity: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate + // and no more than twice as many applications of any projection. + { + std::array input{1, 2, 3, 3, 3, 4, 3, 3, 5, 5, 6, 6, 1}; + std::array expected{1, 2, 3, 4, 3, 5, 6, 1}; + // iterator overload + { + auto in = input; + int numberOfComp = 0; + int numberOfProj = 0; + auto result = std::ranges::unique( + in.begin(), + in.end(), + counting_predicate{std::ranges::equal_to{}, numberOfComp}, + counting_projection{numberOfProj}); + assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end())); + assert(base(result.end()) == in.end()); + assert(numberOfComp == in.size() - 1); + assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1))); + } + // range overload + { + auto in = input; + int numberOfComp = 0; + int numberOfProj = 0; + auto result = std::ranges::unique( + in, counting_predicate{std::ranges::equal_to{}, numberOfComp}, counting_projection{numberOfProj}); + assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end())); + assert(base(result.end()) == in.end()); + assert(numberOfComp == in.size() - 1); + assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1))); + } + } return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique_copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique_copy.pass.cpp index 8ccff619b811..ac7965c8eb2c 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique_copy.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique_copy.pass.cpp @@ -36,15 +36,409 @@ #include <ranges> #include "almost_satisfies_types.h" +#include "counting_predicates.h" +#include "counting_projection.h" +#include "MoveOnly.h" #include "test_iterators.h" -// TODO: SFINAE tests. +template < + class InIter = int*, + class Sent = int*, + class OutIter = int*, + class Comp = std::ranges::equal_to, + class Proj = std::identity> +concept HasUniqueCopyIter = + requires(InIter&& in, Sent&& sent, OutIter&& out, Comp&& comp, Proj&& proj) { + std::ranges::unique_copy( + std::forward<InIter>(in), + std::forward<Sent>(sent), + std::forward<OutIter>(out), + std::forward<Comp>(comp), + std::forward<Proj>(proj)); + }; + +static_assert(HasUniqueCopyIter<int*, int*, int*>); + +// !input_iterator<I> +static_assert(!HasUniqueCopyIter<InputIteratorNotDerivedFrom, sentinel_wrapper<InputIteratorNotDerivedFrom>>); + +// !sentinel_for<S, I> +static_assert(!HasUniqueCopyIter<int*, SentinelForNotSemiregular>); + +// !weakly_incrementable<O> +static_assert(!HasUniqueCopyIter<int*, int*, WeaklyIncrementableNotMovable>); + +// !indirect_equivalence_relation<Comp, projected<I, Proj>> +static_assert(!HasUniqueCopyIter<int*, int*, int*, ComparatorNotCopyable<int>>); + +// !indirectly_copyable<I, O> +static_assert(!HasUniqueCopyIter<const int*, const int*, const int*>); + +// forward_iterator<I> +// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) +// !indirectly_copyable_storable<I, O> +struct AssignableFromMoveOnly { + int data; + constexpr AssignableFromMoveOnly& operator=(MoveOnly const& m) { + data = m.get(); + return *this; + } +}; +static_assert(HasUniqueCopyIter<MoveOnly*, MoveOnly*, AssignableFromMoveOnly*>); +// because: +static_assert(std::forward_iterator<MoveOnly*>); +static_assert(!std::same_as<std::iter_value_t<MoveOnly*>, std::iter_value_t<AssignableFromMoveOnly*>>); +static_assert(!std::indirectly_copyable_storable<MoveOnly*, AssignableFromMoveOnly*>); + +// !forward_iterator<I> +// (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) +// !indirectly_copyable_storable<I, O> +struct CopyAssignableNotCopyConstructible { + int data; + constexpr CopyAssignableNotCopyConstructible(int i = 0) : data(i) {} + CopyAssignableNotCopyConstructible(const CopyAssignableNotCopyConstructible&) = delete; + CopyAssignableNotCopyConstructible& operator=(const CopyAssignableNotCopyConstructible&) = default; + friend constexpr bool + operator==(CopyAssignableNotCopyConstructible const&, CopyAssignableNotCopyConstructible const&) = default; +}; + +using InputAndOutputIterator = cpp17_input_iterator<CopyAssignableNotCopyConstructible*>; +static_assert(std::input_iterator<InputAndOutputIterator>); +static_assert(std::output_iterator<InputAndOutputIterator, CopyAssignableNotCopyConstructible>); + +static_assert( + HasUniqueCopyIter< + cpp20_input_iterator<CopyAssignableNotCopyConstructible*>, + sentinel_wrapper<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>, + InputAndOutputIterator>); +// because: +static_assert(!std::forward_iterator< cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>); +static_assert( + std::input_iterator<InputAndOutputIterator> && + std::same_as<std::iter_value_t<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>, + std::iter_value_t<InputAndOutputIterator>>); +static_assert( + !std::indirectly_copyable_storable< + cpp20_input_iterator<CopyAssignableNotCopyConstructible*>, + InputAndOutputIterator>); + +// !forward_iterator<I> +// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) +// indirectly_copyable_storable<I, O> +static_assert( + HasUniqueCopyIter< + cpp20_input_iterator<int*>, + sentinel_wrapper<cpp20_input_iterator<int*>>, + cpp20_output_iterator<int*>>); +// because: +static_assert(!std::forward_iterator<cpp20_input_iterator<int*>>); +static_assert(!std::input_iterator<cpp20_output_iterator<int*>>); +static_assert(std::indirectly_copyable_storable<cpp20_input_iterator<int*>, cpp20_output_iterator<int*>>); + +// !forward_iterator<I> +// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) +// !indirectly_copyable_storable<I, O> +static_assert( + !HasUniqueCopyIter< + cpp20_input_iterator<MoveOnly*>, + sentinel_wrapper<cpp20_input_iterator<MoveOnly*>>, + cpp20_output_iterator<AssignableFromMoveOnly*>>); +// because: +static_assert(!std::forward_iterator<cpp20_input_iterator<MoveOnly*>>); +static_assert(!std::input_iterator<cpp20_output_iterator<MoveOnly*>>); +static_assert( + !std:: + indirectly_copyable_storable<cpp20_input_iterator<MoveOnly*>, cpp20_output_iterator<AssignableFromMoveOnly*>>); + +template < class Range, class OutIter = int*, class Comp = std::ranges::equal_to, class Proj = std::identity> +concept HasUniqueCopyRange = + requires(Range&& range, OutIter&& out, Comp&& comp, Proj&& proj) { + std::ranges::unique_copy( + std::forward<Range>(range), std::forward<OutIter>(out), std::forward<Comp>(comp), std::forward<Proj>(proj)); + }; + +template <class T> +using R = UncheckedRange<T>; + +static_assert(HasUniqueCopyRange<R<int*>, int*>); + +// !input_range<R> +static_assert(!HasUniqueCopyRange<R<InputIteratorNotDerivedFrom>>); + +// !weakly_incrementable<O> +static_assert(!HasUniqueCopyIter<R<int*>, WeaklyIncrementableNotMovable>); + +// !indirect_equivalence_relation<Comp, projected<I, Proj>> +static_assert(!HasUniqueCopyIter<R<int*>, int*, ComparatorNotCopyable<int>>); + +// !indirectly_copyable<I, O> +static_assert(!HasUniqueCopyIter<R<const int*>, const int*>); + +// !forward_iterator<iterator_t<R>> +// !(input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) +// !indirectly_copyable_storable<iterator_t<R>, O> +static_assert(!HasUniqueCopyIter< R<cpp20_input_iterator<MoveOnly*>>, cpp20_output_iterator<AssignableFromMoveOnly*>>); + +template <class InIter, class OutIter, template <class> class SentWrapper, std::size_t N1, std::size_t N2> +constexpr void testUniqueCopyImpl(std::array<int, N1> in, std::array<int, N2> expected) { + using Sent = SentWrapper<InIter>; + + // iterator overload + { + std::array<int, N2> out; + std::same_as<std::ranges::unique_copy_result<InIter, OutIter>> decltype(auto) result = + std::ranges::unique_copy(InIter{in.data()}, Sent{InIter{in.data() + in.size()}}, OutIter{out.begin()}); + assert(std::ranges::equal(out, expected)); + assert(base(result.in) == in.data() + in.size()); + assert(base(result.out) == out.data() + out.size()); + } + + // range overload + { + std::array<int, N2> out; + std::ranges::subrange r{InIter{in.data()}, Sent{InIter{in.data() + in.size()}}}; + std::same_as<std::ranges::unique_copy_result<InIter, OutIter>> decltype(auto) result = + std::ranges::unique_copy(r, OutIter{out.begin()}); + assert(std::ranges::equal(out, expected)); + assert(base(result.in) == in.data() + in.size()); + assert(base(result.out) == out.data() + out.size()); + } +} + +template <class InIter, class OutIter, template <class> class SentWrapper> +constexpr void testImpl() { + // no consecutive elements + { + std::array in{1, 2, 3, 2, 1}; + std::array expected{1, 2, 3, 2, 1}; + testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected); + } + + // one group of consecutive elements + { + std::array in{2, 3, 3, 3, 4, 3}; + std::array expected{2, 3, 4, 3}; + testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected); + } + + // multiple groups of consecutive elements + { + std::array in{2, 3, 3, 3, 4, 3, 3, 5, 5, 5}; + std::array expected{2, 3, 4, 3, 5}; + testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected); + } + + // all the same + { + std::array in{1, 1, 1, 1, 1, 1}; + std::array expected{1}; + testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected); + } + + // empty range + { + std::array<int, 0> in{}; + std::array<int, 0> expected{}; + testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected); + } +} + +template <class OutIter, template <class> class SentWrapper> +constexpr void withAllPermutationsOfInIter() { + testImpl<cpp20_input_iterator<int*>, OutIter, sentinel_wrapper>(); + testImpl<forward_iterator<int*>, OutIter, SentWrapper>(); + testImpl<bidirectional_iterator<int*>, OutIter, SentWrapper>(); + testImpl<random_access_iterator<int*>, OutIter, SentWrapper>(); + testImpl<contiguous_iterator<int*>, OutIter, SentWrapper>(); + testImpl<int*, OutIter, SentWrapper>(); +} + +template <template <class> class SentWrapper> +constexpr void withAllPermutationsOfInIterAndOutIter() { + withAllPermutationsOfInIter<cpp20_output_iterator<int*>, SentWrapper>(); + withAllPermutationsOfInIter<forward_iterator<int*>, SentWrapper>(); + withAllPermutationsOfInIter<bidirectional_iterator<int*>, SentWrapper>(); + withAllPermutationsOfInIter<random_access_iterator<int*>, SentWrapper>(); + withAllPermutationsOfInIter<contiguous_iterator<int*>, SentWrapper>(); + withAllPermutationsOfInIter<int*, SentWrapper>(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + withAllPermutationsOfInIterAndOutIter<std::type_identity_t>(); + withAllPermutationsOfInIterAndOutIter<sentinel_wrapper>(); + + // Test the overload that re-reads from the input iterator + // forward_iterator<I> + // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) + // !indirectly_copyable_storable<I, O> + { + MoveOnly in[5] = {1, 3, 3, 3, 1}; + // iterator overload + { + AssignableFromMoveOnly out[3] = {}; + auto result = std::ranges::unique_copy(in, in + 5, out); + assert(std::ranges::equal(out, std::array{1, 3, 1}, {}, &AssignableFromMoveOnly::data)); + assert(result.in == in + 5); + assert(result.out == out + 3); + } + // range overload + { + AssignableFromMoveOnly out[3] = {}; + auto result = std::ranges::unique_copy(std::ranges::subrange{in, in + 5}, out); + assert(std::ranges::equal(out, std::array{1, 3, 1}, {}, &AssignableFromMoveOnly::data)); + assert(result.in == in + 5); + assert(result.out == out + 3); + } + } + + // Test the overload that re-reads from the output iterator + // !forward_iterator<I> + // (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) + // !indirectly_copyable_storable<I, O> + { + using InIter = cpp20_input_iterator<CopyAssignableNotCopyConstructible*>; + using Sent = sentinel_wrapper<InIter>; + CopyAssignableNotCopyConstructible in[6] = {1, 1, 2, 2, 3, 3}; + // iterator overload + { + CopyAssignableNotCopyConstructible out[3]; + auto result = std::ranges::unique_copy(InIter{in}, Sent{InIter{in + 6}}, InputAndOutputIterator{out}); + assert(std::ranges::equal(out, std::array{1, 2, 3}, {}, &CopyAssignableNotCopyConstructible::data)); + assert(base(result.in) == in + 6); + assert(base(result.out) == out + 3); + } + // range overload + { + CopyAssignableNotCopyConstructible out[3]; + auto r = std::ranges::subrange(InIter{in}, Sent{InIter{in + 6}}); + auto result = std::ranges::unique_copy(r, InputAndOutputIterator{out}); + assert(std::ranges::equal(out, std::array{1, 2, 3}, {}, &CopyAssignableNotCopyConstructible::data)); + assert(base(result.in) == in + 6); + assert(base(result.out) == out + 3); + } + } + + // Test the overload that reads from the temporary copy of the value + // !forward_iterator<I> + // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) + // indirectly_copyable_storable<I, O> + { + using InIter = cpp20_input_iterator<int*>; + using Sent = sentinel_wrapper<InIter>; + int in[4] = {1, 1, 1, 2}; + // iterator overload + { + int out[2]; + auto result = std::ranges::unique_copy(InIter{in}, Sent{InIter{in + 4}}, cpp20_output_iterator<int*>{out}); + assert(std::ranges::equal(out, std::array{1, 2})); + assert(base(result.in) == in + 4); + assert(base(result.out) == out + 2); + } + // range overload + { + int out[2]; + auto r = std::ranges::subrange(InIter{in}, Sent{InIter{in + 4}}); + auto result = std::ranges::unique_copy(r, cpp20_output_iterator<int*>{out}); + assert(std::ranges::equal(out, std::array{1, 2})); + assert(base(result.in) == in + 4); + assert(base(result.out) == out + 2); + } + } + + struct Data { + int data; + }; + + // Test custom comparator + { + std::array in{Data{4}, Data{8}, Data{8}, Data{8}}; + std::array expected{Data{4}, Data{8}}; + const auto comp = [](const Data& x, const Data& y) { return x.data == y.data; }; + + // iterator overload + { + std::array<Data, 2> out; + auto result = std::ranges::unique_copy(in.begin(), in.end(), out.begin(), comp); + assert(std::ranges::equal(out, expected, comp)); + assert(base(result.in) == in.begin() + 4); + assert(base(result.out) == out.begin() + 2); + } + + // range overload + { + std::array<Data, 2> out; + auto result = std::ranges::unique_copy(in, out.begin(), comp); + assert(std::ranges::equal(out, expected, comp)); + assert(base(result.in) == in.begin() + 4); + assert(base(result.out) == out.begin() + 2); + } + } + + // Test custom projection + { + std::array in{Data{4}, Data{8}, Data{8}, Data{8}}; + std::array expected{Data{4}, Data{8}}; + + const auto proj = &Data::data; + + // iterator overload + { + std::array<Data, 2> out; + auto result = std::ranges::unique_copy(in.begin(), in.end(), out.begin(), {}, proj); + assert(std::ranges::equal(out, expected, {}, proj, proj)); + assert(base(result.in) == in.begin() + 4); + assert(base(result.out) == out.begin() + 2); + } + + // range overload + { + std::array<Data, 2> out; + auto result = std::ranges::unique_copy(in, out.begin(), {}, proj); + assert(std::ranges::equal(out, expected, {}, proj, proj)); + assert(base(result.in) == in.begin() + 4); + assert(base(result.out) == out.begin() + 2); + } + } + // Exactly last - first - 1 applications of the corresponding predicate and no + // more than twice as many applications of any projection. + { + std::array in{1, 2, 3, 3, 3, 4, 3, 3, 5, 5, 6, 6, 1}; + std::array expected{1, 2, 3, 4, 3, 5, 6, 1}; + // iterator overload + { + std::array<int, 8> out; + int numberOfComp = 0; + int numberOfProj = 0; + auto result = std::ranges::unique_copy( + in.begin(), + in.end(), + out.begin(), + counting_predicate{std::ranges::equal_to{}, numberOfComp}, + counting_projection{numberOfProj}); + assert(std::ranges::equal(out, expected)); + assert(base(result.in) == in.end()); + assert(base(result.out) == out.end()); + assert(numberOfComp == in.size() - 1); + assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1))); + } + // range overload + { + std::array<int, 8> out; + int numberOfComp = 0; + int numberOfProj = 0; + auto result = std::ranges::unique_copy( + in, + out.begin(), + counting_predicate{std::ranges::equal_to{}, numberOfComp}, + counting_projection{numberOfProj}); + assert(std::ranges::equal(out, expected)); + assert(base(result.in) == in.end()); + assert(base(result.out) == out.end()); + assert(numberOfComp == in.size() - 1); + assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1))); + } + } return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/unique_copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/unique_copy.pass.cpp index bda304cd7493..bcf9c99e24c2 100644 --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/unique_copy.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/unique_copy.pass.cpp @@ -19,9 +19,21 @@ #include <algorithm> #include <cassert> +#include "MoveOnly.h" #include "test_macros.h" #include "test_iterators.h" +struct AssignableFromMoveOnly { + AssignableFromMoveOnly(int i) : data(i) {} + AssignableFromMoveOnly() : data(0) {} + int data; + AssignableFromMoveOnly& operator=(MoveOnly const& m) { + data = m.get(); + return *this; + } + bool operator==(AssignableFromMoveOnly const& rhs) const { return data == rhs.data; } +}; + #if TEST_STD_VER > 17 TEST_CONSTEXPR bool test_constexpr() { int ia[] = {0, 1, 2, 2, 4}; @@ -107,6 +119,7 @@ test() int main(int, char**) { + test<cpp17_input_iterator<const int*>, cpp17_input_iterator<int*> >(); test<cpp17_input_iterator<const int*>, cpp17_output_iterator<int*> >(); test<cpp17_input_iterator<const int*>, forward_iterator<int*> >(); test<cpp17_input_iterator<const int*>, bidirectional_iterator<int*> >(); @@ -137,6 +150,16 @@ int main(int, char**) test<const int*, random_access_iterator<int*> >(); test<const int*, int*>(); + // Move only inputs + { + MoveOnly in[5] = {1, 3, 3, 3, 1}; + AssignableFromMoveOnly out[3] = {}; + auto result = std::unique_copy(in, in + 5, out); + AssignableFromMoveOnly expected[3] = {1, 3, 1}; + assert(std::equal(out, out + 3, expected)); + assert(result == out + 3); + } + #if TEST_STD_VER > 17 static_assert(test_constexpr()); #endif diff --git a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp index a694376ca6ec..875ca35b1265 100644 --- a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp @@ -43,7 +43,7 @@ static_assert(std::is_same_v<in_out_result<int, long>, uninitialized_copy_result static_assert(std::is_same_v<in_out_result<int, long>, uninitialized_copy_n_result<int, long>>); static_assert(std::is_same_v<in_out_result<int, long>, uninitialized_move_result<int, long>>); static_assert(std::is_same_v<in_out_result<int, long>, uninitialized_move_n_result<int, long>>); -// static_assert(std::is_same_v<in_out_result<int, long>, unique_copy_result<int, long>>); +static_assert(std::is_same_v<in_out_result<int, long>, unique_copy_result<int, long>>); static_assert(std::is_same_v<in_in_out_result<int, long, char>, binary_transform_result<int, long, char>>); static_assert(std::is_same_v<in_in_out_result<int, long, char>, merge_result<int, long, char>>); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp index e147c875902c..b8625f5a3f44 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_dangling.pass.cpp @@ -88,7 +88,7 @@ constexpr bool test_all() { using std::ranges::set_union_result; using std::ranges::swap_ranges_result; using std::ranges::unary_transform_result; - //using std::ranges::unique_copy_result; + using std::ranges::unique_copy_result; auto unary_pred = [](int i) { return i > 0; }; auto binary_pred = [](int i, int j) { return i < j; }; @@ -117,7 +117,7 @@ constexpr bool test_all() { dangling_1st(std::ranges::partition_point, in, unary_pred); dangling_1st(std::ranges::lower_bound, in, x); dangling_1st(std::ranges::upper_bound, in, x); - //dangling_1st(std::ranges::equal_range, in, x); + dangling_1st(std::ranges::equal_range, in, x); dangling_1st(std::ranges::min_element, in); dangling_1st(std::ranges::max_element, in); dangling_1st<minmax_result<dangling>>(std::ranges::minmax_element, in); @@ -157,7 +157,7 @@ constexpr bool test_all() { dangling_both<swap_ranges_result<dangling, dangling>>(std::ranges::swap_ranges, in, in2); dangling_1st<reverse_copy_result<dangling, int*>>(std::ranges::reverse_copy, in, out); dangling_1st<rotate_copy_result<dangling, int*>>(std::ranges::rotate_copy, in, mid, out); - //dangling_1st<unique_copy_result<dangling, int*>>(std::ranges::unique_copy, in, out); + dangling_1st<unique_copy_result<dangling, int*>>(std::ranges::unique_copy, in, out); dangling_1st<partition_copy_result<dangling, int*, int*>>(std::ranges::partition_copy, in, out, out2, unary_pred); //dangling_1st<partial_sort_copy_result<dangling, int*>>(std::ranges::partial_sort_copy, in, in2); //dangling_2nd<partial_sort_copy_result<int*, dangling>>(std::ranges::partial_sort_copy, in, in2); @@ -184,7 +184,7 @@ constexpr bool test_all() { //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); + dangling_1st(std::ranges::unique, in); dangling_1st(std::ranges::partition, in, unary_pred); if (!std::is_constant_evaluated()) dangling_1st(std::ranges::stable_partition, in, unary_pred); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp index eeeec9c1f57f..0d1e3990b3b1 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp @@ -115,7 +115,7 @@ constexpr bool test_all() { //test(std::ranges::remove_copy_if, in, out, unary_pred); test(std::ranges::replace_if, in, unary_pred, x); //test(std::ranges::replace_copy_if, in, out, unary_pred, x); - //test(std::ranges::unique_copy, in, out, binary_pred); + test(std::ranges::unique_copy, in, out, binary_pred); test(std::ranges::partition_copy, in, out, out2, unary_pred); //test(std::ranges::partial_sort_copy, in, in2, binary_pred); test(std::ranges::merge, in, in2, out, binary_pred); @@ -124,7 +124,7 @@ constexpr bool test_all() { test(std::ranges::set_symmetric_difference, in, in2, out, binary_pred); test(std::ranges::set_union, in, in2, out, binary_pred); test(std::ranges::remove_if, in, unary_pred); - //test(std::ranges::unique, in, binary_pred); + test(std::ranges::unique, in, binary_pred); test(std::ranges::partition, in, unary_pred); if (!std::is_constant_evaluated()) test(std::ranges::stable_partition, in, unary_pred); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp index aa0b15db6dee..c6fa8598e613 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp @@ -140,7 +140,7 @@ constexpr bool test_all() { // `reverse_copy` has neither a projection nor a predicate. // `rotate_copy` has neither a projection nor a predicate. // `sample` has no requirement that the given generator be invoked via `std::invoke`. - //test(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val); + test(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val); test(std::ranges::partition_copy, in, out, out2, &Foo::unary_pred, &Bar::val); //test(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val); test(std::ranges::merge, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); @@ -153,7 +153,7 @@ constexpr bool test_all() { // `reverse` has neither a projection nor a predicate. // `rotate` has neither a projection nor a predicate. // `shuffle` has neither a projection nor a predicate. - //test(std::ranges::unique, in, &Foo::binary_pred, &Bar::val); + test(std::ranges::unique, in, &Foo::binary_pred, &Bar::val); test(std::ranges::partition, in, &Foo::unary_pred, &Bar::val); if (!std::is_constant_evaluated()) test(std::ranges::stable_partition, in, &Foo::unary_pred, &Bar::val); 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 index 4013065eb42a..191b4953f025 100644 --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -136,7 +136,7 @@ constexpr void run_tests() { if constexpr (std::copyable<T>) { test(std::ranges::reverse_copy, in, out); test_mid(std::ranges::rotate_copy, in, mid, out); - //test(std::ranges::unique_copy, in, out); + test(std::ranges::unique_copy, in, out); test(std::ranges::partition_copy, in, out, out2, unary_pred); //test_mid(std::ranges::partial_sort_copy, in, in2); test(std::ranges::merge, in, in2, out); @@ -153,7 +153,7 @@ constexpr void run_tests() { test(std::ranges::shuffle, in, rand_gen()); //if (!std::is_constant_evaluated()) // test(std::ranges::sample, in, out, count, rand_gen()); - //test(std::ranges::unique, in); + 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()) 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 index 1fc6dfb89c4b..eac6eece9ac7 100644 --- 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 @@ -145,8 +145,8 @@ static_assert(test(std::ranges::stable_sort, a)); //static_assert(test(std::ranges::starts_with, a, a)); static_assert(test(std::ranges::swap_ranges, a, a)); static_assert(test(std::ranges::transform, a, a, triple)); -//static_assert(test(std::ranges::unique, a)); -//static_assert(test(std::ranges::unique_copy, a, a)); +static_assert(test(std::ranges::unique, a)); +static_assert(test(std::ranges::unique_copy, a, a)); static_assert(test(std::ranges::upper_bound, a, 42)); // [memory.syn] |