// -*- C++ -*-// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.//// This file is part of the GNU ISO C++ Library. This library is free// software; you can redistribute it and/or modify it under the terms// of the GNU General Public License as published by the Free Software// Foundation; either version 3, or (at your option) any later// version.// This library is distributed in the hope that it will be useful, but// WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU// General Public License for more details.// Under Section 7 of GPL version 3, you are granted additional// permissions described in the GCC Runtime Library Exception, version// 3.1, as published by the Free Software Foundation.// You should have received a copy of the GNU General Public License and// a copy of the GCC Runtime Library Exception along with this program;// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see// <http://www.gnu.org/licenses/>./*** @file parallel/numeric** @brief Parallel STL function calls corresponding to stl_numeric.h.* The functions defined here mainly do case switches and* call the actual parallelized versions in other files.* Inlining policy: Functions that basically only contain one function call,* are declared inline.* This file is a GNU parallel extension to the Standard C++ Library.*/// Written by Johannes Singler and Felix Putze.#ifndef _GLIBCXX_PARALLEL_NUMERIC_H#define _GLIBCXX_PARALLEL_NUMERIC_H 1#include <numeric>#include <bits/stl_function.h>#include <parallel/numericfwd.h>#include <parallel/iterator.h>#include <parallel/for_each.h>#include <parallel/for_each_selectors.h>#include <parallel/partial_sum.h>namespace std{namespace __parallel{// Sequential fallback.template<typename _IIter, typename _Tp>inline _Tpaccumulate(_IIter __begin, _IIter __end, _Tp __init,__gnu_parallel::sequential_tag){ return _GLIBCXX_STD_P::accumulate(__begin, __end, __init); }template<typename _IIter, typename _Tp, typename _BinaryOperation>inline _Tpaccumulate(_IIter __begin, _IIter __end, _Tp __init,_BinaryOperation __binary_op, __gnu_parallel::sequential_tag){ return _GLIBCXX_STD_P::accumulate(__begin, __end, __init, __binary_op); }// Sequential fallback for input iterator case.template<typename _IIter, typename _Tp, typename _IteratorTag>inline _Tp__accumulate_switch(_IIter __begin, _IIter __end,_Tp __init, _IteratorTag){ return accumulate(__begin, __end, __init,__gnu_parallel::sequential_tag()); }template<typename _IIter, typename _Tp, typename _BinaryOperation,typename _IteratorTag>inline _Tp__accumulate_switch(_IIter __begin, _IIter __end, _Tp __init,_BinaryOperation __binary_op, _IteratorTag){ return accumulate(__begin, __end, __init, __binary_op,__gnu_parallel::sequential_tag()); }// Parallel algorithm for random access iterators.template<typename __RAIter, typename _Tp, typename _BinaryOperation>_Tp__accumulate_switch(__RAIter __begin, __RAIter __end,_Tp __init, _BinaryOperation __binary_op,random_access_iterator_tag,__gnu_parallel::_Parallelism __parallelism_tag= __gnu_parallel::parallel_unbalanced){if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)>= __gnu_parallel::_Settings::get().accumulate_minimal_n&& __gnu_parallel::__is_parallel(__parallelism_tag))){_Tp __res = __init;__gnu_parallel::__accumulate_selector<__RAIter>__my_selector;__gnu_parallel::__for_each_template_random_access_ed(__begin, __end,__gnu_parallel::_Nothing(),__my_selector,__gnu_parallel::__accumulate_binop_reduct<_BinaryOperation>(__binary_op),__res, __res, -1);return __res;}elsereturn accumulate(__begin, __end, __init, __binary_op,__gnu_parallel::sequential_tag());}// Public interface.template<typename _IIter, typename _Tp>inline _Tpaccumulate(_IIter __begin, _IIter __end, _Tp __init,__gnu_parallel::_Parallelism __parallelism_tag){typedef std::iterator_traits<_IIter> _IteratorTraits;typedef typename _IteratorTraits::value_type _ValueType;typedef typename _IteratorTraits::iterator_category _IteratorCategory;return __accumulate_switch(__begin, __end, __init,__gnu_parallel::_Plus<_Tp, _ValueType>(),_IteratorCategory(), __parallelism_tag);}template<typename _IIter, typename _Tp>inline _Tpaccumulate(_IIter __begin, _IIter __end, _Tp __init){typedef std::iterator_traits<_IIter> _IteratorTraits;typedef typename _IteratorTraits::value_type _ValueType;typedef typename _IteratorTraits::iterator_category _IteratorCategory;return __accumulate_switch(__begin, __end, __init,__gnu_parallel::_Plus<_Tp, _ValueType>(),_IteratorCategory());}template<typename _IIter, typename _Tp, typename _BinaryOperation>inline _Tpaccumulate(_IIter __begin, _IIter __end, _Tp __init,_BinaryOperation __binary_op,__gnu_parallel::_Parallelism __parallelism_tag){typedef iterator_traits<_IIter> _IteratorTraits;typedef typename _IteratorTraits::iterator_category _IteratorCategory;return __accumulate_switch(__begin, __end, __init, __binary_op,_IteratorCategory(), __parallelism_tag);}template<typename _IIter, typename _Tp, typename _BinaryOperation>inline _Tpaccumulate(_IIter __begin, _IIter __end, _Tp __init,_BinaryOperation __binary_op){typedef iterator_traits<_IIter> _IteratorTraits;typedef typename _IteratorTraits::iterator_category _IteratorCategory;return __accumulate_switch(__begin, __end, __init, __binary_op,_IteratorCategory());}// Sequential fallback.template<typename _IIter1, typename _IIter2, typename _Tp>inline _Tpinner_product(_IIter1 __first1, _IIter1 __last1,_IIter2 __first2, _Tp __init,__gnu_parallel::sequential_tag){ return _GLIBCXX_STD_P::inner_product(__first1, __last1, __first2, __init); }template<typename _IIter1, typename _IIter2, typename _Tp,typename _BinaryFunction1, typename _BinaryFunction2>inline _Tpinner_product(_IIter1 __first1, _IIter1 __last1,_IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,_BinaryFunction2 __binary_op2,__gnu_parallel::sequential_tag){ return _GLIBCXX_STD_P::inner_product(__first1, __last1, __first2, __init,__binary_op1, __binary_op2); }// Parallel algorithm for random access iterators.template<typename _RAIter1, typename _RAIter2,typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>_Tp__inner_product_switch(_RAIter1 __first1,_RAIter1 __last1,_RAIter2 __first2, _Tp __init,_BinaryFunction1 __binary_op1,_BinaryFunction2 __binary_op2,random_access_iterator_tag,random_access_iterator_tag,__gnu_parallel::_Parallelism __parallelism_tag= __gnu_parallel::parallel_unbalanced){if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)>= __gnu_parallel::_Settings::get().accumulate_minimal_n&& __gnu_parallel::__is_parallel(__parallelism_tag))){_Tp __res = __init;__gnu_parallel::__inner_product_selector<_RAIter1,_RAIter2, _Tp> __my_selector(__first1, __first2);__gnu_parallel::__for_each_template_random_access_ed(__first1, __last1, __binary_op2, __my_selector, __binary_op1,__res, __res, -1);return __res;}elsereturn inner_product(__first1, __last1, __first2, __init,__gnu_parallel::sequential_tag());}// No parallelism for input iterators.template<typename _IIter1, typename _IIter2, typename _Tp,typename _BinaryFunction1, typename _BinaryFunction2,typename _IteratorTag1, typename _IteratorTag2>inline _Tp__inner_product_switch(_IIter1 __first1, _IIter1 __last1,_IIter2 __first2, _Tp __init,_BinaryFunction1 __binary_op1,_BinaryFunction2 __binary_op2,_IteratorTag1, _IteratorTag2){ return inner_product(__first1, __last1, __first2, __init, __binary_op1,__binary_op2, __gnu_parallel::sequential_tag()); }template<typename _IIter1, typename _IIter2, typename _Tp,typename _BinaryFunction1, typename _BinaryFunction2>inline _Tpinner_product(_IIter1 __first1, _IIter1 __last1,_IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,_BinaryFunction2 __binary_op2,__gnu_parallel::_Parallelism __parallelism_tag){typedef iterator_traits<_IIter1> _TraitsType1;typedef typename _TraitsType1::iterator_category _IteratorCategory1;typedef iterator_traits<_IIter2> _TraitsType2;typedef typename _TraitsType2::iterator_category _IteratorCategory2;return __inner_product_switch(__first1, __last1, __first2, __init,__binary_op1, __binary_op2,_IteratorCategory1(), _IteratorCategory2(),__parallelism_tag);}template<typename _IIter1, typename _IIter2, typename _Tp,typename _BinaryFunction1, typename _BinaryFunction2>inline _Tpinner_product(_IIter1 __first1, _IIter1 __last1,_IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,_BinaryFunction2 __binary_op2){typedef iterator_traits<_IIter1> _TraitsType1;typedef typename _TraitsType1::iterator_category _IteratorCategory1;typedef iterator_traits<_IIter2> _TraitsType2;typedef typename _TraitsType2::iterator_category _IteratorCategory2;return __inner_product_switch(__first1, __last1, __first2, __init,__binary_op1, __binary_op2,_IteratorCategory1(),_IteratorCategory2());}template<typename _IIter1, typename _IIter2, typename _Tp>inline _Tpinner_product(_IIter1 __first1, _IIter1 __last1,_IIter2 __first2, _Tp __init,__gnu_parallel::_Parallelism __parallelism_tag){typedef iterator_traits<_IIter1> _TraitsType1;typedef typename _TraitsType1::value_type _ValueType1;typedef iterator_traits<_IIter2> _TraitsType2;typedef typename _TraitsType2::value_type _ValueType2;typedef typename__gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type_MultipliesResultType;return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,__gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),__gnu_parallel::_Multiplies<_ValueType1, _ValueType2>(),__parallelism_tag);}template<typename _IIter1, typename _IIter2, typename _Tp>inline _Tpinner_product(_IIter1 __first1, _IIter1 __last1,_IIter2 __first2, _Tp __init){typedef iterator_traits<_IIter1> _TraitsType1;typedef typename _TraitsType1::value_type _ValueType1;typedef iterator_traits<_IIter2> _TraitsType2;typedef typename _TraitsType2::value_type _ValueType2;typedef typename__gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type_MultipliesResultType;return __gnu_parallel::inner_product(__first1, __last1, __first2, __init,__gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),__gnu_parallel::_Multiplies<_ValueType1, _ValueType2>());}// Sequential fallback.template<typename _IIter, typename _OutputIterator>inline _OutputIteratorpartial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,__gnu_parallel::sequential_tag){ return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result); }// Sequential fallback.template<typename _IIter, typename _OutputIterator,typename _BinaryOperation>inline _OutputIteratorpartial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,_BinaryOperation __bin_op, __gnu_parallel::sequential_tag){ return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result, __bin_op); }// Sequential fallback for input iterator case.template<typename _IIter, typename _OutputIterator,typename _BinaryOperation, typename _IteratorTag1,typename _IteratorTag2>inline _OutputIterator__partial_sum_switch(_IIter __begin, _IIter __end,_OutputIterator __result, _BinaryOperation __bin_op,_IteratorTag1, _IteratorTag2){ return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result, __bin_op); }// Parallel algorithm for random access iterators.template<typename _IIter, typename _OutputIterator,typename _BinaryOperation>_OutputIterator__partial_sum_switch(_IIter __begin, _IIter __end,_OutputIterator __result, _BinaryOperation __bin_op,random_access_iterator_tag,random_access_iterator_tag){if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)>= __gnu_parallel::_Settings::get().partial_sum_minimal_n))return __gnu_parallel::__parallel_partial_sum(__begin, __end,__result, __bin_op);elsereturn partial_sum(__begin, __end, __result, __bin_op,__gnu_parallel::sequential_tag());}// Public interface.template<typename _IIter, typename _OutputIterator>inline _OutputIteratorpartial_sum(_IIter __begin, _IIter __end, _OutputIterator __result){typedef typename iterator_traits<_IIter>::value_type _ValueType;return __gnu_parallel::partial_sum(__begin, __end,__result, std::plus<_ValueType>());}// Public interfacetemplate<typename _IIter, typename _OutputIterator,typename _BinaryOperation>inline _OutputIteratorpartial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,_BinaryOperation __binary_op){typedef iterator_traits<_IIter> _ITraitsType;typedef typename _ITraitsType::iterator_category _IIteratorCategory;typedef iterator_traits<_OutputIterator> _OTraitsType;typedef typename _OTraitsType::iterator_category _OIterCategory;return __partial_sum_switch(__begin, __end, __result, __binary_op,_IIteratorCategory(), _OIterCategory());}// Sequential fallback.template<typename _IIter, typename _OutputIterator>inline _OutputIteratoradjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,__gnu_parallel::sequential_tag){ return _GLIBCXX_STD_P::adjacent_difference(__begin, __end, __result); }// Sequential fallback.template<typename _IIter, typename _OutputIterator,typename _BinaryOperation>inline _OutputIteratoradjacent_difference(_IIter __begin, _IIter __end,_OutputIterator __result, _BinaryOperation __bin_op,__gnu_parallel::sequential_tag){ return _GLIBCXX_STD_P::adjacent_difference(__begin, __end,__result, __bin_op); }// Sequential fallback for input iterator case.template<typename _IIter, typename _OutputIterator,typename _BinaryOperation, typename _IteratorTag1,typename _IteratorTag2>inline _OutputIterator__adjacent_difference_switch(_IIter __begin, _IIter __end,_OutputIterator __result,_BinaryOperation __bin_op, _IteratorTag1,_IteratorTag2){ return adjacent_difference(__begin, __end, __result, __bin_op,__gnu_parallel::sequential_tag()); }// Parallel algorithm for random access iterators.template<typename _IIter, typename _OutputIterator,typename _BinaryOperation>_OutputIterator__adjacent_difference_switch(_IIter __begin, _IIter __end,_OutputIterator __result,_BinaryOperation __bin_op,random_access_iterator_tag,random_access_iterator_tag,__gnu_parallel::_Parallelism__parallelism_tag= __gnu_parallel::parallel_balanced){if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)>= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n&& __gnu_parallel::__is_parallel(__parallelism_tag))){bool __dummy = true;typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,random_access_iterator_tag> _ItTrip;*__result = *__begin;_ItTrip __begin_pair(__begin + 1, __result + 1),__end_pair(__end, __result + (__end - __begin));__gnu_parallel::__adjacent_difference_selector<_ItTrip>__functionality;__gnu_parallel::__for_each_template_random_access_ed(__begin_pair, __end_pair, __bin_op, __functionality,__gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);return __functionality._M_finish_iterator;}elsereturn adjacent_difference(__begin, __end, __result, __bin_op,__gnu_parallel::sequential_tag());}// Public interface.template<typename _IIter, typename _OutputIterator>inline _OutputIteratoradjacent_difference(_IIter __begin, _IIter __end,_OutputIterator __result,__gnu_parallel::_Parallelism __parallelism_tag){typedef iterator_traits<_IIter> _TraitsType;typedef typename _TraitsType::value_type _ValueType;return adjacent_difference(__begin, __end, __result,std::minus<_ValueType>(),__parallelism_tag);}template<typename _IIter, typename _OutputIterator>inline _OutputIteratoradjacent_difference(_IIter __begin, _IIter __end,_OutputIterator __result){typedef iterator_traits<_IIter> _TraitsType;typedef typename _TraitsType::value_type _ValueType;return adjacent_difference(__begin, __end, __result,std::minus<_ValueType>());}template<typename _IIter, typename _OutputIterator,typename _BinaryOperation>inline _OutputIteratoradjacent_difference(_IIter __begin, _IIter __end,_OutputIterator __result, _BinaryOperation __binary_op,__gnu_parallel::_Parallelism __parallelism_tag){typedef iterator_traits<_IIter> _ITraitsType;typedef typename _ITraitsType::iterator_category _IIteratorCategory;typedef iterator_traits<_OutputIterator> _OTraitsType;typedef typename _OTraitsType::iterator_category _OIterCategory;return __adjacent_difference_switch(__begin, __end, __result,__binary_op,_IIteratorCategory(),_OIterCategory(),__parallelism_tag);}template<typename _IIter, typename _OutputIterator,typename _BinaryOperation>inline _OutputIteratoradjacent_difference(_IIter __begin, _IIter __end,_OutputIterator __result, _BinaryOperation __binary_op){typedef iterator_traits<_IIter> _ITraitsType;typedef typename _ITraitsType::iterator_category _IIteratorCategory;typedef iterator_traits<_OutputIterator> _OTraitsType;typedef typename _OTraitsType::iterator_category _OIterCategory;return __adjacent_difference_switch(__begin, __end, __result,__binary_op,_IIteratorCategory(),_OIterCategory());}} // end namespace} // end namespace#endif /* _GLIBCXX_NUMERIC_H */