libstdc++
numeric
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007-2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /**
00026  * @file parallel/numeric
00027 *
00028  * @brief Parallel STL function calls corresponding to stl_numeric.h.
00029  * The functions defined here mainly do case switches and
00030  * call the actual parallelized versions in other files.
00031  * Inlining policy: Functions that basically only contain one function call,
00032  * are declared inline.
00033  *  This file is a GNU parallel extension to the Standard C++ Library.
00034  */
00035 
00036 // Written by Johannes Singler and Felix Putze.
00037 
00038 #ifndef _GLIBCXX_PARALLEL_NUMERIC_H
00039 #define _GLIBCXX_PARALLEL_NUMERIC_H 1
00040 
00041 #include <numeric>
00042 #include <bits/stl_function.h>
00043 #include <parallel/numericfwd.h>
00044 #include <parallel/iterator.h>
00045 #include <parallel/for_each.h>
00046 #include <parallel/for_each_selectors.h>
00047 #include <parallel/partial_sum.h>
00048 
00049 namespace std _GLIBCXX_VISIBILITY(default)
00050 {
00051 namespace __parallel
00052 {
00053   // Sequential fallback.
00054   template<typename _IIter, typename _Tp>
00055     inline _Tp
00056     accumulate(_IIter __begin, _IIter __end, _Tp __init, 
00057                __gnu_parallel::sequential_tag)
00058     { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init); }
00059 
00060   template<typename _IIter, typename _Tp, typename _BinaryOperation>
00061     inline _Tp
00062     accumulate(_IIter __begin, _IIter __end, _Tp __init,
00063                _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
00064     { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init, __binary_op); }
00065 
00066   // Sequential fallback for input iterator case.
00067   template<typename _IIter, typename _Tp, typename _IteratorTag>
00068     inline _Tp
00069     __accumulate_switch(_IIter __begin, _IIter __end,
00070                       _Tp __init, _IteratorTag) 
00071     { return accumulate(__begin, __end, __init,
00072                         __gnu_parallel::sequential_tag()); }
00073 
00074   template<typename _IIter, typename _Tp, typename _BinaryOperation,
00075            typename _IteratorTag>
00076     inline _Tp
00077     __accumulate_switch(_IIter __begin, _IIter __end, _Tp __init, 
00078                       _BinaryOperation __binary_op, _IteratorTag)
00079     { return accumulate(__begin, __end, __init, __binary_op, 
00080                         __gnu_parallel::sequential_tag()); }
00081 
00082   // Parallel algorithm for random access iterators.
00083   template<typename __RAIter, typename _Tp, typename _BinaryOperation>
00084     _Tp
00085     __accumulate_switch(__RAIter __begin, __RAIter __end, 
00086                       _Tp __init, _BinaryOperation __binary_op, 
00087                       random_access_iterator_tag, 
00088                       __gnu_parallel::_Parallelism __parallelism_tag)
00089     {
00090       if (_GLIBCXX_PARALLEL_CONDITION(
00091             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
00092             >= __gnu_parallel::_Settings::get().accumulate_minimal_n
00093             && __gnu_parallel::__is_parallel(__parallelism_tag)))
00094         {
00095           _Tp __res = __init;
00096           __gnu_parallel::__accumulate_selector<__RAIter>
00097             __my_selector;
00098           __gnu_parallel::
00099             __for_each_template_random_access_ed(__begin, __end,
00100                                                  __gnu_parallel::_Nothing(),
00101                                                  __my_selector,
00102                                                  __gnu_parallel::
00103                                                  __accumulate_binop_reduct
00104                                                <_BinaryOperation>(__binary_op),
00105                                                  __res, __res, -1);
00106           return __res;
00107         }
00108       else
00109         return accumulate(__begin, __end, __init, __binary_op, 
00110                           __gnu_parallel::sequential_tag());
00111     }
00112 
00113   // Public interface.
00114   template<typename _IIter, typename _Tp>
00115     inline _Tp
00116     accumulate(_IIter __begin, _IIter __end, _Tp __init, 
00117                __gnu_parallel::_Parallelism __parallelism_tag)
00118     {
00119       typedef std::iterator_traits<_IIter> _IteratorTraits;
00120       typedef typename _IteratorTraits::value_type _ValueType;
00121       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00122 
00123       return __accumulate_switch(__begin, __end, __init,
00124                                  __gnu_parallel::_Plus<_Tp, _ValueType>(),
00125                                  _IteratorCategory(), __parallelism_tag);
00126     }
00127 
00128   template<typename _IIter, typename _Tp>
00129     inline _Tp
00130     accumulate(_IIter __begin, _IIter __end, _Tp __init)
00131     {
00132       typedef std::iterator_traits<_IIter> _IteratorTraits;
00133       typedef typename _IteratorTraits::value_type _ValueType;
00134       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00135 
00136       return __accumulate_switch(__begin, __end, __init,
00137                                  __gnu_parallel::_Plus<_Tp, _ValueType>(),
00138                                  _IteratorCategory());
00139     }
00140 
00141   template<typename _IIter, typename _Tp, typename _BinaryOperation>
00142     inline _Tp
00143     accumulate(_IIter __begin, _IIter __end, _Tp __init, 
00144                _BinaryOperation __binary_op, 
00145                __gnu_parallel::_Parallelism __parallelism_tag)
00146     {
00147       typedef iterator_traits<_IIter> _IteratorTraits;
00148       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00149       return __accumulate_switch(__begin, __end, __init, __binary_op, 
00150                                  _IteratorCategory(), __parallelism_tag);
00151     }
00152 
00153   template<typename _IIter, typename _Tp, typename _BinaryOperation>
00154     inline _Tp
00155     accumulate(_IIter __begin, _IIter __end, _Tp __init, 
00156                _BinaryOperation __binary_op) 
00157     {
00158       typedef iterator_traits<_IIter> _IteratorTraits;
00159       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00160       return __accumulate_switch(__begin, __end, __init, __binary_op, 
00161                                  _IteratorCategory());
00162     }
00163 
00164 
00165   // Sequential fallback.
00166   template<typename _IIter1, typename _IIter2, typename _Tp>
00167     inline _Tp
00168     inner_product(_IIter1 __first1, _IIter1 __last1, 
00169                   _IIter2 __first2, _Tp __init,
00170                   __gnu_parallel::sequential_tag)
00171     { return _GLIBCXX_STD_A::inner_product(
00172                                __first1, __last1, __first2, __init); }
00173 
00174   template<typename _IIter1, typename _IIter2, typename _Tp,
00175            typename _BinaryFunction1, typename _BinaryFunction2>
00176     inline _Tp
00177     inner_product(_IIter1 __first1, _IIter1 __last1,
00178                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 
00179                   _BinaryFunction2 __binary_op2,
00180                   __gnu_parallel::sequential_tag)
00181     { return _GLIBCXX_STD_A::inner_product(__first1, __last1, __first2, __init,
00182                                            __binary_op1, __binary_op2); }
00183 
00184   // Parallel algorithm for random access iterators.
00185   template<typename _RAIter1, typename _RAIter2,
00186            typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
00187     _Tp
00188     __inner_product_switch(_RAIter1 __first1,
00189                            _RAIter1 __last1,
00190                            _RAIter2 __first2, _Tp __init,
00191                            _BinaryFunction1 __binary_op1,
00192                            _BinaryFunction2 __binary_op2,
00193                            random_access_iterator_tag,
00194                            random_access_iterator_tag,
00195                            __gnu_parallel::_Parallelism __parallelism_tag)
00196     {
00197       if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
00198                                       >= __gnu_parallel::_Settings::get().
00199                                       accumulate_minimal_n
00200                                       && __gnu_parallel::
00201                                       __is_parallel(__parallelism_tag)))
00202         {
00203           _Tp __res = __init;
00204           __gnu_parallel::
00205             __inner_product_selector<_RAIter1,
00206             _RAIter2, _Tp> __my_selector(__first1, __first2);
00207           __gnu_parallel::
00208             __for_each_template_random_access_ed(
00209                 __first1, __last1, __binary_op2, __my_selector, __binary_op1,
00210                 __res, __res, -1);
00211           return __res;
00212         }
00213       else
00214         return inner_product(__first1, __last1, __first2, __init, 
00215                              __gnu_parallel::sequential_tag());
00216     }
00217 
00218   // No parallelism for input iterators.
00219   template<typename _IIter1, typename _IIter2, typename _Tp,
00220            typename _BinaryFunction1, typename _BinaryFunction2,
00221            typename _IteratorTag1, typename _IteratorTag2>
00222     inline _Tp
00223     __inner_product_switch(_IIter1 __first1, _IIter1 __last1, 
00224                            _IIter2 __first2, _Tp __init, 
00225                            _BinaryFunction1 __binary_op1,
00226                            _BinaryFunction2 __binary_op2, 
00227                            _IteratorTag1, _IteratorTag2)
00228     { return inner_product(__first1, __last1, __first2, __init, __binary_op1,
00229                            __binary_op2, __gnu_parallel::sequential_tag()); }
00230 
00231   template<typename _IIter1, typename _IIter2, typename _Tp,
00232            typename _BinaryFunction1, typename _BinaryFunction2>
00233     inline _Tp
00234     inner_product(_IIter1 __first1, _IIter1 __last1, 
00235                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 
00236                   _BinaryFunction2 __binary_op2, 
00237                   __gnu_parallel::_Parallelism __parallelism_tag)
00238     {
00239       typedef iterator_traits<_IIter1> _TraitsType1;
00240       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00241 
00242       typedef iterator_traits<_IIter2> _TraitsType2;
00243       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00244 
00245       return __inner_product_switch(__first1, __last1, __first2, __init,
00246                                     __binary_op1, __binary_op2,
00247                                     _IteratorCategory1(), _IteratorCategory2(),
00248                                     __parallelism_tag);
00249     }
00250 
00251   template<typename _IIter1, typename _IIter2, typename _Tp,
00252            typename _BinaryFunction1, typename _BinaryFunction2>
00253     inline _Tp
00254     inner_product(_IIter1 __first1, _IIter1 __last1, 
00255                   _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 
00256                   _BinaryFunction2 __binary_op2)
00257     {
00258       typedef iterator_traits<_IIter1> _TraitsType1;
00259       typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00260 
00261       typedef iterator_traits<_IIter2> _TraitsType2;
00262       typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00263 
00264       return __inner_product_switch(__first1, __last1, __first2, __init,
00265                                     __binary_op1, __binary_op2,
00266                                     _IteratorCategory1(),
00267                                     _IteratorCategory2());
00268     }
00269 
00270   template<typename _IIter1, typename _IIter2, typename _Tp>
00271     inline _Tp
00272     inner_product(_IIter1 __first1, _IIter1 __last1, 
00273                   _IIter2 __first2, _Tp __init, 
00274                   __gnu_parallel::_Parallelism __parallelism_tag)
00275     {
00276       typedef iterator_traits<_IIter1> _TraitsType1;
00277       typedef typename _TraitsType1::value_type _ValueType1;
00278       typedef iterator_traits<_IIter2> _TraitsType2;
00279       typedef typename _TraitsType2::value_type _ValueType2;
00280 
00281       typedef typename
00282         __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
00283         _MultipliesResultType;
00284       return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
00285                            __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
00286                            __gnu_parallel::
00287                            _Multiplies<_ValueType1, _ValueType2>(),
00288                            __parallelism_tag);
00289     }
00290 
00291   template<typename _IIter1, typename _IIter2, typename _Tp>
00292     inline _Tp
00293     inner_product(_IIter1 __first1, _IIter1 __last1, 
00294                   _IIter2 __first2, _Tp __init)
00295     {
00296       typedef iterator_traits<_IIter1> _TraitsType1;
00297       typedef typename _TraitsType1::value_type _ValueType1;
00298       typedef iterator_traits<_IIter2> _TraitsType2;
00299       typedef typename _TraitsType2::value_type _ValueType2;
00300 
00301       typedef typename
00302         __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
00303         _MultipliesResultType;
00304       return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,
00305                            __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
00306                            __gnu_parallel::
00307                            _Multiplies<_ValueType1, _ValueType2>());
00308     }
00309 
00310   // Sequential fallback.
00311   template<typename _IIter, typename _OutputIterator>
00312     inline _OutputIterator
00313     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
00314                 __gnu_parallel::sequential_tag)
00315     { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); }
00316 
00317   // Sequential fallback.
00318   template<typename _IIter, typename _OutputIterator,
00319            typename _BinaryOperation>
00320     inline _OutputIterator
00321     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
00322                 _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
00323     { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
00324 
00325   // Sequential fallback for input iterator case.
00326   template<typename _IIter, typename _OutputIterator,
00327            typename _BinaryOperation, typename _IteratorTag1,
00328            typename _IteratorTag2>
00329     inline _OutputIterator
00330     __partial_sum_switch(_IIter __begin, _IIter __end,
00331                          _OutputIterator __result, _BinaryOperation __bin_op,
00332                          _IteratorTag1, _IteratorTag2)
00333     { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result, __bin_op); }
00334 
00335   // Parallel algorithm for random access iterators.
00336   template<typename _IIter, typename _OutputIterator,
00337            typename _BinaryOperation>
00338     _OutputIterator
00339     __partial_sum_switch(_IIter __begin, _IIter __end,
00340                          _OutputIterator __result, _BinaryOperation __bin_op,
00341                          random_access_iterator_tag,
00342                          random_access_iterator_tag)
00343     {
00344       if (_GLIBCXX_PARALLEL_CONDITION(
00345             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
00346             >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
00347         return __gnu_parallel::__parallel_partial_sum(__begin, __end,
00348                                                       __result, __bin_op);
00349       else
00350         return partial_sum(__begin, __end, __result, __bin_op,
00351                            __gnu_parallel::sequential_tag());
00352     }
00353 
00354   // Public interface.
00355   template<typename _IIter, typename _OutputIterator>
00356     inline _OutputIterator
00357     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
00358     {
00359       typedef typename iterator_traits<_IIter>::value_type _ValueType;
00360       return __gnu_parallel::partial_sum(__begin, __end,
00361                                          __result, std::plus<_ValueType>());
00362     }
00363 
00364   // Public interface
00365   template<typename _IIter, typename _OutputIterator,
00366            typename _BinaryOperation>
00367     inline _OutputIterator
00368     partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
00369                 _BinaryOperation __binary_op)
00370     {
00371       typedef iterator_traits<_IIter> _ITraitsType;
00372       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
00373 
00374       typedef iterator_traits<_OutputIterator> _OTraitsType;
00375       typedef typename _OTraitsType::iterator_category _OIterCategory;
00376 
00377       return __partial_sum_switch(__begin, __end, __result, __binary_op,
00378                                   _IIteratorCategory(), _OIterCategory());
00379     }
00380 
00381   // Sequential fallback.
00382   template<typename _IIter, typename _OutputIterator>
00383     inline _OutputIterator
00384     adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
00385                         __gnu_parallel::sequential_tag)
00386     { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); }
00387 
00388   // Sequential fallback.
00389   template<typename _IIter, typename _OutputIterator,
00390            typename _BinaryOperation>
00391     inline _OutputIterator
00392     adjacent_difference(_IIter __begin, _IIter __end,
00393                         _OutputIterator __result, _BinaryOperation __bin_op,
00394                         __gnu_parallel::sequential_tag)
00395     { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end,
00396                                                  __result, __bin_op); }
00397 
00398   // Sequential fallback for input iterator case.
00399   template<typename _IIter, typename _OutputIterator,
00400            typename _BinaryOperation, typename _IteratorTag1,
00401            typename _IteratorTag2>
00402     inline _OutputIterator
00403     __adjacent_difference_switch(_IIter __begin, _IIter __end,
00404                                  _OutputIterator __result,
00405                                  _BinaryOperation __bin_op, _IteratorTag1,
00406                                  _IteratorTag2)
00407     { return adjacent_difference(__begin, __end, __result, __bin_op,
00408                                  __gnu_parallel::sequential_tag()); }
00409 
00410   // Parallel algorithm for random access iterators.
00411   template<typename _IIter, typename _OutputIterator,
00412            typename _BinaryOperation>
00413     _OutputIterator
00414     __adjacent_difference_switch(_IIter __begin, _IIter __end,
00415                                  _OutputIterator __result,
00416                                  _BinaryOperation __bin_op,
00417                                  random_access_iterator_tag,
00418                                  random_access_iterator_tag,
00419                                  __gnu_parallel::_Parallelism
00420                                  __parallelism_tag)
00421     {
00422       if (_GLIBCXX_PARALLEL_CONDITION(
00423             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
00424             >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
00425             && __gnu_parallel::__is_parallel(__parallelism_tag)))
00426         {
00427           bool __dummy = true;
00428           typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
00429             random_access_iterator_tag> _ItTrip;
00430           *__result = *__begin;
00431           _ItTrip __begin_pair(__begin + 1, __result + 1),
00432             __end_pair(__end, __result + (__end - __begin));
00433           __gnu_parallel::__adjacent_difference_selector<_ItTrip>
00434                                                             __functionality;
00435           __gnu_parallel::
00436             __for_each_template_random_access_ed(
00437                 __begin_pair, __end_pair, __bin_op, __functionality,
00438                 __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
00439           return __functionality._M_finish_iterator;
00440         }
00441       else
00442         return adjacent_difference(__begin, __end, __result, __bin_op, 
00443                                    __gnu_parallel::sequential_tag());
00444     }
00445 
00446   // Public interface.
00447   template<typename _IIter, typename _OutputIterator>
00448     inline _OutputIterator
00449     adjacent_difference(_IIter __begin, _IIter __end,
00450                         _OutputIterator __result,
00451                         __gnu_parallel::_Parallelism __parallelism_tag)
00452     {
00453       typedef iterator_traits<_IIter> _TraitsType;
00454       typedef typename _TraitsType::value_type _ValueType;
00455       return adjacent_difference(__begin, __end, __result,
00456                                  std::minus<_ValueType>(),
00457                                  __parallelism_tag);
00458     }
00459 
00460   template<typename _IIter, typename _OutputIterator>
00461     inline _OutputIterator
00462     adjacent_difference(_IIter __begin, _IIter __end,
00463                         _OutputIterator __result)
00464     {
00465       typedef iterator_traits<_IIter> _TraitsType;
00466       typedef typename _TraitsType::value_type _ValueType;
00467       return adjacent_difference(__begin, __end, __result,
00468                                  std::minus<_ValueType>());
00469     }
00470 
00471   template<typename _IIter, typename _OutputIterator,
00472            typename _BinaryOperation>
00473     inline _OutputIterator
00474     adjacent_difference(_IIter __begin, _IIter __end,
00475                         _OutputIterator __result, _BinaryOperation __binary_op,
00476                         __gnu_parallel::_Parallelism __parallelism_tag)
00477     {
00478       typedef iterator_traits<_IIter> _ITraitsType;
00479       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
00480 
00481       typedef iterator_traits<_OutputIterator> _OTraitsType;
00482       typedef typename _OTraitsType::iterator_category _OIterCategory;
00483 
00484       return __adjacent_difference_switch(__begin, __end, __result,
00485                                           __binary_op,
00486                                           _IIteratorCategory(),
00487                                           _OIterCategory(),
00488                                           __parallelism_tag);
00489     }
00490 
00491   template<typename _IIter, typename _OutputIterator,
00492            typename _BinaryOperation>
00493     inline _OutputIterator
00494     adjacent_difference(_IIter __begin, _IIter __end,
00495                         _OutputIterator __result, _BinaryOperation __binary_op)
00496     {
00497       typedef iterator_traits<_IIter> _ITraitsType;
00498       typedef typename _ITraitsType::iterator_category _IIteratorCategory;
00499 
00500       typedef iterator_traits<_OutputIterator> _OTraitsType;
00501       typedef typename _OTraitsType::iterator_category _OIterCategory;
00502 
00503       return __adjacent_difference_switch(__begin, __end, __result,
00504                                           __binary_op,
00505                                           _IIteratorCategory(),
00506                                           _OIterCategory());
00507     }
00508 } // end namespace
00509 } // end namespace
00510 
00511 #endif /* _GLIBCXX_NUMERIC_H */