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