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