1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef _LIBCPP___ALGORITHM_FIND_END_OF_H
#define _LIBCPP___ALGORITHM_FIND_END_OF_H
#include <__algorithm/comp.h>
#include <__algorithm/iterator_operations.h>
#include <__algorithm/search.h>
#include <__config>
#include <__functional/identity.h>
#include <__iterator/advance.h>
#include <__iterator/iterator_traits.h>
#include <__iterator/next.h>
#include <__iterator/reverse_iterator.h>
#include <__utility/pair.h>
#include <type_traits>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
#endif
_LIBCPP_BEGIN_NAMESPACE_STD
template <
class _AlgPolicy,
class _Iter1,
class _Sent1,
class _Iter2,
class _Sent2,
class _Pred,
class _Proj1,
class _Proj2>
_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter1> __find_end_impl(
_Iter1 __first1,
_Sent1 __last1,
_Iter2 __first2,
_Sent2 __last2,
_Pred& __pred,
_Proj1& __proj1,
_Proj2& __proj2,
forward_iterator_tag,
forward_iterator_tag) {
// modeled after search algorithm
_Iter1 __match_first = _IterOps<_AlgPolicy>::next(__first1, __last1); // __last1 is the "default" answer
_Iter1 __match_last = __match_first;
if (__first2 == __last2)
return pair<_Iter1, _Iter1>(__match_last, __match_last);
while (true) {
while (true) {
if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found)
return pair<_Iter1, _Iter1>(__match_first, __match_last);
if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2)))
break;
++__first1;
}
// *__first1 matches *__first2, now match elements after here
_Iter1 __m1 = __first1;
_Iter2 __m2 = __first2;
while (true) {
if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one
__match_first = __first1;
__match_last = ++__m1;
++__first1;
break;
}
if (++__m1 == __last1) // Source exhausted, return last answer
return pair<_Iter1, _Iter1>(__match_first, __match_last);
// mismatch, restart with a new __first
if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2)))
{
++__first1;
break;
} // else there is a match, check next elements
}
}
}
template <
class _IterOps,
class _Pred,
class _Iter1,
class _Sent1,
class _Iter2,
class _Sent2,
class _Proj1,
class _Proj2>
_LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter1 __find_end(
_Iter1 __first1,
_Sent1 __sent1,
_Iter2 __first2,
_Sent2 __sent2,
_Pred& __pred,
_Proj1& __proj1,
_Proj2& __proj2,
bidirectional_iterator_tag,
bidirectional_iterator_tag) {
auto __last1 = _IterOps::next(__first1, __sent1);
auto __last2 = _IterOps::next(__first2, __sent2);
// modeled after search algorithm (in reverse)
if (__first2 == __last2)
return __last1; // Everything matches an empty sequence
_Iter1 __l1 = __last1;
_Iter2 __l2 = __last2;
--__l2;
while (true) {
// Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks
while (true) {
if (__first1 == __l1) // return __last1 if no element matches *__first2
return __last1;
if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2)))
break;
}
// *__l1 matches *__l2, now match elements before here
_Iter1 __m1 = __l1;
_Iter2 __m2 = __l2;
while (true) {
if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern)
return __m1;
if (__m1 == __first1) // Otherwise if source exhaused, pattern not found
return __last1;
// if there is a mismatch, restart with a new __l1
if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2)))
{
break;
} // else there is a match, check next elements
}
}
}
template <
class _AlgPolicy,
class _Pred,
class _Iter1,
class _Sent1,
class _Iter2,
class _Sent2,
class _Proj1,
class _Proj2>
_LIBCPP_CONSTEXPR_AFTER_CXX11 _Iter1 __find_end(
_Iter1 __first1,
_Sent1 __sent1,
_Iter2 __first2,
_Sent2 __sent2,
_Pred& __pred,
_Proj1& __proj1,
_Proj2& __proj2,
random_access_iterator_tag,
random_access_iterator_tag) {
typedef typename iterator_traits<_Iter1>::difference_type _D1;
auto __last1 = _IterOps<_AlgPolicy>::next(__first1, __sent1);
auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __sent2);
// Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern
auto __len2 = __last2 - __first2;
if (__len2 == 0)
return __last1;
auto __len1 = __last1 - __first1;
if (__len1 < __len2)
return __last1;
const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here
_Iter1 __l1 = __last1;
_Iter2 __l2 = __last2;
--__l2;
while (true) {
while (true) {
if (__s == __l1)
return __last1;
if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2)))
break;
}
_Iter1 __m1 = __l1;
_Iter2 __m2 = __l2;
while (true) {
if (__m2 == __first2)
return __m1;
// no need to check range on __m1 because __s guarantees we have enough source
if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) {
break;
}
}
}
}
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
_ForwardIterator1 __find_end_classic(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
_BinaryPredicate& __pred) {
auto __proj = __identity();
return std::__find_end_impl<_ClassicAlgPolicy>(
__first1,
__last1,
__first2,
__last2,
__pred,
__proj,
__proj,
typename iterator_traits<_ForwardIterator1>::iterator_category(),
typename iterator_traits<_ForwardIterator2>::iterator_category())
.first;
}
template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
_BinaryPredicate __pred) {
return std::__find_end_classic(__first1, __last1, __first2, __last2, __pred);
}
template <class _ForwardIterator1, class _ForwardIterator2>
_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2) {
using __v1 = typename iterator_traits<_ForwardIterator1>::value_type;
using __v2 = typename iterator_traits<_ForwardIterator2>::value_type;
return std::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());
}
_LIBCPP_END_NAMESPACE_STD
#endif // _LIBCPP___ALGORITHM_FIND_END_OF_H
|
