119 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_FIND_END_OF_H11#define _LIBCPP___ALGORITHM_FIND_END_OF_H12 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_header23#endif24 25_LIBCPP_BEGIN_NAMESPACE_STD26 27template < 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 algorithm46 _Iter1 __match_first = _IterOps<_AlgPolicy>::next(__first1, __last1); // __last1 is the "default" answer47 _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 here59 _Iter1 __m1 = __first1;60 _Iter2 __m2 = __first2;61 while (true) {62 if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one63 __match_first = __first1;64 __match_last = ++__m1;65 ++__first1;66 break;67 }68 if (++__m1 == __last1) // Source exhausted, return last answer69 return pair<_Iter1, _Iter1>(__match_first, __match_last);70 // mismatch, restart with a new __first71 if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {72 ++__first1;73 break;74 } // else there is a match, check next elements75 }76 }77}78 79template <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 100template <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 110template <class _ForwardIterator1, class _ForwardIterator2>111[[__nodiscard__]] inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1112find_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_STD117 118#endif // _LIBCPP___ALGORITHM_FIND_END_OF_H119