diff options
22 files changed, 168 insertions, 1829 deletions
diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv index 34ff673a2ecf..44b240b314f9 100644 --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -23,9 +23,9 @@ Search,max_element,Nikolas Klauser,`D117523 <https://llvm.org/D117523>`_,✅ Search,minmax_element,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅ Search,count,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅ Search,count_if,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅ -Search,search,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅ -Search,search_n,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅ -Search,find_end,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅ +Search,search,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,Under review +Search,search_n,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,Under review +Search,find_end,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,Under review Read-only,is_partitioned,Nikolas Klauser,`D124440 <https://llvm.org/D124440>`_,✅ Read-only,is_sorted,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅ Read-only,is_sorted_until,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index 05c7c7b6bbcc..5af1f9439301 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -83,7 +83,6 @@ set(files __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 @@ -130,8 +129,6 @@ set(files __algorithm/ranges_reverse.h __algorithm/ranges_reverse_copy.h __algorithm/ranges_rotate_copy.h - __algorithm/ranges_search.h - __algorithm/ranges_search_n.h __algorithm/ranges_set_difference.h __algorithm/ranges_set_intersection.h __algorithm/ranges_set_union.h diff --git a/libcxx/include/__algorithm/find_end.h b/libcxx/include/__algorithm/find_end.h index 755b643c1180..0220c0939711 100644 --- a/libcxx/include/__algorithm/find_end.h +++ b/libcxx/include/__algorithm/find_end.h @@ -11,16 +11,8 @@ #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 <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -28,52 +20,35 @@ _LIBCPP_BEGIN_NAMESPACE_STD -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) { +template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> +_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred, forward_iterator_tag, + forward_iterator_tag) { // modeled after search algorithm - _Iter1 __match_first = _IterOps::next(__first1, __last1); // __last1 is the "default" answer - _Iter1 __match_last = __match_first; + _ForwardIterator1 __r = __last1; // __last1 is the "default" answer if (__first2 == __last2) - return pair<_Iter1, _Iter1>(__match_last, __match_last); + return __r; while (true) { while (true) { - 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))) + if (__first1 == __last1) // if source exhausted return last correct answer + return __r; // (or __last1 if never found) + if (__pred(*__first1, *__first2)) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _Iter1 __m1 = __first1; - _Iter2 __m2 = __first2; + _ForwardIterator1 __m1 = __first1; + _ForwardIterator2 __m2 = __first2; while (true) { if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one - __match_first = __first1; - __match_last = ++__m1; + __r = __first1; ++__first1; break; } if (++__m1 == __last1) // Source exhausted, return last answer - 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))) + return __r; + if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first { ++__first1; break; @@ -82,52 +57,33 @@ _LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter1> } } -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 __sent1, - _Iter2 __first2, - _Sent2 __sent2, - _Pred& __pred, - _Proj1& __proj1, - _Proj2& __proj2, - bidirectional_iterator_tag, - bidirectional_iterator_tag) { - auto __last1 = _IterOps::next(__first1, __sent1); - auto __last2 = _IterOps::next(__first2, __sent2); +template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2> +_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 __find_end( + _BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, + _BidirectionalIterator2 __last2, _BinaryPredicate __pred, bidirectional_iterator_tag, bidirectional_iterator_tag) { // modeled after search algorithm (in reverse) if (__first2 == __last2) return __last1; // Everything matches an empty sequence - _Iter1 __l1 = __last1; - _Iter2 __l2 = __last2; + _BidirectionalIterator1 __l1 = __last1; + _BidirectionalIterator2 __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 (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) + if (__pred(*--__l1, *__l2)) break; } // *__l1 matches *__l2, now match elements before here - _Iter1 __m1 = __l1; - _Iter2 __m2 = __l2; + _BidirectionalIterator1 __m1 = __l1; + _BidirectionalIterator2 __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 there is a mismatch, restart with a new __l1 - if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2))) + if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 { break; } // else there is a match, check next elements @@ -135,53 +91,37 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter1 __find_end( } } -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 __sent1, - _Iter2 __first2, - _Sent2 __sent2, - _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, __sent1); - auto __last2 = _IterOps::next(__first2, __sent2); +template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> +_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; // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - auto __len2 = __last2 - __first2; + _D2 __len2 = __last2 - __first2; if (__len2 == 0) return __last1; - auto __len1 = __last1 - __first1; + _D1 __len1 = __last1 - __first1; if (__len1 < __len2) return __last1; - const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here - _Iter1 __l1 = __last1; - _Iter2 __l2 = __last2; + const _RandomAccessIterator1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here + _RandomAccessIterator1 __l1 = __last1; + _RandomAccessIterator2 __l2 = __last2; --__l2; while (true) { while (true) { if (__s == __l1) return __last1; - if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) + if (__pred(*--__l1, *__l2)) break; } - _Iter1 __m1 = __l1; - _Iter2 __m2 = __l2; + _RandomAccessIterator1 __m1 = __l1; + _RandomAccessIterator2 __m2 = __l2; while (true) { if (__m2 == __first2) return __m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) { + if (!__pred(*--__m1, *--__m2)) { break; } } @@ -189,39 +129,20 @@ _LIBCPP_CONSTEXPR_AFTER_CXX11 _Iter1 __find_end( } template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 -_ForwardIterator1 __find_end_classic(_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 <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -_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) { - return std::__find_end_classic(__first1, __last1, __first2, __last2, __pred); +_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()); } template <class _ForwardIterator1, class _ForwardIterator2> -_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_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_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h index 4c4f406efe81..bccac368f302 100644 --- a/libcxx/include/__algorithm/iterator_operations.h +++ b/libcxx/include/__algorithm/iterator_operations.h @@ -39,7 +39,6 @@ struct _IterOps<_RangeAlgPolicy> { static constexpr auto __iter_move = ranges::iter_move; static constexpr auto iter_swap = ranges::iter_swap; static constexpr auto next = ranges::next; - static constexpr auto __advance_to = ranges::advance; }; #endif diff --git a/libcxx/include/__algorithm/ranges_find_end.h b/libcxx/include/__algorithm/ranges_find_end.h deleted file mode 100644 index 5c301b35abbd..000000000000 --- a/libcxx/include/__algorithm/ranges_find_end.h +++ /dev/null @@ -1,113 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___ALGORITHM_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 <class _Iter> -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 <class _Iter> -using __iterator_concept = decltype(__get_iterator_concept<_Iter>()); - -namespace ranges { -namespace __find_end { -struct __fn { - template <forward_iterator _Iter1, sentinel_for<_Iter1> _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 <forward_range _Range1, - forward_range _Range2, - class _Pred = ranges::equal_to, - class _Proj1 = identity, - class _Proj2 = identity> - requires indirectly_comparable<iterator_t<_Range1>, 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_t<_Range1>>(), - __iterator_concept<iterator_t<_Range2>>()); - 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 deleted file mode 100644 index a7b7695d280f..000000000000 --- a/libcxx/include/__algorithm/ranges_search.h +++ /dev/null @@ -1,134 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___ALGORITHM_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 <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2> - _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 <forward_iterator _Iter1, sentinel_for<_Iter1> _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 <forward_range _Range1, - forward_range _Range2, - class _Pred = ranges::equal_to, - class _Proj1 = identity, - class _Proj2 = identity> - requires indirectly_comparable<iterator_t<_Range1>, 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 deleted file mode 100644 index d7178ca415b1..000000000000 --- a/libcxx/include/__algorithm/ranges_search_n.h +++ /dev/null @@ -1,120 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___ALGORITHM_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 <__iterator/iterator_traits.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 <class _Iter1, class _Sent1, class _SizeT, class _Type, class _Pred, class _Proj> - _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 <forward_iterator _Iter, sentinel_for<_Iter> _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 <forward_range _Range, class _Type, class _Pred = ranges::equal_to, class _Proj = identity> - requires indirectly_comparable<iterator_t<_Range>, 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<range_size_t<_Range>>(__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 index b5c4820e5daa..d89ec2b1c5bc 100644 --- a/libcxx/include/__algorithm/search.h +++ b/libcxx/include/__algorithm/search.h @@ -11,15 +11,9 @@ #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 <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -27,43 +21,31 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _IterOps, - class _Iter1, class _Sent1, - class _Iter2, class _Sent2, - class _Pred, - class _Proj1, - class _Proj2> -_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) { +template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> +pair<_ForwardIterator1, _ForwardIterator1> + _LIBCPP_CONSTEXPR_AFTER_CXX11 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { if (__first2 == __last2) - return std::make_pair(__first1, __first1); // Everything matches an empty sequence + return _VSTD::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 - _IterOps::__advance_to(__first1, __last1); - return std::make_pair(__first1, __first1); - } - if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) + if (__first1 == __last1) // return __last1 if no element matches *__first2 + return _VSTD::make_pair(__last1, __last1); + if (__pred(*__first1, *__first2)) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _Iter1 __m1 = __first1; - _Iter2 __m2 = __first2; + _ForwardIterator1 __m1 = __first1; + _ForwardIterator2 __m2 = __first2; while (true) { if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) - 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))) + 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 { ++__first1; break; @@ -72,42 +54,38 @@ pair<_Iter1, _Iter1> __search_forward_impl(_Iter1 __first1, _Sent1 __last1, } } -template <class _IterOps, - class _Iter1, class _Sent1, - class _Iter2, class _Sent2, - class _Pred, - class _Proj1, - class _Proj2, - class _DiffT1, - class _DiffT2> -_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 +template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> +_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 while (true) { while (true) { - 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))) + if (__first1 == __s) + return _VSTD::make_pair(__last1, __last1); + if (__pred(*__first1, *__first2)) break; ++__first1; } - _Iter1 __m1 = __first1; - _Iter2 __m2 = __first2; + _RandomAccessIterator1 __m1 = __first1; + _RandomAccessIterator2 __m2 = __first2; while (true) { if (++__m2 == __last2) - return std::make_pair(__first1, __first1 + _DiffT1(__size2)); + return _VSTD::make_pair(__first1, __first1 + _D1(__len2)); ++__m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { + if (!__pred(*__m1, *__m2)) { ++__first1; break; } @@ -115,78 +93,22 @@ pair<_Iter1, _Iter1> __search_random_access_impl(_Iter1 __first1, _Sent1 __last1 } } -template <class _Iter1, class _Sent1, - class _Iter2, class _Sent2, - class _Pred, - class _Proj1, - class _Proj2> -_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 <class _Iter1, class _Sent1, - class _Iter2, class _Sent2, - class _Pred, - class _Proj1, - class _Proj2> -_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 <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -_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; +_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; } template <class _ForwardIterator1, class _ForwardIterator2> -_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>()); +_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>()); } #if _LIBCPP_STD_VER > 14 diff --git a/libcxx/include/__algorithm/search_n.h b/libcxx/include/__algorithm/search_n.h index 2a9285f4efe5..c51701415bdc 100644 --- a/libcxx/include/__algorithm/search_n.h +++ b/libcxx/include/__algorithm/search_n.h @@ -11,15 +11,8 @@ #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 <type_traits> // __convert_to_integral #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -28,39 +21,30 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _IterOps, class _Pred, class _Iter, class _Sent, class _SizeT, class _Type, class _Proj> -_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) { +template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp> +_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, + _Size __count, const _Tp& __value, _BinaryPredicate __pred, + forward_iterator_tag) { if (__count <= 0) - return std::make_pair(__first, __first); + return __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 - _IterOps::__advance_to(__first, __last); - return std::make_pair(__first, __first); - } - if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value)) + if (__first == __last) // return __last if no element matches __value_ + return __last; + if (__pred(*__first, __value)) break; ++__first; } - // *__first matches __value, now match elements after here - _Iter __m = __first; - _SizeT __c(0); + // *__first matches __value_, now match elements after here + _ForwardIterator __m = __first; + _Size __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - 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)) + 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 { __first = __m; ++__first; @@ -70,44 +54,35 @@ pair<_Iter, _Iter> __search_n_forward_impl(_Iter __first, _Sent __last, } } -template <class _IterOps, class _Pred, class _Iter, class _Sent, class _SizeT, class _Type, class _Proj, class _DiffT> -_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 std::make_pair(__first, __first); - if (__size1 < static_cast<_DiffT>(__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 +template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp> +_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; + 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 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 - _IterOps::__advance_to(__first, __last); - return std::make_pair(__first, __first); - } - if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value)) + if (__first >= __s) // return __last if no element matches __value_ + return __last; + if (__pred(*__first, __value)) break; ++__first; } // *__first matches __value_, now match elements after here - auto __m = __first; - _SizeT __c(0); + _RandomAccessIterator __m = __first; + _Size __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - 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)) + 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 { __first = __m; ++__first; @@ -117,63 +92,19 @@ std::pair<_Iter, _Iter> __search_n_random_access_impl(_Iter __first, _Sent __las } } -template <class _Iter, class _Sent, - class _DiffT, - class _Type, - class _Pred, - class _Proj> -_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 <class _Iter1, class _Sent1, - class _DiffT, - class _Type, - class _Pred, - class _Proj> -_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 <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate> -_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; +_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()); } template <class _ForwardIterator, class _Size, class _Tp> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value) { +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _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 std::search_n(__first, __last, std::__convert_to_integral(__count), __value, __equal_to<__v, _Tp>()); + return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value, __equal_to<__v, _Tp>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_intersection.h b/libcxx/include/__algorithm/set_intersection.h index e0f5bd140be7..650705703219 100644 --- a/libcxx/include/__algorithm/set_intersection.h +++ b/libcxx/include/__algorithm/set_intersection.h @@ -14,7 +14,6 @@ #include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/iterator_traits.h> -#include <__iterator/next.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) diff --git a/libcxx/include/__functional/default_searcher.h b/libcxx/include/__functional/default_searcher.h index 8e37082b6bed..05fb23d7c3c4 100644 --- a/libcxx/include/__functional/default_searcher.h +++ b/libcxx/include/__functional/default_searcher.h @@ -12,7 +12,6 @@ #include <__algorithm/search.h> #include <__config> -#include <__functional/identity.h> #include <__functional/operations.h> #include <__iterator/iterator_traits.h> #include <__utility/pair.h> @@ -39,15 +38,16 @@ public: pair<_ForwardIterator2, _ForwardIterator2> operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { - auto __proj = __identity(); - return std::__search_impl(__f, __l, __first_, __last_, __pred_, __proj, __proj); + return _VSTD::__search(__f, __l, __first_, __last_, __pred_, + typename iterator_traits<_ForwardIterator>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()); } 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 index 63525e230add..1fbdc955d148 100644 --- a/libcxx/include/__iterator/iterator_traits.h +++ b/libcxx/include/__iterator/iterator_traits.h @@ -481,12 +481,6 @@ struct __is_exactly_cpp17_forward_iterator __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value && !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value> {}; -template <class _Tp> -struct __is_exactly_cpp17_bidirectional_iterator - : public integral_constant<bool, - __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value && - !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value> {}; - template<class _InputIterator> using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; diff --git a/libcxx/include/__string/char_traits.h b/libcxx/include/__string/char_traits.h index 18ad67b28e16..457a771b94cf 100644 --- a/libcxx/include/__string/char_traits.h +++ b/libcxx/include/__string/char_traits.h @@ -802,7 +802,9 @@ __str_rfind(const _CharT *__p, _SizeT __sz, __pos += __n; else __pos = __sz; - const _CharT* __r = std::__find_end_classic(__p, __p + __pos, __s, __s + __n, _Traits::eq); + const _CharT* __r = _VSTD::__find_end( + __p, __p + __pos, __s, __s + __n, _Traits::eq, + random_access_iterator_tag(), random_access_iterator_tag()); if (__n > 0 && __r == __p + __pos) return __npos; return static_cast<_SizeT>(__r - __p); diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 18d8ef3805e5..387aebe78e6c 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -649,49 +649,6 @@ namespace ranges { constexpr ranges::rotate_copy_result<borrowed_iterator_t<R>, O> ranges::rotate_copy(R&& r, iterator_t<R> middle, O result); // since C++20 - template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, - sentinel_for<I2> S2, class Pred = ranges::equal_to, - class Proj1 = identity, class Proj2 = identity> - requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> - constexpr subrange<I1> - ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, - Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - - template<forward_range R1, forward_range R2, class Pred = ranges::equal_to, - class Proj1 = identity, class Proj2 = identity> - requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> - constexpr borrowed_subrange_t<R1> - ranges::search(R1&& r1, R2&& r2, Pred pred = {}, - Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - - template<forward_iterator I, sentinel_for<I> S, class T, - class Pred = ranges::equal_to, class Proj = identity> - requires indirectly_comparable<I, const T*, Pred, Proj> - constexpr subrange<I> - ranges::search_n(I first, S last, iter_difference_t<I> count, - const T& value, Pred pred = {}, Proj proj = {}); // since C++20 - - template<forward_range R, class T, class Pred = ranges::equal_to, - class Proj = identity> - requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj> - constexpr borrowed_subrange_t<R> - ranges::search_n(R&& r, range_difference_t<R> count, - const T& value, Pred pred = {}, Proj proj = {}); // since C++20 - - template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2, - class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> - requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> - constexpr subrange<I1> - ranges::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, - Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - - template<forward_range R1, forward_range R2, - class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> - requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> - constexpr borrowed_subrange_t<R1> - ranges::find_end(R1&& r1, R2&& r2, Pred pred = {}, - Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 - } constexpr bool // constexpr in C++20 @@ -1435,7 +1392,6 @@ template <class BidirectionalIterator, class Compare> #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> @@ -1468,8 +1424,6 @@ template <class BidirectionalIterator, class Compare> #include <__algorithm/ranges_reverse.h> #include <__algorithm/ranges_reverse_copy.h> #include <__algorithm/ranges_rotate_copy.h> -#include <__algorithm/ranges_search.h> -#include <__algorithm/ranges_search_n.h> #include <__algorithm/ranges_set_difference.h> #include <__algorithm/ranges_set_intersection.h> #include <__algorithm/ranges_sort.h> diff --git a/libcxx/include/experimental/functional b/libcxx/include/experimental/functional index 12440744ca50..04f195d3cf24 100644 --- a/libcxx/include/experimental/functional +++ b/libcxx/include/experimental/functional @@ -62,7 +62,6 @@ inline namespace fundamentals_v1 { #include <__assert> // all public C++ headers provide the assertion handler #include <__debug> -#include <__functional/identity.h> #include <__memory/uses_allocator.h> #include <array> #include <experimental/__config> @@ -105,8 +104,9 @@ public: pair<_ForwardIterator2, _ForwardIterator2> operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { - auto __proj = __identity(); - return std::__search_impl(__f, __l, __first_, __last_, __pred_, __proj, __proj); + return _VSTD::__search(__f, __l, __first_, __last_, __pred_, + typename iterator_traits<_ForwardIterator>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()); } private: diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in index c0ecfac991fd..8efeb1fc4926 100644 --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -322,7 +322,6 @@ module std [system] { 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" } @@ -369,8 +368,6 @@ module std [system] { module ranges_reverse { private header "__algorithm/ranges_reverse.h" } module ranges_reverse_copy { private header "__algorithm/ranges_reverse_copy.h" } module ranges_rotate_copy { private header "__algorithm/ranges_rotate_copy.h" } - module ranges_search { private header "__algorithm/ranges_search.h" } - module ranges_search_n { private header "__algorithm/ranges_search_n.h" } module ranges_set_difference { private header "__algorithm/ranges_set_difference.h" } module ranges_set_intersection { private header "__algorithm/ranges_set_intersection.h" } module ranges_set_union { private header "__algorithm/ranges_set_union.h" } diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp index 0eec04b7837d..3be1011acf51 100644 --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -84,7 +84,7 @@ constexpr bool all_the_algorithms() 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 @@ constexpr bool all_the_algorithms() (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 @@ constexpr bool all_the_algorithms() //(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 index f46a967809c1..06e3c21eb774 100644 --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -120,7 +120,6 @@ END-SCRIPT #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'}} @@ -167,8 +166,6 @@ END-SCRIPT #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}} #include <__algorithm/ranges_reverse_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse_copy.h'}} #include <__algorithm/ranges_rotate_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_rotate_copy.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_set_difference.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_difference.h'}} #include <__algorithm/ranges_set_intersection.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_intersection.h'}} #include <__algorithm/ranges_set_union.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_union.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 deleted file mode 100644 index bfef8ad13a1b..000000000000 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp +++ /dev/null @@ -1,354 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -// <algorithm> - -// UNSUPPORTED: c++03, c++11, c++14, c++17 -// UNSUPPORTED: libcpp-has-no-incomplete-ranges - -// template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2, -// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> -// requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> -// constexpr subrange<I1> -// ranges::find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, -// Proj1 proj1 = {}, Proj2 proj2 = {}); -// template<forward_range R1, forward_range R2, -// class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> -// requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> -// constexpr borrowed_subrange_t<R1> -// ranges::find_end(R1&& r1, R2&& r2, Pred pred = {}, -// Proj1 proj1 = {}, Proj2 proj2 = {}); - -#include <algorithm> -#include <array> -#include <ranges> - -#include "almost_satisfies_types.h" -#include "test_iterators.h" - -template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2> -concept HasFindEndIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { - std::ranges::find_end(first1, last1, first2, last2); -}; - -static_assert(HasFindEndIt<int*>); -static_assert(!HasFindEndIt<ForwardIteratorNotDerivedFrom>); -static_assert(!HasFindEndIt<ForwardIteratorNotIncrementable>); -static_assert(!HasFindEndIt<int*, SentinelForNotSemiregular>); -static_assert(!HasFindEndIt<int*, int*, int**>); // not indirectly comparable -static_assert(!HasFindEndIt<int*, SentinelForNotWeaklyEqualityComparableWith>); -static_assert(!HasFindEndIt<int*, int*, ForwardIteratorNotDerivedFrom>); -static_assert(!HasFindEndIt<int*, int*, ForwardIteratorNotIncrementable>); -static_assert(!HasFindEndIt<int*, int*, int*, SentinelForNotSemiregular>); -static_assert(!HasFindEndIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>); - -template <class Range1, class Range2 = UncheckedRange<int*>> -concept HasFindEndR = requires (Range1 range1, Range2 range2) { - std::ranges::find_end(range1, range2); -}; - -static_assert(HasFindEndR<UncheckedRange<int*>>); -static_assert(!HasFindEndR<ForwardRangeNotDerivedFrom>); -static_assert(!HasFindEndR<ForwardIteratorNotIncrementable>); -static_assert(!HasFindEndR<ForwardRangeNotSentinelSemiregular>); -static_assert(!HasFindEndR<ForwardRangeNotSentinelEqualityComparableWith>); -static_assert(!HasFindEndR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable -static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>); -static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotIncrementable>); -static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>); -static_assert(!HasFindEndR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>); - -template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2> -constexpr void test_iterators() { - { // simple test - { - int a[] = {1, 2, 3, 4, 5, 6}; - int p[] = {3, 4}; - std::same_as<std::ranges::subrange<Iter1, Iter1>> 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<std::ranges::subrange<Iter1, Iter1>> 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 <class Iter1, class Sent1 = Iter1> -constexpr void test_iterators2() { - test_iterators<Iter1, Sent1, forward_iterator<int*>>(); - test_iterators<Iter1, Sent1, forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>(); - test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>(); - test_iterators<Iter1, Sent1, bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>(); - test_iterators<Iter1, Sent1, random_access_iterator<int*>>(); - test_iterators<Iter1, Sent1, random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>(); - test_iterators<Iter1, Sent1, contiguous_iterator<int*>>(); - test_iterators<Iter1, Sent1, contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>(); - test_iterators<Iter1, Sent1, int*>(); -} - -constexpr bool test() { - test_iterators2<forward_iterator<int*>>(); - test_iterators2<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>(); - test_iterators2<bidirectional_iterator<int*>>(); - test_iterators2<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>(); - test_iterators2<random_access_iterator<int*>>(); - test_iterators2<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>(); - test_iterators2<contiguous_iterator<int*>>(); - test_iterators2<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>(); - test_iterators2<int*>(); - - { // 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<std::ranges::dangling> 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 deleted file mode 100644 index c8c7eab66392..000000000000 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search.pass.cpp +++ /dev/null @@ -1,355 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -// <algorithm> - -// UNSUPPORTED: c++03, c++11, c++14, c++17 -// UNSUPPORTED: libcpp-has-no-incomplete-ranges - -// template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, -// sentinel_for<I2> S2, class Pred = ranges::equal_to, -// class Proj1 = identity, class Proj2 = identity> -// requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> -// constexpr subrange<I1> -// ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, -// Proj1 proj1 = {}, Proj2 proj2 = {}); -// template<forward_range R1, forward_range R2, class Pred = ranges::equal_to, -// class Proj1 = identity, class Proj2 = identity> -// requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> -// constexpr borrowed_subrange_t<R1> -// ranges::search(R1&& r1, R2&& r2, Pred pred = {}, -// Proj1 proj1 = {}, Proj2 proj2 = {}); - -#include <algorithm> -#include <array> -#include <ranges> - -#include "almost_satisfies_types.h" -#include "test_iterators.h" - -template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2> -concept HasSearchIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { - std::ranges::search(first1, last1, first2, last2); -}; - -static_assert(HasSearchIt<int*>); -static_assert(!HasSearchIt<ForwardIteratorNotDerivedFrom>); -static_assert(!HasSearchIt<ForwardIteratorNotIncrementable>); -static_assert(!HasSearchIt<int*, SentinelForNotSemiregular>); -static_assert(!HasSearchIt<int*, int*, int**>); // not indirectly comparable -static_assert(!HasSearchIt<int*, SentinelForNotWeaklyEqualityComparableWith>); -static_assert(!HasSearchIt<int*, int*, ForwardIteratorNotDerivedFrom>); -static_assert(!HasSearchIt<int*, int*, ForwardIteratorNotIncrementable>); -static_assert(!HasSearchIt<int*, int*, int*, SentinelForNotSemiregular>); -static_assert(!HasSearchIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>); - -template <class Range1, class Range2 = UncheckedRange<int*>> -concept HasSearchR = requires (Range1 range1, Range2 range2) { - std::ranges::search(range1, range2); -}; - -static_assert(HasSearchR<UncheckedRange<int*>>); -static_assert(!HasSearchR<ForwardRangeNotDerivedFrom>); -static_assert(!HasSearchR<ForwardIteratorNotIncrementable>); -static_assert(!HasSearchR<ForwardRangeNotSentinelSemiregular>); -static_assert(!HasSearchR<ForwardRangeNotSentinelEqualityComparableWith>); -static_assert(!HasSearchR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable -static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>); -static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotIncrementable>); -static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>); -static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>); - -template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2> -constexpr void test_iterators() { - { // simple test - { - int a[] = {1, 2, 3, 4, 5, 6}; - int p[] = {3, 4}; - std::same_as<std::ranges::subrange<Iter1, Iter1>> 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<std::ranges::subrange<Iter1, Iter1>> 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 <class Iter1, class Sent1 = Iter1> -constexpr void test_iterators2() { - test_iterators<Iter1, Sent1, forward_iterator<int*>>(); - test_iterators<Iter1, Sent1, forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>(); - test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>(); - test_iterators<Iter1, Sent1, bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>(); - test_iterators<Iter1, Sent1, random_access_iterator<int*>>(); - test_iterators<Iter1, Sent1, random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>(); - test_iterators<Iter1, Sent1, contiguous_iterator<int*>>(); - test_iterators<Iter1, Sent1, contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>(); - test_iterators<Iter1, Sent1, int*>(); -} - -constexpr bool test() { - test_iterators2<forward_iterator<int*>>(); - test_iterators2<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>(); - test_iterators2<bidirectional_iterator<int*>>(); - test_iterators2<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>(); - test_iterators2<random_access_iterator<int*>>(); - test_iterators2<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>(); - test_iterators2<contiguous_iterator<int*>>(); - test_iterators2<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>(); - test_iterators2<int*>(); - - { // 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<std::ranges::dangling> 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 deleted file mode 100644 index 2d456a07e36c..000000000000 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp +++ /dev/null @@ -1,298 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -// <algorithm> - -// UNSUPPORTED: c++03, c++11, c++14, c++17 -// UNSUPPORTED: libcpp-has-no-incomplete-ranges - -// template<forward_iterator I, sentinel_for<I> S, class T, -// class Pred = ranges::equal_to, class Proj = identity> -// requires indirectly_comparable<I, const T*, Pred, Proj> -// constexpr subrange<I> -// ranges::search_n(I first, S last, iter_difference_t<I> count, -// const T& value, Pred pred = {}, Proj proj = {}); -// template<forward_range R, class T, class Pred = ranges::equal_to, -// class Proj = identity> -// requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj> -// constexpr borrowed_subrange_t<R> -// ranges::search_n(R&& r, range_difference_t<R> count, -// const T& value, Pred pred = {}, Proj proj = {}); - -#include <algorithm> -#include <array> -#include <ranges> - -#include "almost_satisfies_types.h" -#include "test_iterators.h" - -template <class Iter1, class Sent1 = Iter1> -concept HasSearchNIt = requires (Iter1 first1, Sent1 last1) { - std::ranges::search_n(first1, last1, 0, 0); -}; - -static_assert(HasSearchNIt<int*>); -static_assert(!HasSearchNIt<ForwardIteratorNotDerivedFrom>); -static_assert(!HasSearchNIt<ForwardIteratorNotIncrementable>); -static_assert(!HasSearchNIt<int*, SentinelForNotSemiregular>); -static_assert(!HasSearchNIt<int*, SentinelForNotWeaklyEqualityComparableWith>); -static_assert(!HasSearchNIt<int**, int**>); // not indirectly comparable - -template <class Range1, class Range2 = UncheckedRange<int*>> -concept HasSearchNR = requires (Range1 range) { - std::ranges::search_n(range, 0, 0); -}; - -static_assert(HasSearchNR<UncheckedRange<int*>>); -static_assert(!HasSearchNR<ForwardRangeNotDerivedFrom>); -static_assert(!HasSearchNR<ForwardIteratorNotIncrementable>); -static_assert(!HasSearchNR<ForwardRangeNotSentinelSemiregular>); -static_assert(!HasSearchNR<ForwardRangeNotSentinelEqualityComparableWith>); -static_assert(!HasSearchNR<UncheckedRange<int**>>); // not indirectly comparable - -template <class Iter, class Sent = Iter> -constexpr void test_iterators() { - { // simple test - { - int a[] = {1, 2, 3, 4, 5, 6}; - std::same_as<std::ranges::subrange<Iter, Iter>> 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<std::ranges::subrange<Iter, Iter>> 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<forward_iterator<int*>>(); - test_iterators<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>(); - test_iterators<bidirectional_iterator<int*>>(); - test_iterators<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>(); - test_iterators<random_access_iterator<int*>>(); - test_iterators<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>(); - test_iterators<contiguous_iterator<int*>>(); - test_iterators<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>(); - test_iterators<int*>(); - - { // 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<std::ranges::dangling> 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 index 8574886e3d77..e8c0349519d1 100644 --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -78,7 +78,7 @@ static_assert(test(std::ranges::equal, a, a)); 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)); @@ -131,8 +131,8 @@ static_assert(test(std::ranges::reverse_copy, a, a)); //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)); |