parallel/numeric

Go to the documentation of this file.

// -*- C++ -*-

// Copyright (C) 2007, 2008, 2009, 2010 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 _GLIBCXX_VISIBILITY(default)
{
namespace __parallel
{
  // Sequential fallback.
  template<typename _IIter, typename _Tp>
    inline _Tp
    accumulate(_IIter __begin, _IIter __end, _Tp __init, 
               __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::accumulate(__begin, __end, __init); }

  template<typename _IIter, typename _Tp, typename _BinaryOperation>
    inline _Tp
    accumulate(_IIter __begin, _IIter __end, _Tp __init,
               _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::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;
        }
      else
        return accumulate(__begin, __end, __init, __binary_op, 
                          __gnu_parallel::sequential_tag());
    }

  // Public interface.
  template<typename _IIter, typename _Tp>
    inline _Tp
    accumulate(_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 _Tp
    accumulate(_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 _Tp
    accumulate(_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 _Tp
    accumulate(_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 _Tp
    inner_product(_IIter1 __first1, _IIter1 __last1, 
                  _IIter2 __first2, _Tp __init,
                  __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::inner_product(
                               __first1, __last1, __first2, __init); }

  template<typename _IIter1, typename _IIter2, typename _Tp,
           typename _BinaryFunction1, typename _BinaryFunction2>
    inline _Tp
    inner_product(_IIter1 __first1, _IIter1 __last1,
                  _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1, 
                  _BinaryFunction2 __binary_op2,
                  __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::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;
        }
      else
        return 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 _Tp
    inner_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 _Tp
    inner_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 _Tp
    inner_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 _Tp
    inner_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 _OutputIterator
    partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
                __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::partial_sum(__begin, __end, __result); }

  // Sequential fallback.
  template<typename _IIter, typename _OutputIterator,
       typename _BinaryOperation>
    inline _OutputIterator
    partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
                _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::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_A::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);
      else
        return partial_sum(__begin, __end, __result, __bin_op,
                           __gnu_parallel::sequential_tag());
    }

  // Public interface.
  template<typename _IIter, typename _OutputIterator>
    inline _OutputIterator
    partial_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 interface
  template<typename _IIter, typename _OutputIterator,
           typename _BinaryOperation>
    inline _OutputIterator
    partial_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 _OutputIterator
    adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
                        __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::adjacent_difference(__begin, __end, __result); }

  // Sequential fallback.
  template<typename _IIter, typename _OutputIterator,
           typename _BinaryOperation>
    inline _OutputIterator
    adjacent_difference(_IIter __begin, _IIter __end,
                        _OutputIterator __result, _BinaryOperation __bin_op,
                        __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_A::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;
        }
      else
        return adjacent_difference(__begin, __end, __result, __bin_op, 
                                   __gnu_parallel::sequential_tag());
    }

  // Public interface.
  template<typename _IIter, typename _OutputIterator>
    inline _OutputIterator
    adjacent_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 _OutputIterator
    adjacent_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 _OutputIterator
    adjacent_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 _OutputIterator
    adjacent_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 */