]>
Commit | Line | Data |
---|---|---|
bc464641 PP |
1 | // Core algorithmic facilities -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2020-2022 Free Software Foundation, Inc. |
bc464641 PP |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 3, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // Under Section 7 of GPL version 3, you are granted additional | |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
24 | ||
25 | /** @file bits/ranges_algo.h | |
26 | * This is an internal header file, included by other library headers. | |
27 | * Do not attempt to use it directly. @headername{algorithm} | |
28 | */ | |
29 | ||
30 | #ifndef _RANGES_ALGO_H | |
31 | #define _RANGES_ALGO_H 1 | |
32 | ||
33 | #if __cplusplus > 201703L | |
34 | ||
90fc7b3c | 35 | #include <bits/ranges_algobase.h> |
160061ac | 36 | #include <bits/ranges_util.h> |
9cd4eeef | 37 | #include <bits/uniform_int_dist.h> // concept uniform_random_bit_generator |
bc464641 PP |
38 | |
39 | #if __cpp_lib_concepts | |
40 | namespace std _GLIBCXX_VISIBILITY(default) | |
41 | { | |
42 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
43 | namespace ranges | |
44 | { | |
45 | namespace __detail | |
46 | { | |
bc464641 PP |
47 | template<typename _Comp, typename _Proj> |
48 | constexpr auto | |
49 | __make_comp_proj(_Comp& __comp, _Proj& __proj) | |
50 | { | |
51 | return [&] (auto&& __lhs, auto&& __rhs) -> bool { | |
52 | using _TL = decltype(__lhs); | |
53 | using _TR = decltype(__rhs); | |
54 | return std::__invoke(__comp, | |
55 | std::__invoke(__proj, std::forward<_TL>(__lhs)), | |
56 | std::__invoke(__proj, std::forward<_TR>(__rhs))); | |
57 | }; | |
58 | } | |
59 | ||
60 | template<typename _Pred, typename _Proj> | |
61 | constexpr auto | |
62 | __make_pred_proj(_Pred& __pred, _Proj& __proj) | |
63 | { | |
64 | return [&] <typename _Tp> (_Tp&& __arg) -> bool { | |
65 | return std::__invoke(__pred, | |
66 | std::__invoke(__proj, std::forward<_Tp>(__arg))); | |
67 | }; | |
68 | } | |
69 | } // namespace __detail | |
70 | ||
b40c57bd PP |
71 | struct __all_of_fn |
72 | { | |
73 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
74 | typename _Proj = identity, | |
75 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
76 | constexpr bool | |
55992626 PP |
77 | operator()(_Iter __first, _Sent __last, |
78 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
79 | { |
80 | for (; __first != __last; ++__first) | |
81 | if (!(bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
82 | return false; | |
83 | return true; | |
84 | } | |
bc464641 | 85 | |
b40c57bd | 86 | template<input_range _Range, typename _Proj = identity, |
55992626 PP |
87 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
88 | _Pred> | |
b40c57bd PP |
89 | constexpr bool |
90 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
91 | { | |
92 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
93 | std::move(__pred), std::move(__proj)); | |
94 | } | |
95 | }; | |
bc464641 | 96 | |
b40c57bd | 97 | inline constexpr __all_of_fn all_of{}; |
bc464641 | 98 | |
b40c57bd PP |
99 | struct __any_of_fn |
100 | { | |
101 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
102 | typename _Proj = identity, | |
103 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
104 | constexpr bool | |
55992626 PP |
105 | operator()(_Iter __first, _Sent __last, |
106 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
107 | { |
108 | for (; __first != __last; ++__first) | |
109 | if (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
110 | return true; | |
111 | return false; | |
112 | } | |
113 | ||
114 | template<input_range _Range, typename _Proj = identity, | |
55992626 PP |
115 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
116 | _Pred> | |
b40c57bd PP |
117 | constexpr bool |
118 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
119 | { | |
120 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 121 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
122 | } |
123 | }; | |
124 | ||
125 | inline constexpr __any_of_fn any_of{}; | |
126 | ||
127 | struct __none_of_fn | |
128 | { | |
129 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
130 | typename _Proj = identity, | |
131 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
132 | constexpr bool | |
55992626 PP |
133 | operator()(_Iter __first, _Sent __last, |
134 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
135 | { |
136 | for (; __first != __last; ++__first) | |
137 | if (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
138 | return false; | |
139 | return true; | |
140 | } | |
141 | ||
142 | template<input_range _Range, typename _Proj = identity, | |
55992626 PP |
143 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
144 | _Pred> | |
b40c57bd PP |
145 | constexpr bool |
146 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
147 | { | |
148 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
149 | std::move(__pred), std::move(__proj)); | |
150 | } | |
151 | }; | |
152 | ||
153 | inline constexpr __none_of_fn none_of{}; | |
bc464641 PP |
154 | |
155 | template<typename _Iter, typename _Fp> | |
aa667c3f | 156 | struct in_fun_result |
bc464641 PP |
157 | { |
158 | [[no_unique_address]] _Iter in; | |
159 | [[no_unique_address]] _Fp fun; | |
160 | ||
161 | template<typename _Iter2, typename _F2p> | |
162 | requires convertible_to<const _Iter&, _Iter2> | |
163 | && convertible_to<const _Fp&, _F2p> | |
aa667c3f PP |
164 | constexpr |
165 | operator in_fun_result<_Iter2, _F2p>() const & | |
bc464641 PP |
166 | { return {in, fun}; } |
167 | ||
168 | template<typename _Iter2, typename _F2p> | |
169 | requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p> | |
aa667c3f PP |
170 | constexpr |
171 | operator in_fun_result<_Iter2, _F2p>() && | |
bc464641 PP |
172 | { return {std::move(in), std::move(fun)}; } |
173 | }; | |
174 | ||
aa667c3f PP |
175 | template<typename _Iter, typename _Fp> |
176 | using for_each_result = in_fun_result<_Iter, _Fp>; | |
177 | ||
b40c57bd PP |
178 | struct __for_each_fn |
179 | { | |
180 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
181 | typename _Proj = identity, | |
182 | indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun> | |
183 | constexpr for_each_result<_Iter, _Fun> | |
184 | operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const | |
185 | { | |
186 | for (; __first != __last; ++__first) | |
187 | std::__invoke(__f, std::__invoke(__proj, *__first)); | |
188 | return { std::move(__first), std::move(__f) }; | |
189 | } | |
190 | ||
191 | template<input_range _Range, typename _Proj = identity, | |
192 | indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>> | |
193 | _Fun> | |
15411a64 | 194 | constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun> |
b40c57bd PP |
195 | operator()(_Range&& __r, _Fun __f, _Proj __proj = {}) const |
196 | { | |
197 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 198 | std::move(__f), std::move(__proj)); |
b40c57bd PP |
199 | } |
200 | }; | |
201 | ||
202 | inline constexpr __for_each_fn for_each{}; | |
203 | ||
f3169941 | 204 | template<typename _Iter, typename _Fp> |
aa667c3f | 205 | using for_each_n_result = in_fun_result<_Iter, _Fp>; |
f3169941 PP |
206 | |
207 | struct __for_each_n_fn | |
208 | { | |
209 | template<input_iterator _Iter, typename _Proj = identity, | |
210 | indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun> | |
211 | constexpr for_each_n_result<_Iter, _Fun> | |
212 | operator()(_Iter __first, iter_difference_t<_Iter> __n, | |
213 | _Fun __f, _Proj __proj = {}) const | |
214 | { | |
215 | if constexpr (random_access_iterator<_Iter>) | |
216 | { | |
217 | if (__n <= 0) | |
218 | return {std::move(__first), std::move(__f)}; | |
219 | auto __last = __first + __n; | |
220 | return ranges::for_each(std::move(__first), std::move(__last), | |
221 | std::move(__f), std::move(__proj)); | |
222 | } | |
223 | else | |
224 | { | |
225 | while (__n-- > 0) | |
226 | { | |
227 | std::__invoke(__f, std::__invoke(__proj, *__first)); | |
228 | ++__first; | |
229 | } | |
230 | return {std::move(__first), std::move(__f)}; | |
231 | } | |
232 | } | |
233 | }; | |
234 | ||
235 | inline constexpr __for_each_n_fn for_each_n{}; | |
236 | ||
2786064d | 237 | // find, find_if and find_if_not are defined in <bits/ranges_util.h>. |
b40c57bd PP |
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, | |
55992626 PP |
248 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, |
249 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
250 | { |
251 | for (; __first1 != __last1; ++__first1) | |
252 | for (auto __iter = __first2; __iter != __last2; ++__iter) | |
a45fb21a JW |
253 | if (std::__invoke(__pred, |
254 | std::__invoke(__proj1, *__first1), | |
255 | std::__invoke(__proj2, *__iter))) | |
b40c57bd PP |
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> | |
15411a64 | 265 | constexpr borrowed_iterator_t<_Range1> |
55992626 PP |
266 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, |
267 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
268 | { |
269 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
270 | ranges::begin(__r2), ranges::end(__r2), |
271 | std::move(__pred), | |
272 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
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> | |
55992626 PP |
286 | operator()(_Iter __first, _Sent __last, |
287 | const _Tp& __value, _Proj __proj = {}) const | |
b40c57bd PP |
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), | |
55992626 | 304 | __value, std::move(__proj)); |
b40c57bd PP |
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> | |
55992626 PP |
316 | operator()(_Iter __first, _Sent __last, |
317 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
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, | |
55992626 PP |
328 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
329 | _Pred> | |
b40c57bd PP |
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), | |
55992626 | 334 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
335 | } |
336 | }; | |
337 | ||
338 | inline constexpr __count_if_fn count_if{}; | |
bc464641 | 339 | |
2786064d | 340 | // in_in_result, mismatch and search are defined in <bits/ranges_util.h>. |
bc464641 | 341 | |
b40c57bd PP |
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, | |
55992626 | 349 | const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const |
b40c57bd PP |
350 | { |
351 | if (__count <= 0) | |
352 | return {__first, __first}; | |
bc464641 | 353 | |
d91e7eab | 354 | auto __value_comp = [&] <typename _Rp> (_Rp&& __arg) -> bool { |
b40c57bd PP |
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, | |
55992626 PP |
360 | std::move(__value_comp), |
361 | std::move(__proj)); | |
b40c57bd PP |
362 | if (__first == __last) |
363 | return {__first, __first}; | |
364 | else | |
365 | { | |
366 | auto __end = __first; | |
367 | return {__first, ++__end}; | |
368 | } | |
369 | } | |
bc464641 | 370 | |
8661f4fa PP |
371 | if constexpr (sized_sentinel_for<_Sent, _Iter> |
372 | && random_access_iterator<_Iter>) | |
b40c57bd PP |
373 | { |
374 | auto __tail_size = __last - __first; | |
375 | auto __remainder = __count; | |
bc464641 | 376 | |
b40c57bd PP |
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 | } | |
8661f4fa | 387 | __remainder = __count + 1 - (__first - __backtrack); |
b40c57bd PP |
388 | } |
389 | auto __i = __first + __tail_size; | |
390 | return {__i, __i}; | |
391 | } | |
392 | else | |
bc464641 | 393 | { |
b40c57bd PP |
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}; | |
bc464641 | 413 | } |
b40c57bd | 414 | } |
bc464641 | 415 | |
b40c57bd PP |
416 | template<forward_range _Range, typename _Tp, |
417 | typename _Pred = ranges::equal_to, typename _Proj = identity> | |
55992626 PP |
418 | requires indirectly_comparable<iterator_t<_Range>, const _Tp*, |
419 | _Pred, _Proj> | |
15411a64 | 420 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
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), | |
55992626 PP |
425 | std::move(__count), __value, |
426 | std::move(__pred), std::move(__proj)); | |
b40c57bd PP |
427 | } |
428 | }; | |
bc464641 | 429 | |
b40c57bd | 430 | inline constexpr __search_n_fn search_n{}; |
bc464641 | 431 | |
b40c57bd PP |
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, | |
55992626 PP |
441 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, |
442 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
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> | |
15411a64 | 496 | constexpr borrowed_subrange_t<_Range1> |
55992626 PP |
497 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, |
498 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
499 | { |
500 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
501 | ranges::begin(__r2), ranges::end(__r2), |
502 | std::move(__pred), | |
503 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
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, | |
55992626 | 518 | _Pred __pred = {}, _Proj __proj = {}) const |
b40c57bd PP |
519 | { |
520 | if (__first == __last) | |
521 | return __first; | |
522 | auto __next = __first; | |
523 | for (; ++__next != __last; __first = __next) | |
524 | { | |
a45fb21a JW |
525 | if (std::__invoke(__pred, |
526 | std::__invoke(__proj, *__first), | |
527 | std::__invoke(__proj, *__next))) | |
b40c57bd PP |
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> | |
15411a64 | 537 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
538 | operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const |
539 | { | |
540 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 541 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
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, | |
55992626 PP |
557 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, |
558 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
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 | { | |
d91e7eab PP |
597 | auto&& __proj_scan = std::__invoke(__proj1, *__scan); |
598 | auto __comp_scan = [&] <typename _Tp> (_Tp&& __arg) -> bool { | |
b40c57bd PP |
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 = {}, | |
55992626 | 623 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const |
b40c57bd PP |
624 | { |
625 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
626 | ranges::begin(__r2), ranges::end(__r2), |
627 | std::move(__pred), | |
628 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
629 | } |
630 | }; | |
631 | ||
632 | inline constexpr __is_permutation_fn is_permutation{}; | |
633 | ||
634 | template<typename _Iter, typename _Out> | |
aa667c3f | 635 | using copy_if_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
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, | |
55992626 | 645 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
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, | |
55992626 PP |
658 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
659 | _Pred> | |
b40c57bd | 660 | requires indirectly_copyable<iterator_t<_Range>, _Out> |
15411a64 | 661 | constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out> |
55992626 PP |
662 | operator()(_Range&& __r, _Out __result, |
663 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
664 | { |
665 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
666 | std::move(__result), |
667 | std::move(__pred), std::move(__proj)); | |
b40c57bd PP |
668 | } |
669 | }; | |
670 | ||
671 | inline constexpr __copy_if_fn copy_if{}; | |
672 | ||
673 | template<typename _Iter1, typename _Iter2> | |
aa667c3f | 674 | using swap_ranges_result = in_in_result<_Iter1, _Iter2>; |
b40c57bd PP |
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 | operator()(_Iter1 __first1, _Sent1 __last1, | |
55992626 | 683 | _Iter2 __first2, _Sent2 __last2) const |
b40c57bd PP |
684 | { |
685 | for (; __first1 != __last1 && __first2 != __last2; | |
686 | ++__first1, (void)++__first2) | |
687 | ranges::iter_swap(__first1, __first2); | |
688 | 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>> | |
15411a64 JW |
693 | constexpr swap_ranges_result<borrowed_iterator_t<_Range1>, |
694 | borrowed_iterator_t<_Range2>> | |
b40c57bd PP |
695 | operator()(_Range1&& __r1, _Range2&& __r2) const |
696 | { | |
697 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 | 698 | ranges::begin(__r2), ranges::end(__r2)); |
b40c57bd PP |
699 | } |
700 | }; | |
701 | ||
702 | inline constexpr __swap_ranges_fn swap_ranges{}; | |
703 | ||
704 | template<typename _Iter, typename _Out> | |
aa667c3f | 705 | using unary_transform_result = in_out_result<_Iter, _Out>; |
bc464641 PP |
706 | |
707 | template<typename _Iter1, typename _Iter2, typename _Out> | |
aa667c3f | 708 | struct in_in_out_result |
bc464641 PP |
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> | |
a04f635d | 715 | requires convertible_to<const _Iter1&, _IIter1> |
bc464641 PP |
716 | && convertible_to<const _Iter2&, _IIter2> |
717 | && convertible_to<const _Out&, _OOut> | |
aa667c3f PP |
718 | constexpr |
719 | operator in_in_out_result<_IIter1, _IIter2, _OOut>() const & | |
bc464641 PP |
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> | |
aa667c3f PP |
726 | constexpr |
727 | operator in_in_out_result<_IIter1, _IIter2, _OOut>() && | |
bc464641 PP |
728 | { return {std::move(in1), std::move(in2), std::move(out)}; } |
729 | }; | |
730 | ||
aa667c3f PP |
731 | template<typename _Iter1, typename _Iter2, typename _Out> |
732 | using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>; | |
733 | ||
b40c57bd PP |
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, | |
55992626 | 744 | _Fp __op, _Proj __proj = {}) const |
b40c57bd PP |
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 | } | |
bc464641 | 750 | |
b40c57bd PP |
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>>> | |
15411a64 | 756 | constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd PP |
757 | operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {}) const |
758 | { | |
759 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
760 | std::move(__result), |
761 | std::move(__op), std::move(__proj)); | |
b40c57bd | 762 | } |
bc464641 | 763 | |
b40c57bd PP |
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> | |
55992626 PP |
773 | operator()(_Iter1 __first1, _Sent1 __last1, |
774 | _Iter2 __first2, _Sent2 __last2, | |
775 | _Out __result, _Fp __binary_op, | |
776 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
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 | } | |
bc464641 | 785 | |
b40c57bd PP |
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>>> | |
15411a64 JW |
793 | constexpr binary_transform_result<borrowed_iterator_t<_Range1>, |
794 | borrowed_iterator_t<_Range2>, _Out> | |
55992626 PP |
795 | operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op, |
796 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
797 | { |
798 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
799 | ranges::begin(__r2), ranges::end(__r2), |
800 | std::move(__result), std::move(__binary_op), | |
801 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
802 | } |
803 | }; | |
bc464641 | 804 | |
b40c57bd | 805 | inline constexpr __transform_fn transform{}; |
bc464641 | 806 | |
b40c57bd PP |
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, | |
55992626 PP |
816 | const _Tp1& __old_value, const _Tp2& __new_value, |
817 | _Proj __proj = {}) const | |
b40c57bd PP |
818 | { |
819 | for (; __first != __last; ++__first) | |
820 | if (std::__invoke(__proj, *__first) == __old_value) | |
821 | *__first = __new_value; | |
822 | return __first; | |
823 | } | |
bc464641 | 824 | |
b40c57bd PP |
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*> | |
15411a64 | 831 | constexpr borrowed_iterator_t<_Range> |
b40c57bd | 832 | operator()(_Range&& __r, |
55992626 PP |
833 | const _Tp1& __old_value, const _Tp2& __new_value, |
834 | _Proj __proj = {}) const | |
b40c57bd PP |
835 | { |
836 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 837 | __old_value, __new_value, std::move(__proj)); |
b40c57bd PP |
838 | } |
839 | }; | |
bc464641 | 840 | |
b40c57bd | 841 | inline constexpr __replace_fn replace{}; |
bc464641 | 842 | |
b40c57bd PP |
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 | } | |
bc464641 | 858 | |
b40c57bd | 859 | template<input_range _Range, typename _Tp, typename _Proj = identity, |
55992626 PP |
860 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
861 | _Pred> | |
b40c57bd | 862 | requires indirectly_writable<iterator_t<_Range>, const _Tp&> |
15411a64 | 863 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
864 | operator()(_Range&& __r, |
865 | _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const | |
866 | { | |
867 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 868 | std::move(__pred), __new_value, std::move(__proj)); |
b40c57bd PP |
869 | } |
870 | }; | |
871 | ||
872 | inline constexpr __replace_if_fn replace_if{}; | |
bc464641 PP |
873 | |
874 | template<typename _Iter, typename _Out> | |
aa667c3f | 875 | using replace_copy_result = in_out_result<_Iter, _Out>; |
bc464641 | 876 | |
b40c57bd PP |
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, | |
55992626 PP |
887 | const _Tp1& __old_value, const _Tp2& __new_value, |
888 | _Proj __proj = {}) const | |
b40c57bd PP |
889 | { |
890 | for (; __first != __last; ++__first, (void)++__result) | |
891 | if (std::__invoke(__proj, *__first) == __old_value) | |
892 | *__result = __new_value; | |
893 | else | |
bc464641 | 894 | *__result = *__first; |
b40c57bd PP |
895 | return {std::move(__first), std::move(__result)}; |
896 | } | |
bc464641 | 897 | |
b40c57bd PP |
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*> | |
15411a64 | 904 | constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd | 905 | operator()(_Range&& __r, _Out __result, |
55992626 PP |
906 | const _Tp1& __old_value, const _Tp2& __new_value, |
907 | _Proj __proj = {}) const | |
b40c57bd PP |
908 | { |
909 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
910 | std::move(__result), __old_value, |
911 | __new_value, std::move(__proj)); | |
b40c57bd PP |
912 | } |
913 | }; | |
914 | ||
915 | inline constexpr __replace_copy_fn replace_copy{}; | |
bc464641 PP |
916 | |
917 | template<typename _Iter, typename _Out> | |
aa667c3f | 918 | using replace_copy_if_result = in_out_result<_Iter, _Out>; |
bc464641 | 919 | |
b40c57bd PP |
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, | |
55992626 | 929 | _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const |
b40c57bd PP |
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; | |
bc464641 | 936 | return {std::move(__first), std::move(__result)}; |
b40c57bd | 937 | } |
bc464641 | 938 | |
b40c57bd PP |
939 | template<input_range _Range, |
940 | typename _Tp, output_iterator<const _Tp&> _Out, | |
941 | typename _Proj = identity, | |
55992626 PP |
942 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
943 | _Pred> | |
b40c57bd | 944 | requires indirectly_copyable<iterator_t<_Range>, _Out> |
15411a64 | 945 | constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd | 946 | operator()(_Range&& __r, _Out __result, |
55992626 | 947 | _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const |
b40c57bd PP |
948 | { |
949 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
950 | std::move(__result), std::move(__pred), |
951 | __new_value, std::move(__proj)); | |
b40c57bd PP |
952 | } |
953 | }; | |
bc464641 | 954 | |
b40c57bd | 955 | inline constexpr __replace_copy_if_fn replace_copy_if{}; |
bc464641 | 956 | |
b40c57bd PP |
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 | }; | |
bc464641 | 970 | |
b40c57bd | 971 | inline constexpr __generate_n_fn generate_n{}; |
bc464641 | 972 | |
b40c57bd PP |
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 | } | |
bc464641 | 986 | |
b40c57bd PP |
987 | template<typename _Range, copy_constructible _Fp> |
988 | requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>> | |
15411a64 | 989 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
990 | operator()(_Range&& __r, _Fp __gen) const |
991 | { | |
55992626 | 992 | return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__gen)); |
b40c57bd PP |
993 | } |
994 | }; | |
bc464641 | 995 | |
b40c57bd | 996 | inline constexpr __generate_fn generate{}; |
bc464641 | 997 | |
b40c57bd PP |
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> | |
55992626 PP |
1004 | operator()(_Iter __first, _Sent __last, |
1005 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
1006 | { |
1007 | __first = ranges::find_if(__first, __last, __pred, __proj); | |
1008 | if (__first == __last) | |
1009 | return {__first, __first}; | |
bc464641 | 1010 | |
b40c57bd PP |
1011 | auto __result = __first; |
1012 | ++__first; | |
1013 | for (; __first != __last; ++__first) | |
a45fb21a | 1014 | if (!std::__invoke(__pred, std::__invoke(__proj, *__first))) |
bc464641 | 1015 | { |
b40c57bd PP |
1016 | *__result = std::move(*__first); |
1017 | ++__result; | |
bc464641 PP |
1018 | } |
1019 | ||
b40c57bd PP |
1020 | return {__result, __first}; |
1021 | } | |
bc464641 | 1022 | |
b40c57bd | 1023 | template<forward_range _Range, typename _Proj = identity, |
55992626 PP |
1024 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
1025 | _Pred> | |
b40c57bd | 1026 | requires permutable<iterator_t<_Range>> |
15411a64 | 1027 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
1028 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const |
1029 | { | |
1030 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1031 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
1032 | } |
1033 | }; | |
bc464641 | 1034 | |
b40c57bd | 1035 | inline constexpr __remove_if_fn remove_if{}; |
bc464641 | 1036 | |
b40c57bd PP |
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> | |
55992626 PP |
1045 | operator()(_Iter __first, _Sent __last, |
1046 | const _Tp& __value, _Proj __proj = {}) const | |
b40c57bd | 1047 | { |
d91e7eab | 1048 | auto __pred = [&] (auto&& __arg) -> bool { |
b40c57bd PP |
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*> | |
15411a64 | 1060 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
1061 | operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const |
1062 | { | |
1063 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1064 | __value, std::move(__proj)); |
b40c57bd PP |
1065 | } |
1066 | }; | |
1067 | ||
1068 | inline constexpr __remove_fn remove{}; | |
1069 | ||
1070 | template<typename _Iter, typename _Out> | |
aa667c3f | 1071 | using remove_copy_if_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
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, | |
55992626 | 1081 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
1082 | { |
1083 | for (; __first != __last; ++__first) | |
a45fb21a | 1084 | if (!std::__invoke(__pred, std::__invoke(__proj, *__first))) |
bc464641 | 1085 | { |
b40c57bd PP |
1086 | *__result = *__first; |
1087 | ++__result; | |
bc464641 | 1088 | } |
b40c57bd PP |
1089 | return {std::move(__first), std::move(__result)}; |
1090 | } | |
bc464641 | 1091 | |
b40c57bd PP |
1092 | template<input_range _Range, weakly_incrementable _Out, |
1093 | typename _Proj = identity, | |
55992626 PP |
1094 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
1095 | _Pred> | |
b40c57bd | 1096 | requires indirectly_copyable<iterator_t<_Range>, _Out> |
15411a64 | 1097 | constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd | 1098 | operator()(_Range&& __r, _Out __result, |
55992626 | 1099 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
1100 | { |
1101 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
1102 | std::move(__result), |
1103 | std::move(__pred), std::move(__proj)); | |
b40c57bd PP |
1104 | } |
1105 | }; | |
bc464641 | 1106 | |
b40c57bd | 1107 | inline constexpr __remove_copy_if_fn remove_copy_if{}; |
bc464641 | 1108 | |
b40c57bd | 1109 | template<typename _Iter, typename _Out> |
aa667c3f | 1110 | using remove_copy_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
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, | |
55992626 | 1122 | const _Tp& __value, _Proj __proj = {}) const |
b40c57bd PP |
1123 | { |
1124 | for (; __first != __last; ++__first) | |
1125 | if (!(std::__invoke(__proj, *__first) == __value)) | |
bc464641 | 1126 | { |
b40c57bd PP |
1127 | *__result = *__first; |
1128 | ++__result; | |
bc464641 | 1129 | } |
b40c57bd PP |
1130 | return {std::move(__first), std::move(__result)}; |
1131 | } | |
bc464641 | 1132 | |
b40c57bd PP |
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*> | |
15411a64 | 1139 | constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd | 1140 | operator()(_Range&& __r, _Out __result, |
55992626 | 1141 | const _Tp& __value, _Proj __proj = {}) const |
b40c57bd PP |
1142 | { |
1143 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1144 | std::move(__result), __value, std::move(__proj)); |
b40c57bd PP |
1145 | } |
1146 | }; | |
bc464641 | 1147 | |
b40c57bd | 1148 | inline constexpr __remove_copy_fn remove_copy{}; |
bc464641 | 1149 | |
b40c57bd PP |
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> | |
55992626 PP |
1157 | operator()(_Iter __first, _Sent __last, |
1158 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
1159 | { |
1160 | __first = ranges::adjacent_find(__first, __last, __comp, __proj); | |
1161 | if (__first == __last) | |
1162 | return {__first, __first}; | |
bc464641 | 1163 | |
b40c57bd PP |
1164 | auto __dest = __first; |
1165 | ++__first; | |
1166 | while (++__first != __last) | |
a45fb21a JW |
1167 | if (!std::__invoke(__comp, |
1168 | std::__invoke(__proj, *__dest), | |
1169 | std::__invoke(__proj, *__first))) | |
b40c57bd PP |
1170 | *++__dest = std::move(*__first); |
1171 | return {++__dest, __first}; | |
1172 | } | |
bc464641 | 1173 | |
b40c57bd PP |
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>> | |
15411a64 | 1178 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
1179 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1180 | { | |
1181 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1182 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1183 | } |
1184 | }; | |
bc464641 | 1185 | |
b40c57bd | 1186 | inline constexpr __unique_fn unique{}; |
bc464641 | 1187 | |
0614bbbe PP |
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 | ||
b40c57bd | 1195 | template<typename _Iter, typename _Out> |
aa667c3f | 1196 | using unique_copy_result = in_out_result<_Iter, _Out>; |
bc464641 | 1197 | |
b40c57bd PP |
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> | |
0614bbbe | 1206 | || __detail::__can_reread_output<_Out, iter_value_t<_Iter>> |
b40c57bd PP |
1207 | || indirectly_copyable_storable<_Iter, _Out>) |
1208 | constexpr unique_copy_result<_Iter, _Out> | |
1209 | operator()(_Iter __first, _Sent __last, _Out __result, | |
55992626 | 1210 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
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) | |
a45fb21a JW |
1221 | if (!std::__invoke(__comp, |
1222 | std::__invoke(__proj, *__first), | |
1223 | std::__invoke(__proj, *__next))) | |
b40c57bd PP |
1224 | { |
1225 | __first = __next; | |
1226 | *++__result = *__first; | |
1227 | } | |
1228 | return {__next, std::move(++__result)}; | |
1229 | } | |
0614bbbe | 1230 | else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>) |
b40c57bd PP |
1231 | { |
1232 | *__result = *__first; | |
1233 | while (++__first != __last) | |
a45fb21a JW |
1234 | if (!std::__invoke(__comp, |
1235 | std::__invoke(__proj, *__result), | |
1236 | std::__invoke(__proj, *__first))) | |
b40c57bd PP |
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>> | |
0614bbbe | 1264 | || __detail::__can_reread_output<_Out, range_value_t<_Range>> |
b40c57bd | 1265 | || indirectly_copyable_storable<iterator_t<_Range>, _Out>) |
15411a64 | 1266 | constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd | 1267 | operator()(_Range&& __r, _Out __result, |
55992626 | 1268 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
1269 | { |
1270 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
1271 | std::move(__result), |
1272 | std::move(__comp), std::move(__proj)); | |
b40c57bd PP |
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>) | |
bc464641 | 1289 | { |
b40c57bd PP |
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; | |
bc464641 | 1301 | } |
b40c57bd PP |
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 | } | |
bc464641 | 1315 | |
b40c57bd PP |
1316 | template<bidirectional_range _Range> |
1317 | requires permutable<iterator_t<_Range>> | |
15411a64 | 1318 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1319 | operator()(_Range&& __r) const |
1320 | { | |
1321 | return (*this)(ranges::begin(__r), ranges::end(__r)); | |
1322 | } | |
1323 | }; | |
bc464641 | 1324 | |
b40c57bd | 1325 | inline constexpr __reverse_fn reverse{}; |
bc464641 PP |
1326 | |
1327 | template<typename _Iter, typename _Out> | |
aa667c3f | 1328 | using reverse_copy_result = in_out_result<_Iter, _Out>; |
bc464641 | 1329 | |
b40c57bd PP |
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 | } | |
14d8a5ae | 1346 | return {__i, std::move(__result)}; |
b40c57bd | 1347 | } |
bc464641 | 1348 | |
b40c57bd PP |
1349 | template<bidirectional_range _Range, weakly_incrementable _Out> |
1350 | requires indirectly_copyable<iterator_t<_Range>, _Out> | |
15411a64 | 1351 | constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd PP |
1352 | operator()(_Range&& __r, _Out __result) const |
1353 | { | |
1354 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1355 | std::move(__result)); |
b40c57bd PP |
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 | operator()(_Iter __first, _Iter __middle, _Sent __last) const | |
1366 | { | |
1367 | auto __lasti = ranges::next(__first, __last); | |
1368 | if (__first == __middle) | |
1369 | return {__lasti, __lasti}; | |
1370 | if (__last == __middle) | |
1371 | return {std::move(__first), std::move(__lasti)}; | |
1372 | ||
1373 | if constexpr (random_access_iterator<_Iter>) | |
1374 | { | |
1375 | auto __n = __lasti - __first; | |
1376 | auto __k = __middle - __first; | |
1377 | ||
1378 | if (__k == __n - __k) | |
1379 | { | |
1380 | ranges::swap_ranges(__first, __middle, __middle, __middle + __k); | |
1381 | return {std::move(__middle), std::move(__lasti)}; | |
1382 | } | |
1383 | ||
1384 | auto __p = __first; | |
1385 | auto __ret = __first + (__lasti - __middle); | |
1386 | ||
1387 | for (;;) | |
1388 | { | |
1389 | 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 | auto __q = __p + __k; | |
1402 | for (decltype(__n) __i = 0; __i < __n - __k; ++ __i) | |
1403 | { | |
1404 | ranges::iter_swap(__p, __q); | |
1405 | ++__p; | |
1406 | ++__q; | |
1407 | } | |
1408 | __n %= __k; | |
1409 | if (__n == 0) | |
1410 | return {std::move(__ret), std::move(__lasti)}; | |
1411 | ranges::swap(__n, __k); | |
1412 | __k = __n - __k; | |
1413 | } | |
1414 | else | |
1415 | { | |
1416 | __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 | auto __q = __p + __n; | |
1428 | __p = __q - __k; | |
1429 | for (decltype(__n) __i = 0; __i < __n - __k; ++ __i) | |
1430 | { | |
1431 | --__p; | |
1432 | --__q; | |
1433 | ranges::iter_swap(__p, __q); | |
1434 | } | |
1435 | __n %= __k; | |
1436 | if (__n == 0) | |
1437 | return {std::move(__ret), std::move(__lasti)}; | |
1438 | std::swap(__n, __k); | |
1439 | } | |
1440 | } | |
1441 | } | |
1442 | else if constexpr (bidirectional_iterator<_Iter>) | |
1443 | { | |
1444 | auto __tail = __lasti; | |
bc464641 | 1445 | |
b40c57bd PP |
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 | |
bc464641 | 1467 | { |
b40c57bd PP |
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)}; | |
bc464641 | 1493 | } |
b40c57bd | 1494 | } |
bc464641 | 1495 | |
b40c57bd PP |
1496 | template<forward_range _Range> |
1497 | requires permutable<iterator_t<_Range>> | |
15411a64 | 1498 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
1499 | operator()(_Range&& __r, iterator_t<_Range> __middle) const |
1500 | { | |
55992626 PP |
1501 | return (*this)(ranges::begin(__r), std::move(__middle), |
1502 | ranges::end(__r)); | |
b40c57bd PP |
1503 | } |
1504 | }; | |
bc464641 | 1505 | |
b40c57bd PP |
1506 | inline constexpr __rotate_fn rotate{}; |
1507 | ||
1508 | template<typename _Iter, typename _Out> | |
aa667c3f | 1509 | using rotate_copy_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
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> | |
55992626 PP |
1517 | operator()(_Iter __first, _Iter __middle, _Sent __last, |
1518 | _Out __result) const | |
b40c57bd PP |
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> | |
15411a64 | 1531 | constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out> |
b40c57bd PP |
1532 | operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result) const |
1533 | { | |
55992626 PP |
1534 | return (*this)(ranges::begin(__r), std::move(__middle), |
1535 | ranges::end(__r), std::move(__result)); | |
b40c57bd PP |
1536 | } |
1537 | }; | |
1538 | ||
1539 | inline constexpr __rotate_copy_fn rotate_copy{}; | |
1540 | ||
f3169941 PP |
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); | |
9c24e97a JW |
1557 | return _GLIBCXX_STD_A:: |
1558 | sample(std::move(__first), std::move(__lasti), std::move(__out), | |
1559 | __n, std::forward<_Gen>(__g)); | |
f3169941 PP |
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 | ||
b40c57bd PP |
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>> | |
15411a64 | 1618 | borrowed_iterator_t<_Range> |
b40c57bd PP |
1619 | operator()(_Range&& __r, _Gen&& __g) const |
1620 | { | |
1621 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1622 | std::forward<_Gen>(__g)); |
b40c57bd PP |
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 | |
55992626 PP |
1635 | operator()(_Iter __first, _Sent __last, |
1636 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
1637 | { |
1638 | auto __lasti = ranges::next(__first, __last); | |
1639 | std::push_heap(__first, __lasti, | |
bc464641 | 1640 | __detail::__make_comp_proj(__comp, __proj)); |
b40c57bd PP |
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> | |
15411a64 | 1647 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1648 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1649 | { | |
1650 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1651 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1652 | } |
1653 | }; | |
bc464641 | 1654 | |
b40c57bd PP |
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 | |
55992626 PP |
1663 | operator()(_Iter __first, _Sent __last, |
1664 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
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> | |
15411a64 | 1675 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1676 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1677 | { | |
1678 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1679 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1680 | } |
1681 | }; | |
bc464641 | 1682 | |
b40c57bd PP |
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 | |
55992626 PP |
1691 | operator()(_Iter __first, _Sent __last, |
1692 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
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> | |
15411a64 | 1703 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1704 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1705 | { | |
1706 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1707 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1708 | } |
1709 | }; | |
bc464641 | 1710 | |
b40c57bd PP |
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 | |
55992626 PP |
1719 | operator()(_Iter __first, _Sent __last, |
1720 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
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> | |
15411a64 | 1731 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1732 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1733 | { | |
1734 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1735 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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, | |
55992626 | 1749 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
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> | |
15411a64 | 1768 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1769 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1770 | { | |
1771 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1772 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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 | |
55992626 PP |
1785 | operator()(_Iter __first, _Sent __last, |
1786 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
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), | |
55992626 | 1802 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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 | |
55992626 PP |
1814 | operator()(_Iter __first, _Sent __last, |
1815 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
1816 | { |
1817 | auto __lasti = ranges::next(__first, __last); | |
9c24e97a JW |
1818 | _GLIBCXX_STD_A::sort(std::move(__first), __lasti, |
1819 | __detail::__make_comp_proj(__comp, __proj)); | |
b40c57bd PP |
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> | |
15411a64 | 1826 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
1827 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1828 | { | |
1829 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1830 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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, | |
55992626 | 1843 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
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> | |
15411a64 | 1854 | borrowed_iterator_t<_Range> |
b40c57bd PP |
1855 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
1856 | { | |
1857 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 1858 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
1859 | } |
1860 | }; | |
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, | |
55992626 | 1871 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
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) | |
bc464641 | 1879 | if (std::__invoke(__comp, |
b40c57bd PP |
1880 | std::__invoke(__proj, *__i), |
1881 | std::__invoke(__proj, *__first))) | |
bc464641 | 1882 | { |
b40c57bd PP |
1883 | ranges::pop_heap(__first, __middle, __comp, __proj); |
1884 | ranges::iter_swap(__middle-1, __i); | |
1885 | ranges::push_heap(__first, __middle, __comp, __proj); | |
bc464641 | 1886 | } |
b40c57bd PP |
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> | |
15411a64 | 1895 | constexpr borrowed_iterator_t<_Range> |
b40c57bd | 1896 | operator()(_Range&& __r, iterator_t<_Range> __middle, |
55992626 | 1897 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd | 1898 | { |
55992626 PP |
1899 | return (*this)(ranges::begin(__r), std::move(__middle), |
1900 | ranges::end(__r), | |
1901 | std::move(__comp), std::move(__proj)); | |
b40c57bd PP |
1902 | } |
1903 | }; | |
1904 | ||
1905 | inline constexpr __partial_sort_fn partial_sort{}; | |
1906 | ||
1907 | template<typename _Iter, typename _Out> | |
aa667c3f | 1908 | using partial_sort_copy_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
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, | |
55992626 PP |
1923 | _Iter2 __result_first, _Sent2 __result_last, |
1924 | _Comp __comp = {}, | |
1925 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
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))) | |
bc464641 | 1948 | { |
b40c57bd PP |
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); | |
bc464641 | 1954 | } |
b40c57bd PP |
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>> | |
15411a64 JW |
1968 | constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>, |
1969 | borrowed_iterator_t<_Range2>> | |
b40c57bd | 1970 | operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {}, |
55992626 | 1971 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const |
b40c57bd PP |
1972 | { |
1973 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 PP |
1974 | ranges::begin(__out), ranges::end(__out), |
1975 | std::move(__comp), | |
1976 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
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, | |
55992626 | 1990 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
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> | |
15411a64 | 2007 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
2008 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
2009 | { | |
2010 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2011 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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 | |
55992626 PP |
2024 | operator()(_Iter __first, _Sent __last, |
2025 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
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), | |
55992626 | 2046 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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, | |
55992626 | 2059 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2060 | { |
2061 | auto __lasti = ranges::next(__first, __last); | |
9c24e97a JW |
2062 | _GLIBCXX_STD_A::nth_element(std::move(__first), std::move(__nth), |
2063 | __lasti, | |
2064 | __detail::__make_comp_proj(__comp, __proj)); | |
b40c57bd PP |
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> | |
15411a64 | 2071 | constexpr borrowed_iterator_t<_Range> |
b40c57bd | 2072 | operator()(_Range&& __r, iterator_t<_Range> __nth, |
55992626 | 2073 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2074 | { |
2075 | return (*this)(ranges::begin(__r), std::move(__nth), | |
55992626 | 2076 | ranges::end(__r), std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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, | |
55992626 | 2090 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
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> | |
15411a64 | 2115 | constexpr borrowed_iterator_t<_Range> |
b40c57bd | 2116 | operator()(_Range&& __r, |
55992626 | 2117 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2118 | { |
2119 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2120 | __value, std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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, | |
55992626 | 2134 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
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> | |
15411a64 | 2159 | constexpr borrowed_iterator_t<_Range> |
b40c57bd | 2160 | operator()(_Range&& __r, |
55992626 | 2161 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2162 | { |
2163 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2164 | __value, std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2165 | } |
2166 | }; | |
bc464641 | 2167 | |
b40c57bd | 2168 | inline constexpr __upper_bound_fn upper_bound{}; |
bc464641 | 2169 | |
b40c57bd PP |
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, | |
55992626 | 2178 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2179 | { |
2180 | auto __len = ranges::distance(__first, __last); | |
bc464641 | 2181 | |
b40c57bd PP |
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)) | |
bc464641 | 2190 | { |
b40c57bd | 2191 | __first = __middle; |
bc464641 | 2192 | ++__first; |
b40c57bd PP |
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}; | |
bc464641 | 2209 | } |
b40c57bd PP |
2210 | } |
2211 | return {__first, __first}; | |
2212 | } | |
bc464641 | 2213 | |
b40c57bd PP |
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> | |
15411a64 | 2219 | constexpr borrowed_subrange_t<_Range> |
b40c57bd | 2220 | operator()(_Range&& __r, const _Tp& __value, |
55992626 | 2221 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2222 | { |
2223 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2224 | __value, std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2225 | } |
2226 | }; | |
bc464641 | 2227 | |
b40c57bd PP |
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, | |
55992626 | 2238 | const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2239 | { |
2240 | auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj); | |
2241 | if (__i == __last) | |
2242 | return false; | |
55992626 PP |
2243 | return !(bool)std::__invoke(__comp, __value, |
2244 | std::__invoke(__proj, *__i)); | |
b40c57bd PP |
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 = {}, | |
55992626 | 2254 | _Proj __proj = {}) const |
b40c57bd PP |
2255 | { |
2256 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2257 | __value, std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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 | |
55992626 PP |
2269 | operator()(_Iter __first, _Sent __last, |
2270 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd | 2271 | { |
55992626 PP |
2272 | __first = ranges::find_if_not(std::move(__first), __last, |
2273 | __pred, __proj); | |
b40c57bd PP |
2274 | if (__first == __last) |
2275 | return true; | |
2276 | ++__first; | |
2277 | return ranges::none_of(std::move(__first), std::move(__last), | |
bc464641 | 2278 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
2279 | } |
2280 | ||
2281 | template<input_range _Range, typename _Proj = identity, | |
55992626 PP |
2282 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
2283 | _Pred> | |
b40c57bd PP |
2284 | constexpr bool |
2285 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
2286 | { | |
2287 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2288 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
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> | |
55992626 PP |
2300 | operator()(_Iter __first, _Sent __last, |
2301 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
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)}; | |
55992626 PP |
2312 | else if (std::__invoke(__pred, |
2313 | std::__invoke(__proj, *__first))) | |
b40c57bd PP |
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) | |
d91e7eab | 2333 | return {__first, __first}; |
b40c57bd PP |
2334 | |
2335 | while (std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
2336 | if (++__first == __last) | |
d91e7eab | 2337 | return {__first, __first}; |
b40c57bd PP |
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, | |
55992626 PP |
2352 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
2353 | _Pred> | |
b40c57bd | 2354 | requires permutable<iterator_t<_Range>> |
15411a64 | 2355 | constexpr borrowed_subrange_t<_Range> |
b40c57bd PP |
2356 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const |
2357 | { | |
2358 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2359 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
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> | |
55992626 PP |
2372 | operator()(_Iter __first, _Sent __last, |
2373 | _Pred __pred, _Proj __proj = {}) const | |
b40c57bd PP |
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, | |
55992626 PP |
2383 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
2384 | _Pred> | |
b40c57bd | 2385 | requires permutable<iterator_t<_Range>> |
15411a64 | 2386 | borrowed_subrange_t<_Range> |
b40c57bd PP |
2387 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const |
2388 | { | |
2389 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2390 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
2391 | } |
2392 | }; | |
2393 | ||
2394 | inline constexpr __stable_partition_fn stable_partition{}; | |
bc464641 | 2395 | |
aa667c3f PP |
2396 | template<typename _Iter, typename _Out1, typename _Out2> |
2397 | struct in_out_out_result | |
bc464641 PP |
2398 | { |
2399 | [[no_unique_address]] _Iter in; | |
2400 | [[no_unique_address]] _Out1 out1; | |
aa667c3f | 2401 | [[no_unique_address]] _Out2 out2; |
bc464641 PP |
2402 | |
2403 | template<typename _IIter, typename _OOut1, typename _OOut2> | |
2404 | requires convertible_to<const _Iter&, _IIter> | |
2405 | && convertible_to<const _Out1&, _OOut1> | |
aa667c3f PP |
2406 | && convertible_to<const _Out2&, _OOut2> |
2407 | constexpr | |
2408 | operator in_out_out_result<_IIter, _OOut1, _OOut2>() const & | |
bc464641 PP |
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> | |
aa667c3f PP |
2414 | && convertible_to<_Out2, _OOut2> |
2415 | constexpr | |
2416 | operator in_out_out_result<_IIter, _OOut1, _OOut2>() && | |
bc464641 PP |
2417 | { return {std::move(in), std::move(out1), std::move(out2)}; } |
2418 | }; | |
2419 | ||
aa667c3f PP |
2420 | template<typename _Iter, typename _Out1, typename _Out2> |
2421 | using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>; | |
2422 | ||
b40c57bd PP |
2423 | struct __partition_copy_fn |
2424 | { | |
2425 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
14d8a5ae | 2426 | weakly_incrementable _Out1, weakly_incrementable _Out2, |
b40c57bd PP |
2427 | typename _Proj = identity, |
2428 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
2429 | requires indirectly_copyable<_Iter, _Out1> | |
14d8a5ae PP |
2430 | && indirectly_copyable<_Iter, _Out2> |
2431 | constexpr partition_copy_result<_Iter, _Out1, _Out2> | |
b40c57bd | 2432 | operator()(_Iter __first, _Sent __last, |
14d8a5ae | 2433 | _Out1 __out_true, _Out2 __out_false, |
55992626 | 2434 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
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 | ||
55992626 PP |
2448 | return {std::move(__first), |
2449 | std::move(__out_true), std::move(__out_false)}; | |
b40c57bd PP |
2450 | } |
2451 | ||
2452 | template<input_range _Range, weakly_incrementable _Out1, | |
14d8a5ae | 2453 | weakly_incrementable _Out2, |
b40c57bd | 2454 | typename _Proj = identity, |
55992626 PP |
2455 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
2456 | _Pred> | |
b40c57bd | 2457 | requires indirectly_copyable<iterator_t<_Range>, _Out1> |
14d8a5ae PP |
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, | |
55992626 | 2461 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
2462 | { |
2463 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
14d8a5ae | 2464 | std::move(__out_true), std::move(__out_false), |
55992626 | 2465 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
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, | |
55992626 | 2478 | _Pred __pred, _Proj __proj = {}) const |
b40c57bd PP |
2479 | { |
2480 | auto __len = ranges::distance(__first, __last); | |
2481 | ||
2482 | while (__len > 0) | |
bc464641 | 2483 | { |
b40c57bd PP |
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; | |
bc464641 | 2495 | } |
b40c57bd PP |
2496 | return __first; |
2497 | } | |
2498 | ||
2499 | template<forward_range _Range, typename _Proj = identity, | |
55992626 PP |
2500 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> |
2501 | _Pred> | |
15411a64 | 2502 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
2503 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const |
2504 | { | |
2505 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 2506 | std::move(__pred), std::move(__proj)); |
b40c57bd PP |
2507 | } |
2508 | }; | |
2509 | ||
2510 | inline constexpr __partition_point_fn partition_point{}; | |
2511 | ||
2512 | template<typename _Iter1, typename _Iter2, typename _Out> | |
aa667c3f | 2513 | using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>; |
b40c57bd PP |
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, | |
55992626 PP |
2524 | _Iter2 __first2, _Sent2 __last2, _Out __result, |
2525 | _Comp __comp = {}, | |
2526 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2527 | { |
2528 | while (__first1 != __last1 && __first2 != __last2) | |
bc464641 | 2529 | { |
b40c57bd PP |
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; | |
bc464641 | 2543 | } |
b40c57bd PP |
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 | } | |
bc464641 | 2551 | |
b40c57bd PP |
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> | |
15411a64 JW |
2557 | constexpr merge_result<borrowed_iterator_t<_Range1>, |
2558 | borrowed_iterator_t<_Range2>, | |
b40c57bd PP |
2559 | _Out> |
2560 | operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, | |
55992626 PP |
2561 | _Comp __comp = {}, |
2562 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2563 | { |
2564 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
2565 | ranges::begin(__r2), ranges::end(__r2), |
2566 | std::move(__result), std::move(__comp), | |
2567 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
2568 | } |
2569 | }; | |
bc464641 | 2570 | |
b40c57bd | 2571 | inline constexpr __merge_fn merge{}; |
bc464641 | 2572 | |
b40c57bd PP |
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, | |
55992626 | 2581 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
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 | } | |
bc464641 | 2588 | |
b40c57bd PP |
2589 | template<bidirectional_range _Range, |
2590 | typename _Comp = ranges::less, typename _Proj = identity> | |
2591 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 2592 | borrowed_iterator_t<_Range> |
b40c57bd | 2593 | operator()(_Range&& __r, iterator_t<_Range> __middle, |
55992626 | 2594 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
2595 | { |
2596 | return (*this)(ranges::begin(__r), std::move(__middle), | |
55992626 PP |
2597 | ranges::end(__r), |
2598 | std::move(__comp), std::move(__proj)); | |
b40c57bd PP |
2599 | } |
2600 | }; | |
bc464641 | 2601 | |
b40c57bd PP |
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 | |
55992626 PP |
2613 | operator()(_Iter1 __first1, _Sent1 __last1, |
2614 | _Iter2 __first2, _Sent2 __last2, | |
2615 | _Comp __comp = {}, | |
2616 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2617 | { |
2618 | while (__first1 != __last1 && __first2 != __last2) | |
bc464641 PP |
2619 | if (std::__invoke(__comp, |
2620 | std::__invoke(__proj2, *__first2), | |
2621 | std::__invoke(__proj1, *__first1))) | |
b40c57bd PP |
2622 | return false; |
2623 | else if (std::__invoke(__comp, | |
2624 | std::__invoke(__proj1, *__first1), | |
2625 | std::__invoke(__proj2, *__first2))) | |
2626 | ++__first1; | |
2627 | else | |
bc464641 | 2628 | { |
b40c57bd | 2629 | ++__first1; |
bc464641 PP |
2630 | ++__first2; |
2631 | } | |
b40c57bd PP |
2632 | |
2633 | return __first2 == __last2; | |
2634 | } | |
2635 | ||
55992626 PP |
2636 | template<input_range _Range1, input_range _Range2, |
2637 | typename _Proj1 = identity, typename _Proj2 = identity, | |
b40c57bd PP |
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 = {}, | |
55992626 | 2643 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const |
b40c57bd PP |
2644 | { |
2645 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
2646 | ranges::begin(__r2), ranges::end(__r2), |
2647 | std::move(__comp), | |
2648 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
2649 | } |
2650 | }; | |
2651 | ||
2652 | inline constexpr __includes_fn includes{}; | |
2653 | ||
2654 | template<typename _Iter1, typename _Iter2, typename _Out> | |
aa667c3f | 2655 | using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>; |
b40c57bd PP |
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> | |
55992626 PP |
2665 | operator()(_Iter1 __first1, _Sent1 __last1, |
2666 | _Iter2 __first2, _Sent2 __last2, | |
2667 | _Out __result, _Comp __comp = {}, | |
2668 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
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> | |
15411a64 JW |
2707 | constexpr set_union_result<borrowed_iterator_t<_Range1>, |
2708 | borrowed_iterator_t<_Range2>, _Out> | |
55992626 PP |
2709 | operator()(_Range1&& __r1, _Range2&& __r2, |
2710 | _Out __result, _Comp __comp = {}, | |
2711 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2712 | { |
2713 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
2714 | ranges::begin(__r2), ranges::end(__r2), |
2715 | std::move(__result), std::move(__comp), | |
2716 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
2717 | } |
2718 | }; | |
2719 | ||
2720 | inline constexpr __set_union_fn set_union{}; | |
2721 | ||
2722 | template<typename _Iter1, typename _Iter2, typename _Out> | |
aa667c3f | 2723 | using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>; |
b40c57bd PP |
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, | |
55992626 PP |
2734 | _Iter2 __first2, _Sent2 __last2, _Out __result, |
2735 | _Comp __comp = {}, | |
2736 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
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; | |
bc464641 PP |
2747 | else |
2748 | { | |
2749 | *__result = *__first1; | |
2750 | ++__first1; | |
b40c57bd PP |
2751 | ++__first2; |
2752 | ++__result; | |
bc464641 | 2753 | } |
b40c57bd PP |
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 | } | |
bc464641 | 2759 | |
b40c57bd PP |
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> | |
15411a64 JW |
2765 | constexpr set_intersection_result<borrowed_iterator_t<_Range1>, |
2766 | borrowed_iterator_t<_Range2>, _Out> | |
b40c57bd | 2767 | operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, |
55992626 PP |
2768 | _Comp __comp = {}, |
2769 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2770 | { |
2771 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
2772 | ranges::begin(__r2), ranges::end(__r2), |
2773 | std::move(__result), std::move(__comp), | |
2774 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
2775 | } |
2776 | }; | |
2777 | ||
2778 | inline constexpr __set_intersection_fn set_intersection{}; | |
2779 | ||
2780 | template<typename _Iter, typename _Out> | |
aa667c3f | 2781 | using set_difference_result = in_out_result<_Iter, _Out>; |
b40c57bd PP |
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, | |
55992626 PP |
2792 | _Iter2 __first2, _Sent2 __last2, _Out __result, |
2793 | _Comp __comp = {}, | |
2794 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
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))) | |
bc464641 | 2808 | ++__first2; |
b40c57bd PP |
2809 | else |
2810 | { | |
2811 | ++__first1; | |
2812 | ++__first2; | |
2813 | } | |
2814 | return ranges::copy(std::move(__first1), std::move(__last1), | |
2815 | std::move(__result)); | |
2816 | } | |
bc464641 | 2817 | |
b40c57bd PP |
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> | |
15411a64 | 2823 | constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out> |
b40c57bd | 2824 | operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, |
55992626 PP |
2825 | _Comp __comp = {}, |
2826 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2827 | { |
2828 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
55992626 PP |
2829 | ranges::begin(__r2), ranges::end(__r2), |
2830 | std::move(__result), std::move(__comp), | |
2831 | std::move(__proj1), std::move(__proj2)); | |
b40c57bd PP |
2832 | } |
2833 | }; | |
bc464641 | 2834 | |
b40c57bd | 2835 | inline constexpr __set_difference_fn set_difference{}; |
bc464641 PP |
2836 | |
2837 | template<typename _Iter1, typename _Iter2, typename _Out> | |
b40c57bd | 2838 | using set_symmetric_difference_result |
aa667c3f | 2839 | = in_in_out_result<_Iter1, _Iter2, _Out>; |
bc464641 | 2840 | |
b40c57bd PP |
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, | |
55992626 PP |
2850 | _Iter2 __first2, _Sent2 __last2, |
2851 | _Out __result, _Comp __comp = {}, | |
2852 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
2853 | { |
2854 | while (__first1 != __last1 && __first2 != __last2) | |
bc464641 PP |
2855 | if (std::__invoke(__comp, |
2856 | std::__invoke(__proj1, *__first1), | |
2857 | std::__invoke(__proj2, *__first2))) | |
2858 | { | |
2859 | *__result = *__first1; | |
2860 | ++__first1; | |
b40c57bd | 2861 | ++__result; |
bc464641 PP |
2862 | } |
2863 | else if (std::__invoke(__comp, | |
2864 | std::__invoke(__proj2, *__first2), | |
2865 | std::__invoke(__proj1, *__first1))) | |
2866 | { | |
2867 | *__result = *__first2; | |
2868 | ++__first2; | |
b40c57bd | 2869 | ++__result; |
bc464641 PP |
2870 | } |
2871 | else | |
2872 | { | |
bc464641 PP |
2873 | ++__first1; |
2874 | ++__first2; | |
2875 | } | |
b40c57bd PP |
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 | } | |
bc464641 | 2883 | |
b40c57bd PP |
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> | |
15411a64 JW |
2889 | constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>, |
2890 | borrowed_iterator_t<_Range2>, | |
b40c57bd PP |
2891 | _Out> |
2892 | operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, | |
55992626 PP |
2893 | _Comp __comp = {}, |
2894 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd | 2895 | { |
55992626 PP |
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)); | |
b40c57bd PP |
2900 | } |
2901 | }; | |
bc464641 | 2902 | |
b40c57bd PP |
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& | |
55992626 PP |
2911 | operator()(const _Tp& __a, const _Tp& __b, |
2912 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd | 2913 | { |
d91e7eab | 2914 | if (std::__invoke(__comp, |
b40c57bd PP |
2915 | std::__invoke(__proj, __b), |
2916 | std::__invoke(__proj, __a))) | |
2917 | return __b; | |
bc464641 | 2918 | else |
b40c57bd PP |
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) | |
bc464641 | 2935 | { |
b40c57bd PP |
2936 | auto __tmp = *__first; |
2937 | if (std::__invoke(__comp, | |
2938 | std::__invoke(__proj, __tmp), | |
2939 | std::__invoke(__proj, __result))) | |
2940 | __result = std::move(__tmp); | |
bc464641 | 2941 | } |
b40c57bd PP |
2942 | return __result; |
2943 | } | |
bc464641 | 2944 | |
b40c57bd PP |
2945 | template<copyable _Tp, typename _Proj = identity, |
2946 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
2947 | _Comp = ranges::less> | |
2948 | constexpr _Tp | |
55992626 PP |
2949 | operator()(initializer_list<_Tp> __r, |
2950 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
2951 | { |
2952 | return (*this)(ranges::subrange(__r), | |
55992626 | 2953 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
2954 | } |
2955 | }; | |
bc464641 | 2956 | |
b40c57bd PP |
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& | |
55992626 PP |
2965 | operator()(const _Tp& __a, const _Tp& __b, |
2966 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd | 2967 | { |
d91e7eab | 2968 | if (std::__invoke(__comp, |
b40c57bd PP |
2969 | std::__invoke(__proj, __a), |
2970 | std::__invoke(__proj, __b))) | |
2971 | return __b; | |
bc464641 | 2972 | else |
b40c57bd PP |
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) | |
bc464641 | 2989 | { |
b40c57bd PP |
2990 | auto __tmp = *__first; |
2991 | if (std::__invoke(__comp, | |
2992 | std::__invoke(__proj, __result), | |
2993 | std::__invoke(__proj, __tmp))) | |
2994 | __result = std::move(__tmp); | |
bc464641 | 2995 | } |
b40c57bd PP |
2996 | return __result; |
2997 | } | |
bc464641 | 2998 | |
b40c57bd PP |
2999 | template<copyable _Tp, typename _Proj = identity, |
3000 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
3001 | _Comp = ranges::less> | |
3002 | constexpr _Tp | |
55992626 PP |
3003 | operator()(initializer_list<_Tp> __r, |
3004 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
3005 | { |
3006 | return (*this)(ranges::subrange(__r), | |
55992626 | 3007 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3008 | } |
3009 | }; | |
bc464641 | 3010 | |
b40c57bd | 3011 | inline constexpr __max_fn max{}; |
bc464641 | 3012 | |
f3169941 PP |
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 | ||
bc464641 | 3037 | template<typename _Tp> |
aa667c3f | 3038 | struct min_max_result |
bc464641 PP |
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> | |
aa667c3f PP |
3045 | constexpr |
3046 | operator min_max_result<_Tp2>() const & | |
bc464641 PP |
3047 | { return {min, max}; } |
3048 | ||
3049 | template<typename _Tp2> | |
3050 | requires convertible_to<_Tp, _Tp2> | |
aa667c3f PP |
3051 | constexpr |
3052 | operator min_max_result<_Tp2>() && | |
bc464641 PP |
3053 | { return {std::move(min), std::move(max)}; } |
3054 | }; | |
3055 | ||
aa667c3f PP |
3056 | template<typename _Tp> |
3057 | using minmax_result = min_max_result<_Tp>; | |
3058 | ||
b40c57bd PP |
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&> | |
55992626 PP |
3065 | operator()(const _Tp& __a, const _Tp& __b, |
3066 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd | 3067 | { |
d91e7eab | 3068 | if (std::__invoke(__comp, |
b40c57bd PP |
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> | |
cc9c94d4 | 3079 | requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*> |
b40c57bd PP |
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); | |
cc9c94d4 | 3086 | auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); |
b40c57bd | 3087 | minmax_result<range_value_t<_Range>> __result = {*__first, *__first}; |
cc9c94d4 PP |
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 | } | |
b40c57bd PP |
3100 | while (++__first != __last) |
3101 | { | |
cc9c94d4 PP |
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 | } | |
b40c57bd PP |
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> | |
55992626 PP |
3140 | operator()(initializer_list<_Tp> __r, |
3141 | _Comp __comp = {}, _Proj __proj = {}) const | |
b40c57bd PP |
3142 | { |
3143 | return (*this)(ranges::subrange(__r), | |
55992626 | 3144 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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, | |
55992626 | 3158 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
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 | } | |
bc464641 | 3171 | return __first; |
b40c57bd | 3172 | } |
bc464641 | 3173 | |
b40c57bd PP |
3174 | template<forward_range _Range, typename _Proj = identity, |
3175 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
3176 | _Comp = ranges::less> | |
15411a64 | 3177 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
3178 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
3179 | { | |
3180 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 3181 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
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, | |
55992626 | 3195 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
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 | } | |
bc464641 | 3208 | return __first; |
b40c57bd | 3209 | } |
bc464641 | 3210 | |
b40c57bd PP |
3211 | template<forward_range _Range, typename _Proj = identity, |
3212 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
3213 | _Comp = ranges::less> | |
15411a64 | 3214 | constexpr borrowed_iterator_t<_Range> |
b40c57bd PP |
3215 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
3216 | { | |
3217 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 3218 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3219 | } |
3220 | }; | |
3221 | ||
3222 | inline constexpr __max_element_fn max_element{}; | |
bc464641 PP |
3223 | |
3224 | template<typename _Iter> | |
aa667c3f | 3225 | using minmax_element_result = min_max_result<_Iter>; |
bc464641 | 3226 | |
b40c57bd PP |
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, | |
55992626 | 3235 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd | 3236 | { |
cc9c94d4 | 3237 | auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); |
b40c57bd | 3238 | minmax_element_result<_Iter> __result = {__first, __first}; |
cc9c94d4 PP |
3239 | if (__first == __last || ++__first == __last) |
3240 | return __result; | |
3241 | else | |
b40c57bd | 3242 | { |
cc9c94d4 PP |
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 | } | |
b40c57bd PP |
3281 | } |
3282 | return __result; | |
3283 | } | |
bc464641 | 3284 | |
b40c57bd PP |
3285 | template<forward_range _Range, typename _Proj = identity, |
3286 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
3287 | _Comp = ranges::less> | |
15411a64 | 3288 | constexpr minmax_element_result<borrowed_iterator_t<_Range>> |
b40c57bd PP |
3289 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
3290 | { | |
3291 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 3292 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3293 | } |
3294 | }; | |
bc464641 | 3295 | |
b40c57bd | 3296 | inline constexpr __minmax_element_fn minmax_element{}; |
bc464641 | 3297 | |
b40c57bd PP |
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, | |
55992626 PP |
3308 | _Iter2 __first2, _Sent2 __last2, |
3309 | _Comp __comp = {}, | |
3310 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
b40c57bd PP |
3311 | { |
3312 | if constexpr (__detail::__is_normal_iterator<_Iter1> | |
a73051a0 PP |
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(), | |
55992626 PP |
3322 | std::move(__comp), |
3323 | std::move(__proj1), std::move(__proj2)); | |
93b8cfce | 3324 | else |
b40c57bd | 3325 | { |
93b8cfce PP |
3326 | constexpr bool __sized_iters |
3327 | = (sized_sentinel_for<_Sent1, _Iter1> | |
3328 | && sized_sentinel_for<_Sent2, _Iter2>); | |
3329 | if constexpr (__sized_iters) | |
b40c57bd | 3330 | { |
93b8cfce PP |
3331 | using _ValueType1 = iter_value_t<_Iter1>; |
3332 | using _ValueType2 = iter_value_t<_Iter2>; | |
ce33801f PP |
3333 | // This condition is consistent with the one in |
3334 | // __lexicographical_compare_aux in <bits/stl_algobase.h>. | |
93b8cfce | 3335 | constexpr bool __use_memcmp |
2f983fa6 | 3336 | = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value |
462f6c20 JW |
3337 | && __ptr_to_nonvolatile<_Iter1> |
3338 | && __ptr_to_nonvolatile<_Iter2> | |
93b8cfce PP |
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) | |
b40c57bd | 3344 | { |
113f0a63 JW |
3345 | const auto __d1 = __last1 - __first1; |
3346 | const auto __d2 = __last2 - __first2; | |
3347 | ||
93b8cfce | 3348 | if (const auto __len = std::min(__d1, __d2)) |
b40c57bd | 3349 | { |
93b8cfce PP |
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 | } | |
b40c57bd | 3366 | } |
113f0a63 | 3367 | return __d1 < __d2; |
b40c57bd | 3368 | } |
b40c57bd | 3369 | } |
b40c57bd | 3370 | |
93b8cfce PP |
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; | |
b40c57bd | 3384 | } |
b40c57bd PP |
3385 | } |
3386 | ||
55992626 PP |
3387 | template<input_range _Range1, input_range _Range2, |
3388 | typename _Proj1 = identity, typename _Proj2 = identity, | |
b40c57bd PP |
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 = {}, | |
55992626 | 3394 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const |
b40c57bd | 3395 | { |
55992626 PP |
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)); | |
b40c57bd | 3400 | } |
462f6c20 JW |
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>>; | |
b40c57bd PP |
3406 | }; |
3407 | ||
3408 | inline constexpr __lexicographical_compare_fn lexicographical_compare; | |
bc464641 PP |
3409 | |
3410 | template<typename _Iter> | |
aa667c3f | 3411 | struct in_found_result |
bc464641 | 3412 | { |
aa667c3f | 3413 | [[no_unique_address]] _Iter in; |
bc464641 | 3414 | bool found; |
aa667c3f PP |
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}; } | |
bc464641 PP |
3427 | }; |
3428 | ||
aa667c3f PP |
3429 | template<typename _Iter> |
3430 | using next_permutation_result = in_found_result<_Iter>; | |
3431 | ||
b40c57bd PP |
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, | |
55992626 | 3439 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
3440 | { |
3441 | if (__first == __last) | |
aa667c3f | 3442 | return {std::move(__first), false}; |
bc464641 | 3443 | |
b40c57bd PP |
3444 | auto __i = __first; |
3445 | ++__i; | |
3446 | if (__i == __last) | |
aa667c3f | 3447 | return {std::move(__i), false}; |
bc464641 | 3448 | |
b40c57bd PP |
3449 | auto __lasti = ranges::next(__first, __last); |
3450 | __i = __lasti; | |
3451 | --__i; | |
bc464641 | 3452 | |
b40c57bd PP |
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); | |
aa667c3f | 3468 | return {std::move(__lasti), true}; |
b40c57bd PP |
3469 | } |
3470 | if (__i == __first) | |
3471 | { | |
3472 | ranges::reverse(__first, __last); | |
aa667c3f | 3473 | return {std::move(__lasti), false}; |
b40c57bd PP |
3474 | } |
3475 | } | |
3476 | } | |
bc464641 | 3477 | |
b40c57bd PP |
3478 | template<bidirectional_range _Range, typename _Comp = ranges::less, |
3479 | typename _Proj = identity> | |
3480 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 3481 | constexpr next_permutation_result<borrowed_iterator_t<_Range>> |
b40c57bd PP |
3482 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
3483 | { | |
3484 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 3485 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3486 | } |
3487 | }; | |
3488 | ||
3489 | inline constexpr __next_permutation_fn next_permutation{}; | |
bc464641 PP |
3490 | |
3491 | template<typename _Iter> | |
aa667c3f | 3492 | using prev_permutation_result = in_found_result<_Iter>; |
bc464641 | 3493 | |
b40c57bd PP |
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, | |
55992626 | 3501 | _Comp __comp = {}, _Proj __proj = {}) const |
b40c57bd PP |
3502 | { |
3503 | if (__first == __last) | |
aa667c3f | 3504 | return {std::move(__first), false}; |
bc464641 | 3505 | |
b40c57bd PP |
3506 | auto __i = __first; |
3507 | ++__i; | |
3508 | if (__i == __last) | |
aa667c3f | 3509 | return {std::move(__i), false}; |
bc464641 | 3510 | |
b40c57bd PP |
3511 | auto __lasti = ranges::next(__first, __last); |
3512 | __i = __lasti; | |
3513 | --__i; | |
bc464641 | 3514 | |
b40c57bd PP |
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); | |
aa667c3f | 3530 | return {std::move(__lasti), true}; |
b40c57bd PP |
3531 | } |
3532 | if (__i == __first) | |
3533 | { | |
3534 | ranges::reverse(__first, __last); | |
aa667c3f | 3535 | return {std::move(__lasti), false}; |
b40c57bd PP |
3536 | } |
3537 | } | |
3538 | } | |
bc464641 | 3539 | |
b40c57bd PP |
3540 | template<bidirectional_range _Range, typename _Comp = ranges::less, |
3541 | typename _Proj = identity> | |
3542 | requires sortable<iterator_t<_Range>, _Comp, _Proj> | |
15411a64 | 3543 | constexpr prev_permutation_result<borrowed_iterator_t<_Range>> |
b40c57bd PP |
3544 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const |
3545 | { | |
3546 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
55992626 | 3547 | std::move(__comp), std::move(__proj)); |
b40c57bd PP |
3548 | } |
3549 | }; | |
3550 | ||
3551 | inline constexpr __prev_permutation_fn prev_permutation{}; | |
bc464641 PP |
3552 | |
3553 | } // namespace ranges | |
c5eab4ed | 3554 | |
56772f62 | 3555 | #define __cpp_lib_shift 201806L |
23f75da9 JW |
3556 | template<typename _ForwardIterator> |
3557 | constexpr _ForwardIterator | |
3558 | shift_left(_ForwardIterator __first, _ForwardIterator __last, | |
3559 | typename iterator_traits<_ForwardIterator>::difference_type __n) | |
c5eab4ed PP |
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 | ||
23f75da9 JW |
3571 | template<typename _ForwardIterator> |
3572 | constexpr _ForwardIterator | |
3573 | shift_right(_ForwardIterator __first, _ForwardIterator __last, | |
3574 | typename iterator_traits<_ForwardIterator>::difference_type __n) | |
c5eab4ed PP |
3575 | { |
3576 | __glibcxx_assert(__n >= 0); | |
3577 | if (__n == 0) | |
3578 | return __first; | |
3579 | ||
23f75da9 JW |
3580 | using _Cat |
3581 | = typename iterator_traits<_ForwardIterator>::iterator_category; | |
c5eab4ed PP |
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. | |
cc9c94d4 | 3607 | std::move(std::move(__first), std::move(__dest_head), __result); |
c5eab4ed PP |
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 | ||
bc464641 PP |
3647 | _GLIBCXX_END_NAMESPACE_VERSION |
3648 | } // namespace std | |
3649 | #endif // concepts | |
3650 | #endif // C++20 | |
3651 | #endif // _RANGES_ALGO_H |