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