1fe6060f1SDimitry Andric // -*- C++ -*- 2fe6060f1SDimitry Andric //===----------------------------------------------------------------------===// 3fe6060f1SDimitry Andric // 4fe6060f1SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5fe6060f1SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 6fe6060f1SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7fe6060f1SDimitry Andric // 8fe6060f1SDimitry Andric //===----------------------------------------------------------------------===// 9fe6060f1SDimitry Andric 10fe6060f1SDimitry Andric #ifndef _LIBCPP___ALGORITHM_FIND_END_OF_H 11fe6060f1SDimitry Andric #define _LIBCPP___ALGORITHM_FIND_END_OF_H 12fe6060f1SDimitry Andric 13fe6060f1SDimitry Andric #include <__algorithm/comp.h> 14753f127fSDimitry Andric #include <__algorithm/iterator_operations.h> 15753f127fSDimitry Andric #include <__algorithm/search.h> 1604eeddc0SDimitry Andric #include <__config> 17753f127fSDimitry Andric #include <__functional/identity.h> 1806c3fb27SDimitry Andric #include <__functional/invoke.h> 19753f127fSDimitry Andric #include <__iterator/advance.h> 20fe6060f1SDimitry Andric #include <__iterator/iterator_traits.h> 21753f127fSDimitry Andric #include <__iterator/next.h> 22753f127fSDimitry Andric #include <__iterator/reverse_iterator.h> 23753f127fSDimitry Andric #include <__utility/pair.h> 24fe6060f1SDimitry Andric 25fe6060f1SDimitry Andric #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 26fe6060f1SDimitry Andric # pragma GCC system_header 27fe6060f1SDimitry Andric #endif 28fe6060f1SDimitry Andric 29fe6060f1SDimitry Andric _LIBCPP_BEGIN_NAMESPACE_STD 30fe6060f1SDimitry Andric 31cb14a3feSDimitry Andric template < class _AlgPolicy, 32753f127fSDimitry Andric class _Iter1, 33753f127fSDimitry Andric class _Sent1, 34753f127fSDimitry Andric class _Iter2, 35753f127fSDimitry Andric class _Sent2, 36753f127fSDimitry Andric class _Pred, 37753f127fSDimitry Andric class _Proj1, 38753f127fSDimitry Andric class _Proj2> 39bdd1243dSDimitry Andric _LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_Iter1, _Iter1> __find_end_impl( 40753f127fSDimitry Andric _Iter1 __first1, 41753f127fSDimitry Andric _Sent1 __last1, 42753f127fSDimitry Andric _Iter2 __first2, 43753f127fSDimitry Andric _Sent2 __last2, 44753f127fSDimitry Andric _Pred& __pred, 45753f127fSDimitry Andric _Proj1& __proj1, 46753f127fSDimitry Andric _Proj2& __proj2, 47753f127fSDimitry Andric forward_iterator_tag, 48fe6060f1SDimitry Andric forward_iterator_tag) { 49fe6060f1SDimitry Andric // modeled after search algorithm 50753f127fSDimitry Andric _Iter1 __match_first = _IterOps<_AlgPolicy>::next(__first1, __last1); // __last1 is the "default" answer 51753f127fSDimitry Andric _Iter1 __match_last = __match_first; 52fe6060f1SDimitry Andric if (__first2 == __last2) 53753f127fSDimitry Andric return pair<_Iter1, _Iter1>(__match_last, __match_last); 54fe6060f1SDimitry Andric while (true) { 55fe6060f1SDimitry Andric while (true) { 56753f127fSDimitry Andric if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found) 57753f127fSDimitry Andric return pair<_Iter1, _Iter1>(__match_first, __match_last); 58753f127fSDimitry Andric if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) 59fe6060f1SDimitry Andric break; 60fe6060f1SDimitry Andric ++__first1; 61fe6060f1SDimitry Andric } 62fe6060f1SDimitry Andric // *__first1 matches *__first2, now match elements after here 63753f127fSDimitry Andric _Iter1 __m1 = __first1; 64753f127fSDimitry Andric _Iter2 __m2 = __first2; 65fe6060f1SDimitry Andric while (true) { 66fe6060f1SDimitry Andric if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one 67753f127fSDimitry Andric __match_first = __first1; 68753f127fSDimitry Andric __match_last = ++__m1; 69fe6060f1SDimitry Andric ++__first1; 70fe6060f1SDimitry Andric break; 71fe6060f1SDimitry Andric } 72fe6060f1SDimitry Andric if (++__m1 == __last1) // Source exhausted, return last answer 73753f127fSDimitry Andric return pair<_Iter1, _Iter1>(__match_first, __match_last); 74753f127fSDimitry Andric // mismatch, restart with a new __first 75cb14a3feSDimitry Andric if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { 76fe6060f1SDimitry Andric ++__first1; 77fe6060f1SDimitry Andric break; 78fe6060f1SDimitry Andric } // else there is a match, check next elements 79fe6060f1SDimitry Andric } 80fe6060f1SDimitry Andric } 81fe6060f1SDimitry Andric } 82fe6060f1SDimitry Andric 83cb14a3feSDimitry Andric template < class _IterOps, 84753f127fSDimitry Andric class _Pred, 85753f127fSDimitry Andric class _Iter1, 86753f127fSDimitry Andric class _Sent1, 87753f127fSDimitry Andric class _Iter2, 88753f127fSDimitry Andric class _Sent2, 89753f127fSDimitry Andric class _Proj1, 90753f127fSDimitry Andric class _Proj2> 91bdd1243dSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Iter1 __find_end( 92753f127fSDimitry Andric _Iter1 __first1, 93753f127fSDimitry Andric _Sent1 __sent1, 94753f127fSDimitry Andric _Iter2 __first2, 95753f127fSDimitry Andric _Sent2 __sent2, 96753f127fSDimitry Andric _Pred& __pred, 97753f127fSDimitry Andric _Proj1& __proj1, 98753f127fSDimitry Andric _Proj2& __proj2, 99753f127fSDimitry Andric bidirectional_iterator_tag, 100753f127fSDimitry Andric bidirectional_iterator_tag) { 101753f127fSDimitry Andric auto __last1 = _IterOps::next(__first1, __sent1); 102753f127fSDimitry Andric auto __last2 = _IterOps::next(__first2, __sent2); 103fe6060f1SDimitry Andric // modeled after search algorithm (in reverse) 104fe6060f1SDimitry Andric if (__first2 == __last2) 105fe6060f1SDimitry Andric return __last1; // Everything matches an empty sequence 106753f127fSDimitry Andric _Iter1 __l1 = __last1; 107753f127fSDimitry Andric _Iter2 __l2 = __last2; 108fe6060f1SDimitry Andric --__l2; 109fe6060f1SDimitry Andric while (true) { 110fe6060f1SDimitry Andric // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks 111fe6060f1SDimitry Andric while (true) { 112fe6060f1SDimitry Andric if (__first1 == __l1) // return __last1 if no element matches *__first2 113fe6060f1SDimitry Andric return __last1; 114753f127fSDimitry Andric if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) 115fe6060f1SDimitry Andric break; 116fe6060f1SDimitry Andric } 117fe6060f1SDimitry Andric // *__l1 matches *__l2, now match elements before here 118753f127fSDimitry Andric _Iter1 __m1 = __l1; 119753f127fSDimitry Andric _Iter2 __m2 = __l2; 120fe6060f1SDimitry Andric while (true) { 121fe6060f1SDimitry Andric if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) 122fe6060f1SDimitry Andric return __m1; 123fe6060f1SDimitry Andric if (__m1 == __first1) // Otherwise if source exhaused, pattern not found 124fe6060f1SDimitry Andric return __last1; 125753f127fSDimitry Andric 126753f127fSDimitry Andric // if there is a mismatch, restart with a new __l1 127cb14a3feSDimitry Andric if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2))) { 128fe6060f1SDimitry Andric break; 129fe6060f1SDimitry Andric } // else there is a match, check next elements 130fe6060f1SDimitry Andric } 131fe6060f1SDimitry Andric } 132fe6060f1SDimitry Andric } 133fe6060f1SDimitry Andric 134cb14a3feSDimitry Andric template < class _AlgPolicy, 135753f127fSDimitry Andric class _Pred, 136753f127fSDimitry Andric class _Iter1, 137753f127fSDimitry Andric class _Sent1, 138753f127fSDimitry Andric class _Iter2, 139753f127fSDimitry Andric class _Sent2, 140753f127fSDimitry Andric class _Proj1, 141753f127fSDimitry Andric class _Proj2> 142bdd1243dSDimitry Andric _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iter1 __find_end( 143753f127fSDimitry Andric _Iter1 __first1, 144753f127fSDimitry Andric _Sent1 __sent1, 145753f127fSDimitry Andric _Iter2 __first2, 146753f127fSDimitry Andric _Sent2 __sent2, 147753f127fSDimitry Andric _Pred& __pred, 148753f127fSDimitry Andric _Proj1& __proj1, 149753f127fSDimitry Andric _Proj2& __proj2, 150753f127fSDimitry Andric random_access_iterator_tag, 151753f127fSDimitry Andric random_access_iterator_tag) { 152753f127fSDimitry Andric typedef typename iterator_traits<_Iter1>::difference_type _D1; 153753f127fSDimitry Andric auto __last1 = _IterOps<_AlgPolicy>::next(__first1, __sent1); 154753f127fSDimitry Andric auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __sent2); 155fe6060f1SDimitry Andric // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern 156753f127fSDimitry Andric auto __len2 = __last2 - __first2; 157fe6060f1SDimitry Andric if (__len2 == 0) 158fe6060f1SDimitry Andric return __last1; 159753f127fSDimitry Andric auto __len1 = __last1 - __first1; 160fe6060f1SDimitry Andric if (__len1 < __len2) 161fe6060f1SDimitry Andric return __last1; 162753f127fSDimitry Andric const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here 163753f127fSDimitry Andric _Iter1 __l1 = __last1; 164753f127fSDimitry Andric _Iter2 __l2 = __last2; 165fe6060f1SDimitry Andric --__l2; 166fe6060f1SDimitry Andric while (true) { 167fe6060f1SDimitry Andric while (true) { 168fe6060f1SDimitry Andric if (__s == __l1) 169fe6060f1SDimitry Andric return __last1; 170753f127fSDimitry Andric if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) 171fe6060f1SDimitry Andric break; 172fe6060f1SDimitry Andric } 173753f127fSDimitry Andric _Iter1 __m1 = __l1; 174753f127fSDimitry Andric _Iter2 __m2 = __l2; 175fe6060f1SDimitry Andric while (true) { 176fe6060f1SDimitry Andric if (__m2 == __first2) 177fe6060f1SDimitry Andric return __m1; 178fe6060f1SDimitry Andric // no need to check range on __m1 because __s guarantees we have enough source 179753f127fSDimitry Andric if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) { 180fe6060f1SDimitry Andric break; 181fe6060f1SDimitry Andric } 182fe6060f1SDimitry Andric } 183fe6060f1SDimitry Andric } 184fe6060f1SDimitry Andric } 185fe6060f1SDimitry Andric 186fe6060f1SDimitry Andric template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 187cb14a3feSDimitry Andric _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator1 __find_end_classic( 188cb14a3feSDimitry Andric _ForwardIterator1 __first1, 189cb14a3feSDimitry Andric _ForwardIterator1 __last1, 190cb14a3feSDimitry Andric _ForwardIterator2 __first2, 191cb14a3feSDimitry Andric _ForwardIterator2 __last2, 192753f127fSDimitry Andric _BinaryPredicate& __pred) { 193753f127fSDimitry Andric auto __proj = __identity(); 194753f127fSDimitry Andric return std::__find_end_impl<_ClassicAlgPolicy>( 195753f127fSDimitry Andric __first1, 196753f127fSDimitry Andric __last1, 197753f127fSDimitry Andric __first2, 198753f127fSDimitry Andric __last2, 199753f127fSDimitry Andric __pred, 200753f127fSDimitry Andric __proj, 201753f127fSDimitry Andric __proj, 202753f127fSDimitry Andric typename iterator_traits<_ForwardIterator1>::iterator_category(), 203753f127fSDimitry Andric typename iterator_traits<_ForwardIterator2>::iterator_category()) 204753f127fSDimitry Andric .first; 205753f127fSDimitry Andric } 206753f127fSDimitry Andric 207753f127fSDimitry Andric template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> 208*0fca6ea1SDimitry Andric _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 find_end( 209cb14a3feSDimitry Andric _ForwardIterator1 __first1, 210cb14a3feSDimitry Andric _ForwardIterator1 __last1, 211cb14a3feSDimitry Andric _ForwardIterator2 __first2, 212cb14a3feSDimitry Andric _ForwardIterator2 __last2, 213fe6060f1SDimitry Andric _BinaryPredicate __pred) { 214753f127fSDimitry Andric return std::__find_end_classic(__first1, __last1, __first2, __last2, __pred); 215fe6060f1SDimitry Andric } 216fe6060f1SDimitry Andric 217fe6060f1SDimitry Andric template <class _ForwardIterator1, class _ForwardIterator2> 218*0fca6ea1SDimitry Andric _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator1 219cb14a3feSDimitry Andric find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { 220bdd1243dSDimitry Andric return std::find_end(__first1, __last1, __first2, __last2, __equal_to()); 221fe6060f1SDimitry Andric } 222fe6060f1SDimitry Andric 223fe6060f1SDimitry Andric _LIBCPP_END_NAMESPACE_STD 224fe6060f1SDimitry Andric 225fe6060f1SDimitry Andric #endif // _LIBCPP___ALGORITHM_FIND_END_OF_H 226