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