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