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