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