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