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