193 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___ALGORITHM_SEARCH_H11#define _LIBCPP___ALGORITHM_SEARCH_H12 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/iterator_traits.h>20#include <__type_traits/enable_if.h>21#include <__type_traits/invoke.h>22#include <__type_traits/is_callable.h>23#include <__utility/pair.h>24 25#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)26# pragma GCC system_header27#endif28 29_LIBCPP_BEGIN_NAMESPACE_STD30 31template <class _AlgPolicy,32 class _Iter1,33 class _Sent1,34 class _Iter2,35 class _Sent2,36 class _Pred,37 class _Proj1,38 class _Proj2>39_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __search_forward_impl(40 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {41 if (__first2 == __last2)42 return std::make_pair(__first1, __first1); // Everything matches an empty sequence43 while (true) {44 // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks45 while (true) {46 if (__first1 == __last1) { // return __last1 if no element matches *__first247 _IterOps<_AlgPolicy>::__advance_to(__first1, __last1);48 return std::make_pair(__first1, __first1);49 }50 if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))51 break;52 ++__first1;53 }54 // *__first1 matches *__first2, now match elements after here55 _Iter1 __m1 = __first1;56 _Iter2 __m2 = __first2;57 while (true) {58 if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)59 return std::make_pair(__first1, ++__m1);60 if (++__m1 == __last1) { // Otherwise if source exhaused, pattern not found61 return std::make_pair(__m1, __m1);62 }63 64 // if there is a mismatch, restart with a new __first165 if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {66 ++__first1;67 break;68 } // else there is a match, check next elements69 }70 }71}72 73template <class _AlgPolicy,74 class _Iter1,75 class _Sent1,76 class _Iter2,77 class _Sent2,78 class _Pred,79 class _Proj1,80 class _Proj2,81 class _DiffT1,82 class _DiffT2>83_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __search_random_access_impl(84 _Iter1 __first1,85 _Sent1 __last1,86 _Iter2 __first2,87 _Sent2 __last2,88 _Pred& __pred,89 _Proj1& __proj1,90 _Proj2& __proj2,91 _DiffT1 __size1,92 _DiffT2 __size2) {93 const _Iter1 __s = __first1 + __size1 - _DiffT1(__size2 - 1); // Start of pattern match can't go beyond here94 95 while (true) {96 while (true) {97 if (__first1 == __s) {98 _IterOps<_AlgPolicy>::__advance_to(__first1, __last1);99 return std::make_pair(__first1, __first1);100 }101 if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))102 break;103 ++__first1;104 }105 106 _Iter1 __m1 = __first1;107 _Iter2 __m2 = __first2;108 while (true) {109 if (++__m2 == __last2)110 return std::make_pair(__first1, __first1 + _DiffT1(__size2));111 ++__m1; // no need to check range on __m1 because __s guarantees we have enough source112 if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {113 ++__first1;114 break;115 }116 }117 }118}119 120template <class _Iter1,121 class _Sent1,122 class _Iter2,123 class _Sent2,124 class _Pred,125 class _Proj1,126 class _Proj2,127 __enable_if_t<__has_random_access_iterator_category<_Iter1>::value &&128 __has_random_access_iterator_category<_Iter2>::value,129 int> = 0>130_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __search_impl(131 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {132 auto __size2 = __last2 - __first2;133 if (__size2 == 0)134 return std::make_pair(__first1, __first1);135 136 auto __size1 = __last1 - __first1;137 if (__size1 < __size2) {138 return std::make_pair(__last1, __last1);139 }140 141 return std::__search_random_access_impl<_ClassicAlgPolicy>(142 __first1, __last1, __first2, __last2, __pred, __proj1, __proj2, __size1, __size2);143}144 145template <146 class _Iter1,147 class _Sent1,148 class _Iter2,149 class _Sent2,150 class _Pred,151 class _Proj1,152 class _Proj2,153 __enable_if_t<__has_forward_iterator_category<_Iter1>::value && __has_forward_iterator_category<_Iter2>::value &&154 !(__has_random_access_iterator_category<_Iter1>::value &&155 __has_random_access_iterator_category<_Iter2>::value),156 int> = 0>157_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __search_impl(158 _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {159 return std::__search_forward_impl<_ClassicAlgPolicy>(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2);160}161 162template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>163[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1164search(_ForwardIterator1 __first1,165 _ForwardIterator1 __last1,166 _ForwardIterator2 __first2,167 _ForwardIterator2 __last2,168 _BinaryPredicate __pred) {169 static_assert(__is_callable<_BinaryPredicate&, decltype(*__first1), decltype(*__first2)>::value,170 "The comparator has to be callable");171 auto __proj = __identity();172 return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first;173}174 175template <class _ForwardIterator1, class _ForwardIterator2>176[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1177search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {178 return std::search(__first1, __last1, __first2, __last2, __equal_to());179}180 181#if _LIBCPP_STD_VER >= 17182template <class _ForwardIterator, class _Searcher>183[[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator184search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher& __s) {185 return __s(__f, __l).first;186}187 188#endif189 190_LIBCPP_END_NAMESPACE_STD191 192#endif // _LIBCPP___ALGORITHM_SEARCH_H193