v1/__algorithm/search.h

0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP___ALGORITHM_SEARCH_H
0011 #define _LIBCPP___ALGORITHM_SEARCH_H
0012
0013 #include <__algorithm/comp.h>
0014 #include <__algorithm/iterator_operations.h>
0015 #include <__config>
0016 #include <__functional/identity.h>
0017 #include <__iterator/advance.h>
0018 #include <__iterator/concepts.h>
0019 #include <__iterator/iterator_traits.h>
0020 #include <__type_traits/enable_if.h>
0021 #include <__type_traits/invoke.h>
0022 #include <__type_traits/is_callable.h>
0023 #include <__utility/pair.h>
0024
0025 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0026 #  pragma GCC system_header
0027 #endif
0028
0029 _LIBCPP_BEGIN_NAMESPACE_STD
0030
0031 template <class _AlgPolicy,
0032           class _Iter1,
0033           class _Sent1,
0034           class _Iter2,
0035           class _Sent2,
0036           class _Pred,
0037           class _Proj1,
0038           class _Proj2>
0039 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __search_forward_impl(
0040     _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
0041   if (__first2 == __last2)
0042     return std::make_pair(__first1, __first1); // Everything matches an empty sequence
0043   while (true) {
0044     // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
0045     while (true) {
0046       if (__first1 == __last1) { // return __last1 if no element matches *__first2
0047         _IterOps<_AlgPolicy>::__advance_to(__first1, __last1);
0048         return std::make_pair(__first1, __first1);
0049       }
0050       if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
0051         break;
0052       ++__first1;
0053     }
0054     // *__first1 matches *__first2, now match elements after here
0055     _Iter1 __m1 = __first1;
0056     _Iter2 __m2 = __first2;
0057     while (true) {
0058       if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
0059         return std::make_pair(__first1, ++__m1);
0060       if (++__m1 == __last1) { // Otherwise if source exhaused, pattern not found
0061         return std::make_pair(__m1, __m1);
0062       }
0063
0064       // if there is a mismatch, restart with a new __first1
0065       if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {
0066         ++__first1;
0067         break;
0068       } // else there is a match, check next elements
0069     }
0070   }
0071 }
0072
0073 template <class _AlgPolicy,
0074           class _Iter1,
0075           class _Sent1,
0076           class _Iter2,
0077           class _Sent2,
0078           class _Pred,
0079           class _Proj1,
0080           class _Proj2,
0081           class _DiffT1,
0082           class _DiffT2>
0083 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __search_random_access_impl(
0084     _Iter1 __first1,
0085     _Sent1 __last1,
0086     _Iter2 __first2,
0087     _Sent2 __last2,
0088     _Pred& __pred,
0089     _Proj1& __proj1,
0090     _Proj2& __proj2,
0091     _DiffT1 __size1,
0092     _DiffT2 __size2) {
0093   const _Iter1 __s = __first1 + __size1 - _DiffT1(__size2 - 1); // Start of pattern match can't go beyond here
0094
0095   while (true) {
0096     while (true) {
0097       if (__first1 == __s) {
0098         _IterOps<_AlgPolicy>::__advance_to(__first1, __last1);
0099         return std::make_pair(__first1, __first1);
0100       }
0101       if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
0102         break;
0103       ++__first1;
0104     }
0105
0106     _Iter1 __m1 = __first1;
0107     _Iter2 __m2 = __first2;
0108     while (true) {
0109       if (++__m2 == __last2)
0110         return std::make_pair(__first1, __first1 + _DiffT1(__size2));
0111       ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
0112       if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {
0113         ++__first1;
0114         break;
0115       }
0116     }
0117   }
0118 }
0119
0120 template <class _Iter1,
0121           class _Sent1,
0122           class _Iter2,
0123           class _Sent2,
0124           class _Pred,
0125           class _Proj1,
0126           class _Proj2,
0127           __enable_if_t<__has_random_access_iterator_category<_Iter1>::value &&
0128                             __has_random_access_iterator_category<_Iter2>::value,
0129                         int> = 0>
0130 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __search_impl(
0131     _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
0132   auto __size2 = __last2 - __first2;
0133   if (__size2 == 0)
0134     return std::make_pair(__first1, __first1);
0135
0136   auto __size1 = __last1 - __first1;
0137   if (__size1 < __size2) {
0138     return std::make_pair(__last1, __last1);
0139   }
0140
0141   return std::__search_random_access_impl<_ClassicAlgPolicy>(
0142       __first1, __last1, __first2, __last2, __pred, __proj1, __proj2, __size1, __size2);
0143 }
0144
0145 template <
0146     class _Iter1,
0147     class _Sent1,
0148     class _Iter2,
0149     class _Sent2,
0150     class _Pred,
0151     class _Proj1,
0152     class _Proj2,
0153     __enable_if_t<__has_forward_iterator_category<_Iter1>::value && __has_forward_iterator_category<_Iter2>::value &&
0154                       !(__has_random_access_iterator_category<_Iter1>::value &&
0155                         __has_random_access_iterator_category<_Iter2>::value),
0156                   int> = 0>
0157 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __search_impl(
0158     _Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) {
0159   return std::__search_forward_impl<_ClassicAlgPolicy>(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2);
0160 }
0161
0162 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
0163 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1
0164 search(_ForwardIterator1 __first1,
0165        _ForwardIterator1 __last1,
0166        _ForwardIterator2 __first2,
0167        _ForwardIterator2 __last2,
0168        _BinaryPredicate __pred) {
0169   static_assert(__is_callable<_BinaryPredicate&, decltype(*__first1), decltype(*__first2)>::value,
0170                 "The comparator has to be callable");
0171   auto __proj = __identity();
0172   return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first;
0173 }
0174
0175 template <class _ForwardIterator1, class _ForwardIterator2>
0176 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1
0177 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {
0178   return std::search(__first1, __last1, __first2, __last2, __equal_to());
0179 }
0180
0181 #if _LIBCPP_STD_VER >= 17
0182 template <class _ForwardIterator, class _Searcher>
0183 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator
0184 search(_ForwardIterator __f, _ForwardIterator __l, const _Searcher& __s) {
0185   return __s(__f, __l).first;
0186 }
0187
0188 #endif
0189
0190 _LIBCPP_END_NAMESPACE_STD
0191
0192 #endif // _LIBCPP___ALGORITHM_SEARCH_H