diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -23,9 +23,9 @@ Search,minmax_element,Nikolas Klauser,`D120637 `_,✅ Search,count,Nikolas Klauser, `D121523 `_,✅ Search,count_if,Nikolas Klauser, `D121523 `_,✅ -Search,search,Not assigned,n/a,Not started -Search,search_n,Not assigned,n/a,Not started -Search,find_end,Not assigned,n/a,Not started +Search,search,Nikolas Klauser,`D124079 `_,✅ +Search,search_n,Nikolas Klauser,`D124079 `_,✅ +Search,find_end,Nikolas Klauser,`D124079 `_,✅ Read-only,is_partitioned,Christopher Di Bella,`D105794 `_,Under review Read-only,is_sorted,Not assigned,n/a,Not started Read-only,is_sorted_unitl,Not assigned,n/a,Not started diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -73,6 +73,7 @@ __algorithm/ranges_count.h __algorithm/ranges_count_if.h __algorithm/ranges_find.h + __algorithm/ranges_find_end.h __algorithm/ranges_find_if.h __algorithm/ranges_find_if_not.h __algorithm/ranges_max.h @@ -82,6 +83,8 @@ __algorithm/ranges_minmax.h __algorithm/ranges_minmax_element.h __algorithm/ranges_mismatch.h + __algorithm/ranges_search.h + __algorithm/ranges_search_n.h __algorithm/ranges_swap_ranges.h __algorithm/ranges_transform.h __algorithm/remove.h diff --git a/libcxx/include/__algorithm/find_end.h b/libcxx/include/__algorithm/find_end.h --- a/libcxx/include/__algorithm/find_end.h +++ b/libcxx/include/__algorithm/find_end.h @@ -11,8 +11,15 @@ #define _LIBCPP___ALGORITHM_FIND_END_OF_H #include <__algorithm/comp.h> +#include <__algorithm/search.h> #include <__config> +#include <__functional/identity.h> +#include <__iterator/advance.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/reverse_iterator.h> +#include <__utility/pair.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -20,35 +27,48 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred, forward_iterator_tag, - forward_iterator_tag) { +template +_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, + __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value + && __is_cpp17_forward_iterator<_Iter2>::value + && !(__is_cpp17_bidirectional_iterator<_Iter1>::value + && __is_cpp17_bidirectional_iterator<_Iter2>::value)>* = nullptr) { // modeled after search algorithm - _ForwardIterator1 __r = __last1; // __last1 is the "default" answer + _Iter1 __match_first = std::__next_to(__first1, __last1); // __last1 is the "default" answer + _Iter1 __match_last = __match_first; if (__first2 == __last2) - return __r; + return {__match_last, __match_last}; while (true) { while (true) { - if (__first1 == __last1) // if source exhausted return last correct answer - return __r; // (or __last1 if never found) - if (__pred(*__first1, *__first2)) + if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found) + return {__match_first, __match_last}; + if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _ForwardIterator1 __m1 = __first1; - _ForwardIterator2 __m2 = __first2; + _Iter1 __m1 = __first1; + _Iter2 __m2 = __first2; while (true) { if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one - __r = __first1; + __match_first = __first1; + __match_last = ++__m1; ++__first1; break; } if (++__m1 == __last1) // Source exhausted, return last answer - return __r; - if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first + return {__match_first, __match_last}; + // mismatch, restart with a new __first + if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { ++__first1; break; @@ -57,92 +77,51 @@ } } -template -_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 - _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 (__pred(*--__l1, *__l2)) - break; - } - // *__l1 matches *__l2, now match elements before here - _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 (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 - { - break; - } // else there is a match, check next elements - } - } -} - -template -_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end( - _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) { - typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; - typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; - // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - _D2 __len2 = __last2 - __first2; - if (__len2 == 0) - return __last1; - _D1 __len1 = __last1 - __first1; - if (__len1 < __len2) - return __last1; - const _RandomAccessIterator1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here - _RandomAccessIterator1 __l1 = __last1; - _RandomAccessIterator2 __l2 = __last2; - --__l2; - while (true) { - while (true) { - if (__s == __l1) - return __last1; - if (__pred(*--__l1, *__l2)) - break; - } - _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 (!__pred(*--__m1, *--__m2)) { - break; - } - } +template +_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, + __enable_if_t<__is_cpp17_bidirectional_iterator<_Iter1>::value + && __is_cpp17_bidirectional_iterator<_Iter2>::value>* = nullptr) { + auto __ret = std::__search_impl(std::__make_end_reverse_iterator(__first1, __last1), + std::__make_begin_reverse_iterator(__first1), + std::__make_end_reverse_iterator(__first2, __last2), + std::__make_begin_reverse_iterator(__first2), + __pred, + __proj1, + __proj2); + auto __ret_first = __ret.second.base(); + auto __ret_last = __ret.first.base(); + if (__ret_first == __ret_last) { + std::__advance_to(__first1, __last1); + return {__first1, __first1}; } + return {__ret_first, __ret_last}; } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred) { - return _VSTD::__find_end<_BinaryPredicate&>( - __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + auto __proj = __identity(); + return std::__find_end_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first; } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + using __v1 = typename iterator_traits<_ForwardIterator1>::value_type; + using __v2 = typename iterator_traits<_ForwardIterator2>::value_type; + return std::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_find_end.h b/libcxx/include/__algorithm/ranges_find_end.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_end.h @@ -0,0 +1,76 @@ +//===----------------------------------------------------------------------===// +// +// 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 <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/subrange.h> + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find_end { +struct __fn { + template _Sent1, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + class _Pred = ranges::equal_to, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__find_end_impl(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); + return {__ret.first, __ret.second}; + } + + template + requires indirectly_comparable, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range1> operator()(_Range1&& __range1, + _Range2&& __range2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__find_end_impl(ranges::begin(__range1), ranges::end(__range1), + ranges::begin(__range2), ranges::end(__range2), + __pred, + __proj1, + __proj2); + return {__ret.first, __ret.second}; + } +}; +} // namespace __find_end + +inline namespace __cpo { + inline constexpr auto find_end = __find_end::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_END_H diff --git a/libcxx/include/__algorithm/ranges_search.h b/libcxx/include/__algorithm/ranges_search.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_search.h @@ -0,0 +1,94 @@ +//===----------------------------------------------------------------------===// +// +// 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/search.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/size.h> +#include <__ranges/subrange.h> + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __search { +struct __fn { + + template _Sent1, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + class _Pred = ranges::equal_to, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); + return {__ret.first, __ret.second}; + } + + template + requires indirectly_comparable, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range1> operator()(_Range1&& __range1, + _Range2&& __range2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __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}; + } + } + } + + auto __ret = std::__search_impl(ranges::begin(__range1), ranges::end(__range1), + ranges::begin(__range2), ranges::end(__range2), + __pred, + __proj1, + __proj2); + return {__ret.first, __ret.second}; + } + +}; +} // namespace __search + +inline namespace __cpo { + inline constexpr auto search = __search::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_H diff --git a/libcxx/include/__algorithm/ranges_search_n.h b/libcxx/include/__algorithm/ranges_search_n.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_search_n.h @@ -0,0 +1,82 @@ +//===----------------------------------------------------------------------===// +// +// 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/search_n.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/size.h> +#include <__ranges/subrange.h> + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __search_n { +struct __fn { + + template _Sent, + class _Type, + class _Pred = ranges::equal_to, + class _Proj = identity> + requires indirectly_comparable<_Iter, const _Type*, _Pred, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter> operator()(_Iter __first, _Sent __last, + iter_difference_t<_Iter> __count, + const _Type& __value, + _Pred __pred = {}, + _Proj __proj = _Proj{}) const { + auto __ret = std::__search_n_impl(__first, __last, __count, __value, __pred, __proj); + return {__ret.first, __ret.second}; + } + + template + requires indirectly_comparable, const _Type*, _Pred, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, + range_difference_t<_Range> __count, + const _Type& __value, + _Pred __pred = {}, + _Proj __proj = {}) const { + auto __first = ranges::begin(__range); + if (__count <= 0) + return {__first, __first}; + if constexpr (sized_range<_Range>) { + auto __size1 = ranges::size(__range); + if (__size1 < static_cast>(__count)) { + ranges::advance(__first, ranges::end(__range)); + return {__first, __first}; + } + } + + auto __ret = std::__search_n_impl(ranges::begin(__range), ranges::end(__range), __count, __value, __pred, __proj); + return {__ret.first, __ret.second}; + } +}; +} // namespace __search_n + +inline namespace __cpo { + inline constexpr auto search_n = __search_n::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H diff --git a/libcxx/include/__algorithm/search.h b/libcxx/include/__algorithm/search.h --- a/libcxx/include/__algorithm/search.h +++ b/libcxx/include/__algorithm/search.h @@ -12,8 +12,14 @@ #include <__algorithm/comp.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 <__type_traits/is_callable.h> #include <__utility/pair.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,31 +27,42 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -pair<_ForwardIterator1, _ForwardIterator1> - _LIBCPP_CONSTEXPR_AFTER_CXX11 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { +template +_LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_forward_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2) { if (__first2 == __last2) - return _VSTD::make_pair(__first1, __first1); // Everything matches an empty sequence + return std::make_pair(__first1, __first1); // Everything matches an empty sequence while (true) { // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks while (true) { - if (__first1 == __last1) // return __last1 if no element matches *__first2 - return _VSTD::make_pair(__last1, __last1); - if (__pred(*__first1, *__first2)) + if (__first1 == __last1) { // return __last1 if no element matches *__first2 + std::__advance_to(__first1, __last1); + return std::make_pair(__first1, __first1); + } + if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _ForwardIterator1 __m1 = __first1; - _ForwardIterator2 __m2 = __first2; + _Iter1 __m1 = __first1; + _Iter2 __m2 = __first2; while (true) { if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) - return _VSTD::make_pair(__first1, __m1); - if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found - return _VSTD::make_pair(__last1, __last1); - if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1 + return std::make_pair(__first1, ++__m1); + if (++__m1 == __last1) { // Otherwise if source exhaused, pattern not found + return std::make_pair(__m1, __m1); + } + + // if there is a mismatch, restart with a new __first1 + if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { ++__first1; break; @@ -54,38 +71,41 @@ } } -template -_LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_RandomAccessIterator1, _RandomAccessIterator1> -__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, - random_access_iterator_tag) { - typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; - typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; - // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - const _D2 __len2 = __last2 - __first2; - if (__len2 == 0) - return _VSTD::make_pair(__first1, __first1); - const _D1 __len1 = __last1 - __first1; - if (__len1 < __len2) - return _VSTD::make_pair(__last1, __last1); - const _RandomAccessIterator1 __s = __last1 - _D1(__len2 - 1); // Start of pattern match can't go beyond here +template +_LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_random_access_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + _DiffT1 __size1, + _DiffT2 __size2) { + const _Iter1 __s = __first1 + __size1 - _DiffT1(__size2 - 1); // Start of pattern match can't go beyond here while (true) { while (true) { - if (__first1 == __s) - return _VSTD::make_pair(__last1, __last1); - if (__pred(*__first1, *__first2)) + if (__first1 == __s) { + std::__advance_to(__first1, __last1); + return std::make_pair(__first1, __first1); + } + if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; ++__first1; } - _RandomAccessIterator1 __m1 = __first1; - _RandomAccessIterator2 __m2 = __first2; + _Iter1 __m1 = __first1; + _Iter2 __m2 = __first2; while (true) { if (++__m2 == __last2) - return _VSTD::make_pair(__first1, __first1 + _D1(__len2)); + return std::make_pair(__first1, __first1 + _DiffT1(__size2)); ++__m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!__pred(*__m1, *__m2)) { + if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { ++__first1; break; } @@ -93,22 +113,122 @@ } } +#if _LIBCPP_STD_VER > 17 +template +_LIBCPP_HIDE_FROM_ABI constexpr +pair<_Iter1, _Iter1> __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 std::make_pair(__first1, __first1); + + if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { + auto __size1 = ranges::distance(__first1, __last1); + if (__size1 < __size2) { + ranges::advance(__first1, __last1); + return std::make_pair(__first1, __first1); + } + + if constexpr (random_access_iterator<_Iter1> && random_access_iterator<_Iter2>) { + return std::__search_random_access_impl(__first1, __last1, + __first2, __last2, + __pred, + __proj1, + __proj2, + __size1, + __size2); + } + } + } + + return std::__search_forward_impl(__first1, __last1, + __first2, __last2, + __pred, + __proj1, + __proj2); +} +#else +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + __enable_if_t<__is_cpp17_random_access_iterator<_Iter1>::value + && __is_cpp17_random_access_iterator<_Iter2>::value>* = nullptr) { + + auto __size2 = __last2 - __first2; + if (__size2 == 0) + return std::make_pair(__first1, __first1); + + auto __size1 = __last1 - __first1; + if (__size1 < __size2) { + return std::make_pair(__last1, __last1); + } + + return std::__search_random_access_impl(__first1, __last1, + __first2, __last2, + __pred, + __proj1, + __proj2, + __size1, + __size2); +} + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value + && __is_cpp17_forward_iterator<_Iter2>::value + && !(__is_cpp17_random_access_iterator<_Iter1>::value + && __is_cpp17_random_access_iterator<_Iter2>::value)>* = nullptr) { + return std::__search_forward_impl(__first1, __last1, + __first2, __last2, + __pred, + __proj1, + __proj2); +} +#endif // _LIBCPP_STD_VER > 17 + template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred) { - return _VSTD::__search<_BinaryPredicate&>( - __first1, __last1, __first2, __last2, __pred, - typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()).first; +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value, + "BinaryPredicate has to be callable"); + auto __proj = __identity(); + return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first; } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + using __v1 = typename iterator_traits<_ForwardIterator1>::value_type; + using __v2 = typename iterator_traits<_ForwardIterator2>::value_type; + return std::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } #if _LIBCPP_STD_VER > 14 diff --git a/libcxx/include/__algorithm/search_n.h b/libcxx/include/__algorithm/search_n.h --- a/libcxx/include/__algorithm/search_n.h +++ b/libcxx/include/__algorithm/search_n.h @@ -12,7 +12,13 @@ #include <__algorithm/comp.h> #include <__config> +#include <__functional/identity.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> +#include <__ranges/concepts.h> +#include <__utility/pair.h> #include // __convert_to_integral #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -21,30 +27,39 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, - _Size __count, const _Tp& __value_, _BinaryPredicate __pred, - forward_iterator_tag) { +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter, _Iter> __search_n_forward_impl(_Iter __first, _Sent __last, + _SizeT __count, + const _Type& __value_, + _Pred __pred, + _Proj __proj) { if (__count <= 0) - return __first; + return std::make_pair(__first, __first); while (true) { // Find first element in sequence that matchs __value_, with a mininum of loop checks while (true) { - if (__first == __last) // return __last if no element matches __value_ - return __last; - if (__pred(*__first, __value_)) + if (__first == __last) { // return __last if no element matches __value_ + std::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value_)) break; ++__first; } // *__first matches __value_, now match elements after here - _ForwardIterator __m = __first; - _Size __c(0); + _Iter __m = __first; + _SizeT __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - return __first; - if (++__m == __last) // Otherwise if source exhaused, pattern not found - return __last; - if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first + return std::make_pair(__first, ++__m); + if (++__m == __last) { // Otherwise if source exhaused, pattern not found + std::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + + // if there is a mismatch, restart with a new __first + if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value_)) { __first = __m; ++__first; @@ -54,35 +69,44 @@ } } -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Size __count, - const _Tp& __value_, _BinaryPredicate __pred, - random_access_iterator_tag) { - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +std::pair<_Iter, _Iter> __search_n_random_access_impl(_Iter __first, _Sent __last, + _SizeT __count, + const _Type& __value_, + _Pred __pred, + _Proj __proj, + _DiffT __size1) { + typedef typename iterator_traits<_Iter>::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 + return std::make_pair(__first, __first); + if (__size1 < __count) { + std::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + + const auto __s = __first + __size1 - difference_type(__count - 1); // Start of pattern match can't go beyond here while (true) { // Find first element in sequence that matchs __value_, with a mininum of loop checks while (true) { - if (__first >= __s) // return __last if no element matches __value_ - return __last; - if (__pred(*__first, __value_)) + if (__first >= __s) { // return __last if no element matches __value_ + std::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value_)) break; ++__first; } // *__first matches __value_, now match elements after here - _RandomAccessIterator __m = __first; - _Size __c(0); + auto __m = __first; + _SizeT __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - return __first; - ++__m; // no need to check range on __m because __s guarantees we have enough source - if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first + return std::make_pair(__first, __first + _DiffT(__count)); + ++__m; // no need to check range on __m because __s guarantees we have enough source + + // if there is a mismatch, restart with a new __first + if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value_)) { __first = __m; ++__first; @@ -92,19 +116,104 @@ } } +#if _LIBCPP_STD_VER > 17 +template +_LIBCPP_HIDE_FROM_ABI constexpr +pair<_Iter1, _Iter1> __search_n_impl(_Iter1 __first, _Sent1 __last, + _SizeT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj) { + if (__count == 0) + return std::make_pair(__first, __first); + + if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { + auto __size = ranges::distance(__first, __last); + if (__size < __count) { + ranges::advance(__first, __last); + return std::make_pair(__first, __first); + } + + if constexpr (random_access_iterator<_Iter1>) { + return std::__search_n_random_access_impl(__first, __last, + __count, + __value, + __pred, + __proj, + __size); + } + } + + return std::__search_n_forward_impl(__first, __last, + __count, + __value, + __pred, + __proj); +} +#else +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter, _Iter> __search_n_impl(_Iter __first, _Sent __last, + _DiffT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj, + __enable_if_t<__is_cpp17_random_access_iterator<_Iter>::value>* = nullptr) { + + return std::__search_n_random_access_impl(__first, __last, + __count, + __value, + __pred, + __proj, + __last - __first); +} + +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_n_impl(_Iter1 __first, _Sent1 __last, + _DiffT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj, + __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value + && !__is_cpp17_random_access_iterator<_Iter1>::value>* = nullptr) { + return std::__search_n_forward_impl(__first, __last, + __count, + __value, + __pred, + __proj); +} +#endif // _LIBCPP_STD_VER > 17 + template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator search_n( - _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred) { - return _VSTD::__search_n<_BinaryPredicate&>( - __first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred, - typename iterator_traits<_ForwardIterator>::iterator_category()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, + _Size __count, + const _Tp& __value_, + _BinaryPredicate __pred) { + static_assert(__is_callable<_BinaryPredicate, decltype(*__first), decltype(*__last)>::value, + "BinaryPredicate has to be callable"); + auto __proj = __identity(); + return std::__search_n_impl(__first, __last, std::__convert_to_integral(__count), __value_, __pred, __proj).first; } template -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) { +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) { typedef typename iterator_traits<_ForwardIterator>::value_type __v; - return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>()); + return std::search_n(__first, __last, std::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__functional/default_searcher.h b/libcxx/include/__functional/default_searcher.h --- a/libcxx/include/__functional/default_searcher.h +++ b/libcxx/include/__functional/default_searcher.h @@ -12,6 +12,7 @@ #include <__algorithm/search.h> #include <__config> +#include <__functional/identity.h> #include <__functional/operations.h> #include <__iterator/iterator_traits.h> #include <__utility/pair.h> @@ -38,16 +39,15 @@ pair<_ForwardIterator2, _ForwardIterator2> operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { - return _VSTD::__search(__f, __l, __first_, __last_, __pred_, - typename iterator_traits<_ForwardIterator>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); + auto __proj = __identity(); + return std::__search_impl(__f, __l, __first_, __last_, __pred_, __proj, __proj); } private: _ForwardIterator __first_; _ForwardIterator __last_; _BinaryPredicate __pred_; - }; +}; #endif // _LIBCPP_STD_VER > 14 diff --git a/libcxx/include/__iterator/advance.h b/libcxx/include/__iterator/advance.h --- a/libcxx/include/__iterator/advance.h +++ b/libcxx/include/__iterator/advance.h @@ -195,6 +195,16 @@ #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR +void __advance_to(_Iter& __iter, _Sent& __to) { +#if _LIBCPP_STD_VER > 17 + ranges::advance(__iter, __to); +#else + __iter = std::move(__to); +#endif +} + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_ADVANCE_H diff --git a/libcxx/include/__iterator/next.h b/libcxx/include/__iterator/next.h --- a/libcxx/include/__iterator/next.h +++ b/libcxx/include/__iterator/next.h @@ -81,6 +81,17 @@ #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +template +_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_AFTER_CXX14 +_Iter __next_to(_Iter __iter, _Sent __sent) { +#if _LIBCPP_STD_VER > 17 + return ranges::next(__iter, __sent); +#else + (void)__iter; + return __sent; +#endif +} + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_NEXT_H diff --git a/libcxx/include/__iterator/reverse_iterator.h b/libcxx/include/__iterator/reverse_iterator.h --- a/libcxx/include/__iterator/reverse_iterator.h +++ b/libcxx/include/__iterator/reverse_iterator.h @@ -14,6 +14,7 @@ #include <__compare/three_way_comparable.h> #include <__concepts/convertible_to.h> #include <__config> +#include <__iterator/advance.h> #include <__iterator/concepts.h> #include <__iterator/incrementable_traits.h> #include <__iterator/iter_move.h> @@ -321,6 +322,25 @@ } #endif +template +_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR +reverse_iterator<_Iter> __make_begin_reverse_iterator(_Iter __iter) { + return reverse_iterator<_Iter>(__iter); +} + +template +_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR +reverse_iterator<_Iter> __make_end_reverse_iterator(_Iter __first, _Sent __last) { +#if _LIBCPP_STD_VER > 17 + ranges::advance(__first, __last); + return std::make_reverse_iterator(__first); +#else + static_assert(is_same<_Iter, _Sent>::value, "Iterator and Sentinel have to be the same type pre-C++20"); + (void)__first; + return reverse_iterator<_Iter>(__last); +#endif +} + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ITERATOR_REVERSE_ITERATOR_H diff --git a/libcxx/include/__string b/libcxx/include/__string --- a/libcxx/include/__string +++ b/libcxx/include/__string @@ -1024,9 +1024,7 @@ __pos += __n; else __pos = __sz; - const _CharT* __r = _VSTD::__find_end( - __p, __p + __pos, __s, __s + __n, _Traits::eq, - random_access_iterator_tag(), random_access_iterator_tag()); + const _CharT* __r = std::find_end(__p, __p + __pos, __s, __s + __n, _Traits::eq); if (__n > 0 && __r == __p + __pos) return __npos; return static_cast<_SizeT>(__r - __p); diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -962,6 +962,7 @@ #include <__algorithm/ranges_count.h> #include <__algorithm/ranges_count_if.h> #include <__algorithm/ranges_find.h> +#include <__algorithm/ranges_find_end.h> #include <__algorithm/ranges_find_if.h> #include <__algorithm/ranges_find_if_not.h> #include <__algorithm/ranges_max.h> @@ -971,6 +972,8 @@ #include <__algorithm/ranges_minmax.h> #include <__algorithm/ranges_minmax_element.h> #include <__algorithm/ranges_mismatch.h> +#include <__algorithm/ranges_search.h> +#include <__algorithm/ranges_search_n.h> #include <__algorithm/ranges_swap_ranges.h> #include <__algorithm/ranges_transform.h> #include <__algorithm/remove.h> diff --git a/libcxx/include/experimental/functional b/libcxx/include/experimental/functional --- a/libcxx/include/experimental/functional +++ b/libcxx/include/experimental/functional @@ -62,6 +62,7 @@ #include <__assert> // all public C++ headers provide the assertion handler #include <__debug> +#include <__functional/identity.h> #include <__memory/uses_allocator.h> #include #include @@ -94,9 +95,8 @@ pair<_ForwardIterator2, _ForwardIterator2> operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { - return _VSTD::__search(__f, __l, __first_, __last_, __pred_, - typename iterator_traits<_ForwardIterator>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); + auto __proj = __identity(); + return std::__search_impl(__f, __l, __first_, __last_, __pred_, __proj, __proj); } private: diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -301,6 +301,7 @@ module ranges_count { private header "__algorithm/ranges_count.h" } module ranges_count_if { private header "__algorithm/ranges_count_if.h" } module ranges_find { private header "__algorithm/ranges_find.h" } + module ranges_find_end { private header "__algorithm/ranges_find_end.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" } module ranges_max { private header "__algorithm/ranges_max.h" } @@ -310,6 +311,8 @@ module ranges_minmax { private header "__algorithm/ranges_minmax.h" } module ranges_minmax_element { private header "__algorithm/ranges_minmax_element.h" } module ranges_mismatch { private header "__algorithm/ranges_mismatch.h" } + module ranges_search { private header "__algorithm/ranges_search.h" } + module ranges_search_n { private header "__algorithm/ranges_search_n.h" } module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.h" } module ranges_transform { private header "__algorithm/ranges_transform.h" } module remove { private header "__algorithm/remove.h" } diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -84,10 +84,10 @@ //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; + int count = 1; int copies = 0; //(void)std::ranges::adjacent_find(first, last, Equal(&copies)); assert(copies == 0); @@ -110,8 +110,8 @@ //(void)std::ranges::equal(a, b, Equal(&copies)); assert(copies == 0); //(void)std::ranges::equal_range(first, last, value, Less(&copies)); assert(copies == 0); //(void)std::ranges::equal_range(a, value, Less(&copies)); assert(copies == 0); - //(void)std::ranges::find_end(first, last, first2, mid2, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::find_end(a, b, Equal(&copies)); assert(copies == 0); + (void)std::ranges::find_end(first, last, first2, mid2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::find_end(a, b, Equal(&copies)); assert(copies == 0); //(void)std::ranges::find_first_of(first, last, first2, last2, Equal(&copies)); assert(copies == 0); //(void)std::ranges::find_first_of(a, b, Equal(&copies)); assert(copies == 0); (void)std::ranges::find_if(first, last, UnaryTrue(&copies)); assert(copies == 0); @@ -153,9 +153,9 @@ (void)std::ranges::max_element(a, Less(&copies)); assert(copies == 0); //(void)std::ranges::merge(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); //(void)std::ranges::merge(half, half, b, Less(&copies)); assert(copies == 0); - //(void)std::ranges::min(value, value, Less(&copies)); assert(copies == 0); - //(void)std::ranges::min({ value, value }, Less(&copies)); assert(copies == 0); - //(void)std::ranges::min(a, Less(&copies)); assert(copies == 0); + (void)std::ranges::min(value, value, Less(&copies)); assert(copies == 0); + (void)std::ranges::min({ value, value }, Less(&copies)); assert(copies == 0); + (void)std::ranges::min(a, Less(&copies)); assert(copies == 0); (void)std::ranges::min_element(first, last, Less(&copies)); assert(copies == 0); (void)std::ranges::min_element(a, Less(&copies)); assert(copies == 0); (void)std::ranges::minmax(value, value, Less(&copies)); assert(copies == 0); @@ -195,10 +195,10 @@ //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(&copies), value); assert(copies == 0); //(void)std::ranges::replace_if(first, last, UnaryTrue(&copies), value); assert(copies == 0); //(void)std::ranges::replace_if(a, UnaryTrue(&copies), value); assert(copies == 0); - //(void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0); + (void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0); + (void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0); + (void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0); + (void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0); //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); //(void)std::ranges::set_difference(a, b, first2, Less(&copies)); assert(copies == 0); //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -110,6 +110,7 @@ #include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}} #include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.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_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'}} #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}} @@ -119,6 +120,8 @@ #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}} #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}} #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.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_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}} #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}} #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.h'}} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find.end/ranges.find_end.pass.cpp @@ -0,0 +1,307 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +#include +#include + +#include "test_iterators.h" + +template +constexpr void test_iterators() { + { // simple test + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4}; + std::same_as> decltype(auto) ret = + std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2))); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 4); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2))); + std::same_as> decltype(auto) ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 4); + } + } + + { // matching part begins at the front + { + int a[] = {7, 5, 3, 7, 3, 6}; + int p[] = {7, 5, 3}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {7, 5, 3, 7, 3, 6}; + int p[] = {7, 5, 3}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } + + { // matching part ends at the back + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {4, 8}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 2))); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {4, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + } + + { // pattern does not match + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {1}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 1))); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {1}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + } + + { // range and pattern are identical + { + int a[] = {6, 7, 8, 9}; + int p[] = {6, 7, 8, 9}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 4)), Iter2(p), Sent2(Iter2(p + 4))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + { + int a[] = {6, 7, 8, 9}; + int p[] = {6, 7, 8, 9}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + } + + { // pattern is longer than range + { + int a[] = {6, 7, 8}; + int p[] = {6, 7, 8, 9}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p + 4))); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {6, 7, 8}; + int p[] = {6, 7, 8, 9}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + } + + { // pattern has zero length + { + int a[] = {6, 7, 8}; + int p[] = {}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p))); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {6, 7, 8}; + int p[] = {}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + } + + { // range has zero length + { + int a[] = {}; + int p[] = {6, 7, 8}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + { + int a[] = {}; + int p[] = {6, 7, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + } + + { // check that the first match is returned + { + int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8}; + int p[] = {6, 7, 8}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 9)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a + 6); + assert(base(ret.end()) == a + 9); + } + { + int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8}; + int p[] = {6, 7, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 9))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::find_end(range1, range2); + assert(base(ret.begin()) == a + 6); + assert(base(ret.end()) == a + 9); + } + } + + { // check that the predicate is used + { + int a[] = {1, 2, 8, 1, 5, 6}; + int p[] = {7, 0, 4}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), + Iter2(p), Sent2(Iter2(p + 3)), + [](int l, int r) { return l > r; }); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {1, 2, 8, 1, 5, 6}; + int p[] = {7, 0, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::find_end(range1, range2, [](int l, int r) { return l > r; }); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 5); + } + } + + { // check that the projections are used + { + int a[] = {1, 3, 5, 1, 5, 6}; + int p[] = {2, 3, 4}; + auto ret = std::ranges::find_end(Iter1(a), Sent1(Iter1(a + 6)), + Iter2(p), Sent2(Iter2(p + 3)), + {}, + [](int i) { return i + 3; }, + [](int i) { return i * 2; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {1, 3, 5, 1, 5, 6}; + int p[] = {2, 3, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::find_end(range1, + range2, + {}, + [](int i) { return i + 3; }, + [](int i) { return i * 2; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } +} + +template +constexpr void test_iterators2() { + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators(); +} + +constexpr bool test() { + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2(); + + { // check that std::invoke is used + struct S { + int i; + + constexpr S identity() { + return *this; + } + + constexpr bool compare(const S& s) { + return i == s.i; + } + }; + { + S a[] = {{1}, {2}, {3}, {4}}; + S p[] = {{2}, {3}}; + auto ret = std::ranges::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 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.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search.pass.cpp @@ -0,0 +1,307 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +#include +#include + +#include "test_iterators.h" + +template +constexpr void test_iterators() { + { // simple test + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4}; + std::same_as> decltype(auto) ret = + std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2))); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 4); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + int p[] = {3, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2))); + std::same_as> decltype(auto) ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 4); + } + } + + { // matching part begins at the front + { + int a[] = {7, 5, 3, 7, 3, 6}; + int p[] = {7, 5, 3}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {7, 5, 3, 7, 3, 6}; + int p[] = {7, 5, 3}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } + + { // matching part ends at the back + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {4, 8}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 2))); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {4, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + } + + { // pattern does not match + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {1}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 1))); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 8}; + int p[] = {1}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + } + + { // range and pattern are identical + { + int a[] = {6, 7, 8, 9}; + int p[] = {6, 7, 8, 9}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 4)), Iter2(p), Sent2(Iter2(p + 4))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + { + int a[] = {6, 7, 8, 9}; + int p[] = {6, 7, 8, 9}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + } + + { // pattern is longer than range + { + int a[] = {6, 7, 8}; + int p[] = {6, 7, 8, 9}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p + 4))); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {6, 7, 8}; + int p[] = {6, 7, 8, 9}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + } + + { // pattern has zero length + { + int a[] = {6, 7, 8}; + int p[] = {}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + { + int a[] = {6, 7, 8}; + int p[] = {}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + } + + { // range has zero length + { + int a[] = {}; + int p[] = {6, 7, 8}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + { + int a[] = {}; + int p[] = {6, 7, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + } + + { // check that the first match is returned + { + int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8}; + int p[] = {6, 7, 8}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 9)), Iter2(p), Sent2(Iter2(p + 3))); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8}; + int p[] = {6, 7, 8}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 9))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::search(range1, range2); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } + + { // check that the predicate is used + { + int a[] = {1, 2, 8, 1, 5, 6}; + int p[] = {7, 0, 4}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), + Iter2(p), Sent2(Iter2(p + 3)), + [](int l, int r) { return l > r; }); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {1, 2, 8, 1, 5, 6}; + int p[] = {7, 0, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::search(range1, range2, [](int l, int r) { return l > r; }); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 5); + } + } + + { // check that the projections are used + { + int a[] = {1, 3, 5, 1, 5, 6}; + int p[] = {2, 3, 4}; + auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), + Iter2(p), Sent2(Iter2(p + 3)), + {}, + [](int i) { return i + 3; }, + [](int i) { return i * 2; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {1, 3, 5, 1, 5, 6}; + int p[] = {2, 3, 4}; + auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6))); + auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3))); + auto ret = std::ranges::search(range1, + range2, + {}, + [](int i) { return i + 3; }, + [](int i) { return i * 2; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } +} + +template +constexpr void test_iterators2() { + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators(); +} + +constexpr bool test() { + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2>(); + test_iterators2, sized_sentinel>>(); + test_iterators2(); + + { // check that std::invoke is used + struct S { + int i; + + constexpr S identity() { + return *this; + } + + constexpr bool compare(const S& s) { + return i == s.i; + } + }; + { + S a[] = {{1}, {2}, {3}, {4}}; + S p[] = {{2}, {3}}; + auto ret = std::ranges::search(a, a + 4, p, p + 2, &S::compare, &S::identity, &S::identity); + assert(ret.begin() == a + 1); + assert(ret.end() == a + 3); + } + { + S a[] = {{1}, {2}, {3}, {4}}; + S p[] = {{2}, {3}}; + auto ret = std::ranges::search(a, p, &S::compare, &S::identity, &S::identity); + assert(ret.begin() == a + 1); + assert(ret.end() == a + 3); + } + } + + { // check that std::ranges::dangling is returned + [[maybe_unused]] std::same_as auto ret = + std::ranges::search(std::array {1, 2, 3, 4}, std::array {2, 3}); + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.pass.cpp @@ -0,0 +1,259 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +#include +#include + +#include "test_iterators.h" + +template +constexpr void test_iterators() { + { // simple test + { + int a[] = {1, 2, 3, 4, 5, 6}; + std::same_as> decltype(auto) ret = + std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 1, 3); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {1, 2, 3, 4, 5, 6}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); + std::same_as> decltype(auto) ret = std::ranges::search_n(range, 1, 3); + assert(base(ret.begin()) == a + 2); + assert(base(ret.end()) == a + 3); + } + } + + { // matching part begins at the front + { + int a[] = {7, 7, 3, 7, 3, 6}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 2, 7); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 2); + } + { + int a[] = {7, 7, 3, 7, 3, 6}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); + auto ret = std::ranges::search_n(range, 2, 7); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 2); + } + } + + { // matching part ends at the back + { + int a[] = {9, 3, 6, 4, 4}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 2, 4); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 4}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5))); + auto ret = std::ranges::search_n(range, 2, 4); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 5); + } + } + + { // pattern does not match + { + int a[] = {9, 3, 6, 4, 8}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 1, 1); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + { + int a[] = {9, 3, 6, 4, 8}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5))); + auto ret = std::ranges::search_n(range, 1, 1); + assert(base(ret.begin()) == a + 5); + assert(base(ret.end()) == a + 5); + } + } + + { // range and pattern are identical + { + int a[] = {1, 1, 1, 1}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 4)), 4, 1); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + { + int a[] = {1, 1, 1, 1}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 4))); + auto ret = std::ranges::search_n(range, 4, 1); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 4); + } + } + + { // pattern is longer than range + { + int a[] = {3, 3, 3}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 4, 3); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {3, 3, 3}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3))); + auto ret = std::ranges::search_n(range, 4, 3); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 3); + } + } + + { // pattern has zero length + { + int a[] = {6, 7, 8}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 0, 7); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + { + int a[] = {6, 7, 8}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3))); + auto ret = std::ranges::search_n(range, 0, 7); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + } + + { // range has zero length + { + int a[] = {}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a)), 1, 1); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + { + int a[] = {}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a))); + auto ret = std::ranges::search_n(range, 1, 1); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a); + } + } + + { // check that the first match is returned + { + int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 9)), 2, 6); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 2); + } + { + int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 9))); + auto ret = std::ranges::search_n(range, 2, 6); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 2); + } + } + + { // check that the predicate is used + { + int a[] = {1, 4, 4, 3, 6, 1}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), + 3, + 4, + [](int l, int r) { return l == r || l == 1; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + { + int a[] = {1, 4, 4, 3, 6, 1}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); + auto ret = std::ranges::search_n(range, 3, 4, [](int l, int r) { return l == r || l == 1; }); + assert(base(ret.begin()) == a); + assert(base(ret.end()) == a + 3); + } + } + + { // check that the projections are used + { + int a[] = {1, 3, 1, 6, 5, 6}; + auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), + 3, + 6, + {}, + [](int i) { return i % 2 == 0 ? i : i + 1; }); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 6); + } + { + int a[] = {1, 3, 1, 6, 5, 6}; + auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); + auto ret = std::ranges::search_n(range, + 3, + 6, + {}, + [](int i) { return i % 2 == 0 ? i : i + 1; }); + assert(base(ret.begin()) == a + 3); + assert(base(ret.end()) == a + 6); + } + } +} +constexpr bool test() { + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators>(); + test_iterators, sized_sentinel>>(); + test_iterators(); + + { // check that std::invoke is used + struct S { + int i; + + constexpr S identity() { + return *this; + } + + constexpr bool compare(int o) { + return i == o; + } + }; + { + S a[] = {{1}, {2}, {3}, {4}}; + auto ret = std::ranges::search_n(a, a + 4, 1, 2, &S::compare, &S::identity); + assert(ret.begin() == a + 1); + assert(ret.end() == a + 2); + } + { + S a[] = {{1}, {2}, {3}, {4}}; + auto ret = std::ranges::search_n(a, 1, 2, &S::compare, &S::identity); + assert(ret.begin() == a + 1); + assert(ret.end() == a + 2); + } + } + + { // check that std::ranges::dangling is returned + [[maybe_unused]] std::same_as 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/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -54,7 +54,7 @@ int *p; int a[10]; auto odd = [](int x) { return x % 2 != 0; }; -//auto triple = [](int x) { return 3*x; }; +auto triple = [](int x) { return 3*x; }; //auto plus = [](int x, int y) { return x == y; }; //std::mt19937 g; @@ -65,10 +65,10 @@ //static_assert(test(std::ranges::any_of, a, odd)); //static_assert(test(std::ranges::binary_search, a, 42)); //static_assert(test(std::ranges::clamp, 42, 42, 42)); -//static_assert(test(std::ranges::copy, a, a)); -//static_assert(test(std::ranges::copy_backward, a, a)); -//static_assert(test(std::ranges::copy_if, a, a, odd)); -//static_assert(test(std::ranges::copy_n, a, 10, a)); +static_assert(test(std::ranges::copy, a, a)); +static_assert(test(std::ranges::copy_backward, a, a)); +static_assert(test(std::ranges::copy_if, a, a, odd)); +static_assert(test(std::ranges::copy_n, a, 10, a)); static_assert(test(std::ranges::count, a, 42)); static_assert(test(std::ranges::count_if, a, odd)); //static_assert(test(std::ranges::ends_with, a, a)); @@ -77,7 +77,7 @@ //static_assert(test(std::ranges::fill, a, 42)); //static_assert(test(std::ranges::fill_n, a, 10, 42)); static_assert(test(std::ranges::find, a, 42)); -//static_assert(test(std::ranges::find_end, a, a)); +static_assert(test(std::ranges::find_end, a, a)); //static_assert(test(std::ranges::find_first_of, a, a)); static_assert(test(std::ranges::find_if, a, odd)); static_assert(test(std::ranges::find_if_not, a, odd)); @@ -96,7 +96,7 @@ //static_assert(test(std::ranges::lexicographical_compare, a, a)); //static_assert(test(std::ranges::lower_bound, a, 42)); //static_assert(test(std::ranges::make_heap, a)); -//static_assert(test(std::ranges::max, a)); +static_assert(test(std::ranges::max, a)); static_assert(test(std::ranges::max_element, a)); //static_assert(test(std::ranges::merge, a, a, a)); static_assert(test(std::ranges::min, a)); @@ -130,8 +130,8 @@ //static_assert(test(std::ranges::rotate, a, a+5)); //static_assert(test(std::ranges::rotate_copy, a, a+5, a)); //static_assert(test(std::ranges::sample, a, a, 5)); -//static_assert(test(std::ranges::search, a, a)); -//static_assert(test(std::ranges::search_n, a, 10, 42)); +static_assert(test(std::ranges::search, a, a)); +static_assert(test(std::ranges::search_n, a, 10, 42)); //static_assert(test(std::ranges::set_difference, a, a, a)); //static_assert(test(std::ranges::set_intersection, a, a, a)); //static_assert(test(std::ranges::set_symmetric_difference, a, a, a)); @@ -143,7 +143,7 @@ //static_assert(test(std::ranges::stable_sort, a)); //static_assert(test(std::ranges::starts_with, a, a)); static_assert(test(std::ranges::swap_ranges, a, a)); -//static_assert(test(std::ranges::transform, a, a, triple)); +static_assert(test(std::ranges::transform, a, a, triple)); //static_assert(test(std::ranges::unique, a)); //static_assert(test(std::ranges::unique_copy, a, a)); //static_assert(test(std::ranges::upper_bound, a, 42));