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 <bits/stl_function.h>
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 _IIter, typename _Tp>
00055 inline _Tp
00056 accumulate(_IIter __begin, _IIter __end, _Tp __init,
00057 __gnu_parallel::sequential_tag)
00058 { return _GLIBCXX_STD_P::accumulate(__begin, __end, __init); }
00059
00060 template<typename _IIter, typename _Tp, typename _BinaryOperation>
00061 inline _Tp
00062 accumulate(_IIter __begin, _IIter __end, _Tp __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 _IIter, typename _Tp, typename _IteratorTag>
00068 inline _Tp
00069 __accumulate_switch(_IIter __begin, _IIter __end,
00070 _Tp __init, _IteratorTag)
00071 { return accumulate(__begin, __end, __init,
00072 __gnu_parallel::sequential_tag()); }
00073
00074 template<typename _IIter, typename _Tp, typename _BinaryOperation,
00075 typename _IteratorTag>
00076 inline _Tp
00077 __accumulate_switch(_IIter __begin, _IIter __end, _Tp __init,
00078 _BinaryOperation __binary_op, _IteratorTag)
00079 { return accumulate(__begin, __end, __init, __binary_op,
00080 __gnu_parallel::sequential_tag()); }
00081
00082
00083 template<typename __RAIter, typename _Tp, typename _BinaryOperation>
00084 _Tp
00085 __accumulate_switch(__RAIter __begin, __RAIter __end,
00086 _Tp __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::_SequenceIndex>(__end - __begin)
00093 >= __gnu_parallel::_Settings::get().accumulate_minimal_n
00094 && __gnu_parallel::__is_parallel(__parallelism_tag)))
00095 {
00096 _Tp __res = __init;
00097 __gnu_parallel::__accumulate_selector<__RAIter>
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 _IIter, typename _Tp>
00116 inline _Tp
00117 accumulate(_IIter __begin, _IIter __end, _Tp __init,
00118 __gnu_parallel::_Parallelism __parallelism_tag)
00119 {
00120 typedef std::iterator_traits<_IIter> _IteratorTraits;
00121 typedef typename _IteratorTraits::value_type _ValueType;
00122 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00123
00124 return __accumulate_switch(__begin, __end, __init,
00125 __gnu_parallel::_Plus<_Tp, _ValueType>(),
00126 _IteratorCategory(), __parallelism_tag);
00127 }
00128
00129 template<typename _IIter, typename _Tp>
00130 inline _Tp
00131 accumulate(_IIter __begin, _IIter __end, _Tp __init)
00132 {
00133 typedef std::iterator_traits<_IIter> _IteratorTraits;
00134 typedef typename _IteratorTraits::value_type _ValueType;
00135 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00136
00137 return __accumulate_switch(__begin, __end, __init,
00138 __gnu_parallel::_Plus<_Tp, _ValueType>(),
00139 _IteratorCategory());
00140 }
00141
00142 template<typename _IIter, typename _Tp, typename _BinaryOperation>
00143 inline _Tp
00144 accumulate(_IIter __begin, _IIter __end, _Tp __init,
00145 _BinaryOperation __binary_op,
00146 __gnu_parallel::_Parallelism __parallelism_tag)
00147 {
00148 typedef iterator_traits<_IIter> _IteratorTraits;
00149 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00150 return __accumulate_switch(__begin, __end, __init, __binary_op,
00151 _IteratorCategory(), __parallelism_tag);
00152 }
00153
00154 template<typename _IIter, typename _Tp, typename _BinaryOperation>
00155 inline _Tp
00156 accumulate(_IIter __begin, _IIter __end, _Tp __init,
00157 _BinaryOperation __binary_op)
00158 {
00159 typedef iterator_traits<_IIter> _IteratorTraits;
00160 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
00161 return __accumulate_switch(__begin, __end, __init, __binary_op,
00162 _IteratorCategory());
00163 }
00164
00165
00166
00167 template<typename _IIter1, typename _IIter2, typename _Tp>
00168 inline _Tp
00169 inner_product(_IIter1 __first1, _IIter1 __last1,
00170 _IIter2 __first2, _Tp __init,
00171 __gnu_parallel::sequential_tag)
00172 { return _GLIBCXX_STD_P::inner_product(
00173 __first1, __last1, __first2, __init); }
00174
00175 template<typename _IIter1, typename _IIter2, typename _Tp,
00176 typename _BinaryFunction1, typename _BinaryFunction2>
00177 inline _Tp
00178 inner_product(_IIter1 __first1, _IIter1 __last1,
00179 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
00180 _BinaryFunction2 __binary_op2,
00181 __gnu_parallel::sequential_tag)
00182 { return _GLIBCXX_STD_P::inner_product(__first1, __last1, __first2, __init,
00183 __binary_op1, __binary_op2); }
00184
00185
00186 template<typename _RAIter1, typename _RAIter2,
00187 typename _Tp, typename _BinaryFunction1, typename _BinaryFunction2>
00188 _Tp
00189 __inner_product_switch(_RAIter1 __first1,
00190 _RAIter1 __last1,
00191 _RAIter2 __first2, _Tp __init,
00192 _BinaryFunction1 __binary_op1,
00193 _BinaryFunction2 __binary_op2,
00194 random_access_iterator_tag,
00195 random_access_iterator_tag,
00196 __gnu_parallel::_Parallelism __parallelism_tag
00197 = __gnu_parallel::parallel_unbalanced)
00198 {
00199 if (_GLIBCXX_PARALLEL_CONDITION((__last1 - __first1)
00200 >= __gnu_parallel::_Settings::get().
00201 accumulate_minimal_n
00202 && __gnu_parallel::
00203 __is_parallel(__parallelism_tag)))
00204 {
00205 _Tp __res = __init;
00206 __gnu_parallel::
00207 __inner_product_selector<_RAIter1,
00208 _RAIter2, _Tp> __my_selector(__first1, __first2);
00209 __gnu_parallel::
00210 __for_each_template_random_access_ed(
00211 __first1, __last1, __binary_op2, __my_selector, __binary_op1,
00212 __res, __res, -1);
00213 return __res;
00214 }
00215 else
00216 return inner_product(__first1, __last1, __first2, __init,
00217 __gnu_parallel::sequential_tag());
00218 }
00219
00220
00221 template<typename _IIter1, typename _IIter2, typename _Tp,
00222 typename _BinaryFunction1, typename _BinaryFunction2,
00223 typename _IteratorTag1, typename _IteratorTag2>
00224 inline _Tp
00225 __inner_product_switch(_IIter1 __first1, _IIter1 __last1,
00226 _IIter2 __first2, _Tp __init,
00227 _BinaryFunction1 __binary_op1,
00228 _BinaryFunction2 __binary_op2,
00229 _IteratorTag1, _IteratorTag2)
00230 { return inner_product(__first1, __last1, __first2, __init, __binary_op1,
00231 __binary_op2, __gnu_parallel::sequential_tag()); }
00232
00233 template<typename _IIter1, typename _IIter2, typename _Tp,
00234 typename _BinaryFunction1, typename _BinaryFunction2>
00235 inline _Tp
00236 inner_product(_IIter1 __first1, _IIter1 __last1,
00237 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
00238 _BinaryFunction2 __binary_op2,
00239 __gnu_parallel::_Parallelism __parallelism_tag)
00240 {
00241 typedef iterator_traits<_IIter1> _TraitsType1;
00242 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00243
00244 typedef iterator_traits<_IIter2> _TraitsType2;
00245 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00246
00247 return __inner_product_switch(__first1, __last1, __first2, __init,
00248 __binary_op1, __binary_op2,
00249 _IteratorCategory1(), _IteratorCategory2(),
00250 __parallelism_tag);
00251 }
00252
00253 template<typename _IIter1, typename _IIter2, typename _Tp,
00254 typename _BinaryFunction1, typename _BinaryFunction2>
00255 inline _Tp
00256 inner_product(_IIter1 __first1, _IIter1 __last1,
00257 _IIter2 __first2, _Tp __init, _BinaryFunction1 __binary_op1,
00258 _BinaryFunction2 __binary_op2)
00259 {
00260 typedef iterator_traits<_IIter1> _TraitsType1;
00261 typedef typename _TraitsType1::iterator_category _IteratorCategory1;
00262
00263 typedef iterator_traits<_IIter2> _TraitsType2;
00264 typedef typename _TraitsType2::iterator_category _IteratorCategory2;
00265
00266 return __inner_product_switch(__first1, __last1, __first2, __init,
00267 __binary_op1, __binary_op2,
00268 _IteratorCategory1(),
00269 _IteratorCategory2());
00270 }
00271
00272 template<typename _IIter1, typename _IIter2, typename _Tp>
00273 inline _Tp
00274 inner_product(_IIter1 __first1, _IIter1 __last1,
00275 _IIter2 __first2, _Tp __init,
00276 __gnu_parallel::_Parallelism __parallelism_tag)
00277 {
00278 typedef iterator_traits<_IIter1> _TraitsType1;
00279 typedef typename _TraitsType1::value_type _ValueType1;
00280 typedef iterator_traits<_IIter2> _TraitsType2;
00281 typedef typename _TraitsType2::value_type _ValueType2;
00282
00283 typedef typename
00284 __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
00285 _MultipliesResultType;
00286 return _GLIBCXX_STD_P::inner_product(__first1, __last1, __first2, __init,
00287 __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
00288 __gnu_parallel::
00289 _Multiplies<_ValueType1, _ValueType2>(),
00290 __parallelism_tag);
00291 }
00292
00293 template<typename _IIter1, typename _IIter2, typename _Tp>
00294 inline _Tp
00295 inner_product(_IIter1 __first1, _IIter1 __last1,
00296 _IIter2 __first2, _Tp __init)
00297 {
00298 typedef iterator_traits<_IIter1> _TraitsType1;
00299 typedef typename _TraitsType1::value_type _ValueType1;
00300 typedef iterator_traits<_IIter2> _TraitsType2;
00301 typedef typename _TraitsType2::value_type _ValueType2;
00302
00303 typedef typename
00304 __gnu_parallel::_Multiplies<_ValueType1, _ValueType2>::result_type
00305 _MultipliesResultType;
00306 return _GLIBCXX_STD_P::inner_product(__first1, __last1, __first2, __init,
00307 __gnu_parallel::_Plus<_Tp, _MultipliesResultType>(),
00308 __gnu_parallel::
00309 _Multiplies<_ValueType1, _ValueType2>());
00310 }
00311
00312
00313 template<typename _IIter, typename _OutputIterator>
00314 inline _OutputIterator
00315 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
00316 __gnu_parallel::sequential_tag)
00317 { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result); }
00318
00319
00320 template<typename _IIter, typename _OutputIterator,
00321 typename _BinaryOperation>
00322 inline _OutputIterator
00323 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
00324 _BinaryOperation __bin_op, __gnu_parallel::sequential_tag)
00325 { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result, __bin_op); }
00326
00327
00328 template<typename _IIter, typename _OutputIterator,
00329 typename _BinaryOperation, typename _IteratorTag1,
00330 typename _IteratorTag2>
00331 inline _OutputIterator
00332 __partial_sum_switch(_IIter __begin, _IIter __end,
00333 _OutputIterator __result, _BinaryOperation __bin_op,
00334 _IteratorTag1, _IteratorTag2)
00335 { return _GLIBCXX_STD_P::partial_sum(__begin, __end, __result, __bin_op); }
00336
00337
00338 template<typename _IIter, typename _OutputIterator,
00339 typename _BinaryOperation>
00340 _OutputIterator
00341 __partial_sum_switch(_IIter __begin, _IIter __end,
00342 _OutputIterator __result, _BinaryOperation __bin_op,
00343 random_access_iterator_tag,
00344 random_access_iterator_tag)
00345 {
00346 if (_GLIBCXX_PARALLEL_CONDITION(
00347 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
00348 >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
00349 return __gnu_parallel::__parallel_partial_sum(__begin, __end,
00350 __result, __bin_op);
00351 else
00352 return partial_sum(__begin, __end, __result, __bin_op,
00353 __gnu_parallel::sequential_tag());
00354 }
00355
00356
00357 template<typename _IIter, typename _OutputIterator>
00358 inline _OutputIterator
00359 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result)
00360 {
00361 typedef typename iterator_traits<_IIter>::value_type _ValueType;
00362 return _GLIBCXX_STD_P::partial_sum(__begin, __end,
00363 __result, std::plus<_ValueType>());
00364 }
00365
00366
00367 template<typename _IIter, typename _OutputIterator,
00368 typename _BinaryOperation>
00369 inline _OutputIterator
00370 partial_sum(_IIter __begin, _IIter __end, _OutputIterator __result,
00371 _BinaryOperation __binary_op)
00372 {
00373 typedef iterator_traits<_IIter> _ITraitsType;
00374 typedef typename _ITraitsType::iterator_category _IIteratorCategory;
00375
00376 typedef iterator_traits<_OutputIterator> _OTraitsType;
00377 typedef typename _OTraitsType::iterator_category _OIterCategory;
00378
00379 return __partial_sum_switch(__begin, __end, __result, __binary_op,
00380 _IIteratorCategory(), _OIterCategory());
00381 }
00382
00383
00384 template<typename _IIter, typename _OutputIterator>
00385 inline _OutputIterator
00386 adjacent_difference(_IIter __begin, _IIter __end, _OutputIterator __result,
00387 __gnu_parallel::sequential_tag)
00388 { return _GLIBCXX_STD_P::adjacent_difference(__begin, __end, __result); }
00389
00390
00391 template<typename _IIter, typename _OutputIterator,
00392 typename _BinaryOperation>
00393 inline _OutputIterator
00394 adjacent_difference(_IIter __begin, _IIter __end,
00395 _OutputIterator __result, _BinaryOperation __bin_op,
00396 __gnu_parallel::sequential_tag)
00397 { return _GLIBCXX_STD_P::adjacent_difference(__begin, __end,
00398 __result, __bin_op); }
00399
00400
00401 template<typename _IIter, typename _OutputIterator,
00402 typename _BinaryOperation, typename _IteratorTag1,
00403 typename _IteratorTag2>
00404 inline _OutputIterator
00405 __adjacent_difference_switch(_IIter __begin, _IIter __end,
00406 _OutputIterator __result,
00407 _BinaryOperation __bin_op, _IteratorTag1,
00408 _IteratorTag2)
00409 { return adjacent_difference(__begin, __end, __result, __bin_op,
00410 __gnu_parallel::sequential_tag()); }
00411
00412
00413 template<typename _IIter, typename _OutputIterator,
00414 typename _BinaryOperation>
00415 _OutputIterator
00416 __adjacent_difference_switch(_IIter __begin, _IIter __end,
00417 _OutputIterator __result,
00418 _BinaryOperation __bin_op,
00419 random_access_iterator_tag,
00420 random_access_iterator_tag,
00421 __gnu_parallel::_Parallelism
00422 __parallelism_tag
00423 = __gnu_parallel::parallel_balanced)
00424 {
00425 if (_GLIBCXX_PARALLEL_CONDITION(
00426 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
00427 >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
00428 && __gnu_parallel::__is_parallel(__parallelism_tag)))
00429 {
00430 bool __dummy = true;
00431 typedef __gnu_parallel::_IteratorPair<_IIter, _OutputIterator,
00432 random_access_iterator_tag> _ItTrip;
00433 *__result = *__begin;
00434 _ItTrip __begin_pair(__begin + 1, __result + 1),
00435 __end_pair(__end, __result + (__end - __begin));
00436 __gnu_parallel::__adjacent_difference_selector<_ItTrip>
00437 __functionality;
00438 __gnu_parallel::
00439 __for_each_template_random_access_ed(
00440 __begin_pair, __end_pair, __bin_op, __functionality,
00441 __gnu_parallel::_DummyReduct(), __dummy, __dummy, -1);
00442 return __functionality._M_finish_iterator;
00443 }
00444 else
00445 return adjacent_difference(__begin, __end, __result, __bin_op,
00446 __gnu_parallel::sequential_tag());
00447 }
00448
00449
00450 template<typename _IIter, typename _OutputIterator>
00451 inline _OutputIterator
00452 adjacent_difference(_IIter __begin, _IIter __end,
00453 _OutputIterator __result,
00454 __gnu_parallel::_Parallelism __parallelism_tag)
00455 {
00456 typedef iterator_traits<_IIter> _TraitsType;
00457 typedef typename _TraitsType::value_type _ValueType;
00458 return adjacent_difference(__begin, __end, __result,
00459 std::minus<_ValueType>(),
00460 __parallelism_tag);
00461 }
00462
00463 template<typename _IIter, typename _OutputIterator>
00464 inline _OutputIterator
00465 adjacent_difference(_IIter __begin, _IIter __end,
00466 _OutputIterator __result)
00467 {
00468 typedef iterator_traits<_IIter> _TraitsType;
00469 typedef typename _TraitsType::value_type _ValueType;
00470 return adjacent_difference(__begin, __end, __result,
00471 std::minus<_ValueType>());
00472 }
00473
00474 template<typename _IIter, typename _OutputIterator,
00475 typename _BinaryOperation>
00476 inline _OutputIterator
00477 adjacent_difference(_IIter __begin, _IIter __end,
00478 _OutputIterator __result, _BinaryOperation __binary_op,
00479 __gnu_parallel::_Parallelism __parallelism_tag)
00480 {
00481 typedef iterator_traits<_IIter> _ITraitsType;
00482 typedef typename _ITraitsType::iterator_category _IIteratorCategory;
00483
00484 typedef iterator_traits<_OutputIterator> _OTraitsType;
00485 typedef typename _OTraitsType::iterator_category _OIterCategory;
00486
00487 return __adjacent_difference_switch(__begin, __end, __result,
00488 __binary_op,
00489 _IIteratorCategory(),
00490 _OIterCategory(),
00491 __parallelism_tag);
00492 }
00493
00494 template<typename _IIter, typename _OutputIterator,
00495 typename _BinaryOperation>
00496 inline _OutputIterator
00497 adjacent_difference(_IIter __begin, _IIter __end,
00498 _OutputIterator __result, _BinaryOperation __binary_op)
00499 {
00500 typedef iterator_traits<_IIter> _ITraitsType;
00501 typedef typename _ITraitsType::iterator_category _IIteratorCategory;
00502
00503 typedef iterator_traits<_OutputIterator> _OTraitsType;
00504 typedef typename _OTraitsType::iterator_category _OIterCategory;
00505
00506 return __adjacent_difference_switch(__begin, __end, __result,
00507 __binary_op,
00508 _IIteratorCategory(),
00509 _OIterCategory());
00510 }
00511 }
00512 }
00513
00514 #endif