1// -*- C++ -*-
2
3// Copyright (C) 2007-2013 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                      = __gnu_parallel::parallel_unbalanced)
90    {
91      if (_GLIBCXX_PARALLEL_CONDITION(
92            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
93            >= __gnu_parallel::_Settings::get().accumulate_minimal_n
94            && __gnu_parallel::__is_parallel(__parallelism_tag)))
95        {
96          _Tp __res = __init;
97          __gnu_parallel::__accumulate_selector<__RAIter>
98            __my_selector;
99          __gnu_parallel::
100            __for_each_template_random_access_ed(__begin, __end,
101						 __gnu_parallel::_Nothing(),
102						 __my_selector,
103						 __gnu_parallel::
104						 __accumulate_binop_reduct
105					       <_BinaryOperation>(__binary_op),
106						 __res, __res, -1);
107          return __res;
108        }
109      else
110        return accumulate(__begin, __end, __init, __binary_op, 
111                          __gnu_parallel::sequential_tag());
112    }
113
114  // Public interface.
115  template<typename _IIter, typename _Tp>
116    inline _Tp
117    accumulate(_IIter __begin, _IIter __end, _Tp __init, 
118               __gnu_parallel::_Parallelism __parallelism_tag)
119    {
120      typedef std::iterator_traits<_IIter> _IteratorTraits;
121      typedef typename _IteratorTraits::value_type _ValueType;
122      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
123
124      return __accumulate_switch(__begin, __end, __init,
125				 __gnu_parallel::_Plus<_Tp, _ValueType>(),
126				 _IteratorCategory(), __parallelism_tag);
127    }
128
129  template<typename _IIter, typename _Tp>
130    inline _Tp
131    accumulate(_IIter __begin, _IIter __end, _Tp __init)
132    {
133      typedef std::iterator_traits<_IIter> _IteratorTraits;
134      typedef typename _IteratorTraits::value_type _ValueType;
135      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
136
137      return __accumulate_switch(__begin, __end, __init,
138				 __gnu_parallel::_Plus<_Tp, _ValueType>(),
139				 _IteratorCategory());
140    }
141
142  template<typename _IIter, typename _Tp, typename _BinaryOperation>
143    inline _Tp
144    accumulate(_IIter __begin, _IIter __end, _Tp __init, 
145               _BinaryOperation __binary_op, 
146               __gnu_parallel::_Parallelism __parallelism_tag)
147    {
148      typedef iterator_traits<_IIter> _IteratorTraits;
149      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
150      return __accumulate_switch(__begin, __end, __init, __binary_op, 
151				 _IteratorCategory(), __parallelism_tag);
152    }
153
154  template<typename _IIter, typename _Tp, typename _BinaryOperation>
155    inline _Tp
156    accumulate(_IIter __begin, _IIter __end, _Tp __init, 
157               _BinaryOperation __binary_op) 
158    {
159      typedef iterator_traits<_IIter> _IteratorTraits;
160      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
161      return __accumulate_switch(__begin, __end, __init, __binary_op, 
162				 _IteratorCategory());
163    }
164
165
166  // Sequential fallback.
167  template<typename _IIter1, typename _IIter2, typename _Tp>
168    inline _Tp
169    inner_product(_IIter1 __first1, _IIter1 __last1, 
170                  _IIter2 __first2, _Tp __init,
171                  __gnu_parallel::sequential_tag)
172    { return _GLIBCXX_STD_A::inner_product(
173                               __first1, __last1, __first2, __init); }
174
175  template<typename _IIter1, typename _IIter2, typename _Tp,
176           typename _BinaryFunction1, typename _BinaryFunction2>
177    inline _Tp
178    inner_product(_IIter1 __first1, _IIter1 __last1,
179                  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 
180                  _BinaryFunction2 __binary_op2,
181                  __gnu_parallel::sequential_tag)
182    { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init,
183                                           __binary_op1, __binary_op2); }
184
185  // Parallel algorithm for random access iterators.
186  template<typename _RAIter1, typename _RAIter2,
187           typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
188    _Tp
189    __inner_product_switch(_RAIter1 __first1,
190			   _RAIter1 __last1,
191			   _RAIter2 __first2, _Tp __init,
192			   _BinaryFunction1 __binary_op1,
193			   _BinaryFunction2 __binary_op2,
194			   random_access_iterator_tag,
195			   random_access_iterator_tag,
196			   __gnu_parallel::_Parallelism __parallelism_tag
197			   = __gnu_parallel::parallel_unbalanced)
198    {
199      if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
200                                      >= __gnu_parallel::_Settings::get().
201                                      accumulate_minimal_n
202                                      && __gnu_parallel::
203                                      __is_parallel(__parallelism_tag)))
204        {
205          _Tp __res = __init;
206          __gnu_parallel::
207            __inner_product_selector<_RAIter1,
208            _RAIter2, _Tp> __my_selector(__first1, __first2);
209          __gnu_parallel::
210            __for_each_template_random_access_ed(
211                __first1, __last1, __binary_op2, __my_selector, __binary_op1,
212                __res, __res, -1);
213          return __res;
214        }
215      else
216        return inner_product(__first1, __last1, __first2, __init, 
217                             __gnu_parallel::sequential_tag());
218    }
219
220  // No parallelism for input iterators.
221  template<typename _IIter1, typename _IIter2, typename _Tp,
222           typename _BinaryFunction1, typename _BinaryFunction2,
223           typename _IteratorTag1, typename _IteratorTag2>
224    inline _Tp
225    __inner_product_switch(_IIter1 __first1, _IIter1 __last1, 
226			   _IIter2 __first2, _Tp __init, 
227			   _BinaryFunction1 __binary_op1,
228			   _BinaryFunction2 __binary_op2, 
229			   _IteratorTag1, _IteratorTag2)
230    { return inner_product(__first1, __last1, __first2, __init, __binary_op1,
231			   __binary_op2, __gnu_parallel::sequential_tag()); }
232
233  template<typename _IIter1, typename _IIter2, typename _Tp,
234           typename _BinaryFunction1, typename _BinaryFunction2>
235    inline _Tp
236    inner_product(_IIter1 __first1, _IIter1 __last1, 
237                  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 
238                  _BinaryFunction2 __binary_op2, 
239                  __gnu_parallel::_Parallelism __parallelism_tag)
240    {
241      typedef iterator_traits<_IIter1> _TraitsType1;
242      typedef typename _TraitsType1::iterator_category _IteratorCategory1;
243
244      typedef iterator_traits<_IIter2> _TraitsType2;
245      typedef typename _TraitsType2::iterator_category _IteratorCategory2;
246
247      return __inner_product_switch(__first1, __last1, __first2, __init,
248				    __binary_op1, __binary_op2,
249				    _IteratorCategory1(), _IteratorCategory2(),
250				    __parallelism_tag);
251    }
252
253  template<typename _IIter1, typename _IIter2, typename _Tp,
254           typename _BinaryFunction1, typename _BinaryFunction2>
255    inline _Tp
256    inner_product(_IIter1 __first1, _IIter1 __last1, 
257                  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 
258                  _BinaryFunction2 __binary_op2)
259    {
260      typedef iterator_traits<_IIter1> _TraitsType1;
261      typedef typename _TraitsType1::iterator_category _IteratorCategory1;
262
263      typedef iterator_traits<_IIter2> _TraitsType2;
264      typedef typename _TraitsType2::iterator_category _IteratorCategory2;
265
266      return __inner_product_switch(__first1, __last1, __first2, __init,
267				    __binary_op1, __binary_op2,
268				    _IteratorCategory1(),
269				    _IteratorCategory2());
270    }
271
272  template<typename _IIter1, typename _IIter2, typename _Tp>
273    inline _Tp
274    inner_product(_IIter1 __first1, _IIter1 __last1, 
275                  _IIter2 __first2, _Tp __init, 
276                  __gnu_parallel::_Parallelism __parallelism_tag)
277    {
278      typedef iterator_traits<_IIter1> _TraitsType1;
279      typedef typename _TraitsType1::value_type _ValueType1;
280      typedef iterator_traits<_IIter2> _TraitsType2;
281      typedef typename _TraitsType2::value_type _ValueType2;
282
283      typedef typename
284        __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
285        _MultipliesResultType;
286      return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
287                           __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
288                           __gnu_parallel::
289                           _Multiplies<_ValueType1, _ValueType2>(),
290                           __parallelism_tag);
291    }
292
293  template<typename _IIter1, typename _IIter2, typename _Tp>
294    inline _Tp
295    inner_product(_IIter1 __first1, _IIter1 __last1, 
296                  _IIter2 __first2, _Tp __init)
297    {
298      typedef iterator_traits<_IIter1> _TraitsType1;
299      typedef typename _TraitsType1::value_type _ValueType1;
300      typedef iterator_traits<_IIter2> _TraitsType2;
301      typedef typename _TraitsType2::value_type _ValueType2;
302
303      typedef typename
304        __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
305        _MultipliesResultType;
306      return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
307                           __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
308                           __gnu_parallel::
309                           _Multiplies<_ValueType1, _ValueType2>());
310    }
311
312  // Sequential fallback.
313  template<typename _IIter, typename _OutputIterator>
314    inline _OutputIterator
315    partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
316                __gnu_parallel::sequential_tag)
317    { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); }
318
319  // Sequential fallback.
320  template<typename _IIter, typename _OutputIterator,
321	   typename _BinaryOperation>
322    inline _OutputIterator
323    partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
324                _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
325    { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
326
327  // Sequential fallback for input iterator case.
328  template<typename _IIter, typename _OutputIterator,
329           typename _BinaryOperation, typename _IteratorTag1,
330           typename _IteratorTag2>
331    inline _OutputIterator
332    __partial_sum_switch(_IIter __begin, _IIter __end,
333			 _OutputIterator __result, _BinaryOperation __bin_op,
334			 _IteratorTag1, _IteratorTag2)
335    { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
336
337  // Parallel algorithm for random access iterators.
338  template<typename _IIter, typename _OutputIterator,
339           typename _BinaryOperation>
340    _OutputIterator
341    __partial_sum_switch(_IIter __begin, _IIter __end,
342			 _OutputIterator __result, _BinaryOperation __bin_op,
343			 random_access_iterator_tag,
344			 random_access_iterator_tag)
345    {
346      if (_GLIBCXX_PARALLEL_CONDITION(
347            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
348            >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
349        return __gnu_parallel::__parallel_partial_sum(__begin, __end,
350						      __result, __bin_op);
351      else
352        return partial_sum(__begin, __end, __result, __bin_op,
353                           __gnu_parallel::sequential_tag());
354    }
355
356  // Public interface.
357  template<typename _IIter, typename _OutputIterator>
358    inline _OutputIterator
359    partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
360    {
361      typedef typename iterator_traits<_IIter>::value_type _ValueType;
362      return __gnu_parallel::partial_sum(__begin, __end,
363                                         __result, std::plus<_ValueType>());
364    }
365
366  // Public interface
367  template<typename _IIter, typename _OutputIterator,
368           typename _BinaryOperation>
369    inline _OutputIterator
370    partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
371                _BinaryOperation __binary_op)
372    {
373      typedef iterator_traits<_IIter> _ITraitsType;
374      typedef typename _ITraitsType::iterator_category _IIteratorCategory;
375
376      typedef iterator_traits<_OutputIterator> _OTraitsType;
377      typedef typename _OTraitsType::iterator_category _OIterCategory;
378
379      return __partial_sum_switch(__begin, __end, __result, __binary_op,
380				  _IIteratorCategory(), _OIterCategory());
381    }
382
383  // Sequential fallback.
384  template<typename _IIter, typename _OutputIterator>
385    inline _OutputIterator
386    adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
387                        __gnu_parallel::sequential_tag)
388    { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); }
389
390  // Sequential fallback.
391  template<typename _IIter, typename _OutputIterator,
392           typename _BinaryOperation>
393    inline _OutputIterator
394    adjacent_difference(_IIter __begin, _IIter __end,
395                        _OutputIterator __result, _BinaryOperation __bin_op,
396                        __gnu_parallel::sequential_tag)
397    { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end,
398						 __result, __bin_op); }
399
400  // Sequential fallback for input iterator case.
401  template<typename _IIter, typename _OutputIterator,
402           typename _BinaryOperation, typename _IteratorTag1,
403           typename _IteratorTag2>
404    inline _OutputIterator
405    __adjacent_difference_switch(_IIter __begin, _IIter __end,
406				 _OutputIterator __result,
407				 _BinaryOperation __bin_op, _IteratorTag1,
408				 _IteratorTag2)
409    { return adjacent_difference(__begin, __end, __result, __bin_op,
410                                 __gnu_parallel::sequential_tag()); }
411
412  // Parallel algorithm for random access iterators.
413  template<typename _IIter, typename _OutputIterator,
414           typename _BinaryOperation>
415    _OutputIterator
416    __adjacent_difference_switch(_IIter __begin, _IIter __end,
417				 _OutputIterator __result,
418				 _BinaryOperation __bin_op,
419				 random_access_iterator_tag,
420				 random_access_iterator_tag,
421				 __gnu_parallel::_Parallelism
422				 __parallelism_tag
423				 = __gnu_parallel::parallel_balanced)
424    {
425      if (_GLIBCXX_PARALLEL_CONDITION(
426            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
427            >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
428            && __gnu_parallel::__is_parallel(__parallelism_tag)))
429        {
430          bool __dummy = true;
431          typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
432            random_access_iterator_tag> _ItTrip;
433          *__result = *__begin;
434          _ItTrip __begin_pair(__begin + 1, __result + 1),
435            __end_pair(__end, __result + (__end - __begin));
436          __gnu_parallel::__adjacent_difference_selector<_ItTrip>
437                                                            __functionality;
438          __gnu_parallel::
439            __for_each_template_random_access_ed(
440                __begin_pair, __end_pair, __bin_op, __functionality,
441                __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
442          return __functionality._M_finish_iterator;
443        }
444      else
445        return adjacent_difference(__begin, __end, __result, __bin_op, 
446                                   __gnu_parallel::sequential_tag());
447    }
448
449  // Public interface.
450  template<typename _IIter, typename _OutputIterator>
451    inline _OutputIterator
452    adjacent_difference(_IIter __begin, _IIter __end,
453                        _OutputIterator __result,
454                        __gnu_parallel::_Parallelism __parallelism_tag)
455    {
456      typedef iterator_traits<_IIter> _TraitsType;
457      typedef typename _TraitsType::value_type _ValueType;
458      return adjacent_difference(__begin, __end, __result,
459				 std::minus<_ValueType>(),
460				 __parallelism_tag);
461    }
462
463  template<typename _IIter, typename _OutputIterator>
464    inline _OutputIterator
465    adjacent_difference(_IIter __begin, _IIter __end,
466                        _OutputIterator __result)
467    {
468      typedef iterator_traits<_IIter> _TraitsType;
469      typedef typename _TraitsType::value_type _ValueType;
470      return adjacent_difference(__begin, __end, __result,
471				 std::minus<_ValueType>());
472    }
473
474  template<typename _IIter, typename _OutputIterator,
475           typename _BinaryOperation>
476    inline _OutputIterator
477    adjacent_difference(_IIter __begin, _IIter __end,
478                        _OutputIterator __result, _BinaryOperation __binary_op,
479                        __gnu_parallel::_Parallelism __parallelism_tag)
480    {
481      typedef iterator_traits<_IIter> _ITraitsType;
482      typedef typename _ITraitsType::iterator_category _IIteratorCategory;
483
484      typedef iterator_traits<_OutputIterator> _OTraitsType;
485      typedef typename _OTraitsType::iterator_category _OIterCategory;
486
487      return __adjacent_difference_switch(__begin, __end, __result,
488					  __binary_op,
489					  _IIteratorCategory(),
490					  _OIterCategory(),
491					  __parallelism_tag);
492    }
493
494  template<typename _IIter, typename _OutputIterator,
495	   typename _BinaryOperation>
496    inline _OutputIterator
497    adjacent_difference(_IIter __begin, _IIter __end,
498			_OutputIterator __result, _BinaryOperation __binary_op)
499    {
500      typedef iterator_traits<_IIter> _ITraitsType;
501      typedef typename _ITraitsType::iterator_category _IIteratorCategory;
502
503      typedef iterator_traits<_OutputIterator> _OTraitsType;
504      typedef typename _OTraitsType::iterator_category _OIterCategory;
505
506      return __adjacent_difference_switch(__begin, __end, __result,
507					  __binary_op,
508					  _IIteratorCategory(),
509					  _OIterCategory());
510    }
511} // end namespace
512} // end namespace
513
514#endif /* _GLIBCXX_NUMERIC_H */
515