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 #ifndef _GLIBCXX_PARALLEL_ALGO_H
00044 #define _GLIBCXX_PARALLEL_ALGO_H 1
00045
00046 #include <parallel/algorithmfwd.h>
00047 #include <bits/stl_algobase.h>
00048 #include <bits/stl_algo.h>
00049 #include <parallel/iterator.h>
00050 #include <parallel/base.h>
00051 #include <parallel/sort.h>
00052 #include <parallel/workstealing.h>
00053 #include <parallel/par_loop.h>
00054 #include <parallel/omp_loop.h>
00055 #include <parallel/omp_loop_static.h>
00056 #include <parallel/for_each_selectors.h>
00057 #include <parallel/for_each.h>
00058 #include <parallel/find.h>
00059 #include <parallel/find_selectors.h>
00060 #include <parallel/search.h>
00061 #include <parallel/random_shuffle.h>
00062 #include <parallel/partition.h>
00063 #include <parallel/merge.h>
00064 #include <parallel/unique_copy.h>
00065 #include <parallel/set_operations.h>
00066
00067 namespace std
00068 {
00069 namespace __parallel
00070 {
00071
00072 template<typename InputIterator, typename Function>
00073 inline Function
00074 for_each(InputIterator begin, InputIterator end, Function f,
00075 __gnu_parallel::sequential_tag)
00076 { return _GLIBCXX_STD_P::for_each(begin, end, f); }
00077
00078
00079 template<typename InputIterator, typename Function, typename IteratorTag>
00080 inline Function
00081 for_each_switch(InputIterator begin, InputIterator end, Function f,
00082 IteratorTag)
00083 { return for_each(begin, end, f, __gnu_parallel::sequential_tag()); }
00084
00085
00086 template<typename RandomAccessIterator, typename Function>
00087 Function
00088 for_each_switch(RandomAccessIterator begin, RandomAccessIterator end,
00089 Function f, random_access_iterator_tag,
00090 __gnu_parallel::_Parallelism parallelism_tag
00091 = __gnu_parallel::parallel_balanced)
00092 {
00093 if (_GLIBCXX_PARALLEL_CONDITION(
00094 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
00095 >= __gnu_parallel::_Settings::get().for_each_minimal_n
00096 && __gnu_parallel::is_parallel(parallelism_tag)))
00097 {
00098 bool dummy;
00099 __gnu_parallel::for_each_selector<RandomAccessIterator> functionality;
00100
00101 return __gnu_parallel::
00102 for_each_template_random_access(begin, end, f, functionality,
00103 __gnu_parallel::dummy_reduct(),
00104 true, dummy, -1, parallelism_tag);
00105 }
00106 else
00107 return for_each(begin, end, f, __gnu_parallel::sequential_tag());
00108 }
00109
00110
00111 template<typename Iterator, typename Function>
00112 inline Function
00113 for_each(Iterator begin, Iterator end, Function f,
00114 __gnu_parallel::_Parallelism parallelism_tag)
00115 {
00116 typedef std::iterator_traits<Iterator> iterator_traits;
00117 typedef typename iterator_traits::iterator_category iterator_category;
00118 return for_each_switch(begin, end, f, iterator_category(),
00119 parallelism_tag);
00120 }
00121
00122 template<typename Iterator, typename Function>
00123 inline Function
00124 for_each(Iterator begin, Iterator end, Function f)
00125 {
00126 typedef std::iterator_traits<Iterator> iterator_traits;
00127 typedef typename iterator_traits::iterator_category iterator_category;
00128 return for_each_switch(begin, end, f, iterator_category());
00129 }
00130
00131
00132
00133 template<typename InputIterator, typename T>
00134 inline InputIterator
00135 find(InputIterator begin, InputIterator end, const T& val,
00136 __gnu_parallel::sequential_tag)
00137 { return _GLIBCXX_STD_P::find(begin, end, val); }
00138
00139
00140 template<typename InputIterator, typename T, typename IteratorTag>
00141 inline InputIterator
00142 find_switch(InputIterator begin, InputIterator end, const T& val,
00143 IteratorTag)
00144 { return _GLIBCXX_STD_P::find(begin, end, val); }
00145
00146
00147 template<typename RandomAccessIterator, typename T>
00148 RandomAccessIterator
00149 find_switch(RandomAccessIterator begin, RandomAccessIterator end,
00150 const T& val, random_access_iterator_tag)
00151 {
00152 typedef iterator_traits<RandomAccessIterator> traits_type;
00153 typedef typename traits_type::value_type value_type;
00154
00155 if (_GLIBCXX_PARALLEL_CONDITION(true))
00156 {
00157 binder2nd<__gnu_parallel::equal_to<value_type, T> >
00158 comp(__gnu_parallel::equal_to<value_type, T>(), val);
00159 return __gnu_parallel::find_template(begin, end, begin, comp,
00160 __gnu_parallel::
00161 find_if_selector()).first;
00162 }
00163 else
00164 return _GLIBCXX_STD_P::find(begin, end, val);
00165 }
00166
00167
00168 template<typename InputIterator, typename T>
00169 inline InputIterator
00170 find(InputIterator begin, InputIterator end, const T& val)
00171 {
00172 typedef std::iterator_traits<InputIterator> iterator_traits;
00173 typedef typename iterator_traits::iterator_category iterator_category;
00174 return find_switch(begin, end, val, iterator_category());
00175 }
00176
00177
00178 template<typename InputIterator, typename Predicate>
00179 inline InputIterator
00180 find_if(InputIterator begin, InputIterator end, Predicate pred,
00181 __gnu_parallel::sequential_tag)
00182 { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
00183
00184
00185 template<typename InputIterator, typename Predicate, typename IteratorTag>
00186 inline InputIterator
00187 find_if_switch(InputIterator begin, InputIterator end, Predicate pred,
00188 IteratorTag)
00189 { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
00190
00191
00192 template<typename RandomAccessIterator, typename Predicate>
00193 RandomAccessIterator
00194 find_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
00195 Predicate pred, random_access_iterator_tag)
00196 {
00197 if (_GLIBCXX_PARALLEL_CONDITION(true))
00198 return __gnu_parallel::find_template(begin, end, begin, pred,
00199 __gnu_parallel::
00200 find_if_selector()).first;
00201 else
00202 return _GLIBCXX_STD_P::find_if(begin, end, pred);
00203 }
00204
00205
00206 template<typename InputIterator, typename Predicate>
00207 inline InputIterator
00208 find_if(InputIterator begin, InputIterator end, Predicate pred)
00209 {
00210 typedef std::iterator_traits<InputIterator> iterator_traits;
00211 typedef typename iterator_traits::iterator_category iterator_category;
00212 return find_if_switch(begin, end, pred, iterator_category());
00213 }
00214
00215
00216 template<typename InputIterator, typename ForwardIterator>
00217 inline InputIterator
00218 find_first_of(InputIterator begin1, InputIterator end1,
00219 ForwardIterator begin2, ForwardIterator end2,
00220 __gnu_parallel::sequential_tag)
00221 { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2); }
00222
00223
00224 template<typename InputIterator, typename ForwardIterator,
00225 typename BinaryPredicate>
00226 inline InputIterator
00227 find_first_of(InputIterator begin1, InputIterator end1,
00228 ForwardIterator begin2, ForwardIterator end2,
00229 BinaryPredicate comp, __gnu_parallel::sequential_tag)
00230 { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2, comp); }
00231
00232
00233 template<typename InputIterator, typename ForwardIterator,
00234 typename IteratorTag1, typename IteratorTag2>
00235 inline InputIterator
00236 find_first_of_switch(InputIterator begin1, InputIterator end1,
00237 ForwardIterator begin2, ForwardIterator end2,
00238 IteratorTag1, IteratorTag2)
00239 { return find_first_of(begin1, end1, begin2, end2,
00240 __gnu_parallel::sequential_tag()); }
00241
00242
00243 template<typename RandomAccessIterator, typename ForwardIterator,
00244 typename BinaryPredicate, typename IteratorTag>
00245 inline RandomAccessIterator
00246 find_first_of_switch(RandomAccessIterator begin1,
00247 RandomAccessIterator end1,
00248 ForwardIterator begin2, ForwardIterator end2,
00249 BinaryPredicate comp, random_access_iterator_tag,
00250 IteratorTag)
00251 {
00252 return __gnu_parallel::
00253 find_template(begin1, end1, begin1, comp,
00254 __gnu_parallel::find_first_of_selector
00255 <ForwardIterator>(begin2, end2)).first;
00256 }
00257
00258
00259 template<typename InputIterator, typename ForwardIterator,
00260 typename BinaryPredicate, typename IteratorTag1,
00261 typename IteratorTag2>
00262 inline InputIterator
00263 find_first_of_switch(InputIterator begin1, InputIterator end1,
00264 ForwardIterator begin2, ForwardIterator end2,
00265 BinaryPredicate comp, IteratorTag1, IteratorTag2)
00266 { return find_first_of(begin1, end1, begin2, end2, comp,
00267 __gnu_parallel::sequential_tag()); }
00268
00269
00270 template<typename InputIterator, typename ForwardIterator,
00271 typename BinaryPredicate>
00272 inline InputIterator
00273 find_first_of(InputIterator begin1, InputIterator end1,
00274 ForwardIterator begin2, ForwardIterator end2,
00275 BinaryPredicate comp)
00276 {
00277 typedef std::iterator_traits<InputIterator> iteratori_traits;
00278 typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
00279 typedef typename iteratori_traits::iterator_category iteratori_category;
00280 typedef typename iteratorf_traits::iterator_category iteratorf_category;
00281
00282 return find_first_of_switch(begin1, end1, begin2, end2, comp,
00283 iteratori_category(), iteratorf_category());
00284 }
00285
00286
00287 template<typename InputIterator, typename ForwardIterator>
00288 inline InputIterator
00289 find_first_of(InputIterator begin1, InputIterator end1,
00290 ForwardIterator begin2, ForwardIterator end2)
00291 {
00292 typedef std::iterator_traits<InputIterator> iteratori_traits;
00293 typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
00294 typedef typename iteratori_traits::value_type valuei_type;
00295 typedef typename iteratorf_traits::value_type valuef_type;
00296
00297 return find_first_of(begin1, end1, begin2, end2, __gnu_parallel::
00298 equal_to<valuei_type, valuef_type>());
00299 }
00300
00301
00302 template<typename InputIterator, typename OutputIterator>
00303 inline OutputIterator
00304 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
00305 __gnu_parallel::sequential_tag)
00306 { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out); }
00307
00308
00309 template<typename InputIterator, typename OutputIterator,
00310 typename Predicate>
00311 inline OutputIterator
00312 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
00313 Predicate pred, __gnu_parallel::sequential_tag)
00314 { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out, pred); }
00315
00316
00317 template<typename InputIterator, typename OutputIterator,
00318 typename Predicate, typename IteratorTag1, typename IteratorTag2>
00319 inline OutputIterator
00320 unique_copy_switch(InputIterator begin, InputIterator last,
00321 OutputIterator out, Predicate pred,
00322 IteratorTag1, IteratorTag2)
00323 { return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred); }
00324
00325
00326 template<typename RandomAccessIterator, typename RandomAccessOutputIterator,
00327 typename Predicate>
00328 RandomAccessOutputIterator
00329 unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last,
00330 RandomAccessOutputIterator out, Predicate pred,
00331 random_access_iterator_tag, random_access_iterator_tag)
00332 {
00333 if (_GLIBCXX_PARALLEL_CONDITION(
00334 static_cast<__gnu_parallel::sequence_index_t>(last - begin)
00335 > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
00336 return __gnu_parallel::parallel_unique_copy(begin, last, out, pred);
00337 else
00338 return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
00339 }
00340
00341
00342 template<typename InputIterator, typename OutputIterator>
00343 inline OutputIterator
00344 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out)
00345 {
00346 typedef std::iterator_traits<InputIterator> iteratori_traits;
00347 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00348 typedef typename iteratori_traits::iterator_category iteratori_category;
00349 typedef typename iteratori_traits::value_type value_type;
00350 typedef typename iteratoro_traits::iterator_category iteratoro_category;
00351
00352 return unique_copy_switch(begin1, end1, out, equal_to<value_type>(),
00353 iteratori_category(), iteratoro_category());
00354 }
00355
00356
00357 template<typename InputIterator, typename OutputIterator, typename Predicate>
00358 inline OutputIterator
00359 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
00360 Predicate pred)
00361 {
00362 typedef std::iterator_traits<InputIterator> iteratori_traits;
00363 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00364 typedef typename iteratori_traits::iterator_category iteratori_category;
00365 typedef typename iteratoro_traits::iterator_category iteratoro_category;
00366
00367 return unique_copy_switch(begin1, end1, out, pred, iteratori_category(),
00368 iteratoro_category());
00369 }
00370
00371
00372 template<typename InputIterator1, typename InputIterator2,
00373 typename OutputIterator>
00374 inline OutputIterator
00375 set_union(InputIterator1 begin1, InputIterator1 end1,
00376 InputIterator2 begin2, InputIterator2 end2,
00377 OutputIterator out, __gnu_parallel::sequential_tag)
00378 { return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out); }
00379
00380
00381 template<typename InputIterator1, typename InputIterator2,
00382 typename OutputIterator, typename Predicate>
00383 inline OutputIterator
00384 set_union(InputIterator1 begin1, InputIterator1 end1,
00385 InputIterator2 begin2, InputIterator2 end2,
00386 OutputIterator out, Predicate pred,
00387 __gnu_parallel::sequential_tag)
00388 { return _GLIBCXX_STD_P::set_union(begin1, end1,
00389 begin2, end2, out, pred); }
00390
00391
00392 template<typename InputIterator1, typename InputIterator2,
00393 typename Predicate, typename OutputIterator,
00394 typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
00395 inline OutputIterator
00396 set_union_switch(InputIterator1 begin1, InputIterator1 end1,
00397 InputIterator2 begin2, InputIterator2 end2,
00398 OutputIterator result, Predicate pred, IteratorTag1,
00399 IteratorTag2, IteratorTag3)
00400 { return _GLIBCXX_STD_P::set_union(begin1, end1,
00401 begin2, end2, result, pred); }
00402
00403
00404 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00405 typename OutputRandomAccessIterator, typename Predicate>
00406 OutputRandomAccessIterator
00407 set_union_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
00408 RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
00409 OutputRandomAccessIterator result, Predicate pred,
00410 random_access_iterator_tag, random_access_iterator_tag,
00411 random_access_iterator_tag)
00412 {
00413 if (_GLIBCXX_PARALLEL_CONDITION(
00414 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
00415 >= __gnu_parallel::_Settings::get().set_union_minimal_n
00416 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
00417 >= __gnu_parallel::_Settings::get().set_union_minimal_n))
00418 return __gnu_parallel::parallel_set_union(begin1, end1,
00419 begin2, end2, result, pred);
00420 else
00421 return _GLIBCXX_STD_P::set_union(begin1, end1,
00422 begin2, end2, result, pred);
00423 }
00424
00425
00426 template<typename InputIterator1, typename InputIterator2,
00427 typename OutputIterator>
00428 inline OutputIterator
00429 set_union(InputIterator1 begin1, InputIterator1 end1,
00430 InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
00431 {
00432 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00433 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00434 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00435 typedef typename iteratori1_traits::iterator_category
00436 iteratori1_category;
00437 typedef typename iteratori2_traits::iterator_category
00438 iteratori2_category;
00439 typedef typename iteratoro_traits::iterator_category iteratoro_category;
00440 typedef typename iteratori1_traits::value_type value1_type;
00441 typedef typename iteratori2_traits::value_type value2_type;
00442
00443 return set_union_switch(begin1, end1, begin2, end2, out,
00444 __gnu_parallel::less<value1_type, value2_type>(),
00445 iteratori1_category(), iteratori2_category(),
00446 iteratoro_category());
00447 }
00448
00449
00450 template<typename InputIterator1, typename InputIterator2,
00451 typename OutputIterator, typename Predicate>
00452 inline OutputIterator
00453 set_union(InputIterator1 begin1, InputIterator1 end1,
00454 InputIterator2 begin2, InputIterator2 end2,
00455 OutputIterator out, Predicate pred)
00456 {
00457 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00458 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00459 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00460 typedef typename iteratori1_traits::iterator_category
00461 iteratori1_category;
00462 typedef typename iteratori2_traits::iterator_category
00463 iteratori2_category;
00464 typedef typename iteratoro_traits::iterator_category iteratoro_category;
00465
00466 return set_union_switch(begin1, end1, begin2, end2, out, pred,
00467 iteratori1_category(), iteratori2_category(),
00468 iteratoro_category());
00469 }
00470
00471
00472 template<typename InputIterator1, typename InputIterator2,
00473 typename OutputIterator>
00474 inline OutputIterator
00475 set_intersection(InputIterator1 begin1, InputIterator1 end1,
00476 InputIterator2 begin2, InputIterator2 end2,
00477 OutputIterator out, __gnu_parallel::sequential_tag)
00478 { return _GLIBCXX_STD_P::set_intersection(begin1, end1,
00479 begin2, end2, out); }
00480
00481
00482 template<typename InputIterator1, typename InputIterator2,
00483 typename OutputIterator, typename Predicate>
00484 inline OutputIterator
00485 set_intersection(InputIterator1 begin1, InputIterator1 end1,
00486 InputIterator2 begin2, InputIterator2 end2,
00487 OutputIterator out, Predicate pred,
00488 __gnu_parallel::sequential_tag)
00489 { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2,
00490 out, pred); }
00491
00492
00493 template<typename InputIterator1, typename InputIterator2,
00494 typename Predicate, typename OutputIterator,
00495 typename IteratorTag1, typename IteratorTag2,
00496 typename IteratorTag3>
00497 inline OutputIterator
00498 set_intersection_switch(InputIterator1 begin1, InputIterator1 end1,
00499 InputIterator2 begin2, InputIterator2 end2,
00500 OutputIterator result, Predicate pred,
00501 IteratorTag1, IteratorTag2, IteratorTag3)
00502 { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
00503 end2, result, pred); }
00504
00505
00506 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00507 typename OutputRandomAccessIterator, typename Predicate>
00508 OutputRandomAccessIterator
00509 set_intersection_switch(RandomAccessIterator1 begin1,
00510 RandomAccessIterator1 end1,
00511 RandomAccessIterator2 begin2,
00512 RandomAccessIterator2 end2,
00513 OutputRandomAccessIterator result,
00514 Predicate pred,
00515 random_access_iterator_tag,
00516 random_access_iterator_tag,
00517 random_access_iterator_tag)
00518 {
00519 if (_GLIBCXX_PARALLEL_CONDITION(
00520 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
00521 >= __gnu_parallel::_Settings::get().set_union_minimal_n
00522 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
00523 >= __gnu_parallel::_Settings::get().set_union_minimal_n))
00524 return __gnu_parallel::parallel_set_intersection(begin1, end1, begin2,
00525 end2, result, pred);
00526 else
00527 return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
00528 end2, result, pred);
00529 }
00530
00531
00532 template<typename InputIterator1, typename InputIterator2,
00533 typename OutputIterator>
00534 inline OutputIterator
00535 set_intersection(InputIterator1 begin1, InputIterator1 end1,
00536 InputIterator2 begin2, InputIterator2 end2,
00537 OutputIterator out)
00538 {
00539 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00540 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00541 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00542 typedef typename iteratori1_traits::iterator_category
00543 iteratori1_category;
00544 typedef typename iteratori2_traits::iterator_category
00545 iteratori2_category;
00546 typedef typename iteratoro_traits::iterator_category iteratoro_category;
00547 typedef typename iteratori1_traits::value_type value1_type;
00548 typedef typename iteratori2_traits::value_type value2_type;
00549
00550 return set_intersection_switch(begin1, end1, begin2, end2, out,
00551 __gnu_parallel::
00552 less<value1_type, value2_type>(),
00553 iteratori1_category(),
00554 iteratori2_category(),
00555 iteratoro_category());
00556 }
00557
00558 template<typename InputIterator1, typename InputIterator2,
00559 typename OutputIterator, typename Predicate>
00560 inline OutputIterator
00561 set_intersection(InputIterator1 begin1, InputIterator1 end1,
00562 InputIterator2 begin2, InputIterator2 end2,
00563 OutputIterator out, Predicate pred)
00564 {
00565 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00566 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00567 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00568 typedef typename iteratori1_traits::iterator_category
00569 iteratori1_category;
00570 typedef typename iteratori2_traits::iterator_category
00571 iteratori2_category;
00572 typedef typename iteratoro_traits::iterator_category iteratoro_category;
00573
00574 return set_intersection_switch(begin1, end1, begin2, end2, out, pred,
00575 iteratori1_category(),
00576 iteratori2_category(),
00577 iteratoro_category());
00578 }
00579
00580
00581 template<typename InputIterator1, typename InputIterator2,
00582 typename OutputIterator>
00583 inline OutputIterator
00584 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
00585 InputIterator2 begin2, InputIterator2 end2,
00586 OutputIterator out,
00587 __gnu_parallel::sequential_tag)
00588 { return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1,
00589 begin2, end2, out); }
00590
00591
00592 template<typename InputIterator1, typename InputIterator2,
00593 typename OutputIterator, typename Predicate>
00594 inline OutputIterator
00595 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
00596 InputIterator2 begin2, InputIterator2 end2,
00597 OutputIterator out, Predicate pred,
00598 __gnu_parallel::sequential_tag)
00599 { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2,
00600 end2, out, pred); }
00601
00602
00603 template<typename InputIterator1, typename InputIterator2,
00604 typename Predicate, typename OutputIterator,
00605 typename IteratorTag1, typename IteratorTag2,
00606 typename IteratorTag3>
00607 inline OutputIterator
00608 set_symmetric_difference_switch(InputIterator1 begin1,
00609 InputIterator1 end1,
00610 InputIterator2 begin2,
00611 InputIterator2 end2,
00612 OutputIterator result, Predicate pred,
00613 IteratorTag1, IteratorTag2, IteratorTag3)
00614 { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
00615 begin2, end2,
00616 result, pred); }
00617
00618
00619 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00620 typename OutputRandomAccessIterator, typename Predicate>
00621 OutputRandomAccessIterator
00622 set_symmetric_difference_switch(RandomAccessIterator1 begin1,
00623 RandomAccessIterator1 end1,
00624 RandomAccessIterator2 begin2,
00625 RandomAccessIterator2 end2,
00626 OutputRandomAccessIterator result,
00627 Predicate pred,
00628 random_access_iterator_tag,
00629 random_access_iterator_tag,
00630 random_access_iterator_tag)
00631 {
00632 if (_GLIBCXX_PARALLEL_CONDITION(
00633 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
00634 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
00635 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
00636 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n))
00637 return __gnu_parallel::parallel_set_symmetric_difference(begin1, end1,
00638 begin2, end2,
00639 result, pred);
00640 else
00641 return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
00642 begin2, end2,
00643 result, pred);
00644 }
00645
00646
00647 template<typename InputIterator1, typename InputIterator2,
00648 typename OutputIterator>
00649 inline OutputIterator
00650 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
00651 InputIterator2 begin2, InputIterator2 end2,
00652 OutputIterator out)
00653 {
00654 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00655 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00656 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00657 typedef typename iteratori1_traits::iterator_category
00658 iteratori1_category;
00659 typedef typename iteratori2_traits::iterator_category
00660 iteratori2_category;
00661 typedef typename iteratoro_traits::iterator_category iteratoro_category;
00662 typedef typename iteratori1_traits::value_type value1_type;
00663 typedef typename iteratori2_traits::value_type value2_type;
00664
00665 return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
00666 __gnu_parallel::
00667 less<value1_type, value2_type>(),
00668 iteratori1_category(),
00669 iteratori2_category(),
00670 iteratoro_category());
00671 }
00672
00673
00674 template<typename InputIterator1, typename InputIterator2,
00675 typename OutputIterator, typename Predicate>
00676 inline OutputIterator
00677 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
00678 InputIterator2 begin2, InputIterator2 end2,
00679 OutputIterator out, Predicate pred)
00680 {
00681 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00682 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00683 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00684 typedef typename iteratori1_traits::iterator_category
00685 iteratori1_category;
00686 typedef typename iteratori2_traits::iterator_category
00687 iteratori2_category;
00688 typedef typename iteratoro_traits::iterator_category iteratoro_category;
00689
00690 return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
00691 pred, iteratori1_category(),
00692 iteratori2_category(),
00693 iteratoro_category());
00694 }
00695
00696
00697 template<typename InputIterator1, typename InputIterator2,
00698 typename OutputIterator>
00699 inline OutputIterator
00700 set_difference(InputIterator1 begin1, InputIterator1 end1,
00701 InputIterator2 begin2, InputIterator2 end2,
00702 OutputIterator out, __gnu_parallel::sequential_tag)
00703 { return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out); }
00704
00705
00706 template<typename InputIterator1, typename InputIterator2,
00707 typename OutputIterator, typename Predicate>
00708 inline OutputIterator
00709 set_difference(InputIterator1 begin1, InputIterator1 end1,
00710 InputIterator2 begin2, InputIterator2 end2,
00711 OutputIterator out, Predicate pred,
00712 __gnu_parallel::sequential_tag)
00713 { return _GLIBCXX_STD_P::set_difference(begin1, end1,
00714 begin2, end2, out, pred); }
00715
00716
00717 template<typename InputIterator1, typename InputIterator2,
00718 typename Predicate, typename OutputIterator,
00719 typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
00720 inline OutputIterator
00721 set_difference_switch(InputIterator1 begin1, InputIterator1 end1,
00722 InputIterator2 begin2, InputIterator2 end2,
00723 OutputIterator result, Predicate pred,
00724 IteratorTag1, IteratorTag2, IteratorTag3)
00725 { return _GLIBCXX_STD_P::set_difference(begin1, end1,
00726 begin2, end2, result, pred); }
00727
00728
00729 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00730 typename OutputRandomAccessIterator, typename Predicate>
00731 OutputRandomAccessIterator
00732 set_difference_switch(RandomAccessIterator1 begin1,
00733 RandomAccessIterator1 end1,
00734 RandomAccessIterator2 begin2,
00735 RandomAccessIterator2 end2,
00736 OutputRandomAccessIterator result, Predicate pred,
00737 random_access_iterator_tag,
00738 random_access_iterator_tag,
00739 random_access_iterator_tag)
00740 {
00741 if (_GLIBCXX_PARALLEL_CONDITION(
00742 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
00743 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
00744 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
00745 >= __gnu_parallel::_Settings::get().set_difference_minimal_n))
00746 return __gnu_parallel::parallel_set_difference(begin1, end1,
00747 begin2, end2,
00748 result, pred);
00749 else
00750 return _GLIBCXX_STD_P::set_difference(begin1, end1,
00751 begin2, end2, result, pred);
00752 }
00753
00754
00755 template<typename InputIterator1, typename InputIterator2,
00756 typename OutputIterator>
00757 inline OutputIterator
00758 set_difference(InputIterator1 begin1, InputIterator1 end1,
00759 InputIterator2 begin2, InputIterator2 end2,
00760 OutputIterator out)
00761 {
00762 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00763 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00764 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00765 typedef typename iteratori1_traits::iterator_category
00766 iteratori1_category;
00767 typedef typename iteratori2_traits::iterator_category
00768 iteratori2_category;
00769 typedef typename iteratoro_traits::iterator_category iteratoro_category;
00770 typedef typename iteratori1_traits::value_type value1_type;
00771 typedef typename iteratori2_traits::value_type value2_type;
00772
00773 return set_difference_switch(begin1, end1, begin2, end2, out,
00774 __gnu_parallel::
00775 less<value1_type, value2_type>(),
00776 iteratori1_category(),
00777 iteratori2_category(),
00778 iteratoro_category());
00779 }
00780
00781
00782 template<typename InputIterator1, typename InputIterator2,
00783 typename OutputIterator, typename Predicate>
00784 inline OutputIterator
00785 set_difference(InputIterator1 begin1, InputIterator1 end1,
00786 InputIterator2 begin2, InputIterator2 end2,
00787 OutputIterator out, Predicate pred)
00788 {
00789 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00790 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00791 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00792 typedef typename iteratori1_traits::iterator_category
00793 iteratori1_category;
00794 typedef typename iteratori2_traits::iterator_category
00795 iteratori2_category;
00796 typedef typename iteratoro_traits::iterator_category iteratoro_category;
00797
00798 return set_difference_switch(begin1, end1, begin2, end2, out, pred,
00799 iteratori1_category(),
00800 iteratori2_category(),
00801 iteratoro_category());
00802 }
00803
00804
00805 template<typename ForwardIterator>
00806 inline ForwardIterator
00807 adjacent_find(ForwardIterator begin, ForwardIterator end,
00808 __gnu_parallel::sequential_tag)
00809 { return _GLIBCXX_STD_P::adjacent_find(begin, end); }
00810
00811
00812 template<typename ForwardIterator, typename BinaryPredicate>
00813 inline ForwardIterator
00814 adjacent_find(ForwardIterator begin, ForwardIterator end,
00815 BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
00816 { return _GLIBCXX_STD_P::adjacent_find(begin, end, binary_pred); }
00817
00818
00819 template<typename RandomAccessIterator>
00820 RandomAccessIterator
00821 adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
00822 random_access_iterator_tag)
00823 {
00824 typedef iterator_traits<RandomAccessIterator> traits_type;
00825 typedef typename traits_type::value_type value_type;
00826
00827 if (_GLIBCXX_PARALLEL_CONDITION(true))
00828 {
00829 RandomAccessIterator spot = __gnu_parallel::
00830 find_template(begin, end - 1, begin, equal_to<value_type>(),
00831 __gnu_parallel::adjacent_find_selector()).first;
00832 if (spot == (end - 1))
00833 return end;
00834 else
00835 return spot;
00836 }
00837 else
00838 return adjacent_find(begin, end, __gnu_parallel::sequential_tag());
00839 }
00840
00841
00842 template<typename ForwardIterator, typename IteratorTag>
00843 inline ForwardIterator
00844 adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
00845 IteratorTag)
00846 { return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); }
00847
00848
00849 template<typename ForwardIterator>
00850 inline ForwardIterator
00851 adjacent_find(ForwardIterator begin, ForwardIterator end)
00852 {
00853 typedef iterator_traits<ForwardIterator> traits_type;
00854 typedef typename traits_type::iterator_category iterator_category;
00855 return adjacent_find_switch(begin, end, iterator_category());
00856 }
00857
00858
00859 template<typename ForwardIterator, typename BinaryPredicate,
00860 typename IteratorTag>
00861 inline ForwardIterator
00862 adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
00863 BinaryPredicate pred, IteratorTag)
00864 { return adjacent_find(begin, end, pred,
00865 __gnu_parallel::sequential_tag()); }
00866
00867
00868 template<typename RandomAccessIterator, typename BinaryPredicate>
00869 RandomAccessIterator
00870 adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
00871 BinaryPredicate pred, random_access_iterator_tag)
00872 {
00873 if (_GLIBCXX_PARALLEL_CONDITION(true))
00874 return __gnu_parallel::find_template(begin, end, begin, pred,
00875 __gnu_parallel::
00876 adjacent_find_selector()).first;
00877 else
00878 return adjacent_find(begin, end, pred,
00879 __gnu_parallel::sequential_tag());
00880 }
00881
00882
00883 template<typename ForwardIterator, typename BinaryPredicate>
00884 inline ForwardIterator
00885 adjacent_find(ForwardIterator begin, ForwardIterator end,
00886 BinaryPredicate pred)
00887 {
00888 typedef iterator_traits<ForwardIterator> traits_type;
00889 typedef typename traits_type::iterator_category iterator_category;
00890 return adjacent_find_switch(begin, end, pred, iterator_category());
00891 }
00892
00893
00894 template<typename InputIterator, typename T>
00895 inline typename iterator_traits<InputIterator>::difference_type
00896 count(InputIterator begin, InputIterator end, const T& value,
00897 __gnu_parallel::sequential_tag)
00898 { return _GLIBCXX_STD_P::count(begin, end, value); }
00899
00900
00901 template<typename RandomAccessIterator, typename T>
00902 typename iterator_traits<RandomAccessIterator>::difference_type
00903 count_switch(RandomAccessIterator begin, RandomAccessIterator end,
00904 const T& value, random_access_iterator_tag,
00905 __gnu_parallel::_Parallelism parallelism_tag
00906 = __gnu_parallel::parallel_unbalanced)
00907 {
00908 typedef iterator_traits<RandomAccessIterator> traits_type;
00909 typedef typename traits_type::value_type value_type;
00910 typedef typename traits_type::difference_type difference_type;
00911 typedef __gnu_parallel::sequence_index_t sequence_index_t;
00912
00913 if (_GLIBCXX_PARALLEL_CONDITION(
00914 static_cast<sequence_index_t>(end - begin)
00915 >= __gnu_parallel::_Settings::get().count_minimal_n
00916 && __gnu_parallel::is_parallel(parallelism_tag)))
00917 {
00918 __gnu_parallel::count_selector<RandomAccessIterator, difference_type>
00919 functionality;
00920 difference_type res = 0;
00921 __gnu_parallel::
00922 for_each_template_random_access(begin, end, value,
00923 functionality,
00924 std::plus<sequence_index_t>(),
00925 res, res, -1, parallelism_tag);
00926 return res;
00927 }
00928 else
00929 return count(begin, end, value, __gnu_parallel::sequential_tag());
00930 }
00931
00932
00933 template<typename InputIterator, typename T, typename IteratorTag>
00934 inline typename iterator_traits<InputIterator>::difference_type
00935 count_switch(InputIterator begin, InputIterator end, const T& value,
00936 IteratorTag)
00937 { return count(begin, end, value, __gnu_parallel::sequential_tag()); }
00938
00939
00940 template<typename InputIterator, typename T>
00941 inline typename iterator_traits<InputIterator>::difference_type
00942 count(InputIterator begin, InputIterator end, const T& value,
00943 __gnu_parallel::_Parallelism parallelism_tag)
00944 {
00945 typedef iterator_traits<InputIterator> traits_type;
00946 typedef typename traits_type::iterator_category iterator_category;
00947 return count_switch(begin, end, value, iterator_category(),
00948 parallelism_tag);
00949 }
00950
00951 template<typename InputIterator, typename T>
00952 inline typename iterator_traits<InputIterator>::difference_type
00953 count(InputIterator begin, InputIterator end, const T& value)
00954 {
00955 typedef iterator_traits<InputIterator> traits_type;
00956 typedef typename traits_type::iterator_category iterator_category;
00957 return count_switch(begin, end, value, iterator_category());
00958 }
00959
00960
00961
00962 template<typename InputIterator, typename Predicate>
00963 inline typename iterator_traits<InputIterator>::difference_type
00964 count_if(InputIterator begin, InputIterator end, Predicate pred,
00965 __gnu_parallel::sequential_tag)
00966 { return _GLIBCXX_STD_P::count_if(begin, end, pred); }
00967
00968
00969 template<typename RandomAccessIterator, typename Predicate>
00970 typename iterator_traits<RandomAccessIterator>::difference_type
00971 count_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
00972 Predicate pred, random_access_iterator_tag,
00973 __gnu_parallel::_Parallelism parallelism_tag
00974 = __gnu_parallel::parallel_unbalanced)
00975 {
00976 typedef iterator_traits<RandomAccessIterator> traits_type;
00977 typedef typename traits_type::value_type value_type;
00978 typedef typename traits_type::difference_type difference_type;
00979 typedef __gnu_parallel::sequence_index_t sequence_index_t;
00980
00981 if (_GLIBCXX_PARALLEL_CONDITION(
00982 static_cast<sequence_index_t>(end - begin)
00983 >= __gnu_parallel::_Settings::get().count_minimal_n
00984 && __gnu_parallel::is_parallel(parallelism_tag)))
00985 {
00986 difference_type res = 0;
00987 __gnu_parallel::
00988 count_if_selector<RandomAccessIterator, difference_type>
00989 functionality;
00990 __gnu_parallel::
00991 for_each_template_random_access(begin, end, pred,
00992 functionality,
00993 std::plus<sequence_index_t>(),
00994 res, res, -1, parallelism_tag);
00995 return res;
00996 }
00997 else
00998 return count_if(begin, end, pred, __gnu_parallel::sequential_tag());
00999 }
01000
01001
01002 template<typename InputIterator, typename Predicate, typename IteratorTag>
01003 inline typename iterator_traits<InputIterator>::difference_type
01004 count_if_switch(InputIterator begin, InputIterator end, Predicate pred,
01005 IteratorTag)
01006 { return count_if(begin, end, pred, __gnu_parallel::sequential_tag()); }
01007
01008
01009 template<typename InputIterator, typename Predicate>
01010 inline typename iterator_traits<InputIterator>::difference_type
01011 count_if(InputIterator begin, InputIterator end, Predicate pred,
01012 __gnu_parallel::_Parallelism parallelism_tag)
01013 {
01014 typedef iterator_traits<InputIterator> traits_type;
01015 typedef typename traits_type::iterator_category iterator_category;
01016 return count_if_switch(begin, end, pred, iterator_category(),
01017 parallelism_tag);
01018 }
01019
01020 template<typename InputIterator, typename Predicate>
01021 inline typename iterator_traits<InputIterator>::difference_type
01022 count_if(InputIterator begin, InputIterator end, Predicate pred)
01023 {
01024 typedef iterator_traits<InputIterator> traits_type;
01025 typedef typename traits_type::iterator_category iterator_category;
01026 return count_if_switch(begin, end, pred, iterator_category());
01027 }
01028
01029
01030
01031 template<typename ForwardIterator1, typename ForwardIterator2>
01032 inline ForwardIterator1
01033 search(ForwardIterator1 begin1, ForwardIterator1 end1,
01034 ForwardIterator2 begin2, ForwardIterator2 end2,
01035 __gnu_parallel::sequential_tag)
01036 { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2); }
01037
01038
01039 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
01040 RandomAccessIterator1
01041 search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
01042 RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
01043 random_access_iterator_tag, random_access_iterator_tag)
01044 {
01045 typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits;
01046 typedef typename iterator1_traits::value_type value1_type;
01047 typedef std::iterator_traits<RandomAccessIterator2> iterator2_traits;
01048 typedef typename iterator2_traits::value_type value2_type;
01049
01050 if (_GLIBCXX_PARALLEL_CONDITION(true))
01051 return __gnu_parallel::
01052 search_template(begin1, end1, begin2, end2, __gnu_parallel::
01053 equal_to<value1_type, value2_type>());
01054 else
01055 return search(begin1, end1, begin2, end2,
01056 __gnu_parallel::sequential_tag());
01057 }
01058
01059
01060 template<typename ForwardIterator1, typename ForwardIterator2,
01061 typename IteratorTag1, typename IteratorTag2>
01062 inline ForwardIterator1
01063 search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
01064 ForwardIterator2 begin2, ForwardIterator2 end2,
01065 IteratorTag1, IteratorTag2)
01066 { return search(begin1, end1, begin2, end2,
01067 __gnu_parallel::sequential_tag()); }
01068
01069
01070 template<typename ForwardIterator1, typename ForwardIterator2>
01071 inline ForwardIterator1
01072 search(ForwardIterator1 begin1, ForwardIterator1 end1,
01073 ForwardIterator2 begin2, ForwardIterator2 end2)
01074 {
01075 typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
01076 typedef typename iterator1_traits::iterator_category iterator1_category;
01077 typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
01078 typedef typename iterator2_traits::iterator_category iterator2_category;
01079
01080 return search_switch(begin1, end1, begin2, end2,
01081 iterator1_category(), iterator2_category());
01082 }
01083
01084
01085 template<typename ForwardIterator1, typename ForwardIterator2,
01086 typename BinaryPredicate>
01087 inline ForwardIterator1
01088 search(ForwardIterator1 begin1, ForwardIterator1 end1,
01089 ForwardIterator2 begin2, ForwardIterator2 end2,
01090 BinaryPredicate pred, __gnu_parallel::sequential_tag)
01091 { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred); }
01092
01093
01094 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
01095 typename BinaryPredicate>
01096 RandomAccessIterator1
01097 search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
01098 RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
01099 BinaryPredicate pred,
01100 random_access_iterator_tag, random_access_iterator_tag)
01101 {
01102 if (_GLIBCXX_PARALLEL_CONDITION(true))
01103 return __gnu_parallel::search_template(begin1, end1,
01104 begin2, end2, pred);
01105 else
01106 return search(begin1, end1, begin2, end2, pred,
01107 __gnu_parallel::sequential_tag());
01108 }
01109
01110
01111 template<typename ForwardIterator1, typename ForwardIterator2,
01112 typename BinaryPredicate, typename IteratorTag1,
01113 typename IteratorTag2>
01114 inline ForwardIterator1
01115 search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
01116 ForwardIterator2 begin2, ForwardIterator2 end2,
01117 BinaryPredicate pred, IteratorTag1, IteratorTag2)
01118 { return search(begin1, end1, begin2, end2, pred,
01119 __gnu_parallel::sequential_tag()); }
01120
01121
01122 template<typename ForwardIterator1, typename ForwardIterator2,
01123 typename BinaryPredicate>
01124 inline ForwardIterator1
01125 search(ForwardIterator1 begin1, ForwardIterator1 end1,
01126 ForwardIterator2 begin2, ForwardIterator2 end2,
01127 BinaryPredicate pred)
01128 {
01129 typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
01130 typedef typename iterator1_traits::iterator_category iterator1_category;
01131 typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
01132 typedef typename iterator2_traits::iterator_category iterator2_category;
01133 return search_switch(begin1, end1, begin2, end2, pred,
01134 iterator1_category(), iterator2_category());
01135 }
01136
01137
01138 template<typename ForwardIterator, typename Integer, typename T>
01139 inline ForwardIterator
01140 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
01141 const T& val, __gnu_parallel::sequential_tag)
01142 { return _GLIBCXX_STD_P::search_n(begin, end, count, val); }
01143
01144
01145 template<typename ForwardIterator, typename Integer, typename T,
01146 typename BinaryPredicate>
01147 inline ForwardIterator
01148 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
01149 const T& val, BinaryPredicate binary_pred,
01150 __gnu_parallel::sequential_tag)
01151 { return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred); }
01152
01153
01154 template<typename ForwardIterator, typename Integer, typename T>
01155 inline ForwardIterator
01156 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
01157 const T& val)
01158 {
01159 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
01160 return search_n(begin, end, count, val,
01161 __gnu_parallel::equal_to<value_type, T>());
01162 }
01163
01164
01165 template<typename RandomAccessIterator, typename Integer,
01166 typename T, typename BinaryPredicate>
01167 RandomAccessIterator
01168 search_n_switch(RandomAccessIterator begin, RandomAccessIterator end,
01169 Integer count, const T& val, BinaryPredicate binary_pred,
01170 random_access_iterator_tag)
01171 {
01172 if (_GLIBCXX_PARALLEL_CONDITION(true))
01173 {
01174 __gnu_parallel::pseudo_sequence<T, Integer> ps(val, count);
01175 return __gnu_parallel::search_template(begin, end, ps.begin(),
01176 ps.end(), binary_pred);
01177 }
01178 else
01179 return std::__search_n(begin, end, count, val,
01180 binary_pred, random_access_iterator_tag());
01181 }
01182
01183
01184 template<typename ForwardIterator, typename Integer, typename T,
01185 typename BinaryPredicate, typename IteratorTag>
01186 inline ForwardIterator
01187 search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count,
01188 const T& val, BinaryPredicate binary_pred, IteratorTag)
01189 { return __search_n(begin, end, count, val, binary_pred, IteratorTag()); }
01190
01191
01192 template<typename ForwardIterator, typename Integer, typename T,
01193 typename BinaryPredicate>
01194 inline ForwardIterator
01195 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
01196 const T& val, BinaryPredicate binary_pred)
01197 {
01198 return search_n_switch(begin, end, count, val, binary_pred,
01199 typename std::iterator_traits<ForwardIterator>::
01200 iterator_category());
01201 }
01202
01203
01204
01205 template<typename InputIterator, typename OutputIterator,
01206 typename UnaryOperation>
01207 inline OutputIterator
01208 transform(InputIterator begin, InputIterator end, OutputIterator result,
01209 UnaryOperation unary_op, __gnu_parallel::sequential_tag)
01210 { return _GLIBCXX_STD_P::transform(begin, end, result, unary_op); }
01211
01212
01213 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
01214 typename UnaryOperation>
01215 RandomAccessIterator2
01216 transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
01217 RandomAccessIterator2 result, UnaryOperation unary_op,
01218 random_access_iterator_tag, random_access_iterator_tag,
01219 __gnu_parallel::_Parallelism parallelism_tag
01220 = __gnu_parallel::parallel_balanced)
01221 {
01222 if (_GLIBCXX_PARALLEL_CONDITION(
01223 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01224 >= __gnu_parallel::_Settings::get().transform_minimal_n
01225 && __gnu_parallel::is_parallel(parallelism_tag)))
01226 {
01227 bool dummy = true;
01228 typedef __gnu_parallel::iterator_pair<RandomAccessIterator1,
01229 RandomAccessIterator2, random_access_iterator_tag> ip;
01230 ip begin_pair(begin, result), end_pair(end, result + (end - begin));
01231 __gnu_parallel::transform1_selector<ip> functionality;
01232 __gnu_parallel::
01233 for_each_template_random_access(begin_pair, end_pair,
01234 unary_op, functionality,
01235 __gnu_parallel::dummy_reduct(),
01236 dummy, dummy, -1, parallelism_tag);
01237 return functionality.finish_iterator;
01238 }
01239 else
01240 return transform(begin, end, result, unary_op,
01241 __gnu_parallel::sequential_tag());
01242 }
01243
01244
01245 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
01246 typename UnaryOperation, typename IteratorTag1,
01247 typename IteratorTag2>
01248 inline RandomAccessIterator2
01249 transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
01250 RandomAccessIterator2 result, UnaryOperation unary_op,
01251 IteratorTag1, IteratorTag2)
01252 { return transform(begin, end, result, unary_op,
01253 __gnu_parallel::sequential_tag()); }
01254
01255
01256 template<typename InputIterator, typename OutputIterator,
01257 typename UnaryOperation>
01258 inline OutputIterator
01259 transform(InputIterator begin, InputIterator end, OutputIterator result,
01260 UnaryOperation unary_op,
01261 __gnu_parallel::_Parallelism parallelism_tag)
01262 {
01263 typedef std::iterator_traits<InputIterator> iteratori_traits;
01264 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
01265 typedef typename iteratori_traits::iterator_category iteratori_category;
01266 typedef typename iteratoro_traits::iterator_category iteratoro_category;
01267
01268 return transform1_switch(begin, end, result, unary_op,
01269 iteratori_category(), iteratoro_category(),
01270 parallelism_tag);
01271 }
01272
01273 template<typename InputIterator, typename OutputIterator,
01274 typename UnaryOperation>
01275 inline OutputIterator
01276 transform(InputIterator begin, InputIterator end, OutputIterator result,
01277 UnaryOperation unary_op)
01278 {
01279 typedef std::iterator_traits<InputIterator> iteratori_traits;
01280 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
01281 typedef typename iteratori_traits::iterator_category iteratori_category;
01282 typedef typename iteratoro_traits::iterator_category iteratoro_category;
01283
01284 return transform1_switch(begin, end, result, unary_op,
01285 iteratori_category(), iteratoro_category());
01286 }
01287
01288
01289
01290 template<typename InputIterator1, typename InputIterator2,
01291 typename OutputIterator, typename BinaryOperation>
01292 inline OutputIterator
01293 transform(InputIterator1 begin1, InputIterator1 end1,
01294 InputIterator2 begin2, OutputIterator result,
01295 BinaryOperation binary_op, __gnu_parallel::sequential_tag)
01296 { return _GLIBCXX_STD_P::transform(begin1, end1,
01297 begin2, result, binary_op); }
01298
01299
01300 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
01301 typename RandomAccessIterator3, typename BinaryOperation>
01302 RandomAccessIterator3
01303 transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
01304 RandomAccessIterator2 begin2,
01305 RandomAccessIterator3 result, BinaryOperation binary_op,
01306 random_access_iterator_tag, random_access_iterator_tag,
01307 random_access_iterator_tag,
01308 __gnu_parallel::_Parallelism parallelism_tag
01309 = __gnu_parallel::parallel_balanced)
01310 {
01311 if (_GLIBCXX_PARALLEL_CONDITION(
01312 (end1 - begin1) >= __gnu_parallel::_Settings::get().transform_minimal_n
01313 && __gnu_parallel::is_parallel(parallelism_tag)))
01314 {
01315 bool dummy = true;
01316 typedef __gnu_parallel::iterator_triple<RandomAccessIterator1,
01317 RandomAccessIterator2, RandomAccessIterator3,
01318 random_access_iterator_tag> ip;
01319 ip begin_triple(begin1, begin2, result),
01320 end_triple(end1, begin2 + (end1 - begin1),
01321 result + (end1 - begin1));
01322 __gnu_parallel::transform2_selector<ip> functionality;
01323 __gnu_parallel::
01324 for_each_template_random_access(begin_triple, end_triple,
01325 binary_op, functionality,
01326 __gnu_parallel::dummy_reduct(),
01327 dummy, dummy, -1,
01328 parallelism_tag);
01329 return functionality.finish_iterator;
01330 }
01331 else
01332 return transform(begin1, end1, begin2, result, binary_op,
01333 __gnu_parallel::sequential_tag());
01334 }
01335
01336
01337 template<typename InputIterator1, typename InputIterator2,
01338 typename OutputIterator, typename BinaryOperation,
01339 typename tag1, typename tag2, typename tag3>
01340 inline OutputIterator
01341 transform2_switch(InputIterator1 begin1, InputIterator1 end1,
01342 InputIterator2 begin2, OutputIterator result,
01343 BinaryOperation binary_op, tag1, tag2, tag3)
01344 { return transform(begin1, end1, begin2, result, binary_op,
01345 __gnu_parallel::sequential_tag()); }
01346
01347
01348 template<typename InputIterator1, typename InputIterator2,
01349 typename OutputIterator, typename BinaryOperation>
01350 inline OutputIterator
01351 transform(InputIterator1 begin1, InputIterator1 end1,
01352 InputIterator2 begin2, OutputIterator result,
01353 BinaryOperation binary_op,
01354 __gnu_parallel::_Parallelism parallelism_tag)
01355 {
01356 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
01357 typedef typename iteratori1_traits::iterator_category
01358 iteratori1_category;
01359 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
01360 typedef typename iteratori2_traits::iterator_category
01361 iteratori2_category;
01362 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
01363 typedef typename iteratoro_traits::iterator_category iteratoro_category;
01364
01365 return transform2_switch(begin1, end1, begin2, result, binary_op,
01366 iteratori1_category(), iteratori2_category(),
01367 iteratoro_category(), parallelism_tag);
01368 }
01369
01370 template<typename InputIterator1, typename InputIterator2,
01371 typename OutputIterator, typename BinaryOperation>
01372 inline OutputIterator
01373 transform(InputIterator1 begin1, InputIterator1 end1,
01374 InputIterator2 begin2, OutputIterator result,
01375 BinaryOperation binary_op)
01376 {
01377 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
01378 typedef typename iteratori1_traits::iterator_category
01379 iteratori1_category;
01380 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
01381 typedef typename iteratori2_traits::iterator_category
01382 iteratori2_category;
01383 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
01384 typedef typename iteratoro_traits::iterator_category iteratoro_category;
01385
01386 return transform2_switch(begin1, end1, begin2, result, binary_op,
01387 iteratori1_category(), iteratori2_category(),
01388 iteratoro_category());
01389 }
01390
01391
01392 template<typename ForwardIterator, typename T>
01393 inline void
01394 replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
01395 const T& new_value, __gnu_parallel::sequential_tag)
01396 { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); }
01397
01398
01399 template<typename ForwardIterator, typename T, typename IteratorTag>
01400 inline void
01401 replace_switch(ForwardIterator begin, ForwardIterator end,
01402 const T& old_value, const T& new_value, IteratorTag)
01403 { replace(begin, end, old_value, new_value,
01404 __gnu_parallel::sequential_tag()); }
01405
01406
01407 template<typename RandomAccessIterator, typename T>
01408 inline void
01409 replace_switch(RandomAccessIterator begin, RandomAccessIterator end,
01410 const T& old_value, const T& new_value,
01411 random_access_iterator_tag,
01412 __gnu_parallel::_Parallelism parallelism_tag
01413 = __gnu_parallel::parallel_balanced)
01414 {
01415
01416 replace(begin, end, old_value, new_value,
01417 __gnu_parallel::sequential_tag());
01418 }
01419
01420
01421 template<typename ForwardIterator, typename T>
01422 inline void
01423 replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
01424 const T& new_value, __gnu_parallel::_Parallelism parallelism_tag)
01425 {
01426 typedef iterator_traits<ForwardIterator> traits_type;
01427 typedef typename traits_type::iterator_category iterator_category;
01428 replace_switch(begin, end, old_value, new_value, iterator_category(),
01429 parallelism_tag);
01430 }
01431
01432 template<typename ForwardIterator, typename T>
01433 inline void
01434 replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
01435 const T& new_value)
01436 {
01437 typedef iterator_traits<ForwardIterator> traits_type;
01438 typedef typename traits_type::iterator_category iterator_category;
01439 replace_switch(begin, end, old_value, new_value, iterator_category());
01440 }
01441
01442
01443
01444 template<typename ForwardIterator, typename Predicate, typename T>
01445 inline void
01446 replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred,
01447 const T& new_value, __gnu_parallel::sequential_tag)
01448 { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); }
01449
01450
01451 template<typename ForwardIterator, typename Predicate, typename T,
01452 typename IteratorTag>
01453 inline void
01454 replace_if_switch(ForwardIterator begin, ForwardIterator end,
01455 Predicate pred, const T& new_value, IteratorTag)
01456 { replace_if(begin, end, pred, new_value,
01457 __gnu_parallel::sequential_tag()); }
01458
01459
01460 template<typename RandomAccessIterator, typename Predicate, typename T>
01461 void
01462 replace_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
01463 Predicate pred, const T& new_value,
01464 random_access_iterator_tag,
01465 __gnu_parallel::_Parallelism parallelism_tag
01466 = __gnu_parallel::parallel_balanced)
01467 {
01468 if (_GLIBCXX_PARALLEL_CONDITION(
01469 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01470 >= __gnu_parallel::_Settings::get().replace_minimal_n
01471 && __gnu_parallel::is_parallel(parallelism_tag)))
01472 {
01473 bool dummy;
01474 __gnu_parallel::
01475 replace_if_selector<RandomAccessIterator, Predicate, T>
01476 functionality(new_value);
01477 __gnu_parallel::
01478 for_each_template_random_access(begin, end, pred,
01479 functionality,
01480 __gnu_parallel::dummy_reduct(),
01481 true, dummy, -1, parallelism_tag);
01482 }
01483 else
01484 replace_if(begin, end, pred, new_value,
01485 __gnu_parallel::sequential_tag());
01486 }
01487
01488
01489 template<typename ForwardIterator, typename Predicate, typename T>
01490 inline void
01491 replace_if(ForwardIterator begin, ForwardIterator end,
01492 Predicate pred, const T& new_value,
01493 __gnu_parallel::_Parallelism parallelism_tag)
01494 {
01495 typedef std::iterator_traits<ForwardIterator> iterator_traits;
01496 typedef typename iterator_traits::iterator_category iterator_category;
01497 replace_if_switch(begin, end, pred, new_value, iterator_category(),
01498 parallelism_tag);
01499 }
01500
01501 template<typename ForwardIterator, typename Predicate, typename T>
01502 inline void
01503 replace_if(ForwardIterator begin, ForwardIterator end,
01504 Predicate pred, const T& new_value)
01505 {
01506 typedef std::iterator_traits<ForwardIterator> iterator_traits;
01507 typedef typename iterator_traits::iterator_category iterator_category;
01508 replace_if_switch(begin, end, pred, new_value, iterator_category());
01509 }
01510
01511
01512 template<typename ForwardIterator, typename Generator>
01513 inline void
01514 generate(ForwardIterator begin, ForwardIterator end, Generator gen,
01515 __gnu_parallel::sequential_tag)
01516 { _GLIBCXX_STD_P::generate(begin, end, gen); }
01517
01518
01519 template<typename ForwardIterator, typename Generator, typename IteratorTag>
01520 inline void
01521 generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen,
01522 IteratorTag)
01523 { generate(begin, end, gen, __gnu_parallel::sequential_tag()); }
01524
01525
01526 template<typename RandomAccessIterator, typename Generator>
01527 void
01528 generate_switch(RandomAccessIterator begin, RandomAccessIterator end,
01529 Generator gen, random_access_iterator_tag,
01530 __gnu_parallel::_Parallelism parallelism_tag
01531 = __gnu_parallel::parallel_balanced)
01532 {
01533 if (_GLIBCXX_PARALLEL_CONDITION(
01534 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01535 >= __gnu_parallel::_Settings::get().generate_minimal_n
01536 && __gnu_parallel::is_parallel(parallelism_tag)))
01537 {
01538 bool dummy;
01539 __gnu_parallel::generate_selector<RandomAccessIterator>
01540 functionality;
01541 __gnu_parallel::
01542 for_each_template_random_access(begin, end, gen, functionality,
01543 __gnu_parallel::dummy_reduct(),
01544 true, dummy, -1, parallelism_tag);
01545 }
01546 else
01547 generate(begin, end, gen, __gnu_parallel::sequential_tag());
01548 }
01549
01550
01551 template<typename ForwardIterator, typename Generator>
01552 inline void
01553 generate(ForwardIterator begin, ForwardIterator end,
01554 Generator gen, __gnu_parallel::_Parallelism parallelism_tag)
01555 {
01556 typedef std::iterator_traits<ForwardIterator> iterator_traits;
01557 typedef typename iterator_traits::iterator_category iterator_category;
01558 generate_switch(begin, end, gen, iterator_category(), parallelism_tag);
01559 }
01560
01561 template<typename ForwardIterator, typename Generator>
01562 inline void
01563 generate(ForwardIterator begin, ForwardIterator end, Generator gen)
01564 {
01565 typedef std::iterator_traits<ForwardIterator> iterator_traits;
01566 typedef typename iterator_traits::iterator_category iterator_category;
01567 generate_switch(begin, end, gen, iterator_category());
01568 }
01569
01570
01571
01572 template<typename OutputIterator, typename Size, typename Generator>
01573 inline OutputIterator
01574 generate_n(OutputIterator begin, Size n, Generator gen,
01575 __gnu_parallel::sequential_tag)
01576 { return _GLIBCXX_STD_P::generate_n(begin, n, gen); }
01577
01578
01579 template<typename OutputIterator, typename Size, typename Generator,
01580 typename IteratorTag>
01581 inline OutputIterator
01582 generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag)
01583 { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
01584
01585
01586 template<typename RandomAccessIterator, typename Size, typename Generator>
01587 inline RandomAccessIterator
01588 generate_n_switch(RandomAccessIterator begin, Size n, Generator gen,
01589 random_access_iterator_tag,
01590 __gnu_parallel::_Parallelism parallelism_tag
01591 = __gnu_parallel::parallel_balanced)
01592 {
01593
01594 return generate_n(begin, n, gen, __gnu_parallel::sequential_tag());
01595 }
01596
01597
01598 template<typename OutputIterator, typename Size, typename Generator>
01599 inline OutputIterator
01600 generate_n(OutputIterator begin, Size n, Generator gen,
01601 __gnu_parallel::_Parallelism parallelism_tag)
01602 {
01603 typedef std::iterator_traits<OutputIterator> iterator_traits;
01604 typedef typename iterator_traits::iterator_category iterator_category;
01605 return generate_n_switch(begin, n, gen, iterator_category(),
01606 parallelism_tag);
01607 }
01608
01609 template<typename OutputIterator, typename Size, typename Generator>
01610 inline OutputIterator
01611 generate_n(OutputIterator begin, Size n, Generator gen)
01612 {
01613 typedef std::iterator_traits<OutputIterator> iterator_traits;
01614 typedef typename iterator_traits::iterator_category iterator_category;
01615 return generate_n_switch(begin, n, gen, iterator_category());
01616 }
01617
01618
01619
01620 template<typename RandomAccessIterator>
01621 inline void
01622 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
01623 __gnu_parallel::sequential_tag)
01624 { _GLIBCXX_STD_P::random_shuffle(begin, end); }
01625
01626
01627 template<typename RandomAccessIterator, typename RandomNumberGenerator>
01628 inline void
01629 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
01630 RandomNumberGenerator& rand, __gnu_parallel::sequential_tag)
01631 { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); }
01632
01633
01634
01635 template<typename must_be_int = int>
01636 struct c_rand_number
01637 {
01638 int
01639 operator()(int limit)
01640 { return rand() % limit; }
01641 };
01642
01643
01644 template<typename RandomAccessIterator>
01645 inline void
01646 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end)
01647 {
01648 c_rand_number<> r;
01649
01650 __gnu_parallel::random_shuffle(begin, end, r);
01651 }
01652
01653
01654 template<typename RandomAccessIterator, typename RandomNumberGenerator>
01655 void
01656 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
01657 RandomNumberGenerator& rand)
01658 {
01659 if (begin == end)
01660 return;
01661 if (_GLIBCXX_PARALLEL_CONDITION(
01662 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01663 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
01664 __gnu_parallel::parallel_random_shuffle(begin, end, rand);
01665 else
01666 __gnu_parallel::sequential_random_shuffle(begin, end, rand);
01667 }
01668
01669
01670 template<typename ForwardIterator, typename Predicate>
01671 inline ForwardIterator
01672 partition(ForwardIterator begin, ForwardIterator end,
01673 Predicate pred, __gnu_parallel::sequential_tag)
01674 { return _GLIBCXX_STD_P::partition(begin, end, pred); }
01675
01676
01677 template<typename ForwardIterator, typename Predicate, typename IteratorTag>
01678 inline ForwardIterator
01679 partition_switch(ForwardIterator begin, ForwardIterator end,
01680 Predicate pred, IteratorTag)
01681 { return partition(begin, end, pred, __gnu_parallel::sequential_tag()); }
01682
01683
01684 template<typename RandomAccessIterator, typename Predicate>
01685 RandomAccessIterator
01686 partition_switch(RandomAccessIterator begin, RandomAccessIterator end,
01687 Predicate pred, random_access_iterator_tag)
01688 {
01689 if (_GLIBCXX_PARALLEL_CONDITION(
01690 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01691 >= __gnu_parallel::_Settings::get().partition_minimal_n))
01692 {
01693 typedef typename std::iterator_traits<RandomAccessIterator>::
01694 difference_type difference_type;
01695 difference_type middle = __gnu_parallel::
01696 parallel_partition(begin, end, pred,
01697 __gnu_parallel::get_max_threads());
01698 return begin + middle;
01699 }
01700 else
01701 return partition(begin, end, pred, __gnu_parallel::sequential_tag());
01702 }
01703
01704
01705 template<typename ForwardIterator, typename Predicate>
01706 inline ForwardIterator
01707 partition(ForwardIterator begin, ForwardIterator end, Predicate pred)
01708 {
01709 typedef iterator_traits<ForwardIterator> traits_type;
01710 typedef typename traits_type::iterator_category iterator_category;
01711 return partition_switch(begin, end, pred, iterator_category());
01712 }
01713
01714
01715 template<typename RandomAccessIterator>
01716 inline void
01717 sort(RandomAccessIterator begin, RandomAccessIterator end,
01718 __gnu_parallel::sequential_tag)
01719 { _GLIBCXX_STD_P::sort(begin, end); }
01720
01721
01722 template<typename RandomAccessIterator, typename Comparator>
01723 inline void
01724 sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
01725 __gnu_parallel::sequential_tag)
01726 { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end,
01727 comp); }
01728
01729
01730 template<typename RandomAccessIterator>
01731 inline void
01732 sort(RandomAccessIterator begin, RandomAccessIterator end)
01733 {
01734 typedef iterator_traits<RandomAccessIterator> traits_type;
01735 typedef typename traits_type::value_type value_type;
01736 sort(begin, end, std::less<value_type>());
01737 }
01738
01739 template<typename RandomAccessIterator, typename Comparator>
01740 void
01741 sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
01742 {
01743 typedef iterator_traits<RandomAccessIterator> traits_type;
01744 typedef typename traits_type::value_type value_type;
01745
01746 if (begin != end)
01747 {
01748 if (_GLIBCXX_PARALLEL_CONDITION(
01749 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01750 >= __gnu_parallel::_Settings::get().sort_minimal_n))
01751 __gnu_parallel::parallel_sort(begin, end, comp, false);
01752 else
01753 sort(begin, end, comp, __gnu_parallel::sequential_tag());
01754 }
01755 }
01756
01757
01758 template<typename RandomAccessIterator>
01759 inline void
01760 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01761 __gnu_parallel::sequential_tag)
01762 { return _GLIBCXX_STD_P::stable_sort(begin, end); }
01763
01764
01765 template<typename RandomAccessIterator, typename Comparator>
01766 inline void
01767 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01768 Comparator comp, __gnu_parallel::sequential_tag)
01769 { return _GLIBCXX_STD_P::stable_sort(begin, end, comp); }
01770
01771 template<typename RandomAccessIterator>
01772 inline void
01773 stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
01774 {
01775 typedef iterator_traits<RandomAccessIterator> traits_type;
01776 typedef typename traits_type::value_type value_type;
01777 stable_sort(begin, end, std::less<value_type>());
01778 }
01779
01780
01781 template<typename RandomAccessIterator, typename Comparator>
01782 void
01783 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01784 Comparator comp)
01785 {
01786 if (begin != end)
01787 {
01788 if (_GLIBCXX_PARALLEL_CONDITION(
01789 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01790 >= __gnu_parallel::_Settings::get().sort_minimal_n))
01791 __gnu_parallel::parallel_sort(begin, end, comp, true);
01792 else
01793 stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
01794 }
01795 }
01796
01797
01798 template<typename InputIterator1, typename InputIterator2,
01799 typename OutputIterator>
01800 inline OutputIterator
01801 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
01802 InputIterator2 end2, OutputIterator result,
01803 __gnu_parallel::sequential_tag)
01804 { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result); }
01805
01806
01807 template<typename InputIterator1, typename InputIterator2,
01808 typename OutputIterator, typename Comparator>
01809 inline OutputIterator
01810 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
01811 InputIterator2 end2, OutputIterator result, Comparator comp,
01812 __gnu_parallel::sequential_tag)
01813 { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp); }
01814
01815
01816 template<typename InputIterator1, typename InputIterator2,
01817 typename OutputIterator, typename Comparator,
01818 typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
01819 inline OutputIterator
01820 merge_switch(InputIterator1 begin1, InputIterator1 end1,
01821 InputIterator2 begin2, InputIterator2 end2,
01822 OutputIterator result, Comparator comp,
01823 IteratorTag1, IteratorTag2, IteratorTag3)
01824 { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2,
01825 result, comp); }
01826
01827
01828 template<typename InputIterator1, typename InputIterator2,
01829 typename OutputIterator, typename Comparator>
01830 OutputIterator
01831 merge_switch(InputIterator1 begin1, InputIterator1 end1,
01832 InputIterator2 begin2, InputIterator2 end2,
01833 OutputIterator result, Comparator comp,
01834 random_access_iterator_tag, random_access_iterator_tag,
01835 random_access_iterator_tag)
01836 {
01837 if (_GLIBCXX_PARALLEL_CONDITION(
01838 (static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
01839 >= __gnu_parallel::_Settings::get().merge_minimal_n
01840 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
01841 >= __gnu_parallel::_Settings::get().merge_minimal_n)))
01842 return __gnu_parallel::parallel_merge_advance(begin1, end1,
01843 begin2, end2,
01844 result, (end1 - begin1)
01845 + (end2 - begin2), comp);
01846 else
01847 return __gnu_parallel::merge_advance(begin1, end1, begin2, end2,
01848 result, (end1 - begin1)
01849 + (end2 - begin2), comp);
01850 }
01851
01852
01853 template<typename InputIterator1, typename InputIterator2,
01854 typename OutputIterator, typename Comparator>
01855 inline OutputIterator
01856 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
01857 InputIterator2 end2, OutputIterator result, Comparator comp)
01858 {
01859 typedef typename iterator_traits<InputIterator1>::value_type value_type;
01860
01861 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
01862 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
01863 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
01864 typedef typename iteratori1_traits::iterator_category
01865 iteratori1_category;
01866 typedef typename iteratori2_traits::iterator_category
01867 iteratori2_category;
01868 typedef typename iteratoro_traits::iterator_category iteratoro_category;
01869
01870 return merge_switch(begin1, end1, begin2, end2, result, comp,
01871 iteratori1_category(), iteratori2_category(),
01872 iteratoro_category());
01873 }
01874
01875
01876
01877 template<typename InputIterator1, typename InputIterator2,
01878 typename OutputIterator>
01879 inline OutputIterator
01880 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
01881 InputIterator2 end2, OutputIterator result)
01882 {
01883 typedef std::iterator_traits<InputIterator1> iterator1_traits;
01884 typedef std::iterator_traits<InputIterator2> iterator2_traits;
01885 typedef typename iterator1_traits::value_type value1_type;
01886 typedef typename iterator2_traits::value_type value2_type;
01887
01888 return merge(begin1, end1, begin2, end2, result,
01889 __gnu_parallel::less<value1_type, value2_type>());
01890 }
01891
01892
01893 template<typename RandomAccessIterator>
01894 inline void
01895 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
01896 RandomAccessIterator end, __gnu_parallel::sequential_tag)
01897 { return _GLIBCXX_STD_P::nth_element(begin, nth, end); }
01898
01899
01900 template<typename RandomAccessIterator, typename Comparator>
01901 inline void
01902 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
01903 RandomAccessIterator end, Comparator comp,
01904 __gnu_parallel::sequential_tag)
01905 { return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); }
01906
01907
01908 template<typename RandomAccessIterator, typename Comparator>
01909 inline void
01910 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
01911 RandomAccessIterator end, Comparator comp)
01912 {
01913 if (_GLIBCXX_PARALLEL_CONDITION(
01914 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01915 >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
01916 __gnu_parallel::parallel_nth_element(begin, nth, end, comp);
01917 else
01918 nth_element(begin, nth, end, comp, __gnu_parallel::sequential_tag());
01919 }
01920
01921
01922 template<typename RandomAccessIterator>
01923 inline void
01924 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
01925 RandomAccessIterator end)
01926 {
01927 typedef iterator_traits<RandomAccessIterator> traits_type;
01928 typedef typename traits_type::value_type value_type;
01929 nth_element(begin, nth, end, std::less<value_type>());
01930 }
01931
01932
01933 template<typename RandomAccessIterator, typename _Compare>
01934 inline void
01935 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
01936 RandomAccessIterator end, _Compare comp,
01937 __gnu_parallel::sequential_tag)
01938 { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); }
01939
01940
01941 template<typename RandomAccessIterator>
01942 inline void
01943 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
01944 RandomAccessIterator end, __gnu_parallel::sequential_tag)
01945 { _GLIBCXX_STD_P::partial_sort(begin, middle, end); }
01946
01947
01948 template<typename RandomAccessIterator, typename _Compare>
01949 void
01950 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
01951 RandomAccessIterator end, _Compare comp)
01952 {
01953 if (_GLIBCXX_PARALLEL_CONDITION(
01954 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01955 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
01956 __gnu_parallel::parallel_partial_sort(begin, middle, end, comp);
01957 else
01958 partial_sort(begin, middle, end, comp,
01959 __gnu_parallel::sequential_tag());
01960 }
01961
01962
01963 template<typename RandomAccessIterator>
01964 inline void
01965 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
01966 RandomAccessIterator end)
01967 {
01968 typedef iterator_traits<RandomAccessIterator> traits_type;
01969 typedef typename traits_type::value_type value_type;
01970 partial_sort(begin, middle, end, std::less<value_type>());
01971 }
01972
01973
01974 template<typename ForwardIterator>
01975 inline ForwardIterator
01976 max_element(ForwardIterator begin, ForwardIterator end,
01977 __gnu_parallel::sequential_tag)
01978 { return _GLIBCXX_STD_P::max_element(begin, end); }
01979
01980
01981 template<typename ForwardIterator, typename Comparator>
01982 inline ForwardIterator
01983 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
01984 __gnu_parallel::sequential_tag)
01985 { return _GLIBCXX_STD_P::max_element(begin, end, comp); }
01986
01987
01988 template<typename ForwardIterator, typename Comparator, typename IteratorTag>
01989 inline ForwardIterator
01990 max_element_switch(ForwardIterator begin, ForwardIterator end,
01991 Comparator comp, IteratorTag)
01992 { return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
01993
01994
01995 template<typename RandomAccessIterator, typename Comparator>
01996 RandomAccessIterator
01997 max_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
01998 Comparator comp, random_access_iterator_tag,
01999 __gnu_parallel::_Parallelism parallelism_tag
02000 = __gnu_parallel::parallel_balanced)
02001 {
02002 if (_GLIBCXX_PARALLEL_CONDITION(
02003 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
02004 >= __gnu_parallel::_Settings::get().max_element_minimal_n
02005 && __gnu_parallel::is_parallel(parallelism_tag)))
02006 {
02007 RandomAccessIterator res(begin);
02008 __gnu_parallel::identity_selector<RandomAccessIterator>
02009 functionality;
02010 __gnu_parallel::
02011 for_each_template_random_access(begin, end,
02012 __gnu_parallel::nothing(),
02013 functionality,
02014 __gnu_parallel::
02015 max_element_reduct<Comparator,
02016 RandomAccessIterator>(comp),
02017 res, res, -1, parallelism_tag);
02018 return res;
02019 }
02020 else
02021 return max_element(begin, end, comp, __gnu_parallel::sequential_tag());
02022 }
02023
02024
02025 template<typename ForwardIterator>
02026 inline ForwardIterator
02027 max_element(ForwardIterator begin, ForwardIterator end,
02028 __gnu_parallel::_Parallelism parallelism_tag)
02029 {
02030 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
02031 return max_element(begin, end, std::less<value_type>(), parallelism_tag);
02032 }
02033
02034 template<typename ForwardIterator>
02035 inline ForwardIterator
02036 max_element(ForwardIterator begin, ForwardIterator end)
02037 {
02038 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
02039 return max_element(begin, end, std::less<value_type>());
02040 }
02041
02042
02043 template<typename ForwardIterator, typename Comparator>
02044 inline ForwardIterator
02045 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
02046 __gnu_parallel::_Parallelism parallelism_tag)
02047 {
02048 typedef iterator_traits<ForwardIterator> traits_type;
02049 typedef typename traits_type::iterator_category iterator_category;
02050 return max_element_switch(begin, end, comp, iterator_category(),
02051 parallelism_tag);
02052 }
02053
02054 template<typename ForwardIterator, typename Comparator>
02055 inline ForwardIterator
02056 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
02057 {
02058 typedef iterator_traits<ForwardIterator> traits_type;
02059 typedef typename traits_type::iterator_category iterator_category;
02060 return max_element_switch(begin, end, comp, iterator_category());
02061 }
02062
02063
02064
02065 template<typename ForwardIterator>
02066 inline ForwardIterator
02067 min_element(ForwardIterator begin, ForwardIterator end,
02068 __gnu_parallel::sequential_tag)
02069 { return _GLIBCXX_STD_P::min_element(begin, end); }
02070
02071
02072 template<typename ForwardIterator, typename Comparator>
02073 inline ForwardIterator
02074 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
02075 __gnu_parallel::sequential_tag)
02076 { return _GLIBCXX_STD_P::min_element(begin, end, comp); }
02077
02078
02079 template<typename ForwardIterator, typename Comparator, typename IteratorTag>
02080 inline ForwardIterator
02081 min_element_switch(ForwardIterator begin, ForwardIterator end,
02082 Comparator comp, IteratorTag)
02083 { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
02084
02085
02086 template<typename RandomAccessIterator, typename Comparator>
02087 RandomAccessIterator
02088 min_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
02089 Comparator comp, random_access_iterator_tag,
02090 __gnu_parallel::_Parallelism parallelism_tag
02091 = __gnu_parallel::parallel_balanced)
02092 {
02093 if (_GLIBCXX_PARALLEL_CONDITION(
02094 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
02095 >= __gnu_parallel::_Settings::get().min_element_minimal_n
02096 && __gnu_parallel::is_parallel(parallelism_tag)))
02097 {
02098 RandomAccessIterator res(begin);
02099 __gnu_parallel::identity_selector<RandomAccessIterator>
02100 functionality;
02101 __gnu_parallel::
02102 for_each_template_random_access(begin, end,
02103 __gnu_parallel::nothing(),
02104 functionality,
02105 __gnu_parallel::
02106 min_element_reduct<Comparator,
02107 RandomAccessIterator>(comp),
02108 res, res, -1, parallelism_tag);
02109 return res;
02110 }
02111 else
02112 return min_element(begin, end, comp, __gnu_parallel::sequential_tag());
02113 }
02114
02115
02116 template<typename ForwardIterator>
02117 inline ForwardIterator
02118 min_element(ForwardIterator begin, ForwardIterator end,
02119 __gnu_parallel::_Parallelism parallelism_tag)
02120 {
02121 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
02122 return min_element(begin, end, std::less<value_type>(), parallelism_tag);
02123 }
02124
02125 template<typename ForwardIterator>
02126 inline ForwardIterator
02127 min_element(ForwardIterator begin, ForwardIterator end)
02128 {
02129 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
02130 return min_element(begin, end, std::less<value_type>());
02131 }
02132
02133
02134 template<typename ForwardIterator, typename Comparator>
02135 inline ForwardIterator
02136 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
02137 __gnu_parallel::_Parallelism parallelism_tag)
02138 {
02139 typedef iterator_traits<ForwardIterator> traits_type;
02140 typedef typename traits_type::iterator_category iterator_category;
02141 return min_element_switch(begin, end, comp, iterator_category(),
02142 parallelism_tag);
02143 }
02144
02145 template<typename ForwardIterator, typename Comparator>
02146 inline ForwardIterator
02147 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
02148 {
02149 typedef iterator_traits<ForwardIterator> traits_type;
02150 typedef typename traits_type::iterator_category iterator_category;
02151 return min_element_switch(begin, end, comp, iterator_category());
02152 }
02153 }
02154 }
02155
02156 #endif