1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___ALGORITHM_SEARCH_N_H 11 #define _LIBCPP___ALGORITHM_SEARCH_N_H 12 13 #include <__algorithm/comp.h> 14 #include <__algorithm/iterator_operations.h> 15 #include <__config> 16 #include <__functional/identity.h> 17 #include <__iterator/advance.h> 18 #include <__iterator/concepts.h> 19 #include <__iterator/distance.h> 20 #include <__iterator/iterator_traits.h> 21 #include <__ranges/concepts.h> 22 #include <__utility/pair.h> 23 #include <type_traits> // __convert_to_integral 24 25 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 26 # pragma GCC system_header 27 #endif 28 29 _LIBCPP_BEGIN_NAMESPACE_STD 30 31 template <class _AlgPolicy, class _Pred, class _Iter, class _Sent, class _SizeT, class _Type, class _Proj> 32 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 33 pair<_Iter, _Iter> __search_n_forward_impl(_Iter __first, _Sent __last, 34 _SizeT __count, 35 const _Type& __value, 36 _Pred& __pred, 37 _Proj& __proj) { 38 if (__count <= 0) 39 return std::make_pair(__first, __first); 40 while (true) { 41 // Find first element in sequence that matchs __value, with a mininum of loop checks 42 while (true) { 43 if (__first == __last) { // return __last if no element matches __value 44 _IterOps<_AlgPolicy>::__advance_to(__first, __last); 45 return std::make_pair(__first, __first); 46 } 47 if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value)) 48 break; 49 ++__first; 50 } 51 // *__first matches __value, now match elements after here 52 _Iter __m = __first; 53 _SizeT __c(0); 54 while (true) { 55 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) 56 return std::make_pair(__first, ++__m); 57 if (++__m == __last) { // Otherwise if source exhaused, pattern not found 58 _IterOps<_AlgPolicy>::__advance_to(__first, __last); 59 return std::make_pair(__first, __first); 60 } 61 62 // if there is a mismatch, restart with a new __first 63 if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value)) 64 { 65 __first = __m; 66 ++__first; 67 break; 68 } // else there is a match, check next elements 69 } 70 } 71 } 72 73 template <class _AlgPolicy, class _Pred, class _Iter, class _Sent, class _SizeT, class _Type, class _Proj, class _DiffT> 74 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 75 std::pair<_Iter, _Iter> __search_n_random_access_impl(_Iter __first, _Sent __last, 76 _SizeT __count, 77 const _Type& __value, 78 _Pred& __pred, 79 _Proj& __proj, 80 _DiffT __size1) { 81 using difference_type = typename iterator_traits<_Iter>::difference_type; 82 if (__count == 0) 83 return std::make_pair(__first, __first); 84 if (__size1 < static_cast<_DiffT>(__count)) { 85 _IterOps<_AlgPolicy>::__advance_to(__first, __last); 86 return std::make_pair(__first, __first); 87 } 88 89 const auto __s = __first + __size1 - difference_type(__count - 1); // Start of pattern match can't go beyond here 90 while (true) { 91 // Find first element in sequence that matchs __value, with a mininum of loop checks 92 while (true) { 93 if (__first >= __s) { // return __last if no element matches __value 94 _IterOps<_AlgPolicy>::__advance_to(__first, __last); 95 return std::make_pair(__first, __first); 96 } 97 if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value)) 98 break; 99 ++__first; 100 } 101 // *__first matches __value_, now match elements after here 102 auto __m = __first; 103 _SizeT __c(0); 104 while (true) { 105 if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) 106 return std::make_pair(__first, __first + _DiffT(__count)); 107 ++__m; // no need to check range on __m because __s guarantees we have enough source 108 109 // if there is a mismatch, restart with a new __first 110 if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value)) 111 { 112 __first = __m; 113 ++__first; 114 break; 115 } // else there is a match, check next elements 116 } 117 } 118 } 119 120 template <class _Iter, class _Sent, 121 class _DiffT, 122 class _Type, 123 class _Pred, 124 class _Proj> 125 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 126 pair<_Iter, _Iter> __search_n_impl(_Iter __first, _Sent __last, 127 _DiffT __count, 128 const _Type& __value, 129 _Pred& __pred, 130 _Proj& __proj, 131 __enable_if_t<__is_cpp17_random_access_iterator<_Iter>::value>* = nullptr) { 132 return std::__search_n_random_access_impl<_ClassicAlgPolicy>(__first, __last, 133 __count, 134 __value, 135 __pred, 136 __proj, 137 __last - __first); 138 } 139 140 template <class _Iter1, class _Sent1, 141 class _DiffT, 142 class _Type, 143 class _Pred, 144 class _Proj> 145 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 146 pair<_Iter1, _Iter1> __search_n_impl(_Iter1 __first, _Sent1 __last, 147 _DiffT __count, 148 const _Type& __value, 149 _Pred& __pred, 150 _Proj& __proj, 151 __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value 152 && !__is_cpp17_random_access_iterator<_Iter1>::value>* = nullptr) { 153 return std::__search_n_forward_impl<_ClassicAlgPolicy>(__first, __last, 154 __count, 155 __value, 156 __pred, 157 __proj); 158 } 159 160 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate> 161 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 162 _ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, 163 _Size __count, 164 const _Tp& __value, 165 _BinaryPredicate __pred) { 166 static_assert(__is_callable<_BinaryPredicate, decltype(*__first), const _Tp&>::value, 167 "BinaryPredicate has to be callable"); 168 auto __proj = __identity(); 169 return std::__search_n_impl(__first, __last, std::__convert_to_integral(__count), __value, __pred, __proj).first; 170 } 171 172 template <class _ForwardIterator, class _Size, class _Tp> 173 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 174 _ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value) { 175 typedef typename iterator_traits<_ForwardIterator>::value_type __v; 176 return std::search_n(__first, __last, std::__convert_to_integral(__count), __value, __equal_to<__v, _Tp>()); 177 } 178 179 _LIBCPP_END_NAMESPACE_STD 180 181 #endif // _LIBCPP___ALGORITHM_SEARCH_N_H 182