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