00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044 #ifndef _GLIBCXX_PARALLEL_NUMERIC_H
00045 #define _GLIBCXX_PARALLEL_NUMERIC_H 1
00046
00047 #include <numeric>
00048 #include <functional>
00049 #include <parallel/numericfwd.h>
00050 #include <parallel/iterator.h>
00051 #include <parallel/for_each.h>
00052 #include <parallel/for_each_selectors.h>
00053 #include <parallel/partial_sum.h>
00054
00055 namespace std
00056 {
00057 namespace __parallel
00058 {
00059
00060 template<typename InputIterator, typename T>
00061 inline T
00062 accumulate(InputIterator begin, InputIterator end, T init,
00063 __gnu_parallel::sequential_tag)
00064 { return _GLIBCXX_STD_P::accumulate(begin, end, init); }
00065
00066 template<typename InputIterator, typename T, typename BinaryOperation>
00067 inline T
00068 accumulate(InputIterator begin, InputIterator end, T init,
00069 BinaryOperation binary_op, __gnu_parallel::sequential_tag)
00070 { return _GLIBCXX_STD_P::accumulate(begin, end, init, binary_op); }
00071
00072
00073 template<typename InputIterator, typename T, typename IteratorTag>
00074 inline T
00075 accumulate_switch(InputIterator begin, InputIterator end,
00076 T init, IteratorTag)
00077 { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); }
00078
00079 template<typename InputIterator, typename T, typename BinaryOperation,
00080 typename IteratorTag>
00081 inline T
00082 accumulate_switch(InputIterator begin, InputIterator end, T init,
00083 BinaryOperation binary_op, IteratorTag)
00084 { return accumulate(begin, end, init, binary_op,
00085 __gnu_parallel::sequential_tag()); }
00086
00087
00088 template<typename _RandomAccessIterator, typename T,
00089 typename BinaryOperation>
00090 T
00091 accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end,
00092 T init, BinaryOperation binary_op,
00093 random_access_iterator_tag,
00094 __gnu_parallel::_Parallelism parallelism_tag
00095 = __gnu_parallel::parallel_unbalanced)
00096 {
00097 if (_GLIBCXX_PARALLEL_CONDITION(
00098 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
00099 >= __gnu_parallel::_Settings::get().accumulate_minimal_n
00100 && __gnu_parallel::is_parallel(parallelism_tag)))
00101 {
00102 T res = init;
00103 __gnu_parallel::accumulate_selector<_RandomAccessIterator>
00104 my_selector;
00105 __gnu_parallel::
00106 for_each_template_random_access(begin, end,
00107 __gnu_parallel::nothing(),
00108 my_selector,
00109 __gnu_parallel::
00110 accumulate_binop_reduct
00111 <BinaryOperation>(binary_op),
00112 res, res, -1, parallelism_tag);
00113 return res;
00114 }
00115 else
00116 return accumulate(begin, end, init, binary_op,
00117 __gnu_parallel::sequential_tag());
00118 }
00119
00120
00121 template<typename InputIterator, typename T>
00122 inline T
00123 accumulate(InputIterator begin, InputIterator end, T init,
00124 __gnu_parallel::_Parallelism parallelism_tag)
00125 {
00126 typedef std::iterator_traits<InputIterator> iterator_traits;
00127 typedef typename iterator_traits::value_type value_type;
00128 typedef typename iterator_traits::iterator_category iterator_category;
00129
00130 return accumulate_switch(begin, end, init,
00131 __gnu_parallel::plus<T, value_type>(),
00132 iterator_category(), parallelism_tag);
00133 }
00134
00135 template<typename InputIterator, typename T>
00136 inline T
00137 accumulate(InputIterator begin, InputIterator end, T init)
00138 {
00139 typedef std::iterator_traits<InputIterator> iterator_traits;
00140 typedef typename iterator_traits::value_type value_type;
00141 typedef typename iterator_traits::iterator_category iterator_category;
00142
00143 return accumulate_switch(begin, end, init,
00144 __gnu_parallel::plus<T, value_type>(),
00145 iterator_category());
00146 }
00147
00148 template<typename InputIterator, typename T, typename BinaryOperation>
00149 inline T
00150 accumulate(InputIterator begin, InputIterator end, T init,
00151 BinaryOperation binary_op,
00152 __gnu_parallel::_Parallelism parallelism_tag)
00153 {
00154 typedef iterator_traits<InputIterator> iterator_traits;
00155 typedef typename iterator_traits::iterator_category iterator_category;
00156 return accumulate_switch(begin, end, init, binary_op,
00157 iterator_category(), parallelism_tag);
00158 }
00159
00160 template<typename InputIterator, typename T, typename BinaryOperation>
00161 inline T
00162 accumulate(InputIterator begin, InputIterator end, T init,
00163 BinaryOperation binary_op)
00164 {
00165 typedef iterator_traits<InputIterator> iterator_traits;
00166 typedef typename iterator_traits::iterator_category iterator_category;
00167 return accumulate_switch(begin, end, init, binary_op,
00168 iterator_category());
00169 }
00170
00171
00172
00173 template<typename InputIterator1, typename InputIterator2, typename T>
00174 inline T
00175 inner_product(InputIterator1 first1, InputIterator1 last1,
00176 InputIterator2 first2, T init,
00177 __gnu_parallel::sequential_tag)
00178 { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); }
00179
00180 template<typename InputIterator1, typename InputIterator2, typename T,
00181 typename BinaryFunction1, typename BinaryFunction2>
00182 inline T
00183 inner_product(InputIterator1 first1, InputIterator1 last1,
00184 InputIterator2 first2, T init, BinaryFunction1 binary_op1,
00185 BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag)
00186 { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init,
00187 binary_op1, binary_op2); }
00188
00189
00190 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00191 typename T, typename BinaryFunction1, typename BinaryFunction2>
00192 T
00193 inner_product_switch(RandomAccessIterator1 first1,
00194 RandomAccessIterator1 last1,
00195 RandomAccessIterator2 first2, T init,
00196 BinaryFunction1 binary_op1,
00197 BinaryFunction2 binary_op2,
00198 random_access_iterator_tag,
00199 random_access_iterator_tag,
00200 __gnu_parallel::_Parallelism parallelism_tag
00201 = __gnu_parallel::parallel_unbalanced)
00202 {
00203 if (_GLIBCXX_PARALLEL_CONDITION((last1 - first1)
00204 >= __gnu_parallel::_Settings::get().
00205 accumulate_minimal_n
00206 && __gnu_parallel::
00207 is_parallel(parallelism_tag)))
00208 {
00209 T res = init;
00210 __gnu_parallel::
00211 inner_product_selector<RandomAccessIterator1,
00212 RandomAccessIterator2, T> my_selector(first1, first2);
00213 __gnu_parallel::
00214 for_each_template_random_access(first1, last1, binary_op2,
00215 my_selector, binary_op1,
00216 res, res, -1, parallelism_tag);
00217 return res;
00218 }
00219 else
00220 return inner_product(first1, last1, first2, init,
00221 __gnu_parallel::sequential_tag());
00222 }
00223
00224
00225 template<typename InputIterator1, typename InputIterator2, typename T,
00226 typename BinaryFunction1, typename BinaryFunction2,
00227 typename IteratorTag1, typename IteratorTag2>
00228 inline T
00229 inner_product_switch(InputIterator1 first1, InputIterator1 last1,
00230 InputIterator2 first2, T init,
00231 BinaryFunction1 binary_op1,
00232 BinaryFunction2 binary_op2,
00233 IteratorTag1, IteratorTag2)
00234 { return inner_product(first1, last1, first2, init,
00235 binary_op1, binary_op2,
00236 __gnu_parallel::sequential_tag()); }
00237
00238 template<typename InputIterator1, typename InputIterator2, typename T,
00239 typename BinaryFunction1, typename BinaryFunction2>
00240 inline T
00241 inner_product(InputIterator1 first1, InputIterator1 last1,
00242 InputIterator2 first2, T init, BinaryFunction1 binary_op1,
00243 BinaryFunction2 binary_op2,
00244 __gnu_parallel::_Parallelism parallelism_tag)
00245 {
00246 typedef iterator_traits<InputIterator1> traits1_type;
00247 typedef typename traits1_type::iterator_category iterator1_category;
00248
00249 typedef iterator_traits<InputIterator2> traits2_type;
00250 typedef typename traits2_type::iterator_category iterator2_category;
00251
00252 return inner_product_switch(first1, last1, first2, init, binary_op1,
00253 binary_op2, iterator1_category(),
00254 iterator2_category(), parallelism_tag);
00255 }
00256
00257 template<typename InputIterator1, typename InputIterator2, typename T,
00258 typename BinaryFunction1, typename BinaryFunction2>
00259 inline T
00260 inner_product(InputIterator1 first1, InputIterator1 last1,
00261 InputIterator2 first2, T init, BinaryFunction1 binary_op1,
00262 BinaryFunction2 binary_op2)
00263 {
00264 typedef iterator_traits<InputIterator1> traits1_type;
00265 typedef typename traits1_type::iterator_category iterator1_category;
00266
00267 typedef iterator_traits<InputIterator2> traits2_type;
00268 typedef typename traits2_type::iterator_category iterator2_category;
00269
00270 return inner_product_switch(first1, last1, first2, init, binary_op1,
00271 binary_op2, iterator1_category(),
00272 iterator2_category());
00273 }
00274
00275 template<typename InputIterator1, typename InputIterator2, typename T>
00276 inline T
00277 inner_product(InputIterator1 first1, InputIterator1 last1,
00278 InputIterator2 first2, T init,
00279 __gnu_parallel::_Parallelism parallelism_tag)
00280 {
00281 typedef iterator_traits<InputIterator1> traits_type1;
00282 typedef typename traits_type1::value_type value_type1;
00283 typedef iterator_traits<InputIterator2> traits_type2;
00284 typedef typename traits_type2::value_type value_type2;
00285
00286 typedef typename
00287 __gnu_parallel::multiplies<value_type1, value_type2>::result
00288 multiplies_result_type;
00289 return inner_product(first1, last1, first2, init,
00290 __gnu_parallel::plus<T, multiplies_result_type>(),
00291 __gnu_parallel::
00292 multiplies<value_type1, value_type2>(),
00293 parallelism_tag);
00294 }
00295
00296 template<typename InputIterator1, typename InputIterator2, typename T>
00297 inline T
00298 inner_product(InputIterator1 first1, InputIterator1 last1,
00299 InputIterator2 first2, T init)
00300 {
00301 typedef iterator_traits<InputIterator1> traits_type1;
00302 typedef typename traits_type1::value_type value_type1;
00303 typedef iterator_traits<InputIterator2> traits_type2;
00304 typedef typename traits_type2::value_type value_type2;
00305
00306 typedef typename
00307 __gnu_parallel::multiplies<value_type1, value_type2>::result
00308 multiplies_result_type;
00309 return inner_product(first1, last1, first2, init,
00310 __gnu_parallel::plus<T, multiplies_result_type>(),
00311 __gnu_parallel::
00312 multiplies<value_type1, value_type2>());
00313 }
00314
00315
00316 template<typename InputIterator, typename OutputIterator>
00317 inline OutputIterator
00318 partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
00319 __gnu_parallel::sequential_tag)
00320 { return _GLIBCXX_STD_P::partial_sum(begin, end, result); }
00321
00322
00323 template<typename InputIterator, typename OutputIterator,
00324 typename BinaryOperation>
00325 inline OutputIterator
00326 partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
00327 BinaryOperation bin_op, __gnu_parallel::sequential_tag)
00328 { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
00329
00330
00331 template<typename InputIterator, typename OutputIterator,
00332 typename BinaryOperation, typename IteratorTag1,
00333 typename IteratorTag2>
00334 inline OutputIterator
00335 partial_sum_switch(InputIterator begin, InputIterator end,
00336 OutputIterator result, BinaryOperation bin_op,
00337 IteratorTag1, IteratorTag2)
00338 { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
00339
00340
00341 template<typename InputIterator, typename OutputIterator,
00342 typename BinaryOperation>
00343 OutputIterator
00344 partial_sum_switch(InputIterator begin, InputIterator end,
00345 OutputIterator result, BinaryOperation bin_op,
00346 random_access_iterator_tag, random_access_iterator_tag)
00347 {
00348 if (_GLIBCXX_PARALLEL_CONDITION(
00349 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
00350 >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
00351 return __gnu_parallel::parallel_partial_sum(begin, end,
00352 result, bin_op);
00353 else
00354 return partial_sum(begin, end, result, bin_op,
00355 __gnu_parallel::sequential_tag());
00356 }
00357
00358
00359 template<typename InputIterator, typename OutputIterator>
00360 inline OutputIterator
00361 partial_sum(InputIterator begin, InputIterator end, OutputIterator result)
00362 {
00363 typedef typename iterator_traits<InputIterator>::value_type value_type;
00364 return partial_sum(begin, end, result, std::plus<value_type>());
00365 }
00366
00367
00368 template<typename InputIterator, typename OutputIterator,
00369 typename BinaryOperation>
00370 inline OutputIterator
00371 partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
00372 BinaryOperation binary_op)
00373 {
00374 typedef iterator_traits<InputIterator> traitsi_type;
00375 typedef typename traitsi_type::iterator_category iteratori_category;
00376
00377 typedef iterator_traits<OutputIterator> traitso_type;
00378 typedef typename traitso_type::iterator_category iteratoro_category;
00379
00380 return partial_sum_switch(begin, end, result, binary_op,
00381 iteratori_category(), iteratoro_category());
00382 }
00383
00384
00385 template<typename InputIterator, typename OutputIterator>
00386 inline OutputIterator
00387 adjacent_difference(InputIterator begin, InputIterator end,
00388 OutputIterator result, __gnu_parallel::sequential_tag)
00389 { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); }
00390
00391
00392 template<typename InputIterator, typename OutputIterator,
00393 typename BinaryOperation>
00394 inline OutputIterator
00395 adjacent_difference(InputIterator begin, InputIterator end,
00396 OutputIterator result, BinaryOperation bin_op,
00397 __gnu_parallel::sequential_tag)
00398 { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op); }
00399
00400
00401 template<typename InputIterator, typename OutputIterator,
00402 typename BinaryOperation, typename IteratorTag1,
00403 typename IteratorTag2>
00404 inline OutputIterator
00405 adjacent_difference_switch(InputIterator begin, InputIterator end,
00406 OutputIterator result, BinaryOperation bin_op,
00407 IteratorTag1, IteratorTag2)
00408 { return adjacent_difference(begin, end, result, bin_op,
00409 __gnu_parallel::sequential_tag()); }
00410
00411
00412 template<typename InputIterator, typename OutputIterator,
00413 typename BinaryOperation>
00414 OutputIterator
00415 adjacent_difference_switch(InputIterator begin, InputIterator end,
00416 OutputIterator result, BinaryOperation bin_op,
00417 random_access_iterator_tag,
00418 random_access_iterator_tag,
00419 __gnu_parallel::_Parallelism parallelism_tag
00420 = __gnu_parallel::parallel_balanced)
00421 {
00422 if (_GLIBCXX_PARALLEL_CONDITION(
00423 static_cast<__gnu_parallel::sequence_index_t>(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::iterator_pair<InputIterator, OutputIterator,
00429 random_access_iterator_tag> ip;
00430 *result = *begin;
00431 ip begin_pair(begin + 1, result + 1),
00432 end_pair(end, result + (end - begin));
00433 __gnu_parallel::adjacent_difference_selector<ip> functionality;
00434 __gnu_parallel::
00435 for_each_template_random_access(begin_pair, end_pair, bin_op,
00436 functionality,
00437 __gnu_parallel::dummy_reduct(),
00438 dummy, dummy, -1, parallelism_tag);
00439 return functionality.finish_iterator;
00440 }
00441 else
00442 return adjacent_difference(begin, end, result, bin_op,
00443 __gnu_parallel::sequential_tag());
00444 }
00445
00446
00447 template<typename InputIterator, typename OutputIterator>
00448 inline OutputIterator
00449 adjacent_difference(InputIterator begin, InputIterator end,
00450 OutputIterator result,
00451 __gnu_parallel::_Parallelism parallelism_tag)
00452 {
00453 typedef iterator_traits<InputIterator> traits_type;
00454 typedef typename traits_type::value_type value_type;
00455 return adjacent_difference(begin, end, result, std::minus<value_type>(),
00456 parallelism_tag);
00457 }
00458
00459 template<typename InputIterator, typename OutputIterator>
00460 inline OutputIterator
00461 adjacent_difference(InputIterator begin, InputIterator end,
00462 OutputIterator result)
00463 {
00464 typedef iterator_traits<InputIterator> traits_type;
00465 typedef typename traits_type::value_type value_type;
00466 return adjacent_difference(begin, end, result, std::minus<value_type>());
00467 }
00468
00469 template<typename InputIterator, typename OutputIterator,
00470 typename BinaryOperation>
00471 inline OutputIterator
00472 adjacent_difference(InputIterator begin, InputIterator end,
00473 OutputIterator result, BinaryOperation binary_op,
00474 __gnu_parallel::_Parallelism parallelism_tag)
00475 {
00476 typedef iterator_traits<InputIterator> traitsi_type;
00477 typedef typename traitsi_type::iterator_category iteratori_category;
00478
00479 typedef iterator_traits<OutputIterator> traitso_type;
00480 typedef typename traitso_type::iterator_category iteratoro_category;
00481
00482 return adjacent_difference_switch(begin, end, result, binary_op,
00483 iteratori_category(),
00484 iteratoro_category(), parallelism_tag);
00485 }
00486
00487 template<typename InputIterator, typename OutputIterator,
00488 typename BinaryOperation>
00489 inline OutputIterator
00490 adjacent_difference(InputIterator begin, InputIterator end,
00491 OutputIterator result, BinaryOperation binary_op)
00492 {
00493 typedef iterator_traits<InputIterator> traitsi_type;
00494 typedef typename traitsi_type::iterator_category iteratori_category;
00495
00496 typedef iterator_traits<OutputIterator> traitso_type;
00497 typedef typename traitso_type::iterator_category iteratoro_category;
00498
00499 return adjacent_difference_switch(begin, end, result, binary_op,
00500 iteratori_category(),
00501 iteratoro_category());
00502 }
00503 }
00504 }
00505
00506 #endif