]>
Commit | Line | Data |
---|---|---|
bc464641 PP |
1 | // Core algorithmic facilities -*- C++ -*- |
2 | ||
99dee823 | 3 | // Copyright (C) 2020-2021 Free Software Foundation, Inc. |
bc464641 PP |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 3, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // Under Section 7 of GPL version 3, you are granted additional | |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
24 | ||
25 | /** @file bits/ranges_algo.h | |
26 | * This is an internal header file, included by other library headers. | |
27 | * Do not attempt to use it directly. @headername{algorithm} | |
28 | */ | |
29 | ||
30 | #ifndef _RANGES_ALGO_H | |
31 | #define _RANGES_ALGO_H 1 | |
32 | ||
33 | #if __cplusplus > 201703L | |
34 | ||
90fc7b3c | 35 | #include <bits/ranges_algobase.h> |
160061ac | 36 | #include <bits/ranges_util.h> |
9cd4eeef | 37 | #include <bits/uniform_int_dist.h> // concept uniform_random_bit_generator |
bc464641 PP |
38 | |
39 | #if __cpp_lib_concepts | |
40 | namespace std _GLIBCXX_VISIBILITY(default) | |
41 | { | |
42 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
43 | namespace ranges | |
44 | { | |
45 | namespace __detail | |
46 | { | |
bc464641 PP |
47 | template<typename _Comp, typename _Proj> |
48 | constexpr auto | |
49 | __make_comp_proj(_Comp& __comp, _Proj& __proj) | |
50 | { | |
51 | return [&] (auto&& __lhs, auto&& __rhs) -> bool { | |
52 | using _TL = decltype(__lhs); | |
53 | using _TR = decltype(__rhs); | |
54 | return std::__invoke(__comp, | |
55 | std::__invoke(__proj, std::forward<_TL>(__lhs)), | |
56 | std::__invoke(__proj, std::forward<_TR>(__rhs))); | |
57 | }; | |
58 | } | |
59 | ||
60 | template<typename _Pred, typename _Proj> | |
61 | constexpr auto | |
62 | __make_pred_proj(_Pred& __pred, _Proj& __proj) | |
63 | { | |
64 | return [&] <typename _Tp> (_Tp&& __arg) -> bool { | |
65 | return std::__invoke(__pred, | |
66 | std::__invoke(__proj, std::forward<_Tp>(__arg))); | |
67 | }; | |
68 | } | |
69 | } // namespace __detail | |
70 | ||
b40c57bd PP |
71 | struct __all_of_fn |
72 | { | |
73 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
74 | typename _Proj = identity, | |
75 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
76 | constexpr bool | |
55992626 PP |
77 | operator()(_Iter __first, _Sent __last, |
78 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
79 | { |
80 | for (; __first != __last; ++__first) | |
81 | if (!(bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
82 | return false; | |
83 | return true; | |
84 | } | |
bc464641 | 85 | |
b40c57bd | 86 | template<input_range _Range, typename _Proj = identity, |
55992626 PP |
87 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
88 | _Pred> | |
b40c57bd PP |
89 | constexpr bool |
90 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
91 | { | |
92 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
93 | std::move(__pred), std::move(__proj)); | |
94 | } | |
95 | }; | |
bc464641 | 96 | |
b40c57bd | 97 | inline constexpr __all_of_fn all_of{}; |
bc464641 | 98 | |
b40c57bd PP |
99 | struct __any_of_fn |
100 | { | |
101 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
102 | typename _Proj = identity, | |
103 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
104 | constexpr bool | |
55992626 PP |
105 | operator()(_Iter __first, _Sent __last, |
106 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
107 | { |
108 | for (; __first != __last; ++__first) | |
109 | if (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
110 | return true; | |
111 | return false; | |
112 | } | |
113 | ||
114 | template<input_range _Range, typename _Proj = identity, | |
55992626 PP |
115 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
116 | _Pred> | |
b40c57bd PP |
117 | constexpr bool |
118 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
119 | { | |
120 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 121 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
122 | } |
123 | }; | |
124 | ||
125 | inline constexpr __any_of_fn any_of{}; | |
126 | ||
127 | struct __none_of_fn | |
128 | { | |
129 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
130 | typename _Proj = identity, | |
131 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
132 | constexpr bool | |
55992626 PP |
133 | operator()(_Iter __first, _Sent __last, |
134 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
135 | { |
136 | for (; __first != __last; ++__first) | |
137 | if (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
138 | return false; | |
139 | return true; | |
140 | } | |
141 | ||
142 | template<input_range _Range, typename _Proj = identity, | |
55992626 PP |
143 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
144 | _Pred> | |
b40c57bd PP |
145 | constexpr bool |
146 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
147 | { | |
148 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
149 | std::move(__pred), std::move(__proj)); | |
150 | } | |
151 | }; | |
152 | ||
153 | inline constexpr __none_of_fn none_of{}; | |
bc464641 PP |
154 | |
155 | template<typename _Iter, typename _Fp> | |
aa667c3f | 156 | struct in_fun_result |
bc464641 PP |
157 | { |
158 | [[no_unique_address]] _Iter in; | |
159 | [[no_unique_address]] _Fp fun; | |
160 | ||
161 | template<typename _Iter2, typename _F2p> | |
162 | requires convertible_to<const _Iter&, _Iter2> | |
163 | && convertible_to<const _Fp&, _F2p> | |
aa667c3f PP |
164 | constexpr |
165 | operator in_fun_result<_Iter2, _F2p>() const & | |
bc464641 PP |
166 | { return {in, fun}; } |
167 | ||
168 | template<typename _Iter2, typename _F2p> | |
169 | requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p> | |
aa667c3f PP |
170 | constexpr |
171 | operator in_fun_result<_Iter2, _F2p>() && | |
bc464641 PP |
172 | { return {std::move(in), std::move(fun)}; } |
173 | }; | |
174 | ||
aa667c3f PP |
175 | template<typename _Iter, typename _Fp> |
176 | using for_each_result = in_fun_result<_Iter, _Fp>; | |
177 | ||
b40c57bd PP |
178 | struct __for_each_fn |
179 | { | |
180 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
181 | typename _Proj = identity, | |
182 | indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun> | |
183 | constexpr for_each_result<_Iter, _Fun> | |
184 | operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const | |
185 | { | |
186 | for (; __first != __last; ++__first) | |
187 | std::__invoke(__f, std::__invoke(__proj, *__first)); | |
188 | return { std::move(__first), std::move(__f) }; | |
189 | } | |
190 | ||
191 | template<input_range _Range, typename _Proj = identity, | |
192 | indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>> | |
193 | _Fun> | |
15411a64 | 194 | constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun> |
b40c57bd PP |
195 | operator()(_Range&& __r, _Fun __f, _Proj __proj = {}) const |
196 | { | |
197 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 198 | std::move(__f), std::move(__proj)); |
b40c57bd PP |
199 | } |
200 | }; | |
201 | ||
202 | inline constexpr __for_each_fn for_each{}; | |
203 | ||
f3169941 | 204 | template<typename _Iter, typename _Fp> |
aa667c3f | 205 | using for_each_n_result = in_fun_result<_Iter, _Fp>; |
f3169941 PP |
206 | |
207 | struct __for_each_n_fn | |
208 | { | |
209 | template<input_iterator _Iter, typename _Proj = identity, | |
210 | indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun> | |
211 | constexpr for_each_n_result<_Iter, _Fun> | |
212 | operator()(_Iter __first, iter_difference_t<_Iter> __n, | |
213 | _Fun __f, _Proj __proj = {}) const | |
214 | { | |
215 | if constexpr (random_access_iterator<_Iter>) | |
216 | { | |
217 | if (__n <= 0) | |
218 | return {std::move(__first), std::move(__f)}; | |
219 | auto __last = __first + __n; | |
220 | return ranges::for_each(std::move(__first), std::move(__last), | |
221 | std::move(__f), std::move(__proj)); | |
222 | } | |
223 | else | |
224 | { | |
225 | while (__n-- > 0) | |
226 | { | |
227 | std::__invoke(__f, std::__invoke(__proj, *__first)); | |
228 | ++__first; | |
229 | } | |
230 | return {std::move(__first), std::move(__f)}; | |
231 | } | |
232 | } | |
233 | }; | |
234 | ||
235 | inline constexpr __for_each_n_fn for_each_n{}; | |
236 | ||
b40c57bd PP |
237 | struct __find_fn |
238 | { | |
239 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp, | |
240 | typename _Proj = identity> | |
241 | requires indirect_binary_predicate<ranges::equal_to, | |
242 | projected<_Iter, _Proj>, const _Tp*> | |
243 | constexpr _Iter | |
55992626 PP |
244 | operator()(_Iter __first, _Sent __last, |
245 | const _Tp& __value, _Proj __proj = {}) const | |
b40c57bd PP |
246 | { |
247 | while (__first != __last | |
a45fb21a | 248 | && !(std::__invoke(__proj, *__first) == __value)) |
b40c57bd PP |
249 | ++__first; |
250 | return __first; | |
251 | } | |
252 | ||
253 | template<input_range _Range, typename _Tp, typename _Proj = identity> | |
254 | requires indirect_binary_predicate<ranges::equal_to, | |
255 | projected<iterator_t<_Range>, _Proj>, | |
256 | const _Tp*> | |
15411a64 | 257 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
258 | operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const |
259 | { | |
55992626 PP |
260 | return (*this)(ranges::begin(__r), ranges::end(__r), |
261 | __value, std::move(__proj)); | |
b40c57bd PP |
262 | } |
263 | }; | |
264 | ||
265 | inline constexpr __find_fn find{}; | |
266 | ||
267 | struct __find_if_fn | |
268 | { | |
269 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
270 | typename _Proj = identity, | |
271 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
272 | constexpr _Iter | |
55992626 PP |
273 | operator()(_Iter __first, _Sent __last, |
274 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
275 | { |
276 | while (__first != __last | |
277 | && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
278 | ++__first; | |
279 | return __first; | |
280 | } | |
281 | ||
282 | template<input_range _Range, typename _Proj = identity, | |
283 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
284 | _Pred> | |
15411a64 | 285 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
286 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const |
287 | { | |
288 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 289 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
290 | } |
291 | }; | |
292 | ||
293 | inline constexpr __find_if_fn find_if{}; | |
294 | ||
295 | struct __find_if_not_fn | |
296 | { | |
297 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
298 | typename _Proj = identity, | |
299 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
300 | constexpr _Iter | |
55992626 PP |
301 | operator()(_Iter __first, _Sent __last, |
302 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
303 | { |
304 | while (__first != __last | |
305 | && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
306 | ++__first; | |
307 | return __first; | |
308 | } | |
309 | ||
310 | template<input_range _Range, typename _Proj = identity, | |
311 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
312 | _Pred> | |
15411a64 | 313 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
314 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const |
315 | { | |
316 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 317 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
318 | } |
319 | }; | |
320 | ||
321 | inline constexpr __find_if_not_fn find_if_not{}; | |
322 | ||
323 | struct __find_first_of_fn | |
324 | { | |
325 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
326 | forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
327 | typename _Pred = ranges::equal_to, | |
328 | typename _Proj1 = identity, typename _Proj2 = identity> | |
329 | requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> | |
330 | constexpr _Iter1 | |
331 | operator()(_Iter1 __first1, _Sent1 __last1, | |
55992626 PP |
332 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, |
333 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
334 | { |
335 | for (; __first1 != __last1; ++__first1) | |
336 | for (auto __iter = __first2; __iter != __last2; ++__iter) | |
a45fb21a JW |
337 | if (std::__invoke(__pred, |
338 | std::__invoke(__proj1, *__first1), | |
339 | std::__invoke(__proj2, *__iter))) | |
b40c57bd PP |
340 | return __first1; |
341 | return __first1; | |
342 | } | |
343 | ||
344 | template<input_range _Range1, forward_range _Range2, | |
345 | typename _Pred = ranges::equal_to, | |
346 | typename _Proj1 = identity, typename _Proj2 = identity> | |
347 | requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
348 | _Pred, _Proj1, _Proj2> | |
15411a64 | 349 | constexpr borrowed_iterator_t<_Range1> |
55992626 PP |
350 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, |
351 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
352 | { |
353 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
354 | ranges::begin(__r2), ranges::end(__r2), |
355 | std::move(__pred), | |
356 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
357 | } |
358 | }; | |
359 | ||
360 | inline constexpr __find_first_of_fn find_first_of{}; | |
361 | ||
362 | struct __count_fn | |
363 | { | |
364 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
365 | typename _Tp, typename _Proj = identity> | |
366 | requires indirect_binary_predicate<ranges::equal_to, | |
367 | projected<_Iter, _Proj>, | |
368 | const _Tp*> | |
369 | constexpr iter_difference_t<_Iter> | |
55992626 PP |
370 | operator()(_Iter __first, _Sent __last, |
371 | const _Tp& __value, _Proj __proj = {}) const | |
b40c57bd PP |
372 | { |
373 | iter_difference_t<_Iter> __n = 0; | |
374 | for (; __first != __last; ++__first) | |
375 | if (std::__invoke(__proj, *__first) == __value) | |
376 | ++__n; | |
377 | return __n; | |
378 | } | |
379 | ||
380 | template<input_range _Range, typename _Tp, typename _Proj = identity> | |
381 | requires indirect_binary_predicate<ranges::equal_to, | |
382 | projected<iterator_t<_Range>, _Proj>, | |
383 | const _Tp*> | |
384 | constexpr range_difference_t<_Range> | |
385 | operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const | |
386 | { | |
387 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 388 | __value, std::move(__proj)); |
b40c57bd PP |
389 | } |
390 | }; | |
391 | ||
392 | inline constexpr __count_fn count{}; | |
393 | ||
394 | struct __count_if_fn | |
395 | { | |
396 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
397 | typename _Proj = identity, | |
398 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
399 | constexpr iter_difference_t<_Iter> | |
55992626 PP |
400 | operator()(_Iter __first, _Sent __last, |
401 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
402 | { |
403 | iter_difference_t<_Iter> __n = 0; | |
404 | for (; __first != __last; ++__first) | |
405 | if (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
406 | ++__n; | |
407 | return __n; | |
408 | } | |
409 | ||
410 | template<input_range _Range, | |
411 | typename _Proj = identity, | |
55992626 PP |
412 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
413 | _Pred> | |
b40c57bd PP |
414 | constexpr range_difference_t<_Range> |
415 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
416 | { | |
417 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 418 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
419 | } |
420 | }; | |
421 | ||
422 | inline constexpr __count_if_fn count_if{}; | |
bc464641 PP |
423 | |
424 | template<typename _Iter1, typename _Iter2> | |
aa667c3f | 425 | struct in_in_result |
bc464641 PP |
426 | { |
427 | [[no_unique_address]] _Iter1 in1; | |
428 | [[no_unique_address]] _Iter2 in2; | |
429 | ||
430 | template<typename _IIter1, typename _IIter2> | |
431 | requires convertible_to<const _Iter1&, _IIter1> | |
432 | && convertible_to<const _Iter2&, _IIter2> | |
aa667c3f PP |
433 | constexpr |
434 | operator in_in_result<_IIter1, _IIter2>() const & | |
bc464641 PP |
435 | { return {in1, in2}; } |
436 | ||
437 | template<typename _IIter1, typename _IIter2> | |
438 | requires convertible_to<_Iter1, _IIter1> | |
439 | && convertible_to<_Iter2, _IIter2> | |
aa667c3f PP |
440 | constexpr |
441 | operator in_in_result<_IIter1, _IIter2>() && | |
bc464641 PP |
442 | { return {std::move(in1), std::move(in2)}; } |
443 | }; | |
444 | ||
aa667c3f PP |
445 | template<typename _Iter1, typename _Iter2> |
446 | using mismatch_result = in_in_result<_Iter1, _Iter2>; | |
447 | ||
b40c57bd PP |
448 | struct __mismatch_fn |
449 | { | |
450 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
451 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
452 | typename _Pred = ranges::equal_to, | |
453 | typename _Proj1 = identity, typename _Proj2 = identity> | |
454 | requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> | |
455 | constexpr mismatch_result<_Iter1, _Iter2> | |
55992626 PP |
456 | operator()(_Iter1 __first1, _Sent1 __last1, |
457 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, | |
458 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
459 | { |
460 | while (__first1 != __last1 && __first2 != __last2 | |
461 | && (bool)std::__invoke(__pred, | |
462 | std::__invoke(__proj1, *__first1), | |
463 | std::__invoke(__proj2, *__first2))) | |
bc464641 | 464 | { |
b40c57bd PP |
465 | ++__first1; |
466 | ++__first2; | |
bc464641 | 467 | } |
b40c57bd PP |
468 | return { std::move(__first1), std::move(__first2) }; |
469 | } | |
bc464641 | 470 | |
b40c57bd PP |
471 | template<input_range _Range1, input_range _Range2, |
472 | typename _Pred = ranges::equal_to, | |
473 | typename _Proj1 = identity, typename _Proj2 = identity> | |
474 | requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
475 | _Pred, _Proj1, _Proj2> | |
476 | constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>> | |
55992626 PP |
477 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, |
478 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
479 | { |
480 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
481 | ranges::begin(__r2), ranges::end(__r2), |
482 | std::move(__pred), | |
483 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
484 | } |
485 | }; | |
bc464641 | 486 | |
b40c57bd | 487 | inline constexpr __mismatch_fn mismatch{}; |
bc464641 | 488 | |
b40c57bd PP |
489 | struct __search_fn |
490 | { | |
491 | template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
492 | forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
493 | typename _Pred = ranges::equal_to, | |
494 | typename _Proj1 = identity, typename _Proj2 = identity> | |
495 | requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> | |
496 | constexpr subrange<_Iter1> | |
55992626 PP |
497 | operator()(_Iter1 __first1, _Sent1 __last1, |
498 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, | |
499 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
500 | { |
501 | if (__first1 == __last1 || __first2 == __last2) | |
502 | return {__first1, __first1}; | |
bc464641 | 503 | |
b40c57bd PP |
504 | for (;;) |
505 | { | |
506 | for (;;) | |
507 | { | |
508 | if (__first1 == __last1) | |
509 | return {__first1, __first1}; | |
510 | if (std::__invoke(__pred, | |
511 | std::__invoke(__proj1, *__first1), | |
512 | std::__invoke(__proj2, *__first2))) | |
513 | break; | |
514 | ++__first1; | |
515 | } | |
516 | auto __cur1 = __first1; | |
517 | auto __cur2 = __first2; | |
518 | for (;;) | |
519 | { | |
520 | if (++__cur2 == __last2) | |
521 | return {__first1, ++__cur1}; | |
522 | if (++__cur1 == __last1) | |
523 | return {__cur1, __cur1}; | |
524 | if (!(bool)std::__invoke(__pred, | |
525 | std::__invoke(__proj1, *__cur1), | |
526 | std::__invoke(__proj2, *__cur2))) | |
527 | { | |
528 | ++__first1; | |
529 | break; | |
530 | } | |
531 | } | |
532 | } | |
533 | } | |
90b7eb65 | 534 | |
b40c57bd PP |
535 | template<forward_range _Range1, forward_range _Range2, |
536 | typename _Pred = ranges::equal_to, | |
537 | typename _Proj1 = identity, typename _Proj2 = identity> | |
538 | requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
539 | _Pred, _Proj1, _Proj2> | |
15411a64 | 540 | constexpr borrowed_subrange_t<_Range1> |
55992626 PP |
541 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, |
542 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
543 | { |
544 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
545 | ranges::begin(__r2), ranges::end(__r2), |
546 | std::move(__pred), | |
547 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
548 | } |
549 | }; | |
bc464641 | 550 | |
b40c57bd | 551 | inline constexpr __search_fn search{}; |
bc464641 | 552 | |
b40c57bd PP |
553 | struct __search_n_fn |
554 | { | |
555 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp, | |
556 | typename _Pred = ranges::equal_to, typename _Proj = identity> | |
557 | requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj> | |
558 | constexpr subrange<_Iter> | |
559 | operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count, | |
55992626 | 560 | const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const |
b40c57bd PP |
561 | { |
562 | if (__count <= 0) | |
563 | return {__first, __first}; | |
bc464641 | 564 | |
b40c57bd PP |
565 | auto __value_comp = [&] <typename _Rp> (_Rp&& __arg) { |
566 | return std::__invoke(__pred, std::forward<_Rp>(__arg), __value); | |
567 | }; | |
568 | if (__count == 1) | |
569 | { | |
570 | __first = ranges::find_if(std::move(__first), __last, | |
55992626 PP |
571 | std::move(__value_comp), |
572 | std::move(__proj)); | |
b40c57bd PP |
573 | if (__first == __last) |
574 | return {__first, __first}; | |
575 | else | |
576 | { | |
577 | auto __end = __first; | |
578 | return {__first, ++__end}; | |
579 | } | |
580 | } | |
bc464641 | 581 | |
8661f4fa PP |
582 | if constexpr (sized_sentinel_for<_Sent, _Iter> |
583 | && random_access_iterator<_Iter>) | |
b40c57bd PP |
584 | { |
585 | auto __tail_size = __last - __first; | |
586 | auto __remainder = __count; | |
bc464641 | 587 | |
b40c57bd PP |
588 | while (__remainder <= __tail_size) |
589 | { | |
590 | __first += __remainder; | |
591 | __tail_size -= __remainder; | |
592 | auto __backtrack = __first; | |
593 | while (__value_comp(std::__invoke(__proj, *--__backtrack))) | |
594 | { | |
595 | if (--__remainder == 0) | |
596 | return {__first - __count, __first}; | |
597 | } | |
8661f4fa | 598 | __remainder = __count + 1 - (__first - __backtrack); |
b40c57bd PP |
599 | } |
600 | auto __i = __first + __tail_size; | |
601 | return {__i, __i}; | |
602 | } | |
603 | else | |
bc464641 | 604 | { |
b40c57bd PP |
605 | __first = ranges::find_if(__first, __last, __value_comp, __proj); |
606 | while (__first != __last) | |
607 | { | |
608 | auto __n = __count; | |
609 | auto __i = __first; | |
610 | ++__i; | |
611 | while (__i != __last && __n != 1 | |
612 | && __value_comp(std::__invoke(__proj, *__i))) | |
613 | { | |
614 | ++__i; | |
615 | --__n; | |
616 | } | |
617 | if (__n == 1) | |
618 | return {__first, __i}; | |
619 | if (__i == __last) | |
620 | return {__i, __i}; | |
621 | __first = ranges::find_if(++__i, __last, __value_comp, __proj); | |
622 | } | |
623 | return {__first, __first}; | |
bc464641 | 624 | } |
b40c57bd | 625 | } |
bc464641 | 626 | |
b40c57bd PP |
627 | template<forward_range _Range, typename _Tp, |
628 | typename _Pred = ranges::equal_to, typename _Proj = identity> | |
55992626 PP |
629 | requires indirectly_comparable<iterator_t<_Range>, const _Tp*, |
630 | _Pred, _Proj> | |
15411a64 | 631 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
632 | operator()(_Range&& __r, range_difference_t<_Range> __count, |
633 | const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const | |
634 | { | |
635 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
636 | std::move(__count), __value, |
637 | std::move(__pred), std::move(__proj)); | |
b40c57bd PP |
638 | } |
639 | }; | |
bc464641 | 640 | |
b40c57bd | 641 | inline constexpr __search_n_fn search_n{}; |
bc464641 | 642 | |
b40c57bd PP |
643 | struct __find_end_fn |
644 | { | |
645 | template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
646 | forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
647 | typename _Pred = ranges::equal_to, | |
648 | typename _Proj1 = identity, typename _Proj2 = identity> | |
649 | requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> | |
650 | constexpr subrange<_Iter1> | |
651 | operator()(_Iter1 __first1, _Sent1 __last1, | |
55992626 PP |
652 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, |
653 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
654 | { |
655 | if constexpr (bidirectional_iterator<_Iter1> | |
656 | && bidirectional_iterator<_Iter2>) | |
657 | { | |
658 | auto __i1 = ranges::next(__first1, __last1); | |
659 | auto __i2 = ranges::next(__first2, __last2); | |
660 | auto __rresult | |
661 | = ranges::search(reverse_iterator<_Iter1>{__i1}, | |
662 | reverse_iterator<_Iter1>{__first1}, | |
663 | reverse_iterator<_Iter2>{__i2}, | |
664 | reverse_iterator<_Iter2>{__first2}, | |
665 | std::move(__pred), | |
666 | std::move(__proj1), std::move(__proj2)); | |
667 | auto __result_first = ranges::end(__rresult).base(); | |
668 | auto __result_last = ranges::begin(__rresult).base(); | |
669 | if (__result_last == __first1) | |
670 | return {__i1, __i1}; | |
671 | else | |
672 | return {__result_first, __result_last}; | |
673 | } | |
674 | else | |
675 | { | |
676 | auto __i = ranges::next(__first1, __last1); | |
677 | if (__first2 == __last2) | |
678 | return {__i, __i}; | |
679 | ||
680 | auto __result_begin = __i; | |
681 | auto __result_end = __i; | |
682 | for (;;) | |
683 | { | |
684 | auto __new_range = ranges::search(__first1, __last1, | |
685 | __first2, __last2, | |
686 | __pred, __proj1, __proj2); | |
687 | auto __new_result_begin = ranges::begin(__new_range); | |
688 | auto __new_result_end = ranges::end(__new_range); | |
689 | if (__new_result_begin == __last1) | |
690 | return {__result_begin, __result_end}; | |
691 | else | |
692 | { | |
693 | __result_begin = __new_result_begin; | |
694 | __result_end = __new_result_end; | |
695 | __first1 = __result_begin; | |
696 | ++__first1; | |
697 | } | |
698 | } | |
699 | } | |
700 | } | |
701 | ||
702 | template<forward_range _Range1, forward_range _Range2, | |
703 | typename _Pred = ranges::equal_to, | |
704 | typename _Proj1 = identity, typename _Proj2 = identity> | |
705 | requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
706 | _Pred, _Proj1, _Proj2> | |
15411a64 | 707 | constexpr borrowed_subrange_t<_Range1> |
55992626 PP |
708 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, |
709 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
710 | { |
711 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
712 | ranges::begin(__r2), ranges::end(__r2), |
713 | std::move(__pred), | |
714 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
715 | } |
716 | }; | |
717 | ||
718 | inline constexpr __find_end_fn find_end{}; | |
719 | ||
720 | struct __adjacent_find_fn | |
721 | { | |
722 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
723 | typename _Proj = identity, | |
724 | indirect_binary_predicate<projected<_Iter, _Proj>, | |
725 | projected<_Iter, _Proj>> _Pred | |
726 | = ranges::equal_to> | |
727 | constexpr _Iter | |
728 | operator()(_Iter __first, _Sent __last, | |
55992626 | 729 | _Pred __pred = {}, _Proj __proj = {}) const |
b40c57bd PP |
730 | { |
731 | if (__first == __last) | |
732 | return __first; | |
733 | auto __next = __first; | |
734 | for (; ++__next != __last; __first = __next) | |
735 | { | |
a45fb21a JW |
736 | if (std::__invoke(__pred, |
737 | std::__invoke(__proj, *__first), | |
738 | std::__invoke(__proj, *__next))) | |
b40c57bd PP |
739 | return __first; |
740 | } | |
741 | return __next; | |
742 | } | |
743 | ||
744 | template<forward_range _Range, typename _Proj = identity, | |
745 | indirect_binary_predicate< | |
746 | projected<iterator_t<_Range>, _Proj>, | |
747 | projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to> | |
15411a64 | 748 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
749 | operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const |
750 | { | |
751 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 752 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
753 | } |
754 | }; | |
755 | ||
756 | inline constexpr __adjacent_find_fn adjacent_find{}; | |
757 | ||
758 | struct __is_permutation_fn | |
759 | { | |
760 | template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
761 | forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
762 | typename _Proj1 = identity, typename _Proj2 = identity, | |
763 | indirect_equivalence_relation<projected<_Iter1, _Proj1>, | |
764 | projected<_Iter2, _Proj2>> _Pred | |
765 | = ranges::equal_to> | |
766 | constexpr bool | |
767 | operator()(_Iter1 __first1, _Sent1 __last1, | |
55992626 PP |
768 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, |
769 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
770 | { |
771 | constexpr bool __sized_iters | |
772 | = (sized_sentinel_for<_Sent1, _Iter1> | |
773 | && sized_sentinel_for<_Sent2, _Iter2>); | |
774 | if constexpr (__sized_iters) | |
775 | { | |
776 | auto __d1 = ranges::distance(__first1, __last1); | |
777 | auto __d2 = ranges::distance(__first2, __last2); | |
778 | if (__d1 != __d2) | |
779 | return false; | |
780 | } | |
781 | ||
782 | // Efficiently compare identical prefixes: O(N) if sequences | |
783 | // have the same elements in the same order. | |
784 | for (; __first1 != __last1 && __first2 != __last2; | |
785 | ++__first1, (void)++__first2) | |
786 | if (!(bool)std::__invoke(__pred, | |
787 | std::__invoke(__proj1, *__first1), | |
788 | std::__invoke(__proj2, *__first2))) | |
789 | break; | |
790 | ||
791 | if constexpr (__sized_iters) | |
792 | { | |
793 | if (__first1 == __last1) | |
794 | return true; | |
795 | } | |
796 | else | |
797 | { | |
798 | auto __d1 = ranges::distance(__first1, __last1); | |
799 | auto __d2 = ranges::distance(__first2, __last2); | |
800 | if (__d1 == 0 && __d2 == 0) | |
801 | return true; | |
802 | if (__d1 != __d2) | |
803 | return false; | |
804 | } | |
805 | ||
806 | for (auto __scan = __first1; __scan != __last1; ++__scan) | |
807 | { | |
808 | auto __proj_scan = std::__invoke(__proj1, *__scan); | |
809 | auto __comp_scan = [&] <typename _Tp> (_Tp&& __arg) { | |
810 | return std::__invoke(__pred, __proj_scan, | |
811 | std::forward<_Tp>(__arg)); | |
812 | }; | |
813 | if (__scan != ranges::find_if(__first1, __scan, | |
814 | __comp_scan, __proj1)) | |
815 | continue; // We've seen this one before. | |
816 | ||
817 | auto __matches = ranges::count_if(__first2, __last2, | |
818 | __comp_scan, __proj2); | |
819 | if (__matches == 0 | |
820 | || ranges::count_if(__scan, __last1, | |
821 | __comp_scan, __proj1) != __matches) | |
822 | return false; | |
823 | } | |
824 | return true; | |
825 | } | |
826 | ||
827 | template<forward_range _Range1, forward_range _Range2, | |
828 | typename _Proj1 = identity, typename _Proj2 = identity, | |
829 | indirect_equivalence_relation< | |
830 | projected<iterator_t<_Range1>, _Proj1>, | |
831 | projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to> | |
832 | constexpr bool | |
833 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, | |
55992626 | 834 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const |
b40c57bd PP |
835 | { |
836 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
837 | ranges::begin(__r2), ranges::end(__r2), |
838 | std::move(__pred), | |
839 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
840 | } |
841 | }; | |
842 | ||
843 | inline constexpr __is_permutation_fn is_permutation{}; | |
844 | ||
845 | template<typename _Iter, typename _Out> | |
aa667c3f | 846 | using copy_if_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
847 | |
848 | struct __copy_if_fn | |
849 | { | |
850 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
851 | weakly_incrementable _Out, typename _Proj = identity, | |
852 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
853 | requires indirectly_copyable<_Iter, _Out> | |
854 | constexpr copy_if_result<_Iter, _Out> | |
855 | operator()(_Iter __first, _Sent __last, _Out __result, | |
55992626 | 856 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
857 | { |
858 | for (; __first != __last; ++__first) | |
859 | if (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
860 | { | |
861 | *__result = *__first; | |
862 | ++__result; | |
863 | } | |
864 | return {std::move(__first), std::move(__result)}; | |
865 | } | |
866 | ||
867 | template<input_range _Range, weakly_incrementable _Out, | |
868 | typename _Proj = identity, | |
55992626 PP |
869 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
870 | _Pred> | |
b40c57bd | 871 | requires indirectly_copyable<iterator_t<_Range>, _Out> |
15411a64 | 872 | constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out> |
55992626 PP |
873 | operator()(_Range&& __r, _Out __result, |
874 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
875 | { |
876 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
877 | std::move(__result), |
878 | std::move(__pred), std::move(__proj)); | |
b40c57bd PP |
879 | } |
880 | }; | |
881 | ||
882 | inline constexpr __copy_if_fn copy_if{}; | |
883 | ||
884 | template<typename _Iter1, typename _Iter2> | |
aa667c3f | 885 | using swap_ranges_result = in_in_result<_Iter1, _Iter2>; |
b40c57bd PP |
886 | |
887 | struct __swap_ranges_fn | |
888 | { | |
889 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
890 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2> | |
891 | requires indirectly_swappable<_Iter1, _Iter2> | |
892 | constexpr swap_ranges_result<_Iter1, _Iter2> | |
893 | operator()(_Iter1 __first1, _Sent1 __last1, | |
55992626 | 894 | _Iter2 __first2, _Sent2 __last2) const |
b40c57bd PP |
895 | { |
896 | for (; __first1 != __last1 && __first2 != __last2; | |
897 | ++__first1, (void)++__first2) | |
898 | ranges::iter_swap(__first1, __first2); | |
899 | return {std::move(__first1), std::move(__first2)}; | |
900 | } | |
901 | ||
902 | template<input_range _Range1, input_range _Range2> | |
903 | requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>> | |
15411a64 JW |
904 | constexpr swap_ranges_result<borrowed_iterator_t<_Range1>, |
905 | borrowed_iterator_t<_Range2>> | |
b40c57bd PP |
906 | operator()(_Range1&& __r1, _Range2&& __r2) const |
907 | { | |
908 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 | 909 | ranges::begin(__r2), ranges::end(__r2)); |
b40c57bd PP |
910 | } |
911 | }; | |
912 | ||
913 | inline constexpr __swap_ranges_fn swap_ranges{}; | |
914 | ||
915 | template<typename _Iter, typename _Out> | |
aa667c3f | 916 | using unary_transform_result = in_out_result<_Iter, _Out>; |
bc464641 PP |
917 | |
918 | template<typename _Iter1, typename _Iter2, typename _Out> | |
aa667c3f | 919 | struct in_in_out_result |
bc464641 PP |
920 | { |
921 | [[no_unique_address]] _Iter1 in1; | |
922 | [[no_unique_address]] _Iter2 in2; | |
923 | [[no_unique_address]] _Out out; | |
924 | ||
925 | template<typename _IIter1, typename _IIter2, typename _OOut> | |
a04f635d | 926 | requires convertible_to<const _Iter1&, _IIter1> |
bc464641 PP |
927 | && convertible_to<const _Iter2&, _IIter2> |
928 | && convertible_to<const _Out&, _OOut> | |
aa667c3f PP |
929 | constexpr |
930 | operator in_in_out_result<_IIter1, _IIter2, _OOut>() const & | |
bc464641 PP |
931 | { return {in1, in2, out}; } |
932 | ||
933 | template<typename _IIter1, typename _IIter2, typename _OOut> | |
934 | requires convertible_to<_Iter1, _IIter1> | |
935 | && convertible_to<_Iter2, _IIter2> | |
936 | && convertible_to<_Out, _OOut> | |
aa667c3f PP |
937 | constexpr |
938 | operator in_in_out_result<_IIter1, _IIter2, _OOut>() && | |
bc464641 PP |
939 | { return {std::move(in1), std::move(in2), std::move(out)}; } |
940 | }; | |
941 | ||
aa667c3f PP |
942 | template<typename _Iter1, typename _Iter2, typename _Out> |
943 | using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>; | |
944 | ||
b40c57bd PP |
945 | struct __transform_fn |
946 | { | |
947 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
948 | weakly_incrementable _Out, | |
949 | copy_constructible _Fp, typename _Proj = identity> | |
950 | requires indirectly_writable<_Out, | |
951 | indirect_result_t<_Fp&, | |
952 | projected<_Iter, _Proj>>> | |
953 | constexpr unary_transform_result<_Iter, _Out> | |
954 | operator()(_Iter __first1, _Sent __last1, _Out __result, | |
55992626 | 955 | _Fp __op, _Proj __proj = {}) const |
b40c57bd PP |
956 | { |
957 | for (; __first1 != __last1; ++__first1, (void)++__result) | |
958 | *__result = std::__invoke(__op, std::__invoke(__proj, *__first1)); | |
959 | return {std::move(__first1), std::move(__result)}; | |
960 | } | |
bc464641 | 961 | |
b40c57bd PP |
962 | template<input_range _Range, weakly_incrementable _Out, |
963 | copy_constructible _Fp, typename _Proj = identity> | |
964 | requires indirectly_writable<_Out, | |
965 | indirect_result_t<_Fp&, | |
966 | projected<iterator_t<_Range>, _Proj>>> | |
15411a64 | 967 | constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd PP |
968 | operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {}) const |
969 | { | |
970 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
971 | std::move(__result), |
972 | std::move(__op), std::move(__proj)); | |
b40c57bd | 973 | } |
bc464641 | 974 | |
b40c57bd PP |
975 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, |
976 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
977 | weakly_incrementable _Out, copy_constructible _Fp, | |
978 | typename _Proj1 = identity, typename _Proj2 = identity> | |
979 | requires indirectly_writable<_Out, | |
980 | indirect_result_t<_Fp&, | |
981 | projected<_Iter1, _Proj1>, | |
982 | projected<_Iter2, _Proj2>>> | |
983 | constexpr binary_transform_result<_Iter1, _Iter2, _Out> | |
55992626 PP |
984 | operator()(_Iter1 __first1, _Sent1 __last1, |
985 | _Iter2 __first2, _Sent2 __last2, | |
986 | _Out __result, _Fp __binary_op, | |
987 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
988 | { |
989 | for (; __first1 != __last1 && __first2 != __last2; | |
990 | ++__first1, (void)++__first2, ++__result) | |
991 | *__result = std::__invoke(__binary_op, | |
992 | std::__invoke(__proj1, *__first1), | |
993 | std::__invoke(__proj2, *__first2)); | |
994 | return {std::move(__first1), std::move(__first2), std::move(__result)}; | |
995 | } | |
bc464641 | 996 | |
b40c57bd PP |
997 | template<input_range _Range1, input_range _Range2, |
998 | weakly_incrementable _Out, copy_constructible _Fp, | |
999 | typename _Proj1 = identity, typename _Proj2 = identity> | |
1000 | requires indirectly_writable<_Out, | |
1001 | indirect_result_t<_Fp&, | |
1002 | projected<iterator_t<_Range1>, _Proj1>, | |
1003 | projected<iterator_t<_Range2>, _Proj2>>> | |
15411a64 JW |
1004 | constexpr binary_transform_result<borrowed_iterator_t<_Range1>, |
1005 | borrowed_iterator_t<_Range2>, _Out> | |
55992626 PP |
1006 | operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op, |
1007 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
1008 | { |
1009 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
1010 | ranges::begin(__r2), ranges::end(__r2), |
1011 | std::move(__result), std::move(__binary_op), | |
1012 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
1013 | } |
1014 | }; | |
bc464641 | 1015 | |
b40c57bd | 1016 | inline constexpr __transform_fn transform{}; |
bc464641 | 1017 | |
b40c57bd PP |
1018 | struct __replace_fn |
1019 | { | |
1020 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1021 | typename _Tp1, typename _Tp2, typename _Proj = identity> | |
1022 | requires indirectly_writable<_Iter, const _Tp2&> | |
1023 | && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, | |
1024 | const _Tp1*> | |
1025 | constexpr _Iter | |
1026 | operator()(_Iter __first, _Sent __last, | |
55992626 PP |
1027 | const _Tp1& __old_value, const _Tp2& __new_value, |
1028 | _Proj __proj = {}) const | |
b40c57bd PP |
1029 | { |
1030 | for (; __first != __last; ++__first) | |
1031 | if (std::__invoke(__proj, *__first) == __old_value) | |
1032 | *__first = __new_value; | |
1033 | return __first; | |
1034 | } | |
bc464641 | 1035 | |
b40c57bd PP |
1036 | template<input_range _Range, |
1037 | typename _Tp1, typename _Tp2, typename _Proj = identity> | |
1038 | requires indirectly_writable<iterator_t<_Range>, const _Tp2&> | |
1039 | && indirect_binary_predicate<ranges::equal_to, | |
1040 | projected<iterator_t<_Range>, _Proj>, | |
1041 | const _Tp1*> | |
15411a64 | 1042 | constexpr borrowed_iterator_t<_Range> |
b40c57bd | 1043 | operator()(_Range&& __r, |
55992626 PP |
1044 | const _Tp1& __old_value, const _Tp2& __new_value, |
1045 | _Proj __proj = {}) const | |
b40c57bd PP |
1046 | { |
1047 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1048 | __old_value, __new_value, std::move(__proj)); |
b40c57bd PP |
1049 | } |
1050 | }; | |
bc464641 | 1051 | |
b40c57bd | 1052 | inline constexpr __replace_fn replace{}; |
bc464641 | 1053 | |
b40c57bd PP |
1054 | struct __replace_if_fn |
1055 | { | |
1056 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1057 | typename _Tp, typename _Proj = identity, | |
1058 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
1059 | requires indirectly_writable<_Iter, const _Tp&> | |
1060 | constexpr _Iter | |
1061 | operator()(_Iter __first, _Sent __last, | |
1062 | _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const | |
1063 | { | |
1064 | for (; __first != __last; ++__first) | |
1065 | if (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
1066 | *__first = __new_value; | |
1067 | return std::move(__first); | |
1068 | } | |
bc464641 | 1069 | |
b40c57bd | 1070 | template<input_range _Range, typename _Tp, typename _Proj = identity, |
55992626 PP |
1071 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
1072 | _Pred> | |
b40c57bd | 1073 | requires indirectly_writable<iterator_t<_Range>, const _Tp&> |
15411a64 | 1074 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1075 | operator()(_Range&& __r, |
1076 | _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const | |
1077 | { | |
1078 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1079 | std::move(__pred), __new_value, std::move(__proj)); |
b40c57bd PP |
1080 | } |
1081 | }; | |
1082 | ||
1083 | inline constexpr __replace_if_fn replace_if{}; | |
bc464641 PP |
1084 | |
1085 | template<typename _Iter, typename _Out> | |
aa667c3f | 1086 | using replace_copy_result = in_out_result<_Iter, _Out>; |
bc464641 | 1087 | |
b40c57bd PP |
1088 | struct __replace_copy_fn |
1089 | { | |
1090 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1091 | typename _Tp1, typename _Tp2, output_iterator<const _Tp2&> _Out, | |
1092 | typename _Proj = identity> | |
1093 | requires indirectly_copyable<_Iter, _Out> | |
1094 | && indirect_binary_predicate<ranges::equal_to, | |
1095 | projected<_Iter, _Proj>, const _Tp1*> | |
1096 | constexpr replace_copy_result<_Iter, _Out> | |
1097 | operator()(_Iter __first, _Sent __last, _Out __result, | |
55992626 PP |
1098 | const _Tp1& __old_value, const _Tp2& __new_value, |
1099 | _Proj __proj = {}) const | |
b40c57bd PP |
1100 | { |
1101 | for (; __first != __last; ++__first, (void)++__result) | |
1102 | if (std::__invoke(__proj, *__first) == __old_value) | |
1103 | *__result = __new_value; | |
1104 | else | |
bc464641 | 1105 | *__result = *__first; |
b40c57bd PP |
1106 | return {std::move(__first), std::move(__result)}; |
1107 | } | |
bc464641 | 1108 | |
b40c57bd PP |
1109 | template<input_range _Range, typename _Tp1, typename _Tp2, |
1110 | output_iterator<const _Tp2&> _Out, typename _Proj = identity> | |
1111 | requires indirectly_copyable<iterator_t<_Range>, _Out> | |
1112 | && indirect_binary_predicate<ranges::equal_to, | |
1113 | projected<iterator_t<_Range>, _Proj>, | |
1114 | const _Tp1*> | |
15411a64 | 1115 | constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd | 1116 | operator()(_Range&& __r, _Out __result, |
55992626 PP |
1117 | const _Tp1& __old_value, const _Tp2& __new_value, |
1118 | _Proj __proj = {}) const | |
b40c57bd PP |
1119 | { |
1120 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
1121 | std::move(__result), __old_value, |
1122 | __new_value, std::move(__proj)); | |
b40c57bd PP |
1123 | } |
1124 | }; | |
1125 | ||
1126 | inline constexpr __replace_copy_fn replace_copy{}; | |
bc464641 PP |
1127 | |
1128 | template<typename _Iter, typename _Out> | |
aa667c3f | 1129 | using replace_copy_if_result = in_out_result<_Iter, _Out>; |
bc464641 | 1130 | |
b40c57bd PP |
1131 | struct __replace_copy_if_fn |
1132 | { | |
1133 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1134 | typename _Tp, output_iterator<const _Tp&> _Out, | |
1135 | typename _Proj = identity, | |
1136 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
1137 | requires indirectly_copyable<_Iter, _Out> | |
1138 | constexpr replace_copy_if_result<_Iter, _Out> | |
1139 | operator()(_Iter __first, _Sent __last, _Out __result, | |
55992626 | 1140 | _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const |
b40c57bd PP |
1141 | { |
1142 | for (; __first != __last; ++__first, (void)++__result) | |
1143 | if (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
1144 | *__result = __new_value; | |
1145 | else | |
1146 | *__result = *__first; | |
bc464641 | 1147 | return {std::move(__first), std::move(__result)}; |
b40c57bd | 1148 | } |
bc464641 | 1149 | |
b40c57bd PP |
1150 | template<input_range _Range, |
1151 | typename _Tp, output_iterator<const _Tp&> _Out, | |
1152 | typename _Proj = identity, | |
55992626 PP |
1153 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
1154 | _Pred> | |
b40c57bd | 1155 | requires indirectly_copyable<iterator_t<_Range>, _Out> |
15411a64 | 1156 | constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd | 1157 | operator()(_Range&& __r, _Out __result, |
55992626 | 1158 | _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const |
b40c57bd PP |
1159 | { |
1160 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
1161 | std::move(__result), std::move(__pred), |
1162 | __new_value, std::move(__proj)); | |
b40c57bd PP |
1163 | } |
1164 | }; | |
bc464641 | 1165 | |
b40c57bd | 1166 | inline constexpr __replace_copy_if_fn replace_copy_if{}; |
bc464641 | 1167 | |
b40c57bd PP |
1168 | struct __generate_n_fn |
1169 | { | |
1170 | template<input_or_output_iterator _Out, copy_constructible _Fp> | |
1171 | requires invocable<_Fp&> | |
1172 | && indirectly_writable<_Out, invoke_result_t<_Fp&>> | |
1173 | constexpr _Out | |
1174 | operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen) const | |
1175 | { | |
1176 | for (; __n > 0; --__n, (void)++__first) | |
1177 | *__first = std::__invoke(__gen); | |
1178 | return __first; | |
1179 | } | |
1180 | }; | |
bc464641 | 1181 | |
b40c57bd | 1182 | inline constexpr __generate_n_fn generate_n{}; |
bc464641 | 1183 | |
b40c57bd PP |
1184 | struct __generate_fn |
1185 | { | |
1186 | template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, | |
1187 | copy_constructible _Fp> | |
1188 | requires invocable<_Fp&> | |
1189 | && indirectly_writable<_Out, invoke_result_t<_Fp&>> | |
1190 | constexpr _Out | |
1191 | operator()(_Out __first, _Sent __last, _Fp __gen) const | |
1192 | { | |
1193 | for (; __first != __last; ++__first) | |
1194 | *__first = std::__invoke(__gen); | |
1195 | return __first; | |
1196 | } | |
bc464641 | 1197 | |
b40c57bd PP |
1198 | template<typename _Range, copy_constructible _Fp> |
1199 | requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>> | |
15411a64 | 1200 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1201 | operator()(_Range&& __r, _Fp __gen) const |
1202 | { | |
55992626 | 1203 | return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__gen)); |
b40c57bd PP |
1204 | } |
1205 | }; | |
bc464641 | 1206 | |
b40c57bd | 1207 | inline constexpr __generate_fn generate{}; |
bc464641 | 1208 | |
b40c57bd PP |
1209 | struct __remove_if_fn |
1210 | { | |
1211 | template<permutable _Iter, sentinel_for<_Iter> _Sent, | |
1212 | typename _Proj = identity, | |
1213 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
1214 | constexpr subrange<_Iter> | |
55992626 PP |
1215 | operator()(_Iter __first, _Sent __last, |
1216 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
1217 | { |
1218 | __first = ranges::find_if(__first, __last, __pred, __proj); | |
1219 | if (__first == __last) | |
1220 | return {__first, __first}; | |
bc464641 | 1221 | |
b40c57bd PP |
1222 | auto __result = __first; |
1223 | ++__first; | |
1224 | for (; __first != __last; ++__first) | |
a45fb21a | 1225 | if (!std::__invoke(__pred, std::__invoke(__proj, *__first))) |
bc464641 | 1226 | { |
b40c57bd PP |
1227 | *__result = std::move(*__first); |
1228 | ++__result; | |
bc464641 PP |
1229 | } |
1230 | ||
b40c57bd PP |
1231 | return {__result, __first}; |
1232 | } | |
bc464641 | 1233 | |
b40c57bd | 1234 | template<forward_range _Range, typename _Proj = identity, |
55992626 PP |
1235 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
1236 | _Pred> | |
b40c57bd | 1237 | requires permutable<iterator_t<_Range>> |
15411a64 | 1238 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
1239 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const |
1240 | { | |
1241 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1242 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
1243 | } |
1244 | }; | |
bc464641 | 1245 | |
b40c57bd | 1246 | inline constexpr __remove_if_fn remove_if{}; |
bc464641 | 1247 | |
b40c57bd PP |
1248 | struct __remove_fn |
1249 | { | |
1250 | template<permutable _Iter, sentinel_for<_Iter> _Sent, | |
1251 | typename _Tp, typename _Proj = identity> | |
1252 | requires indirect_binary_predicate<ranges::equal_to, | |
1253 | projected<_Iter, _Proj>, | |
1254 | const _Tp*> | |
1255 | constexpr subrange<_Iter> | |
55992626 PP |
1256 | operator()(_Iter __first, _Sent __last, |
1257 | const _Tp& __value, _Proj __proj = {}) const | |
b40c57bd PP |
1258 | { |
1259 | auto __pred = [&] (auto&& __arg) { | |
1260 | return std::forward<decltype(__arg)>(__arg) == __value; | |
1261 | }; | |
1262 | return ranges::remove_if(__first, __last, | |
1263 | std::move(__pred), std::move(__proj)); | |
1264 | } | |
1265 | ||
1266 | template<forward_range _Range, typename _Tp, typename _Proj = identity> | |
1267 | requires permutable<iterator_t<_Range>> | |
1268 | && indirect_binary_predicate<ranges::equal_to, | |
1269 | projected<iterator_t<_Range>, _Proj>, | |
1270 | const _Tp*> | |
15411a64 | 1271 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
1272 | operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const |
1273 | { | |
1274 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1275 | __value, std::move(__proj)); |
b40c57bd PP |
1276 | } |
1277 | }; | |
1278 | ||
1279 | inline constexpr __remove_fn remove{}; | |
1280 | ||
1281 | template<typename _Iter, typename _Out> | |
aa667c3f | 1282 | using remove_copy_if_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
1283 | |
1284 | struct __remove_copy_if_fn | |
1285 | { | |
1286 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1287 | weakly_incrementable _Out, typename _Proj = identity, | |
1288 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
1289 | requires indirectly_copyable<_Iter, _Out> | |
1290 | constexpr remove_copy_if_result<_Iter, _Out> | |
1291 | operator()(_Iter __first, _Sent __last, _Out __result, | |
55992626 | 1292 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
1293 | { |
1294 | for (; __first != __last; ++__first) | |
a45fb21a | 1295 | if (!std::__invoke(__pred, std::__invoke(__proj, *__first))) |
bc464641 | 1296 | { |
b40c57bd PP |
1297 | *__result = *__first; |
1298 | ++__result; | |
bc464641 | 1299 | } |
b40c57bd PP |
1300 | return {std::move(__first), std::move(__result)}; |
1301 | } | |
bc464641 | 1302 | |
b40c57bd PP |
1303 | template<input_range _Range, weakly_incrementable _Out, |
1304 | typename _Proj = identity, | |
55992626 PP |
1305 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
1306 | _Pred> | |
b40c57bd | 1307 | requires indirectly_copyable<iterator_t<_Range>, _Out> |
15411a64 | 1308 | constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd | 1309 | operator()(_Range&& __r, _Out __result, |
55992626 | 1310 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
1311 | { |
1312 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
1313 | std::move(__result), |
1314 | std::move(__pred), std::move(__proj)); | |
b40c57bd PP |
1315 | } |
1316 | }; | |
bc464641 | 1317 | |
b40c57bd | 1318 | inline constexpr __remove_copy_if_fn remove_copy_if{}; |
bc464641 | 1319 | |
b40c57bd | 1320 | template<typename _Iter, typename _Out> |
aa667c3f | 1321 | using remove_copy_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
1322 | |
1323 | struct __remove_copy_fn | |
1324 | { | |
1325 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1326 | weakly_incrementable _Out, typename _Tp, typename _Proj = identity> | |
1327 | requires indirectly_copyable<_Iter, _Out> | |
1328 | && indirect_binary_predicate<ranges::equal_to, | |
1329 | projected<_Iter, _Proj>, | |
1330 | const _Tp*> | |
1331 | constexpr remove_copy_result<_Iter, _Out> | |
1332 | operator()(_Iter __first, _Sent __last, _Out __result, | |
55992626 | 1333 | const _Tp& __value, _Proj __proj = {}) const |
b40c57bd PP |
1334 | { |
1335 | for (; __first != __last; ++__first) | |
1336 | if (!(std::__invoke(__proj, *__first) == __value)) | |
bc464641 | 1337 | { |
b40c57bd PP |
1338 | *__result = *__first; |
1339 | ++__result; | |
bc464641 | 1340 | } |
b40c57bd PP |
1341 | return {std::move(__first), std::move(__result)}; |
1342 | } | |
bc464641 | 1343 | |
b40c57bd PP |
1344 | template<input_range _Range, weakly_incrementable _Out, |
1345 | typename _Tp, typename _Proj = identity> | |
1346 | requires indirectly_copyable<iterator_t<_Range>, _Out> | |
1347 | && indirect_binary_predicate<ranges::equal_to, | |
1348 | projected<iterator_t<_Range>, _Proj>, | |
1349 | const _Tp*> | |
15411a64 | 1350 | constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd | 1351 | operator()(_Range&& __r, _Out __result, |
55992626 | 1352 | const _Tp& __value, _Proj __proj = {}) const |
b40c57bd PP |
1353 | { |
1354 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1355 | std::move(__result), __value, std::move(__proj)); |
b40c57bd PP |
1356 | } |
1357 | }; | |
bc464641 | 1358 | |
b40c57bd | 1359 | inline constexpr __remove_copy_fn remove_copy{}; |
bc464641 | 1360 | |
b40c57bd PP |
1361 | struct __unique_fn |
1362 | { | |
1363 | template<permutable _Iter, sentinel_for<_Iter> _Sent, | |
1364 | typename _Proj = identity, | |
1365 | indirect_equivalence_relation< | |
1366 | projected<_Iter, _Proj>> _Comp = ranges::equal_to> | |
1367 | constexpr subrange<_Iter> | |
55992626 PP |
1368 | operator()(_Iter __first, _Sent __last, |
1369 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
1370 | { |
1371 | __first = ranges::adjacent_find(__first, __last, __comp, __proj); | |
1372 | if (__first == __last) | |
1373 | return {__first, __first}; | |
bc464641 | 1374 | |
b40c57bd PP |
1375 | auto __dest = __first; |
1376 | ++__first; | |
1377 | while (++__first != __last) | |
a45fb21a JW |
1378 | if (!std::__invoke(__comp, |
1379 | std::__invoke(__proj, *__dest), | |
1380 | std::__invoke(__proj, *__first))) | |
b40c57bd PP |
1381 | *++__dest = std::move(*__first); |
1382 | return {++__dest, __first}; | |
1383 | } | |
bc464641 | 1384 | |
b40c57bd PP |
1385 | template<forward_range _Range, typename _Proj = identity, |
1386 | indirect_equivalence_relation< | |
1387 | projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to> | |
1388 | requires permutable<iterator_t<_Range>> | |
15411a64 | 1389 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
1390 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1391 | { | |
1392 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1393 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1394 | } |
1395 | }; | |
bc464641 | 1396 | |
b40c57bd | 1397 | inline constexpr __unique_fn unique{}; |
bc464641 | 1398 | |
b40c57bd | 1399 | template<typename _Iter, typename _Out> |
aa667c3f | 1400 | using unique_copy_result = in_out_result<_Iter, _Out>; |
bc464641 | 1401 | |
b40c57bd PP |
1402 | struct __unique_copy_fn |
1403 | { | |
1404 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1405 | weakly_incrementable _Out, typename _Proj = identity, | |
1406 | indirect_equivalence_relation< | |
1407 | projected<_Iter, _Proj>> _Comp = ranges::equal_to> | |
1408 | requires indirectly_copyable<_Iter, _Out> | |
1409 | && (forward_iterator<_Iter> | |
1410 | || (input_iterator<_Out> | |
1411 | && same_as<iter_value_t<_Iter>, iter_value_t<_Out>>) | |
1412 | || indirectly_copyable_storable<_Iter, _Out>) | |
1413 | constexpr unique_copy_result<_Iter, _Out> | |
1414 | operator()(_Iter __first, _Sent __last, _Out __result, | |
55992626 | 1415 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
1416 | { |
1417 | if (__first == __last) | |
1418 | return {std::move(__first), std::move(__result)}; | |
1419 | ||
1420 | // TODO: perform a closer comparison with reference implementations | |
1421 | if constexpr (forward_iterator<_Iter>) | |
1422 | { | |
1423 | auto __next = __first; | |
1424 | *__result = *__next; | |
1425 | while (++__next != __last) | |
a45fb21a JW |
1426 | if (!std::__invoke(__comp, |
1427 | std::__invoke(__proj, *__first), | |
1428 | std::__invoke(__proj, *__next))) | |
b40c57bd PP |
1429 | { |
1430 | __first = __next; | |
1431 | *++__result = *__first; | |
1432 | } | |
1433 | return {__next, std::move(++__result)}; | |
1434 | } | |
1435 | else if constexpr (input_iterator<_Out> | |
1436 | && same_as<iter_value_t<_Iter>, iter_value_t<_Out>>) | |
1437 | { | |
1438 | *__result = *__first; | |
1439 | while (++__first != __last) | |
a45fb21a JW |
1440 | if (!std::__invoke(__comp, |
1441 | std::__invoke(__proj, *__result), | |
1442 | std::__invoke(__proj, *__first))) | |
b40c57bd PP |
1443 | *++__result = *__first; |
1444 | return {std::move(__first), std::move(++__result)}; | |
1445 | } | |
1446 | else // indirectly_copyable_storable<_Iter, _Out> | |
1447 | { | |
1448 | auto __value = *__first; | |
1449 | *__result = __value; | |
1450 | while (++__first != __last) | |
1451 | { | |
1452 | if (!(bool)std::__invoke(__comp, | |
1453 | std::__invoke(__proj, *__first), | |
1454 | std::__invoke(__proj, __value))) | |
1455 | { | |
1456 | __value = *__first; | |
1457 | *++__result = __value; | |
1458 | } | |
1459 | } | |
1460 | return {std::move(__first), std::move(++__result)}; | |
1461 | } | |
1462 | } | |
1463 | ||
1464 | template<input_range _Range, | |
1465 | weakly_incrementable _Out, typename _Proj = identity, | |
1466 | indirect_equivalence_relation< | |
1467 | projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to> | |
1468 | requires indirectly_copyable<iterator_t<_Range>, _Out> | |
1469 | && (forward_iterator<iterator_t<_Range>> | |
1470 | || (input_iterator<_Out> | |
1471 | && same_as<range_value_t<_Range>, iter_value_t<_Out>>) | |
1472 | || indirectly_copyable_storable<iterator_t<_Range>, _Out>) | |
15411a64 | 1473 | constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd | 1474 | operator()(_Range&& __r, _Out __result, |
55992626 | 1475 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
1476 | { |
1477 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
1478 | std::move(__result), |
1479 | std::move(__comp), std::move(__proj)); | |
b40c57bd PP |
1480 | } |
1481 | }; | |
1482 | ||
1483 | inline constexpr __unique_copy_fn unique_copy{}; | |
1484 | ||
1485 | struct __reverse_fn | |
1486 | { | |
1487 | template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent> | |
1488 | requires permutable<_Iter> | |
1489 | constexpr _Iter | |
1490 | operator()(_Iter __first, _Sent __last) const | |
1491 | { | |
1492 | auto __i = ranges::next(__first, __last); | |
1493 | auto __tail = __i; | |
1494 | ||
1495 | if constexpr (random_access_iterator<_Iter>) | |
bc464641 | 1496 | { |
b40c57bd PP |
1497 | if (__first != __last) |
1498 | { | |
1499 | --__tail; | |
1500 | while (__first < __tail) | |
1501 | { | |
1502 | ranges::iter_swap(__first, __tail); | |
1503 | ++__first; | |
1504 | --__tail; | |
1505 | } | |
1506 | } | |
1507 | return __i; | |
bc464641 | 1508 | } |
b40c57bd PP |
1509 | else |
1510 | { | |
1511 | for (;;) | |
1512 | if (__first == __tail || __first == --__tail) | |
1513 | break; | |
1514 | else | |
1515 | { | |
1516 | ranges::iter_swap(__first, __tail); | |
1517 | ++__first; | |
1518 | } | |
1519 | return __i; | |
1520 | } | |
1521 | } | |
bc464641 | 1522 | |
b40c57bd PP |
1523 | template<bidirectional_range _Range> |
1524 | requires permutable<iterator_t<_Range>> | |
15411a64 | 1525 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1526 | operator()(_Range&& __r) const |
1527 | { | |
1528 | return (*this)(ranges::begin(__r), ranges::end(__r)); | |
1529 | } | |
1530 | }; | |
bc464641 | 1531 | |
b40c57bd | 1532 | inline constexpr __reverse_fn reverse{}; |
bc464641 PP |
1533 | |
1534 | template<typename _Iter, typename _Out> | |
aa667c3f | 1535 | using reverse_copy_result = in_out_result<_Iter, _Out>; |
bc464641 | 1536 | |
b40c57bd PP |
1537 | struct __reverse_copy_fn |
1538 | { | |
1539 | template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1540 | weakly_incrementable _Out> | |
1541 | requires indirectly_copyable<_Iter, _Out> | |
1542 | constexpr reverse_copy_result<_Iter, _Out> | |
1543 | operator()(_Iter __first, _Sent __last, _Out __result) const | |
1544 | { | |
1545 | auto __i = ranges::next(__first, __last); | |
1546 | auto __tail = __i; | |
1547 | while (__first != __tail) | |
1548 | { | |
1549 | --__tail; | |
1550 | *__result = *__tail; | |
1551 | ++__result; | |
1552 | } | |
1553 | return {__i, __result}; | |
1554 | } | |
bc464641 | 1555 | |
b40c57bd PP |
1556 | template<bidirectional_range _Range, weakly_incrementable _Out> |
1557 | requires indirectly_copyable<iterator_t<_Range>, _Out> | |
15411a64 | 1558 | constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd PP |
1559 | operator()(_Range&& __r, _Out __result) const |
1560 | { | |
1561 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1562 | std::move(__result)); |
b40c57bd PP |
1563 | } |
1564 | }; | |
1565 | ||
1566 | inline constexpr __reverse_copy_fn reverse_copy{}; | |
1567 | ||
1568 | struct __rotate_fn | |
1569 | { | |
1570 | template<permutable _Iter, sentinel_for<_Iter> _Sent> | |
1571 | constexpr subrange<_Iter> | |
1572 | operator()(_Iter __first, _Iter __middle, _Sent __last) const | |
1573 | { | |
1574 | auto __lasti = ranges::next(__first, __last); | |
1575 | if (__first == __middle) | |
1576 | return {__lasti, __lasti}; | |
1577 | if (__last == __middle) | |
1578 | return {std::move(__first), std::move(__lasti)}; | |
1579 | ||
1580 | if constexpr (random_access_iterator<_Iter>) | |
1581 | { | |
1582 | auto __n = __lasti - __first; | |
1583 | auto __k = __middle - __first; | |
1584 | ||
1585 | if (__k == __n - __k) | |
1586 | { | |
1587 | ranges::swap_ranges(__first, __middle, __middle, __middle + __k); | |
1588 | return {std::move(__middle), std::move(__lasti)}; | |
1589 | } | |
1590 | ||
1591 | auto __p = __first; | |
1592 | auto __ret = __first + (__lasti - __middle); | |
1593 | ||
1594 | for (;;) | |
1595 | { | |
1596 | if (__k < __n - __k) | |
1597 | { | |
1598 | // TODO: is_pod is deprecated, but this condition is | |
1599 | // consistent with the STL implementation. | |
1600 | if constexpr (__is_pod(iter_value_t<_Iter>)) | |
1601 | if (__k == 1) | |
1602 | { | |
1603 | auto __t = std::move(*__p); | |
1604 | ranges::move(__p + 1, __p + __n, __p); | |
1605 | *(__p + __n - 1) = std::move(__t); | |
1606 | return {std::move(__ret), std::move(__lasti)}; | |
1607 | } | |
1608 | auto __q = __p + __k; | |
1609 | for (decltype(__n) __i = 0; __i < __n - __k; ++ __i) | |
1610 | { | |
1611 | ranges::iter_swap(__p, __q); | |
1612 | ++__p; | |
1613 | ++__q; | |
1614 | } | |
1615 | __n %= __k; | |
1616 | if (__n == 0) | |
1617 | return {std::move(__ret), std::move(__lasti)}; | |
1618 | ranges::swap(__n, __k); | |
1619 | __k = __n - __k; | |
1620 | } | |
1621 | else | |
1622 | { | |
1623 | __k = __n - __k; | |
1624 | // TODO: is_pod is deprecated, but this condition is | |
1625 | // consistent with the STL implementation. | |
1626 | if constexpr (__is_pod(iter_value_t<_Iter>)) | |
1627 | if (__k == 1) | |
1628 | { | |
1629 | auto __t = std::move(*(__p + __n - 1)); | |
1630 | ranges::move_backward(__p, __p + __n - 1, __p + __n); | |
1631 | *__p = std::move(__t); | |
1632 | return {std::move(__ret), std::move(__lasti)}; | |
1633 | } | |
1634 | auto __q = __p + __n; | |
1635 | __p = __q - __k; | |
1636 | for (decltype(__n) __i = 0; __i < __n - __k; ++ __i) | |
1637 | { | |
1638 | --__p; | |
1639 | --__q; | |
1640 | ranges::iter_swap(__p, __q); | |
1641 | } | |
1642 | __n %= __k; | |
1643 | if (__n == 0) | |
1644 | return {std::move(__ret), std::move(__lasti)}; | |
1645 | std::swap(__n, __k); | |
1646 | } | |
1647 | } | |
1648 | } | |
1649 | else if constexpr (bidirectional_iterator<_Iter>) | |
1650 | { | |
1651 | auto __tail = __lasti; | |
bc464641 | 1652 | |
b40c57bd PP |
1653 | ranges::reverse(__first, __middle); |
1654 | ranges::reverse(__middle, __tail); | |
1655 | ||
1656 | while (__first != __middle && __middle != __tail) | |
1657 | { | |
1658 | ranges::iter_swap(__first, --__tail); | |
1659 | ++__first; | |
1660 | } | |
1661 | ||
1662 | if (__first == __middle) | |
1663 | { | |
1664 | ranges::reverse(__middle, __tail); | |
1665 | return {std::move(__tail), std::move(__lasti)}; | |
1666 | } | |
1667 | else | |
1668 | { | |
1669 | ranges::reverse(__first, __middle); | |
1670 | return {std::move(__first), std::move(__lasti)}; | |
1671 | } | |
1672 | } | |
1673 | else | |
bc464641 | 1674 | { |
b40c57bd PP |
1675 | auto __first2 = __middle; |
1676 | do | |
1677 | { | |
1678 | ranges::iter_swap(__first, __first2); | |
1679 | ++__first; | |
1680 | ++__first2; | |
1681 | if (__first == __middle) | |
1682 | __middle = __first2; | |
1683 | } while (__first2 != __last); | |
1684 | ||
1685 | auto __ret = __first; | |
1686 | ||
1687 | __first2 = __middle; | |
1688 | ||
1689 | while (__first2 != __last) | |
1690 | { | |
1691 | ranges::iter_swap(__first, __first2); | |
1692 | ++__first; | |
1693 | ++__first2; | |
1694 | if (__first == __middle) | |
1695 | __middle = __first2; | |
1696 | else if (__first2 == __last) | |
1697 | __first2 = __middle; | |
1698 | } | |
1699 | return {std::move(__ret), std::move(__lasti)}; | |
bc464641 | 1700 | } |
b40c57bd | 1701 | } |
bc464641 | 1702 | |
b40c57bd PP |
1703 | template<forward_range _Range> |
1704 | requires permutable<iterator_t<_Range>> | |
15411a64 | 1705 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
1706 | operator()(_Range&& __r, iterator_t<_Range> __middle) const |
1707 | { | |
55992626 PP |
1708 | return (*this)(ranges::begin(__r), std::move(__middle), |
1709 | ranges::end(__r)); | |
b40c57bd PP |
1710 | } |
1711 | }; | |
bc464641 | 1712 | |
b40c57bd PP |
1713 | inline constexpr __rotate_fn rotate{}; |
1714 | ||
1715 | template<typename _Iter, typename _Out> | |
aa667c3f | 1716 | using rotate_copy_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
1717 | |
1718 | struct __rotate_copy_fn | |
1719 | { | |
1720 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1721 | weakly_incrementable _Out> | |
1722 | requires indirectly_copyable<_Iter, _Out> | |
1723 | constexpr rotate_copy_result<_Iter, _Out> | |
55992626 PP |
1724 | operator()(_Iter __first, _Iter __middle, _Sent __last, |
1725 | _Out __result) const | |
b40c57bd PP |
1726 | { |
1727 | auto __copy1 = ranges::copy(__middle, | |
1728 | std::move(__last), | |
1729 | std::move(__result)); | |
1730 | auto __copy2 = ranges::copy(std::move(__first), | |
1731 | std::move(__middle), | |
1732 | std::move(__copy1.out)); | |
1733 | return { std::move(__copy1.in), std::move(__copy2.out) }; | |
1734 | } | |
1735 | ||
1736 | template<forward_range _Range, weakly_incrementable _Out> | |
1737 | requires indirectly_copyable<iterator_t<_Range>, _Out> | |
15411a64 | 1738 | constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd PP |
1739 | operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result) const |
1740 | { | |
55992626 PP |
1741 | return (*this)(ranges::begin(__r), std::move(__middle), |
1742 | ranges::end(__r), std::move(__result)); | |
b40c57bd PP |
1743 | } |
1744 | }; | |
1745 | ||
1746 | inline constexpr __rotate_copy_fn rotate_copy{}; | |
1747 | ||
f3169941 PP |
1748 | struct __sample_fn |
1749 | { | |
1750 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1751 | weakly_incrementable _Out, typename _Gen> | |
1752 | requires (forward_iterator<_Iter> || random_access_iterator<_Out>) | |
1753 | && indirectly_copyable<_Iter, _Out> | |
1754 | && uniform_random_bit_generator<remove_reference_t<_Gen>> | |
1755 | _Out | |
1756 | operator()(_Iter __first, _Sent __last, _Out __out, | |
1757 | iter_difference_t<_Iter> __n, _Gen&& __g) const | |
1758 | { | |
1759 | if constexpr (forward_iterator<_Iter>) | |
1760 | { | |
1761 | // FIXME: Forwarding to std::sample here requires computing __lasti | |
1762 | // which may take linear time. | |
1763 | auto __lasti = ranges::next(__first, __last); | |
9c24e97a JW |
1764 | return _GLIBCXX_STD_A:: |
1765 | sample(std::move(__first), std::move(__lasti), std::move(__out), | |
1766 | __n, std::forward<_Gen>(__g)); | |
f3169941 PP |
1767 | } |
1768 | else | |
1769 | { | |
1770 | using __distrib_type | |
1771 | = uniform_int_distribution<iter_difference_t<_Iter>>; | |
1772 | using __param_type = typename __distrib_type::param_type; | |
1773 | __distrib_type __d{}; | |
1774 | iter_difference_t<_Iter> __sample_sz = 0; | |
1775 | while (__first != __last && __sample_sz != __n) | |
1776 | { | |
1777 | __out[__sample_sz++] = *__first; | |
1778 | ++__first; | |
1779 | } | |
1780 | for (auto __pop_sz = __sample_sz; __first != __last; | |
1781 | ++__first, (void) ++__pop_sz) | |
1782 | { | |
1783 | const auto __k = __d(__g, __param_type{0, __pop_sz}); | |
1784 | if (__k < __n) | |
1785 | __out[__k] = *__first; | |
1786 | } | |
1787 | return __out + __sample_sz; | |
1788 | } | |
1789 | } | |
1790 | ||
1791 | template<input_range _Range, weakly_incrementable _Out, typename _Gen> | |
1792 | requires (forward_range<_Range> || random_access_iterator<_Out>) | |
1793 | && indirectly_copyable<iterator_t<_Range>, _Out> | |
1794 | && uniform_random_bit_generator<remove_reference_t<_Gen>> | |
1795 | _Out | |
1796 | operator()(_Range&& __r, _Out __out, | |
1797 | range_difference_t<_Range> __n, _Gen&& __g) const | |
1798 | { | |
1799 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
1800 | std::move(__out), __n, | |
1801 | std::forward<_Gen>(__g)); | |
1802 | } | |
1803 | }; | |
1804 | ||
1805 | inline constexpr __sample_fn sample{}; | |
1806 | ||
b40c57bd PP |
1807 | #ifdef _GLIBCXX_USE_C99_STDINT_TR1 |
1808 | struct __shuffle_fn | |
1809 | { | |
1810 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1811 | typename _Gen> | |
1812 | requires permutable<_Iter> | |
1813 | && uniform_random_bit_generator<remove_reference_t<_Gen>> | |
1814 | _Iter | |
1815 | operator()(_Iter __first, _Sent __last, _Gen&& __g) const | |
1816 | { | |
1817 | auto __lasti = ranges::next(__first, __last); | |
1818 | std::shuffle(std::move(__first), __lasti, std::forward<_Gen>(__g)); | |
1819 | return __lasti; | |
1820 | } | |
1821 | ||
1822 | template<random_access_range _Range, typename _Gen> | |
1823 | requires permutable<iterator_t<_Range>> | |
1824 | && uniform_random_bit_generator<remove_reference_t<_Gen>> | |
15411a64 | 1825 | borrowed_iterator_t<_Range> |
b40c57bd PP |
1826 | operator()(_Range&& __r, _Gen&& __g) const |
1827 | { | |
1828 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1829 | std::forward<_Gen>(__g)); |
b40c57bd PP |
1830 | } |
1831 | }; | |
1832 | ||
1833 | inline constexpr __shuffle_fn shuffle{}; | |
1834 | #endif | |
1835 | ||
1836 | struct __push_heap_fn | |
1837 | { | |
1838 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1839 | typename _Comp = ranges::less, typename _Proj = identity> | |
1840 | requires sortable<_Iter, _Comp, _Proj> | |
1841 | constexpr _Iter | |
55992626 PP |
1842 | operator()(_Iter __first, _Sent __last, |
1843 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
1844 | { |
1845 | auto __lasti = ranges::next(__first, __last); | |
1846 | std::push_heap(__first, __lasti, | |
bc464641 | 1847 | __detail::__make_comp_proj(__comp, __proj)); |
b40c57bd PP |
1848 | return __lasti; |
1849 | } | |
1850 | ||
1851 | template<random_access_range _Range, | |
1852 | typename _Comp = ranges::less, typename _Proj = identity> | |
1853 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 1854 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1855 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1856 | { | |
1857 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1858 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1859 | } |
1860 | }; | |
bc464641 | 1861 | |
b40c57bd PP |
1862 | inline constexpr __push_heap_fn push_heap{}; |
1863 | ||
1864 | struct __pop_heap_fn | |
1865 | { | |
1866 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1867 | typename _Comp = ranges::less, typename _Proj = identity> | |
1868 | requires sortable<_Iter, _Comp, _Proj> | |
1869 | constexpr _Iter | |
55992626 PP |
1870 | operator()(_Iter __first, _Sent __last, |
1871 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
1872 | { |
1873 | auto __lasti = ranges::next(__first, __last); | |
1874 | std::pop_heap(__first, __lasti, | |
1875 | __detail::__make_comp_proj(__comp, __proj)); | |
1876 | return __lasti; | |
1877 | } | |
1878 | ||
1879 | template<random_access_range _Range, | |
1880 | typename _Comp = ranges::less, typename _Proj = identity> | |
1881 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 1882 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1883 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1884 | { | |
1885 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1886 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1887 | } |
1888 | }; | |
bc464641 | 1889 | |
b40c57bd PP |
1890 | inline constexpr __pop_heap_fn pop_heap{}; |
1891 | ||
1892 | struct __make_heap_fn | |
1893 | { | |
1894 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1895 | typename _Comp = ranges::less, typename _Proj = identity> | |
1896 | requires sortable<_Iter, _Comp, _Proj> | |
1897 | constexpr _Iter | |
55992626 PP |
1898 | operator()(_Iter __first, _Sent __last, |
1899 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
1900 | { |
1901 | auto __lasti = ranges::next(__first, __last); | |
1902 | std::make_heap(__first, __lasti, | |
1903 | __detail::__make_comp_proj(__comp, __proj)); | |
1904 | return __lasti; | |
1905 | } | |
1906 | ||
1907 | template<random_access_range _Range, | |
1908 | typename _Comp = ranges::less, typename _Proj = identity> | |
1909 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 1910 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1911 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1912 | { | |
1913 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1914 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1915 | } |
1916 | }; | |
bc464641 | 1917 | |
b40c57bd PP |
1918 | inline constexpr __make_heap_fn make_heap{}; |
1919 | ||
1920 | struct __sort_heap_fn | |
1921 | { | |
1922 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1923 | typename _Comp = ranges::less, typename _Proj = identity> | |
1924 | requires sortable<_Iter, _Comp, _Proj> | |
1925 | constexpr _Iter | |
55992626 PP |
1926 | operator()(_Iter __first, _Sent __last, |
1927 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
1928 | { |
1929 | auto __lasti = ranges::next(__first, __last); | |
1930 | std::sort_heap(__first, __lasti, | |
1931 | __detail::__make_comp_proj(__comp, __proj)); | |
1932 | return __lasti; | |
1933 | } | |
1934 | ||
1935 | template<random_access_range _Range, | |
1936 | typename _Comp = ranges::less, typename _Proj = identity> | |
1937 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 1938 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1939 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1940 | { | |
1941 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1942 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1943 | } |
1944 | }; | |
1945 | ||
1946 | inline constexpr __sort_heap_fn sort_heap{}; | |
1947 | ||
1948 | struct __is_heap_until_fn | |
1949 | { | |
1950 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1951 | typename _Proj = identity, | |
1952 | indirect_strict_weak_order<projected<_Iter, _Proj>> | |
1953 | _Comp = ranges::less> | |
1954 | constexpr _Iter | |
1955 | operator()(_Iter __first, _Sent __last, | |
55992626 | 1956 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
1957 | { |
1958 | iter_difference_t<_Iter> __n = ranges::distance(__first, __last); | |
1959 | iter_difference_t<_Iter> __parent = 0, __child = 1; | |
1960 | for (; __child < __n; ++__child) | |
1961 | if (std::__invoke(__comp, | |
1962 | std::__invoke(__proj, *(__first + __parent)), | |
1963 | std::__invoke(__proj, *(__first + __child)))) | |
1964 | return __first + __child; | |
1965 | else if ((__child & 1) == 0) | |
1966 | ++__parent; | |
1967 | ||
1968 | return __first + __n; | |
1969 | } | |
1970 | ||
1971 | template<random_access_range _Range, | |
1972 | typename _Proj = identity, | |
1973 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
1974 | _Comp = ranges::less> | |
15411a64 | 1975 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1976 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1977 | { | |
1978 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1979 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1980 | } |
1981 | }; | |
1982 | ||
1983 | inline constexpr __is_heap_until_fn is_heap_until{}; | |
1984 | ||
1985 | struct __is_heap_fn | |
1986 | { | |
1987 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
1988 | typename _Proj = identity, | |
1989 | indirect_strict_weak_order<projected<_Iter, _Proj>> | |
1990 | _Comp = ranges::less> | |
1991 | constexpr bool | |
55992626 PP |
1992 | operator()(_Iter __first, _Sent __last, |
1993 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
1994 | { |
1995 | return (__last | |
1996 | == ranges::is_heap_until(__first, __last, | |
1997 | std::move(__comp), | |
1998 | std::move(__proj))); | |
1999 | } | |
2000 | ||
2001 | template<random_access_range _Range, | |
2002 | typename _Proj = identity, | |
2003 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
2004 | _Comp = ranges::less> | |
2005 | constexpr bool | |
2006 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const | |
2007 | { | |
2008 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2009 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2010 | } |
2011 | }; | |
2012 | ||
2013 | inline constexpr __is_heap_fn is_heap{}; | |
2014 | ||
2015 | struct __sort_fn | |
2016 | { | |
2017 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2018 | typename _Comp = ranges::less, typename _Proj = identity> | |
2019 | requires sortable<_Iter, _Comp, _Proj> | |
2020 | constexpr _Iter | |
55992626 PP |
2021 | operator()(_Iter __first, _Sent __last, |
2022 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
2023 | { |
2024 | auto __lasti = ranges::next(__first, __last); | |
9c24e97a JW |
2025 | _GLIBCXX_STD_A::sort(std::move(__first), __lasti, |
2026 | __detail::__make_comp_proj(__comp, __proj)); | |
b40c57bd PP |
2027 | return __lasti; |
2028 | } | |
2029 | ||
2030 | template<random_access_range _Range, | |
2031 | typename _Comp = ranges::less, typename _Proj = identity> | |
2032 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 2033 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
2034 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
2035 | { | |
2036 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2037 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2038 | } |
2039 | }; | |
2040 | ||
2041 | inline constexpr __sort_fn sort{}; | |
2042 | ||
2043 | struct __stable_sort_fn | |
2044 | { | |
2045 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2046 | typename _Comp = ranges::less, typename _Proj = identity> | |
2047 | requires sortable<_Iter, _Comp, _Proj> | |
2048 | _Iter | |
2049 | operator()(_Iter __first, _Sent __last, | |
55992626 | 2050 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2051 | { |
2052 | auto __lasti = ranges::next(__first, __last); | |
2053 | std::stable_sort(std::move(__first), __lasti, | |
2054 | __detail::__make_comp_proj(__comp, __proj)); | |
2055 | return __lasti; | |
2056 | } | |
2057 | ||
2058 | template<random_access_range _Range, | |
2059 | typename _Comp = ranges::less, typename _Proj = identity> | |
2060 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 2061 | borrowed_iterator_t<_Range> |
b40c57bd PP |
2062 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
2063 | { | |
2064 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2065 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2066 | } |
2067 | }; | |
2068 | ||
2069 | inline constexpr __stable_sort_fn stable_sort{}; | |
2070 | ||
2071 | struct __partial_sort_fn | |
2072 | { | |
2073 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2074 | typename _Comp = ranges::less, typename _Proj = identity> | |
2075 | requires sortable<_Iter, _Comp, _Proj> | |
2076 | constexpr _Iter | |
2077 | operator()(_Iter __first, _Iter __middle, _Sent __last, | |
55992626 | 2078 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2079 | { |
2080 | if (__first == __middle) | |
2081 | return ranges::next(__first, __last); | |
2082 | ||
2083 | ranges::make_heap(__first, __middle, __comp, __proj); | |
2084 | auto __i = __middle; | |
2085 | for (; __i != __last; ++__i) | |
bc464641 | 2086 | if (std::__invoke(__comp, |
b40c57bd PP |
2087 | std::__invoke(__proj, *__i), |
2088 | std::__invoke(__proj, *__first))) | |
bc464641 | 2089 | { |
b40c57bd PP |
2090 | ranges::pop_heap(__first, __middle, __comp, __proj); |
2091 | ranges::iter_swap(__middle-1, __i); | |
2092 | ranges::push_heap(__first, __middle, __comp, __proj); | |
bc464641 | 2093 | } |
b40c57bd PP |
2094 | ranges::sort_heap(__first, __middle, __comp, __proj); |
2095 | ||
2096 | return __i; | |
2097 | } | |
2098 | ||
2099 | template<random_access_range _Range, | |
2100 | typename _Comp = ranges::less, typename _Proj = identity> | |
2101 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 2102 | constexpr borrowed_iterator_t<_Range> |
b40c57bd | 2103 | operator()(_Range&& __r, iterator_t<_Range> __middle, |
55992626 | 2104 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd | 2105 | { |
55992626 PP |
2106 | return (*this)(ranges::begin(__r), std::move(__middle), |
2107 | ranges::end(__r), | |
2108 | std::move(__comp), std::move(__proj)); | |
b40c57bd PP |
2109 | } |
2110 | }; | |
2111 | ||
2112 | inline constexpr __partial_sort_fn partial_sort{}; | |
2113 | ||
2114 | template<typename _Iter, typename _Out> | |
aa667c3f | 2115 | using partial_sort_copy_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
2116 | |
2117 | struct __partial_sort_copy_fn | |
2118 | { | |
2119 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
2120 | random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
2121 | typename _Comp = ranges::less, | |
2122 | typename _Proj1 = identity, typename _Proj2 = identity> | |
2123 | requires indirectly_copyable<_Iter1, _Iter2> | |
2124 | && sortable<_Iter2, _Comp, _Proj2> | |
2125 | && indirect_strict_weak_order<_Comp, | |
2126 | projected<_Iter1, _Proj1>, | |
2127 | projected<_Iter2, _Proj2>> | |
2128 | constexpr partial_sort_copy_result<_Iter1, _Iter2> | |
2129 | operator()(_Iter1 __first, _Sent1 __last, | |
55992626 PP |
2130 | _Iter2 __result_first, _Sent2 __result_last, |
2131 | _Comp __comp = {}, | |
2132 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2133 | { |
2134 | if (__result_first == __result_last) | |
2135 | { | |
2136 | // TODO: Eliminating the variable __lasti triggers an ICE. | |
2137 | auto __lasti = ranges::next(std::move(__first), | |
2138 | std::move(__last)); | |
2139 | return {std::move(__lasti), std::move(__result_first)}; | |
2140 | } | |
2141 | ||
2142 | auto __result_real_last = __result_first; | |
2143 | while (__first != __last && __result_real_last != __result_last) | |
2144 | { | |
2145 | *__result_real_last = *__first; | |
2146 | ++__result_real_last; | |
2147 | ++__first; | |
2148 | } | |
2149 | ||
2150 | ranges::make_heap(__result_first, __result_real_last, __comp, __proj2); | |
2151 | for (; __first != __last; ++__first) | |
2152 | if (std::__invoke(__comp, | |
2153 | std::__invoke(__proj1, *__first), | |
2154 | std::__invoke(__proj2, *__result_first))) | |
bc464641 | 2155 | { |
b40c57bd PP |
2156 | ranges::pop_heap(__result_first, __result_real_last, |
2157 | __comp, __proj2); | |
2158 | *(__result_real_last-1) = *__first; | |
2159 | ranges::push_heap(__result_first, __result_real_last, | |
2160 | __comp, __proj2); | |
bc464641 | 2161 | } |
b40c57bd PP |
2162 | ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2); |
2163 | ||
2164 | return {std::move(__first), std::move(__result_real_last)}; | |
2165 | } | |
2166 | ||
2167 | template<input_range _Range1, random_access_range _Range2, | |
2168 | typename _Comp = ranges::less, | |
2169 | typename _Proj1 = identity, typename _Proj2 = identity> | |
2170 | requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>> | |
2171 | && sortable<iterator_t<_Range2>, _Comp, _Proj2> | |
2172 | && indirect_strict_weak_order<_Comp, | |
2173 | projected<iterator_t<_Range1>, _Proj1>, | |
2174 | projected<iterator_t<_Range2>, _Proj2>> | |
15411a64 JW |
2175 | constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>, |
2176 | borrowed_iterator_t<_Range2>> | |
b40c57bd | 2177 | operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {}, |
55992626 | 2178 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const |
b40c57bd PP |
2179 | { |
2180 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
2181 | ranges::begin(__out), ranges::end(__out), |
2182 | std::move(__comp), | |
2183 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
2184 | } |
2185 | }; | |
2186 | ||
2187 | inline constexpr __partial_sort_copy_fn partial_sort_copy{}; | |
2188 | ||
2189 | struct __is_sorted_until_fn | |
2190 | { | |
2191 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2192 | typename _Proj = identity, | |
2193 | indirect_strict_weak_order<projected<_Iter, _Proj>> | |
2194 | _Comp = ranges::less> | |
2195 | constexpr _Iter | |
2196 | operator()(_Iter __first, _Sent __last, | |
55992626 | 2197 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2198 | { |
2199 | if (__first == __last) | |
2200 | return __first; | |
2201 | ||
2202 | auto __next = __first; | |
2203 | for (++__next; __next != __last; __first = __next, (void)++__next) | |
2204 | if (std::__invoke(__comp, | |
2205 | std::__invoke(__proj, *__next), | |
2206 | std::__invoke(__proj, *__first))) | |
2207 | return __next; | |
2208 | return __next; | |
2209 | } | |
2210 | ||
2211 | template<forward_range _Range, typename _Proj = identity, | |
2212 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
2213 | _Comp = ranges::less> | |
15411a64 | 2214 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
2215 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
2216 | { | |
2217 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2218 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2219 | } |
2220 | }; | |
2221 | ||
2222 | inline constexpr __is_sorted_until_fn is_sorted_until{}; | |
2223 | ||
2224 | struct __is_sorted_fn | |
2225 | { | |
2226 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2227 | typename _Proj = identity, | |
2228 | indirect_strict_weak_order<projected<_Iter, _Proj>> | |
2229 | _Comp = ranges::less> | |
2230 | constexpr bool | |
55992626 PP |
2231 | operator()(_Iter __first, _Sent __last, |
2232 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
2233 | { |
2234 | if (__first == __last) | |
2235 | return true; | |
2236 | ||
2237 | auto __next = __first; | |
2238 | for (++__next; __next != __last; __first = __next, (void)++__next) | |
2239 | if (std::__invoke(__comp, | |
2240 | std::__invoke(__proj, *__next), | |
2241 | std::__invoke(__proj, *__first))) | |
2242 | return false; | |
2243 | return true; | |
2244 | } | |
2245 | ||
2246 | template<forward_range _Range, typename _Proj = identity, | |
2247 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
2248 | _Comp = ranges::less> | |
2249 | constexpr bool | |
2250 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const | |
2251 | { | |
2252 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2253 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2254 | } |
2255 | }; | |
2256 | ||
2257 | inline constexpr __is_sorted_fn is_sorted{}; | |
2258 | ||
2259 | struct __nth_element_fn | |
2260 | { | |
2261 | template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2262 | typename _Comp = ranges::less, typename _Proj = identity> | |
2263 | requires sortable<_Iter, _Comp, _Proj> | |
2264 | constexpr _Iter | |
2265 | operator()(_Iter __first, _Iter __nth, _Sent __last, | |
55992626 | 2266 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2267 | { |
2268 | auto __lasti = ranges::next(__first, __last); | |
9c24e97a JW |
2269 | _GLIBCXX_STD_A::nth_element(std::move(__first), std::move(__nth), |
2270 | __lasti, | |
2271 | __detail::__make_comp_proj(__comp, __proj)); | |
b40c57bd PP |
2272 | return __lasti; |
2273 | } | |
2274 | ||
2275 | template<random_access_range _Range, | |
2276 | typename _Comp = ranges::less, typename _Proj = identity> | |
2277 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 2278 | constexpr borrowed_iterator_t<_Range> |
b40c57bd | 2279 | operator()(_Range&& __r, iterator_t<_Range> __nth, |
55992626 | 2280 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2281 | { |
2282 | return (*this)(ranges::begin(__r), std::move(__nth), | |
55992626 | 2283 | ranges::end(__r), std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2284 | } |
2285 | }; | |
2286 | ||
2287 | inline constexpr __nth_element_fn nth_element{}; | |
2288 | ||
2289 | struct __lower_bound_fn | |
2290 | { | |
2291 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2292 | typename _Tp, typename _Proj = identity, | |
2293 | indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> | |
2294 | _Comp = ranges::less> | |
2295 | constexpr _Iter | |
2296 | operator()(_Iter __first, _Sent __last, | |
55992626 | 2297 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2298 | { |
2299 | auto __len = ranges::distance(__first, __last); | |
2300 | ||
2301 | while (__len > 0) | |
2302 | { | |
2303 | auto __half = __len / 2; | |
2304 | auto __middle = __first; | |
2305 | ranges::advance(__middle, __half); | |
2306 | if (std::__invoke(__comp, std::__invoke(__proj, *__middle), __value)) | |
2307 | { | |
2308 | __first = __middle; | |
2309 | ++__first; | |
2310 | __len = __len - __half - 1; | |
2311 | } | |
2312 | else | |
2313 | __len = __half; | |
2314 | } | |
2315 | return __first; | |
2316 | } | |
2317 | ||
2318 | template<forward_range _Range, typename _Tp, typename _Proj = identity, | |
2319 | indirect_strict_weak_order<const _Tp*, | |
2320 | projected<iterator_t<_Range>, _Proj>> | |
2321 | _Comp = ranges::less> | |
15411a64 | 2322 | constexpr borrowed_iterator_t<_Range> |
b40c57bd | 2323 | operator()(_Range&& __r, |
55992626 | 2324 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2325 | { |
2326 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2327 | __value, std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2328 | } |
2329 | }; | |
2330 | ||
2331 | inline constexpr __lower_bound_fn lower_bound{}; | |
2332 | ||
2333 | struct __upper_bound_fn | |
2334 | { | |
2335 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2336 | typename _Tp, typename _Proj = identity, | |
2337 | indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> | |
2338 | _Comp = ranges::less> | |
2339 | constexpr _Iter | |
2340 | operator()(_Iter __first, _Sent __last, | |
55992626 | 2341 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2342 | { |
2343 | auto __len = ranges::distance(__first, __last); | |
2344 | ||
2345 | while (__len > 0) | |
2346 | { | |
2347 | auto __half = __len / 2; | |
2348 | auto __middle = __first; | |
2349 | ranges::advance(__middle, __half); | |
2350 | if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle))) | |
2351 | __len = __half; | |
2352 | else | |
2353 | { | |
2354 | __first = __middle; | |
2355 | ++__first; | |
2356 | __len = __len - __half - 1; | |
2357 | } | |
2358 | } | |
2359 | return __first; | |
2360 | } | |
2361 | ||
2362 | template<forward_range _Range, typename _Tp, typename _Proj = identity, | |
2363 | indirect_strict_weak_order<const _Tp*, | |
2364 | projected<iterator_t<_Range>, _Proj>> | |
2365 | _Comp = ranges::less> | |
15411a64 | 2366 | constexpr borrowed_iterator_t<_Range> |
b40c57bd | 2367 | operator()(_Range&& __r, |
55992626 | 2368 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2369 | { |
2370 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2371 | __value, std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2372 | } |
2373 | }; | |
bc464641 | 2374 | |
b40c57bd | 2375 | inline constexpr __upper_bound_fn upper_bound{}; |
bc464641 | 2376 | |
b40c57bd PP |
2377 | struct __equal_range_fn |
2378 | { | |
2379 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2380 | typename _Tp, typename _Proj = identity, | |
2381 | indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> | |
2382 | _Comp = ranges::less> | |
2383 | constexpr subrange<_Iter> | |
2384 | operator()(_Iter __first, _Sent __last, | |
55992626 | 2385 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2386 | { |
2387 | auto __len = ranges::distance(__first, __last); | |
bc464641 | 2388 | |
b40c57bd PP |
2389 | while (__len > 0) |
2390 | { | |
2391 | auto __half = __len / 2; | |
2392 | auto __middle = __first; | |
2393 | ranges::advance(__middle, __half); | |
2394 | if (std::__invoke(__comp, | |
2395 | std::__invoke(__proj, *__middle), | |
2396 | __value)) | |
bc464641 | 2397 | { |
b40c57bd | 2398 | __first = __middle; |
bc464641 | 2399 | ++__first; |
b40c57bd PP |
2400 | __len = __len - __half - 1; |
2401 | } | |
2402 | else if (std::__invoke(__comp, | |
2403 | __value, | |
2404 | std::__invoke(__proj, *__middle))) | |
2405 | __len = __half; | |
2406 | else | |
2407 | { | |
2408 | auto __left | |
2409 | = ranges::lower_bound(__first, __middle, | |
2410 | __value, __comp, __proj); | |
2411 | ranges::advance(__first, __len); | |
2412 | auto __right | |
2413 | = ranges::upper_bound(++__middle, __first, | |
2414 | __value, __comp, __proj); | |
2415 | return {__left, __right}; | |
bc464641 | 2416 | } |
b40c57bd PP |
2417 | } |
2418 | return {__first, __first}; | |
2419 | } | |
bc464641 | 2420 | |
b40c57bd PP |
2421 | template<forward_range _Range, |
2422 | typename _Tp, typename _Proj = identity, | |
2423 | indirect_strict_weak_order<const _Tp*, | |
2424 | projected<iterator_t<_Range>, _Proj>> | |
2425 | _Comp = ranges::less> | |
15411a64 | 2426 | constexpr borrowed_subrange_t<_Range> |
b40c57bd | 2427 | operator()(_Range&& __r, const _Tp& __value, |
55992626 | 2428 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2429 | { |
2430 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2431 | __value, std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2432 | } |
2433 | }; | |
bc464641 | 2434 | |
b40c57bd PP |
2435 | inline constexpr __equal_range_fn equal_range{}; |
2436 | ||
2437 | struct __binary_search_fn | |
2438 | { | |
2439 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2440 | typename _Tp, typename _Proj = identity, | |
2441 | indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> | |
2442 | _Comp = ranges::less> | |
2443 | constexpr bool | |
2444 | operator()(_Iter __first, _Sent __last, | |
55992626 | 2445 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2446 | { |
2447 | auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj); | |
2448 | if (__i == __last) | |
2449 | return false; | |
55992626 PP |
2450 | return !(bool)std::__invoke(__comp, __value, |
2451 | std::__invoke(__proj, *__i)); | |
b40c57bd PP |
2452 | } |
2453 | ||
2454 | template<forward_range _Range, | |
2455 | typename _Tp, typename _Proj = identity, | |
2456 | indirect_strict_weak_order<const _Tp*, | |
2457 | projected<iterator_t<_Range>, _Proj>> | |
2458 | _Comp = ranges::less> | |
2459 | constexpr bool | |
2460 | operator()(_Range&& __r, const _Tp& __value, _Comp __comp = {}, | |
55992626 | 2461 | _Proj __proj = {}) const |
b40c57bd PP |
2462 | { |
2463 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2464 | __value, std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2465 | } |
2466 | }; | |
2467 | ||
2468 | inline constexpr __binary_search_fn binary_search{}; | |
2469 | ||
2470 | struct __is_partitioned_fn | |
2471 | { | |
2472 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2473 | typename _Proj = identity, | |
2474 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
2475 | constexpr bool | |
55992626 PP |
2476 | operator()(_Iter __first, _Sent __last, |
2477 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd | 2478 | { |
55992626 PP |
2479 | __first = ranges::find_if_not(std::move(__first), __last, |
2480 | __pred, __proj); | |
b40c57bd PP |
2481 | if (__first == __last) |
2482 | return true; | |
2483 | ++__first; | |
2484 | return ranges::none_of(std::move(__first), std::move(__last), | |
bc464641 | 2485 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
2486 | } |
2487 | ||
2488 | template<input_range _Range, typename _Proj = identity, | |
55992626 PP |
2489 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
2490 | _Pred> | |
b40c57bd PP |
2491 | constexpr bool |
2492 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
2493 | { | |
2494 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2495 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
2496 | } |
2497 | }; | |
2498 | ||
2499 | inline constexpr __is_partitioned_fn is_partitioned{}; | |
2500 | ||
2501 | struct __partition_fn | |
2502 | { | |
2503 | template<permutable _Iter, sentinel_for<_Iter> _Sent, | |
2504 | typename _Proj = identity, | |
2505 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
2506 | constexpr subrange<_Iter> | |
55992626 PP |
2507 | operator()(_Iter __first, _Sent __last, |
2508 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
2509 | { |
2510 | if constexpr (bidirectional_iterator<_Iter>) | |
2511 | { | |
2512 | auto __lasti = ranges::next(__first, __last); | |
2513 | auto __tail = __lasti; | |
2514 | for (;;) | |
2515 | { | |
2516 | for (;;) | |
2517 | if (__first == __tail) | |
2518 | return {std::move(__first), std::move(__lasti)}; | |
55992626 PP |
2519 | else if (std::__invoke(__pred, |
2520 | std::__invoke(__proj, *__first))) | |
b40c57bd PP |
2521 | ++__first; |
2522 | else | |
2523 | break; | |
2524 | --__tail; | |
2525 | for (;;) | |
2526 | if (__first == __tail) | |
2527 | return {std::move(__first), std::move(__lasti)}; | |
2528 | else if (!(bool)std::__invoke(__pred, | |
2529 | std::__invoke(__proj, *__tail))) | |
2530 | --__tail; | |
2531 | else | |
2532 | break; | |
2533 | ranges::iter_swap(__first, __tail); | |
2534 | ++__first; | |
2535 | } | |
2536 | } | |
2537 | else | |
2538 | { | |
2539 | if (__first == __last) | |
2540 | return {std::move(__first), std::move(__first)}; | |
2541 | ||
2542 | while (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
2543 | if (++__first == __last) | |
2544 | return {std::move(__first), std::move(__first)}; | |
2545 | ||
2546 | auto __next = __first; | |
2547 | while (++__next != __last) | |
2548 | if (std::__invoke(__pred, std::__invoke(__proj, *__next))) | |
2549 | { | |
2550 | ranges::iter_swap(__first, __next); | |
2551 | ++__first; | |
2552 | } | |
2553 | ||
2554 | return {std::move(__first), std::move(__next)}; | |
2555 | } | |
2556 | } | |
2557 | ||
2558 | template<forward_range _Range, typename _Proj = identity, | |
55992626 PP |
2559 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
2560 | _Pred> | |
b40c57bd | 2561 | requires permutable<iterator_t<_Range>> |
15411a64 | 2562 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
2563 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const |
2564 | { | |
2565 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2566 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
2567 | } |
2568 | }; | |
2569 | ||
2570 | inline constexpr __partition_fn partition{}; | |
2571 | ||
2572 | struct __stable_partition_fn | |
2573 | { | |
2574 | template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2575 | typename _Proj = identity, | |
2576 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
2577 | requires permutable<_Iter> | |
2578 | subrange<_Iter> | |
55992626 PP |
2579 | operator()(_Iter __first, _Sent __last, |
2580 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
2581 | { |
2582 | auto __lasti = ranges::next(__first, __last); | |
2583 | auto __middle | |
2584 | = std::stable_partition(std::move(__first), __lasti, | |
2585 | __detail::__make_pred_proj(__pred, __proj)); | |
2586 | return {std::move(__middle), std::move(__lasti)}; | |
2587 | } | |
2588 | ||
2589 | template<bidirectional_range _Range, typename _Proj = identity, | |
55992626 PP |
2590 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
2591 | _Pred> | |
b40c57bd | 2592 | requires permutable<iterator_t<_Range>> |
15411a64 | 2593 | borrowed_subrange_t<_Range> |
b40c57bd PP |
2594 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const |
2595 | { | |
2596 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2597 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
2598 | } |
2599 | }; | |
2600 | ||
2601 | inline constexpr __stable_partition_fn stable_partition{}; | |
bc464641 | 2602 | |
aa667c3f PP |
2603 | template<typename _Iter, typename _Out1, typename _Out2> |
2604 | struct in_out_out_result | |
bc464641 PP |
2605 | { |
2606 | [[no_unique_address]] _Iter in; | |
2607 | [[no_unique_address]] _Out1 out1; | |
aa667c3f | 2608 | [[no_unique_address]] _Out2 out2; |
bc464641 PP |
2609 | |
2610 | template<typename _IIter, typename _OOut1, typename _OOut2> | |
2611 | requires convertible_to<const _Iter&, _IIter> | |
2612 | && convertible_to<const _Out1&, _OOut1> | |
aa667c3f PP |
2613 | && convertible_to<const _Out2&, _OOut2> |
2614 | constexpr | |
2615 | operator in_out_out_result<_IIter, _OOut1, _OOut2>() const & | |
bc464641 PP |
2616 | { return {in, out1, out2}; } |
2617 | ||
2618 | template<typename _IIter, typename _OOut1, typename _OOut2> | |
2619 | requires convertible_to<_Iter, _IIter> | |
2620 | && convertible_to<_Out1, _OOut1> | |
aa667c3f PP |
2621 | && convertible_to<_Out2, _OOut2> |
2622 | constexpr | |
2623 | operator in_out_out_result<_IIter, _OOut1, _OOut2>() && | |
bc464641 PP |
2624 | { return {std::move(in), std::move(out1), std::move(out2)}; } |
2625 | }; | |
2626 | ||
aa667c3f PP |
2627 | template<typename _Iter, typename _Out1, typename _Out2> |
2628 | using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>; | |
2629 | ||
b40c57bd PP |
2630 | struct __partition_copy_fn |
2631 | { | |
2632 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2633 | weakly_incrementable _Out1, weakly_incrementable _O2, | |
2634 | typename _Proj = identity, | |
2635 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
2636 | requires indirectly_copyable<_Iter, _Out1> | |
2637 | && indirectly_copyable<_Iter, _O2> | |
2638 | constexpr partition_copy_result<_Iter, _Out1, _O2> | |
2639 | operator()(_Iter __first, _Sent __last, | |
55992626 PP |
2640 | _Out1 __out_true, _O2 __out_false, |
2641 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
2642 | { |
2643 | for (; __first != __last; ++__first) | |
2644 | if (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
2645 | { | |
2646 | *__out_true = *__first; | |
2647 | ++__out_true; | |
2648 | } | |
2649 | else | |
2650 | { | |
2651 | *__out_false = *__first; | |
2652 | ++__out_false; | |
2653 | } | |
2654 | ||
55992626 PP |
2655 | return {std::move(__first), |
2656 | std::move(__out_true), std::move(__out_false)}; | |
b40c57bd PP |
2657 | } |
2658 | ||
2659 | template<input_range _Range, weakly_incrementable _Out1, | |
2660 | weakly_incrementable _O2, | |
2661 | typename _Proj = identity, | |
55992626 PP |
2662 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
2663 | _Pred> | |
b40c57bd PP |
2664 | requires indirectly_copyable<iterator_t<_Range>, _Out1> |
2665 | && indirectly_copyable<iterator_t<_Range>, _O2> | |
15411a64 | 2666 | constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _O2> |
b40c57bd | 2667 | operator()(_Range&& __r, _Out1 out_true, _O2 out_false, |
55992626 | 2668 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
2669 | { |
2670 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
2671 | std::move(out_true), std::move(out_false), |
2672 | std::move(__pred), std::move(__proj)); | |
b40c57bd PP |
2673 | } |
2674 | }; | |
2675 | ||
2676 | inline constexpr __partition_copy_fn partition_copy{}; | |
2677 | ||
2678 | struct __partition_point_fn | |
2679 | { | |
2680 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2681 | typename _Proj = identity, | |
2682 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
2683 | constexpr _Iter | |
2684 | operator()(_Iter __first, _Sent __last, | |
55992626 | 2685 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
2686 | { |
2687 | auto __len = ranges::distance(__first, __last); | |
2688 | ||
2689 | while (__len > 0) | |
bc464641 | 2690 | { |
b40c57bd PP |
2691 | auto __half = __len / 2; |
2692 | auto __middle = __first; | |
2693 | ranges::advance(__middle, __half); | |
2694 | if (std::__invoke(__pred, std::__invoke(__proj, *__middle))) | |
2695 | { | |
2696 | __first = __middle; | |
2697 | ++__first; | |
2698 | __len = __len - __half - 1; | |
2699 | } | |
2700 | else | |
2701 | __len = __half; | |
bc464641 | 2702 | } |
b40c57bd PP |
2703 | return __first; |
2704 | } | |
2705 | ||
2706 | template<forward_range _Range, typename _Proj = identity, | |
55992626 PP |
2707 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
2708 | _Pred> | |
15411a64 | 2709 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
2710 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const |
2711 | { | |
2712 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2713 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
2714 | } |
2715 | }; | |
2716 | ||
2717 | inline constexpr __partition_point_fn partition_point{}; | |
2718 | ||
2719 | template<typename _Iter1, typename _Iter2, typename _Out> | |
aa667c3f | 2720 | using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>; |
b40c57bd PP |
2721 | |
2722 | struct __merge_fn | |
2723 | { | |
2724 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
2725 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
2726 | weakly_incrementable _Out, typename _Comp = ranges::less, | |
2727 | typename _Proj1 = identity, typename _Proj2 = identity> | |
2728 | requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> | |
2729 | constexpr merge_result<_Iter1, _Iter2, _Out> | |
2730 | operator()(_Iter1 __first1, _Sent1 __last1, | |
55992626 PP |
2731 | _Iter2 __first2, _Sent2 __last2, _Out __result, |
2732 | _Comp __comp = {}, | |
2733 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2734 | { |
2735 | while (__first1 != __last1 && __first2 != __last2) | |
bc464641 | 2736 | { |
b40c57bd PP |
2737 | if (std::__invoke(__comp, |
2738 | std::__invoke(__proj2, *__first2), | |
2739 | std::__invoke(__proj1, *__first1))) | |
2740 | { | |
2741 | *__result = *__first2; | |
2742 | ++__first2; | |
2743 | } | |
2744 | else | |
2745 | { | |
2746 | *__result = *__first1; | |
2747 | ++__first1; | |
2748 | } | |
2749 | ++__result; | |
bc464641 | 2750 | } |
b40c57bd PP |
2751 | auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1), |
2752 | std::move(__result)); | |
2753 | auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2), | |
2754 | std::move(__copy1.out)); | |
2755 | return { std::move(__copy1.in), std::move(__copy2.in), | |
2756 | std::move(__copy2.out) }; | |
2757 | } | |
bc464641 | 2758 | |
b40c57bd PP |
2759 | template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, |
2760 | typename _Comp = ranges::less, | |
2761 | typename _Proj1 = identity, typename _Proj2 = identity> | |
2762 | requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, | |
2763 | _Comp, _Proj1, _Proj2> | |
15411a64 JW |
2764 | constexpr merge_result<borrowed_iterator_t<_Range1>, |
2765 | borrowed_iterator_t<_Range2>, | |
b40c57bd PP |
2766 | _Out> |
2767 | operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, | |
55992626 PP |
2768 | _Comp __comp = {}, |
2769 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2770 | { |
2771 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
2772 | ranges::begin(__r2), ranges::end(__r2), |
2773 | std::move(__result), std::move(__comp), | |
2774 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
2775 | } |
2776 | }; | |
bc464641 | 2777 | |
b40c57bd | 2778 | inline constexpr __merge_fn merge{}; |
bc464641 | 2779 | |
b40c57bd PP |
2780 | struct __inplace_merge_fn |
2781 | { | |
2782 | template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
2783 | typename _Comp = ranges::less, | |
2784 | typename _Proj = identity> | |
2785 | requires sortable<_Iter, _Comp, _Proj> | |
2786 | _Iter | |
2787 | operator()(_Iter __first, _Iter __middle, _Sent __last, | |
55992626 | 2788 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2789 | { |
2790 | auto __lasti = ranges::next(__first, __last); | |
2791 | std::inplace_merge(std::move(__first), std::move(__middle), __lasti, | |
2792 | __detail::__make_comp_proj(__comp, __proj)); | |
2793 | return __lasti; | |
2794 | } | |
bc464641 | 2795 | |
b40c57bd PP |
2796 | template<bidirectional_range _Range, |
2797 | typename _Comp = ranges::less, typename _Proj = identity> | |
2798 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 2799 | borrowed_iterator_t<_Range> |
b40c57bd | 2800 | operator()(_Range&& __r, iterator_t<_Range> __middle, |
55992626 | 2801 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2802 | { |
2803 | return (*this)(ranges::begin(__r), std::move(__middle), | |
55992626 PP |
2804 | ranges::end(__r), |
2805 | std::move(__comp), std::move(__proj)); | |
b40c57bd PP |
2806 | } |
2807 | }; | |
bc464641 | 2808 | |
b40c57bd PP |
2809 | inline constexpr __inplace_merge_fn inplace_merge{}; |
2810 | ||
2811 | struct __includes_fn | |
2812 | { | |
2813 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
2814 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
2815 | typename _Proj1 = identity, typename _Proj2 = identity, | |
2816 | indirect_strict_weak_order<projected<_Iter1, _Proj1>, | |
2817 | projected<_Iter2, _Proj2>> | |
2818 | _Comp = ranges::less> | |
2819 | constexpr bool | |
55992626 PP |
2820 | operator()(_Iter1 __first1, _Sent1 __last1, |
2821 | _Iter2 __first2, _Sent2 __last2, | |
2822 | _Comp __comp = {}, | |
2823 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2824 | { |
2825 | while (__first1 != __last1 && __first2 != __last2) | |
bc464641 PP |
2826 | if (std::__invoke(__comp, |
2827 | std::__invoke(__proj2, *__first2), | |
2828 | std::__invoke(__proj1, *__first1))) | |
b40c57bd PP |
2829 | return false; |
2830 | else if (std::__invoke(__comp, | |
2831 | std::__invoke(__proj1, *__first1), | |
2832 | std::__invoke(__proj2, *__first2))) | |
2833 | ++__first1; | |
2834 | else | |
bc464641 | 2835 | { |
b40c57bd | 2836 | ++__first1; |
bc464641 PP |
2837 | ++__first2; |
2838 | } | |
b40c57bd PP |
2839 | |
2840 | return __first2 == __last2; | |
2841 | } | |
2842 | ||
55992626 PP |
2843 | template<input_range _Range1, input_range _Range2, |
2844 | typename _Proj1 = identity, typename _Proj2 = identity, | |
b40c57bd PP |
2845 | indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>, |
2846 | projected<iterator_t<_Range2>, _Proj2>> | |
2847 | _Comp = ranges::less> | |
2848 | constexpr bool | |
2849 | operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {}, | |
55992626 | 2850 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const |
b40c57bd PP |
2851 | { |
2852 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
2853 | ranges::begin(__r2), ranges::end(__r2), |
2854 | std::move(__comp), | |
2855 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
2856 | } |
2857 | }; | |
2858 | ||
2859 | inline constexpr __includes_fn includes{}; | |
2860 | ||
2861 | template<typename _Iter1, typename _Iter2, typename _Out> | |
aa667c3f | 2862 | using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>; |
b40c57bd PP |
2863 | |
2864 | struct __set_union_fn | |
2865 | { | |
2866 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
2867 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
2868 | weakly_incrementable _Out, typename _Comp = ranges::less, | |
2869 | typename _Proj1 = identity, typename _Proj2 = identity> | |
2870 | requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> | |
2871 | constexpr set_union_result<_Iter1, _Iter2, _Out> | |
55992626 PP |
2872 | operator()(_Iter1 __first1, _Sent1 __last1, |
2873 | _Iter2 __first2, _Sent2 __last2, | |
2874 | _Out __result, _Comp __comp = {}, | |
2875 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2876 | { |
2877 | while (__first1 != __last1 && __first2 != __last2) | |
2878 | { | |
2879 | if (std::__invoke(__comp, | |
2880 | std::__invoke(__proj1, *__first1), | |
2881 | std::__invoke(__proj2, *__first2))) | |
2882 | { | |
2883 | *__result = *__first1; | |
2884 | ++__first1; | |
2885 | } | |
2886 | else if (std::__invoke(__comp, | |
2887 | std::__invoke(__proj2, *__first2), | |
2888 | std::__invoke(__proj1, *__first1))) | |
2889 | { | |
2890 | *__result = *__first2; | |
2891 | ++__first2; | |
2892 | } | |
2893 | else | |
2894 | { | |
2895 | *__result = *__first1; | |
2896 | ++__first1; | |
2897 | ++__first2; | |
2898 | } | |
2899 | ++__result; | |
2900 | } | |
2901 | auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1), | |
2902 | std::move(__result)); | |
2903 | auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2), | |
2904 | std::move(__copy1.out)); | |
2905 | return {std::move(__copy1.in), std::move(__copy2.in), | |
2906 | std::move(__copy2.out)}; | |
2907 | } | |
2908 | ||
2909 | template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, | |
2910 | typename _Comp = ranges::less, | |
2911 | typename _Proj1 = identity, typename _Proj2 = identity> | |
2912 | requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, | |
2913 | _Comp, _Proj1, _Proj2> | |
15411a64 JW |
2914 | constexpr set_union_result<borrowed_iterator_t<_Range1>, |
2915 | borrowed_iterator_t<_Range2>, _Out> | |
55992626 PP |
2916 | operator()(_Range1&& __r1, _Range2&& __r2, |
2917 | _Out __result, _Comp __comp = {}, | |
2918 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2919 | { |
2920 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
2921 | ranges::begin(__r2), ranges::end(__r2), |
2922 | std::move(__result), std::move(__comp), | |
2923 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
2924 | } |
2925 | }; | |
2926 | ||
2927 | inline constexpr __set_union_fn set_union{}; | |
2928 | ||
2929 | template<typename _Iter1, typename _Iter2, typename _Out> | |
aa667c3f | 2930 | using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>; |
b40c57bd PP |
2931 | |
2932 | struct __set_intersection_fn | |
2933 | { | |
2934 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
2935 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
2936 | weakly_incrementable _Out, typename _Comp = ranges::less, | |
2937 | typename _Proj1 = identity, typename _Proj2 = identity> | |
2938 | requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> | |
2939 | constexpr set_intersection_result<_Iter1, _Iter2, _Out> | |
2940 | operator()(_Iter1 __first1, _Sent1 __last1, | |
55992626 PP |
2941 | _Iter2 __first2, _Sent2 __last2, _Out __result, |
2942 | _Comp __comp = {}, | |
2943 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2944 | { |
2945 | while (__first1 != __last1 && __first2 != __last2) | |
2946 | if (std::__invoke(__comp, | |
2947 | std::__invoke(__proj1, *__first1), | |
2948 | std::__invoke(__proj2, *__first2))) | |
2949 | ++__first1; | |
2950 | else if (std::__invoke(__comp, | |
2951 | std::__invoke(__proj2, *__first2), | |
2952 | std::__invoke(__proj1, *__first1))) | |
2953 | ++__first2; | |
bc464641 PP |
2954 | else |
2955 | { | |
2956 | *__result = *__first1; | |
2957 | ++__first1; | |
b40c57bd PP |
2958 | ++__first2; |
2959 | ++__result; | |
bc464641 | 2960 | } |
b40c57bd PP |
2961 | // TODO: Eliminating these variables triggers an ICE. |
2962 | auto __last1i = ranges::next(std::move(__first1), std::move(__last1)); | |
2963 | auto __last2i = ranges::next(std::move(__first2), std::move(__last2)); | |
2964 | return {std::move(__last1i), std::move(__last2i), std::move(__result)}; | |
2965 | } | |
bc464641 | 2966 | |
b40c57bd PP |
2967 | template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, |
2968 | typename _Comp = ranges::less, | |
2969 | typename _Proj1 = identity, typename _Proj2 = identity> | |
2970 | requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, | |
2971 | _Comp, _Proj1, _Proj2> | |
15411a64 JW |
2972 | constexpr set_intersection_result<borrowed_iterator_t<_Range1>, |
2973 | borrowed_iterator_t<_Range2>, _Out> | |
b40c57bd | 2974 | operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, |
55992626 PP |
2975 | _Comp __comp = {}, |
2976 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2977 | { |
2978 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
2979 | ranges::begin(__r2), ranges::end(__r2), |
2980 | std::move(__result), std::move(__comp), | |
2981 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
2982 | } |
2983 | }; | |
2984 | ||
2985 | inline constexpr __set_intersection_fn set_intersection{}; | |
2986 | ||
2987 | template<typename _Iter, typename _Out> | |
aa667c3f | 2988 | using set_difference_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
2989 | |
2990 | struct __set_difference_fn | |
2991 | { | |
2992 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
2993 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
2994 | weakly_incrementable _Out, typename _Comp = ranges::less, | |
2995 | typename _Proj1 = identity, typename _Proj2 = identity> | |
2996 | requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> | |
2997 | constexpr set_difference_result<_Iter1, _Out> | |
2998 | operator()(_Iter1 __first1, _Sent1 __last1, | |
55992626 PP |
2999 | _Iter2 __first2, _Sent2 __last2, _Out __result, |
3000 | _Comp __comp = {}, | |
3001 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
3002 | { |
3003 | while (__first1 != __last1 && __first2 != __last2) | |
3004 | if (std::__invoke(__comp, | |
3005 | std::__invoke(__proj1, *__first1), | |
3006 | std::__invoke(__proj2, *__first2))) | |
3007 | { | |
3008 | *__result = *__first1; | |
3009 | ++__first1; | |
3010 | ++__result; | |
3011 | } | |
3012 | else if (std::__invoke(__comp, | |
3013 | std::__invoke(__proj2, *__first2), | |
3014 | std::__invoke(__proj1, *__first1))) | |
bc464641 | 3015 | ++__first2; |
b40c57bd PP |
3016 | else |
3017 | { | |
3018 | ++__first1; | |
3019 | ++__first2; | |
3020 | } | |
3021 | return ranges::copy(std::move(__first1), std::move(__last1), | |
3022 | std::move(__result)); | |
3023 | } | |
bc464641 | 3024 | |
b40c57bd PP |
3025 | template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, |
3026 | typename _Comp = ranges::less, | |
3027 | typename _Proj1 = identity, typename _Proj2 = identity> | |
3028 | requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, | |
3029 | _Comp, _Proj1, _Proj2> | |
15411a64 | 3030 | constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out> |
b40c57bd | 3031 | operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, |
55992626 PP |
3032 | _Comp __comp = {}, |
3033 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
3034 | { |
3035 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
3036 | ranges::begin(__r2), ranges::end(__r2), |
3037 | std::move(__result), std::move(__comp), | |
3038 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
3039 | } |
3040 | }; | |
bc464641 | 3041 | |
b40c57bd | 3042 | inline constexpr __set_difference_fn set_difference{}; |
bc464641 PP |
3043 | |
3044 | template<typename _Iter1, typename _Iter2, typename _Out> | |
b40c57bd | 3045 | using set_symmetric_difference_result |
aa667c3f | 3046 | = in_in_out_result<_Iter1, _Iter2, _Out>; |
bc464641 | 3047 | |
b40c57bd PP |
3048 | struct __set_symmetric_difference_fn |
3049 | { | |
3050 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
3051 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
3052 | weakly_incrementable _Out, typename _Comp = ranges::less, | |
3053 | typename _Proj1 = identity, typename _Proj2 = identity> | |
3054 | requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2> | |
3055 | constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out> | |
3056 | operator()(_Iter1 __first1, _Sent1 __last1, | |
55992626 PP |
3057 | _Iter2 __first2, _Sent2 __last2, |
3058 | _Out __result, _Comp __comp = {}, | |
3059 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
3060 | { |
3061 | while (__first1 != __last1 && __first2 != __last2) | |
bc464641 PP |
3062 | if (std::__invoke(__comp, |
3063 | std::__invoke(__proj1, *__first1), | |
3064 | std::__invoke(__proj2, *__first2))) | |
3065 | { | |
3066 | *__result = *__first1; | |
3067 | ++__first1; | |
b40c57bd | 3068 | ++__result; |
bc464641 PP |
3069 | } |
3070 | else if (std::__invoke(__comp, | |
3071 | std::__invoke(__proj2, *__first2), | |
3072 | std::__invoke(__proj1, *__first1))) | |
3073 | { | |
3074 | *__result = *__first2; | |
3075 | ++__first2; | |
b40c57bd | 3076 | ++__result; |
bc464641 PP |
3077 | } |
3078 | else | |
3079 | { | |
bc464641 PP |
3080 | ++__first1; |
3081 | ++__first2; | |
3082 | } | |
b40c57bd PP |
3083 | auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1), |
3084 | std::move(__result)); | |
3085 | auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2), | |
3086 | std::move(__copy1.out)); | |
3087 | return {std::move(__copy1.in), std::move(__copy2.in), | |
3088 | std::move(__copy2.out)}; | |
3089 | } | |
bc464641 | 3090 | |
b40c57bd PP |
3091 | template<input_range _Range1, input_range _Range2, weakly_incrementable _Out, |
3092 | typename _Comp = ranges::less, | |
3093 | typename _Proj1 = identity, typename _Proj2 = identity> | |
3094 | requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out, | |
3095 | _Comp, _Proj1, _Proj2> | |
15411a64 JW |
3096 | constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>, |
3097 | borrowed_iterator_t<_Range2>, | |
b40c57bd PP |
3098 | _Out> |
3099 | operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, | |
55992626 PP |
3100 | _Comp __comp = {}, |
3101 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd | 3102 | { |
55992626 PP |
3103 | return (*this)(ranges::begin(__r1), ranges::end(__r1), |
3104 | ranges::begin(__r2), ranges::end(__r2), | |
3105 | std::move(__result), std::move(__comp), | |
3106 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
3107 | } |
3108 | }; | |
bc464641 | 3109 | |
b40c57bd PP |
3110 | inline constexpr __set_symmetric_difference_fn set_symmetric_difference{}; |
3111 | ||
3112 | struct __min_fn | |
3113 | { | |
3114 | template<typename _Tp, typename _Proj = identity, | |
3115 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
3116 | _Comp = ranges::less> | |
3117 | constexpr const _Tp& | |
55992626 PP |
3118 | operator()(const _Tp& __a, const _Tp& __b, |
3119 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
3120 | { |
3121 | if (std::__invoke(std::move(__comp), | |
3122 | std::__invoke(__proj, __b), | |
3123 | std::__invoke(__proj, __a))) | |
3124 | return __b; | |
bc464641 | 3125 | else |
b40c57bd PP |
3126 | return __a; |
3127 | } | |
3128 | ||
3129 | template<input_range _Range, typename _Proj = identity, | |
3130 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
3131 | _Comp = ranges::less> | |
3132 | requires indirectly_copyable_storable<iterator_t<_Range>, | |
3133 | range_value_t<_Range>*> | |
3134 | constexpr range_value_t<_Range> | |
3135 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const | |
3136 | { | |
3137 | auto __first = ranges::begin(__r); | |
3138 | auto __last = ranges::end(__r); | |
3139 | __glibcxx_assert(__first != __last); | |
3140 | auto __result = *__first; | |
3141 | while (++__first != __last) | |
bc464641 | 3142 | { |
b40c57bd PP |
3143 | auto __tmp = *__first; |
3144 | if (std::__invoke(__comp, | |
3145 | std::__invoke(__proj, __tmp), | |
3146 | std::__invoke(__proj, __result))) | |
3147 | __result = std::move(__tmp); | |
bc464641 | 3148 | } |
b40c57bd PP |
3149 | return __result; |
3150 | } | |
bc464641 | 3151 | |
b40c57bd PP |
3152 | template<copyable _Tp, typename _Proj = identity, |
3153 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
3154 | _Comp = ranges::less> | |
3155 | constexpr _Tp | |
55992626 PP |
3156 | operator()(initializer_list<_Tp> __r, |
3157 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
3158 | { |
3159 | return (*this)(ranges::subrange(__r), | |
55992626 | 3160 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3161 | } |
3162 | }; | |
bc464641 | 3163 | |
b40c57bd PP |
3164 | inline constexpr __min_fn min{}; |
3165 | ||
3166 | struct __max_fn | |
3167 | { | |
3168 | template<typename _Tp, typename _Proj = identity, | |
3169 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
3170 | _Comp = ranges::less> | |
3171 | constexpr const _Tp& | |
55992626 PP |
3172 | operator()(const _Tp& __a, const _Tp& __b, |
3173 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
3174 | { |
3175 | if (std::__invoke(std::move(__comp), | |
3176 | std::__invoke(__proj, __a), | |
3177 | std::__invoke(__proj, __b))) | |
3178 | return __b; | |
bc464641 | 3179 | else |
b40c57bd PP |
3180 | return __a; |
3181 | } | |
3182 | ||
3183 | template<input_range _Range, typename _Proj = identity, | |
3184 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
3185 | _Comp = ranges::less> | |
3186 | requires indirectly_copyable_storable<iterator_t<_Range>, | |
3187 | range_value_t<_Range>*> | |
3188 | constexpr range_value_t<_Range> | |
3189 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const | |
3190 | { | |
3191 | auto __first = ranges::begin(__r); | |
3192 | auto __last = ranges::end(__r); | |
3193 | __glibcxx_assert(__first != __last); | |
3194 | auto __result = *__first; | |
3195 | while (++__first != __last) | |
bc464641 | 3196 | { |
b40c57bd PP |
3197 | auto __tmp = *__first; |
3198 | if (std::__invoke(__comp, | |
3199 | std::__invoke(__proj, __result), | |
3200 | std::__invoke(__proj, __tmp))) | |
3201 | __result = std::move(__tmp); | |
bc464641 | 3202 | } |
b40c57bd PP |
3203 | return __result; |
3204 | } | |
bc464641 | 3205 | |
b40c57bd PP |
3206 | template<copyable _Tp, typename _Proj = identity, |
3207 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
3208 | _Comp = ranges::less> | |
3209 | constexpr _Tp | |
55992626 PP |
3210 | operator()(initializer_list<_Tp> __r, |
3211 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
3212 | { |
3213 | return (*this)(ranges::subrange(__r), | |
55992626 | 3214 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3215 | } |
3216 | }; | |
bc464641 | 3217 | |
b40c57bd | 3218 | inline constexpr __max_fn max{}; |
bc464641 | 3219 | |
f3169941 PP |
3220 | struct __clamp_fn |
3221 | { | |
3222 | template<typename _Tp, typename _Proj = identity, | |
3223 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp | |
3224 | = ranges::less> | |
3225 | constexpr const _Tp& | |
3226 | operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, | |
3227 | _Comp __comp = {}, _Proj __proj = {}) const | |
3228 | { | |
3229 | __glibcxx_assert(!(std::__invoke(__comp, | |
3230 | std::__invoke(__proj, __hi), | |
3231 | std::__invoke(__proj, __lo)))); | |
3232 | auto&& __proj_val = std::__invoke(__proj, __val); | |
3233 | if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo))) | |
3234 | return __lo; | |
3235 | else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val)) | |
3236 | return __hi; | |
3237 | else | |
3238 | return __val; | |
3239 | } | |
3240 | }; | |
3241 | ||
3242 | inline constexpr __clamp_fn clamp{}; | |
3243 | ||
bc464641 | 3244 | template<typename _Tp> |
aa667c3f | 3245 | struct min_max_result |
bc464641 PP |
3246 | { |
3247 | [[no_unique_address]] _Tp min; | |
3248 | [[no_unique_address]] _Tp max; | |
3249 | ||
3250 | template<typename _Tp2> | |
3251 | requires convertible_to<const _Tp&, _Tp2> | |
aa667c3f PP |
3252 | constexpr |
3253 | operator min_max_result<_Tp2>() const & | |
bc464641 PP |
3254 | { return {min, max}; } |
3255 | ||
3256 | template<typename _Tp2> | |
3257 | requires convertible_to<_Tp, _Tp2> | |
aa667c3f PP |
3258 | constexpr |
3259 | operator min_max_result<_Tp2>() && | |
bc464641 PP |
3260 | { return {std::move(min), std::move(max)}; } |
3261 | }; | |
3262 | ||
aa667c3f PP |
3263 | template<typename _Tp> |
3264 | using minmax_result = min_max_result<_Tp>; | |
3265 | ||
b40c57bd PP |
3266 | struct __minmax_fn |
3267 | { | |
3268 | template<typename _Tp, typename _Proj = identity, | |
3269 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
3270 | _Comp = ranges::less> | |
3271 | constexpr minmax_result<const _Tp&> | |
55992626 PP |
3272 | operator()(const _Tp& __a, const _Tp& __b, |
3273 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
3274 | { |
3275 | if (std::__invoke(std::move(__comp), | |
3276 | std::__invoke(__proj, __b), | |
3277 | std::__invoke(__proj, __a))) | |
3278 | return {__b, __a}; | |
3279 | else | |
3280 | return {__a, __b}; | |
3281 | } | |
3282 | ||
3283 | template<input_range _Range, typename _Proj = identity, | |
3284 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
3285 | _Comp = ranges::less> | |
3286 | requires indirectly_copyable_storable<iterator_t<_Range>, | |
3287 | range_value_t<_Range>*> | |
3288 | constexpr minmax_result<range_value_t<_Range>> | |
3289 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const | |
3290 | { | |
3291 | auto __first = ranges::begin(__r); | |
3292 | auto __last = ranges::end(__r); | |
3293 | __glibcxx_assert(__first != __last); | |
3294 | minmax_result<range_value_t<_Range>> __result = {*__first, *__first}; | |
3295 | while (++__first != __last) | |
3296 | { | |
3297 | auto __tmp = *__first; | |
3298 | if (std::__invoke(__comp, | |
3299 | std::__invoke(__proj, __tmp), | |
3300 | std::__invoke(__proj, __result.min))) | |
3301 | __result.min = std::move(__tmp); | |
3302 | if (!(bool)std::__invoke(__comp, | |
3303 | std::__invoke(__proj, __tmp), | |
3304 | std::__invoke(__proj, __result.max))) | |
3305 | __result.max = std::move(__tmp); | |
3306 | } | |
3307 | return __result; | |
3308 | } | |
3309 | ||
3310 | template<copyable _Tp, typename _Proj = identity, | |
3311 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
3312 | _Comp = ranges::less> | |
3313 | constexpr minmax_result<_Tp> | |
55992626 PP |
3314 | operator()(initializer_list<_Tp> __r, |
3315 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
3316 | { |
3317 | return (*this)(ranges::subrange(__r), | |
55992626 | 3318 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3319 | } |
3320 | }; | |
3321 | ||
3322 | inline constexpr __minmax_fn minmax{}; | |
3323 | ||
3324 | struct __min_element_fn | |
3325 | { | |
3326 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
3327 | typename _Proj = identity, | |
3328 | indirect_strict_weak_order<projected<_Iter, _Proj>> | |
3329 | _Comp = ranges::less> | |
3330 | constexpr _Iter | |
3331 | operator()(_Iter __first, _Sent __last, | |
55992626 | 3332 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
3333 | { |
3334 | if (__first == __last) | |
3335 | return __first; | |
3336 | ||
3337 | auto __i = __first; | |
3338 | while (++__i != __last) | |
3339 | { | |
3340 | if (std::__invoke(__comp, | |
3341 | std::__invoke(__proj, *__i), | |
3342 | std::__invoke(__proj, *__first))) | |
3343 | __first = __i; | |
3344 | } | |
bc464641 | 3345 | return __first; |
b40c57bd | 3346 | } |
bc464641 | 3347 | |
b40c57bd PP |
3348 | template<forward_range _Range, typename _Proj = identity, |
3349 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
3350 | _Comp = ranges::less> | |
15411a64 | 3351 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
3352 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
3353 | { | |
3354 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 3355 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3356 | } |
3357 | }; | |
3358 | ||
3359 | inline constexpr __min_element_fn min_element{}; | |
3360 | ||
3361 | struct __max_element_fn | |
3362 | { | |
3363 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
3364 | typename _Proj = identity, | |
3365 | indirect_strict_weak_order<projected<_Iter, _Proj>> | |
3366 | _Comp = ranges::less> | |
3367 | constexpr _Iter | |
3368 | operator()(_Iter __first, _Sent __last, | |
55992626 | 3369 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
3370 | { |
3371 | if (__first == __last) | |
3372 | return __first; | |
3373 | ||
3374 | auto __i = __first; | |
3375 | while (++__i != __last) | |
3376 | { | |
3377 | if (std::__invoke(__comp, | |
3378 | std::__invoke(__proj, *__first), | |
3379 | std::__invoke(__proj, *__i))) | |
3380 | __first = __i; | |
3381 | } | |
bc464641 | 3382 | return __first; |
b40c57bd | 3383 | } |
bc464641 | 3384 | |
b40c57bd PP |
3385 | template<forward_range _Range, typename _Proj = identity, |
3386 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
3387 | _Comp = ranges::less> | |
15411a64 | 3388 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
3389 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
3390 | { | |
3391 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 3392 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3393 | } |
3394 | }; | |
3395 | ||
3396 | inline constexpr __max_element_fn max_element{}; | |
bc464641 PP |
3397 | |
3398 | template<typename _Iter> | |
aa667c3f | 3399 | using minmax_element_result = min_max_result<_Iter>; |
bc464641 | 3400 | |
b40c57bd PP |
3401 | struct __minmax_element_fn |
3402 | { | |
3403 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
3404 | typename _Proj = identity, | |
3405 | indirect_strict_weak_order<projected<_Iter, _Proj>> | |
3406 | _Comp = ranges::less> | |
3407 | constexpr minmax_element_result<_Iter> | |
3408 | operator()(_Iter __first, _Sent __last, | |
55992626 | 3409 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
3410 | { |
3411 | if (__first == __last) | |
3412 | return {__first, __first}; | |
bc464641 | 3413 | |
b40c57bd PP |
3414 | minmax_element_result<_Iter> __result = {__first, __first}; |
3415 | auto __i = __first; | |
3416 | while (++__i != __last) | |
3417 | { | |
3418 | if (std::__invoke(__comp, | |
3419 | std::__invoke(__proj, *__i), | |
3420 | std::__invoke(__proj, *__result.min))) | |
3421 | __result.min = __i; | |
3422 | if (!(bool)std::__invoke(__comp, | |
3423 | std::__invoke(__proj, *__i), | |
3424 | std::__invoke(__proj, *__result.max))) | |
3425 | __result.max = __i; | |
3426 | } | |
3427 | return __result; | |
3428 | } | |
bc464641 | 3429 | |
b40c57bd PP |
3430 | template<forward_range _Range, typename _Proj = identity, |
3431 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
3432 | _Comp = ranges::less> | |
15411a64 | 3433 | constexpr minmax_element_result<borrowed_iterator_t<_Range>> |
b40c57bd PP |
3434 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
3435 | { | |
3436 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 3437 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3438 | } |
3439 | }; | |
bc464641 | 3440 | |
b40c57bd | 3441 | inline constexpr __minmax_element_fn minmax_element{}; |
bc464641 | 3442 | |
b40c57bd PP |
3443 | struct __lexicographical_compare_fn |
3444 | { | |
3445 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
3446 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
3447 | typename _Proj1 = identity, typename _Proj2 = identity, | |
3448 | indirect_strict_weak_order<projected<_Iter1, _Proj1>, | |
3449 | projected<_Iter2, _Proj2>> | |
3450 | _Comp = ranges::less> | |
3451 | constexpr bool | |
3452 | operator()(_Iter1 __first1, _Sent1 __last1, | |
55992626 PP |
3453 | _Iter2 __first2, _Sent2 __last2, |
3454 | _Comp __comp = {}, | |
3455 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
3456 | { |
3457 | if constexpr (__detail::__is_normal_iterator<_Iter1> | |
a73051a0 PP |
3458 | && same_as<_Iter1, _Sent1>) |
3459 | return (*this)(__first1.base(), __last1.base(), | |
3460 | std::move(__first2), std::move(__last2), | |
3461 | std::move(__comp), | |
3462 | std::move(__proj1), std::move(__proj2)); | |
3463 | else if constexpr (__detail::__is_normal_iterator<_Iter2> | |
3464 | && same_as<_Iter2, _Sent2>) | |
3465 | return (*this)(std::move(__first1), std::move(__last1), | |
3466 | __first2.base(), __last2.base(), | |
55992626 PP |
3467 | std::move(__comp), |
3468 | std::move(__proj1), std::move(__proj2)); | |
93b8cfce | 3469 | else |
b40c57bd | 3470 | { |
93b8cfce PP |
3471 | constexpr bool __sized_iters |
3472 | = (sized_sentinel_for<_Sent1, _Iter1> | |
3473 | && sized_sentinel_for<_Sent2, _Iter2>); | |
3474 | if constexpr (__sized_iters) | |
b40c57bd | 3475 | { |
93b8cfce PP |
3476 | using _ValueType1 = iter_value_t<_Iter1>; |
3477 | using _ValueType2 = iter_value_t<_Iter2>; | |
ce33801f PP |
3478 | // This condition is consistent with the one in |
3479 | // __lexicographical_compare_aux in <bits/stl_algobase.h>. | |
93b8cfce | 3480 | constexpr bool __use_memcmp |
2f983fa6 | 3481 | = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value |
462f6c20 JW |
3482 | && __ptr_to_nonvolatile<_Iter1> |
3483 | && __ptr_to_nonvolatile<_Iter2> | |
93b8cfce PP |
3484 | && (is_same_v<_Comp, ranges::less> |
3485 | || is_same_v<_Comp, ranges::greater>) | |
3486 | && is_same_v<_Proj1, identity> | |
3487 | && is_same_v<_Proj2, identity>); | |
3488 | if constexpr (__use_memcmp) | |
b40c57bd | 3489 | { |
113f0a63 JW |
3490 | const auto __d1 = __last1 - __first1; |
3491 | const auto __d2 = __last2 - __first2; | |
3492 | ||
93b8cfce | 3493 | if (const auto __len = std::min(__d1, __d2)) |
b40c57bd | 3494 | { |
93b8cfce PP |
3495 | const auto __c |
3496 | = std::__memcmp(__first1, __first2, __len); | |
3497 | if constexpr (is_same_v<_Comp, ranges::less>) | |
3498 | { | |
3499 | if (__c < 0) | |
3500 | return true; | |
3501 | if (__c > 0) | |
3502 | return false; | |
3503 | } | |
3504 | else if constexpr (is_same_v<_Comp, ranges::greater>) | |
3505 | { | |
3506 | if (__c > 0) | |
3507 | return true; | |
3508 | if (__c < 0) | |
3509 | return false; | |
3510 | } | |
b40c57bd | 3511 | } |
113f0a63 | 3512 | return __d1 < __d2; |
b40c57bd | 3513 | } |
b40c57bd | 3514 | } |
b40c57bd | 3515 | |
93b8cfce PP |
3516 | for (; __first1 != __last1 && __first2 != __last2; |
3517 | ++__first1, (void) ++__first2) | |
3518 | { | |
3519 | if (std::__invoke(__comp, | |
3520 | std::__invoke(__proj1, *__first1), | |
3521 | std::__invoke(__proj2, *__first2))) | |
3522 | return true; | |
3523 | if (std::__invoke(__comp, | |
3524 | std::__invoke(__proj2, *__first2), | |
3525 | std::__invoke(__proj1, *__first1))) | |
3526 | return false; | |
3527 | } | |
3528 | return __first1 == __last1 && __first2 != __last2; | |
b40c57bd | 3529 | } |
b40c57bd PP |
3530 | } |
3531 | ||
55992626 PP |
3532 | template<input_range _Range1, input_range _Range2, |
3533 | typename _Proj1 = identity, typename _Proj2 = identity, | |
b40c57bd PP |
3534 | indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>, |
3535 | projected<iterator_t<_Range2>, _Proj2>> | |
3536 | _Comp = ranges::less> | |
3537 | constexpr bool | |
3538 | operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {}, | |
55992626 | 3539 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const |
b40c57bd | 3540 | { |
55992626 PP |
3541 | return (*this)(ranges::begin(__r1), ranges::end(__r1), |
3542 | ranges::begin(__r2), ranges::end(__r2), | |
3543 | std::move(__comp), | |
3544 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd | 3545 | } |
462f6c20 JW |
3546 | |
3547 | private: | |
3548 | template<typename _Iter, typename _Ref = iter_reference_t<_Iter>> | |
3549 | static constexpr bool __ptr_to_nonvolatile | |
3550 | = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>; | |
b40c57bd PP |
3551 | }; |
3552 | ||
3553 | inline constexpr __lexicographical_compare_fn lexicographical_compare; | |
bc464641 PP |
3554 | |
3555 | template<typename _Iter> | |
aa667c3f | 3556 | struct in_found_result |
bc464641 | 3557 | { |
aa667c3f | 3558 | [[no_unique_address]] _Iter in; |
bc464641 | 3559 | bool found; |
aa667c3f PP |
3560 | |
3561 | template<typename _Iter2> | |
3562 | requires convertible_to<const _Iter&, _Iter2> | |
3563 | constexpr | |
3564 | operator in_found_result<_Iter2>() const & | |
3565 | { return {in, found}; } | |
3566 | ||
3567 | template<typename _Iter2> | |
3568 | requires convertible_to<_Iter, _Iter2> | |
3569 | constexpr | |
3570 | operator in_found_result<_Iter2>() && | |
3571 | { return {std::move(in), found}; } | |
bc464641 PP |
3572 | }; |
3573 | ||
aa667c3f PP |
3574 | template<typename _Iter> |
3575 | using next_permutation_result = in_found_result<_Iter>; | |
3576 | ||
b40c57bd PP |
3577 | struct __next_permutation_fn |
3578 | { | |
3579 | template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
3580 | typename _Comp = ranges::less, typename _Proj = identity> | |
3581 | requires sortable<_Iter, _Comp, _Proj> | |
3582 | constexpr next_permutation_result<_Iter> | |
3583 | operator()(_Iter __first, _Sent __last, | |
55992626 | 3584 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
3585 | { |
3586 | if (__first == __last) | |
aa667c3f | 3587 | return {std::move(__first), false}; |
bc464641 | 3588 | |
b40c57bd PP |
3589 | auto __i = __first; |
3590 | ++__i; | |
3591 | if (__i == __last) | |
aa667c3f | 3592 | return {std::move(__i), false}; |
bc464641 | 3593 | |
b40c57bd PP |
3594 | auto __lasti = ranges::next(__first, __last); |
3595 | __i = __lasti; | |
3596 | --__i; | |
bc464641 | 3597 | |
b40c57bd PP |
3598 | for (;;) |
3599 | { | |
3600 | auto __ii = __i; | |
3601 | --__i; | |
3602 | if (std::__invoke(__comp, | |
3603 | std::__invoke(__proj, *__i), | |
3604 | std::__invoke(__proj, *__ii))) | |
3605 | { | |
3606 | auto __j = __lasti; | |
3607 | while (!(bool)std::__invoke(__comp, | |
3608 | std::__invoke(__proj, *__i), | |
3609 | std::__invoke(__proj, *--__j))) | |
3610 | ; | |
3611 | ranges::iter_swap(__i, __j); | |
3612 | ranges::reverse(__ii, __last); | |
aa667c3f | 3613 | return {std::move(__lasti), true}; |
b40c57bd PP |
3614 | } |
3615 | if (__i == __first) | |
3616 | { | |
3617 | ranges::reverse(__first, __last); | |
aa667c3f | 3618 | return {std::move(__lasti), false}; |
b40c57bd PP |
3619 | } |
3620 | } | |
3621 | } | |
bc464641 | 3622 | |
b40c57bd PP |
3623 | template<bidirectional_range _Range, typename _Comp = ranges::less, |
3624 | typename _Proj = identity> | |
3625 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 3626 | constexpr next_permutation_result<borrowed_iterator_t<_Range>> |
b40c57bd PP |
3627 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
3628 | { | |
3629 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 3630 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3631 | } |
3632 | }; | |
3633 | ||
3634 | inline constexpr __next_permutation_fn next_permutation{}; | |
bc464641 PP |
3635 | |
3636 | template<typename _Iter> | |
aa667c3f | 3637 | using prev_permutation_result = in_found_result<_Iter>; |
bc464641 | 3638 | |
b40c57bd PP |
3639 | struct __prev_permutation_fn |
3640 | { | |
3641 | template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, | |
3642 | typename _Comp = ranges::less, typename _Proj = identity> | |
3643 | requires sortable<_Iter, _Comp, _Proj> | |
3644 | constexpr prev_permutation_result<_Iter> | |
3645 | operator()(_Iter __first, _Sent __last, | |
55992626 | 3646 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
3647 | { |
3648 | if (__first == __last) | |
aa667c3f | 3649 | return {std::move(__first), false}; |
bc464641 | 3650 | |
b40c57bd PP |
3651 | auto __i = __first; |
3652 | ++__i; | |
3653 | if (__i == __last) | |
aa667c3f | 3654 | return {std::move(__i), false}; |
bc464641 | 3655 | |
b40c57bd PP |
3656 | auto __lasti = ranges::next(__first, __last); |
3657 | __i = __lasti; | |
3658 | --__i; | |
bc464641 | 3659 | |
b40c57bd PP |
3660 | for (;;) |
3661 | { | |
3662 | auto __ii = __i; | |
3663 | --__i; | |
3664 | if (std::__invoke(__comp, | |
3665 | std::__invoke(__proj, *__ii), | |
3666 | std::__invoke(__proj, *__i))) | |
3667 | { | |
3668 | auto __j = __lasti; | |
3669 | while (!(bool)std::__invoke(__comp, | |
3670 | std::__invoke(__proj, *--__j), | |
3671 | std::__invoke(__proj, *__i))) | |
3672 | ; | |
3673 | ranges::iter_swap(__i, __j); | |
3674 | ranges::reverse(__ii, __last); | |
aa667c3f | 3675 | return {std::move(__lasti), true}; |
b40c57bd PP |
3676 | } |
3677 | if (__i == __first) | |
3678 | { | |
3679 | ranges::reverse(__first, __last); | |
aa667c3f | 3680 | return {std::move(__lasti), false}; |
b40c57bd PP |
3681 | } |
3682 | } | |
3683 | } | |
bc464641 | 3684 | |
b40c57bd PP |
3685 | template<bidirectional_range _Range, typename _Comp = ranges::less, |
3686 | typename _Proj = identity> | |
3687 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 3688 | constexpr prev_permutation_result<borrowed_iterator_t<_Range>> |
b40c57bd PP |
3689 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
3690 | { | |
3691 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 3692 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3693 | } |
3694 | }; | |
3695 | ||
3696 | inline constexpr __prev_permutation_fn prev_permutation{}; | |
bc464641 PP |
3697 | |
3698 | } // namespace ranges | |
c5eab4ed | 3699 | |
56772f62 | 3700 | #define __cpp_lib_shift 201806L |
23f75da9 JW |
3701 | template<typename _ForwardIterator> |
3702 | constexpr _ForwardIterator | |
3703 | shift_left(_ForwardIterator __first, _ForwardIterator __last, | |
3704 | typename iterator_traits<_ForwardIterator>::difference_type __n) | |
c5eab4ed PP |
3705 | { |
3706 | __glibcxx_assert(__n >= 0); | |
3707 | if (__n == 0) | |
3708 | return __last; | |
3709 | ||
3710 | auto __mid = ranges::next(__first, __n, __last); | |
3711 | if (__mid == __last) | |
3712 | return __first; | |
3713 | return std::move(std::move(__mid), std::move(__last), std::move(__first)); | |
3714 | } | |
3715 | ||
23f75da9 JW |
3716 | template<typename _ForwardIterator> |
3717 | constexpr _ForwardIterator | |
3718 | shift_right(_ForwardIterator __first, _ForwardIterator __last, | |
3719 | typename iterator_traits<_ForwardIterator>::difference_type __n) | |
c5eab4ed PP |
3720 | { |
3721 | __glibcxx_assert(__n >= 0); | |
3722 | if (__n == 0) | |
3723 | return __first; | |
3724 | ||
23f75da9 JW |
3725 | using _Cat |
3726 | = typename iterator_traits<_ForwardIterator>::iterator_category; | |
c5eab4ed PP |
3727 | if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) |
3728 | { | |
3729 | auto __mid = ranges::next(__last, -__n, __first); | |
3730 | if (__mid == __first) | |
3731 | return __last; | |
3732 | ||
3733 | return std::move_backward(std::move(__first), std::move(__mid), | |
3734 | std::move(__last)); | |
3735 | } | |
3736 | else | |
3737 | { | |
3738 | auto __result = ranges::next(__first, __n, __last); | |
3739 | if (__result == __last) | |
3740 | return __last; | |
3741 | ||
3742 | auto __dest_head = __first, __dest_tail = __result; | |
3743 | while (__dest_head != __result) | |
3744 | { | |
3745 | if (__dest_tail == __last) | |
3746 | { | |
3747 | // If we get here, then we must have | |
3748 | // 2*n >= distance(__first, __last) | |
3749 | // i.e. we are shifting out at least half of the range. In | |
3750 | // this case we can safely perform the shift with a single | |
3751 | // move. | |
3752 | std::move(std::move(__first), std::move(__dest_head), | |
3753 | std::move(__result)); | |
3754 | return __result; | |
3755 | } | |
3756 | ++__dest_head; | |
3757 | ++__dest_tail; | |
3758 | } | |
3759 | ||
3760 | for (;;) | |
3761 | { | |
3762 | // At the start of each iteration of this outer loop, the range | |
3763 | // [__first, __result) contains those elements that after shifting | |
3764 | // the whole range right by __n, should end up in | |
3765 | // [__dest_head, __dest_tail) in order. | |
3766 | ||
3767 | // The below inner loop swaps the elements of [__first, __result) | |
3768 | // and [__dest_head, __dest_tail), while simultaneously shifting | |
3769 | // the latter range by __n. | |
3770 | auto __cursor = __first; | |
3771 | while (__cursor != __result) | |
3772 | { | |
3773 | if (__dest_tail == __last) | |
3774 | { | |
3775 | // At this point the ranges [__first, result) and | |
3776 | // [__dest_head, dest_tail) are disjoint, so we can safely | |
3777 | // move the remaining elements. | |
3778 | __dest_head = std::move(__cursor, __result, | |
3779 | std::move(__dest_head)); | |
3780 | std::move(std::move(__first), std::move(__cursor), | |
3781 | std::move(__dest_head)); | |
3782 | return __result; | |
3783 | } | |
3784 | std::iter_swap(__cursor, __dest_head); | |
3785 | ++__dest_head; | |
3786 | ++__dest_tail; | |
3787 | ++__cursor; | |
3788 | } | |
3789 | } | |
3790 | } | |
3791 | } | |
3792 | ||
bc464641 PP |
3793 | _GLIBCXX_END_NAMESPACE_VERSION |
3794 | } // namespace std | |
3795 | #endif // concepts | |
3796 | #endif // C++20 | |
3797 | #endif // _RANGES_ALGO_H |