1181254a7Smrg // -*- C++ -*-
2181254a7Smrg //===-- numeric_impl.h ----------------------------------------------------===//
3181254a7Smrg //
4181254a7Smrg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5181254a7Smrg // See https://llvm.org/LICENSE.txt for license information.
6181254a7Smrg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7181254a7Smrg //
8181254a7Smrg //===----------------------------------------------------------------------===//
9181254a7Smrg
10fb8a8121Smrg #ifndef _PSTL_NUMERIC_IMPL_H
11fb8a8121Smrg #define _PSTL_NUMERIC_IMPL_H
12181254a7Smrg
13181254a7Smrg #include <iterator>
14181254a7Smrg #include <type_traits>
15181254a7Smrg #include <numeric>
16181254a7Smrg
17fb8a8121Smrg #include "parallel_backend.h"
18fb8a8121Smrg #include "pstl_config.h"
19181254a7Smrg #include "execution_impl.h"
20181254a7Smrg #include "unseq_backend_simd.h"
21181254a7Smrg #include "algorithm_fwd.h"
22181254a7Smrg
23181254a7Smrg namespace __pstl
24181254a7Smrg {
25181254a7Smrg namespace __internal
26181254a7Smrg {
27181254a7Smrg
28181254a7Smrg //------------------------------------------------------------------------
29181254a7Smrg // transform_reduce (version with two binary functions, according to draft N4659)
30181254a7Smrg //------------------------------------------------------------------------
31181254a7Smrg
32181254a7Smrg template <class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
33181254a7Smrg _Tp
__brick_transform_reduce(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_Tp __init,_BinaryOperation1 __binary_op1,_BinaryOperation2 __binary_op2,std::false_type)34181254a7Smrg __brick_transform_reduce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _Tp __init,
35181254a7Smrg _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2,
36181254a7Smrg /*is_vector=*/std::false_type) noexcept
37181254a7Smrg {
38181254a7Smrg return std::inner_product(__first1, __last1, __first2, __init, __binary_op1, __binary_op2);
39181254a7Smrg }
40181254a7Smrg
41181254a7Smrg template <class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
42181254a7Smrg _Tp
__brick_transform_reduce(_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_Tp __init,_BinaryOperation1 __binary_op1,_BinaryOperation2 __binary_op2,std::true_type)43181254a7Smrg __brick_transform_reduce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _Tp __init,
44181254a7Smrg _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2,
45181254a7Smrg /*is_vector=*/std::true_type) noexcept
46181254a7Smrg {
47181254a7Smrg typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType;
48181254a7Smrg return __unseq_backend::__simd_transform_reduce(
49181254a7Smrg __last1 - __first1, __init, __binary_op1,
50181254a7Smrg [=, &__binary_op2](_DifferenceType __i) { return __binary_op2(__first1[__i], __first2[__i]); });
51181254a7Smrg }
52181254a7Smrg
53181254a7Smrg template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1,
54181254a7Smrg class _BinaryOperation2, class _IsVector>
55181254a7Smrg _Tp
__pattern_transform_reduce(_ExecutionPolicy &&,_ForwardIterator1 __first1,_ForwardIterator1 __last1,_ForwardIterator2 __first2,_Tp __init,_BinaryOperation1 __binary_op1,_BinaryOperation2 __binary_op2,_IsVector __is_vector,std::false_type)56181254a7Smrg __pattern_transform_reduce(_ExecutionPolicy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
57181254a7Smrg _ForwardIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1,
58181254a7Smrg _BinaryOperation2 __binary_op2, _IsVector __is_vector,
59181254a7Smrg /*is_parallel=*/std::false_type) noexcept
60181254a7Smrg {
61181254a7Smrg return __brick_transform_reduce(__first1, __last1, __first2, __init, __binary_op1, __binary_op2, __is_vector);
62181254a7Smrg }
63181254a7Smrg
64181254a7Smrg template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Tp,
65181254a7Smrg class _BinaryOperation1, class _BinaryOperation2, class _IsVector>
66181254a7Smrg _Tp
__pattern_transform_reduce(_ExecutionPolicy && __exec,_RandomAccessIterator1 __first1,_RandomAccessIterator1 __last1,_RandomAccessIterator2 __first2,_Tp __init,_BinaryOperation1 __binary_op1,_BinaryOperation2 __binary_op2,_IsVector __is_vector,std::true_type)67181254a7Smrg __pattern_transform_reduce(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
68181254a7Smrg _RandomAccessIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1,
69181254a7Smrg _BinaryOperation2 __binary_op2, _IsVector __is_vector, /*is_parallel=*/std::true_type)
70181254a7Smrg {
71181254a7Smrg return __internal::__except_handler([&]() {
72181254a7Smrg return __par_backend::__parallel_transform_reduce(
73181254a7Smrg std::forward<_ExecutionPolicy>(__exec), __first1, __last1,
74181254a7Smrg [__first1, __first2, __binary_op2](_RandomAccessIterator1 __i) mutable {
75181254a7Smrg return __binary_op2(*__i, *(__first2 + (__i - __first1)));
76181254a7Smrg },
77181254a7Smrg __init,
78181254a7Smrg __binary_op1, // Combine
79181254a7Smrg [__first1, __first2, __binary_op1, __binary_op2,
80181254a7Smrg __is_vector](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j, _Tp __init) -> _Tp {
81181254a7Smrg return __internal::__brick_transform_reduce(__i, __j, __first2 + (__i - __first1), __init, __binary_op1,
82181254a7Smrg __binary_op2, __is_vector);
83181254a7Smrg });
84181254a7Smrg });
85181254a7Smrg }
86181254a7Smrg
87181254a7Smrg //------------------------------------------------------------------------
88181254a7Smrg // transform_reduce (version with unary and binary functions)
89181254a7Smrg //------------------------------------------------------------------------
90181254a7Smrg
91181254a7Smrg template <class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
92181254a7Smrg _Tp
__brick_transform_reduce(_ForwardIterator __first,_ForwardIterator __last,_Tp __init,_BinaryOperation __binary_op,_UnaryOperation __unary_op,std::false_type)93181254a7Smrg __brick_transform_reduce(_ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation __binary_op,
94181254a7Smrg _UnaryOperation __unary_op, /*is_vector=*/std::false_type) noexcept
95181254a7Smrg {
96*b1e83836Smrg return std::transform_reduce(__first, __last, __init, __binary_op, __unary_op);
97181254a7Smrg }
98181254a7Smrg
99181254a7Smrg template <class _ForwardIterator, class _Tp, class _UnaryOperation, class _BinaryOperation>
100181254a7Smrg _Tp
__brick_transform_reduce(_ForwardIterator __first,_ForwardIterator __last,_Tp __init,_BinaryOperation __binary_op,_UnaryOperation __unary_op,std::true_type)101181254a7Smrg __brick_transform_reduce(_ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation __binary_op,
102181254a7Smrg _UnaryOperation __unary_op, /*is_vector=*/std::true_type) noexcept
103181254a7Smrg {
104181254a7Smrg typedef typename std::iterator_traits<_ForwardIterator>::difference_type _DifferenceType;
105181254a7Smrg return __unseq_backend::__simd_transform_reduce(
106181254a7Smrg __last - __first, __init, __binary_op,
107181254a7Smrg [=, &__unary_op](_DifferenceType __i) { return __unary_op(__first[__i]); });
108181254a7Smrg }
109181254a7Smrg
110181254a7Smrg template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation,
111181254a7Smrg class _IsVector>
112181254a7Smrg _Tp
__pattern_transform_reduce(_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_Tp __init,_BinaryOperation __binary_op,_UnaryOperation __unary_op,_IsVector __is_vector,std::false_type)113181254a7Smrg __pattern_transform_reduce(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
114181254a7Smrg _BinaryOperation __binary_op, _UnaryOperation __unary_op, _IsVector __is_vector,
115181254a7Smrg /*is_parallel=*/std::false_type) noexcept
116181254a7Smrg {
117181254a7Smrg return __internal::__brick_transform_reduce(__first, __last, __init, __binary_op, __unary_op, __is_vector);
118181254a7Smrg }
119181254a7Smrg
120181254a7Smrg template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation,
121181254a7Smrg class _IsVector>
122181254a7Smrg _Tp
__pattern_transform_reduce(_ExecutionPolicy && __exec,_ForwardIterator __first,_ForwardIterator __last,_Tp __init,_BinaryOperation __binary_op,_UnaryOperation __unary_op,_IsVector __is_vector,std::true_type)123181254a7Smrg __pattern_transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
124181254a7Smrg _BinaryOperation __binary_op, _UnaryOperation __unary_op, _IsVector __is_vector,
125181254a7Smrg /*is_parallel=*/std::true_type)
126181254a7Smrg {
127181254a7Smrg return __internal::__except_handler([&]() {
128181254a7Smrg return __par_backend::__parallel_transform_reduce(
129181254a7Smrg std::forward<_ExecutionPolicy>(__exec), __first, __last,
130181254a7Smrg [__unary_op](_ForwardIterator __i) mutable { return __unary_op(*__i); }, __init, __binary_op,
131181254a7Smrg [__unary_op, __binary_op, __is_vector](_ForwardIterator __i, _ForwardIterator __j, _Tp __init) {
132181254a7Smrg return __internal::__brick_transform_reduce(__i, __j, __init, __binary_op, __unary_op, __is_vector);
133181254a7Smrg });
134181254a7Smrg });
135181254a7Smrg }
136181254a7Smrg
137181254a7Smrg //------------------------------------------------------------------------
138181254a7Smrg // transform_exclusive_scan
139181254a7Smrg //
140181254a7Smrg // walk3 evaluates f(x,y,z) for (x,y,z) drawn from [first1,last1), [first2,...), [first3,...)
141181254a7Smrg //------------------------------------------------------------------------
142181254a7Smrg
143181254a7Smrg // Exclusive form
144181254a7Smrg template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
145181254a7Smrg std::pair<_OutputIterator, _Tp>
__brick_transform_scan(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,_UnaryOperation __unary_op,_Tp __init,_BinaryOperation __binary_op,std::false_type,std::false_type)146181254a7Smrg __brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
147181254a7Smrg _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
148181254a7Smrg /*Inclusive*/ std::false_type, /*is_vector=*/std::false_type) noexcept
149181254a7Smrg {
150181254a7Smrg for (; __first != __last; ++__first, ++__result)
151181254a7Smrg {
152181254a7Smrg *__result = __init;
153fb8a8121Smrg _PSTL_PRAGMA_FORCEINLINE
154181254a7Smrg __init = __binary_op(__init, __unary_op(*__first));
155181254a7Smrg }
156181254a7Smrg return std::make_pair(__result, __init);
157181254a7Smrg }
158181254a7Smrg
159181254a7Smrg // Inclusive form
160181254a7Smrg template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
161181254a7Smrg std::pair<_OutputIterator, _Tp>
__brick_transform_scan(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,_UnaryOperation __unary_op,_Tp __init,_BinaryOperation __binary_op,std::true_type,std::false_type)162181254a7Smrg __brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
163181254a7Smrg _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
164181254a7Smrg /*Inclusive*/ std::true_type, /*is_vector=*/std::false_type) noexcept
165181254a7Smrg {
166181254a7Smrg for (; __first != __last; ++__first, ++__result)
167181254a7Smrg {
168fb8a8121Smrg _PSTL_PRAGMA_FORCEINLINE
169181254a7Smrg __init = __binary_op(__init, __unary_op(*__first));
170181254a7Smrg *__result = __init;
171181254a7Smrg }
172181254a7Smrg return std::make_pair(__result, __init);
173181254a7Smrg }
174181254a7Smrg
175181254a7Smrg // type is arithmetic and binary operation is a user defined operation.
176181254a7Smrg template <typename _Tp, typename _BinaryOperation>
177181254a7Smrg using is_arithmetic_udop = std::integral_constant<bool, std::is_arithmetic<_Tp>::value &&
178181254a7Smrg !std::is_same<_BinaryOperation, std::plus<_Tp>>::value>;
179181254a7Smrg
180181254a7Smrg // [restriction] - T shall be DefaultConstructible.
181181254a7Smrg // [violation] - default ctor of T shall set the identity value for binary_op.
182181254a7Smrg template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation,
183181254a7Smrg class _Inclusive>
184181254a7Smrg typename std::enable_if<!is_arithmetic_udop<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
__brick_transform_scan(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,_UnaryOperation __unary_op,_Tp __init,_BinaryOperation __binary_op,_Inclusive,std::true_type)185181254a7Smrg __brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
186181254a7Smrg _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op, _Inclusive,
187181254a7Smrg /*is_vector=*/std::true_type) noexcept
188181254a7Smrg {
189fb8a8121Smrg #if (_PSTL_UDS_PRESENT)
190181254a7Smrg return __unseq_backend::__simd_scan(__first, __last - __first, __result, __unary_op, __init, __binary_op,
191181254a7Smrg _Inclusive());
192181254a7Smrg #else
193181254a7Smrg // We need to call serial brick here to call function for inclusive and exclusive scan that depends on _Inclusive() value
194181254a7Smrg return __internal::__brick_transform_scan(__first, __last, __result, __unary_op, __init, __binary_op, _Inclusive(),
195181254a7Smrg /*is_vector=*/std::false_type());
196181254a7Smrg #endif
197181254a7Smrg }
198181254a7Smrg
199181254a7Smrg template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation,
200181254a7Smrg class _Inclusive>
201181254a7Smrg typename std::enable_if<is_arithmetic_udop<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
__brick_transform_scan(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,_UnaryOperation __unary_op,_Tp __init,_BinaryOperation __binary_op,_Inclusive,std::true_type)202181254a7Smrg __brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
203181254a7Smrg _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op, _Inclusive,
204181254a7Smrg /*is_vector=*/std::true_type) noexcept
205181254a7Smrg {
206181254a7Smrg return __internal::__brick_transform_scan(__first, __last, __result, __unary_op, __init, __binary_op, _Inclusive(),
207181254a7Smrg /*is_vector=*/std::false_type());
208181254a7Smrg }
209181254a7Smrg
210181254a7Smrg template <class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp,
211181254a7Smrg class _BinaryOperation, class _Inclusive, class _IsVector>
212181254a7Smrg _OutputIterator
__pattern_transform_scan(_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __result,_UnaryOperation __unary_op,_Tp __init,_BinaryOperation __binary_op,_Inclusive,_IsVector __is_vector,std::false_type)213181254a7Smrg __pattern_transform_scan(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last,
214181254a7Smrg _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
215181254a7Smrg _Inclusive, _IsVector __is_vector, /*is_parallel=*/std::false_type) noexcept
216181254a7Smrg {
217fb8a8121Smrg return __internal::__brick_transform_scan(__first, __last, __result, __unary_op, __init, __binary_op, _Inclusive(),
218fb8a8121Smrg __is_vector)
219181254a7Smrg .first;
220181254a7Smrg }
221181254a7Smrg
222181254a7Smrg template <class _ExecutionPolicy, class _RandomAccessIterator, class _OutputIterator, class _UnaryOperation, class _Tp,
223181254a7Smrg class _BinaryOperation, class _Inclusive, class _IsVector>
224181254a7Smrg typename std::enable_if<!std::is_floating_point<_Tp>::value, _OutputIterator>::type
__pattern_transform_scan(_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_OutputIterator __result,_UnaryOperation __unary_op,_Tp __init,_BinaryOperation __binary_op,_Inclusive,_IsVector __is_vector,std::true_type)225181254a7Smrg __pattern_transform_scan(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
226181254a7Smrg _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
227181254a7Smrg _Inclusive, _IsVector __is_vector, /*is_parallel=*/std::true_type)
228181254a7Smrg {
229181254a7Smrg typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
230181254a7Smrg
231181254a7Smrg return __internal::__except_handler([&]() {
232181254a7Smrg __par_backend::__parallel_transform_scan(
233181254a7Smrg std::forward<_ExecutionPolicy>(__exec), __last - __first,
234181254a7Smrg [__first, __unary_op](_DifferenceType __i) mutable { return __unary_op(__first[__i]); }, __init,
235181254a7Smrg __binary_op,
236181254a7Smrg [__first, __unary_op, __binary_op](_DifferenceType __i, _DifferenceType __j, _Tp __init) {
237181254a7Smrg // Execute serial __brick_transform_reduce, due to the explicit SIMD vectorization (reduction) requires a commutative operation for the guarantee of correct scan.
238fb8a8121Smrg return __internal::__brick_transform_reduce(__first + __i, __first + __j, __init, __binary_op,
239fb8a8121Smrg __unary_op,
240181254a7Smrg /*__is_vector*/ std::false_type());
241181254a7Smrg },
242181254a7Smrg [__first, __unary_op, __binary_op, __result, __is_vector](_DifferenceType __i, _DifferenceType __j,
243181254a7Smrg _Tp __init) {
244fb8a8121Smrg return __internal::__brick_transform_scan(__first + __i, __first + __j, __result + __i, __unary_op,
245fb8a8121Smrg __init, __binary_op, _Inclusive(), __is_vector)
246181254a7Smrg .second;
247181254a7Smrg });
248181254a7Smrg return __result + (__last - __first);
249181254a7Smrg });
250181254a7Smrg }
251181254a7Smrg
252181254a7Smrg template <class _ExecutionPolicy, class _RandomAccessIterator, class _OutputIterator, class _UnaryOperation, class _Tp,
253181254a7Smrg class _BinaryOperation, class _Inclusive, class _IsVector>
254181254a7Smrg typename std::enable_if<std::is_floating_point<_Tp>::value, _OutputIterator>::type
__pattern_transform_scan(_ExecutionPolicy && __exec,_RandomAccessIterator __first,_RandomAccessIterator __last,_OutputIterator __result,_UnaryOperation __unary_op,_Tp __init,_BinaryOperation __binary_op,_Inclusive,_IsVector __is_vector,std::true_type)255181254a7Smrg __pattern_transform_scan(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
256181254a7Smrg _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
257181254a7Smrg _Inclusive, _IsVector __is_vector, /*is_parallel=*/std::true_type)
258181254a7Smrg {
259181254a7Smrg typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
260181254a7Smrg _DifferenceType __n = __last - __first;
261181254a7Smrg
262181254a7Smrg if (__n <= 0)
263181254a7Smrg {
264181254a7Smrg return __result;
265181254a7Smrg }
266181254a7Smrg return __internal::__except_handler([&]() {
267181254a7Smrg __par_backend::__parallel_strict_scan(
268181254a7Smrg std::forward<_ExecutionPolicy>(__exec), __n, __init,
269181254a7Smrg [__first, __unary_op, __binary_op, __result, __is_vector](_DifferenceType __i, _DifferenceType __len) {
270fb8a8121Smrg return __internal::__brick_transform_scan(__first + __i, __first + (__i + __len), __result + __i,
271fb8a8121Smrg __unary_op, _Tp{}, __binary_op, _Inclusive(), __is_vector)
272181254a7Smrg .second;
273181254a7Smrg },
274181254a7Smrg __binary_op,
275181254a7Smrg [__result, &__binary_op](_DifferenceType __i, _DifferenceType __len, _Tp __initial) {
276181254a7Smrg return *(std::transform(__result + __i, __result + __i + __len, __result + __i,
277181254a7Smrg [&__initial, &__binary_op](const _Tp& __x) {
278fb8a8121Smrg _PSTL_PRAGMA_FORCEINLINE
279181254a7Smrg return __binary_op(__initial, __x);
280181254a7Smrg }) -
281181254a7Smrg 1);
282181254a7Smrg },
283*b1e83836Smrg [](_Tp) {});
284181254a7Smrg return __result + (__last - __first);
285181254a7Smrg });
286181254a7Smrg }
287181254a7Smrg
288181254a7Smrg //------------------------------------------------------------------------
289181254a7Smrg // adjacent_difference
290181254a7Smrg //------------------------------------------------------------------------
291181254a7Smrg
292181254a7Smrg template <class _ForwardIterator, class _OutputIterator, class _BinaryOperation>
293181254a7Smrg _OutputIterator
__brick_adjacent_difference(_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __d_first,_BinaryOperation __op,std::false_type)294181254a7Smrg __brick_adjacent_difference(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __d_first,
295181254a7Smrg _BinaryOperation __op, /*is_vector*/ std::false_type) noexcept
296181254a7Smrg {
297181254a7Smrg return std::adjacent_difference(__first, __last, __d_first, __op);
298181254a7Smrg }
299181254a7Smrg
300181254a7Smrg template <class _ForwardIterator1, class _ForwardIterator2, class BinaryOperation>
301181254a7Smrg _ForwardIterator2
__brick_adjacent_difference(_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __d_first,BinaryOperation __op,std::true_type)302181254a7Smrg __brick_adjacent_difference(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __d_first,
303181254a7Smrg BinaryOperation __op, /*is_vector=*/std::true_type) noexcept
304181254a7Smrg {
305fb8a8121Smrg _PSTL_ASSERT(__first != __last);
306181254a7Smrg
307181254a7Smrg typedef typename std::iterator_traits<_ForwardIterator1>::reference _ReferenceType1;
308181254a7Smrg typedef typename std::iterator_traits<_ForwardIterator2>::reference _ReferenceType2;
309181254a7Smrg
310181254a7Smrg auto __n = __last - __first;
311181254a7Smrg *__d_first = *__first;
312181254a7Smrg return __unseq_backend::__simd_walk_3(
313181254a7Smrg __first + 1, __n - 1, __first, __d_first + 1,
314181254a7Smrg [&__op](_ReferenceType1 __x, _ReferenceType1 __y, _ReferenceType2 __z) { __z = __op(__x, __y); });
315181254a7Smrg }
316181254a7Smrg
317181254a7Smrg template <class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _BinaryOperation,
318181254a7Smrg class _IsVector>
319181254a7Smrg _OutputIterator
__pattern_adjacent_difference(_ExecutionPolicy &&,_ForwardIterator __first,_ForwardIterator __last,_OutputIterator __d_first,_BinaryOperation __op,_IsVector __is_vector,std::false_type)320181254a7Smrg __pattern_adjacent_difference(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last,
321181254a7Smrg _OutputIterator __d_first, _BinaryOperation __op, _IsVector __is_vector,
322181254a7Smrg /*is_parallel*/ std::false_type) noexcept
323181254a7Smrg {
324181254a7Smrg return __internal::__brick_adjacent_difference(__first, __last, __d_first, __op, __is_vector);
325181254a7Smrg }
326181254a7Smrg
327181254a7Smrg template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation,
328181254a7Smrg class _IsVector>
329181254a7Smrg _ForwardIterator2
__pattern_adjacent_difference(_ExecutionPolicy && __exec,_ForwardIterator1 __first,_ForwardIterator1 __last,_ForwardIterator2 __d_first,_BinaryOperation __op,_IsVector __is_vector,std::true_type)330181254a7Smrg __pattern_adjacent_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
331181254a7Smrg _ForwardIterator2 __d_first, _BinaryOperation __op, _IsVector __is_vector,
332181254a7Smrg /*is_parallel=*/std::true_type)
333181254a7Smrg {
334fb8a8121Smrg _PSTL_ASSERT(__first != __last);
335181254a7Smrg typedef typename std::iterator_traits<_ForwardIterator1>::reference _ReferenceType1;
336181254a7Smrg typedef typename std::iterator_traits<_ForwardIterator2>::reference _ReferenceType2;
337181254a7Smrg
338181254a7Smrg *__d_first = *__first;
339181254a7Smrg __par_backend::__parallel_for(
340181254a7Smrg std::forward<_ExecutionPolicy>(__exec), __first, __last - 1,
341181254a7Smrg [&__op, __is_vector, __d_first, __first](_ForwardIterator1 __b, _ForwardIterator1 __e) {
342181254a7Smrg _ForwardIterator2 __d_b = __d_first + (__b - __first);
343181254a7Smrg __internal::__brick_walk3(
344181254a7Smrg __b, __e, __b + 1, __d_b + 1,
345181254a7Smrg [&__op](_ReferenceType1 __x, _ReferenceType1 __y, _ReferenceType2 __z) { __z = __op(__y, __x); },
346181254a7Smrg __is_vector);
347181254a7Smrg });
348181254a7Smrg return __d_first + (__last - __first);
349181254a7Smrg }
350181254a7Smrg
351181254a7Smrg } // namespace __internal
352181254a7Smrg } // namespace __pstl
353181254a7Smrg
354fb8a8121Smrg #endif /* _PSTL_NUMERIC_IMPL_H */
355