183 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03___ALGORITHM_SEARCH_H11#define _LIBCPP___CXX03___ALGORITHM_SEARCH_H12 13#include <__cxx03/__algorithm/comp.h>14#include <__cxx03/__algorithm/iterator_operations.h>15#include <__cxx03/__config>16#include <__cxx03/__functional/identity.h>17#include <__cxx03/__iterator/advance.h>18#include <__cxx03/__iterator/iterator_traits.h>19#include <__cxx03/__type_traits/enable_if.h>20#include <__cxx03/__type_traits/invoke.h>21#include <__cxx03/__type_traits/is_callable.h>22#include <__cxx03/__utility/pair.h>23 24#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)25# pragma GCC system_header26#endif27 28_LIBCPP_BEGIN_NAMESPACE_STD29 30template <class _AlgPolicy,31 class _Iter1,32 class _Sent1,33 class _Iter2,34 class _Sent2,35 class _Pred,36 class _Proj1,37 class _Proj2>38_LIBCPP_HIDE_FROM_ABI pair<_Iter1, _Iter1> __search_forward_impl(39 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {40 if (__first2 == __last2)41 return std::make_pair(__first1, __first1); // Everything matches an empty sequence42 while (true) {43 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks44 while (true) {45 if (__first1 == __last1) { // return __last1 if no element matches *__first246 _IterOps<_AlgPolicy>::__advance_to(__first1, __last1);47 return std::make_pair(__first1, __first1);48 }49 if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))50 break;51 ++__first1;52 }53 // *__first1 matches *__first2, now match elements after here54 _Iter1 __m1 = __first1;55 _Iter2 __m2 = __first2;56 while (true) {57 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)58 return std::make_pair(__first1, ++__m1);59 if (++__m1 == __last1) { // Otherwise if source exhaused, pattern not found60 return std::make_pair(__m1, __m1);61 }62 63 // if there is a mismatch, restart with a new __first164 if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {65 ++__first1;66 break;67 } // else there is a match, check next elements68 }69 }70}71 72template <class _AlgPolicy,73 class _Iter1,74 class _Sent1,75 class _Iter2,76 class _Sent2,77 class _Pred,78 class _Proj1,79 class _Proj2,80 class _DiffT1,81 class _DiffT2>82_LIBCPP_HIDE_FROM_ABI pair<_Iter1, _Iter1> __search_random_access_impl(83 _Iter1 __first1,84 _Sent1 __last1,85 _Iter2 __first2,86 _Sent2 __last2,87 _Pred& __pred,88 _Proj1& __proj1,89 _Proj2& __proj2,90 _DiffT1 __size1,91 _DiffT2 __size2) {92 const _Iter1 __s = __first1 + __size1 - _DiffT1(__size2 - 1); // Start of pattern match can't go beyond here93 94 while (true) {95 while (true) {96 if (__first1 == __s) {97 _IterOps<_AlgPolicy>::__advance_to(__first1, __last1);98 return std::make_pair(__first1, __first1);99 }100 if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))101 break;102 ++__first1;103 }104 105 _Iter1 __m1 = __first1;106 _Iter2 __m2 = __first2;107 while (true) {108 if (++__m2 == __last2)109 return std::make_pair(__first1, __first1 + _DiffT1(__size2));110 ++__m1; // no need to check range on __m1 because __s guarantees we have enough source111 if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {112 ++__first1;113 break;114 }115 }116 }117}118 119template <class _Iter1,120 class _Sent1,121 class _Iter2,122 class _Sent2,123 class _Pred,124 class _Proj1,125 class _Proj2,126 __enable_if_t<__has_random_access_iterator_category<_Iter1>::value &&127 __has_random_access_iterator_category<_Iter2>::value,128 int> = 0>129_LIBCPP_HIDE_FROM_ABI pair<_Iter1, _Iter1> __search_impl(130 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {131 auto __size2 = __last2 - __first2;132 if (__size2 == 0)133 return std::make_pair(__first1, __first1);134 135 auto __size1 = __last1 - __first1;136 if (__size1 < __size2) {137 return std::make_pair(__last1, __last1);138 }139 140 return std::__search_random_access_impl<_ClassicAlgPolicy>(141 __first1, __last1, __first2, __last2, __pred, __proj1, __proj2, __size1, __size2);142}143 144template <145 class _Iter1,146 class _Sent1,147 class _Iter2,148 class _Sent2,149 class _Pred,150 class _Proj1,151 class _Proj2,152 __enable_if_t<__has_forward_iterator_category<_Iter1>::value && __has_forward_iterator_category<_Iter2>::value &&153 !(__has_random_access_iterator_category<_Iter1>::value &&154 __has_random_access_iterator_category<_Iter2>::value),155 int> = 0>156_LIBCPP_HIDE_FROM_ABI pair<_Iter1, _Iter1> __search_impl(157 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {158 return std::__search_forward_impl<_ClassicAlgPolicy>(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2);159}160 161template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>162_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator1163search(_ForwardIterator1 __first1,164 _ForwardIterator1 __last1,165 _ForwardIterator2 __first2,166 _ForwardIterator2 __last2,167 _BinaryPredicate __pred) {168 static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value,169 "BinaryPredicate has to be callable");170 auto __proj = __identity();171 return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first;172}173 174template <class _ForwardIterator1, class _ForwardIterator2>175_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator1176search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {177 return std::search(__first1, __last1, __first2, __last2, __equal_to());178}179 180_LIBCPP_END_NAMESPACE_STD181 182#endif // _LIBCPP___CXX03___ALGORITHM_SEARCH_H183