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_FIND_END_OF_H 11 #define _LIBCPP___ALGORITHM_FIND_END_OF_H 12 13 #include <__algorithm/comp.h> 14 #include <__algorithm/iterator_operations.h> 15 #include <__config> 16 #include <__functional/identity.h> 17 #include <__iterator/iterator_traits.h> 18 #include <__type_traits/invoke.h> 19 #include <__utility/pair.h> 20 21 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 22 # pragma GCC system_header 23 #endif 24 25 _LIBCPP_BEGIN_NAMESPACE_STD 26 27 template < class _AlgPolicy, 28 class _Iter1, 29 class _Sent1, 30 class _Iter2, 31 class _Sent2, 32 class _Pred, 33 class _Proj1, 34 class _Proj2> 35 _LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __find_end_impl( 36 _Iter1 __first1, 37 _Sent1 __last1, 38 _Iter2 __first2, 39 _Sent2 __last2, 40 _Pred& __pred, 41 _Proj1& __proj1, 42 _Proj2& __proj2, 43 forward_iterator_tag, 44 forward_iterator_tag) { 45 // modeled after search algorithm 46 _Iter1 __match_first = _IterOps<_AlgPolicy>::next(__first1, __last1); // __last1 is the "default" answer 47 _Iter1 __match_last = __match_first; 48 if (__first2 == __last2) 49 return pair<_Iter1, _Iter1>(__match_last, __match_last); 50 while (true) { 51 while (true) { 52 if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found) 53 return pair<_Iter1, _Iter1>(__match_first, __match_last); 54 if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) 55 break; 56 ++__first1; 57 } 58 // *__first1 matches *__first2, now match elements after here 59 _Iter1 __m1 = __first1; 60 _Iter2 __m2 = __first2; 61 while (true) { 62 if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one 63 __match_first = __first1; 64 __match_last = ++__m1; 65 ++__first1; 66 break; 67 } 68 if (++__m1 == __last1) // Source exhausted, return last answer 69 return pair<_Iter1, _Iter1>(__match_first, __match_last); 70 // mismatch, restart with a new __first 71 if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { 72 ++__first1; 73 break; 74 } // else there is a match, check next elements 75 } 76 } 77 } 78 79 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 80 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator1 __find_end_classic( 81 _ForwardIterator1 __first1, 82 _ForwardIterator1 __last1, 83 _ForwardIterator2 __first2, 84 _ForwardIterator2 __last2, 85 _BinaryPredicate& __pred) { 86 auto __proj = __identity(); 87 return std::__find_end_impl<_ClassicAlgPolicy>( 88 __first1, 89 __last1, 90 __first2, 91 __last2, 92 __pred, 93 __proj, 94 __proj, 95 typename iterator_traits<_ForwardIterator1>::iterator_category(), 96 typename iterator_traits<_ForwardIterator2>::iterator_category()) 97 .first; 98 } 99 100 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 101 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 find_end( 102 _ForwardIterator1 __first1, 103 _ForwardIterator1 __last1, 104 _ForwardIterator2 __first2, 105 _ForwardIterator2 __last2, 106 _BinaryPredicate __pred) { 107 return std::__find_end_classic(__first1, __last1, __first2, __last2, __pred); 108 } 109 110 template <class _ForwardIterator1, class _ForwardIterator2> 111 [[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 112 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { 113 return std::find_end(__first1, __last1, __first2, __last2, __equal_to()); 114 } 115 116 _LIBCPP_END_NAMESPACE_STD 117 118 #endif // _LIBCPP___ALGORITHM_FIND_END_OF_H 119