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 @@ -57,7 +57,7 @@ Write,reverse_copy,Nikolas Klauser,`D127211 `_,✅ Write,rotate_copy,Nikolas Klauser,`D127211 `_,✅ Write,sample,Not assigned,n/a,Not started -Write,unique_copy,Not assigned,n/a,Not started +Write,unique_copy,Hui Xie,`D130404 `,✅ Write,partition_copy,Konstantin Varlamov,`D130070 `_,✅ Write,partial_sort_copy,Konstantin Varlamov,n/a,In progress Merge,merge,Hui Xie,`D128611 `_,✅ @@ -70,7 +70,7 @@ Permutation,reverse,Nikolas Klauser,`D125752 `_,✅ Permutation,rotate,Nikolas Klauser,`D124122 `_,Under review Permutation,shuffle,Not assigned,n/a,Not started -Permutation,unique,Not assigned,n/a,Not started +Permutation,unique,Hui Xie,`D130404 `,✅ Permutation,partition,Konstantin Varlamov,`D129624 `_,✅ Permutation,stable_partition,Konstantin Varlamov,`D129624 `_,✅ Permutation,sort,Konstantin Varlamov,`D127557 `_,✅ diff --git a/libcxx/include/__algorithm/adjacent_find.h b/libcxx/include/__algorithm/adjacent_find.h --- 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 -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) { +template +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter +__adjacent_find(_Iter __first, _Sent __last, _BinaryPredicate&& __pred) { if (__first != __last) { - _ForwardIterator __i = __first; + _Iter __i = __first; while (++__i != __last) { if (__pred(*__first, *__i)) return __first; __first = __i; } } - return __last; + return _IterOps<_AlgPolicy>::next(std::move(__first), std::move(__last)); +} + +template +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator +adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) { + return std::__adjacent_find<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __pred); } template -_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(__first, __last, __equal_to<__v>()); } _LIBCPP_END_NAMESPACE_STD 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 @@ -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/forward.h> #include <__utility/move.h> #include @@ -34,6 +35,10 @@ template <> struct _IterOps<_RangeAlgPolicy> { + + template + 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; @@ -49,6 +54,9 @@ template <> struct _IterOps<_ClassicAlgPolicy> { + template + using __value_type = typename iterator_traits<_Iter>::value_type; + // advance template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 @@ -100,7 +108,7 @@ template _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 - __uncvref_t<_Iter> next(_Iter&& __it, + __uncvref_t<_Iter> next(_Iter&& __it, typename iterator_traits<__uncvref_t<_Iter> >::difference_type __n = 1){ return std::next(std::forward<_Iter>(__it), __n); } diff --git a/libcxx/include/__algorithm/ranges_unique.h b/libcxx/include/__algorithm/ranges_unique.h --- 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 @@ namespace ranges { namespace __unique { -struct __fn { + struct __fn { + template < + permutable _Iter, + sentinel_for<_Iter> _Sent, + class _Proj = identity, + indirect_equivalence_relation> _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 _Sent, class _Proj = identity, - indirect_equivalence_relation> _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 , _Proj>> _Comp = ranges::equal_to> - requires permutable> - _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, _Proj>> _Comp = ranges::equal_to> + requires permutable> + _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 --- 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,37 +43,66 @@ namespace __unique_copy { -struct __fn { - - template _Sent, weakly_incrementable _OutIter, class _Proj = identity, - indirect_equivalence_relation> _Comp = ranges::equal_to> - requires indirectly_copyable<_InIter, _OutIter> && - (forward_iterator<_InIter> || - (input_iterator<_OutIter> && same_as, 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 {}; - } - - template , _Proj>> _Comp = ranges::equal_to> - requires indirectly_copyable, _OutIter> && - (forward_iterator> || - (input_iterator<_OutIter> && same_as, iter_value_t<_OutIter>>) || - indirectly_copyable_storable, _OutIter>) - _LIBCPP_HIDE_FROM_ABI constexpr - unique_copy_result, _OutIter> - operator()(_Range&& __range, _OutIter __result, _Comp __comp = {}, _Proj __proj = {}) const { - // TODO: implement - (void)__range; (void)__result; (void)__comp; (void)__proj; - return {}; - } - -}; + template + concept __can_reread_from_output = (input_iterator<_OutIter> && same_as, iter_value_t<_OutIter>>); + + struct __fn { + template + static consteval auto __get_algo_tag() { + if constexpr (forward_iterator<_InIter>) { + return std::__unique_copy::__reread_from_input_tag{}; + } else if constexpr (__can_reread_from_output<_InIter, _OutIter>) { + return std::__unique_copy::__reread_from_output_tag{}; + } else if (indirectly_copyable_storable<_InIter, _OutIter>) { + return std::__unique_copy::__read_from_tmp_value_tag{}; + } + } + + template + using __algo_tag_t = decltype(__get_algo_tag<_InIter, _OutIter>()); + + template < + input_iterator _InIter, + sentinel_for<_InIter> _Sent, + weakly_incrementable _OutIter, + class _Proj = identity, + indirect_equivalence_relation> _Comp = ranges::equal_to> + requires indirectly_copyable<_InIter, _OutIter> && + (forward_iterator<_InIter> || + (input_iterator<_OutIter> && same_as, 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 { + auto __ret = std::__unique_copy_impl<_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, + indirect_equivalence_relation, _Proj>> _Comp = ranges::equal_to> + requires indirectly_copyable, + _OutIter> && + (forward_iterator> || + (input_iterator<_OutIter> && same_as, iter_value_t<_OutIter>>) || + indirectly_copyable_storable, _OutIter>) + _LIBCPP_HIDE_FROM_ABI constexpr unique_copy_result, _OutIter> + operator()(_Range&& __range, _OutIter __result, _Comp __comp = {}, _Proj __proj = {}) const { + auto __ret = std::__unique_copy_impl<_RangeAlgPolicy>( + ranges::begin(__range), + ranges::end(__range), + std::move(__result), + __make_projected_comp(__comp, __proj), + __algo_tag_t, _OutIter>()); + return {std::move(__ret.first), std::move(__ret.second)}; + } + }; } // namespace __unique_copy diff --git a/libcxx/include/__algorithm/unique.h b/libcxx/include/__algorithm/unique.h --- 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,33 @@ // unique +template +_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<_AlgPolicy>(__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); + return std::pair<_Iter, _Iter>(std::move(++__first), std::move(__i)); + } + return std::pair<_Iter, _Iter>(__first, __first); +} + template -_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 -_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 --- 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 -_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 { + +struct __reread_from_input_tag {}; +struct __reread_from_output_tag {}; +struct __read_from_tmp_value_tag {}; + +} // namespace __unique_copy + +template +_LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _OutputIterator> __unique_copy_impl( + _InputIterator __first, + _Sent __last, + _OutputIterator __result, + _BinaryPredicate&& __pred, + __unique_copy::__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 -_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 +_LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI pair<_ForwardIterator, _OutputIterator> __unique_copy_impl( + _ForwardIterator __first, + _Sent __last, + _OutputIterator __result, + _BinaryPredicate&& __pred, + __unique_copy::__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 -_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 +_LIBCPP_CONSTEXPR_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI pair<_InputIterator, _InputOutputIterator> __unique_copy_impl( + _InputIterator __first, + _Sent __last, + _InputOutputIterator __result, + _BinaryPredicate&& __pred, + __unique_copy::__reread_from_output_tag) { + if (__first != __last) { + *__result = *__first; + while (++__first != __last) + if (!__pred(*__result, *__first)) + *++__result = *__first; + ++__result; + } + return pair<_InputIterator, _InputOutputIterator>(std::move(__first), std::move(__result)); } template -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::iterator_category>::value, + __unique_copy::__reread_from_input_tag, + typename conditional< + is_base_of::iterator_category>::value && + is_same< typename iterator_traits<_InputIterator>::value_type, + typename iterator_traits<_OutputIterator>::value_type>::value, + __unique_copy::__reread_from_output_tag, + __unique_copy::__read_from_tmp_value_tag>::type >::type; + return std::__unique_copy_impl<_ClassicAlgPolicy>( + std::move(__first), std::move(__last), std::move(__result), __pred, __algo_tag()) + .second; } template -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 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -815,6 +815,34 @@ projected, Proj2>> Comp = ranges::less> constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 + + template S, class Proj = identity, + indirect_equivalence_relation> C = ranges::equal_to> + constexpr subrange unique(I first, S last, C comp = {}, Proj proj = {}); // Since C++20 + + template, Proj>> C = ranges::equal_to> + requires permutable> + constexpr borrowed_subrange_t + unique(R&& r, C comp = {}, Proj proj = {}); // Since C++20 + + template S, weakly_incrementable O, class Proj = identity, + indirect_equivalence_relation> C = ranges::equal_to> + requires indirectly_copyable && + (forward_iterator || + (input_iterator && same_as, iter_value_t>) || + indirectly_copyable_storable) + constexpr unique_copy_result + unique_copy(I first, S last, O result, C comp = {}, Proj proj = {}); // Since C++20 + + template, Proj>> C = ranges::equal_to> + requires indirectly_copyable, O> && + (forward_iterator> || + (input_iterator && same_as, iter_value_t>) || + indirectly_copyable_storable, O>) + constexpr unique_copy_result, O> + unique_copy(R&& r, O result, C comp = {}, Proj proj = {}); // Since C++20 } constexpr bool // constexpr in C++20 @@ -1609,6 +1637,8 @@ #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 --- 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 @@ (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 --- 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 @@ (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 --- 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,209 @@ #include #include "almost_satisfies_types.h" +#include "counting_predicates.h" +#include "counting_projection.h" #include "test_iterators.h" -// TODO: SFINAE tests. +template +concept HasUniqueIter = + requires(Iter&& iter, Sent&& sent, Comp&& comp, Proj&& proj) { + std::ranges::unique( + std::forward(iter), std::forward(sent), std::forward(comp), std::forward(proj)); + }; + +static_assert(HasUniqueIter); + +// !permutable +static_assert(!HasUniqueIter); +static_assert(!HasUniqueIter); + +// !sentinel_for +static_assert(!HasUniqueIter); + +// !indirect_equivalence_relation> +static_assert(!HasUniqueIter>); + +template +concept HasUniqueRange = + requires(Range&& range, Comp&& comp, Proj&& proj) { + std::ranges::unique(std::forward(range), std::forward(comp), std::forward(proj)); + }; + +template +using R = UncheckedRange; + +static_assert(HasUniqueRange>); + +// !forward_range +static_assert(!HasUniqueRange); +static_assert(!HasUniqueRange); + +// permutable> +static_assert(!HasUniqueRange>); +static_assert(!HasUniqueRange>); + +// !indirect_equivalence_relation, Proj>> +static_assert(!HasUniqueRange, ComparatorNotCopyable>); + +template class SentWrapper, std::size_t N1, std::size_t N2> +constexpr void testUniqueImpl(std::array input, std::array expected) { + using Sent = SentWrapper; + + // iterator overload + { + auto in = input; + std::same_as> decltype(auto) result = + std::ranges::unique(Iter{in.data()}, Sent{Iter{in.data() + in.size()}}); + assert(std::ranges::equal(std::ranges::subrange{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> decltype(auto) result = std::ranges::unique(r); + assert(std::ranges::equal(std::ranges::subrange{Iter{in.data()}, result.begin()}, expected)); + assert(base(result.end()) == in.data() + in.size()); + } +} + +template 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(in, expected); + } + + // one group of consecutive elements + { + std::array in{2, 3, 3, 3, 4, 3}; + std::array expected{2, 3, 4, 3}; + testUniqueImpl(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(in, expected); + } + + // all the same + { + std::array in{1, 1, 1, 1, 1, 1}; + std::array expected{1}; + testUniqueImpl(in, expected); + } + + // empty range + { + std::array in{}; + std::array expected{}; + testUniqueImpl(in, expected); + } +} + +template