mingw/lib/gcc/mingw32/4.3.3/include/c++/parallel/numeric

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /**
  32  * @file parallel/numeric
  33 *
  34  * @brief Parallel STL function calls corresponding to stl_numeric.h.
  35  * The functions defined here mainly do case switches and
  36  * call the actual parallelized versions in other files.
  37  * Inlining policy: Functions that basically only contain one function call,
  38  * are declared inline.
  39  *  This file is a GNU parallel extension to the Standard C++ Library.
  40  */
  41
  42 // Written by Johannes Singler and Felix Putze.
  43
  44 #ifndef _GLIBCXX_PARALLEL_NUMERIC_H
  45 #define _GLIBCXX_PARALLEL_NUMERIC_H 1
  46
  47 #include <numeric>
  48 #include <functional>
  49 #include <parallel/numericfwd.h>
  50 #include <parallel/iterator.h>
  51 #include <parallel/for_each.h>
  52 #include <parallel/for_each_selectors.h>
  53 #include <parallel/partial_sum.h>
  54
  55 namespace std
  56 {
  57 namespace __parallel
  58 {
  59   // Sequential fallback.
  60   template<typename InputIterator, typename T>
  61     inline T
  62     accumulate(InputIterator begin, InputIterator end, T init,
  63                __gnu_parallel::sequential_tag)
  64     { return _GLIBCXX_STD_P::accumulate(begin, end, init); }
  65
  66   template<typename InputIterator, typename T, typename BinaryOperation>
  67     inline T
  68     accumulate(InputIterator begin, InputIterator end, T init,
  69                BinaryOperation binary_op, __gnu_parallel::sequential_tag)
  70     { return _GLIBCXX_STD_P::accumulate(begin, end, init, binary_op); }
  71
  72   // Sequential fallback for input iterator case.
  73   template<typename InputIterator, typename T, typename IteratorTag>
  74     inline T
  75     accumulate_switch(InputIterator begin, InputIterator end,
  76                       T init, IteratorTag)
  77     { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); }
  78
  79   template<typename InputIterator, typename T, typename BinaryOperation,
  80            typename IteratorTag>
  81     inline T
  82     accumulate_switch(InputIterator begin, InputIterator end, T init,
  83                       BinaryOperation binary_op, IteratorTag)
  84     { return accumulate(begin, end, init, binary_op,
  85                         __gnu_parallel::sequential_tag()); }
  86
  87   // Parallel algorithm for random access iterators.
  88   template<typename _RandomAccessIterator, typename T,
  89            typename BinaryOperation>
  90     T
  91     accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end,
  92                       T init, BinaryOperation binary_op,
  93                       random_access_iterator_tag,
  94                       __gnu_parallel::_Parallelism parallelism_tag
  95                       = __gnu_parallel::parallel_unbalanced)
  96     {
  97       if (_GLIBCXX_PARALLEL_CONDITION(
  98             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
  99             >= __gnu_parallel::_Settings::get().accumulate_minimal_n
 100             && __gnu_parallel::is_parallel(parallelism_tag)))
 101         {
 102           T res = init;
 103           __gnu_parallel::accumulate_selector<_RandomAccessIterator>
 104             my_selector;
 105           __gnu_parallel::
 106             for_each_template_random_access(begin, end,
 107                                             __gnu_parallel::nothing(),
 108                                             my_selector,
 109                                             __gnu_parallel::
 110                                             accumulate_binop_reduct
 111                                             <BinaryOperation>(binary_op),
 112                                             res, res, -1, parallelism_tag);
 113           return res;
 114         }
 115       else
 116         return accumulate(begin, end, init, binary_op,
 117                           __gnu_parallel::sequential_tag());
 118     }
 119
 120   // Public interface.
 121   template<typename InputIterator, typename T>
 122     inline T
 123     accumulate(InputIterator begin, InputIterator end, T init,
 124                __gnu_parallel::_Parallelism parallelism_tag)
 125     {
 126       typedef std::iterator_traits<InputIterator> iterator_traits;
 127       typedef typename iterator_traits::value_type value_type;
 128       typedef typename iterator_traits::iterator_category iterator_category;
 129
 130       return accumulate_switch(begin, end, init,
 131                                __gnu_parallel::plus<T, value_type>(),
 132                                iterator_category(), parallelism_tag);
 133     }
 134
 135   template<typename InputIterator, typename T>
 136     inline T
 137     accumulate(InputIterator begin, InputIterator end, T init)
 138     {
 139       typedef std::iterator_traits<InputIterator> iterator_traits;
 140       typedef typename iterator_traits::value_type value_type;
 141       typedef typename iterator_traits::iterator_category iterator_category;
 142
 143       return accumulate_switch(begin, end, init,
 144                                __gnu_parallel::plus<T, value_type>(),
 145                                iterator_category());
 146     }
 147
 148   template<typename InputIterator, typename T, typename BinaryOperation>
 149     inline T
 150     accumulate(InputIterator begin, InputIterator end, T init,
 151                BinaryOperation binary_op,
 152                __gnu_parallel::_Parallelism parallelism_tag)
 153     {
 154       typedef iterator_traits<InputIterator> iterator_traits;
 155       typedef typename iterator_traits::iterator_category iterator_category;
 156       return accumulate_switch(begin, end, init, binary_op,
 157                                iterator_category(), parallelism_tag);
 158     }
 159
 160   template<typename InputIterator, typename T, typename BinaryOperation>
 161     inline T
 162     accumulate(InputIterator begin, InputIterator end, T init,
 163                BinaryOperation binary_op)
 164     {
 165       typedef iterator_traits<InputIterator> iterator_traits;
 166       typedef typename iterator_traits::iterator_category iterator_category;
 167       return accumulate_switch(begin, end, init, binary_op,
 168                                iterator_category());
 169     }
 170
 171
 172   // Sequential fallback.
 173   template<typename InputIterator1, typename InputIterator2, typename T>
 174     inline T
 175     inner_product(InputIterator1 first1, InputIterator1 last1,
 176                   InputIterator2 first2, T init,
 177                   __gnu_parallel::sequential_tag)
 178     { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); }
 179
 180   template<typename InputIterator1, typename InputIterator2, typename T,
 181            typename BinaryFunction1, typename BinaryFunction2>
 182     inline T
 183     inner_product(InputIterator1 first1, InputIterator1 last1,
 184                   InputIterator2 first2, T init, BinaryFunction1 binary_op1,
 185                   BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag)
 186     { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
 187                                            binary_op1, binary_op2); }
 188
 189   // Parallel algorithm for random access iterators.
 190   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 191            typename T, typename BinaryFunction1, typename BinaryFunction2>
 192     T
 193     inner_product_switch(RandomAccessIterator1 first1,
 194                          RandomAccessIterator1 last1,
 195                          RandomAccessIterator2 first2, T init,
 196                          BinaryFunction1 binary_op1,
 197                          BinaryFunction2 binary_op2,
 198                          random_access_iterator_tag,
 199                          random_access_iterator_tag,
 200                          __gnu_parallel::_Parallelism parallelism_tag
 201                          = __gnu_parallel::parallel_unbalanced)
 202     {
 203       if (_GLIBCXX_PARALLEL_CONDITION((last1 - first1)
 204                                       >= __gnu_parallel::_Settings::get().
 205                                       accumulate_minimal_n
 206                                       && __gnu_parallel::
 207                                       is_parallel(parallelism_tag)))
 208         {
 209           T res = init;
 210           __gnu_parallel::
 211             inner_product_selector<RandomAccessIterator1,
 212             RandomAccessIterator2, T> my_selector(first1, first2);
 213           __gnu_parallel::
 214             for_each_template_random_access(first1, last1, binary_op2,
 215                                             my_selector, binary_op1,
 216                                             res, res, -1, parallelism_tag);
 217           return res;
 218         }
 219       else
 220         return inner_product(first1, last1, first2, init,
 221                              __gnu_parallel::sequential_tag());
 222     }
 223
 224   // No parallelism for input iterators.
 225   template<typename InputIterator1, typename InputIterator2, typename T,
 226            typename BinaryFunction1, typename BinaryFunction2,
 227            typename IteratorTag1, typename IteratorTag2>
 228     inline T
 229     inner_product_switch(InputIterator1 first1, InputIterator1 last1,
 230                          InputIterator2 first2, T init,
 231                          BinaryFunction1 binary_op1,
 232                          BinaryFunction2 binary_op2,
 233                          IteratorTag1, IteratorTag2)
 234     { return inner_product(first1, last1, first2, init,
 235                            binary_op1, binary_op2,
 236                            __gnu_parallel::sequential_tag()); }
 237
 238   template<typename InputIterator1, typename InputIterator2, typename T,
 239            typename BinaryFunction1, typename BinaryFunction2>
 240     inline T
 241     inner_product(InputIterator1 first1, InputIterator1 last1,
 242                   InputIterator2 first2, T init, BinaryFunction1 binary_op1,
 243                   BinaryFunction2 binary_op2,
 244                   __gnu_parallel::_Parallelism parallelism_tag)
 245     {
 246       typedef iterator_traits<InputIterator1> traits1_type;
 247       typedef typename traits1_type::iterator_category iterator1_category;
 248
 249       typedef iterator_traits<InputIterator2> traits2_type;
 250       typedef typename traits2_type::iterator_category iterator2_category;
 251
 252       return inner_product_switch(first1, last1, first2, init, binary_op1,
 253                                   binary_op2, iterator1_category(),
 254                                   iterator2_category(), parallelism_tag);
 255     }
 256
 257   template<typename InputIterator1, typename InputIterator2, typename T,
 258            typename BinaryFunction1, typename BinaryFunction2>
 259     inline T
 260     inner_product(InputIterator1 first1, InputIterator1 last1,
 261                   InputIterator2 first2, T init, BinaryFunction1 binary_op1,
 262                   BinaryFunction2 binary_op2)
 263     {
 264       typedef iterator_traits<InputIterator1> traits1_type;
 265       typedef typename traits1_type::iterator_category iterator1_category;
 266
 267       typedef iterator_traits<InputIterator2> traits2_type;
 268       typedef typename traits2_type::iterator_category iterator2_category;
 269
 270       return inner_product_switch(first1, last1, first2, init, binary_op1,
 271                                   binary_op2, iterator1_category(),
 272                                   iterator2_category());
 273     }
 274
 275   template<typename InputIterator1, typename InputIterator2, typename T>
 276     inline T
 277     inner_product(InputIterator1 first1, InputIterator1 last1,
 278                   InputIterator2 first2, T init,
 279                   __gnu_parallel::_Parallelism parallelism_tag)
 280     {
 281       typedef iterator_traits<InputIterator1> traits_type1;
 282       typedef typename traits_type1::value_type value_type1;
 283       typedef iterator_traits<InputIterator2> traits_type2;
 284       typedef typename traits_type2::value_type value_type2;
 285
 286       typedef typename
 287         __gnu_parallel::multiplies<value_type1, value_type2>::result
 288         multiplies_result_type;
 289       return inner_product(first1, last1, first2, init,
 290                            __gnu_parallel::plus<T, multiplies_result_type>(),
 291                            __gnu_parallel::
 292                            multiplies<value_type1, value_type2>(),
 293                            parallelism_tag);
 294     }
 295
 296   template<typename InputIterator1, typename InputIterator2, typename T>
 297     inline T
 298     inner_product(InputIterator1 first1, InputIterator1 last1,
 299                   InputIterator2 first2, T init)
 300     {
 301       typedef iterator_traits<InputIterator1> traits_type1;
 302       typedef typename traits_type1::value_type value_type1;
 303       typedef iterator_traits<InputIterator2> traits_type2;
 304       typedef typename traits_type2::value_type value_type2;
 305
 306       typedef typename
 307         __gnu_parallel::multiplies<value_type1, value_type2>::result
 308         multiplies_result_type;
 309       return inner_product(first1, last1, first2, init,
 310                            __gnu_parallel::plus<T, multiplies_result_type>(),
 311                            __gnu_parallel::
 312                            multiplies<value_type1, value_type2>());
 313     }
 314
 315   // Sequential fallback.
 316   template<typename InputIterator, typename OutputIterator>
 317     inline OutputIterator
 318     partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
 319                 __gnu_parallel::sequential_tag)
 320     { return _GLIBCXX_STD_P::partial_sum(begin, end, result); }
 321
 322   // Sequential fallback.
 323   template<typename InputIterator, typename OutputIterator,
 324            typename BinaryOperation>
 325     inline OutputIterator
 326     partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
 327                 BinaryOperation bin_op, __gnu_parallel::sequential_tag)
 328     { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
 329
 330   // Sequential fallback for input iterator case.
 331   template<typename InputIterator, typename OutputIterator,
 332            typename BinaryOperation, typename IteratorTag1,
 333            typename IteratorTag2>
 334     inline OutputIterator
 335     partial_sum_switch(InputIterator begin, InputIterator end,
 336                        OutputIterator result, BinaryOperation bin_op,
 337                        IteratorTag1, IteratorTag2)
 338     { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
 339
 340   // Parallel algorithm for random access iterators.
 341   template<typename InputIterator, typename OutputIterator,
 342            typename BinaryOperation>
 343     OutputIterator
 344     partial_sum_switch(InputIterator begin, InputIterator end,
 345                        OutputIterator result, BinaryOperation bin_op,
 346                        random_access_iterator_tag, random_access_iterator_tag)
 347     {
 348       if (_GLIBCXX_PARALLEL_CONDITION(
 349             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
 350             >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
 351         return __gnu_parallel::parallel_partial_sum(begin, end,
 352                                                     result, bin_op);
 353       else
 354         return partial_sum(begin, end, result, bin_op,
 355                            __gnu_parallel::sequential_tag());
 356     }
 357
 358   // Public interface.
 359   template<typename InputIterator, typename OutputIterator>
 360     inline OutputIterator
 361     partial_sum(InputIterator begin, InputIterator end, OutputIterator result)
 362     {
 363       typedef typename iterator_traits<InputIterator>::value_type value_type;
 364       return partial_sum(begin, end, result, std::plus<value_type>());
 365     }
 366
 367   // Public interface
 368   template<typename InputIterator, typename OutputIterator,
 369            typename BinaryOperation>
 370     inline OutputIterator
 371     partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
 372                 BinaryOperation binary_op)
 373     {
 374       typedef iterator_traits<InputIterator> traitsi_type;
 375       typedef typename traitsi_type::iterator_category iteratori_category;
 376
 377       typedef iterator_traits<OutputIterator> traitso_type;
 378       typedef typename traitso_type::iterator_category iteratoro_category;
 379
 380       return partial_sum_switch(begin, end, result, binary_op,
 381                                 iteratori_category(), iteratoro_category());
 382     }
 383
 384   // Sequential fallback.
 385   template<typename InputIterator, typename OutputIterator>
 386     inline OutputIterator
 387     adjacent_difference(InputIterator begin, InputIterator end,
 388                         OutputIterator result, __gnu_parallel::sequential_tag)
 389     { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); }
 390
 391   // Sequential fallback.
 392   template<typename InputIterator, typename OutputIterator,
 393            typename BinaryOperation>
 394     inline OutputIterator
 395     adjacent_difference(InputIterator begin, InputIterator end,
 396                         OutputIterator result, BinaryOperation bin_op,
 397                         __gnu_parallel::sequential_tag)
 398     { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op); }
 399
 400   // Sequential fallback for input iterator case.
 401   template<typename InputIterator, typename OutputIterator,
 402            typename BinaryOperation, typename IteratorTag1,
 403            typename IteratorTag2>
 404     inline OutputIterator
 405     adjacent_difference_switch(InputIterator begin, InputIterator end,
 406                                OutputIterator result, BinaryOperation bin_op,
 407                              IteratorTag1, IteratorTag2)
 408     { return adjacent_difference(begin, end, result, bin_op,
 409                                  __gnu_parallel::sequential_tag()); }
 410
 411   // Parallel algorithm for random access iterators.
 412   template<typename InputIterator, typename OutputIterator,
 413            typename BinaryOperation>
 414     OutputIterator
 415     adjacent_difference_switch(InputIterator begin, InputIterator end,
 416                                OutputIterator result, BinaryOperation bin_op,
 417                                random_access_iterator_tag,
 418                                random_access_iterator_tag,
 419                                __gnu_parallel::_Parallelism parallelism_tag
 420                                = __gnu_parallel::parallel_balanced)
 421     {
 422       if (_GLIBCXX_PARALLEL_CONDITION(
 423             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
 424             >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
 425             && __gnu_parallel::is_parallel(parallelism_tag)))
 426         {
 427           bool dummy = true;
 428           typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator,
 429             random_access_iterator_tag> ip;
 430           *result = *begin;
 431           ip begin_pair(begin + 1, result + 1),
 432             end_pair(end, result + (end - begin));
 433           __gnu_parallel::adjacent_difference_selector<ip> functionality;
 434           __gnu_parallel::
 435             for_each_template_random_access(begin_pair, end_pair, bin_op,
 436                                             functionality,
 437                                             __gnu_parallel::dummy_reduct(),
 438                                             dummy, dummy, -1, parallelism_tag);
 439           return functionality.finish_iterator;
 440         }
 441       else
 442         return adjacent_difference(begin, end, result, bin_op,
 443                                    __gnu_parallel::sequential_tag());
 444     }
 445
 446   // Public interface.
 447   template<typename InputIterator, typename OutputIterator>
 448     inline OutputIterator
 449     adjacent_difference(InputIterator begin, InputIterator end,
 450                         OutputIterator result,
 451                         __gnu_parallel::_Parallelism parallelism_tag)
 452     {
 453       typedef iterator_traits<InputIterator> traits_type;
 454       typedef typename traits_type::value_type value_type;
 455       return adjacent_difference(begin, end, result, std::minus<value_type>(),
 456                                  parallelism_tag);
 457     }
 458
 459   template<typename InputIterator, typename OutputIterator>
 460     inline OutputIterator
 461     adjacent_difference(InputIterator begin, InputIterator end,
 462                         OutputIterator result)
 463     {
 464       typedef iterator_traits<InputIterator> traits_type;
 465       typedef typename traits_type::value_type value_type;
 466       return adjacent_difference(begin, end, result, std::minus<value_type>());
 467     }
 468
 469   template<typename InputIterator, typename OutputIterator,
 470            typename BinaryOperation>
 471     inline OutputIterator
 472     adjacent_difference(InputIterator begin, InputIterator end,
 473                         OutputIterator result, BinaryOperation binary_op,
 474                         __gnu_parallel::_Parallelism parallelism_tag)
 475     {
 476       typedef iterator_traits<InputIterator> traitsi_type;
 477       typedef typename traitsi_type::iterator_category iteratori_category;
 478
 479       typedef iterator_traits<OutputIterator> traitso_type;
 480       typedef typename traitso_type::iterator_category iteratoro_category;
 481
 482       return adjacent_difference_switch(begin, end, result, binary_op,
 483                                         iteratori_category(),
 484                                         iteratoro_category(), parallelism_tag);
 485     }
 486
 487   template<typename InputIterator, typename OutputIterator,
 488            typename BinaryOperation>
 489     inline OutputIterator
 490     adjacent_difference(InputIterator begin, InputIterator end,
 491                         OutputIterator result, BinaryOperation binary_op)
 492     {
 493       typedef iterator_traits<InputIterator> traitsi_type;
 494       typedef typename traitsi_type::iterator_category iteratori_category;
 495
 496       typedef iterator_traits<OutputIterator> traitso_type;
 497       typedef typename traitso_type::iterator_category iteratoro_category;
 498
 499       return adjacent_difference_switch(begin, end, result, binary_op,
 500                                         iteratori_category(),
 501                                         iteratoro_category());
 502     }
 503 } // end namespace
 504 } // end namespace
 505
 506 #endif /* _GLIBCXX_NUMERIC_H */