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