1139749Simp// -*- C++ -*- 2122526Ssimokawa//===----------------------------------------------------------------------===// 3122526Ssimokawa// 4103285Sikob// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5103285Sikob// See https://llvm.org/LICENSE.txt for license information. 6103285Sikob// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7103285Sikob// 8103285Sikob//===----------------------------------------------------------------------===// 9103285Sikob 10103285Sikob#ifndef _LIBCPP___ALGORITHM_FIND_END_OF_H 11103285Sikob#define _LIBCPP___ALGORITHM_FIND_END_OF_H 12103285Sikob 13103285Sikob#include <__algorithm/comp.h> 14103285Sikob#include <__algorithm/iterator_operations.h> 15103285Sikob#include <__algorithm/search.h> 16103285Sikob#include <__config> 17103285Sikob#include <__functional/identity.h> 18103285Sikob#include <__functional/invoke.h> 19103285Sikob#include <__iterator/advance.h> 20103285Sikob#include <__iterator/iterator_traits.h> 21103285Sikob#include <__iterator/next.h> 22103285Sikob#include <__iterator/reverse_iterator.h> 23103285Sikob#include <__utility/pair.h> 24103285Sikob 25103285Sikob#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 26103285Sikob# pragma GCC system_header 27103285Sikob#endif 28103285Sikob 29103285Sikob_LIBCPP_BEGIN_NAMESPACE_STD 30103285Sikob 31103285Sikobtemplate < class _AlgPolicy, 32103285Sikob class _Iter1, 33103285Sikob class _Sent1, 34103285Sikob class _Iter2, 35103285Sikob class _Sent2, 36103285Sikob class _Pred, 37103285Sikob class _Proj1, 38103285Sikob class _Proj2> 39103285Sikob_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __find_end_impl( 40103285Sikob _Iter1 __first1, 41103285Sikob _Sent1 __last1, 42127468Ssimokawa _Iter2 __first2, 43103285Sikob _Sent2 __last2, 44103285Sikob _Pred& __pred, 45103285Sikob _Proj1& __proj1, 46127468Ssimokawa _Proj2& __proj2, 47117126Sscottl forward_iterator_tag, 48117126Sscottl forward_iterator_tag) { 49117732Ssimokawa // modeled after search algorithm 50103285Sikob _Iter1 __match_first = _IterOps<_AlgPolicy>::next(__first1, __last1); // __last1 is the "default" answer 51127468Ssimokawa _Iter1 __match_last = __match_first; 52112136Ssimokawa if (__first2 == __last2) 53112136Ssimokawa return pair<_Iter1, _Iter1>(__match_last, __match_last); 54103285Sikob while (true) { 55127468Ssimokawa while (true) { 56127468Ssimokawa if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found) 57127468Ssimokawa return pair<_Iter1, _Iter1>(__match_first, __match_last); 58127468Ssimokawa if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) 59127468Ssimokawa break; 60127468Ssimokawa ++__first1; 61127468Ssimokawa } 62127468Ssimokawa // *__first1 matches *__first2, now match elements after here 63127468Ssimokawa _Iter1 __m1 = __first1; 64127468Ssimokawa _Iter2 __m2 = __first2; 65127468Ssimokawa while (true) { 66127468Ssimokawa if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one 67127468Ssimokawa __match_first = __first1; 68127468Ssimokawa __match_last = ++__m1; 69127468Ssimokawa ++__first1; 70103285Sikob break; 71103285Sikob } 72103285Sikob if (++__m1 == __last1) // Source exhausted, return last answer 73103285Sikob return pair<_Iter1, _Iter1>(__match_first, __match_last); 74103285Sikob // mismatch, restart with a new __first 75103285Sikob if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { 76103285Sikob ++__first1; 77103285Sikob break; 78103285Sikob } // else there is a match, check next elements 79103285Sikob } 80113584Ssimokawa } 81103285Sikob} 82120660Ssimokawa 83127468Ssimokawatemplate < class _IterOps, 84103285Sikob class _Pred, 85103285Sikob class _Iter1, 86103285Sikob class _Sent1, 87103285Sikob class _Iter2, 88111615Ssimokawa class _Sent2, 89121185Ssimokawa class _Proj1, 90121185Ssimokawa class _Proj2> 91121185Ssimokawa_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter1 __find_end( 92121185Ssimokawa _Iter1 __first1, 93121185Ssimokawa _Sent1 __sent1, 94167622Ssimokawa _Iter2 __first2, 95113584Ssimokawa _Sent2 __sent2, 96113584Ssimokawa _Pred& __pred, 97113584Ssimokawa _Proj1& __proj1, 98103285Sikob _Proj2& __proj2, 99113584Ssimokawa bidirectional_iterator_tag, 100111615Ssimokawa bidirectional_iterator_tag) { 101111615Ssimokawa auto __last1 = _IterOps::next(__first1, __sent1); 102111615Ssimokawa auto __last2 = _IterOps::next(__first2, __sent2); 103111615Ssimokawa // modeled after search algorithm (in reverse) 104130532Sdfr if (__first2 == __last2) 105111615Ssimokawa return __last1; // Everything matches an empty sequence 106111615Ssimokawa _Iter1 __l1 = __last1; 107120660Ssimokawa _Iter2 __l2 = __last2; 108111615Ssimokawa --__l2; 109111615Ssimokawa while (true) { 110111615Ssimokawa // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks 111103285Sikob while (true) { 112120660Ssimokawa if (__first1 == __l1) // return __last1 if no element matches *__first2 113120660Ssimokawa return __last1; 114120660Ssimokawa if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) 115120660Ssimokawa break; 116103285Sikob } 117103285Sikob // *__l1 matches *__l2, now match elements before here 118120660Ssimokawa _Iter1 __m1 = __l1; 119103285Sikob _Iter2 __m2 = __l2; 120103285Sikob while (true) { 121120660Ssimokawa if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) 122103285Sikob return __m1; 123103285Sikob if (__m1 == __first1) // Otherwise if source exhaused, pattern not found 124111203Ssimokawa return __last1; 125103285Sikob 126124251Ssimokawa // if there is a mismatch, restart with a new __l1 127111199Ssimokawa if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2))) { 128122387Ssimokawa break; 129122387Ssimokawa } // else there is a match, check next elements 130122387Ssimokawa } 131127468Ssimokawa } 132127468Ssimokawa} 133103285Sikob 134103285Sikobtemplate < class _AlgPolicy, 135103285Sikob class _Pred, 136103285Sikob class _Iter1, 137103285Sikob class _Sent1, 138103285Sikob class _Iter2, 139103285Sikob class _Sent2, 140103285Sikob class _Proj1, 141103285Sikob class _Proj2> 142121792Ssimokawa_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iter1 __find_end( 143130677Ssimokawa _Iter1 __first1, 144122387Ssimokawa _Sent1 __sent1, 145122387Ssimokawa _Iter2 __first2, 146122387Ssimokawa _Sent2 __sent2, 147122387Ssimokawa _Pred& __pred, 148127468Ssimokawa _Proj1& __proj1, 149127468Ssimokawa _Proj2& __proj2, 150127468Ssimokawa random_access_iterator_tag, 151127468Ssimokawa random_access_iterator_tag) { 152103285Sikob typedef typename iterator_traits<_Iter1>::difference_type _D1; 153122387Ssimokawa auto __last1 = _IterOps<_AlgPolicy>::next(__first1, __sent1); 154122387Ssimokawa auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __sent2); 155122387Ssimokawa // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern 156122387Ssimokawa auto __len2 = __last2 - __first2; 157122387Ssimokawa if (__len2 == 0) 158127468Ssimokawa return __last1; 159127468Ssimokawa auto __len1 = __last1 - __first1; 160122387Ssimokawa if (__len1 < __len2) 161103285Sikob return __last1; 162103285Sikob const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here 163113584Ssimokawa _Iter1 __l1 = __last1; 164113584Ssimokawa _Iter2 __l2 = __last2; 165167622Ssimokawa --__l2; 166113584Ssimokawa while (true) { 167167622Ssimokawa while (true) { 168113584Ssimokawa if (__s == __l1) 169103285Sikob return __last1; 170103285Sikob if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) 171103285Sikob break; 172113584Ssimokawa } 173129585Sdfr _Iter1 __m1 = __l1; 174129585Sdfr _Iter2 __m2 = __l2; 175120660Ssimokawa while (true) { 176103285Sikob if (__m2 == __first2) 177113584Ssimokawa return __m1; 178103285Sikob // no need to check range on __m1 because __s guarantees we have enough source 179103285Sikob if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) { 180113584Ssimokawa break; 181103285Sikob } 182103285Sikob } 183113584Ssimokawa } 184103285Sikob} 185103285Sikob 186103285Sikobtemplate <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 187114732Ssimokawa_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator1 __find_end_classic( 188110336Ssimokawa _ForwardIterator1 __first1, 189103285Sikob _ForwardIterator1 __last1, 190110336Ssimokawa _ForwardIterator2 __first2, 191103285Sikob _ForwardIterator2 __last2, 192103285Sikob _BinaryPredicate& __pred) { 193103285Sikob auto __proj = __identity(); 194103285Sikob return std::__find_end_impl<_ClassicAlgPolicy>( 195103285Sikob __first1, 196129585Sdfr __last1, 197114732Ssimokawa __first2, 198129585Sdfr __last2, 199129585Sdfr __pred, 200129585Sdfr __proj, 201121185Ssimokawa __proj, 202121185Ssimokawa typename iterator_traits<_ForwardIterator1>::iterator_category(), 203121185Ssimokawa typename iterator_traits<_ForwardIterator2>::iterator_category()) 204121185Ssimokawa .first; 205127468Ssimokawa} 206127468Ssimokawa 207127468Ssimokawatemplate <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 208129585Sdfr_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 find_end( 209103285Sikob _ForwardIterator1 __first1, 210103285Sikob _ForwardIterator1 __last1, 211113584Ssimokawa _ForwardIterator2 __first2, 212113584Ssimokawa _ForwardIterator2 __last2, 213111615Ssimokawa _BinaryPredicate __pred) { 214113584Ssimokawa return std::__find_end_classic(__first1, __last1, __first2, __last2, __pred); 215103285Sikob} 216113584Ssimokawa 217127468Ssimokawatemplate <class _ForwardIterator1, class _ForwardIterator2> 218103285Sikob_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 219103285Sikobfind_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { 220103285Sikob return std::find_end(__first1, __last1, __first2, __last2, __equal_to()); 221188756Ssbruno} 222103285Sikob 223103285Sikob_LIBCPP_END_NAMESPACE_STD 224103285Sikob 225103285Sikob#endif // _LIBCPP___ALGORITHM_FIND_END_OF_H 226103285Sikob