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