?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge from trunk @ 138209
[official-gcc.git] / libstdc++-v3 / include / parallel / algo.h
blob23e7bdcbabce7a7aff606d8aa56d695212602586
1 // -*- C++ -*-
2
3 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 2, or (at your option) any later
9 // version.
10
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
20
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
29 // Public License.
30
31 /** @file parallel/algo.h
32 * @brief Parallel STL function calls corresponding to the stl_algo.h header.
33 *
34 * The functions defined here mainly do case switches and
35 * call the actual parallelized versions in other files.
36 * Inlining policy: Functions that basically only contain one function call,
37 * are declared inline.
38 * This file is a GNU parallel extension to the Standard C++ Library.
39 */
40
41 // Written by Johannes Singler and Felix Putze.
42
43 #ifndef _GLIBCXX_PARALLEL_ALGO_H
44 #define _GLIBCXX_PARALLEL_ALGO_H 1
45
46 #include <parallel/algorithmfwd.h>
47 #include <bits/stl_algobase.h>
48 #include <bits/stl_algo.h>
49 #include <parallel/iterator.h>
50 #include <parallel/base.h>
51 #include <parallel/sort.h>
52 #include <parallel/workstealing.h>
53 #include <parallel/par_loop.h>
54 #include <parallel/omp_loop.h>
55 #include <parallel/omp_loop_static.h>
56 #include <parallel/for_each_selectors.h>
57 #include <parallel/for_each.h>
58 #include <parallel/find.h>
59 #include <parallel/find_selectors.h>
60 #include <parallel/search.h>
61 #include <parallel/random_shuffle.h>
62 #include <parallel/partition.h>
63 #include <parallel/merge.h>
64 #include <parallel/unique_copy.h>
65 #include <parallel/set_operations.h>
66
67 namespace std
68 {
69 namespace __parallel
70 {
71 // Sequential fallback
72 template<typename InputIterator, typename Function>
73 inline Function
74 for_each(InputIterator begin, InputIterator end, Function f,
75 __gnu_parallel::sequential_tag)
76 { return _GLIBCXX_STD_P::for_each(begin, end, f); }
77
78
79 // Sequential fallback for input iterator case
80 template<typename InputIterator, typename Function, typename IteratorTag>
81 inline Function
82 for_each_switch(InputIterator begin, InputIterator end, Function f,
83 IteratorTag)
84 { return for_each(begin, end, f, __gnu_parallel::sequential_tag()); }
85
86 // Parallel algorithm for random access iterators
87 template<typename RandomAccessIterator, typename Function>
88 Function
89 for_each_switch(RandomAccessIterator begin, RandomAccessIterator end,
90 Function f, random_access_iterator_tag,
91 __gnu_parallel::_Parallelism parallelism_tag
92 = __gnu_parallel::parallel_balanced)
93 {
94 if (_GLIBCXX_PARALLEL_CONDITION(
95 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
96 >= __gnu_parallel::_Settings::get().for_each_minimal_n
97 && __gnu_parallel::is_parallel(parallelism_tag)))
98 {
99 bool dummy;
100 __gnu_parallel::for_each_selector<RandomAccessIterator> functionality;
101
102 return __gnu_parallel::
103 for_each_template_random_access(begin, end, f, functionality,
104 __gnu_parallel::dummy_reduct(),
105 true, dummy, -1, parallelism_tag);
106 }
107 else
108 return for_each(begin, end, f, __gnu_parallel::sequential_tag());
109 }
110
111 // Public interface
112 template<typename Iterator, typename Function>
113 inline Function
114 for_each(Iterator begin, Iterator end, Function f,
115 __gnu_parallel::_Parallelism parallelism_tag)
116 {
117 typedef std::iterator_traits<Iterator> iterator_traits;
118 typedef typename iterator_traits::iterator_category iterator_category;
119 return for_each_switch(begin, end, f, iterator_category(),
120 parallelism_tag);
121 }
122
123 template<typename Iterator, typename Function>
124 inline Function
125 for_each(Iterator begin, Iterator end, Function f)
126 {
127 typedef std::iterator_traits<Iterator> iterator_traits;
128 typedef typename iterator_traits::iterator_category iterator_category;
129 return for_each_switch(begin, end, f, iterator_category());
130 }
131
132
133 // Sequential fallback
134 template<typename InputIterator, typename T>
135 inline InputIterator
136 find(InputIterator begin, InputIterator end, const T& val,
137 __gnu_parallel::sequential_tag)
138 { return _GLIBCXX_STD_P::find(begin, end, val); }
139
140 // Sequential fallback for input iterator case
141 template<typename InputIterator, typename T, typename IteratorTag>
142 inline InputIterator
143 find_switch(InputIterator begin, InputIterator end, const T& val,
144 IteratorTag)
145 { return _GLIBCXX_STD_P::find(begin, end, val); }
146
147 // Parallel find for random access iterators
148 template<typename RandomAccessIterator, typename T>
149 RandomAccessIterator
150 find_switch(RandomAccessIterator begin, RandomAccessIterator end,
151 const T& val, random_access_iterator_tag)
152 {
153 typedef iterator_traits<RandomAccessIterator> traits_type;
154 typedef typename traits_type::value_type value_type;
155
156 if (_GLIBCXX_PARALLEL_CONDITION(true))
157 {
158 binder2nd<__gnu_parallel::equal_to<value_type, T> >
159 comp(__gnu_parallel::equal_to<value_type, T>(), val);
160 return __gnu_parallel::find_template(begin, end, begin, comp,
161 __gnu_parallel::
162 find_if_selector()).first;
163 }
164 else
165 return _GLIBCXX_STD_P::find(begin, end, val);
166 }
167
168 // Public interface
169 template<typename InputIterator, typename T>
170 inline InputIterator
171 find(InputIterator begin, InputIterator end, const T& val)
172 {
173 typedef std::iterator_traits<InputIterator> iterator_traits;
174 typedef typename iterator_traits::iterator_category iterator_category;
175 return find_switch(begin, end, val, iterator_category());
176 }
177
178 // Sequential fallback
179 template<typename InputIterator, typename Predicate>
180 inline InputIterator
181 find_if(InputIterator begin, InputIterator end, Predicate pred,
182 __gnu_parallel::sequential_tag)
183 { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
184
185 // Sequential fallback for input iterator case
186 template<typename InputIterator, typename Predicate, typename IteratorTag>
187 inline InputIterator
188 find_if_switch(InputIterator begin, InputIterator end, Predicate pred,
189 IteratorTag)
190 { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
191
192 // Parallel find_if for random access iterators
193 template<typename RandomAccessIterator, typename Predicate>
194 RandomAccessIterator
195 find_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
196 Predicate pred, random_access_iterator_tag)
197 {
198 if (_GLIBCXX_PARALLEL_CONDITION(true))
199 return __gnu_parallel::find_template(begin, end, begin, pred,
200 __gnu_parallel::
201 find_if_selector()).first;
202 else
203 return _GLIBCXX_STD_P::find_if(begin, end, pred);
204 }
205
206 // Public interface
207 template<typename InputIterator, typename Predicate>
208 inline InputIterator
209 find_if(InputIterator begin, InputIterator end, Predicate pred)
210 {
211 typedef std::iterator_traits<InputIterator> iterator_traits;
212 typedef typename iterator_traits::iterator_category iterator_category;
213 return find_if_switch(begin, end, pred, iterator_category());
214 }
215
216 // Sequential fallback
217 template<typename InputIterator, typename ForwardIterator>
218 inline InputIterator
219 find_first_of(InputIterator begin1, InputIterator end1,
220 ForwardIterator begin2, ForwardIterator end2,
221 __gnu_parallel::sequential_tag)
222 { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2); }
223
224 // Sequential fallback
225 template<typename InputIterator, typename ForwardIterator,
226 typename BinaryPredicate>
227 inline InputIterator
228 find_first_of(InputIterator begin1, InputIterator end1,
229 ForwardIterator begin2, ForwardIterator end2,
230 BinaryPredicate comp, __gnu_parallel::sequential_tag)
231 { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2, comp); }
232
233 // Sequential fallback for input iterator type
234 template<typename InputIterator, typename ForwardIterator,
235 typename IteratorTag1, typename IteratorTag2>
236 inline InputIterator
237 find_first_of_switch(InputIterator begin1, InputIterator end1,
238 ForwardIterator begin2, ForwardIterator end2,
239 IteratorTag1, IteratorTag2)
240 { return find_first_of(begin1, end1, begin2, end2,
241 __gnu_parallel::sequential_tag()); }
242
243 // Parallel algorithm for random access iterators
244 template<typename RandomAccessIterator, typename ForwardIterator,
245 typename BinaryPredicate, typename IteratorTag>
246 inline RandomAccessIterator
247 find_first_of_switch(RandomAccessIterator begin1,
248 RandomAccessIterator end1,
249 ForwardIterator begin2, ForwardIterator end2,
250 BinaryPredicate comp, random_access_iterator_tag,
251 IteratorTag)
252 {
253 return __gnu_parallel::
254 find_template(begin1, end1, begin1, comp,
255 __gnu_parallel::find_first_of_selector
256 <ForwardIterator>(begin2, end2)).first;
257 }
258
259 // Sequential fallback for input iterator type
260 template<typename InputIterator, typename ForwardIterator,
261 typename BinaryPredicate, typename IteratorTag1,
262 typename IteratorTag2>
263 inline InputIterator
264 find_first_of_switch(InputIterator begin1, InputIterator end1,
265 ForwardIterator begin2, ForwardIterator end2,
266 BinaryPredicate comp, IteratorTag1, IteratorTag2)
267 { return find_first_of(begin1, end1, begin2, end2, comp,
268 __gnu_parallel::sequential_tag()); }
269
270 // Public interface
271 template<typename InputIterator, typename ForwardIterator,
272 typename BinaryPredicate>
273 inline InputIterator
274 find_first_of(InputIterator begin1, InputIterator end1,
275 ForwardIterator begin2, ForwardIterator end2,
276 BinaryPredicate comp)
277 {
278 typedef std::iterator_traits<InputIterator> iteratori_traits;
279 typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
280 typedef typename iteratori_traits::iterator_category iteratori_category;
281 typedef typename iteratorf_traits::iterator_category iteratorf_category;
282
283 return find_first_of_switch(begin1, end1, begin2, end2, comp,
284 iteratori_category(), iteratorf_category());
285 }
286
287 // Public interface, insert default comparator
288 template<typename InputIterator, typename ForwardIterator>
289 inline InputIterator
290 find_first_of(InputIterator begin1, InputIterator end1,
291 ForwardIterator begin2, ForwardIterator end2)
292 {
293 typedef std::iterator_traits<InputIterator> iteratori_traits;
294 typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
295 typedef typename iteratori_traits::value_type valuei_type;
296 typedef typename iteratorf_traits::value_type valuef_type;
297
298 return find_first_of(begin1, end1, begin2, end2, __gnu_parallel::
299 equal_to<valuei_type, valuef_type>());
300 }
301
302 // Sequential fallback
303 template<typename InputIterator, typename OutputIterator>
304 inline OutputIterator
305 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
306 __gnu_parallel::sequential_tag)
307 { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out); }
308
309 // Sequential fallback
310 template<typename InputIterator, typename OutputIterator,
311 typename Predicate>
312 inline OutputIterator
313 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
314 Predicate pred, __gnu_parallel::sequential_tag)
315 { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out, pred); }
316
317 // Sequential fallback for input iterator case
318 template<typename InputIterator, typename OutputIterator,
319 typename Predicate, typename IteratorTag1, typename IteratorTag2>
320 inline OutputIterator
321 unique_copy_switch(InputIterator begin, InputIterator last,
322 OutputIterator out, Predicate pred,
323 IteratorTag1, IteratorTag2)
324 { return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred); }
325
326 // Parallel unique_copy for random access iterators
327 template<typename RandomAccessIterator, typename RandomAccessOutputIterator,
328 typename Predicate>
329 RandomAccessOutputIterator
330 unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last,
331 RandomAccessOutputIterator out, Predicate pred,
332 random_access_iterator_tag, random_access_iterator_tag)
333 {
334 if (_GLIBCXX_PARALLEL_CONDITION(
335 static_cast<__gnu_parallel::sequence_index_t>(last - begin)
336 > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
337 return __gnu_parallel::parallel_unique_copy(begin, last, out, pred);
338 else
339 return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
340 }
341
342 // Public interface
343 template<typename InputIterator, typename OutputIterator>
344 inline OutputIterator
345 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out)
346 {
347 typedef std::iterator_traits<InputIterator> iteratori_traits;
348 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
349 typedef typename iteratori_traits::iterator_category iteratori_category;
350 typedef typename iteratori_traits::value_type value_type;
351 typedef typename iteratoro_traits::iterator_category iteratoro_category;
352
353 return unique_copy_switch(begin1, end1, out, equal_to<value_type>(),
354 iteratori_category(), iteratoro_category());
355 }
356
357 // Public interface
358 template<typename InputIterator, typename OutputIterator, typename Predicate>
359 inline OutputIterator
360 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
361 Predicate pred)
362 {
363 typedef std::iterator_traits<InputIterator> iteratori_traits;
364 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
365 typedef typename iteratori_traits::iterator_category iteratori_category;
366 typedef typename iteratoro_traits::iterator_category iteratoro_category;
367
368 return unique_copy_switch(begin1, end1, out, pred, iteratori_category(),
369 iteratoro_category());
370 }
371
372 // Sequential fallback
373 template<typename InputIterator1, typename InputIterator2,
374 typename OutputIterator>
375 inline OutputIterator
376 set_union(InputIterator1 begin1, InputIterator1 end1,
377 InputIterator2 begin2, InputIterator2 end2,
378 OutputIterator out, __gnu_parallel::sequential_tag)
379 { return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out); }
380
381 // Sequential fallback
382 template<typename InputIterator1, typename InputIterator2,
383 typename OutputIterator, typename Predicate>
384 inline OutputIterator
385 set_union(InputIterator1 begin1, InputIterator1 end1,
386 InputIterator2 begin2, InputIterator2 end2,
387 OutputIterator out, Predicate pred,
388 __gnu_parallel::sequential_tag)
389 { return _GLIBCXX_STD_P::set_union(begin1, end1,
390 begin2, end2, out, pred); }
391
392 // Sequential fallback for input iterator case
393 template<typename InputIterator1, typename InputIterator2,
394 typename Predicate, typename OutputIterator,
395 typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
396 inline OutputIterator
397 set_union_switch(InputIterator1 begin1, InputIterator1 end1,
398 InputIterator2 begin2, InputIterator2 end2,
399 OutputIterator result, Predicate pred, IteratorTag1,
400 IteratorTag2, IteratorTag3)
401 { return _GLIBCXX_STD_P::set_union(begin1, end1,
402 begin2, end2, result, pred); }
403
404 // Parallel set_union for random access iterators
405 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
406 typename OutputRandomAccessIterator, typename Predicate>
407 OutputRandomAccessIterator
408 set_union_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
409 RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
410 OutputRandomAccessIterator result, Predicate pred,
411 random_access_iterator_tag, random_access_iterator_tag,
412 random_access_iterator_tag)
413 {
414 if (_GLIBCXX_PARALLEL_CONDITION(
415 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
416 >= __gnu_parallel::_Settings::get().set_union_minimal_n
417 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
418 >= __gnu_parallel::_Settings::get().set_union_minimal_n))
419 return __gnu_parallel::parallel_set_union(begin1, end1,
420 begin2, end2, result, pred);
421 else
422 return _GLIBCXX_STD_P::set_union(begin1, end1,
423 begin2, end2, result, pred);
424 }
425
426 // Public interface
427 template<typename InputIterator1, typename InputIterator2,
428 typename OutputIterator>
429 inline OutputIterator
430 set_union(InputIterator1 begin1, InputIterator1 end1,
431 InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
432 {
433 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
434 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
435 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
436 typedef typename iteratori1_traits::iterator_category
437 iteratori1_category;
438 typedef typename iteratori2_traits::iterator_category
439 iteratori2_category;
440 typedef typename iteratoro_traits::iterator_category iteratoro_category;
441 typedef typename iteratori1_traits::value_type value1_type;
442 typedef typename iteratori2_traits::value_type value2_type;
443
444 return set_union_switch(begin1, end1, begin2, end2, out,
445 __gnu_parallel::less<value1_type, value2_type>(),
446 iteratori1_category(), iteratori2_category(),
447 iteratoro_category());
448 }
449
450 // Public interface
451 template<typename InputIterator1, typename InputIterator2,
452 typename OutputIterator, typename Predicate>
453 inline OutputIterator
454 set_union(InputIterator1 begin1, InputIterator1 end1,
455 InputIterator2 begin2, InputIterator2 end2,
456 OutputIterator out, Predicate pred)
457 {
458 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
459 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
460 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
461 typedef typename iteratori1_traits::iterator_category
462 iteratori1_category;
463 typedef typename iteratori2_traits::iterator_category
464 iteratori2_category;
465 typedef typename iteratoro_traits::iterator_category iteratoro_category;
466
467 return set_union_switch(begin1, end1, begin2, end2, out, pred,
468 iteratori1_category(), iteratori2_category(),
469 iteratoro_category());
470 }
471
472 // Sequential fallback.
473 template<typename InputIterator1, typename InputIterator2,
474 typename OutputIterator>
475 inline OutputIterator
476 set_intersection(InputIterator1 begin1, InputIterator1 end1,
477 InputIterator2 begin2, InputIterator2 end2,
478 OutputIterator out, __gnu_parallel::sequential_tag)
479 { return _GLIBCXX_STD_P::set_intersection(begin1, end1,
480 begin2, end2, out); }
481
482 // Sequential fallback.
483 template<typename InputIterator1, typename InputIterator2,
484 typename OutputIterator, typename Predicate>
485 inline OutputIterator
486 set_intersection(InputIterator1 begin1, InputIterator1 end1,
487 InputIterator2 begin2, InputIterator2 end2,
488 OutputIterator out, Predicate pred,
489 __gnu_parallel::sequential_tag)
490 { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2,
491 out, pred); }
492
493 // Sequential fallback for input iterator case
494 template<typename InputIterator1, typename InputIterator2,
495 typename Predicate, typename OutputIterator,
496 typename IteratorTag1, typename IteratorTag2,
497 typename IteratorTag3>
498 inline OutputIterator
499 set_intersection_switch(InputIterator1 begin1, InputIterator1 end1,
500 InputIterator2 begin2, InputIterator2 end2,
501 OutputIterator result, Predicate pred,
502 IteratorTag1, IteratorTag2, IteratorTag3)
503 { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
504 end2, result, pred); }
505
506 // Parallel set_intersection for random access iterators
507 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
508 typename OutputRandomAccessIterator, typename Predicate>
509 OutputRandomAccessIterator
510 set_intersection_switch(RandomAccessIterator1 begin1,
511 RandomAccessIterator1 end1,
512 RandomAccessIterator2 begin2,
513 RandomAccessIterator2 end2,
514 OutputRandomAccessIterator result,
515 Predicate pred,
516 random_access_iterator_tag,
517 random_access_iterator_tag,
518 random_access_iterator_tag)
519 {
520 if (_GLIBCXX_PARALLEL_CONDITION(
521 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
522 >= __gnu_parallel::_Settings::get().set_union_minimal_n
523 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
524 >= __gnu_parallel::_Settings::get().set_union_minimal_n))
525 return __gnu_parallel::parallel_set_intersection(begin1, end1, begin2,
526 end2, result, pred);
527 else
528 return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
529 end2, result, pred);
530 }
531
532 // Public interface
533 template<typename InputIterator1, typename InputIterator2,
534 typename OutputIterator>
535 inline OutputIterator
536 set_intersection(InputIterator1 begin1, InputIterator1 end1,
537 InputIterator2 begin2, InputIterator2 end2,
538 OutputIterator out)
539 {
540 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
541 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
542 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
543 typedef typename iteratori1_traits::iterator_category
544 iteratori1_category;
545 typedef typename iteratori2_traits::iterator_category
546 iteratori2_category;
547 typedef typename iteratoro_traits::iterator_category iteratoro_category;
548 typedef typename iteratori1_traits::value_type value1_type;
549 typedef typename iteratori2_traits::value_type value2_type;
550
551 return set_intersection_switch(begin1, end1, begin2, end2, out,
552 __gnu_parallel::
553 less<value1_type, value2_type>(),
554 iteratori1_category(),
555 iteratori2_category(),
556 iteratoro_category());
557 }
558
559 template<typename InputIterator1, typename InputIterator2,
560 typename OutputIterator, typename Predicate>
561 inline OutputIterator
562 set_intersection(InputIterator1 begin1, InputIterator1 end1,
563 InputIterator2 begin2, InputIterator2 end2,
564 OutputIterator out, Predicate pred)
565 {
566 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
567 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
568 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
569 typedef typename iteratori1_traits::iterator_category
570 iteratori1_category;
571 typedef typename iteratori2_traits::iterator_category
572 iteratori2_category;
573 typedef typename iteratoro_traits::iterator_category iteratoro_category;
574
575 return set_intersection_switch(begin1, end1, begin2, end2, out, pred,
576 iteratori1_category(),
577 iteratori2_category(),
578 iteratoro_category());
579 }
580
581 // Sequential fallback
582 template<typename InputIterator1, typename InputIterator2,
583 typename OutputIterator>
584 inline OutputIterator
585 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
586 InputIterator2 begin2, InputIterator2 end2,
587 OutputIterator out,
588 __gnu_parallel::sequential_tag)
589 { return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1,
590 begin2, end2, out); }
591
592 // Sequential fallback
593 template<typename InputIterator1, typename InputIterator2,
594 typename OutputIterator, typename Predicate>
595 inline OutputIterator
596 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
597 InputIterator2 begin2, InputIterator2 end2,
598 OutputIterator out, Predicate pred,
599 __gnu_parallel::sequential_tag)
600 { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2,
601 end2, out, pred); }
602
603 // Sequential fallback for input iterator case
604 template<typename InputIterator1, typename InputIterator2,
605 typename Predicate, typename OutputIterator,
606 typename IteratorTag1, typename IteratorTag2,
607 typename IteratorTag3>
608 inline OutputIterator
609 set_symmetric_difference_switch(InputIterator1 begin1,
610 InputIterator1 end1,
611 InputIterator2 begin2,
612 InputIterator2 end2,
613 OutputIterator result, Predicate pred,
614 IteratorTag1, IteratorTag2, IteratorTag3)
615 { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
616 begin2, end2,
617 result, pred); }
618
619 // Parallel set_symmetric_difference for random access iterators
620 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
621 typename OutputRandomAccessIterator, typename Predicate>
622 OutputRandomAccessIterator
623 set_symmetric_difference_switch(RandomAccessIterator1 begin1,
624 RandomAccessIterator1 end1,
625 RandomAccessIterator2 begin2,
626 RandomAccessIterator2 end2,
627 OutputRandomAccessIterator result,
628 Predicate pred,
629 random_access_iterator_tag,
630 random_access_iterator_tag,
631 random_access_iterator_tag)
632 {
633 if (_GLIBCXX_PARALLEL_CONDITION(
634 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
635 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
636 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
637 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n))
638 return __gnu_parallel::parallel_set_symmetric_difference(begin1, end1,
639 begin2, end2,
640 result, pred);
641 else
642 return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
643 begin2, end2,
644 result, pred);
645 }
646
647 // Public interface.
648 template<typename InputIterator1, typename InputIterator2,
649 typename OutputIterator>
650 inline OutputIterator
651 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
652 InputIterator2 begin2, InputIterator2 end2,
653 OutputIterator out)
654 {
655 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
656 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
657 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
658 typedef typename iteratori1_traits::iterator_category
659 iteratori1_category;
660 typedef typename iteratori2_traits::iterator_category
661 iteratori2_category;
662 typedef typename iteratoro_traits::iterator_category iteratoro_category;
663 typedef typename iteratori1_traits::value_type value1_type;
664 typedef typename iteratori2_traits::value_type value2_type;
665
666 return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
667 __gnu_parallel::
668 less<value1_type, value2_type>(),
669 iteratori1_category(),
670 iteratori2_category(),
671 iteratoro_category());
672 }
673
674 // Public interface.
675 template<typename InputIterator1, typename InputIterator2,
676 typename OutputIterator, typename Predicate>
677 inline OutputIterator
678 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
679 InputIterator2 begin2, InputIterator2 end2,
680 OutputIterator out, Predicate pred)
681 {
682 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
683 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
684 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
685 typedef typename iteratori1_traits::iterator_category
686 iteratori1_category;
687 typedef typename iteratori2_traits::iterator_category
688 iteratori2_category;
689 typedef typename iteratoro_traits::iterator_category iteratoro_category;
690
691 return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
692 pred, iteratori1_category(),
693 iteratori2_category(),
694 iteratoro_category());
695 }
696
697 // Sequential fallback.
698 template<typename InputIterator1, typename InputIterator2,
699 typename OutputIterator>
700 inline OutputIterator
701 set_difference(InputIterator1 begin1, InputIterator1 end1,
702 InputIterator2 begin2, InputIterator2 end2,
703 OutputIterator out, __gnu_parallel::sequential_tag)
704 { return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out); }
705
706 // Sequential fallback.
707 template<typename InputIterator1, typename InputIterator2,
708 typename OutputIterator, typename Predicate>
709 inline OutputIterator
710 set_difference(InputIterator1 begin1, InputIterator1 end1,
711 InputIterator2 begin2, InputIterator2 end2,
712 OutputIterator out, Predicate pred,
713 __gnu_parallel::sequential_tag)
714 { return _GLIBCXX_STD_P::set_difference(begin1, end1,
715 begin2, end2, out, pred); }
716
717 // Sequential fallback for input iterator case.
718 template<typename InputIterator1, typename InputIterator2,
719 typename Predicate, typename OutputIterator,
720 typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
721 inline OutputIterator
722 set_difference_switch(InputIterator1 begin1, InputIterator1 end1,
723 InputIterator2 begin2, InputIterator2 end2,
724 OutputIterator result, Predicate pred,
725 IteratorTag1, IteratorTag2, IteratorTag3)
726 { return _GLIBCXX_STD_P::set_difference(begin1, end1,
727 begin2, end2, result, pred); }
728
729 // Parallel set_difference for random access iterators
730 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
731 typename OutputRandomAccessIterator, typename Predicate>
732 OutputRandomAccessIterator
733 set_difference_switch(RandomAccessIterator1 begin1,
734 RandomAccessIterator1 end1,
735 RandomAccessIterator2 begin2,
736 RandomAccessIterator2 end2,
737 OutputRandomAccessIterator result, Predicate pred,
738 random_access_iterator_tag,
739 random_access_iterator_tag,
740 random_access_iterator_tag)
741 {
742 if (_GLIBCXX_PARALLEL_CONDITION(
743 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
744 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
745 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
746 >= __gnu_parallel::_Settings::get().set_difference_minimal_n))
747 return __gnu_parallel::parallel_set_difference(begin1, end1,
748 begin2, end2,
749 result, pred);
750 else
751 return _GLIBCXX_STD_P::set_difference(begin1, end1,
752 begin2, end2, result, pred);
753 }
754
755 // Public interface
756 template<typename InputIterator1, typename InputIterator2,
757 typename OutputIterator>
758 inline OutputIterator
759 set_difference(InputIterator1 begin1, InputIterator1 end1,
760 InputIterator2 begin2, InputIterator2 end2,
761 OutputIterator out)
762 {
763 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
764 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
765 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
766 typedef typename iteratori1_traits::iterator_category
767 iteratori1_category;
768 typedef typename iteratori2_traits::iterator_category
769 iteratori2_category;
770 typedef typename iteratoro_traits::iterator_category iteratoro_category;
771 typedef typename iteratori1_traits::value_type value1_type;
772 typedef typename iteratori2_traits::value_type value2_type;
773
774 return set_difference_switch(begin1, end1, begin2, end2, out,
775 __gnu_parallel::
776 less<value1_type, value2_type>(),
777 iteratori1_category(),
778 iteratori2_category(),
779 iteratoro_category());
780 }
781
782 // Public interface
783 template<typename InputIterator1, typename InputIterator2,
784 typename OutputIterator, typename Predicate>
785 inline OutputIterator
786 set_difference(InputIterator1 begin1, InputIterator1 end1,
787 InputIterator2 begin2, InputIterator2 end2,
788 OutputIterator out, Predicate pred)
789 {
790 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
791 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
792 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
793 typedef typename iteratori1_traits::iterator_category
794 iteratori1_category;
795 typedef typename iteratori2_traits::iterator_category
796 iteratori2_category;
797 typedef typename iteratoro_traits::iterator_category iteratoro_category;
798
799 return set_difference_switch(begin1, end1, begin2, end2, out, pred,
800 iteratori1_category(),
801 iteratori2_category(),
802 iteratoro_category());
803 }
804
805 // Sequential fallback
806 template<typename ForwardIterator>
807 inline ForwardIterator
808 adjacent_find(ForwardIterator begin, ForwardIterator end,
809 __gnu_parallel::sequential_tag)
810 { return _GLIBCXX_STD_P::adjacent_find(begin, end); }
811
812 // Sequential fallback
813 template<typename ForwardIterator, typename BinaryPredicate>
814 inline ForwardIterator
815 adjacent_find(ForwardIterator begin, ForwardIterator end,
816 BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
817 { return _GLIBCXX_STD_P::adjacent_find(begin, end, binary_pred); }
818
819 // Parallel algorithm for random access iterators
820 template<typename RandomAccessIterator>
821 RandomAccessIterator
822 adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
823 random_access_iterator_tag)
824 {
825 typedef iterator_traits<RandomAccessIterator> traits_type;
826 typedef typename traits_type::value_type value_type;
827
828 if (_GLIBCXX_PARALLEL_CONDITION(true))
829 {
830 RandomAccessIterator spot = __gnu_parallel::
831 find_template(begin, end - 1, begin, equal_to<value_type>(),
832 __gnu_parallel::adjacent_find_selector()).first;
833 if (spot == (end - 1))
834 return end;
835 else
836 return spot;
837 }
838 else
839 return adjacent_find(begin, end, __gnu_parallel::sequential_tag());
840 }
841
842 // Sequential fallback for input iterator case
843 template<typename ForwardIterator, typename IteratorTag>
844 inline ForwardIterator
845 adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
846 IteratorTag)
847 { return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); }
848
849 // Public interface
850 template<typename ForwardIterator>
851 inline ForwardIterator
852 adjacent_find(ForwardIterator begin, ForwardIterator end)
853 {
854 typedef iterator_traits<ForwardIterator> traits_type;
855 typedef typename traits_type::iterator_category iterator_category;
856 return adjacent_find_switch(begin, end, iterator_category());
857 }
858
859 // Sequential fallback for input iterator case
860 template<typename ForwardIterator, typename BinaryPredicate,
861 typename IteratorTag>
862 inline ForwardIterator
863 adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
864 BinaryPredicate pred, IteratorTag)
865 { return adjacent_find(begin, end, pred,
866 __gnu_parallel::sequential_tag()); }
867
868 // Parallel algorithm for random access iterators
869 template<typename RandomAccessIterator, typename BinaryPredicate>
870 RandomAccessIterator
871 adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
872 BinaryPredicate pred, random_access_iterator_tag)
873 {
874 if (_GLIBCXX_PARALLEL_CONDITION(true))
875 return __gnu_parallel::find_template(begin, end, begin, pred,
876 __gnu_parallel::
877 adjacent_find_selector()).first;
878 else
879 return adjacent_find(begin, end, pred,
880 __gnu_parallel::sequential_tag());
881 }
882
883 // Public interface
884 template<typename ForwardIterator, typename BinaryPredicate>
885 inline ForwardIterator
886 adjacent_find(ForwardIterator begin, ForwardIterator end,
887 BinaryPredicate pred)
888 {
889 typedef iterator_traits<ForwardIterator> traits_type;
890 typedef typename traits_type::iterator_category iterator_category;
891 return adjacent_find_switch(begin, end, pred, iterator_category());
892 }
893
894 // Sequential fallback
895 template<typename InputIterator, typename T>
896 inline typename iterator_traits<InputIterator>::difference_type
897 count(InputIterator begin, InputIterator end, const T& value,
898 __gnu_parallel::sequential_tag)
899 { return _GLIBCXX_STD_P::count(begin, end, value); }
900
901 // Parallel code for random access iterators
902 template<typename RandomAccessIterator, typename T>
903 typename iterator_traits<RandomAccessIterator>::difference_type
904 count_switch(RandomAccessIterator begin, RandomAccessIterator end,
905 const T& value, random_access_iterator_tag,
906 __gnu_parallel::_Parallelism parallelism_tag
907 = __gnu_parallel::parallel_unbalanced)
908 {
909 typedef iterator_traits<RandomAccessIterator> traits_type;
910 typedef typename traits_type::value_type value_type;
911 typedef typename traits_type::difference_type difference_type;
912 typedef __gnu_parallel::sequence_index_t sequence_index_t;
913
914 if (_GLIBCXX_PARALLEL_CONDITION(
915 static_cast<sequence_index_t>(end - begin)
916 >= __gnu_parallel::_Settings::get().count_minimal_n
917 && __gnu_parallel::is_parallel(parallelism_tag)))
918 {
919 __gnu_parallel::count_selector<RandomAccessIterator, difference_type>
920 functionality;
921 difference_type res = 0;
922 __gnu_parallel::
923 for_each_template_random_access(begin, end, value,
924 functionality,
925 std::plus<sequence_index_t>(),
926 res, res, -1, parallelism_tag);
927 return res;
928 }
929 else
930 return count(begin, end, value, __gnu_parallel::sequential_tag());
931 }
932
933 // Sequential fallback for input iterator case.
934 template<typename InputIterator, typename T, typename IteratorTag>
935 inline typename iterator_traits<InputIterator>::difference_type
936 count_switch(InputIterator begin, InputIterator end, const T& value,
937 IteratorTag)
938 { return count(begin, end, value, __gnu_parallel::sequential_tag()); }
939
940 // Public interface.
941 template<typename InputIterator, typename T>
942 inline typename iterator_traits<InputIterator>::difference_type
943 count(InputIterator begin, InputIterator end, const T& value,
944 __gnu_parallel::_Parallelism parallelism_tag)
945 {
946 typedef iterator_traits<InputIterator> traits_type;
947 typedef typename traits_type::iterator_category iterator_category;
948 return count_switch(begin, end, value, iterator_category(),
949 parallelism_tag);
950 }
951
952 template<typename InputIterator, typename T>
953 inline typename iterator_traits<InputIterator>::difference_type
954 count(InputIterator begin, InputIterator end, const T& value)
955 {
956 typedef iterator_traits<InputIterator> traits_type;
957 typedef typename traits_type::iterator_category iterator_category;
958 return count_switch(begin, end, value, iterator_category());
959 }
960
961
962 // Sequential fallback.
963 template<typename InputIterator, typename Predicate>
964 inline typename iterator_traits<InputIterator>::difference_type
965 count_if(InputIterator begin, InputIterator end, Predicate pred,
966 __gnu_parallel::sequential_tag)
967 { return _GLIBCXX_STD_P::count_if(begin, end, pred); }
968
969 // Parallel count_if for random access iterators
970 template<typename RandomAccessIterator, typename Predicate>
971 typename iterator_traits<RandomAccessIterator>::difference_type
972 count_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
973 Predicate pred, random_access_iterator_tag,
974 __gnu_parallel::_Parallelism parallelism_tag
975 = __gnu_parallel::parallel_unbalanced)
976 {
977 typedef iterator_traits<RandomAccessIterator> traits_type;
978 typedef typename traits_type::value_type value_type;
979 typedef typename traits_type::difference_type difference_type;
980 typedef __gnu_parallel::sequence_index_t sequence_index_t;
981
982 if (_GLIBCXX_PARALLEL_CONDITION(
983 static_cast<sequence_index_t>(end - begin)
984 >= __gnu_parallel::_Settings::get().count_minimal_n
985 && __gnu_parallel::is_parallel(parallelism_tag)))
986 {
987 difference_type res = 0;
988 __gnu_parallel::
989 count_if_selector<RandomAccessIterator, difference_type>
990 functionality;
991 __gnu_parallel::
992 for_each_template_random_access(begin, end, pred,
993 functionality,
994 std::plus<sequence_index_t>(),
995 res, res, -1, parallelism_tag);
996 return res;
997 }
998 else
999 return count_if(begin, end, pred, __gnu_parallel::sequential_tag());
1000 }
1001
1002 // Sequential fallback for input iterator case.
1003 template<typename InputIterator, typename Predicate, typename IteratorTag>
1004 inline typename iterator_traits<InputIterator>::difference_type
1005 count_if_switch(InputIterator begin, InputIterator end, Predicate pred,
1006 IteratorTag)
1007 { return count_if(begin, end, pred, __gnu_parallel::sequential_tag()); }
1008
1009 // Public interface.
1010 template<typename InputIterator, typename Predicate>
1011 inline typename iterator_traits<InputIterator>::difference_type
1012 count_if(InputIterator begin, InputIterator end, Predicate pred,
1013 __gnu_parallel::_Parallelism parallelism_tag)
1014 {
1015 typedef iterator_traits<InputIterator> traits_type;
1016 typedef typename traits_type::iterator_category iterator_category;
1017 return count_if_switch(begin, end, pred, iterator_category(),
1018 parallelism_tag);
1019 }
1020
1021 template<typename InputIterator, typename Predicate>
1022 inline typename iterator_traits<InputIterator>::difference_type
1023 count_if(InputIterator begin, InputIterator end, Predicate pred)
1024 {
1025 typedef iterator_traits<InputIterator> traits_type;
1026 typedef typename traits_type::iterator_category iterator_category;
1027 return count_if_switch(begin, end, pred, iterator_category());
1028 }
1029
1030
1031 // Sequential fallback.
1032 template<typename ForwardIterator1, typename ForwardIterator2>
1033 inline ForwardIterator1
1034 search(ForwardIterator1 begin1, ForwardIterator1 end1,
1035 ForwardIterator2 begin2, ForwardIterator2 end2,
1036 __gnu_parallel::sequential_tag)
1037 { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2); }
1038
1039 // Parallel algorithm for random access iterator
1040 template<typename RandomAccessIterator1, typename RandomAccessIterator2>
1041 RandomAccessIterator1
1042 search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
1043 RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
1044 random_access_iterator_tag, random_access_iterator_tag)
1045 {
1046 typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits;
1047 typedef typename iterator1_traits::value_type value1_type;
1048 typedef std::iterator_traits<RandomAccessIterator2> iterator2_traits;
1049 typedef typename iterator2_traits::value_type value2_type;
1050
1051 if (_GLIBCXX_PARALLEL_CONDITION(true))
1052 return __gnu_parallel::
1053 search_template(begin1, end1, begin2, end2, __gnu_parallel::
1054 equal_to<value1_type, value2_type>());
1055 else
1056 return search(begin1, end1, begin2, end2,
1057 __gnu_parallel::sequential_tag());
1058 }
1059
1060 // Sequential fallback for input iterator case
1061 template<typename ForwardIterator1, typename ForwardIterator2,
1062 typename IteratorTag1, typename IteratorTag2>
1063 inline ForwardIterator1
1064 search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
1065 ForwardIterator2 begin2, ForwardIterator2 end2,
1066 IteratorTag1, IteratorTag2)
1067 { return search(begin1, end1, begin2, end2,
1068 __gnu_parallel::sequential_tag()); }
1069
1070 // Public interface.
1071 template<typename ForwardIterator1, typename ForwardIterator2>
1072 inline ForwardIterator1
1073 search(ForwardIterator1 begin1, ForwardIterator1 end1,
1074 ForwardIterator2 begin2, ForwardIterator2 end2)
1075 {
1076 typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
1077 typedef typename iterator1_traits::iterator_category iterator1_category;
1078 typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
1079 typedef typename iterator2_traits::iterator_category iterator2_category;
1080
1081 return search_switch(begin1, end1, begin2, end2,
1082 iterator1_category(), iterator2_category());
1083 }
1084
1085 // Public interface.
1086 template<typename ForwardIterator1, typename ForwardIterator2,
1087 typename BinaryPredicate>
1088 inline ForwardIterator1
1089 search(ForwardIterator1 begin1, ForwardIterator1 end1,
1090 ForwardIterator2 begin2, ForwardIterator2 end2,
1091 BinaryPredicate pred, __gnu_parallel::sequential_tag)
1092 { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred); }
1093
1094 // Parallel algorithm for random access iterator.
1095 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
1096 typename BinaryPredicate>
1097 RandomAccessIterator1
1098 search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
1099 RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
1100 BinaryPredicate pred,
1101 random_access_iterator_tag, random_access_iterator_tag)
1102 {
1103 if (_GLIBCXX_PARALLEL_CONDITION(true))
1104 return __gnu_parallel::search_template(begin1, end1,
1105 begin2, end2, pred);
1106 else
1107 return search(begin1, end1, begin2, end2, pred,
1108 __gnu_parallel::sequential_tag());
1109 }
1110
1111 // Sequential fallback for input iterator case
1112 template<typename ForwardIterator1, typename ForwardIterator2,
1113 typename BinaryPredicate, typename IteratorTag1,
1114 typename IteratorTag2>
1115 inline ForwardIterator1
1116 search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
1117 ForwardIterator2 begin2, ForwardIterator2 end2,
1118 BinaryPredicate pred, IteratorTag1, IteratorTag2)
1119 { return search(begin1, end1, begin2, end2, pred,
1120 __gnu_parallel::sequential_tag()); }
1121
1122 // Public interface
1123 template<typename ForwardIterator1, typename ForwardIterator2,
1124 typename BinaryPredicate>
1125 inline ForwardIterator1
1126 search(ForwardIterator1 begin1, ForwardIterator1 end1,
1127 ForwardIterator2 begin2, ForwardIterator2 end2,
1128 BinaryPredicate pred)
1129 {
1130 typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
1131 typedef typename iterator1_traits::iterator_category iterator1_category;
1132 typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
1133 typedef typename iterator2_traits::iterator_category iterator2_category;
1134 return search_switch(begin1, end1, begin2, end2, pred,
1135 iterator1_category(), iterator2_category());
1136 }
1137
1138 // Sequential fallback
1139 template<typename ForwardIterator, typename Integer, typename T>
1140 inline ForwardIterator
1141 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1142 const T& val, __gnu_parallel::sequential_tag)
1143 { return _GLIBCXX_STD_P::search_n(begin, end, count, val); }
1144
1145 // Sequential fallback
1146 template<typename ForwardIterator, typename Integer, typename T,
1147 typename BinaryPredicate>
1148 inline ForwardIterator
1149 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1150 const T& val, BinaryPredicate binary_pred,
1151 __gnu_parallel::sequential_tag)
1152 { return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred); }
1153
1154 // Public interface.
1155 template<typename ForwardIterator, typename Integer, typename T>
1156 inline ForwardIterator
1157 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1158 const T& val)
1159 {
1160 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
1161 return search_n(begin, end, count, val,
1162 __gnu_parallel::equal_to<value_type, T>());
1163 }
1164
1165 // Parallel algorithm for random access iterators.
1166 template<typename RandomAccessIterator, typename Integer,
1167 typename T, typename BinaryPredicate>
1168 RandomAccessIterator
1169 search_n_switch(RandomAccessIterator begin, RandomAccessIterator end,
1170 Integer count, const T& val, BinaryPredicate binary_pred,
1171 random_access_iterator_tag)
1172 {
1173 if (_GLIBCXX_PARALLEL_CONDITION(true))
1174 {
1175 __gnu_parallel::pseudo_sequence<T, Integer> ps(val, count);
1176 return __gnu_parallel::search_template(begin, end, ps.begin(),
1177 ps.end(), binary_pred);
1178 }
1179 else
1180 return std::__search_n(begin, end, count, val,
1181 binary_pred, random_access_iterator_tag());
1182 }
1183
1184 // Sequential fallback for input iterator case.
1185 template<typename ForwardIterator, typename Integer, typename T,
1186 typename BinaryPredicate, typename IteratorTag>
1187 inline ForwardIterator
1188 search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count,
1189 const T& val, BinaryPredicate binary_pred, IteratorTag)
1190 { return __search_n(begin, end, count, val, binary_pred, IteratorTag()); }
1191
1192 // Public interface.
1193 template<typename ForwardIterator, typename Integer, typename T,
1194 typename BinaryPredicate>
1195 inline ForwardIterator
1196 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1197 const T& val, BinaryPredicate binary_pred)
1198 {
1199 return search_n_switch(begin, end, count, val, binary_pred,
1200 typename std::iterator_traits<ForwardIterator>::
1201 iterator_category());
1202 }
1203
1204
1205 // Sequential fallback.
1206 template<typename InputIterator, typename OutputIterator,
1207 typename UnaryOperation>
1208 inline OutputIterator
1209 transform(InputIterator begin, InputIterator end, OutputIterator result,
1210 UnaryOperation unary_op, __gnu_parallel::sequential_tag)
1211 { return _GLIBCXX_STD_P::transform(begin, end, result, unary_op); }
1212
1213 // Parallel unary transform for random access iterators.
1214 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
1215 typename UnaryOperation>
1216 RandomAccessIterator2
1217 transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
1218 RandomAccessIterator2 result, UnaryOperation unary_op,
1219 random_access_iterator_tag, random_access_iterator_tag,
1220 __gnu_parallel::_Parallelism parallelism_tag
1221 = __gnu_parallel::parallel_balanced)
1222 {
1223 if (_GLIBCXX_PARALLEL_CONDITION(
1224 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1225 >= __gnu_parallel::_Settings::get().transform_minimal_n
1226 && __gnu_parallel::is_parallel(parallelism_tag)))
1227 {
1228 bool dummy = true;
1229 typedef __gnu_parallel::iterator_pair<RandomAccessIterator1,
1230 RandomAccessIterator2, random_access_iterator_tag> ip;
1231 ip begin_pair(begin, result), end_pair(end, result + (end - begin));
1232 __gnu_parallel::transform1_selector<ip> functionality;
1233 __gnu_parallel::
1234 for_each_template_random_access(begin_pair, end_pair,
1235 unary_op, functionality,
1236 __gnu_parallel::dummy_reduct(),
1237 dummy, dummy, -1, parallelism_tag);
1238 return functionality.finish_iterator;
1239 }
1240 else
1241 return transform(begin, end, result, unary_op,
1242 __gnu_parallel::sequential_tag());
1243 }
1244
1245 // Sequential fallback for input iterator case.
1246 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
1247 typename UnaryOperation, typename IteratorTag1,
1248 typename IteratorTag2>
1249 inline RandomAccessIterator2
1250 transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
1251 RandomAccessIterator2 result, UnaryOperation unary_op,
1252 IteratorTag1, IteratorTag2)
1253 { return transform(begin, end, result, unary_op,
1254 __gnu_parallel::sequential_tag()); }
1255
1256 // Public interface.
1257 template<typename InputIterator, typename OutputIterator,
1258 typename UnaryOperation>
1259 inline OutputIterator
1260 transform(InputIterator begin, InputIterator end, OutputIterator result,
1261 UnaryOperation unary_op,
1262 __gnu_parallel::_Parallelism parallelism_tag)
1263 {
1264 typedef std::iterator_traits<InputIterator> iteratori_traits;
1265 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1266 typedef typename iteratori_traits::iterator_category iteratori_category;
1267 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1268
1269 return transform1_switch(begin, end, result, unary_op,
1270 iteratori_category(), iteratoro_category(),
1271 parallelism_tag);
1272 }
1273
1274 template<typename InputIterator, typename OutputIterator,
1275 typename UnaryOperation>
1276 inline OutputIterator
1277 transform(InputIterator begin, InputIterator end, OutputIterator result,
1278 UnaryOperation unary_op)
1279 {
1280 typedef std::iterator_traits<InputIterator> iteratori_traits;
1281 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1282 typedef typename iteratori_traits::iterator_category iteratori_category;
1283 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1284
1285 return transform1_switch(begin, end, result, unary_op,
1286 iteratori_category(), iteratoro_category());
1287 }
1288
1289
1290 // Sequential fallback
1291 template<typename InputIterator1, typename InputIterator2,
1292 typename OutputIterator, typename BinaryOperation>
1293 inline OutputIterator
1294 transform(InputIterator1 begin1, InputIterator1 end1,
1295 InputIterator2 begin2, OutputIterator result,
1296 BinaryOperation binary_op, __gnu_parallel::sequential_tag)
1297 { return _GLIBCXX_STD_P::transform(begin1, end1,
1298 begin2, result, binary_op); }
1299
1300 // Parallel binary transform for random access iterators.
1301 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
1302 typename RandomAccessIterator3, typename BinaryOperation>
1303 RandomAccessIterator3
1304 transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
1305 RandomAccessIterator2 begin2,
1306 RandomAccessIterator3 result, BinaryOperation binary_op,
1307 random_access_iterator_tag, random_access_iterator_tag,
1308 random_access_iterator_tag,
1309 __gnu_parallel::_Parallelism parallelism_tag
1310 = __gnu_parallel::parallel_balanced)
1311 {
1312 if (_GLIBCXX_PARALLEL_CONDITION(
1313 (end1 - begin1) >=
1314 __gnu_parallel::_Settings::get().transform_minimal_n
1315 && __gnu_parallel::is_parallel(parallelism_tag)))
1316 {
1317 bool dummy = true;
1318 typedef __gnu_parallel::iterator_triple<RandomAccessIterator1,
1319 RandomAccessIterator2, RandomAccessIterator3,
1320 random_access_iterator_tag> ip;
1321 ip begin_triple(begin1, begin2, result),
1322 end_triple(end1, begin2 + (end1 - begin1),
1323 result + (end1 - begin1));
1324 __gnu_parallel::transform2_selector<ip> functionality;
1325 __gnu_parallel::
1326 for_each_template_random_access(begin_triple, end_triple,
1327 binary_op, functionality,
1328 __gnu_parallel::dummy_reduct(),
1329 dummy, dummy, -1,
1330 parallelism_tag);
1331 return functionality.finish_iterator;
1332 }
1333 else
1334 return transform(begin1, end1, begin2, result, binary_op,
1335 __gnu_parallel::sequential_tag());
1336 }
1337
1338 // Sequential fallback for input iterator case.
1339 template<typename InputIterator1, typename InputIterator2,
1340 typename OutputIterator, typename BinaryOperation,
1341 typename tag1, typename tag2, typename tag3>
1342 inline OutputIterator
1343 transform2_switch(InputIterator1 begin1, InputIterator1 end1,
1344 InputIterator2 begin2, OutputIterator result,
1345 BinaryOperation binary_op, tag1, tag2, tag3)
1346 { return transform(begin1, end1, begin2, result, binary_op,
1347 __gnu_parallel::sequential_tag()); }
1348
1349 // Public interface.
1350 template<typename InputIterator1, typename InputIterator2,
1351 typename OutputIterator, typename BinaryOperation>
1352 inline OutputIterator
1353 transform(InputIterator1 begin1, InputIterator1 end1,
1354 InputIterator2 begin2, OutputIterator result,
1355 BinaryOperation binary_op,
1356 __gnu_parallel::_Parallelism parallelism_tag)
1357 {
1358 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
1359 typedef typename iteratori1_traits::iterator_category
1360 iteratori1_category;
1361 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
1362 typedef typename iteratori2_traits::iterator_category
1363 iteratori2_category;
1364 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1365 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1366
1367 return transform2_switch(begin1, end1, begin2, result, binary_op,
1368 iteratori1_category(), iteratori2_category(),
1369 iteratoro_category(), parallelism_tag);
1370 }
1371
1372 template<typename InputIterator1, typename InputIterator2,
1373 typename OutputIterator, typename BinaryOperation>
1374 inline OutputIterator
1375 transform(InputIterator1 begin1, InputIterator1 end1,
1376 InputIterator2 begin2, OutputIterator result,
1377 BinaryOperation binary_op)
1378 {
1379 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
1380 typedef typename iteratori1_traits::iterator_category
1381 iteratori1_category;
1382 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
1383 typedef typename iteratori2_traits::iterator_category
1384 iteratori2_category;
1385 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1386 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1387
1388 return transform2_switch(begin1, end1, begin2, result, binary_op,
1389 iteratori1_category(), iteratori2_category(),
1390 iteratoro_category());
1391 }
1392
1393 // Sequential fallback
1394 template<typename ForwardIterator, typename T>
1395 inline void
1396 replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
1397 const T& new_value, __gnu_parallel::sequential_tag)
1398 { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); }
1399
1400 // Sequential fallback for input iterator case
1401 template<typename ForwardIterator, typename T, typename IteratorTag>
1402 inline void
1403 replace_switch(ForwardIterator begin, ForwardIterator end,
1404 const T& old_value, const T& new_value, IteratorTag)
1405 { replace(begin, end, old_value, new_value,
1406 __gnu_parallel::sequential_tag()); }
1407
1408 // Parallel replace for random access iterators
1409 template<typename RandomAccessIterator, typename T>
1410 inline void
1411 replace_switch(RandomAccessIterator begin, RandomAccessIterator end,
1412 const T& old_value, const T& new_value,
1413 random_access_iterator_tag,
1414 __gnu_parallel::_Parallelism parallelism_tag
1415 = __gnu_parallel::parallel_balanced)
1416 {
1417 // XXX parallel version is where?
1418 replace(begin, end, old_value, new_value,
1419 __gnu_parallel::sequential_tag());
1420 }
1421
1422 // Public interface
1423 template<typename ForwardIterator, typename T>
1424 inline void
1425 replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
1426 const T& new_value, __gnu_parallel::_Parallelism parallelism_tag)
1427 {
1428 typedef iterator_traits<ForwardIterator> traits_type;
1429 typedef typename traits_type::iterator_category iterator_category;
1430 replace_switch(begin, end, old_value, new_value, iterator_category(),
1431 parallelism_tag);
1432 }
1433
1434 template<typename ForwardIterator, typename T>
1435 inline void
1436 replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
1437 const T& new_value)
1438 {
1439 typedef iterator_traits<ForwardIterator> traits_type;
1440 typedef typename traits_type::iterator_category iterator_category;
1441 replace_switch(begin, end, old_value, new_value, iterator_category());
1442 }
1443
1444
1445 // Sequential fallback
1446 template<typename ForwardIterator, typename Predicate, typename T>
1447 inline void
1448 replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred,
1449 const T& new_value, __gnu_parallel::sequential_tag)
1450 { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); }
1451
1452 // Sequential fallback for input iterator case
1453 template<typename ForwardIterator, typename Predicate, typename T,
1454 typename IteratorTag>
1455 inline void
1456 replace_if_switch(ForwardIterator begin, ForwardIterator end,
1457 Predicate pred, const T& new_value, IteratorTag)
1458 { replace_if(begin, end, pred, new_value,
1459 __gnu_parallel::sequential_tag()); }
1460
1461 // Parallel algorithm for random access iterators.
1462 template<typename RandomAccessIterator, typename Predicate, typename T>
1463 void
1464 replace_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
1465 Predicate pred, const T& new_value,
1466 random_access_iterator_tag,
1467 __gnu_parallel::_Parallelism parallelism_tag
1468 = __gnu_parallel::parallel_balanced)
1469 {
1470 if (_GLIBCXX_PARALLEL_CONDITION(
1471 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1472 >= __gnu_parallel::_Settings::get().replace_minimal_n
1473 && __gnu_parallel::is_parallel(parallelism_tag)))
1474 {
1475 bool dummy;
1476 __gnu_parallel::
1477 replace_if_selector<RandomAccessIterator, Predicate, T>
1478 functionality(new_value);
1479 __gnu_parallel::
1480 for_each_template_random_access(begin, end, pred,
1481 functionality,
1482 __gnu_parallel::dummy_reduct(),
1483 true, dummy, -1, parallelism_tag);
1484 }
1485 else
1486 replace_if(begin, end, pred, new_value,
1487 __gnu_parallel::sequential_tag());
1488 }
1489
1490 // Public interface.
1491 template<typename ForwardIterator, typename Predicate, typename T>
1492 inline void
1493 replace_if(ForwardIterator begin, ForwardIterator end,
1494 Predicate pred, const T& new_value,
1495 __gnu_parallel::_Parallelism parallelism_tag)
1496 {
1497 typedef std::iterator_traits<ForwardIterator> iterator_traits;
1498 typedef typename iterator_traits::iterator_category iterator_category;
1499 replace_if_switch(begin, end, pred, new_value, iterator_category(),
1500 parallelism_tag);
1501 }
1502
1503 template<typename ForwardIterator, typename Predicate, typename T>
1504 inline void
1505 replace_if(ForwardIterator begin, ForwardIterator end,
1506 Predicate pred, const T& new_value)
1507 {
1508 typedef std::iterator_traits<ForwardIterator> iterator_traits;
1509 typedef typename iterator_traits::iterator_category iterator_category;
1510 replace_if_switch(begin, end, pred, new_value, iterator_category());
1511 }
1512
1513 // Sequential fallback
1514 template<typename ForwardIterator, typename Generator>
1515 inline void
1516 generate(ForwardIterator begin, ForwardIterator end, Generator gen,
1517 __gnu_parallel::sequential_tag)
1518 { _GLIBCXX_STD_P::generate(begin, end, gen); }
1519
1520 // Sequential fallback for input iterator case.
1521 template<typename ForwardIterator, typename Generator, typename IteratorTag>
1522 inline void
1523 generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen,
1524 IteratorTag)
1525 { generate(begin, end, gen, __gnu_parallel::sequential_tag()); }
1526
1527 // Parallel algorithm for random access iterators.
1528 template<typename RandomAccessIterator, typename Generator>
1529 void
1530 generate_switch(RandomAccessIterator begin, RandomAccessIterator end,
1531 Generator gen, random_access_iterator_tag,
1532 __gnu_parallel::_Parallelism parallelism_tag
1533 = __gnu_parallel::parallel_balanced)
1534 {
1535 if (_GLIBCXX_PARALLEL_CONDITION(
1536 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1537 >= __gnu_parallel::_Settings::get().generate_minimal_n
1538 && __gnu_parallel::is_parallel(parallelism_tag)))
1539 {
1540 bool dummy;
1541 __gnu_parallel::generate_selector<RandomAccessIterator>
1542 functionality;
1543 __gnu_parallel::
1544 for_each_template_random_access(begin, end, gen, functionality,
1545 __gnu_parallel::dummy_reduct(),
1546 true, dummy, -1, parallelism_tag);
1547 }
1548 else
1549 generate(begin, end, gen, __gnu_parallel::sequential_tag());
1550 }
1551
1552 // Public interface.
1553 template<typename ForwardIterator, typename Generator>
1554 inline void
1555 generate(ForwardIterator begin, ForwardIterator end,
1556 Generator gen, __gnu_parallel::_Parallelism parallelism_tag)
1557 {
1558 typedef std::iterator_traits<ForwardIterator> iterator_traits;
1559 typedef typename iterator_traits::iterator_category iterator_category;
1560 generate_switch(begin, end, gen, iterator_category(), parallelism_tag);
1561 }
1562
1563 template<typename ForwardIterator, typename Generator>
1564 inline void
1565 generate(ForwardIterator begin, ForwardIterator end, Generator gen)
1566 {
1567 typedef std::iterator_traits<ForwardIterator> iterator_traits;
1568 typedef typename iterator_traits::iterator_category iterator_category;
1569 generate_switch(begin, end, gen, iterator_category());
1570 }
1571
1572
1573 // Sequential fallback.
1574 template<typename OutputIterator, typename Size, typename Generator>
1575 inline OutputIterator
1576 generate_n(OutputIterator begin, Size n, Generator gen,
1577 __gnu_parallel::sequential_tag)
1578 { return _GLIBCXX_STD_P::generate_n(begin, n, gen); }
1579
1580 // Sequential fallback for input iterator case.
1581 template<typename OutputIterator, typename Size, typename Generator,
1582 typename IteratorTag>
1583 inline OutputIterator
1584 generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag)
1585 { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
1586
1587 // Parallel algorithm for random access iterators.
1588 template<typename RandomAccessIterator, typename Size, typename Generator>
1589 inline RandomAccessIterator
1590 generate_n_switch(RandomAccessIterator begin, Size n, Generator gen,
1591 random_access_iterator_tag,
1592 __gnu_parallel::_Parallelism parallelism_tag
1593 = __gnu_parallel::parallel_balanced)
1594 {
1595 // XXX parallel version is where?
1596 return generate_n(begin, n, gen, __gnu_parallel::sequential_tag());
1597 }
1598
1599 // Public interface.
1600 template<typename OutputIterator, typename Size, typename Generator>
1601 inline OutputIterator
1602 generate_n(OutputIterator begin, Size n, Generator gen,
1603 __gnu_parallel::_Parallelism parallelism_tag)
1604 {
1605 typedef std::iterator_traits<OutputIterator> iterator_traits;
1606 typedef typename iterator_traits::iterator_category iterator_category;
1607 return generate_n_switch(begin, n, gen, iterator_category(),
1608 parallelism_tag);
1609 }
1610
1611 template<typename OutputIterator, typename Size, typename Generator>
1612 inline OutputIterator
1613 generate_n(OutputIterator begin, Size n, Generator gen)
1614 {
1615 typedef std::iterator_traits<OutputIterator> iterator_traits;
1616 typedef typename iterator_traits::iterator_category iterator_category;
1617 return generate_n_switch(begin, n, gen, iterator_category());
1618 }
1619
1620
1621 // Sequential fallback.
1622 template<typename RandomAccessIterator>
1623 inline void
1624 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
1625 __gnu_parallel::sequential_tag)
1626 { _GLIBCXX_STD_P::random_shuffle(begin, end); }
1627
1628 // Sequential fallback.
1629 template<typename RandomAccessIterator, typename RandomNumberGenerator>
1630 inline void
1631 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
1632 RandomNumberGenerator& rand, __gnu_parallel::sequential_tag)
1633 { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); }
1634
1635
1636 /** @brief Functor wrapper for std::rand(). */
1637 template<typename must_be_int = int>
1638 struct c_rand_number
1639 {
1640 int
1641 operator()(int limit)
1642 { return rand() % limit; }
1643 };
1644
1645 // Fill in random number generator.
1646 template<typename RandomAccessIterator>
1647 inline void
1648 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end)
1649 {
1650 c_rand_number<> r;
1651 // Parallelization still possible.
1652 __gnu_parallel::random_shuffle(begin, end, r);
1653 }
1654
1655 // Parallel algorithm for random access iterators.
1656 template<typename RandomAccessIterator, typename RandomNumberGenerator>
1657 void
1658 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
1659 RandomNumberGenerator& rand)
1660 {
1661 if (begin == end)
1662 return;
1663 if (_GLIBCXX_PARALLEL_CONDITION(
1664 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1665 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
1666 __gnu_parallel::parallel_random_shuffle(begin, end, rand);
1667 else
1668 __gnu_parallel::sequential_random_shuffle(begin, end, rand);
1669 }
1670
1671 // Sequential fallback.
1672 template<typename ForwardIterator, typename Predicate>
1673 inline ForwardIterator
1674 partition(ForwardIterator begin, ForwardIterator end,
1675 Predicate pred, __gnu_parallel::sequential_tag)
1676 { return _GLIBCXX_STD_P::partition(begin, end, pred); }
1677
1678 // Sequential fallback for input iterator case.
1679 template<typename ForwardIterator, typename Predicate, typename IteratorTag>
1680 inline ForwardIterator
1681 partition_switch(ForwardIterator begin, ForwardIterator end,
1682 Predicate pred, IteratorTag)
1683 { return partition(begin, end, pred, __gnu_parallel::sequential_tag()); }
1684
1685 // Parallel algorithm for random access iterators.
1686 template<typename RandomAccessIterator, typename Predicate>
1687 RandomAccessIterator
1688 partition_switch(RandomAccessIterator begin, RandomAccessIterator end,
1689 Predicate pred, random_access_iterator_tag)
1690 {
1691 if (_GLIBCXX_PARALLEL_CONDITION(
1692 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1693 >= __gnu_parallel::_Settings::get().partition_minimal_n))
1694 {
1695 typedef typename std::iterator_traits<RandomAccessIterator>::
1696 difference_type difference_type;
1697 difference_type middle = __gnu_parallel::
1698 parallel_partition(begin, end, pred,
1699 __gnu_parallel::get_max_threads());
1700 return begin + middle;
1701 }
1702 else
1703 return partition(begin, end, pred, __gnu_parallel::sequential_tag());
1704 }
1705
1706 // Public interface.
1707 template<typename ForwardIterator, typename Predicate>
1708 inline ForwardIterator
1709 partition(ForwardIterator begin, ForwardIterator end, Predicate pred)
1710 {
1711 typedef iterator_traits<ForwardIterator> traits_type;
1712 typedef typename traits_type::iterator_category iterator_category;
1713 return partition_switch(begin, end, pred, iterator_category());
1714 }
1715
1716 // sort interface
1717
1718 // Sequential fallback
1719 template<typename RandomAccessIterator>
1720 inline void
1721 sort(RandomAccessIterator begin, RandomAccessIterator end,
1722 __gnu_parallel::sequential_tag)
1723 { _GLIBCXX_STD_P::sort(begin, end); }
1724
1725 // Sequential fallback
1726 template<typename RandomAccessIterator, typename Comparator>
1727 inline void
1728 sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
1729 __gnu_parallel::sequential_tag)
1730 { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end,
1731 comp); }
1732
1733 // Public interface
1734 template<typename RandomAccessIterator, typename Comparator,
1735 typename Parallelism>
1736 void
1737 sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
1738 Parallelism parallelism)
1739 {
1740 typedef iterator_traits<RandomAccessIterator> traits_type;
1741 typedef typename traits_type::value_type value_type;
1742
1743 if (begin != end)
1744 {
1745 if (_GLIBCXX_PARALLEL_CONDITION(
1746 static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
1747 __gnu_parallel::_Settings::get().sort_minimal_n))
1748 __gnu_parallel::parallel_sort<false>(begin, end, comp, parallelism);
1749 else
1750 sort(begin, end, comp, __gnu_parallel::sequential_tag());
1751 }
1752 }
1753
1754 // Public interface, insert default comparator
1755 template<typename RandomAccessIterator>
1756 inline void
1757 sort(RandomAccessIterator begin, RandomAccessIterator end)
1758 {
1759 typedef iterator_traits<RandomAccessIterator> traits_type;
1760 typedef typename traits_type::value_type value_type;
1761 sort(begin, end, std::less<value_type>(),
1762 __gnu_parallel::default_parallel_tag());
1763 }
1764
1765 // Public interface, insert default comparator
1766 template<typename RandomAccessIterator>
1767 inline void
1768 sort(RandomAccessIterator begin, RandomAccessIterator end,
1769 __gnu_parallel::default_parallel_tag parallelism)
1770 {
1771 typedef iterator_traits<RandomAccessIterator> traits_type;
1772 typedef typename traits_type::value_type value_type;
1773 sort(begin, end, std::less<value_type>(), parallelism);
1774 }
1775
1776 // Public interface, insert default comparator
1777 template<typename RandomAccessIterator>
1778 inline void
1779 sort(RandomAccessIterator begin, RandomAccessIterator end,
1780 __gnu_parallel::parallel_tag parallelism)
1781 {
1782 typedef iterator_traits<RandomAccessIterator> traits_type;
1783 typedef typename traits_type::value_type value_type;
1784 sort(begin, end, std::less<value_type>(), parallelism);
1785 }
1786
1787 // Public interface, insert default comparator
1788 template<typename RandomAccessIterator>
1789 inline void
1790 sort(RandomAccessIterator begin, RandomAccessIterator end,
1791 __gnu_parallel::multiway_mergesort_tag parallelism)
1792 {
1793 typedef iterator_traits<RandomAccessIterator> traits_type;
1794 typedef typename traits_type::value_type value_type;
1795 sort(begin, end, std::less<value_type>(), parallelism);
1796 }
1797
1798 // Public interface, insert default comparator
1799 template<typename RandomAccessIterator>
1800 inline void
1801 sort(RandomAccessIterator begin, RandomAccessIterator end,
1802 __gnu_parallel::multiway_mergesort_sampling_tag parallelism)
1803 {
1804 typedef iterator_traits<RandomAccessIterator> traits_type;
1805 typedef typename traits_type::value_type value_type;
1806 sort(begin, end, std::less<value_type>(), parallelism);
1807 }
1808
1809 // Public interface, insert default comparator
1810 template<typename RandomAccessIterator>
1811 inline void
1812 sort(RandomAccessIterator begin, RandomAccessIterator end,
1813 __gnu_parallel::multiway_mergesort_exact_tag parallelism)
1814 {
1815 typedef iterator_traits<RandomAccessIterator> traits_type;
1816 typedef typename traits_type::value_type value_type;
1817 sort(begin, end, std::less<value_type>(), parallelism);
1818 }
1819
1820 // Public interface, insert default comparator
1821 template<typename RandomAccessIterator>
1822 inline void
1823 sort(RandomAccessIterator begin, RandomAccessIterator end,
1824 __gnu_parallel::quicksort_tag parallelism)
1825 {
1826 typedef iterator_traits<RandomAccessIterator> traits_type;
1827 typedef typename traits_type::value_type value_type;
1828 sort(begin, end, std::less<value_type>(), parallelism);
1829 }
1830
1831 // Public interface, insert default comparator
1832 template<typename RandomAccessIterator>
1833 inline void
1834 sort(RandomAccessIterator begin, RandomAccessIterator end,
1835 __gnu_parallel::balanced_quicksort_tag parallelism)
1836 {
1837 typedef iterator_traits<RandomAccessIterator> traits_type;
1838 typedef typename traits_type::value_type value_type;
1839 sort(begin, end, std::less<value_type>(), parallelism);
1840 }
1841
1842 // Public interface
1843 template<typename RandomAccessIterator, typename Comparator>
1844 void
1845 sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
1846 {
1847 typedef iterator_traits<RandomAccessIterator> traits_type;
1848 typedef typename traits_type::value_type value_type;
1849 sort(begin, end, comp, __gnu_parallel::default_parallel_tag());
1850 }
1851
1852
1853 // stable_sort interface
1854
1855
1856 // Sequential fallback
1857 template<typename RandomAccessIterator>
1858 inline void
1859 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1860 __gnu_parallel::sequential_tag)
1861 { _GLIBCXX_STD_P::stable_sort(begin, end); }
1862
1863 // Sequential fallback
1864 template<typename RandomAccessIterator, typename Comparator>
1865 inline void
1866 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1867 Comparator comp, __gnu_parallel::sequential_tag)
1868 { _GLIBCXX_STD_P::stable_sort<RandomAccessIterator, Comparator>(
1869 begin, end, comp); }
1870
1871 // Public interface
1872 template<typename RandomAccessIterator, typename Comparator,
1873 typename Parallelism>
1874 void
1875 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1876 Comparator comp, Parallelism parallelism)
1877 {
1878 typedef iterator_traits<RandomAccessIterator> traits_type;
1879 typedef typename traits_type::value_type value_type;
1880
1881 if (begin != end)
1882 {
1883 if (_GLIBCXX_PARALLEL_CONDITION(
1884 static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
1885 __gnu_parallel::_Settings::get().sort_minimal_n))
1886 __gnu_parallel::parallel_sort<true>(begin, end, comp, parallelism);
1887 else
1888 stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
1889 }
1890 }
1891
1892 // Public interface, insert default comparator
1893 template<typename RandomAccessIterator>
1894 inline void
1895 stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
1896 {
1897 typedef iterator_traits<RandomAccessIterator> traits_type;
1898 typedef typename traits_type::value_type value_type;
1899 stable_sort(begin, end, std::less<value_type>(),
1900 __gnu_parallel::default_parallel_tag());
1901 }
1902
1903 // Public interface, insert default comparator
1904 template<typename RandomAccessIterator>
1905 inline void
1906 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1907 __gnu_parallel::default_parallel_tag parallelism)
1908 {
1909 typedef iterator_traits<RandomAccessIterator> traits_type;
1910 typedef typename traits_type::value_type value_type;
1911 stable_sort(begin, end, std::less<value_type>(), parallelism);
1912 }
1913
1914 // Public interface, insert default comparator
1915 template<typename RandomAccessIterator>
1916 inline void
1917 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1918 __gnu_parallel::parallel_tag parallelism)
1919 {
1920 typedef iterator_traits<RandomAccessIterator> traits_type;
1921 typedef typename traits_type::value_type value_type;
1922 stable_sort(begin, end, std::less<value_type>(), parallelism);
1923 }
1924
1925 // Public interface, insert default comparator
1926 template<typename RandomAccessIterator>
1927 inline void
1928 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1929 __gnu_parallel::multiway_mergesort_tag parallelism)
1930 {
1931 typedef iterator_traits<RandomAccessIterator> traits_type;
1932 typedef typename traits_type::value_type value_type;
1933 stable_sort(begin, end, std::less<value_type>(), parallelism);
1934 }
1935
1936 // Public interface, insert default comparator
1937 template<typename RandomAccessIterator>
1938 inline void
1939 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1940 __gnu_parallel::quicksort_tag parallelism)
1941 {
1942 typedef iterator_traits<RandomAccessIterator> traits_type;
1943 typedef typename traits_type::value_type value_type;
1944 stable_sort(begin, end, std::less<value_type>(), parallelism);
1945 }
1946
1947 // Public interface, insert default comparator
1948 template<typename RandomAccessIterator>
1949 inline void
1950 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1951 __gnu_parallel::balanced_quicksort_tag parallelism)
1952 {
1953 typedef iterator_traits<RandomAccessIterator> traits_type;
1954 typedef typename traits_type::value_type value_type;
1955 stable_sort(begin, end, std::less<value_type>(), parallelism);
1956 }
1957
1958 // Public interface
1959 template<typename RandomAccessIterator, typename Comparator>
1960 void
1961 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1962 Comparator comp)
1963 {
1964 typedef iterator_traits<RandomAccessIterator> traits_type;
1965 typedef typename traits_type::value_type value_type;
1966 stable_sort(begin, end, comp, __gnu_parallel::default_parallel_tag());
1967 }
1968
1969
1970 // // Sequential fallback
1971 // template<typename RandomAccessIterator>
1972 // inline void
1973 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1974 // __gnu_parallel::sequential_tag)
1975 // { return _GLIBCXX_STD_P::stable_sort(begin, end); }
1976 //
1977 // // Sequential fallback
1978 // template<typename RandomAccessIterator, typename Comparator>
1979 // inline void
1980 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1981 // Comparator comp, __gnu_parallel::sequential_tag)
1982 // { return _GLIBCXX_STD_P::stable_sort(begin, end, comp); }
1983 //
1984 // template<typename RandomAccessIterator>
1985 // void
1986 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
1987 // {
1988 // typedef iterator_traits<RandomAccessIterator> traits_type;
1989 // typedef typename traits_type::value_type value_type;
1990 // stable_sort(begin, end, std::less<value_type>());
1991 // }
1992 //
1993 // // Parallel algorithm for random access iterators
1994 // template<typename RandomAccessIterator, typename Comparator>
1995 // void
1996 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1997 // Comparator comp)
1998 // {
1999 // if (begin != end)
2000 // {
2001 // if (_GLIBCXX_PARALLEL_CONDITION(
2002 // static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
2003 // __gnu_parallel::_Settings::get().sort_minimal_n))
2004 // __gnu_parallel::parallel_sort(begin, end, comp,
2005 // __gnu_parallel::parallel_tag());
2006 // else
2007 // stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
2008 // }
2009 // }
2010
2011 // Sequential fallback
2012 template<typename InputIterator1, typename InputIterator2,
2013 typename OutputIterator>
2014 inline OutputIterator
2015 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2016 InputIterator2 end2, OutputIterator result,
2017 __gnu_parallel::sequential_tag)
2018 { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result); }
2019
2020 // Sequential fallback
2021 template<typename InputIterator1, typename InputIterator2,
2022 typename OutputIterator, typename Comparator>
2023 inline OutputIterator
2024 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2025 InputIterator2 end2, OutputIterator result, Comparator comp,
2026 __gnu_parallel::sequential_tag)
2027 { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp); }
2028
2029 // Sequential fallback for input iterator case
2030 template<typename InputIterator1, typename InputIterator2,
2031 typename OutputIterator, typename Comparator,
2032 typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
2033 inline OutputIterator
2034 merge_switch(InputIterator1 begin1, InputIterator1 end1,
2035 InputIterator2 begin2, InputIterator2 end2,
2036 OutputIterator result, Comparator comp,
2037 IteratorTag1, IteratorTag2, IteratorTag3)
2038 { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2,
2039 result, comp); }
2040
2041 // Parallel algorithm for random access iterators
2042 template<typename InputIterator1, typename InputIterator2,
2043 typename OutputIterator, typename Comparator>
2044 OutputIterator
2045 merge_switch(InputIterator1 begin1, InputIterator1 end1,
2046 InputIterator2 begin2, InputIterator2 end2,
2047 OutputIterator result, Comparator comp,
2048 random_access_iterator_tag, random_access_iterator_tag,
2049 random_access_iterator_tag)
2050 {
2051 if (_GLIBCXX_PARALLEL_CONDITION(
2052 (static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
2053 >= __gnu_parallel::_Settings::get().merge_minimal_n
2054 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
2055 >= __gnu_parallel::_Settings::get().merge_minimal_n)))
2056 return __gnu_parallel::parallel_merge_advance(begin1, end1,
2057 begin2, end2,
2058 result, (end1 - begin1)
2059 + (end2 - begin2), comp);
2060 else
2061 return __gnu_parallel::merge_advance(begin1, end1, begin2, end2,
2062 result, (end1 - begin1)
2063 + (end2 - begin2), comp);
2064 }
2065
2066 // Public interface
2067 template<typename InputIterator1, typename InputIterator2,
2068 typename OutputIterator, typename Comparator>
2069 inline OutputIterator
2070 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2071 InputIterator2 end2, OutputIterator result, Comparator comp)
2072 {
2073 typedef typename iterator_traits<InputIterator1>::value_type value_type;
2074
2075 typedef std::iterator_traits<InputIterator1> iteratori1_traits;
2076 typedef std::iterator_traits<InputIterator2> iteratori2_traits;
2077 typedef std::iterator_traits<OutputIterator> iteratoro_traits;
2078 typedef typename iteratori1_traits::iterator_category
2079 iteratori1_category;
2080 typedef typename iteratori2_traits::iterator_category
2081 iteratori2_category;
2082 typedef typename iteratoro_traits::iterator_category iteratoro_category;
2083
2084 return merge_switch(begin1, end1, begin2, end2, result, comp,
2085 iteratori1_category(), iteratori2_category(),
2086 iteratoro_category());
2087 }
2088
2089
2090 // Public interface, insert default comparator
2091 template<typename InputIterator1, typename InputIterator2,
2092 typename OutputIterator>
2093 inline OutputIterator
2094 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2095 InputIterator2 end2, OutputIterator result)
2096 {
2097 typedef std::iterator_traits<InputIterator1> iterator1_traits;
2098 typedef std::iterator_traits<InputIterator2> iterator2_traits;
2099 typedef typename iterator1_traits::value_type value1_type;
2100 typedef typename iterator2_traits::value_type value2_type;
2101
2102 return merge(begin1, end1, begin2, end2, result,
2103 __gnu_parallel::less<value1_type, value2_type>());
2104 }
2105
2106 // Sequential fallback
2107 template<typename RandomAccessIterator>
2108 inline void
2109 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2110 RandomAccessIterator end, __gnu_parallel::sequential_tag)
2111 { return _GLIBCXX_STD_P::nth_element(begin, nth, end); }
2112
2113 // Sequential fallback
2114 template<typename RandomAccessIterator, typename Comparator>
2115 inline void
2116 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2117 RandomAccessIterator end, Comparator comp,
2118 __gnu_parallel::sequential_tag)
2119 { return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); }
2120
2121 // Public interface
2122 template<typename RandomAccessIterator, typename Comparator>
2123 inline void
2124 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2125 RandomAccessIterator end, Comparator comp)
2126 {
2127 if (_GLIBCXX_PARALLEL_CONDITION(
2128 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2129 >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
2130 __gnu_parallel::parallel_nth_element(begin, nth, end, comp);
2131 else
2132 nth_element(begin, nth, end, comp, __gnu_parallel::sequential_tag());
2133 }
2134
2135 // Public interface, insert default comparator
2136 template<typename RandomAccessIterator>
2137 inline void
2138 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2139 RandomAccessIterator end)
2140 {
2141 typedef iterator_traits<RandomAccessIterator> traits_type;
2142 typedef typename traits_type::value_type value_type;
2143 nth_element(begin, nth, end, std::less<value_type>());
2144 }
2145
2146 // Sequential fallback
2147 template<typename RandomAccessIterator, typename _Compare>
2148 inline void
2149 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2150 RandomAccessIterator end, _Compare comp,
2151 __gnu_parallel::sequential_tag)
2152 { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); }
2153
2154 // Sequential fallback
2155 template<typename RandomAccessIterator>
2156 inline void
2157 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2158 RandomAccessIterator end, __gnu_parallel::sequential_tag)
2159 { _GLIBCXX_STD_P::partial_sort(begin, middle, end); }
2160
2161 // Public interface, parallel algorithm for random access iterators
2162 template<typename RandomAccessIterator, typename _Compare>
2163 void
2164 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2165 RandomAccessIterator end, _Compare comp)
2166 {
2167 if (_GLIBCXX_PARALLEL_CONDITION(
2168 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2169 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
2170 __gnu_parallel::parallel_partial_sort(begin, middle, end, comp);
2171 else
2172 partial_sort(begin, middle, end, comp,
2173 __gnu_parallel::sequential_tag());
2174 }
2175
2176 // Public interface, insert default comparator
2177 template<typename RandomAccessIterator>
2178 inline void
2179 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2180 RandomAccessIterator end)
2181 {
2182 typedef iterator_traits<RandomAccessIterator> traits_type;
2183 typedef typename traits_type::value_type value_type;
2184 partial_sort(begin, middle, end, std::less<value_type>());
2185 }
2186
2187 // Sequential fallback
2188 template<typename ForwardIterator>
2189 inline ForwardIterator
2190 max_element(ForwardIterator begin, ForwardIterator end,
2191 __gnu_parallel::sequential_tag)
2192 { return _GLIBCXX_STD_P::max_element(begin, end); }
2193
2194 // Sequential fallback
2195 template<typename ForwardIterator, typename Comparator>
2196 inline ForwardIterator
2197 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2198 __gnu_parallel::sequential_tag)
2199 { return _GLIBCXX_STD_P::max_element(begin, end, comp); }
2200
2201 // Sequential fallback for input iterator case
2202 template<typename ForwardIterator, typename Comparator, typename IteratorTag>
2203 inline ForwardIterator
2204 max_element_switch(ForwardIterator begin, ForwardIterator end,
2205 Comparator comp, IteratorTag)
2206 { return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
2207
2208 // Parallel algorithm for random access iterators
2209 template<typename RandomAccessIterator, typename Comparator>
2210 RandomAccessIterator
2211 max_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
2212 Comparator comp, random_access_iterator_tag,
2213 __gnu_parallel::_Parallelism parallelism_tag
2214 = __gnu_parallel::parallel_balanced)
2215 {
2216 if (_GLIBCXX_PARALLEL_CONDITION(
2217 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2218 >= __gnu_parallel::_Settings::get().max_element_minimal_n
2219 && __gnu_parallel::is_parallel(parallelism_tag)))
2220 {
2221 RandomAccessIterator res(begin);
2222 __gnu_parallel::identity_selector<RandomAccessIterator>
2223 functionality;
2224 __gnu_parallel::
2225 for_each_template_random_access(begin, end,
2226 __gnu_parallel::nothing(),
2227 functionality,
2228 __gnu_parallel::
2229 max_element_reduct<Comparator,
2230 RandomAccessIterator>(comp),
2231 res, res, -1, parallelism_tag);
2232 return res;
2233 }
2234 else
2235 return max_element(begin, end, comp, __gnu_parallel::sequential_tag());
2236 }
2237
2238 // Public interface, insert default comparator
2239 template<typename ForwardIterator>
2240 inline ForwardIterator
2241 max_element(ForwardIterator begin, ForwardIterator end,
2242 __gnu_parallel::_Parallelism parallelism_tag)
2243 {
2244 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2245 return max_element(begin, end, std::less<value_type>(), parallelism_tag);
2246 }
2247
2248 template<typename ForwardIterator>
2249 inline ForwardIterator
2250 max_element(ForwardIterator begin, ForwardIterator end)
2251 {
2252 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2253 return max_element(begin, end, std::less<value_type>());
2254 }
2255
2256 // Public interface
2257 template<typename ForwardIterator, typename Comparator>
2258 inline ForwardIterator
2259 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2260 __gnu_parallel::_Parallelism parallelism_tag)
2261 {
2262 typedef iterator_traits<ForwardIterator> traits_type;
2263 typedef typename traits_type::iterator_category iterator_category;
2264 return max_element_switch(begin, end, comp, iterator_category(),
2265 parallelism_tag);
2266 }
2267
2268 template<typename ForwardIterator, typename Comparator>
2269 inline ForwardIterator
2270 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
2271 {
2272 typedef iterator_traits<ForwardIterator> traits_type;
2273 typedef typename traits_type::iterator_category iterator_category;
2274 return max_element_switch(begin, end, comp, iterator_category());
2275 }
2276
2277
2278 // Sequential fallback
2279 template<typename ForwardIterator>
2280 inline ForwardIterator
2281 min_element(ForwardIterator begin, ForwardIterator end,
2282 __gnu_parallel::sequential_tag)
2283 { return _GLIBCXX_STD_P::min_element(begin, end); }
2284
2285 // Sequential fallback
2286 template<typename ForwardIterator, typename Comparator>
2287 inline ForwardIterator
2288 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2289 __gnu_parallel::sequential_tag)
2290 { return _GLIBCXX_STD_P::min_element(begin, end, comp); }
2291
2292 // Sequential fallback for input iterator case
2293 template<typename ForwardIterator, typename Comparator, typename IteratorTag>
2294 inline ForwardIterator
2295 min_element_switch(ForwardIterator begin, ForwardIterator end,
2296 Comparator comp, IteratorTag)
2297 { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
2298
2299 // Parallel algorithm for random access iterators
2300 template<typename RandomAccessIterator, typename Comparator>
2301 RandomAccessIterator
2302 min_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
2303 Comparator comp, random_access_iterator_tag,
2304 __gnu_parallel::_Parallelism parallelism_tag
2305 = __gnu_parallel::parallel_balanced)
2306 {
2307 if (_GLIBCXX_PARALLEL_CONDITION(
2308 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2309 >= __gnu_parallel::_Settings::get().min_element_minimal_n
2310 && __gnu_parallel::is_parallel(parallelism_tag)))
2311 {
2312 RandomAccessIterator res(begin);
2313 __gnu_parallel::identity_selector<RandomAccessIterator>
2314 functionality;
2315 __gnu_parallel::
2316 for_each_template_random_access(begin, end,
2317 __gnu_parallel::nothing(),
2318 functionality,
2319 __gnu_parallel::
2320 min_element_reduct<Comparator,
2321 RandomAccessIterator>(comp),
2322 res, res, -1, parallelism_tag);
2323 return res;
2324 }
2325 else
2326 return min_element(begin, end, comp, __gnu_parallel::sequential_tag());
2327 }
2328
2329 // Public interface, insert default comparator
2330 template<typename ForwardIterator>
2331 inline ForwardIterator
2332 min_element(ForwardIterator begin, ForwardIterator end,
2333 __gnu_parallel::_Parallelism parallelism_tag)
2334 {
2335 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2336 return min_element(begin, end, std::less<value_type>(), parallelism_tag);
2337 }
2338
2339 template<typename ForwardIterator>
2340 inline ForwardIterator
2341 min_element(ForwardIterator begin, ForwardIterator end)
2342 {
2343 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2344 return min_element(begin, end, std::less<value_type>());
2345 }
2346
2347 // Public interface
2348 template<typename ForwardIterator, typename Comparator>
2349 inline ForwardIterator
2350 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2351 __gnu_parallel::_Parallelism parallelism_tag)
2352 {
2353 typedef iterator_traits<ForwardIterator> traits_type;
2354 typedef typename traits_type::iterator_category iterator_category;
2355 return min_element_switch(begin, end, comp, iterator_category(),
2356 parallelism_tag);
2357 }
2358
2359 template<typename ForwardIterator, typename Comparator>
2360 inline ForwardIterator
2361 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
2362 {
2363 typedef iterator_traits<ForwardIterator> traits_type;
2364 typedef typename traits_type::iterator_category iterator_category;
2365 return min_element_switch(begin, end, comp, iterator_category());
2366 }
2367 } // end namespace
2368 } // end namespace
2369
2370 #endif /* _GLIBCXX_PARALLEL_ALGO_H */
Mirror of the offical gcc git repository hosted at gcc.gnu.org