226 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_FIND_END_OF_H11#define _LIBCPP___CXX03___ALGORITHM_FIND_END_OF_H12 13#include <__cxx03/__algorithm/comp.h>14#include <__cxx03/__algorithm/iterator_operations.h>15#include <__cxx03/__algorithm/search.h>16#include <__cxx03/__config>17#include <__cxx03/__functional/identity.h>18#include <__cxx03/__iterator/advance.h>19#include <__cxx03/__iterator/iterator_traits.h>20#include <__cxx03/__iterator/next.h>21#include <__cxx03/__iterator/reverse_iterator.h>22#include <__cxx03/__type_traits/invoke.h>23#include <__cxx03/__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 inline pair<_Iter1, _Iter1> __find_end_impl(40 _Iter1 __first1,41 _Sent1 __last1,42 _Iter2 __first2,43 _Sent2 __last2,44 _Pred& __pred,45 _Proj1& __proj1,46 _Proj2& __proj2,47 forward_iterator_tag,48 forward_iterator_tag) {49 // modeled after search algorithm50 _Iter1 __match_first = _IterOps<_AlgPolicy>::next(__first1, __last1); // __last1 is the "default" answer51 _Iter1 __match_last = __match_first;52 if (__first2 == __last2)53 return pair<_Iter1, _Iter1>(__match_last, __match_last);54 while (true) {55 while (true) {56 if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found)57 return pair<_Iter1, _Iter1>(__match_first, __match_last);58 if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))59 break;60 ++__first1;61 }62 // *__first1 matches *__first2, now match elements after here63 _Iter1 __m1 = __first1;64 _Iter2 __m2 = __first2;65 while (true) {66 if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one67 __match_first = __first1;68 __match_last = ++__m1;69 ++__first1;70 break;71 }72 if (++__m1 == __last1) // Source exhausted, return last answer73 return pair<_Iter1, _Iter1>(__match_first, __match_last);74 // mismatch, restart with a new __first75 if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) {76 ++__first1;77 break;78 } // else there is a match, check next elements79 }80 }81}82 83template < class _IterOps,84 class _Pred,85 class _Iter1,86 class _Sent1,87 class _Iter2,88 class _Sent2,89 class _Proj1,90 class _Proj2>91_LIBCPP_HIDE_FROM_ABI _Iter1 __find_end(92 _Iter1 __first1,93 _Sent1 __sent1,94 _Iter2 __first2,95 _Sent2 __sent2,96 _Pred& __pred,97 _Proj1& __proj1,98 _Proj2& __proj2,99 bidirectional_iterator_tag,100 bidirectional_iterator_tag) {101 auto __last1 = _IterOps::next(__first1, __sent1);102 auto __last2 = _IterOps::next(__first2, __sent2);103 // modeled after search algorithm (in reverse)104 if (__first2 == __last2)105 return __last1; // Everything matches an empty sequence106 _Iter1 __l1 = __last1;107 _Iter2 __l2 = __last2;108 --__l2;109 while (true) {110 // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks111 while (true) {112 if (__first1 == __l1) // return __last1 if no element matches *__first2113 return __last1;114 if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2)))115 break;116 }117 // *__l1 matches *__l2, now match elements before here118 _Iter1 __m1 = __l1;119 _Iter2 __m2 = __l2;120 while (true) {121 if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)122 return __m1;123 if (__m1 == __first1) // Otherwise if source exhaused, pattern not found124 return __last1;125 126 // if there is a mismatch, restart with a new __l1127 if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2))) {128 break;129 } // else there is a match, check next elements130 }131 }132}133 134template < class _AlgPolicy,135 class _Pred,136 class _Iter1,137 class _Sent1,138 class _Iter2,139 class _Sent2,140 class _Proj1,141 class _Proj2>142_LIBCPP_HIDE_FROM_ABI _Iter1 __find_end(143 _Iter1 __first1,144 _Sent1 __sent1,145 _Iter2 __first2,146 _Sent2 __sent2,147 _Pred& __pred,148 _Proj1& __proj1,149 _Proj2& __proj2,150 random_access_iterator_tag,151 random_access_iterator_tag) {152 typedef typename iterator_traits<_Iter1>::difference_type _D1;153 auto __last1 = _IterOps<_AlgPolicy>::next(__first1, __sent1);154 auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __sent2);155 // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern156 auto __len2 = __last2 - __first2;157 if (__len2 == 0)158 return __last1;159 auto __len1 = __last1 - __first1;160 if (__len1 < __len2)161 return __last1;162 const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here163 _Iter1 __l1 = __last1;164 _Iter2 __l2 = __last2;165 --__l2;166 while (true) {167 while (true) {168 if (__s == __l1)169 return __last1;170 if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2)))171 break;172 }173 _Iter1 __m1 = __l1;174 _Iter2 __m2 = __l2;175 while (true) {176 if (__m2 == __first2)177 return __m1;178 // no need to check range on __m1 because __s guarantees we have enough source179 if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) {180 break;181 }182 }183 }184}185 186template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>187_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator1 __find_end_classic(188 _ForwardIterator1 __first1,189 _ForwardIterator1 __last1,190 _ForwardIterator2 __first2,191 _ForwardIterator2 __last2,192 _BinaryPredicate& __pred) {193 auto __proj = __identity();194 return std::__find_end_impl<_ClassicAlgPolicy>(195 __first1,196 __last1,197 __first2,198 __last2,199 __pred,200 __proj,201 __proj,202 typename iterator_traits<_ForwardIterator1>::iterator_category(),203 typename iterator_traits<_ForwardIterator2>::iterator_category())204 .first;205}206 207template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>208_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator1 find_end(209 _ForwardIterator1 __first1,210 _ForwardIterator1 __last1,211 _ForwardIterator2 __first2,212 _ForwardIterator2 __last2,213 _BinaryPredicate __pred) {214 return std::__find_end_classic(__first1, __last1, __first2, __last2, __pred);215}216 217template <class _ForwardIterator1, class _ForwardIterator2>218_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _ForwardIterator1219find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {220 return std::find_end(__first1, __last1, __first2, __last2, __equal_to());221}222 223_LIBCPP_END_NAMESPACE_STD224 225#endif // _LIBCPP___CXX03___ALGORITHM_FIND_END_OF_H226