libcxx/include/__algorithm/search_n.h

   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