1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _PSTL_GLUE_ALGORITHM_IMPL_H
11#define _PSTL_GLUE_ALGORITHM_IMPL_H
12
13#include <functional>
14
15#include "pstl_config.h"
16
17#include "execution_defs.h"
18#include "utils.h"
19#include "algorithm_fwd.h"
20#include "numeric_fwd.h" /* count and count_if use __pattern_transform_reduce */
21
22#include "execution_impl.h"
23
24_PSTL_HIDE_FROM_ABI_PUSH
25
26namespace std
27{
28
29// [alg.any_of]
30
31template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
32__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
33any_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
34{
35 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
36
37 return __pstl::__internal::__pattern_any_of(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
38 __pred);
39}
40
41// [alg.all_of]
42
43template <class _ExecutionPolicy, class _ForwardIterator, class _Pred>
44__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
45all_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred)
46{
47 return !std::any_of(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::not_fn(__pred));
48}
49
50// [alg.none_of]
51
52template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
53__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
54none_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
55{
56 return !std::any_of(std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred);
57}
58
59// [alg.foreach]
60
61template <class _ExecutionPolicy, class _ForwardIterator, class _Function>
62__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
63for_each(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Function __f)
64{
65 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
66
67 __pstl::__internal::__pattern_walk1(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __f);
68}
69
70template <class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Function>
71__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
72for_each_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Size __n, _Function __f)
73{
74 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
75
76 return __pstl::__internal::__pattern_walk1_n(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __n,
77 __f);
78}
79
80// [alg.find]
81
82template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
83__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
84find_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
85{
86 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
87
88 return __pstl::__internal::__pattern_find_if(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
89 __last, __pred);
90}
91
92template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
93__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
94find_if_not(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
95{
96 return std::find_if(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::not_fn(__pred));
97}
98
99template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
100__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
101find(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
102{
103 return std::find_if(std::forward<_ExecutionPolicy>(__exec), __first, __last,
104 __pstl::__internal::__equal_value<_Tp>(__value));
105}
106
107// [alg.find.end]
108template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
109__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator1>
110find_end(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first,
111 _ForwardIterator2 __s_last, _BinaryPredicate __pred)
112{
113 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __s_first);
114
115 return __pstl::__internal::__pattern_find_end(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
116 __last, __s_first, __s_last, __pred);
117}
118
119template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
120__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator1>
121find_end(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first,
122 _ForwardIterator2 __s_last)
123{
124 return std::find_end(std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __s_last,
125 std::equal_to<>());
126}
127
128// [alg.find_first_of]
129template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
130__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator1>
131find_first_of(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
132 _ForwardIterator2 __s_first, _ForwardIterator2 __s_last, _BinaryPredicate __pred)
133{
134 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __s_first);
135
136 return __pstl::__internal::__pattern_find_first_of(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
137 __last, __s_first, __s_last, __pred);
138}
139
140template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
141__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator1>
142find_first_of(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
143 _ForwardIterator2 __s_first, _ForwardIterator2 __s_last)
144{
145 return std::find_first_of(std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __s_last,
146 std::equal_to<>());
147}
148
149// [alg.adjacent_find]
150template <class _ExecutionPolicy, class _ForwardIterator>
151__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
152adjacent_find(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last)
153{
154 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
155
156 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
157 return __pstl::__internal::__pattern_adjacent_find(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
158 __last, std::equal_to<_ValueType>(), /*first_semantic*/ false);
159}
160
161template <class _ExecutionPolicy, class _ForwardIterator, class _BinaryPredicate>
162__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
163adjacent_find(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
164{
165 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
166 return __pstl::__internal::__pattern_adjacent_find(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
167 __last, __pred, /*first_semantic*/ false);
168}
169
170// [alg.count]
171
172// Implementation note: count and count_if call the pattern directly instead of calling std::transform_reduce
173// so that we do not have to include <numeric>.
174
175template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
176__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy,
177 typename iterator_traits<_ForwardIterator>::difference_type>
178count(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
179{
180 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
181
182 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
183 return __pstl::__internal::__pattern_count(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
184 [&__value](const _ValueType& __x) { return __value == __x; });
185}
186
187template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
188__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy,
189 typename iterator_traits<_ForwardIterator>::difference_type>
190count_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
191{
192 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
193 return __pstl::__internal::__pattern_count(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
194 __pred);
195}
196
197// [alg.search]
198
199template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
200__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator1>
201search(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first,
202 _ForwardIterator2 __s_last, _BinaryPredicate __pred)
203{
204 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __s_first);
205
206 return __pstl::__internal::__pattern_search(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
207 __s_first, __s_last, __pred);
208}
209
210template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
211__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator1>
212search(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first,
213 _ForwardIterator2 __s_last)
214{
215 return std::search(std::forward<_ExecutionPolicy>(__exec), __first, __last, __s_first, __s_last, std::equal_to<>());
216}
217
218template <class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
219__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
220search_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Size __count,
221 const _Tp& __value, _BinaryPredicate __pred)
222{
223 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
224
225 return __pstl::__internal::__pattern_search_n(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
226 __last, __count, __value, __pred);
227}
228
229template <class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Tp>
230__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
231search_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Size __count,
232 const _Tp& __value)
233{
234 return std::search_n(std::forward<_ExecutionPolicy>(__exec), __first, __last, __count, __value,
235 std::equal_to<typename iterator_traits<_ForwardIterator>::value_type>());
236}
237
238// [alg.copy]
239
240template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
241__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
242copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result)
243{
244 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
245
246 using __is_vector = typename decltype(__dispatch_tag)::__is_vector;
247
248 return __pstl::__internal::__pattern_walk2_brick(
249 __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __result,
250 [](_ForwardIterator1 __begin, _ForwardIterator1 __end, _ForwardIterator2 __res)
251 { return __pstl::__internal::__brick_copy(__begin, __end, __res, __is_vector{}); });
252}
253
254template <class _ExecutionPolicy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
255__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
256copy_n(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result)
257{
258 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
259
260 using __is_vector = typename decltype(__dispatch_tag)::__is_vector;
261
262 return __pstl::__internal::__pattern_walk2_brick_n(
263 __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __n, __result,
264 [](_ForwardIterator1 __begin, _Size __sz, _ForwardIterator2 __res)
265 { return __pstl::__internal::__brick_copy_n(__begin, __sz, __res, __is_vector{}); });
266}
267
268template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
269__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
270copy_if(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result,
271 _Predicate __pred)
272{
273 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
274
275 return __pstl::__internal::__pattern_copy_if(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
276 __last, __result, __pred);
277}
278
279// [alg.swap]
280
281template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
282__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
283swap_ranges(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
284 _ForwardIterator2 __first2)
285{
286 typedef typename iterator_traits<_ForwardIterator1>::reference _ReferenceType1;
287 typedef typename iterator_traits<_ForwardIterator2>::reference _ReferenceType2;
288
289 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2);
290
291 return __pstl::__internal::__pattern_walk2(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1,
292 __last1, __first2,
293 [](_ReferenceType1 __x, _ReferenceType2 __y)
294 {
295 using std::swap;
296 swap(__x, __y);
297 });
298}
299
300// [alg.transform]
301
302template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _UnaryOperation>
303__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
304transform(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result,
305 _UnaryOperation __op)
306{
307 typedef typename iterator_traits<_ForwardIterator1>::reference _InputType;
308 typedef typename iterator_traits<_ForwardIterator2>::reference _OutputType;
309
310 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
311
312 return __pstl::__internal::__pattern_walk2(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
313 __result,
314 [__op](_InputType __x, _OutputType __y) mutable { __y = __op(__x); });
315}
316
317template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator,
318 class _BinaryOperation>
319__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
320transform(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
321 _ForwardIterator __result, _BinaryOperation __op)
322{
323 typedef typename iterator_traits<_ForwardIterator1>::reference _Input1Type;
324 typedef typename iterator_traits<_ForwardIterator2>::reference _Input2Type;
325 typedef typename iterator_traits<_ForwardIterator>::reference _OutputType;
326
327 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2, __result);
328
329 return __pstl::__internal::__pattern_walk3(
330 __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __result,
331 [__op](_Input1Type x, _Input2Type y, _OutputType z) mutable { z = __op(x, y); });
332}
333
334// [alg.replace]
335
336template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate, class _Tp>
337__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
338replace_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred,
339 const _Tp& __new_value)
340{
341 typedef typename iterator_traits<_ForwardIterator>::reference _ElementType;
342
343 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
344
345 __pstl::__internal::__pattern_walk1(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
346 [&__pred, &__new_value](_ElementType __elem)
347 {
348 if (__pred(__elem))
349 {
350 __elem = __new_value;
351 }
352 });
353}
354
355template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
356__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
357replace(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value,
358 const _Tp& __new_value)
359{
360 std::replace_if(std::forward<_ExecutionPolicy>(__exec), __first, __last,
361 __pstl::__internal::__equal_value<_Tp>(__old_value), __new_value);
362}
363
364template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _UnaryPredicate, class _Tp>
365__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
366replace_copy_if(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
367 _ForwardIterator2 __result, _UnaryPredicate __pred, const _Tp& __new_value)
368{
369 typedef typename iterator_traits<_ForwardIterator1>::reference _InputType;
370 typedef typename iterator_traits<_ForwardIterator2>::reference _OutputType;
371
372 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
373
374 return __pstl::__internal::__pattern_walk2(
375 __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __result,
376 [__pred, &__new_value](_InputType __x, _OutputType __y) mutable { __y = __pred(__x) ? __new_value : __x; });
377}
378
379template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
380__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
381replace_copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result,
382 const _Tp& __old_value, const _Tp& __new_value)
383{
384 return std::replace_copy_if(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result,
385 __pstl::__internal::__equal_value<_Tp>(__old_value), __new_value);
386}
387
388// [alg.fill]
389
390template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
391__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
392fill(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
393{
394 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
395
396 __pstl::__internal::__pattern_fill(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
397 __value);
398}
399
400template <class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Tp>
401__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
402fill_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Size __count, const _Tp& __value)
403{
404 if (__count <= 0)
405 return __first;
406
407 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
408
409 return __pstl::__internal::__pattern_fill_n(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
410 __count, __value);
411}
412
413// [alg.generate]
414template <class _ExecutionPolicy, class _ForwardIterator, class _Generator>
415__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
416generate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Generator __g)
417{
418 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
419
420 __pstl::__internal::__pattern_generate(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
421 __g);
422}
423
424template <class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Generator>
425__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
426generate_n(_ExecutionPolicy&& __exec, _ForwardIterator __first, _Size __count, _Generator __g)
427{
428 if (__count <= 0)
429 return __first;
430
431 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
432
433 return __pstl::__internal::__pattern_generate_n(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
434 __count, __g);
435}
436
437// [alg.remove]
438
439template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
440__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
441remove_copy_if(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
442 _ForwardIterator2 __result, _Predicate __pred)
443{
444 return std::copy_if(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result, std::not_fn(__pred));
445}
446
447template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
448__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
449remove_copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result,
450 const _Tp& __value)
451{
452 return std::copy_if(std::forward<_ExecutionPolicy>(__exec), __first, __last, __result,
453 __pstl::__internal::__not_equal_value<_Tp>(__value));
454}
455
456template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate>
457__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
458remove_if(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred)
459{
460 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
461
462 return __pstl::__internal::__pattern_remove_if(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
463 __last, __pred);
464}
465
466template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
467__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
468remove(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
469{
470 return std::remove_if(std::forward<_ExecutionPolicy>(__exec), __first, __last,
471 __pstl::__internal::__equal_value<_Tp>(__value));
472}
473
474// [alg.unique]
475
476template <class _ExecutionPolicy, class _ForwardIterator, class _BinaryPredicate>
477__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
478unique(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
479{
480 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
481
482 return __pstl::__internal::__pattern_unique(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
483 __pred);
484}
485
486template <class _ExecutionPolicy, class _ForwardIterator>
487__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
488unique(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last)
489{
490 return std::unique(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::equal_to<>());
491}
492
493template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
494__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
495unique_copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result,
496 _BinaryPredicate __pred)
497{
498 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
499
500 return __pstl::__internal::__pattern_unique_copy(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
501 __last, __result, __pred);
502}
503
504template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
505__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
506unique_copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result)
507{
508 return std::unique_copy(__exec, __first, __last, __result, std::equal_to<>());
509}
510
511// [alg.reverse]
512
513template <class _ExecutionPolicy, class _BidirectionalIterator>
514__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
515reverse(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last)
516{
517 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
518
519 __pstl::__internal::__pattern_reverse(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last);
520}
521
522template <class _ExecutionPolicy, class _BidirectionalIterator, class _ForwardIterator>
523__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
524reverse_copy(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last,
525 _ForwardIterator __d_first)
526{
527 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __d_first);
528
529 return __pstl::__internal::__pattern_reverse_copy(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
530 __last, __d_first);
531}
532
533// [alg.rotate]
534
535template <class _ExecutionPolicy, class _ForwardIterator>
536__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
537rotate(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
538{
539 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
540
541 return __pstl::__internal::__pattern_rotate(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
542 __middle, __last);
543}
544
545template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
546__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
547rotate_copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __middle, _ForwardIterator1 __last,
548 _ForwardIterator2 __result)
549{
550 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
551
552 return __pstl::__internal::__pattern_rotate_copy(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
553 __middle, __last, __result);
554}
555
556// [alg.partitions]
557
558template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate>
559__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
560is_partitioned(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred)
561{
562 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
563 return __pstl::__internal::__pattern_is_partitioned(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
564 __last, __pred);
565}
566
567template <class _ExecutionPolicy, class _ForwardIterator, class _UnaryPredicate>
568__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
569partition(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _UnaryPredicate __pred)
570{
571 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
572
573 return __pstl::__internal::__pattern_partition(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
574 __last, __pred);
575}
576
577template <class _ExecutionPolicy, class _BidirectionalIterator, class _UnaryPredicate>
578__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _BidirectionalIterator>
579stable_partition(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __last,
580 _UnaryPredicate __pred)
581{
582 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
583 return __pstl::__internal::__pattern_stable_partition(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec),
584 __first, __last, __pred);
585}
586
587template <class _ExecutionPolicy, class _ForwardIterator, class _ForwardIterator1, class _ForwardIterator2,
588 class _UnaryPredicate>
589__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, std::pair<_ForwardIterator1, _ForwardIterator2>>
590partition_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last,
591 _ForwardIterator1 __out_true, _ForwardIterator2 __out_false, _UnaryPredicate __pred)
592{
593 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __out_true, __out_false);
594
595 return __pstl::__internal::__pattern_partition_copy(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
596 __last, __out_true, __out_false, __pred);
597}
598
599// [alg.sort]
600
601template <class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
602__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
603sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
604{
605 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
606
607 typedef typename iterator_traits<_RandomAccessIterator>::value_type _InputType;
608 return __pstl::__internal::__pattern_sort(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
609 __comp, typename std::is_move_constructible<_InputType>::type());
610}
611
612template <class _ExecutionPolicy, class _RandomAccessIterator>
613__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
614sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last)
615{
616 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _InputType;
617 std::sort(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::less<_InputType>());
618}
619
620// [stable.sort]
621
622template <class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
623__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
624stable_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
625{
626 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
627
628 return __pstl::__internal::__pattern_stable_sort(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
629 __last, __comp);
630}
631
632template <class _ExecutionPolicy, class _RandomAccessIterator>
633__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
634stable_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last)
635{
636 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _InputType;
637 std::stable_sort(__exec, __first, __last, std::less<_InputType>());
638}
639
640// [mismatch]
641
642template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
643__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, std::pair<_ForwardIterator1, _ForwardIterator2>>
644mismatch(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
645 _ForwardIterator2 __last2, _BinaryPredicate __pred)
646{
647 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2);
648
649 return __pstl::__internal::__pattern_mismatch(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1,
650 __last1, __first2, __last2, __pred);
651}
652
653template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
654__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, std::pair<_ForwardIterator1, _ForwardIterator2>>
655mismatch(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
656 _BinaryPredicate __pred)
657{
658 return std::mismatch(__exec, __first1, __last1, __first2, std::next(__first2, std::distance(__first1, __last1)),
659 __pred);
660}
661
662template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
663__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, std::pair<_ForwardIterator1, _ForwardIterator2>>
664mismatch(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
665 _ForwardIterator2 __last2)
666{
667 return std::mismatch(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2,
668 std::equal_to<>());
669}
670
671template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
672__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, std::pair<_ForwardIterator1, _ForwardIterator2>>
673mismatch(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
674{
675 //TODO: to get rid of "distance"
676 return std::mismatch(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2,
677 std::next(__first2, std::distance(__first1, __last1)));
678}
679
680// [alg.equal]
681
682template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
683__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
684equal(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
685 _BinaryPredicate __p)
686{
687 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2);
688
689 return __pstl::__internal::__pattern_equal(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1,
690 __last1, __first2, __p);
691}
692
693template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
694__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
695equal(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
696{
697 return std::equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, std::equal_to<>());
698}
699
700template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
701__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
702equal(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
703 _ForwardIterator2 __last2, _BinaryPredicate __p)
704{
705 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2);
706
707 return __pstl::__internal::__pattern_equal(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1,
708 __last1, __first2, __last2, __p);
709}
710
711template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
712__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
713equal(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
714 _ForwardIterator2 __last2)
715{
716 return equal(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, std::equal_to<>());
717}
718
719// [alg.move]
720template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
721__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
722move(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __d_first)
723{
724 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __d_first);
725
726 using __is_vector = typename decltype(__dispatch_tag)::__is_vector;
727
728 return __pstl::__internal::__pattern_walk2_brick(
729 __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first,
730 [](_ForwardIterator1 __begin, _ForwardIterator1 __end, _ForwardIterator2 __res)
731 { return __pstl::__internal::__brick_move(__begin, __end, __res, __is_vector{}); });
732}
733
734// [partial.sort]
735
736template <class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
737__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
738partial_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __middle,
739 _RandomAccessIterator __last, _Compare __comp)
740{
741 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
742
743 __pstl::__internal::__pattern_partial_sort(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
744 __middle, __last, __comp);
745}
746
747template <class _ExecutionPolicy, class _RandomAccessIterator>
748__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
749partial_sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __middle,
750 _RandomAccessIterator __last)
751{
752 typedef typename iterator_traits<_RandomAccessIterator>::value_type _InputType;
753 std::partial_sort(__exec, __first, __middle, __last, std::less<_InputType>());
754}
755
756// [partial.sort.copy]
757
758template <class _ExecutionPolicy, class _ForwardIterator, class _RandomAccessIterator, class _Compare>
759__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _RandomAccessIterator>
760partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last,
761 _RandomAccessIterator __d_first, _RandomAccessIterator __d_last, _Compare __comp)
762{
763 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __d_first);
764
765 return __pstl::__internal::__pattern_partial_sort_copy(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec),
766 __first, __last, __d_first, __d_last, __comp);
767}
768
769template <class _ExecutionPolicy, class _ForwardIterator, class _RandomAccessIterator>
770__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _RandomAccessIterator>
771partial_sort_copy(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last,
772 _RandomAccessIterator __d_first, _RandomAccessIterator __d_last)
773{
774 return std::partial_sort_copy(std::forward<_ExecutionPolicy>(__exec), __first, __last, __d_first, __d_last,
775 std::less<>());
776}
777
778// [is.sorted]
779template <class _ExecutionPolicy, class _ForwardIterator, class _Compare>
780__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
781is_sorted_until(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
782{
783 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
784 const _ForwardIterator __res =
785 __pstl::__internal::__pattern_adjacent_find(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
786 __last, __pstl::__internal::__reorder_pred<_Compare>(__comp),
787 /*first_semantic*/ false);
788 return __res == __last ? __last : std::next(__res);
789}
790
791template <class _ExecutionPolicy, class _ForwardIterator>
792__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
793is_sorted_until(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last)
794{
795 typedef typename std::iterator_traits<_ForwardIterator>::value_type _InputType;
796 return is_sorted_until(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::less<_InputType>());
797}
798
799template <class _ExecutionPolicy, class _ForwardIterator, class _Compare>
800__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
801is_sorted(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
802{
803 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
804 return __pstl::__internal::__pattern_adjacent_find(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
805 __last, __pstl::__internal::__reorder_pred<_Compare>(__comp),
806 /*or_semantic*/ true) == __last;
807}
808
809template <class _ExecutionPolicy, class _ForwardIterator>
810__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
811is_sorted(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last)
812{
813 typedef typename std::iterator_traits<_ForwardIterator>::value_type _InputType;
814 return std::is_sorted(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::less<_InputType>());
815}
816
817// [alg.merge]
818template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator,
819 class _Compare>
820__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
821merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
822 _ForwardIterator2 __last2, _ForwardIterator __d_first, _Compare __comp)
823{
824 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2, __d_first);
825
826 return __pstl::__internal::__pattern_merge(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1,
827 __last1, __first2, __last2, __d_first, __comp);
828}
829
830template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator>
831__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
832merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
833 _ForwardIterator2 __last2, _ForwardIterator __d_first)
834{
835 return std::merge(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __d_first,
836 std::less<>());
837}
838
839template <class _ExecutionPolicy, class _BidirectionalIterator, class _Compare>
840__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
841inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __middle,
842 _BidirectionalIterator __last, _Compare __comp)
843{
844 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
845
846 __pstl::__internal::__pattern_inplace_merge(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
847 __middle, __last, __comp);
848}
849
850template <class _ExecutionPolicy, class _BidirectionalIterator>
851__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
852inplace_merge(_ExecutionPolicy&& __exec, _BidirectionalIterator __first, _BidirectionalIterator __middle,
853 _BidirectionalIterator __last)
854{
855 typedef typename std::iterator_traits<_BidirectionalIterator>::value_type _InputType;
856 std::inplace_merge(__exec, __first, __middle, __last, std::less<_InputType>());
857}
858
859// [includes]
860
861template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Compare>
862__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
863includes(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
864 _ForwardIterator2 __last2, _Compare __comp)
865{
866 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2);
867
868 return __pstl::__internal::__pattern_includes(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1,
869 __last1, __first2, __last2, __comp);
870}
871
872template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
873__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
874includes(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
875 _ForwardIterator2 __last2)
876{
877 return std::includes(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, std::less<>());
878}
879
880// [set.union]
881
882template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator,
883 class _Compare>
884__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
885set_union(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
886 _ForwardIterator2 __last2, _ForwardIterator __result, _Compare __comp)
887{
888 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2, __result);
889
890 return __pstl::__internal::__pattern_set_union(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1,
891 __last1, __first2, __last2, __result, __comp);
892}
893
894template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator>
895__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
896set_union(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
897 _ForwardIterator2 __last2, _ForwardIterator __result)
898{
899 return std::set_union(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result,
900 std::less<>());
901}
902
903// [set.intersection]
904
905template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator,
906 class _Compare>
907__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
908set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
909 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result, _Compare __comp)
910{
911 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2, __result);
912
913 return __pstl::__internal::__pattern_set_intersection(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec),
914 __first1, __last1, __first2, __last2, __result, __comp);
915}
916
917template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator>
918__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
919set_intersection(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
920 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result)
921{
922 return std::set_intersection(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result,
923 std::less<>());
924}
925
926// [set.difference]
927
928template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator,
929 class _Compare>
930__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
931set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
932 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result, _Compare __comp)
933{
934 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2, __result);
935
936 return __pstl::__internal::__pattern_set_difference(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec),
937 __first1, __last1, __first2, __last2, __result, __comp);
938}
939
940template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator>
941__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
942set_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
943 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result)
944{
945 return std::set_difference(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result,
946 std::less<>());
947}
948
949// [set.symmetric.difference]
950
951template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator,
952 class _Compare>
953__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
954set_symmetric_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
955 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result,
956 _Compare __comp)
957{
958 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2, __result);
959
960 return __pstl::__internal::__pattern_set_symmetric_difference(
961 __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2, __result, __comp);
962}
963
964template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator>
965__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
966set_symmetric_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
967 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _ForwardIterator __result)
968{
969 return std::set_symmetric_difference(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2,
970 __result, std::less<>());
971}
972
973// [is.heap]
974template <class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
975__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _RandomAccessIterator>
976is_heap_until(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
977{
978 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
979
980 return __pstl::__internal::__pattern_is_heap_until(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
981 __last, __comp);
982}
983
984template <class _ExecutionPolicy, class _RandomAccessIterator>
985__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _RandomAccessIterator>
986is_heap_until(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last)
987{
988 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _InputType;
989 return std::is_heap_until(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::less<_InputType>());
990}
991
992template <class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
993__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
994is_heap(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
995{
996 return std::is_heap_until(std::forward<_ExecutionPolicy>(__exec), __first, __last, __comp) == __last;
997}
998
999template <class _ExecutionPolicy, class _RandomAccessIterator>
1000__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
1001is_heap(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last)
1002{
1003 typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _InputType;
1004 return std::is_heap(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::less<_InputType>());
1005}
1006
1007// [alg.min.max]
1008
1009template <class _ExecutionPolicy, class _ForwardIterator, class _Compare>
1010__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
1011min_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
1012{
1013 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
1014 return __pstl::__internal::__pattern_min_element(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
1015 __last, __comp);
1016}
1017
1018template <class _ExecutionPolicy, class _ForwardIterator>
1019__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
1020min_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last)
1021{
1022 typedef typename std::iterator_traits<_ForwardIterator>::value_type _InputType;
1023 return std::min_element(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::less<_InputType>());
1024}
1025
1026template <class _ExecutionPolicy, class _ForwardIterator, class _Compare>
1027__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
1028max_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
1029{
1030 return min_element(std::forward<_ExecutionPolicy>(__exec), __first, __last,
1031 __pstl::__internal::__reorder_pred<_Compare>(__comp));
1032}
1033
1034template <class _ExecutionPolicy, class _ForwardIterator>
1035__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator>
1036max_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last)
1037{
1038 typedef typename std::iterator_traits<_ForwardIterator>::value_type _InputType;
1039 return std::min_element(std::forward<_ExecutionPolicy>(__exec), __first, __last,
1040 __pstl::__internal::__reorder_pred<std::less<_InputType>>(std::less<_InputType>()));
1041}
1042
1043template <class _ExecutionPolicy, class _ForwardIterator, class _Compare>
1044__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, std::pair<_ForwardIterator, _ForwardIterator>>
1045minmax_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
1046{
1047 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
1048 return __pstl::__internal::__pattern_minmax_element(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first,
1049 __last, __comp);
1050}
1051
1052template <class _ExecutionPolicy, class _ForwardIterator>
1053__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, std::pair<_ForwardIterator, _ForwardIterator>>
1054minmax_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last)
1055{
1056 typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
1057 return std::minmax_element(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::less<_ValueType>());
1058}
1059
1060// [alg.nth.element]
1061
1062template <class _ExecutionPolicy, class _RandomAccessIterator, class _Compare>
1063__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
1064nth_element(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __nth,
1065 _RandomAccessIterator __last, _Compare __comp)
1066{
1067 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
1068
1069 __pstl::__internal::__pattern_nth_element(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __nth,
1070 __last, __comp);
1071}
1072
1073template <class _ExecutionPolicy, class _RandomAccessIterator>
1074__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, void>
1075nth_element(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __nth,
1076 _RandomAccessIterator __last)
1077{
1078 typedef typename iterator_traits<_RandomAccessIterator>::value_type _InputType;
1079 std::nth_element(std::forward<_ExecutionPolicy>(__exec), __first, __nth, __last, std::less<_InputType>());
1080}
1081
1082// [alg.lex.comparison]
1083
1084template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Compare>
1085__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
1086lexicographical_compare(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
1087 _ForwardIterator2 __first2, _ForwardIterator2 __last2, _Compare __comp)
1088{
1089 auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2);
1090
1091 return __pstl::__internal::__pattern_lexicographical_compare(__dispatch_tag, std::forward<_ExecutionPolicy>(__exec),
1092 __first1, __last1, __first2, __last2, __comp);
1093}
1094
1095template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
1096__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
1097lexicographical_compare(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
1098 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
1099{
1100 return std::lexicographical_compare(std::forward<_ExecutionPolicy>(__exec), __first1, __last1, __first2, __last2,
1101 std::less<>());
1102}
1103
1104} // namespace std
1105
1106_PSTL_HIDE_FROM_ABI_POP
1107
1108#endif /* _PSTL_GLUE_ALGORITHM_IMPL_H */
1109

source code of pstl/include/pstl/internal/glue_algorithm_impl.h