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

source code of include/c++/11/pstl/glue_algorithm_impl.h