contrib/gcc-4.4/libstdc++-v3/include/parallel/numeric

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009 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 <functional>
  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
  49 namespace std
  50 {
  51 namespace __parallel
  52 {
  53   // Sequential fallback.
  54   template<typename InputIterator, typename T>
  55     inline T
  56     accumulate(InputIterator begin, InputIterator end, T init,
  57                __gnu_parallel::sequential_tag)
  58     { return _GLIBCXX_STD_P::accumulate(begin, end, init); }
  59
  60   template<typename InputIterator, typename T, typename BinaryOperation>
  61     inline T
  62     accumulate(InputIterator begin, InputIterator end, T init,
  63                BinaryOperation binary_op, __gnu_parallel::sequential_tag)
  64     { return _GLIBCXX_STD_P::accumulate(begin, end, init, binary_op); }
  65
  66   // Sequential fallback for input iterator case.
  67   template<typename InputIterator, typename T, typename IteratorTag>
  68     inline T
  69     accumulate_switch(InputIterator begin, InputIterator end,
  70                       T init, IteratorTag)
  71     { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); }
  72
  73   template<typename InputIterator, typename T, typename BinaryOperation,
  74            typename IteratorTag>
  75     inline T
  76     accumulate_switch(InputIterator begin, InputIterator end, T init,
  77                       BinaryOperation binary_op, IteratorTag)
  78     { return accumulate(begin, end, init, binary_op,
  79                         __gnu_parallel::sequential_tag()); }
  80
  81   // Parallel algorithm for random access iterators.
  82   template<typename _RandomAccessIterator, typename T,
  83            typename BinaryOperation>
  84     T
  85     accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end,
  86                       T 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::sequence_index_t>(end - begin)
  93             >= __gnu_parallel::_Settings::get().accumulate_minimal_n
  94             && __gnu_parallel::is_parallel(parallelism_tag)))
  95         {
  96           T res = init;
  97           __gnu_parallel::accumulate_selector<_RandomAccessIterator>
  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 InputIterator, typename T>
 116     inline T
 117     accumulate(InputIterator begin, InputIterator end, T init,
 118                __gnu_parallel::_Parallelism parallelism_tag)
 119     {
 120       typedef std::iterator_traits<InputIterator> iterator_traits;
 121       typedef typename iterator_traits::value_type value_type;
 122       typedef typename iterator_traits::iterator_category iterator_category;
 123
 124       return accumulate_switch(begin, end, init,
 125                                __gnu_parallel::plus<T, value_type>(),
 126                                iterator_category(), parallelism_tag);
 127     }
 128
 129   template<typename InputIterator, typename T>
 130     inline T
 131     accumulate(InputIterator begin, InputIterator end, T init)
 132     {
 133       typedef std::iterator_traits<InputIterator> iterator_traits;
 134       typedef typename iterator_traits::value_type value_type;
 135       typedef typename iterator_traits::iterator_category iterator_category;
 136
 137       return accumulate_switch(begin, end, init,
 138                                __gnu_parallel::plus<T, value_type>(),
 139                                iterator_category());
 140     }
 141
 142   template<typename InputIterator, typename T, typename BinaryOperation>
 143     inline T
 144     accumulate(InputIterator begin, InputIterator end, T init,
 145                BinaryOperation binary_op,
 146                __gnu_parallel::_Parallelism parallelism_tag)
 147     {
 148       typedef iterator_traits<InputIterator> iterator_traits;
 149       typedef typename iterator_traits::iterator_category iterator_category;
 150       return accumulate_switch(begin, end, init, binary_op,
 151                                iterator_category(), parallelism_tag);
 152     }
 153
 154   template<typename InputIterator, typename T, typename BinaryOperation>
 155     inline T
 156     accumulate(InputIterator begin, InputIterator end, T init,
 157                BinaryOperation binary_op)
 158     {
 159       typedef iterator_traits<InputIterator> iterator_traits;
 160       typedef typename iterator_traits::iterator_category iterator_category;
 161       return accumulate_switch(begin, end, init, binary_op,
 162                                iterator_category());
 163     }
 164
 165
 166   // Sequential fallback.
 167   template<typename InputIterator1, typename InputIterator2, typename T>
 168     inline T
 169     inner_product(InputIterator1 first1, InputIterator1 last1,
 170                   InputIterator2 first2, T init,
 171                   __gnu_parallel::sequential_tag)
 172     { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); }
 173
 174   template<typename InputIterator1, typename InputIterator2, typename T,
 175            typename BinaryFunction1, typename BinaryFunction2>
 176     inline T
 177     inner_product(InputIterator1 first1, InputIterator1 last1,
 178                   InputIterator2 first2, T init, BinaryFunction1 binary_op1,
 179                   BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag)
 180     { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
 181                                            binary_op1, binary_op2); }
 182
 183   // Parallel algorithm for random access iterators.
 184   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 185            typename T, typename BinaryFunction1, typename BinaryFunction2>
 186     T
 187     inner_product_switch(RandomAccessIterator1 first1,
 188                          RandomAccessIterator1 last1,
 189                          RandomAccessIterator2 first2, T init,
 190                          BinaryFunction1 binary_op1,
 191                          BinaryFunction2 binary_op2,
 192                          random_access_iterator_tag,
 193                          random_access_iterator_tag,
 194                          __gnu_parallel::_Parallelism parallelism_tag
 195                          = __gnu_parallel::parallel_unbalanced)
 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           T res = init;
 204           __gnu_parallel::
 205             inner_product_selector<RandomAccessIterator1,
 206             RandomAccessIterator2, T> my_selector(first1, first2);
 207           __gnu_parallel::
 208             for_each_template_random_access_ed(first1, last1, binary_op2,
 209                                             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 InputIterator1, typename InputIterator2, typename T,
 220            typename BinaryFunction1, typename BinaryFunction2,
 221            typename IteratorTag1, typename IteratorTag2>
 222     inline T
 223     inner_product_switch(InputIterator1 first1, InputIterator1 last1,
 224                          InputIterator2 first2, T init,
 225                          BinaryFunction1 binary_op1,
 226                          BinaryFunction2 binary_op2,
 227                          IteratorTag1, IteratorTag2)
 228     { return inner_product(first1, last1, first2, init,
 229                            binary_op1, binary_op2,
 230                            __gnu_parallel::sequential_tag()); }
 231
 232   template<typename InputIterator1, typename InputIterator2, typename T,
 233            typename BinaryFunction1, typename BinaryFunction2>
 234     inline T
 235     inner_product(InputIterator1 first1, InputIterator1 last1,
 236                   InputIterator2 first2, T init, BinaryFunction1 binary_op1,
 237                   BinaryFunction2 binary_op2,
 238                   __gnu_parallel::_Parallelism parallelism_tag)
 239     {
 240       typedef iterator_traits<InputIterator1> traits1_type;
 241       typedef typename traits1_type::iterator_category iterator1_category;
 242
 243       typedef iterator_traits<InputIterator2> traits2_type;
 244       typedef typename traits2_type::iterator_category iterator2_category;
 245
 246       return inner_product_switch(first1, last1, first2, init, binary_op1,
 247                                   binary_op2, iterator1_category(),
 248                                   iterator2_category(), parallelism_tag);
 249     }
 250
 251   template<typename InputIterator1, typename InputIterator2, typename T,
 252            typename BinaryFunction1, typename BinaryFunction2>
 253     inline T
 254     inner_product(InputIterator1 first1, InputIterator1 last1,
 255                   InputIterator2 first2, T init, BinaryFunction1 binary_op1,
 256                   BinaryFunction2 binary_op2)
 257     {
 258       typedef iterator_traits<InputIterator1> traits1_type;
 259       typedef typename traits1_type::iterator_category iterator1_category;
 260
 261       typedef iterator_traits<InputIterator2> traits2_type;
 262       typedef typename traits2_type::iterator_category iterator2_category;
 263
 264       return inner_product_switch(first1, last1, first2, init, binary_op1,
 265                                   binary_op2, iterator1_category(),
 266                                   iterator2_category());
 267     }
 268
 269   template<typename InputIterator1, typename InputIterator2, typename T>
 270     inline T
 271     inner_product(InputIterator1 first1, InputIterator1 last1,
 272                   InputIterator2 first2, T init,
 273                   __gnu_parallel::_Parallelism parallelism_tag)
 274     {
 275       typedef iterator_traits<InputIterator1> traits_type1;
 276       typedef typename traits_type1::value_type value_type1;
 277       typedef iterator_traits<InputIterator2> traits_type2;
 278       typedef typename traits_type2::value_type value_type2;
 279
 280       typedef typename
 281         __gnu_parallel::multiplies<value_type1, value_type2>::result
 282         multiplies_result_type;
 283       return inner_product(first1, last1, first2, init,
 284                            __gnu_parallel::plus<T, multiplies_result_type>(),
 285                            __gnu_parallel::
 286                            multiplies<value_type1, value_type2>(),
 287                            parallelism_tag);
 288     }
 289
 290   template<typename InputIterator1, typename InputIterator2, typename T>
 291     inline T
 292     inner_product(InputIterator1 first1, InputIterator1 last1,
 293                   InputIterator2 first2, T init)
 294     {
 295       typedef iterator_traits<InputIterator1> traits_type1;
 296       typedef typename traits_type1::value_type value_type1;
 297       typedef iterator_traits<InputIterator2> traits_type2;
 298       typedef typename traits_type2::value_type value_type2;
 299
 300       typedef typename
 301         __gnu_parallel::multiplies<value_type1, value_type2>::result
 302         multiplies_result_type;
 303       return inner_product(first1, last1, first2, init,
 304                            __gnu_parallel::plus<T, multiplies_result_type>(),
 305                            __gnu_parallel::
 306                            multiplies<value_type1, value_type2>());
 307     }
 308
 309   // Sequential fallback.
 310   template<typename InputIterator, typename OutputIterator>
 311     inline OutputIterator
 312     partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
 313                 __gnu_parallel::sequential_tag)
 314     { return _GLIBCXX_STD_P::partial_sum(begin, end, result); }
 315
 316   // Sequential fallback.
 317   template<typename InputIterator, typename OutputIterator,
 318            typename BinaryOperation>
 319     inline OutputIterator
 320     partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
 321                 BinaryOperation bin_op, __gnu_parallel::sequential_tag)
 322     { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
 323
 324   // Sequential fallback for input iterator case.
 325   template<typename InputIterator, typename OutputIterator,
 326            typename BinaryOperation, typename IteratorTag1,
 327            typename IteratorTag2>
 328     inline OutputIterator
 329     partial_sum_switch(InputIterator begin, InputIterator end,
 330                        OutputIterator result, BinaryOperation bin_op,
 331                        IteratorTag1, IteratorTag2)
 332     { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
 333
 334   // Parallel algorithm for random access iterators.
 335   template<typename InputIterator, typename OutputIterator,
 336            typename BinaryOperation>
 337     OutputIterator
 338     partial_sum_switch(InputIterator begin, InputIterator end,
 339                        OutputIterator result, BinaryOperation bin_op,
 340                        random_access_iterator_tag, random_access_iterator_tag)
 341     {
 342       if (_GLIBCXX_PARALLEL_CONDITION(
 343             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
 344             >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
 345         return __gnu_parallel::parallel_partial_sum(begin, end,
 346                                                     result, bin_op);
 347       else
 348         return partial_sum(begin, end, result, bin_op,
 349                            __gnu_parallel::sequential_tag());
 350     }
 351
 352   // Public interface.
 353   template<typename InputIterator, typename OutputIterator>
 354     inline OutputIterator
 355     partial_sum(InputIterator begin, InputIterator end, OutputIterator result)
 356     {
 357       typedef typename iterator_traits<InputIterator>::value_type value_type;
 358       return partial_sum(begin, end, result, std::plus<value_type>());
 359     }
 360
 361   // Public interface
 362   template<typename InputIterator, typename OutputIterator,
 363            typename BinaryOperation>
 364     inline OutputIterator
 365     partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
 366                 BinaryOperation binary_op)
 367     {
 368       typedef iterator_traits<InputIterator> traitsi_type;
 369       typedef typename traitsi_type::iterator_category iteratori_category;
 370
 371       typedef iterator_traits<OutputIterator> traitso_type;
 372       typedef typename traitso_type::iterator_category iteratoro_category;
 373
 374       return partial_sum_switch(begin, end, result, binary_op,
 375                                 iteratori_category(), iteratoro_category());
 376     }
 377
 378   // Sequential fallback.
 379   template<typename InputIterator, typename OutputIterator>
 380     inline OutputIterator
 381     adjacent_difference(InputIterator begin, InputIterator end,
 382                         OutputIterator result, __gnu_parallel::sequential_tag)
 383     { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); }
 384
 385   // Sequential fallback.
 386   template<typename InputIterator, typename OutputIterator,
 387            typename BinaryOperation>
 388     inline OutputIterator
 389     adjacent_difference(InputIterator begin, InputIterator end,
 390                         OutputIterator result, BinaryOperation bin_op,
 391                         __gnu_parallel::sequential_tag)
 392     { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op); }
 393
 394   // Sequential fallback for input iterator case.
 395   template<typename InputIterator, typename OutputIterator,
 396            typename BinaryOperation, typename IteratorTag1,
 397            typename IteratorTag2>
 398     inline OutputIterator
 399     adjacent_difference_switch(InputIterator begin, InputIterator end,
 400                                OutputIterator result, BinaryOperation bin_op,
 401                              IteratorTag1, IteratorTag2)
 402     { return adjacent_difference(begin, end, result, bin_op,
 403                                  __gnu_parallel::sequential_tag()); }
 404
 405   // Parallel algorithm for random access iterators.
 406   template<typename InputIterator, typename OutputIterator,
 407            typename BinaryOperation>
 408     OutputIterator
 409     adjacent_difference_switch(InputIterator begin, InputIterator end,
 410                                OutputIterator result, BinaryOperation bin_op,
 411                                random_access_iterator_tag,
 412                                random_access_iterator_tag,
 413                                __gnu_parallel::_Parallelism parallelism_tag
 414                                = __gnu_parallel::parallel_balanced)
 415     {
 416       if (_GLIBCXX_PARALLEL_CONDITION(
 417             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
 418             >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
 419             && __gnu_parallel::is_parallel(parallelism_tag)))
 420         {
 421           bool dummy = true;
 422           typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator,
 423             random_access_iterator_tag> ip;
 424           *result = *begin;
 425           ip begin_pair(begin + 1, result + 1),
 426             end_pair(end, result + (end - begin));
 427           __gnu_parallel::adjacent_difference_selector<ip> functionality;
 428           __gnu_parallel::
 429             for_each_template_random_access_ed(begin_pair, end_pair, bin_op,
 430                                             functionality,
 431                                             __gnu_parallel::dummy_reduct(),
 432                                             dummy, dummy, -1);
 433           return functionality.finish_iterator;
 434         }
 435       else
 436         return adjacent_difference(begin, end, result, bin_op,
 437                                    __gnu_parallel::sequential_tag());
 438     }
 439
 440   // Public interface.
 441   template<typename InputIterator, typename OutputIterator>
 442     inline OutputIterator
 443     adjacent_difference(InputIterator begin, InputIterator end,
 444                         OutputIterator result,
 445                         __gnu_parallel::_Parallelism parallelism_tag)
 446     {
 447       typedef iterator_traits<InputIterator> traits_type;
 448       typedef typename traits_type::value_type value_type;
 449       return adjacent_difference(begin, end, result, std::minus<value_type>(),
 450                                  parallelism_tag);
 451     }
 452
 453   template<typename InputIterator, typename OutputIterator>
 454     inline OutputIterator
 455     adjacent_difference(InputIterator begin, InputIterator end,
 456                         OutputIterator result)
 457     {
 458       typedef iterator_traits<InputIterator> traits_type;
 459       typedef typename traits_type::value_type value_type;
 460       return adjacent_difference(begin, end, result, std::minus<value_type>());
 461     }
 462
 463   template<typename InputIterator, typename OutputIterator,
 464            typename BinaryOperation>
 465     inline OutputIterator
 466     adjacent_difference(InputIterator begin, InputIterator end,
 467                         OutputIterator result, BinaryOperation binary_op,
 468                         __gnu_parallel::_Parallelism parallelism_tag)
 469     {
 470       typedef iterator_traits<InputIterator> traitsi_type;
 471       typedef typename traitsi_type::iterator_category iteratori_category;
 472
 473       typedef iterator_traits<OutputIterator> traitso_type;
 474       typedef typename traitso_type::iterator_category iteratoro_category;
 475
 476       return adjacent_difference_switch(begin, end, result, binary_op,
 477                                         iteratori_category(),
 478                                         iteratoro_category(), parallelism_tag);
 479     }
 480
 481   template<typename InputIterator, typename OutputIterator,
 482            typename BinaryOperation>
 483     inline OutputIterator
 484     adjacent_difference(InputIterator begin, InputIterator end,
 485                         OutputIterator result, BinaryOperation binary_op)
 486     {
 487       typedef iterator_traits<InputIterator> traitsi_type;
 488       typedef typename traitsi_type::iterator_category iteratori_category;
 489
 490       typedef iterator_traits<OutputIterator> traitso_type;
 491       typedef typename traitso_type::iterator_category iteratoro_category;
 492
 493       return adjacent_difference_switch(begin, end, result, binary_op,
 494                                         iteratori_category(),
 495                                         iteratoro_category());
 496     }
 497 } // end namespace
 498 } // end namespace
 499
 500 #endif /* _GLIBCXX_NUMERIC_H */