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