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 _GLIBCXX_STD_P::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 _GLIBCXX_STD_P::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 _GLIBCXX_STD_P::partial_sum(begin, end, result,
00359 std::plus<value_type>());
00360 }
00361
00362
00363 template<typename InputIterator, typename OutputIterator,
00364 typename BinaryOperation>
00365 inline OutputIterator
00366 partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
00367 BinaryOperation binary_op)
00368 {
00369 typedef iterator_traits<InputIterator> traitsi_type;
00370 typedef typename traitsi_type::iterator_category iteratori_category;
00371
00372 typedef iterator_traits<OutputIterator> traitso_type;
00373 typedef typename traitso_type::iterator_category iteratoro_category;
00374
00375 return partial_sum_switch(begin, end, result, binary_op,
00376 iteratori_category(), iteratoro_category());
00377 }
00378
00379
00380 template<typename InputIterator, typename OutputIterator>
00381 inline OutputIterator
00382 adjacent_difference(InputIterator begin, InputIterator end,
00383 OutputIterator result, __gnu_parallel::sequential_tag)
00384 { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); }
00385
00386
00387 template<typename InputIterator, typename OutputIterator,
00388 typename BinaryOperation>
00389 inline OutputIterator
00390 adjacent_difference(InputIterator begin, InputIterator end,
00391 OutputIterator result, BinaryOperation bin_op,
00392 __gnu_parallel::sequential_tag)
00393 { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op); }
00394
00395
00396 template<typename InputIterator, typename OutputIterator,
00397 typename BinaryOperation, typename IteratorTag1,
00398 typename IteratorTag2>
00399 inline OutputIterator
00400 adjacent_difference_switch(InputIterator begin, InputIterator end,
00401 OutputIterator result, BinaryOperation bin_op,
00402 IteratorTag1, IteratorTag2)
00403 { return adjacent_difference(begin, end, result, bin_op,
00404 __gnu_parallel::sequential_tag()); }
00405
00406
00407 template<typename InputIterator, typename OutputIterator,
00408 typename BinaryOperation>
00409 OutputIterator
00410 adjacent_difference_switch(InputIterator begin, InputIterator end,
00411 OutputIterator result, BinaryOperation bin_op,
00412 random_access_iterator_tag,
00413 random_access_iterator_tag,
00414 __gnu_parallel::_Parallelism parallelism_tag
00415 = __gnu_parallel::parallel_balanced)
00416 {
00417 if (_GLIBCXX_PARALLEL_CONDITION(
00418 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
00419 >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
00420 && __gnu_parallel::is_parallel(parallelism_tag)))
00421 {
00422 bool dummy = true;
00423 typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator,
00424 random_access_iterator_tag> ip;
00425 *result = *begin;
00426 ip begin_pair(begin + 1, result + 1),
00427 end_pair(end, result + (end - begin));
00428 __gnu_parallel::adjacent_difference_selector<ip> functionality;
00429 __gnu_parallel::
00430 for_each_template_random_access_ed(begin_pair, end_pair, bin_op,
00431 functionality,
00432 __gnu_parallel::dummy_reduct(),
00433 dummy, dummy, -1);
00434 return functionality.finish_iterator;
00435 }
00436 else
00437 return adjacent_difference(begin, end, result, bin_op,
00438 __gnu_parallel::sequential_tag());
00439 }
00440
00441
00442 template<typename InputIterator, typename OutputIterator>
00443 inline OutputIterator
00444 adjacent_difference(InputIterator begin, InputIterator end,
00445 OutputIterator result,
00446 __gnu_parallel::_Parallelism parallelism_tag)
00447 {
00448 typedef iterator_traits<InputIterator> traits_type;
00449 typedef typename traits_type::value_type value_type;
00450 return adjacent_difference(begin, end, result, std::minus<value_type>(),
00451 parallelism_tag);
00452 }
00453
00454 template<typename InputIterator, typename OutputIterator>
00455 inline OutputIterator
00456 adjacent_difference(InputIterator begin, InputIterator end,
00457 OutputIterator result)
00458 {
00459 typedef iterator_traits<InputIterator> traits_type;
00460 typedef typename traits_type::value_type value_type;
00461 return adjacent_difference(begin, end, result, std::minus<value_type>());
00462 }
00463
00464 template<typename InputIterator, typename OutputIterator,
00465 typename BinaryOperation>
00466 inline OutputIterator
00467 adjacent_difference(InputIterator begin, InputIterator end,
00468 OutputIterator result, BinaryOperation binary_op,
00469 __gnu_parallel::_Parallelism parallelism_tag)
00470 {
00471 typedef iterator_traits<InputIterator> traitsi_type;
00472 typedef typename traitsi_type::iterator_category iteratori_category;
00473
00474 typedef iterator_traits<OutputIterator> traitso_type;
00475 typedef typename traitso_type::iterator_category iteratoro_category;
00476
00477 return adjacent_difference_switch(begin, end, result, binary_op,
00478 iteratori_category(),
00479 iteratoro_category(), parallelism_tag);
00480 }
00481
00482 template<typename InputIterator, typename OutputIterator,
00483 typename BinaryOperation>
00484 inline OutputIterator
00485 adjacent_difference(InputIterator begin, InputIterator end,
00486 OutputIterator result, BinaryOperation binary_op)
00487 {
00488 typedef iterator_traits<InputIterator> traitsi_type;
00489 typedef typename traitsi_type::iterator_category iteratori_category;
00490
00491 typedef iterator_traits<OutputIterator> traitso_type;
00492 typedef typename traitso_type::iterator_category iteratoro_category;
00493
00494 return adjacent_difference_switch(begin, end, result, binary_op,
00495 iteratori_category(),
00496 iteratoro_category());
00497 }
00498 }
00499 }
00500
00501 #endif