1// -*- C++ -*-
2
3// Copyright (C) 2007-2020 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 3, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14// General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25/**
26 * @file parallel/numeric
27*
28 * @brief Parallel STL function calls corresponding to stl_numeric.h.
29 * The functions defined here mainly do case switches and
30 * call the actual parallelized versions in other files.
31 * Inlining policy: Functions that basically only contain one function call,
32 * are declared inline.
33 *  This file is a GNU parallel extension to the Standard C++ Library.
34 */
35
36// Written by Johannes Singler and Felix Putze.
37
38#ifndef _GLIBCXX_PARALLEL_NUMERIC_H
39#define _GLIBCXX_PARALLEL_NUMERIC_H 1
40
41#include <numeric>
42#include <bits/stl_function.h>
43#include <parallel/numericfwd.h>
44#include <parallel/iterator.h>
45#include <parallel/for_each.h>
46#include <parallel/for_each_selectors.h>
47#include <parallel/partial_sum.h>
48
49namespace std _GLIBCXX_VISIBILITY(default)
50{
51namespace __parallel
52{
53  // Sequential fallback.
54  template<typename _IIter, typename _Tp>
55    inline _Tp
56    accumulate(_IIter __begin, _IIter __end, _Tp __init,
57               __gnu_parallel::sequential_tag)
58    { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init); }
59
60  template<typename _IIter, typename _Tp, typename _BinaryOperation>
61    inline _Tp
62    accumulate(_IIter __begin, _IIter __end, _Tp __init,
63               _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
64    { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init, __binary_op); }
65
66  // Sequential fallback for input iterator case.
67  template<typename _IIter, typename _Tp, typename _IteratorTag>
68    inline _Tp
69    __accumulate_switch(_IIter __begin, _IIter __end,
70                      _Tp __init, _IteratorTag)
71    { return accumulate(__begin, __end, __init,
72			__gnu_parallel::sequential_tag()); }
73
74  template<typename _IIter, typename _Tp, typename _BinaryOperation,
75           typename _IteratorTag>
76    inline _Tp
77    __accumulate_switch(_IIter __begin, _IIter __end, _Tp __init,
78                      _BinaryOperation __binary_op, _IteratorTag)
79    { return accumulate(__begin, __end, __init, __binary_op,
80                        __gnu_parallel::sequential_tag()); }
81
82  // Parallel algorithm for random access iterators.
83  template<typename __RAIter, typename _Tp, typename _BinaryOperation>
84    _Tp
85    __accumulate_switch(__RAIter __begin, __RAIter __end,
86                      _Tp __init, _BinaryOperation __binary_op,
87                      random_access_iterator_tag,
88                      __gnu_parallel::_Parallelism __parallelism_tag)
89    {
90      if (_GLIBCXX_PARALLEL_CONDITION(
91            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
92            >= __gnu_parallel::_Settings::get().accumulate_minimal_n
93            && __gnu_parallel::__is_parallel(__parallelism_tag)))
94        {
95          _Tp __res = __init;
96          __gnu_parallel::__accumulate_selector<__RAIter>
97            __my_selector;
98          __gnu_parallel::
99            __for_each_template_random_access_ed(__begin, __end,
100						 __gnu_parallel::_Nothing(),
101						 __my_selector,
102						 __gnu_parallel::
103						 __accumulate_binop_reduct
104					       <_BinaryOperation>(__binary_op),
105						 __res, __res, -1);
106          return __res;
107        }
108      else
109        return accumulate(__begin, __end, __init, __binary_op,
110                          __gnu_parallel::sequential_tag());
111    }
112
113  // Public interface.
114  template<typename _IIter, typename _Tp>
115    inline _Tp
116    accumulate(_IIter __begin, _IIter __end, _Tp __init,
117               __gnu_parallel::_Parallelism __parallelism_tag)
118    {
119      typedef std::iterator_traits<_IIter> _IteratorTraits;
120      typedef typename _IteratorTraits::value_type _ValueType;
121      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
122
123      return __accumulate_switch(__begin, __end, __init,
124				 __gnu_parallel::_Plus<_Tp, _ValueType>(),
125				 _IteratorCategory(), __parallelism_tag);
126    }
127
128  template<typename _IIter, typename _Tp>
129    inline _Tp
130    accumulate(_IIter __begin, _IIter __end, _Tp __init)
131    {
132      typedef std::iterator_traits<_IIter> _IteratorTraits;
133      typedef typename _IteratorTraits::value_type _ValueType;
134      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
135
136      return __accumulate_switch(__begin, __end, __init,
137				 __gnu_parallel::_Plus<_Tp, _ValueType>(),
138				 _IteratorCategory());
139    }
140
141  template<typename _IIter, typename _Tp, typename _BinaryOperation>
142    inline _Tp
143    accumulate(_IIter __begin, _IIter __end, _Tp __init,
144               _BinaryOperation __binary_op,
145               __gnu_parallel::_Parallelism __parallelism_tag)
146    {
147      typedef iterator_traits<_IIter> _IteratorTraits;
148      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
149      return __accumulate_switch(__begin, __end, __init, __binary_op,
150				 _IteratorCategory(), __parallelism_tag);
151    }
152
153  template<typename _IIter, typename _Tp, typename _BinaryOperation>
154    inline _Tp
155    accumulate(_IIter __begin, _IIter __end, _Tp __init,
156               _BinaryOperation __binary_op)
157    {
158      typedef iterator_traits<_IIter> _IteratorTraits;
159      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
160      return __accumulate_switch(__begin, __end, __init, __binary_op,
161				 _IteratorCategory());
162    }
163
164
165  // Sequential fallback.
166  template<typename _IIter1, typename _IIter2, typename _Tp>
167    inline _Tp
168    inner_product(_IIter1 __first1, _IIter1 __last1,
169                  _IIter2 __first2, _Tp __init,
170                  __gnu_parallel::sequential_tag)
171    { return _GLIBCXX_STD_A::inner_product(
172                               __first1, __last1, __first2, __init); }
173
174  template<typename _IIter1, typename _IIter2, typename _Tp,
175           typename _BinaryFunction1, typename _BinaryFunction2>
176    inline _Tp
177    inner_product(_IIter1 __first1, _IIter1 __last1,
178                  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
179                  _BinaryFunction2 __binary_op2,
180                  __gnu_parallel::sequential_tag)
181    { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init,
182                                           __binary_op1, __binary_op2); }
183
184  // Parallel algorithm for random access iterators.
185  template<typename _RAIter1, typename _RAIter2,
186           typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
187    _Tp
188    __inner_product_switch(_RAIter1 __first1,
189			   _RAIter1 __last1,
190			   _RAIter2 __first2, _Tp __init,
191			   _BinaryFunction1 __binary_op1,
192			   _BinaryFunction2 __binary_op2,
193			   random_access_iterator_tag,
194			   random_access_iterator_tag,
195			   __gnu_parallel::_Parallelism __parallelism_tag)
196    {
197      if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
198                                      >= __gnu_parallel::_Settings::get().
199                                      accumulate_minimal_n
200                                      && __gnu_parallel::
201                                      __is_parallel(__parallelism_tag)))
202        {
203          _Tp __res = __init;
204          __gnu_parallel::
205            __inner_product_selector<_RAIter1,
206            _RAIter2, _Tp> __my_selector(__first1, __first2);
207          __gnu_parallel::
208            __for_each_template_random_access_ed(
209                __first1, __last1, __binary_op2, __my_selector, __binary_op1,
210                __res, __res, -1);
211          return __res;
212        }
213      else
214        return inner_product(__first1, __last1, __first2, __init,
215                             __gnu_parallel::sequential_tag());
216    }
217
218  // No parallelism for input iterators.
219  template<typename _IIter1, typename _IIter2, typename _Tp,
220           typename _BinaryFunction1, typename _BinaryFunction2,
221           typename _IteratorTag1, typename _IteratorTag2>
222    inline _Tp
223    __inner_product_switch(_IIter1 __first1, _IIter1 __last1,
224			   _IIter2 __first2, _Tp __init,
225			   _BinaryFunction1 __binary_op1,
226			   _BinaryFunction2 __binary_op2,
227			   _IteratorTag1, _IteratorTag2)
228    { return inner_product(__first1, __last1, __first2, __init, __binary_op1,
229			   __binary_op2, __gnu_parallel::sequential_tag()); }
230
231  template<typename _IIter1, typename _IIter2, typename _Tp,
232           typename _BinaryFunction1, typename _BinaryFunction2>
233    inline _Tp
234    inner_product(_IIter1 __first1, _IIter1 __last1,
235                  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
236                  _BinaryFunction2 __binary_op2,
237                  __gnu_parallel::_Parallelism __parallelism_tag)
238    {
239      typedef iterator_traits<_IIter1> _TraitsType1;
240      typedef typename _TraitsType1::iterator_category _IteratorCategory1;
241
242      typedef iterator_traits<_IIter2> _TraitsType2;
243      typedef typename _TraitsType2::iterator_category _IteratorCategory2;
244
245      return __inner_product_switch(__first1, __last1, __first2, __init,
246				    __binary_op1, __binary_op2,
247				    _IteratorCategory1(), _IteratorCategory2(),
248				    __parallelism_tag);
249    }
250
251  template<typename _IIter1, typename _IIter2, typename _Tp,
252           typename _BinaryFunction1, typename _BinaryFunction2>
253    inline _Tp
254    inner_product(_IIter1 __first1, _IIter1 __last1,
255                  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
256                  _BinaryFunction2 __binary_op2)
257    {
258      typedef iterator_traits<_IIter1> _TraitsType1;
259      typedef typename _TraitsType1::iterator_category _IteratorCategory1;
260
261      typedef iterator_traits<_IIter2> _TraitsType2;
262      typedef typename _TraitsType2::iterator_category _IteratorCategory2;
263
264      return __inner_product_switch(__first1, __last1, __first2, __init,
265				    __binary_op1, __binary_op2,
266				    _IteratorCategory1(),
267				    _IteratorCategory2());
268    }
269
270  template<typename _IIter1, typename _IIter2, typename _Tp>
271    inline _Tp
272    inner_product(_IIter1 __first1, _IIter1 __last1,
273                  _IIter2 __first2, _Tp __init,
274                  __gnu_parallel::_Parallelism __parallelism_tag)
275    {
276      typedef iterator_traits<_IIter1> _TraitsType1;
277      typedef typename _TraitsType1::value_type _ValueType1;
278      typedef iterator_traits<_IIter2> _TraitsType2;
279      typedef typename _TraitsType2::value_type _ValueType2;
280
281      typedef typename
282        __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
283        _MultipliesResultType;
284      return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
285                           __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
286                           __gnu_parallel::
287                           _Multiplies<_ValueType1, _ValueType2>(),
288                           __parallelism_tag);
289    }
290
291  template<typename _IIter1, typename _IIter2, typename _Tp>
292    inline _Tp
293    inner_product(_IIter1 __first1, _IIter1 __last1,
294                  _IIter2 __first2, _Tp __init)
295    {
296      typedef iterator_traits<_IIter1> _TraitsType1;
297      typedef typename _TraitsType1::value_type _ValueType1;
298      typedef iterator_traits<_IIter2> _TraitsType2;
299      typedef typename _TraitsType2::value_type _ValueType2;
300
301      typedef typename
302        __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
303        _MultipliesResultType;
304      return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
305                           __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
306                           __gnu_parallel::
307                           _Multiplies<_ValueType1, _ValueType2>());
308    }
309
310  // Sequential fallback.
311  template<typename _IIter, typename _OutputIterator>
312    inline _OutputIterator
313    partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
314                __gnu_parallel::sequential_tag)
315    { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); }
316
317  // Sequential fallback.
318  template<typename _IIter, typename _OutputIterator,
319	   typename _BinaryOperation>
320    inline _OutputIterator
321    partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
322                _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
323    { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
324
325  // Sequential fallback for input iterator case.
326  template<typename _IIter, typename _OutputIterator,
327           typename _BinaryOperation, typename _IteratorTag1,
328           typename _IteratorTag2>
329    inline _OutputIterator
330    __partial_sum_switch(_IIter __begin, _IIter __end,
331			 _OutputIterator __result, _BinaryOperation __bin_op,
332			 _IteratorTag1, _IteratorTag2)
333    { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
334
335  // Parallel algorithm for random access iterators.
336  template<typename _IIter, typename _OutputIterator,
337           typename _BinaryOperation>
338    _OutputIterator
339    __partial_sum_switch(_IIter __begin, _IIter __end,
340			 _OutputIterator __result, _BinaryOperation __bin_op,
341			 random_access_iterator_tag,
342			 random_access_iterator_tag)
343    {
344      if (_GLIBCXX_PARALLEL_CONDITION(
345            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
346            >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
347        return __gnu_parallel::__parallel_partial_sum(__begin, __end,
348						      __result, __bin_op);
349      else
350        return partial_sum(__begin, __end, __result, __bin_op,
351                           __gnu_parallel::sequential_tag());
352    }
353
354  // Public interface.
355  template<typename _IIter, typename _OutputIterator>
356    inline _OutputIterator
357    partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
358    {
359      typedef typename iterator_traits<_IIter>::value_type _ValueType;
360      return __gnu_parallel::partial_sum(__begin, __end,
361                                         __result, std::plus<_ValueType>());
362    }
363
364  // Public interface
365  template<typename _IIter, typename _OutputIterator,
366           typename _BinaryOperation>
367    inline _OutputIterator
368    partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
369                _BinaryOperation __binary_op)
370    {
371      typedef iterator_traits<_IIter> _ITraitsType;
372      typedef typename _ITraitsType::iterator_category _IIteratorCategory;
373
374      typedef iterator_traits<_OutputIterator> _OTraitsType;
375      typedef typename _OTraitsType::iterator_category _OIterCategory;
376
377      return __partial_sum_switch(__begin, __end, __result, __binary_op,
378				  _IIteratorCategory(), _OIterCategory());
379    }
380
381  // Sequential fallback.
382  template<typename _IIter, typename _OutputIterator>
383    inline _OutputIterator
384    adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
385                        __gnu_parallel::sequential_tag)
386    { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); }
387
388  // Sequential fallback.
389  template<typename _IIter, typename _OutputIterator,
390           typename _BinaryOperation>
391    inline _OutputIterator
392    adjacent_difference(_IIter __begin, _IIter __end,
393                        _OutputIterator __result, _BinaryOperation __bin_op,
394                        __gnu_parallel::sequential_tag)
395    { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end,
396						 __result, __bin_op); }
397
398  // Sequential fallback for input iterator case.
399  template<typename _IIter, typename _OutputIterator,
400           typename _BinaryOperation, typename _IteratorTag1,
401           typename _IteratorTag2>
402    inline _OutputIterator
403    __adjacent_difference_switch(_IIter __begin, _IIter __end,
404				 _OutputIterator __result,
405				 _BinaryOperation __bin_op, _IteratorTag1,
406				 _IteratorTag2)
407    { return adjacent_difference(__begin, __end, __result, __bin_op,
408                                 __gnu_parallel::sequential_tag()); }
409
410  // Parallel algorithm for random access iterators.
411  template<typename _IIter, typename _OutputIterator,
412           typename _BinaryOperation>
413    _OutputIterator
414    __adjacent_difference_switch(_IIter __begin, _IIter __end,
415				 _OutputIterator __result,
416				 _BinaryOperation __bin_op,
417				 random_access_iterator_tag,
418				 random_access_iterator_tag,
419				 __gnu_parallel::_Parallelism
420				 __parallelism_tag)
421    {
422      if (_GLIBCXX_PARALLEL_CONDITION(
423            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
424            >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
425            && __gnu_parallel::__is_parallel(__parallelism_tag)))
426        {
427          bool __dummy = true;
428          typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
429            random_access_iterator_tag> _ItTrip;
430          *__result = *__begin;
431          _ItTrip __begin_pair(__begin + 1, __result + 1),
432            __end_pair(__end, __result + (__end - __begin));
433          __gnu_parallel::__adjacent_difference_selector<_ItTrip>
434                                                            __functionality;
435          __gnu_parallel::
436            __for_each_template_random_access_ed(
437                __begin_pair, __end_pair, __bin_op, __functionality,
438                __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
439          return __functionality._M_finish_iterator;
440        }
441      else
442        return adjacent_difference(__begin, __end, __result, __bin_op,
443                                   __gnu_parallel::sequential_tag());
444    }
445
446  // Public interface.
447  template<typename _IIter, typename _OutputIterator>
448    inline _OutputIterator
449    adjacent_difference(_IIter __begin, _IIter __end,
450                        _OutputIterator __result,
451                        __gnu_parallel::_Parallelism __parallelism_tag)
452    {
453      typedef iterator_traits<_IIter> _TraitsType;
454      typedef typename _TraitsType::value_type _ValueType;
455      return adjacent_difference(__begin, __end, __result,
456				 std::minus<_ValueType>(),
457				 __parallelism_tag);
458    }
459
460  template<typename _IIter, typename _OutputIterator>
461    inline _OutputIterator
462    adjacent_difference(_IIter __begin, _IIter __end,
463                        _OutputIterator __result)
464    {
465      typedef iterator_traits<_IIter> _TraitsType;
466      typedef typename _TraitsType::value_type _ValueType;
467      return adjacent_difference(__begin, __end, __result,
468				 std::minus<_ValueType>());
469    }
470
471  template<typename _IIter, typename _OutputIterator,
472           typename _BinaryOperation>
473    inline _OutputIterator
474    adjacent_difference(_IIter __begin, _IIter __end,
475                        _OutputIterator __result, _BinaryOperation __binary_op,
476                        __gnu_parallel::_Parallelism __parallelism_tag)
477    {
478      typedef iterator_traits<_IIter> _ITraitsType;
479      typedef typename _ITraitsType::iterator_category _IIteratorCategory;
480
481      typedef iterator_traits<_OutputIterator> _OTraitsType;
482      typedef typename _OTraitsType::iterator_category _OIterCategory;
483
484      return __adjacent_difference_switch(__begin, __end, __result,
485					  __binary_op,
486					  _IIteratorCategory(),
487					  _OIterCategory(),
488					  __parallelism_tag);
489    }
490
491  template<typename _IIter, typename _OutputIterator,
492	   typename _BinaryOperation>
493    inline _OutputIterator
494    adjacent_difference(_IIter __begin, _IIter __end,
495			_OutputIterator __result, _BinaryOperation __binary_op)
496    {
497      typedef iterator_traits<_IIter> _ITraitsType;
498      typedef typename _ITraitsType::iterator_category _IIteratorCategory;
499
500      typedef iterator_traits<_OutputIterator> _OTraitsType;
501      typedef typename _OTraitsType::iterator_category _OIterCategory;
502
503      return __adjacent_difference_switch(__begin, __end, __result,
504					  __binary_op,
505					  _IIteratorCategory(),
506					  _OIterCategory());
507    }
508} // end namespace
509} // end namespace
510
511#endif /* _GLIBCXX_NUMERIC_H */
512