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 @@ -24,8 +24,8 @@ Search,count,Nikolas Klauser,`D121523 `_,✅ Search,count_if,Nikolas Klauser,`D121523 `_,✅ Search,search,Nikolas Klauser,`D124079 `_,Under review -Search,search_n,Nikolas Klauser,`D124079 `_,Under review -Search,find_end,Nikolas Klauser,`D124079 `_,Under review +Search,search_n,Nikolas Klauser,`D124079 `_,✅ +Search,find_end,Nikolas Klauser,`D124079 `_,✅ Read-only,is_partitioned,Nikolas Klauser,`D124440 `_,✅ Read-only,is_sorted,Nikolas Klauser,`D125608 `_,✅ Read-only,is_sorted_unitl,Nikolas Klauser,`D125608 `_,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -82,6 +82,7 @@ __algorithm/ranges_fill.h __algorithm/ranges_fill_n.h __algorithm/ranges_find.h + __algorithm/ranges_find_end.h __algorithm/ranges_find_first_of.h __algorithm/ranges_find_if.h __algorithm/ranges_find_if_not.h @@ -106,6 +107,8 @@ __algorithm/ranges_replace.h __algorithm/ranges_replace_if.h __algorithm/ranges_reverse.h + __algorithm/ranges_search.h + __algorithm/ranges_search_n.h __algorithm/ranges_sort.h __algorithm/ranges_stable_sort.h __algorithm/ranges_swap_ranges.h diff --git a/libcxx/include/__algorithm/find_end.h b/libcxx/include/__algorithm/find_end.h --- a/libcxx/include/__algorithm/find_end.h +++ b/libcxx/include/__algorithm/find_end.h @@ -11,8 +11,16 @@ #define _LIBCPP___ALGORITHM_FIND_END_OF_H #include <__algorithm/comp.h> +#include <__algorithm/iterator_operations.h> +#include <__algorithm/search.h> #include <__config> +#include <__functional/identity.h> +#include <__iterator/advance.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/reverse_iterator.h> +#include <__utility/pair.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -20,35 +28,52 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred, forward_iterator_tag, - forward_iterator_tag) { +template < + class _IterOps, + class _Iter1, + class _Sent1, + class _Iter2, + class _Sent2, + class _Pred, + class _Proj1, + class _Proj2> +_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter1> __find_end_impl( + _Iter1 __first1, + _Sent1 __last1, + _Iter2 __first2, + _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + forward_iterator_tag, + forward_iterator_tag) { // modeled after search algorithm - _ForwardIterator1 __r = __last1; // __last1 is the "default" answer + _Iter1 __match_first = _IterOps::next(__first1, __last1); // __last1 is the "default" answer + _Iter1 __match_last = __match_first; if (__first2 == __last2) - return __r; + return pair<_Iter1, _Iter1>(__match_last, __match_last); while (true) { while (true) { - if (__first1 == __last1) // if source exhausted return last correct answer - return __r; // (or __last1 if never found) - if (__pred(*__first1, *__first2)) + if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found) + return pair<_Iter1, _Iter1>(__match_first, __match_last); + if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _ForwardIterator1 __m1 = __first1; - _ForwardIterator2 __m2 = __first2; + _Iter1 __m1 = __first1; + _Iter2 __m2 = __first2; while (true) { if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one - __r = __first1; + __match_first = __first1; + __match_last = ++__m1; ++__first1; break; } if (++__m1 == __last1) // Source exhausted, return last answer - return __r; - if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first + return pair<_Iter1, _Iter1>(__match_first, __match_last); + // mismatch, restart with a new __first + if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { ++__first1; break; @@ -57,33 +82,52 @@ } } -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 __find_end( - _BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, - _BidirectionalIterator2 __last2, _BinaryPredicate __pred, bidirectional_iterator_tag, bidirectional_iterator_tag) { +template < + class _IterOps, + class _Pred, + class _Iter1, + class _Sent1, + class _Iter2, + class _Sent2, + class _Proj1, + class _Proj2> +_LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter1 __find_end( + _Iter1 __first1, + _Sent1 __last1_, + _Iter2 __first2, + _Sent2 __last2_, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + bidirectional_iterator_tag, + bidirectional_iterator_tag) { + auto __last1 = _IterOps::next(__first1, __last1_); + auto __last2 = _IterOps::next(__first2, __last2_); // modeled after search algorithm (in reverse) if (__first2 == __last2) return __last1; // Everything matches an empty sequence - _BidirectionalIterator1 __l1 = __last1; - _BidirectionalIterator2 __l2 = __last2; + _Iter1 __l1 = __last1; + _Iter2 __l2 = __last2; --__l2; while (true) { // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks while (true) { if (__first1 == __l1) // return __last1 if no element matches *__first2 return __last1; - if (__pred(*--__l1, *__l2)) + if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) break; } // *__l1 matches *__l2, now match elements before here - _BidirectionalIterator1 __m1 = __l1; - _BidirectionalIterator2 __m2 = __l2; + _Iter1 __m1 = __l1; + _Iter2 __m2 = __l2; while (true) { if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) return __m1; if (__m1 == __first1) // Otherwise if source exhaused, pattern not found return __last1; - if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 + + // if there is a mismatch, restart with a new __l1 + if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2))) { break; } // else there is a match, check next elements @@ -91,37 +135,53 @@ } } -template -_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end( - _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) { - typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; - typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; +template < + class _IterOps, + class _Pred, + class _Iter1, + class _Sent1, + class _Iter2, + class _Sent2, + class _Proj1, + class _Proj2> +_LIBCPP_CONSTEXPR_AFTER_CXX11 _Iter1 __find_end( + _Iter1 __first1, + _Sent1 __last1_, + _Iter2 __first2, + _Sent2 __last2_, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + random_access_iterator_tag, + random_access_iterator_tag) { + typedef typename iterator_traits<_Iter1>::difference_type _D1; + auto __last1 = _IterOps::next(__first1, __last1_); + auto __last2 = _IterOps::next(__first2, __last2_); // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - _D2 __len2 = __last2 - __first2; + auto __len2 = __last2 - __first2; if (__len2 == 0) return __last1; - _D1 __len1 = __last1 - __first1; + auto __len1 = __last1 - __first1; if (__len1 < __len2) return __last1; - const _RandomAccessIterator1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here - _RandomAccessIterator1 __l1 = __last1; - _RandomAccessIterator2 __l2 = __last2; + const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here + _Iter1 __l1 = __last1; + _Iter2 __l2 = __last2; --__l2; while (true) { while (true) { if (__s == __l1) return __last1; - if (__pred(*--__l1, *__l2)) + if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) break; } - _RandomAccessIterator1 __m1 = __l1; - _RandomAccessIterator2 __m2 = __l2; + _Iter1 __m1 = __l1; + _Iter2 __m2 = __l2; while (true) { if (__m2 == __first2) return __m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!__pred(*--__m1, *--__m2)) { + if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) { break; } } @@ -129,20 +189,31 @@ } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred) { - return _VSTD::__find_end<_BinaryPredicate&>( - __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + auto __proj = __identity(); + return std::__find_end_impl<_StdIterOps>( + __first1, + __last1, + __first2, + __last2, + __pred, + __proj, + __proj, + typename iterator_traits<_ForwardIterator1>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()) + .first; } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + using __v1 = typename iterator_traits<_ForwardIterator1>::value_type; + using __v2 = typename iterator_traits<_ForwardIterator2>::value_type; + return std::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } _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 @@ -13,6 +13,7 @@ #include <__iterator/advance.h> #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -24,6 +25,8 @@ struct _RangesIterOps { static constexpr auto advance = ranges::advance; static constexpr auto distance = ranges::distance; + static constexpr auto next = ranges::next; + static constexpr auto __advance_to = ranges::advance; }; #endif @@ -40,6 +43,17 @@ return std::distance(__first, __last); } + template + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 + _Iterator next(_Iterator, _Iterator __last) { + return __last; + } + + template + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void __advance_to(_Iterator& __first, _Iterator __last) { + __first = __last; + } + }; _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_find_end.h b/libcxx/include/__algorithm/ranges_find_end.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_end.h @@ -0,0 +1,113 @@ +//===----------------------------------------------------------------------===// +// +// 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_FIND_END_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_END_H + +#include <__algorithm/find_end.h> +#include <__algorithm/iterator_operations.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/indirectly_comparable.h> +#include <__iterator/iterator_traits.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/subrange.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 + +template +consteval auto __get_iterator_concept() { + if constexpr (contiguous_iterator<_Iter>) + return contiguous_iterator_tag(); + else if constexpr (random_access_iterator<_Iter>) + return random_access_iterator_tag(); + else if constexpr (bidirectional_iterator<_Iter>) + return bidirectional_iterator_tag(); + else if constexpr (forward_iterator<_Iter>) + return forward_iterator_tag(); + else if constexpr (input_iterator<_Iter>) + return input_iterator_tag(); +} + +template +using __iterator_concept = decltype(__get_iterator_concept<_Iter>()); + +namespace ranges { +namespace __find_end { +struct __fn { + template _Sent1, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + class _Pred = ranges::equal_to, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__find_end_impl<_RangesIterOps>( + __first1, + __last1, + __first2, + __last2, + __pred, + __proj1, + __proj2, + __iterator_concept<_Iter1>(), + __iterator_concept<_Iter2>()); + return {__ret.first, __ret.second}; + } + + template + requires indirectly_comparable, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range1> operator()(_Range1&& __range1, + _Range2&& __range2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__find_end_impl<_RangesIterOps>( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + __pred, + __proj1, + __proj2, + __iterator_concept>(), + __iterator_concept>()); + return {__ret.first, __ret.second}; + } +}; +} // namespace __find_end + +inline namespace __cpo { + inline constexpr auto find_end = __find_end::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_END_H diff --git a/libcxx/include/__algorithm/ranges_search.h b/libcxx/include/__algorithm/ranges_search.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_search.h @@ -0,0 +1,134 @@ +//===----------------------------------------------------------------------===// +// +// 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_SEARCH_H +#define _LIBCPP___ALGORITHM_RANGES_SEARCH_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/search.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/size.h> +#include <__ranges/subrange.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 __search { +struct __fn { + template + _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_impl( + _Iter1 __first1, + _Sent1 __last1, + _Iter2 __first2, + _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2) { + if constexpr (sized_sentinel_for<_Sent2, _Iter2>) { + auto __size2 = ranges::distance(__first2, __last2); + if (__size2 == 0) + return {__first1, __first1}; + + if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { + auto __size1 = ranges::distance(__first1, __last1); + if (__size1 < __size2) { + ranges::advance(__first1, __last1); + return {__first1, __first1}; + } + + if constexpr (random_access_iterator<_Iter1> && random_access_iterator<_Iter2>) { + auto __ret = std::__search_random_access_impl<_RangesIterOps>( + __first1, __last1, __first2, __last2, __pred, __proj1, __proj2, __size1, __size2); + return {__ret.first, __ret.second}; + } + } + } + + auto __ret = + std::__search_forward_impl<_RangesIterOps>(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); + return {__ret.first, __ret.second}; + } + + template _Sent1, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + class _Pred = ranges::equal_to, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __ranges_search_impl(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); + } + + template + requires indirectly_comparable, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range1> operator()(_Range1&& __range1, + _Range2&& __range2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __first1 = ranges::begin(__range1); + if constexpr (sized_range<_Range2>) { + auto __size2 = ranges::size(__range2); + if (__size2 == 0) + return {__first1, __first1}; + if constexpr (sized_range<_Range1>) { + auto __size1 = ranges::size(__range1); + if (__size1 < __size2) { + ranges::advance(__first1, ranges::end(__range1)); + return {__first1, __first1}; + } + } + } + + return __ranges_search_impl( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + __pred, + __proj1, + __proj2); + } + +}; +} // namespace __search + +inline namespace __cpo { + inline constexpr auto search = __search::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_H diff --git a/libcxx/include/__algorithm/ranges_search_n.h b/libcxx/include/__algorithm/ranges_search_n.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_search_n.h @@ -0,0 +1,119 @@ +//===----------------------------------------------------------------------===// +// +// 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_SEARCH_N_H +#define _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/search_n.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/size.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 __search_n { +struct __fn { + + template + _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_n_impl( + _Iter1 __first, _Sent1 __last, _SizeT __count, const _Type& __value, _Pred& __pred, _Proj& __proj) { + if (__count == 0) + return {__first, __first}; + + if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { + auto __size = ranges::distance(__first, __last); + if (__size < __count) { + ranges::advance(__first, __last); + return {__first, __first}; + } + + if constexpr (random_access_iterator<_Iter1>) { + auto __ret = __search_n_random_access_impl<_RangesIterOps>(__first, __last, + __count, + __value, + __pred, + __proj, + __size); + return {std::move(__ret.first), std::move(__ret.second)}; + } + } + + auto __ret = std::__search_n_forward_impl<_RangesIterOps>(__first, __last, + __count, + __value, + __pred, + __proj); + return {std::move(__ret.first), std::move(__ret.second)}; + } + + template _Sent, + class _Type, + class _Pred = ranges::equal_to, + class _Proj = identity> + requires indirectly_comparable<_Iter, const _Type*, _Pred, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter> operator()(_Iter __first, _Sent __last, + iter_difference_t<_Iter> __count, + const _Type& __value, + _Pred __pred = {}, + _Proj __proj = _Proj{}) const { + return __ranges_search_n_impl(__first, __last, __count, __value, __pred, __proj); + } + + template + requires indirectly_comparable, const _Type*, _Pred, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, + range_difference_t<_Range> __count, + const _Type& __value, + _Pred __pred = {}, + _Proj __proj = {}) const { + auto __first = ranges::begin(__range); + if (__count <= 0) + return {__first, __first}; + if constexpr (sized_range<_Range>) { + auto __size1 = ranges::size(__range); + if (__size1 < static_cast>(__count)) { + ranges::advance(__first, ranges::end(__range)); + return {__first, __first}; + } + } + + return __ranges_search_n_impl(ranges::begin(__range), ranges::end(__range), __count, __value, __pred, __proj); + } +}; +} // namespace __search_n + +inline namespace __cpo { + inline constexpr auto search_n = __search_n::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H diff --git a/libcxx/include/__algorithm/search.h b/libcxx/include/__algorithm/search.h --- a/libcxx/include/__algorithm/search.h +++ b/libcxx/include/__algorithm/search.h @@ -11,9 +11,15 @@ #define _LIBCPP___ALGORITHM_SEARCH_H #include <__algorithm/comp.h> +#include <__algorithm/iterator_operations.h> #include <__config> +#include <__functional/identity.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> #include <__iterator/iterator_traits.h> +#include <__type_traits/is_callable.h> #include <__utility/pair.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,31 +27,43 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -pair<_ForwardIterator1, _ForwardIterator1> - _LIBCPP_CONSTEXPR_AFTER_CXX11 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_forward_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2) { if (__first2 == __last2) - return _VSTD::make_pair(__first1, __first1); // Everything matches an empty sequence + return std::make_pair(__first1, __first1); // Everything matches an empty sequence while (true) { // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks while (true) { - if (__first1 == __last1) // return __last1 if no element matches *__first2 - return _VSTD::make_pair(__last1, __last1); - if (__pred(*__first1, *__first2)) + if (__first1 == __last1) { // return __last1 if no element matches *__first2 + _IterOps::__advance_to(__first1, __last1); + return std::make_pair(__first1, __first1); + } + if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _ForwardIterator1 __m1 = __first1; - _ForwardIterator2 __m2 = __first2; + _Iter1 __m1 = __first1; + _Iter2 __m2 = __first2; while (true) { if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) - return _VSTD::make_pair(__first1, __m1); - if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found - return _VSTD::make_pair(__last1, __last1); - if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1 + return std::make_pair(__first1, ++__m1); + if (++__m1 == __last1) { // Otherwise if source exhaused, pattern not found + return std::make_pair(__m1, __m1); + } + + // if there is a mismatch, restart with a new __first1 + if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { ++__first1; break; @@ -54,38 +72,42 @@ } } -template -_LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_RandomAccessIterator1, _RandomAccessIterator1> -__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, - random_access_iterator_tag) { - typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; - typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; - // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - const _D2 __len2 = __last2 - __first2; - if (__len2 == 0) - return _VSTD::make_pair(__first1, __first1); - const _D1 __len1 = __last1 - __first1; - if (__len1 < __len2) - return _VSTD::make_pair(__last1, __last1); - const _RandomAccessIterator1 __s = __last1 - _D1(__len2 - 1); // Start of pattern match can't go beyond here +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_random_access_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + _DiffT1 __size1, + _DiffT2 __size2) { + const _Iter1 __s = __first1 + __size1 - _DiffT1(__size2 - 1); // Start of pattern match can't go beyond here while (true) { while (true) { - if (__first1 == __s) - return _VSTD::make_pair(__last1, __last1); - if (__pred(*__first1, *__first2)) + if (__first1 == __s) { + _IterOps::__advance_to(__first1, __last1); + return std::make_pair(__first1, __first1); + } + if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; ++__first1; } - _RandomAccessIterator1 __m1 = __first1; - _RandomAccessIterator2 __m2 = __first2; + _Iter1 __m1 = __first1; + _Iter2 __m2 = __first2; while (true) { if (++__m2 == __last2) - return _VSTD::make_pair(__first1, __first1 + _D1(__len2)); + return std::make_pair(__first1, __first1 + _DiffT1(__size2)); ++__m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!__pred(*__m1, *__m2)) { + if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { ++__first1; break; } @@ -93,22 +115,78 @@ } } +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + __enable_if_t<__is_cpp17_random_access_iterator<_Iter1>::value + && __is_cpp17_random_access_iterator<_Iter2>::value>* = nullptr) { + + auto __size2 = __last2 - __first2; + if (__size2 == 0) + return std::make_pair(__first1, __first1); + + auto __size1 = __last1 - __first1; + if (__size1 < __size2) { + return std::make_pair(__last1, __last1); + } + + return std::__search_random_access_impl<_StdIterOps>(__first1, __last1, + __first2, __last2, + __pred, + __proj1, + __proj2, + __size1, + __size2); +} + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value + && __is_cpp17_forward_iterator<_Iter2>::value + && !(__is_cpp17_random_access_iterator<_Iter1>::value + && __is_cpp17_random_access_iterator<_Iter2>::value)>* = nullptr) { + return std::__search_forward_impl<_StdIterOps>(__first1, __last1, + __first2, __last2, + __pred, + __proj1, + __proj2); +} + template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred) { - return _VSTD::__search<_BinaryPredicate&>( - __first1, __last1, __first2, __last2, __pred, - typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()).first; +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value, + "BinaryPredicate has to be callable"); + auto __proj = __identity(); + return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first; } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + using __v1 = typename iterator_traits<_ForwardIterator1>::value_type; + using __v2 = typename iterator_traits<_ForwardIterator2>::value_type; + return std::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } #if _LIBCPP_STD_VER > 14 diff --git a/libcxx/include/__algorithm/search_n.h b/libcxx/include/__algorithm/search_n.h --- a/libcxx/include/__algorithm/search_n.h +++ b/libcxx/include/__algorithm/search_n.h @@ -11,8 +11,15 @@ #define _LIBCPP___ALGORITHM_SEARCH_N_H #include <__algorithm/comp.h> +#include <__algorithm/iterator_operations.h> #include <__config> +#include <__functional/identity.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> +#include <__ranges/concepts.h> +#include <__utility/pair.h> #include // __convert_to_integral #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -21,30 +28,39 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, - _Size __count, const _Tp& __value_, _BinaryPredicate __pred, - forward_iterator_tag) { +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter, _Iter> __search_n_forward_impl(_Iter __first, _Sent __last, + _SizeT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj) { if (__count <= 0) - return __first; + return std::make_pair(__first, __first); while (true) { - // Find first element in sequence that matchs __value_, with a mininum of loop checks + // Find first element in sequence that matchs __value, with a mininum of loop checks while (true) { - if (__first == __last) // return __last if no element matches __value_ - return __last; - if (__pred(*__first, __value_)) + if (__first == __last) { // return __last if no element matches __value + _IterOps::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value)) break; ++__first; } - // *__first matches __value_, now match elements after here - _ForwardIterator __m = __first; - _Size __c(0); + // *__first matches __value, now match elements after here + _Iter __m = __first; + _SizeT __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - return __first; - if (++__m == __last) // Otherwise if source exhaused, pattern not found - return __last; - if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first + return std::make_pair(__first, ++__m); + if (++__m == __last) { // Otherwise if source exhaused, pattern not found + _IterOps::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + + // if there is a mismatch, restart with a new __first + if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value)) { __first = __m; ++__first; @@ -54,35 +70,44 @@ } } -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Size __count, - const _Tp& __value_, _BinaryPredicate __pred, - random_access_iterator_tag) { - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +std::pair<_Iter, _Iter> __search_n_random_access_impl(_Iter __first, _Sent __last, + _SizeT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj, + _DiffT __size1) { + using difference_type = typename iterator_traits<_Iter>::difference_type; if (__count <= 0) - return __first; - _Size __len = static_cast<_Size>(__last - __first); - if (__len < __count) - return __last; - const _RandomAccessIterator __s = __last - difference_type(__count - 1); // Start of pattern match can't go beyond here + return std::make_pair(__first, __first); + if (__size1 < __count) { + _IterOps::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + + const auto __s = __first + __size1 - difference_type(__count - 1); // Start of pattern match can't go beyond here while (true) { - // Find first element in sequence that matchs __value_, with a mininum of loop checks + // Find first element in sequence that matchs __value, with a mininum of loop checks while (true) { - if (__first >= __s) // return __last if no element matches __value_ - return __last; - if (__pred(*__first, __value_)) + if (__first >= __s) { // return __last if no element matches __value + _IterOps::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value)) break; ++__first; } // *__first matches __value_, now match elements after here - _RandomAccessIterator __m = __first; - _Size __c(0); + auto __m = __first; + _SizeT __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - return __first; - ++__m; // no need to check range on __m because __s guarantees we have enough source - if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first + return std::make_pair(__first, __first + _DiffT(__count)); + ++__m; // no need to check range on __m because __s guarantees we have enough source + + // if there is a mismatch, restart with a new __first + if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value)) { __first = __m; ++__first; @@ -92,19 +117,63 @@ } } +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter, _Iter> __search_n_impl(_Iter __first, _Sent __last, + _DiffT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj, + __enable_if_t<__is_cpp17_random_access_iterator<_Iter>::value>* = nullptr) { + return std::__search_n_random_access_impl<_StdIterOps>(__first, __last, + __count, + __value, + __pred, + __proj, + __last - __first); +} + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_n_impl(_Iter1 __first, _Sent1 __last, + _DiffT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj, + __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value + && !__is_cpp17_random_access_iterator<_Iter1>::value>* = nullptr) { + return std::__search_n_forward_impl<_StdIterOps>(__first, __last, + __count, + __value, + __pred, + __proj); +} + template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator search_n( - _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred) { - return _VSTD::__search_n<_BinaryPredicate&>( - __first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred, - typename iterator_traits<_ForwardIterator>::iterator_category()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, + _Size __count, + const _Tp& __value_, + _BinaryPredicate __pred) { + static_assert(__is_callable<_BinaryPredicate, decltype(*__first), decltype(*__last)>::value, + "BinaryPredicate has to be callable"); + auto __proj = __identity(); + return std::__search_n_impl(__first, __last, std::__convert_to_integral(__count), __value_, __pred, __proj).first; } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) { +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) { typedef typename iterator_traits<_ForwardIterator>::value_type __v; - return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>()); + return std::search_n(__first, __last, std::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__functional/default_searcher.h b/libcxx/include/__functional/default_searcher.h --- a/libcxx/include/__functional/default_searcher.h +++ b/libcxx/include/__functional/default_searcher.h @@ -12,6 +12,7 @@ #include <__algorithm/search.h> #include <__config> +#include <__functional/identity.h> #include <__functional/operations.h> #include <__iterator/iterator_traits.h> #include <__utility/pair.h> @@ -38,16 +39,15 @@ pair<_ForwardIterator2, _ForwardIterator2> operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { - return _VSTD::__search(__f, __l, __first_, __last_, __pred_, - typename iterator_traits<_ForwardIterator>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); + auto __proj = __identity(); + return std::__search_impl(__f, __l, __first_, __last_, __pred_, __proj, __proj); } private: _ForwardIterator __first_; _ForwardIterator __last_; _BinaryPredicate __pred_; - }; +}; #endif // _LIBCPP_STD_VER > 14 diff --git a/libcxx/include/__iterator/iterator_traits.h b/libcxx/include/__iterator/iterator_traits.h --- a/libcxx/include/__iterator/iterator_traits.h +++ b/libcxx/include/__iterator/iterator_traits.h @@ -481,6 +481,12 @@ __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value && !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value> {}; +template +struct __is_exactly_cpp17_bidirectional_iterator + : public integral_constant::value && + !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value> {}; + template using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; 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 @@ -15,6 +15,7 @@ #include <__compare/three_way_comparable.h> #include <__concepts/convertible_to.h> #include <__config> +#include <__iterator/advance.h> #include <__iterator/concepts.h> #include <__iterator/incrementable_traits.h> #include <__iterator/iter_move.h> diff --git a/libcxx/include/__string/char_traits.h b/libcxx/include/__string/char_traits.h --- a/libcxx/include/__string/char_traits.h +++ b/libcxx/include/__string/char_traits.h @@ -802,9 +802,7 @@ __pos += __n; else __pos = __sz; - const _CharT* __r = _VSTD::__find_end( - __p, __p + __pos, __s, __s + __n, _Traits::eq, - random_access_iterator_tag(), random_access_iterator_tag()); + const _CharT* __r = std::find_end(__p, __p + __pos, __s, __s + __n, _Traits::eq); if (__n > 0 && __r == __p + __pos) return __npos; return static_cast<_SizeT>(__r - __p); diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -511,6 +511,49 @@ merge(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + template S1, forward_iterator I2, + sentinel_for S2, class Pred = ranges::equal_to, + class Proj1 = identity, class Proj2 = identity> + requires indirectly_comparable + constexpr subrange + ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + + template + requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> + constexpr borrowed_subrange_t + ranges::search(R1&& r1, R2&& r2, Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + + template S, class T, + class Pred = ranges::equal_to, class Proj = identity> + requires indirectly_comparable + constexpr subrange + ranges::search_n(I first, S last, iter_difference_t count, + const T& value, Pred pred = {}, Proj proj = {}); // since C++20 + + template + requires indirectly_comparable, const T*, Pred, Proj> + constexpr borrowed_subrange_t + ranges::search_n(R&& r, range_difference_t count, + const T& value, Pred pred = {}, Proj proj = {}); // since C++20 + + template S1, forward_iterator I2, sentinel_for S2, + class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> + requires indirectly_comparable + constexpr subrange + ranges::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + + template + requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> + constexpr borrowed_subrange_t + ranges::find_end(R1&& r1, R2&& r2, Pred pred = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + } constexpr bool // constexpr in C++20 @@ -1254,6 +1297,7 @@ #include <__algorithm/ranges_fill.h> #include <__algorithm/ranges_fill_n.h> #include <__algorithm/ranges_find.h> +#include <__algorithm/ranges_find_end.h> #include <__algorithm/ranges_find_first_of.h> #include <__algorithm/ranges_find_if.h> #include <__algorithm/ranges_find_if_not.h> @@ -1278,6 +1322,8 @@ #include <__algorithm/ranges_replace.h> #include <__algorithm/ranges_replace_if.h> #include <__algorithm/ranges_reverse.h> +#include <__algorithm/ranges_search.h> +#include <__algorithm/ranges_search_n.h> #include <__algorithm/ranges_sort.h> #include <__algorithm/ranges_stable_sort.h> #include <__algorithm/ranges_swap_ranges.h> diff --git a/libcxx/include/experimental/functional b/libcxx/include/experimental/functional --- a/libcxx/include/experimental/functional +++ b/libcxx/include/experimental/functional @@ -62,6 +62,7 @@ #include <__assert> // all public C++ headers provide the assertion handler #include <__debug> +#include <__functional/identity.h> #include <__memory/uses_allocator.h> #include #include @@ -104,9 +105,8 @@ pair<_ForwardIterator2, _ForwardIterator2> operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { - return _VSTD::__search(__f, __l, __first_, __last_, __pred_, - typename iterator_traits<_ForwardIterator>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); + auto __proj = __identity(); + return std::__search_impl(__f, __l, __first_, __last_, __pred_, __proj, __proj); } private: 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 @@ -321,6 +321,7 @@ module ranges_fill { private header "__algorithm/ranges_fill.h" } module ranges_fill_n { private header "__algorithm/ranges_fill_n.h" } module ranges_find { private header "__algorithm/ranges_find.h" } + module ranges_find_end { private header "__algorithm/ranges_find_end.h" } module ranges_find_first_of { private header "__algorithm/ranges_find_first_of.h" } module ranges_find_if { private header "__algorithm/ranges_find_if.h" } module ranges_find_if_not { private header "__algorithm/ranges_find_if_not.h" } @@ -345,6 +346,8 @@ module ranges_replace { private header "__algorithm/ranges_replace.h" } module ranges_replace_if { private header "__algorithm/ranges_replace_if.h" } module ranges_reverse { private header "__algorithm/ranges_reverse.h" } + module ranges_search { private header "__algorithm/ranges_search.h" } + module ranges_search_n { private header "__algorithm/ranges_search_n.h" } module ranges_sort { private header "__algorithm/ranges_sort.h" } module ranges_stable_sort { private header "__algorithm/ranges_stable_sort.h" } module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.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 @@ -84,7 +84,7 @@ void **mid = a+5; void **last = a+10; void **first2 = b; - //void **mid2 = b+5; + void **mid2 = b+5; void **last2 = b+10; void *value = nullptr; int count = 1; @@ -110,8 +110,8 @@ (void)std::ranges::equal(a, b, Equal(&copies)); assert(copies == 0); //(void)std::ranges::equal_range(first, last, value, Less(&copies)); assert(copies == 0); //(void)std::ranges::equal_range(a, value, Less(&copies)); assert(copies == 0); - //(void)std::ranges::find_end(first, last, first2, mid2, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::find_end(a, b, Equal(&copies)); assert(copies == 0); + (void)std::ranges::find_end(first, last, first2, mid2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::find_end(a, b, Equal(&copies)); assert(copies == 0); (void)std::ranges::find_first_of(first, last, first2, last2, Equal(&copies)); assert(copies == 0); (void)std::ranges::find_first_of(a, b, Equal(&copies)); assert(copies == 0); (void)std::ranges::find_if(first, last, UnaryTrue(&copies)); assert(copies == 0); @@ -195,10 +195,10 @@ //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(&copies), value); assert(copies == 0); (void)std::ranges::replace_if(first, last, UnaryTrue(&copies), value); assert(copies == 0); (void)std::ranges::replace_if(a, UnaryTrue(&copies), value); assert(copies == 0); - //(void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0); + (void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0); + (void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0); + (void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0); //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); //(void)std::ranges::set_difference(a, b, first2, Less(&copies)); assert(copies == 0); //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -119,6 +119,7 @@ #include <__algorithm/ranges_fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill.h'}} #include <__algorithm/ranges_fill_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_fill_n.h'}} #include <__algorithm/ranges_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find.h'}} +#include <__algorithm/ranges_find_end.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_end.h'}} #include <__algorithm/ranges_find_first_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_first_of.h'}} #include <__algorithm/ranges_find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if.h'}} #include <__algorithm/ranges_find_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}} @@ -143,6 +144,8 @@ #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}} #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_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search.h'}} +#include <__algorithm/ranges_search_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_search_n.h'}} #include <__algorithm/ranges_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}} #include <__algorithm/ranges_stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}} #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp @@ -0,0 +1,354 @@ +//===----------------------------------------------------------------------===// +// +// 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 S1, forward_iterator I2, sentinel_for S2, +// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> +// requires indirectly_comparable +// constexpr subrange +// ranges::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); +// template +// requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> +// constexpr borrowed_subrange_t +// ranges::find_end(R1&& r1, R2&& r2, Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); + +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template +concept HasFindEndIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { + std::ranges::find_end(first1, last1, first2, last2); +}; + +static_assert(HasFindEndIt); +static_assert(!HasFindEndIt); +static_assert(!HasFindEndIt); +static_assert(!HasFindEndIt); +static_assert(!HasFindEndIt); // not indirectly comparable +static_assert(!HasFindEndIt); +static_assert(!HasFindEndIt); +static_assert(!HasFindEndIt); +static_assert(!HasFindEndIt); +static_assert(!HasFindEndIt); + +template > +concept HasFindEndR = requires (Range1 range1, Range2 range2) { + std::ranges::find_end(range1, range2); +}; + +static_assert(HasFindEndR>); +static_assert(!HasFindEndR); +static_assert(!HasFindEndR); +static_assert(!HasFindEndR); +static_assert(!HasFindEndR); +static_assert(!HasFindEndR, UncheckedRange>); // not indirectly comparable +static_assert(!HasFindEndR, ForwardRangeNotDerivedFrom>); +static_assert(!HasFindEndR, ForwardRangeNotIncrementable>); +static_assert(!HasFindEndR, ForwardRangeNotSentinelSemiregular>); +static_assert(!HasFindEndR, ForwardRangeNotSentinelEqualityComparableWith>); + +template +constexpr void test_iterators() { + { // simple test + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4}; + std::same_as> decltype(auto) ret = + std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2))); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 4); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2))); + std::same_as> decltype(auto) ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 4); + } + } + + { // matching part begins at the front + { + int a[] = {7, 5, 3, 7, 3, 6}; + int p[] = {7, 5, 3}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {7, 5, 3, 7, 3, 6}; + int p[] = {7, 5, 3}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } + + { // matching part ends at the back + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {4, 8}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 2))); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {4, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + } + + { // pattern does not match + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {1}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 1))); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {1}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + } + + { // range and pattern are identical + { + int a[] = {6, 7, 8, 9}; + int p[] = {6, 7, 8, 9}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 4)), Iter2(p), Sent2(Iter2(p + 4))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + { + int a[] = {6, 7, 8, 9}; + int p[] = {6, 7, 8, 9}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + } + + { // pattern is longer than range + { + int a[] = {6, 7, 8}; + int p[] = {6, 7, 8, 9}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p + 4))); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {6, 7, 8}; + int p[] = {6, 7, 8, 9}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + } + + { // pattern has zero length + { + int a[] = {6, 7, 8}; + int p[] = {}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p))); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {6, 7, 8}; + int p[] = {}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + } + + { // range has zero length + { + int a[] = {}; + int p[] = {6, 7, 8}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + { + int a[] = {}; + int p[] = {6, 7, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + } + + { // check that the first match is returned + { + int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8}; + int p[] = {6, 7, 8}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 9)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a + 6); + assert(base(ret.end()) == a + 9); + } + { + int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8}; + int p[] = {6, 7, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 9))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 6); + assert(base(ret.end()) == a + 9); + } + } + + { // check that the predicate is used + { + int a[] = {1, 2, 8, 1, 5, 6}; + int p[] = {7, 0, 4}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), + Iter2(p), Sent2(Iter2(p + 3)), + [](int l, int r) { return l > r; }); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {1, 2, 8, 1, 5, 6}; + int p[] = {7, 0, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::find_end(range1, range2, [](int l, int r) { return l > r; }); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 5); + } + } + + { // check that the projections are used + { + int a[] = {1, 3, 5, 1, 5, 6}; + int p[] = {2, 3, 4}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), + Iter2(p), Sent2(Iter2(p + 3)), + {}, + [](int i) { return i + 3; }, + [](int i) { return i * 2; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {1, 3, 5, 1, 5, 6}; + int p[] = {2, 3, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::find_end(range1, + range2, + {}, + [](int i) { return i + 3; }, + [](int i) { return i * 2; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } +} + +template +constexpr void test_iterators2() { + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators(); +} + +constexpr bool test() { + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2(); + + { // check that std::invoke is used + struct S { + int i; + + constexpr S identity() { + return *this; + } + + constexpr bool compare(const S& s) { + return i == s.i; + } + }; + { + S a[] = {{1}, {2}, {3}, {4}}; + S p[] = {{2}, {3}}; + auto ret = std::ranges::find_end(a, a + 4, p, p + 2, &S::compare, &S::identity, &S::identity); + assert(ret.begin() == a + 1); + assert(ret.end() == a + 3); + } + { + S a[] = {{1}, {2}, {3}, {4}}; + S p[] = {{2}, {3}}; + auto ret = std::ranges::find_end(a, p, &S::compare, &S::identity, &S::identity); + assert(ret.begin() == a + 1); + assert(ret.end() == a + 3); + } + } + + { // check that std::ranges::dangling is returned + [[maybe_unused]] std::same_as decltype(auto) ret = + std::ranges::find_end(std::array {1, 2, 3, 4}, std::array {2, 3}); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search.pass.cpp @@ -0,0 +1,355 @@ +//===----------------------------------------------------------------------===// +// +// 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 S1, forward_iterator I2, +// sentinel_for S2, class Pred = ranges::equal_to, +// class Proj1 = identity, class Proj2 = identity> +// requires indirectly_comparable +// constexpr subrange +// ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); +// template +// requires indirectly_comparable, iterator_t, Pred, Proj1, Proj2> +// constexpr borrowed_subrange_t +// ranges::search(R1&& r1, R2&& r2, Pred pred = {}, +// Proj1 proj1 = {}, Proj2 proj2 = {}); + +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template +concept HasSearchIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { + std::ranges::search(first1, last1, first2, last2); +}; + +static_assert(HasSearchIt); +static_assert(!HasSearchIt); +static_assert(!HasSearchIt); +static_assert(!HasSearchIt); +static_assert(!HasSearchIt); // not indirectly comparable +static_assert(!HasSearchIt); +static_assert(!HasSearchIt); +static_assert(!HasSearchIt); +static_assert(!HasSearchIt); +static_assert(!HasSearchIt); + +template > +concept HasSearchR = requires (Range1 range1, Range2 range2) { + std::ranges::search(range1, range2); +}; + +static_assert(HasSearchR>); +static_assert(!HasSearchR); +static_assert(!HasSearchR); +static_assert(!HasSearchR); +static_assert(!HasSearchR); +static_assert(!HasSearchR, UncheckedRange>); // not indirectly comparable +static_assert(!HasSearchR, ForwardRangeNotDerivedFrom>); +static_assert(!HasSearchR, ForwardRangeNotIncrementable>); +static_assert(!HasSearchR, ForwardRangeNotSentinelSemiregular>); +static_assert(!HasSearchR, ForwardRangeNotSentinelEqualityComparableWith>); + +template +constexpr void test_iterators() { + { // simple test + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4}; + std::same_as> decltype(auto) ret = + std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2))); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 4); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2))); + std::same_as> decltype(auto) ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 4); + } + } + + { // matching part begins at the front + { + int a[] = {7, 5, 3, 7, 3, 6}; + int p[] = {7, 5, 3}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {7, 5, 3, 7, 3, 6}; + int p[] = {7, 5, 3}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } + + { // matching part ends at the back + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {4, 8}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 2))); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {4, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + } + + { // pattern does not match + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {1}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 1))); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {1}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + } + + { // range and pattern are identical + { + int a[] = {6, 7, 8, 9}; + int p[] = {6, 7, 8, 9}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 4)), Iter2(p), Sent2(Iter2(p + 4))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + { + int a[] = {6, 7, 8, 9}; + int p[] = {6, 7, 8, 9}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + } + + { // pattern is longer than range + { + int a[] = {6, 7, 8}; + int p[] = {6, 7, 8, 9}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p + 4))); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {6, 7, 8}; + int p[] = {6, 7, 8, 9}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + } + + { // pattern has zero length + { + int a[] = {6, 7, 8}; + int p[] = {}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + { + int a[] = {6, 7, 8}; + int p[] = {}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + } + + { // range has zero length + { + int a[] = {}; + int p[] = {6, 7, 8}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + { + int a[] = {}; + int p[] = {6, 7, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + } + + { // check that the first match is returned + { + int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8}; + int p[] = {6, 7, 8}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 9)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8}; + int p[] = {6, 7, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 9))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } + + { // check that the predicate is used + { + int a[] = {1, 2, 8, 1, 5, 6}; + int p[] = {7, 0, 4}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), + Iter2(p), Sent2(Iter2(p + 3)), + [](int l, int r) { return l > r; }); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {1, 2, 8, 1, 5, 6}; + int p[] = {7, 0, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::search(range1, range2, [](int l, int r) { return l > r; }); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 5); + } + } + + { // check that the projections are used + { + int a[] = {1, 3, 5, 1, 5, 6}; + int p[] = {2, 3, 4}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), + Iter2(p), Sent2(Iter2(p + 3)), + {}, + [](int i) { return i + 3; }, + [](int i) { return i * 2; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {1, 3, 5, 1, 5, 6}; + int p[] = {2, 3, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::search(range1, + range2, + {}, + [](int i) { return i + 3; }, + [](int i) { return i * 2; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } +} + +template +constexpr void test_iterators2() { + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators(); +} + +constexpr bool test() { + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2(); + + { // check that std::invoke is used + struct S { + int i; + + constexpr S identity() { + return *this; + } + + constexpr bool compare(const S& s) { + return i == s.i; + } + }; + { + S a[] = {{1}, {2}, {3}, {4}}; + S p[] = {{2}, {3}}; + auto ret = std::ranges::search(a, a + 4, p, p + 2, &S::compare, &S::identity, &S::identity); + assert(ret.begin() == a + 1); + assert(ret.end() == a + 3); + } + { + S a[] = {{1}, {2}, {3}, {4}}; + S p[] = {{2}, {3}}; + auto ret = std::ranges::search(a, p, &S::compare, &S::identity, &S::identity); + assert(ret.begin() == a + 1); + assert(ret.end() == a + 3); + } + } + + { // check that std::ranges::dangling is returned + [[maybe_unused]] std::same_as decltype(auto) ret = + std::ranges::search(std::array {1, 2, 3, 4}, std::array {2, 3}); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp @@ -0,0 +1,298 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S, class T, +// class Pred = ranges::equal_to, class Proj = identity> +// requires indirectly_comparable +// constexpr subrange +// ranges::search_n(I first, S last, iter_difference_t count, +// const T& value, Pred pred = {}, Proj proj = {}); +// template +// requires indirectly_comparable, const T*, Pred, Proj> +// constexpr borrowed_subrange_t +// ranges::search_n(R&& r, range_difference_t count, +// const T& value, Pred pred = {}, Proj proj = {}); + +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "test_iterators.h" + +template +concept HasSearchNIt = requires (Iter1 first1, Sent1 last1) { + std::ranges::search_n(first1, last1, 0, 0); +}; + +static_assert(HasSearchNIt); +static_assert(!HasSearchNIt); +static_assert(!HasSearchNIt); +static_assert(!HasSearchNIt); +static_assert(!HasSearchNIt); +static_assert(!HasSearchNIt); // not indirectly comparable + +template > +concept HasSearchNR = requires (Range1 range) { + std::ranges::search_n(range, 0, 0); +}; + +static_assert(HasSearchNR>); +static_assert(!HasSearchNR); +static_assert(!HasSearchNR); +static_assert(!HasSearchNR); +static_assert(!HasSearchNR); +static_assert(!HasSearchNR>); // not indirectly comparable + +template +constexpr void test_iterators() { + { // simple test + { + int a[] = {1, 2, 3, 4, 5, 6}; + std::same_as> decltype(auto) ret = + std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 1, 3); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); + std::same_as> decltype(auto) ret = std::ranges::search_n(range, 1, 3); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 3); + } + } + + { // matching part begins at the front + { + int a[] = {7, 7, 3, 7, 3, 6}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 2, 7); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 2); + } + { + int a[] = {7, 7, 3, 7, 3, 6}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); + auto ret = std::ranges::search_n(range, 2, 7); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 2); + } + } + + { // matching part ends at the back + { + int a[] = {9, 3, 6, 4, 4}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 2, 4); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 4}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5))); + auto ret = std::ranges::search_n(range, 2, 4); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + } + + { // pattern does not match + { + int a[] = {9, 3, 6, 4, 8}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 1, 1); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 8}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5))); + auto ret = std::ranges::search_n(range, 1, 1); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + } + + { // range and pattern are identical + { + int a[] = {1, 1, 1, 1}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 4)), 4, 1); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + { + int a[] = {1, 1, 1, 1}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 4))); + auto ret = std::ranges::search_n(range, 4, 1); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + } + + { // pattern is longer than range + { + int a[] = {3, 3, 3}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 4, 3); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {3, 3, 3}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3))); + auto ret = std::ranges::search_n(range, 4, 3); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + } + + { // pattern has zero length + { + int a[] = {6, 7, 8}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 0, 7); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + { + int a[] = {6, 7, 8}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3))); + auto ret = std::ranges::search_n(range, 0, 7); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + } + + { // range has zero length + { + int a[] = {}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a)), 1, 1); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + { + int a[] = {}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a))); + auto ret = std::ranges::search_n(range, 1, 1); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + } + + { // check that the first match is returned + { + int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 9)), 2, 6); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 2); + } + { + int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 9))); + auto ret = std::ranges::search_n(range, 2, 6); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 2); + } + } + + { // check that the predicate is used + { + int a[] = {1, 4, 4, 3, 6, 1}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), + 3, + 4, + [](int l, int r) { return l == r || l == 1; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {1, 4, 4, 3, 6, 1}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); + auto ret = std::ranges::search_n(range, 3, 4, [](int l, int r) { return l == r || l == 1; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } + + { // check that the projections are used + { + int a[] = {1, 3, 1, 6, 5, 6}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), + 3, + 6, + {}, + [](int i) { return i % 2 == 0 ? i : i + 1; }); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 6); + } + { + int a[] = {1, 3, 1, 6, 5, 6}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); + auto ret = std::ranges::search_n(range, + 3, + 6, + {}, + [](int i) { return i % 2 == 0 ? i : i + 1; }); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 6); + } + } +} +constexpr bool test() { + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators(); + + { // check that std::invoke is used + struct S { + int i; + + constexpr S identity() { + return *this; + } + + constexpr bool compare(int o) { + return i == o; + } + }; + { + S a[] = {{1}, {2}, {3}, {4}}; + auto ret = std::ranges::search_n(a, a + 4, 1, 2, &S::compare, &S::identity); + assert(ret.begin() == a + 1); + assert(ret.end() == a + 2); + } + { + S a[] = {{1}, {2}, {3}, {4}}; + auto ret = std::ranges::search_n(a, 1, 2, &S::compare, &S::identity); + assert(ret.begin() == a + 1); + assert(ret.end() == a + 2); + } + } + + { // check that std::ranges::dangling is returned + [[maybe_unused]] std::same_as decltype(auto) ret = + std::ranges::search_n(std::array {1, 2, 3, 4}, 1, 0); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} 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 @@ -77,7 +77,7 @@ static_assert(test(std::ranges::fill, a, 42)); static_assert(test(std::ranges::fill_n, a, 10, 42)); static_assert(test(std::ranges::find, a, 42)); -//static_assert(test(std::ranges::find_end, a, a)); +static_assert(test(std::ranges::find_end, a, a)); //static_assert(test(std::ranges::find_first_of, a, a)); static_assert(test(std::ranges::find_if, a, odd)); static_assert(test(std::ranges::find_if_not, a, odd)); @@ -130,8 +130,8 @@ //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)); -//static_assert(test(std::ranges::search, a, a)); -//static_assert(test(std::ranges::search_n, a, 10, 42)); +static_assert(test(std::ranges::search, a, a)); +static_assert(test(std::ranges::search_n, a, 10, 42)); //static_assert(test(std::ranges::set_difference, a, a, a)); //static_assert(test(std::ranges::set_intersection, a, a, a)); //static_assert(test(std::ranges::set_symmetric_difference, a, a, a));