]>
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 | |
1acba85b | 295 | return find_first_of(__begin1, __end1, __begin2, __end2, __gnu_parallel:: |
4459d22e | 296 | _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 PC |
1045 | |
1046 | if (_GLIBCXX_PARALLEL_CONDITION(true)) | |
d7066497 | 1047 | return __gnu_parallel:: |
15ac3c72 JS |
1048 | __search_template( |
1049 | __begin1, __end1, __begin2, __end2, | |
4459d22e | 1050 | __gnu_parallel::_EqualTo<_ValueType1, _ValueType2>()); |
531898c3 | 1051 | else |
1acba85b | 1052 | return search(__begin1, __end1, __begin2, __end2, |
d7066497 | 1053 | __gnu_parallel::sequential_tag()); |
531898c3 | 1054 | } |
c2ba9709 JS |
1055 | |
1056 | // Sequential fallback for input iterator case | |
15ac3c72 | 1057 | template<typename _FIterator1, typename _FIterator2, |
1acba85b | 1058 | typename _IteratorTag1, typename _IteratorTag2> |
15ac3c72 JS |
1059 | inline _FIterator1 |
1060 | __search_switch(_FIterator1 __begin1, _FIterator1 __end1, | |
1061 | _FIterator2 __begin2, _FIterator2 __end2, | |
1acba85b JS |
1062 | _IteratorTag1, _IteratorTag2) |
1063 | { return search(__begin1, __end1, __begin2, __end2, | |
d7066497 | 1064 | __gnu_parallel::sequential_tag()); } |
c2ba9709 JS |
1065 | |
1066 | // Public interface. | |
15ac3c72 JS |
1067 | template<typename _FIterator1, typename _FIterator2> |
1068 | inline _FIterator1 | |
1069 | search(_FIterator1 __begin1, _FIterator1 __end1, | |
1070 | _FIterator2 __begin2, _FIterator2 __end2) | |
531898c3 | 1071 | { |
4459d22e JS |
1072 | typedef std::iterator_traits<_FIterator1> _Iterator1Traits; |
1073 | typedef typename _Iterator1Traits::iterator_category _IteratorCategory1; | |
1074 | typedef std::iterator_traits<_FIterator2> _Iterator2Traits; | |
1075 | typedef typename _Iterator2Traits::iterator_category _IteratorCategory2; | |
531898c3 | 1076 | |
1acba85b JS |
1077 | return __search_switch(__begin1, __end1, __begin2, __end2, |
1078 | _IteratorCategory1(), _IteratorCategory2()); | |
531898c3 | 1079 | } |
c2ba9709 JS |
1080 | |
1081 | // Public interface. | |
15ac3c72 | 1082 | template<typename _FIterator1, typename _FIterator2, |
1acba85b | 1083 | typename _BinaryPredicate> |
15ac3c72 JS |
1084 | inline _FIterator1 |
1085 | search(_FIterator1 __begin1, _FIterator1 __end1, | |
1086 | _FIterator2 __begin2, _FIterator2 __end2, | |
1acba85b | 1087 | _BinaryPredicate __pred, __gnu_parallel::sequential_tag) |
15ac3c72 JS |
1088 | { return _GLIBCXX_STD_P::search( |
1089 | __begin1, __end1, __begin2, __end2, __pred); } | |
c2ba9709 JS |
1090 | |
1091 | // Parallel algorithm for random access iterator. | |
1acba85b JS |
1092 | template<typename _RAIter1, typename _RAIter2, |
1093 | typename _BinaryPredicate> | |
1094 | _RAIter1 | |
1095 | __search_switch(_RAIter1 __begin1, _RAIter1 __end1, | |
1096 | _RAIter2 __begin2, _RAIter2 __end2, | |
1097 | _BinaryPredicate __pred, | |
d7066497 | 1098 | random_access_iterator_tag, random_access_iterator_tag) |
531898c3 PC |
1099 | { |
1100 | if (_GLIBCXX_PARALLEL_CONDITION(true)) | |
1acba85b JS |
1101 | return __gnu_parallel::__search_template(__begin1, __end1, |
1102 | __begin2, __end2, __pred); | |
531898c3 | 1103 | else |
1acba85b | 1104 | return search(__begin1, __end1, __begin2, __end2, __pred, |
d7066497 | 1105 | __gnu_parallel::sequential_tag()); |
531898c3 | 1106 | } |
c2ba9709 JS |
1107 | |
1108 | // Sequential fallback for input iterator case | |
15ac3c72 | 1109 | template<typename _FIterator1, typename _FIterator2, |
1acba85b JS |
1110 | typename _BinaryPredicate, typename _IteratorTag1, |
1111 | typename _IteratorTag2> | |
15ac3c72 JS |
1112 | inline _FIterator1 |
1113 | __search_switch(_FIterator1 __begin1, _FIterator1 __end1, | |
1114 | _FIterator2 __begin2, _FIterator2 __end2, | |
1acba85b JS |
1115 | _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2) |
1116 | { return search(__begin1, __end1, __begin2, __end2, __pred, | |
d7066497 | 1117 | __gnu_parallel::sequential_tag()); } |
c2ba9709 JS |
1118 | |
1119 | // Public interface | |
15ac3c72 | 1120 | template<typename _FIterator1, typename _FIterator2, |
1acba85b | 1121 | typename _BinaryPredicate> |
15ac3c72 JS |
1122 | inline _FIterator1 |
1123 | search(_FIterator1 __begin1, _FIterator1 __end1, | |
1124 | _FIterator2 __begin2, _FIterator2 __end2, | |
1acba85b | 1125 | _BinaryPredicate __pred) |
531898c3 | 1126 | { |
4459d22e JS |
1127 | typedef std::iterator_traits<_FIterator1> _Iterator1Traits; |
1128 | typedef typename _Iterator1Traits::iterator_category _IteratorCategory1; | |
1129 | typedef std::iterator_traits<_FIterator2> _Iterator2Traits; | |
1130 | typedef typename _Iterator2Traits::iterator_category _IteratorCategory2; | |
1acba85b JS |
1131 | return __search_switch(__begin1, __end1, __begin2, __end2, __pred, |
1132 | _IteratorCategory1(), _IteratorCategory2()); | |
531898c3 | 1133 | } |
c2ba9709 JS |
1134 | |
1135 | // Sequential fallback | |
15ac3c72 JS |
1136 | template<typename _FIterator, typename _Integer, typename _Tp> |
1137 | inline _FIterator | |
4459d22e | 1138 | search_n(_FIterator __begin, _FIterator __end, _Integer __count, |
1acba85b | 1139 | const _Tp& __val, __gnu_parallel::sequential_tag) |
4459d22e | 1140 | { return _GLIBCXX_STD_P::search_n(__begin, __end, __count, __val); } |
c2ba9709 JS |
1141 | |
1142 | // Sequential fallback | |
15ac3c72 | 1143 | template<typename _FIterator, typename _Integer, typename _Tp, |
1acba85b | 1144 | typename _BinaryPredicate> |
15ac3c72 | 1145 | inline _FIterator |
4459d22e | 1146 | search_n(_FIterator __begin, _FIterator __end, _Integer __count, |
1acba85b | 1147 | const _Tp& __val, _BinaryPredicate __binary_pred, |
d7066497 | 1148 | __gnu_parallel::sequential_tag) |
15ac3c72 | 1149 | { return _GLIBCXX_STD_P::search_n( |
4459d22e | 1150 | __begin, __end, __count, __val, __binary_pred); } |
c2ba9709 JS |
1151 | |
1152 | // Public interface. | |
15ac3c72 JS |
1153 | template<typename _FIterator, typename _Integer, typename _Tp> |
1154 | inline _FIterator | |
4459d22e | 1155 | search_n(_FIterator __begin, _FIterator __end, _Integer __count, |
1acba85b | 1156 | const _Tp& __val) |
531898c3 | 1157 | { |
15ac3c72 | 1158 | typedef typename iterator_traits<_FIterator>::value_type _ValueType; |
4459d22e JS |
1159 | return search_n(__begin, __end, __count, __val, |
1160 | __gnu_parallel::_EqualTo<_ValueType, _Tp>()); | |
531898c3 | 1161 | } |
c2ba9709 JS |
1162 | |
1163 | // Parallel algorithm for random access iterators. | |
1acba85b JS |
1164 | template<typename _RAIter, typename _Integer, |
1165 | typename _Tp, typename _BinaryPredicate> | |
1166 | _RAIter | |
4459d22e | 1167 | __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count, |
15ac3c72 JS |
1168 | const _Tp& __val, _BinaryPredicate __binary_pred, |
1169 | random_access_iterator_tag) | |
531898c3 PC |
1170 | { |
1171 | if (_GLIBCXX_PARALLEL_CONDITION(true)) | |
d7066497 | 1172 | { |
4459d22e | 1173 | __gnu_parallel::_PseudoSequence<_Tp, _Integer> __ps(__val, __count); |
15ac3c72 JS |
1174 | return __gnu_parallel::__search_template( |
1175 | __begin, __end, __ps.begin(), __ps.end(), __binary_pred); | |
d7066497 | 1176 | } |
531898c3 | 1177 | else |
4459d22e | 1178 | return std::__search_n(__begin, __end, __count, __val, |
1acba85b | 1179 | __binary_pred, random_access_iterator_tag()); |
531898c3 | 1180 | } |
c2ba9709 JS |
1181 | |
1182 | // Sequential fallback for input iterator case. | |
15ac3c72 | 1183 | template<typename _FIterator, typename _Integer, typename _Tp, |
1acba85b | 1184 | typename _BinaryPredicate, typename _IteratorTag> |
15ac3c72 | 1185 | inline _FIterator |
4459d22e | 1186 | __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count, |
15ac3c72 JS |
1187 | const _Tp& __val, _BinaryPredicate __binary_pred, |
1188 | _IteratorTag) | |
4459d22e | 1189 | { return __search_n(__begin, __end, __count, __val, __binary_pred, |
15ac3c72 | 1190 | _IteratorTag()); } |
c2ba9709 JS |
1191 | |
1192 | // Public interface. | |
15ac3c72 | 1193 | template<typename _FIterator, typename _Integer, typename _Tp, |
1acba85b | 1194 | typename _BinaryPredicate> |
15ac3c72 | 1195 | inline _FIterator |
4459d22e | 1196 | search_n(_FIterator __begin, _FIterator __end, _Integer __count, |
1acba85b JS |
1197 | const _Tp& __val, _BinaryPredicate __binary_pred) |
1198 | { | |
4459d22e | 1199 | return __search_n_switch(__begin, __end, __count, __val, __binary_pred, |
15ac3c72 | 1200 | typename std::iterator_traits<_FIterator>:: |
d7066497 | 1201 | iterator_category()); |
531898c3 | 1202 | } |
c2ba9709 | 1203 | |
6f95a65a | 1204 | |
c2ba9709 | 1205 | // Sequential fallback. |
1acba85b JS |
1206 | template<typename _IIter, typename _OutputIterator, |
1207 | typename _UnaryOperation> | |
1208 | inline _OutputIterator | |
1209 | transform(_IIter __begin, _IIter __end, _OutputIterator __result, | |
4459d22e JS |
1210 | _UnaryOperation __unary_op, __gnu_parallel::sequential_tag) |
1211 | { return _GLIBCXX_STD_P::transform(__begin, __end, __result, __unary_op); } | |
c2ba9709 JS |
1212 | |
1213 | // Parallel unary transform for random access iterators. | |
1acba85b JS |
1214 | template<typename _RAIter1, typename _RAIter2, |
1215 | typename _UnaryOperation> | |
1216 | _RAIter2 | |
1217 | __transform1_switch(_RAIter1 __begin, _RAIter1 __end, | |
4459d22e | 1218 | _RAIter2 __result, _UnaryOperation __unary_op, |
d7066497 | 1219 | random_access_iterator_tag, random_access_iterator_tag, |
1acba85b | 1220 | __gnu_parallel::_Parallelism __parallelism_tag |
d7066497 | 1221 | = __gnu_parallel::parallel_balanced) |
531898c3 | 1222 | { |
5817ff8e | 1223 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 1224 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
d7066497 | 1225 | >= __gnu_parallel::_Settings::get().transform_minimal_n |
1acba85b | 1226 | && __gnu_parallel::__is_parallel(__parallelism_tag))) |
d7066497 | 1227 | { |
1acba85b JS |
1228 | bool __dummy = true; |
1229 | typedef __gnu_parallel::_IteratorPair<_RAIter1, | |
1230 | _RAIter2, random_access_iterator_tag> _ItTrip; | |
78605f0a JS |
1231 | _ItTrip __begin_pair(__begin, __result), |
1232 | __end_pair(__end, __result + (__end - __begin)); | |
1acba85b | 1233 | __gnu_parallel::__transform1_selector<_ItTrip> __functionality; |
d7066497 | 1234 | __gnu_parallel:: |
15ac3c72 | 1235 | __for_each_template_random_access( |
78605f0a | 1236 | __begin_pair, __end_pair, __unary_op, __functionality, |
15ac3c72 JS |
1237 | __gnu_parallel::_DummyReduct(), |
1238 | __dummy, __dummy, -1, __parallelism_tag); | |
54384f7f | 1239 | return __functionality._M_finish_iterator; |
d7066497 | 1240 | } |
531898c3 | 1241 | else |
4459d22e | 1242 | return transform(__begin, __end, __result, __unary_op, |
d7066497 | 1243 | __gnu_parallel::sequential_tag()); |
531898c3 | 1244 | } |
c2ba9709 JS |
1245 | |
1246 | // Sequential fallback for input iterator case. | |
1acba85b JS |
1247 | template<typename _RAIter1, typename _RAIter2, |
1248 | typename _UnaryOperation, typename _IteratorTag1, | |
1249 | typename _IteratorTag2> | |
1250 | inline _RAIter2 | |
1251 | __transform1_switch(_RAIter1 __begin, _RAIter1 __end, | |
4459d22e | 1252 | _RAIter2 __result, _UnaryOperation __unary_op, |
1acba85b | 1253 | _IteratorTag1, _IteratorTag2) |
4459d22e | 1254 | { return transform(__begin, __end, __result, __unary_op, |
d7066497 | 1255 | __gnu_parallel::sequential_tag()); } |
6f95a65a BK |
1256 | |
1257 | // Public interface. | |
1acba85b JS |
1258 | template<typename _IIter, typename _OutputIterator, |
1259 | typename _UnaryOperation> | |
1260 | inline _OutputIterator | |
1261 | transform(_IIter __begin, _IIter __end, _OutputIterator __result, | |
4459d22e | 1262 | _UnaryOperation __unary_op, |
1acba85b | 1263 | __gnu_parallel::_Parallelism __parallelism_tag) |
531898c3 | 1264 | { |
1acba85b JS |
1265 | typedef std::iterator_traits<_IIter> _IIterTraits; |
1266 | typedef std::iterator_traits<_OutputIterator> _OIterTraits; | |
1267 | typedef typename _IIterTraits::iterator_category _IIteratorCategory; | |
1268 | typedef typename _OIterTraits::iterator_category _OIterCategory; | |
531898c3 | 1269 | |
4459d22e | 1270 | return __transform1_switch(__begin, __end, __result, __unary_op, |
1acba85b JS |
1271 | _IIteratorCategory(), _OIterCategory(), |
1272 | __parallelism_tag); | |
531898c3 PC |
1273 | } |
1274 | ||
1acba85b JS |
1275 | template<typename _IIter, typename _OutputIterator, |
1276 | typename _UnaryOperation> | |
1277 | inline _OutputIterator | |
1278 | transform(_IIter __begin, _IIter __end, _OutputIterator __result, | |
4459d22e | 1279 | _UnaryOperation __unary_op) |
531898c3 | 1280 | { |
1acba85b JS |
1281 | typedef std::iterator_traits<_IIter> _IIterTraits; |
1282 | typedef std::iterator_traits<_OutputIterator> _OIterTraits; | |
1283 | typedef typename _IIterTraits::iterator_category _IIteratorCategory; | |
1284 | typedef typename _OIterTraits::iterator_category _OIterCategory; | |
531898c3 | 1285 | |
4459d22e | 1286 | return __transform1_switch(__begin, __end, __result, __unary_op, |
1acba85b | 1287 | _IIteratorCategory(), _OIterCategory()); |
531898c3 | 1288 | } |
c2ba9709 JS |
1289 | |
1290 | ||
6f95a65a | 1291 | // Sequential fallback |
1acba85b JS |
1292 | template<typename _IIter1, typename _IIter2, |
1293 | typename _OutputIterator, typename _BinaryOperation> | |
1294 | inline _OutputIterator | |
1295 | transform(_IIter1 __begin1, _IIter1 __end1, | |
1296 | _IIter2 __begin2, _OutputIterator __result, | |
1297 | _BinaryOperation __binary_op, __gnu_parallel::sequential_tag) | |
1298 | { return _GLIBCXX_STD_P::transform(__begin1, __end1, | |
1299 | __begin2, __result, __binary_op); } | |
6f95a65a | 1300 | |
c2ba9709 | 1301 | // Parallel binary transform for random access iterators. |
1acba85b JS |
1302 | template<typename _RAIter1, typename _RAIter2, |
1303 | typename _RAIter3, typename _BinaryOperation> | |
1304 | _RAIter3 | |
1305 | __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1, | |
1306 | _RAIter2 __begin2, | |
1307 | _RAIter3 __result, _BinaryOperation __binary_op, | |
d7066497 JS |
1308 | random_access_iterator_tag, random_access_iterator_tag, |
1309 | random_access_iterator_tag, | |
1acba85b | 1310 | __gnu_parallel::_Parallelism __parallelism_tag |
d7066497 | 1311 | = __gnu_parallel::parallel_balanced) |
531898c3 | 1312 | { |
5817ff8e | 1313 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 1314 | (__end1 - __begin1) >= |
d7066497 | 1315 | __gnu_parallel::_Settings::get().transform_minimal_n |
1acba85b | 1316 | && __gnu_parallel::__is_parallel(__parallelism_tag))) |
d7066497 | 1317 | { |
1acba85b JS |
1318 | bool __dummy = true; |
1319 | typedef __gnu_parallel::_IteratorTriple<_RAIter1, | |
1320 | _RAIter2, _RAIter3, | |
1321 | random_access_iterator_tag> _ItTrip; | |
1322 | _ItTrip __begin_triple(__begin1, __begin2, __result), | |
1323 | __end_triple(__end1, __begin2 + (__end1 - __begin1), | |
1324 | __result + (__end1 - __begin1)); | |
1325 | __gnu_parallel::__transform2_selector<_ItTrip> __functionality; | |
d7066497 | 1326 | __gnu_parallel:: |
1acba85b JS |
1327 | __for_each_template_random_access(__begin_triple, __end_triple, |
1328 | __binary_op, __functionality, | |
1329 | __gnu_parallel::_DummyReduct(), | |
1330 | __dummy, __dummy, -1, | |
1331 | __parallelism_tag); | |
54384f7f | 1332 | return __functionality._M_finish_iterator; |
d7066497 | 1333 | } |
531898c3 | 1334 | else |
1acba85b | 1335 | return transform(__begin1, __end1, __begin2, __result, __binary_op, |
d7066497 | 1336 | __gnu_parallel::sequential_tag()); |
531898c3 | 1337 | } |
c2ba9709 JS |
1338 | |
1339 | // Sequential fallback for input iterator case. | |
1acba85b JS |
1340 | template<typename _IIter1, typename _IIter2, |
1341 | typename _OutputIterator, typename _BinaryOperation, | |
1342 | typename _Tag1, typename _Tag2, typename _Tag3> | |
1343 | inline _OutputIterator | |
1344 | __transform2_switch(_IIter1 __begin1, _IIter1 __end1, | |
1345 | _IIter2 __begin2, _OutputIterator __result, | |
1346 | _BinaryOperation __binary_op, _Tag1, _Tag2, _Tag3) | |
1347 | { return transform(__begin1, __end1, __begin2, __result, __binary_op, | |
d7066497 | 1348 | __gnu_parallel::sequential_tag()); } |
c2ba9709 JS |
1349 | |
1350 | // Public interface. | |
1acba85b JS |
1351 | template<typename _IIter1, typename _IIter2, |
1352 | typename _OutputIterator, typename _BinaryOperation> | |
1353 | inline _OutputIterator | |
1354 | transform(_IIter1 __begin1, _IIter1 __end1, | |
1355 | _IIter2 __begin2, _OutputIterator __result, | |
1356 | _BinaryOperation __binary_op, | |
1357 | __gnu_parallel::_Parallelism __parallelism_tag) | |
1358 | { | |
1359 | typedef std::iterator_traits<_IIter1> _IIterTraits1; | |
1360 | typedef typename _IIterTraits1::iterator_category | |
1361 | _IIterCategory1; | |
1362 | typedef std::iterator_traits<_IIter2> _IIterTraits2; | |
1363 | typedef typename _IIterTraits2::iterator_category | |
1364 | _IIterCategory2; | |
1365 | typedef std::iterator_traits<_OutputIterator> _OIterTraits; | |
1366 | typedef typename _OIterTraits::iterator_category _OIterCategory; | |
1367 | ||
15ac3c72 JS |
1368 | return __transform2_switch( |
1369 | __begin1, __end1, __begin2, __result, __binary_op, | |
1370 | _IIterCategory1(), _IIterCategory2(), _OIterCategory(), | |
1371 | __parallelism_tag); | |
1acba85b JS |
1372 | } |
1373 | ||
1374 | template<typename _IIter1, typename _IIter2, | |
1375 | typename _OutputIterator, typename _BinaryOperation> | |
1376 | inline _OutputIterator | |
1377 | transform(_IIter1 __begin1, _IIter1 __end1, | |
1378 | _IIter2 __begin2, _OutputIterator __result, | |
1379 | _BinaryOperation __binary_op) | |
1380 | { | |
1381 | typedef std::iterator_traits<_IIter1> _IIterTraits1; | |
1382 | typedef typename _IIterTraits1::iterator_category | |
1383 | _IIterCategory1; | |
1384 | typedef std::iterator_traits<_IIter2> _IIterTraits2; | |
1385 | typedef typename _IIterTraits2::iterator_category | |
1386 | _IIterCategory2; | |
1387 | typedef std::iterator_traits<_OutputIterator> _OIterTraits; | |
1388 | typedef typename _OIterTraits::iterator_category _OIterCategory; | |
1389 | ||
15ac3c72 JS |
1390 | return __transform2_switch( |
1391 | __begin1, __end1, __begin2, __result, __binary_op, | |
1392 | _IIterCategory1(), _IIterCategory2(), _OIterCategory()); | |
531898c3 | 1393 | } |
c2ba9709 JS |
1394 | |
1395 | // Sequential fallback | |
15ac3c72 | 1396 | template<typename _FIterator, typename _Tp> |
531898c3 | 1397 | inline void |
15ac3c72 | 1398 | replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, |
1acba85b JS |
1399 | const _Tp& __new_value, __gnu_parallel::sequential_tag) |
1400 | { _GLIBCXX_STD_P::replace(__begin, __end, __old_value, __new_value); } | |
c2ba9709 JS |
1401 | |
1402 | // Sequential fallback for input iterator case | |
15ac3c72 | 1403 | template<typename _FIterator, typename _Tp, typename _IteratorTag> |
531898c3 | 1404 | inline void |
15ac3c72 JS |
1405 | __replace_switch(_FIterator __begin, _FIterator __end, |
1406 | const _Tp& __old_value, const _Tp& __new_value, | |
1407 | _IteratorTag) | |
1acba85b | 1408 | { replace(__begin, __end, __old_value, __new_value, |
d7066497 | 1409 | __gnu_parallel::sequential_tag()); } |
c2ba9709 JS |
1410 | |
1411 | // Parallel replace for random access iterators | |
1acba85b | 1412 | template<typename _RAIter, typename _Tp> |
531898c3 | 1413 | inline void |
1acba85b JS |
1414 | __replace_switch(_RAIter __begin, _RAIter __end, |
1415 | const _Tp& __old_value, const _Tp& __new_value, | |
d7066497 | 1416 | random_access_iterator_tag, |
1acba85b | 1417 | __gnu_parallel::_Parallelism __parallelism_tag |
d7066497 | 1418 | = __gnu_parallel::parallel_balanced) |
531898c3 PC |
1419 | { |
1420 | // XXX parallel version is where? | |
1acba85b | 1421 | replace(__begin, __end, __old_value, __new_value, |
d7066497 | 1422 | __gnu_parallel::sequential_tag()); |
531898c3 | 1423 | } |
c2ba9709 JS |
1424 | |
1425 | // Public interface | |
15ac3c72 | 1426 | template<typename _FIterator, typename _Tp> |
531898c3 | 1427 | inline void |
15ac3c72 JS |
1428 | replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, |
1429 | const _Tp& __new_value, | |
1430 | __gnu_parallel::_Parallelism __parallelism_tag) | |
531898c3 | 1431 | { |
15ac3c72 | 1432 | typedef iterator_traits<_FIterator> _TraitsType; |
1acba85b | 1433 | typedef typename _TraitsType::iterator_category _IteratorCategory; |
15ac3c72 JS |
1434 | __replace_switch(__begin, __end, __old_value, __new_value, |
1435 | _IteratorCategory(), | |
1acba85b | 1436 | __parallelism_tag); |
531898c3 | 1437 | } |
6f95a65a | 1438 | |
15ac3c72 | 1439 | template<typename _FIterator, typename _Tp> |
531898c3 | 1440 | inline void |
15ac3c72 | 1441 | replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, |
1acba85b | 1442 | const _Tp& __new_value) |
531898c3 | 1443 | { |
15ac3c72 | 1444 | typedef iterator_traits<_FIterator> _TraitsType; |
1acba85b | 1445 | typedef typename _TraitsType::iterator_category _IteratorCategory; |
15ac3c72 JS |
1446 | __replace_switch(__begin, __end, __old_value, __new_value, |
1447 | _IteratorCategory()); | |
531898c3 | 1448 | } |
c2ba9709 JS |
1449 | |
1450 | ||
1451 | // Sequential fallback | |
15ac3c72 | 1452 | template<typename _FIterator, typename _Predicate, typename _Tp> |
531898c3 | 1453 | inline void |
15ac3c72 | 1454 | replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred, |
1acba85b JS |
1455 | const _Tp& __new_value, __gnu_parallel::sequential_tag) |
1456 | { _GLIBCXX_STD_P::replace_if(__begin, __end, __pred, __new_value); } | |
c2ba9709 JS |
1457 | |
1458 | // Sequential fallback for input iterator case | |
15ac3c72 | 1459 | template<typename _FIterator, typename _Predicate, typename _Tp, |
1acba85b | 1460 | typename _IteratorTag> |
531898c3 | 1461 | inline void |
15ac3c72 | 1462 | __replace_if_switch(_FIterator __begin, _FIterator __end, |
1acba85b JS |
1463 | _Predicate __pred, const _Tp& __new_value, _IteratorTag) |
1464 | { replace_if(__begin, __end, __pred, __new_value, | |
d7066497 | 1465 | __gnu_parallel::sequential_tag()); } |
c2ba9709 JS |
1466 | |
1467 | // Parallel algorithm for random access iterators. | |
1acba85b | 1468 | template<typename _RAIter, typename _Predicate, typename _Tp> |
531898c3 | 1469 | void |
1acba85b JS |
1470 | __replace_if_switch(_RAIter __begin, _RAIter __end, |
1471 | _Predicate __pred, const _Tp& __new_value, | |
d7066497 | 1472 | random_access_iterator_tag, |
1acba85b | 1473 | __gnu_parallel::_Parallelism __parallelism_tag |
d7066497 | 1474 | = __gnu_parallel::parallel_balanced) |
531898c3 | 1475 | { |
5817ff8e | 1476 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 1477 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
d7066497 | 1478 | >= __gnu_parallel::_Settings::get().replace_minimal_n |
1acba85b | 1479 | && __gnu_parallel::__is_parallel(__parallelism_tag))) |
d7066497 | 1480 | { |
1acba85b | 1481 | bool __dummy; |
d7066497 | 1482 | __gnu_parallel:: |
1acba85b JS |
1483 | __replace_if_selector<_RAIter, _Predicate, _Tp> |
1484 | __functionality(__new_value); | |
d7066497 | 1485 | __gnu_parallel:: |
15ac3c72 JS |
1486 | __for_each_template_random_access( |
1487 | __begin, __end, __pred, __functionality, | |
1488 | __gnu_parallel::_DummyReduct(), | |
1489 | true, __dummy, -1, __parallelism_tag); | |
d7066497 | 1490 | } |
531898c3 | 1491 | else |
1acba85b | 1492 | replace_if(__begin, __end, __pred, __new_value, |
d7066497 | 1493 | __gnu_parallel::sequential_tag()); |
531898c3 | 1494 | } |
c2ba9709 JS |
1495 | |
1496 | // Public interface. | |
15ac3c72 | 1497 | template<typename _FIterator, typename _Predicate, typename _Tp> |
531898c3 | 1498 | inline void |
15ac3c72 | 1499 | replace_if(_FIterator __begin, _FIterator __end, |
1acba85b JS |
1500 | _Predicate __pred, const _Tp& __new_value, |
1501 | __gnu_parallel::_Parallelism __parallelism_tag) | |
531898c3 | 1502 | { |
15ac3c72 | 1503 | typedef std::iterator_traits<_FIterator> _IteratorTraits; |
1acba85b | 1504 | typedef typename _IteratorTraits::iterator_category _IteratorCategory; |
15ac3c72 JS |
1505 | __replace_if_switch(__begin, __end, __pred, __new_value, |
1506 | _IteratorCategory(), __parallelism_tag); | |
531898c3 | 1507 | } |
c2ba9709 | 1508 | |
15ac3c72 | 1509 | template<typename _FIterator, typename _Predicate, typename _Tp> |
531898c3 | 1510 | inline void |
15ac3c72 | 1511 | replace_if(_FIterator __begin, _FIterator __end, |
1acba85b | 1512 | _Predicate __pred, const _Tp& __new_value) |
531898c3 | 1513 | { |
15ac3c72 | 1514 | typedef std::iterator_traits<_FIterator> _IteratorTraits; |
1acba85b | 1515 | typedef typename _IteratorTraits::iterator_category _IteratorCategory; |
15ac3c72 JS |
1516 | __replace_if_switch(__begin, __end, __pred, __new_value, |
1517 | _IteratorCategory()); | |
531898c3 | 1518 | } |
c2ba9709 JS |
1519 | |
1520 | // Sequential fallback | |
4459d22e | 1521 | template<typename _FIterator, typename _Generator> |
531898c3 | 1522 | inline void |
4459d22e | 1523 | generate(_FIterator __begin, _FIterator __end, _Generator __gen, |
d7066497 | 1524 | __gnu_parallel::sequential_tag) |
1acba85b | 1525 | { _GLIBCXX_STD_P::generate(__begin, __end, __gen); } |
c2ba9709 JS |
1526 | |
1527 | // Sequential fallback for input iterator case. | |
4459d22e | 1528 | template<typename _FIterator, typename _Generator, typename _IteratorTag> |
531898c3 | 1529 | inline void |
4459d22e | 1530 | __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen, |
1acba85b JS |
1531 | _IteratorTag) |
1532 | { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); } | |
c2ba9709 JS |
1533 | |
1534 | // Parallel algorithm for random access iterators. | |
4459d22e | 1535 | template<typename _RAIter, typename _Generator> |
531898c3 | 1536 | void |
1acba85b | 1537 | __generate_switch(_RAIter __begin, _RAIter __end, |
4459d22e | 1538 | _Generator __gen, random_access_iterator_tag, |
1acba85b | 1539 | __gnu_parallel::_Parallelism __parallelism_tag |
d7066497 | 1540 | = __gnu_parallel::parallel_balanced) |
531898c3 | 1541 | { |
5817ff8e | 1542 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 1543 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
d7066497 | 1544 | >= __gnu_parallel::_Settings::get().generate_minimal_n |
1acba85b | 1545 | && __gnu_parallel::__is_parallel(__parallelism_tag))) |
d7066497 | 1546 | { |
1acba85b JS |
1547 | bool __dummy; |
1548 | __gnu_parallel::__generate_selector<_RAIter> | |
1549 | __functionality; | |
d7066497 | 1550 | __gnu_parallel:: |
15ac3c72 JS |
1551 | __for_each_template_random_access( |
1552 | __begin, __end, __gen, __functionality, | |
1553 | __gnu_parallel::_DummyReduct(), | |
1554 | true, __dummy, -1, __parallelism_tag); | |
d7066497 | 1555 | } |
531898c3 | 1556 | else |
1acba85b | 1557 | generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); |
531898c3 | 1558 | } |
c2ba9709 JS |
1559 | |
1560 | // Public interface. | |
4459d22e | 1561 | template<typename _FIterator, typename _Generator> |
531898c3 | 1562 | inline void |
15ac3c72 | 1563 | generate(_FIterator __begin, _FIterator __end, |
4459d22e | 1564 | _Generator __gen, __gnu_parallel::_Parallelism __parallelism_tag) |
531898c3 | 1565 | { |
15ac3c72 | 1566 | typedef std::iterator_traits<_FIterator> _IteratorTraits; |
1acba85b | 1567 | typedef typename _IteratorTraits::iterator_category _IteratorCategory; |
15ac3c72 JS |
1568 | __generate_switch(__begin, __end, __gen, _IteratorCategory(), |
1569 | __parallelism_tag); | |
531898c3 | 1570 | } |
c2ba9709 | 1571 | |
4459d22e | 1572 | template<typename _FIterator, typename _Generator> |
531898c3 | 1573 | inline void |
4459d22e | 1574 | generate(_FIterator __begin, _FIterator __end, _Generator __gen) |
531898c3 | 1575 | { |
15ac3c72 | 1576 | typedef std::iterator_traits<_FIterator> _IteratorTraits; |
1acba85b JS |
1577 | typedef typename _IteratorTraits::iterator_category _IteratorCategory; |
1578 | __generate_switch(__begin, __end, __gen, _IteratorCategory()); | |
531898c3 | 1579 | } |
6f95a65a | 1580 | |
c2ba9709 JS |
1581 | |
1582 | // Sequential fallback. | |
4459d22e | 1583 | template<typename _OutputIterator, typename _Size, typename _Generator> |
1acba85b | 1584 | inline _OutputIterator |
4459d22e | 1585 | generate_n(_OutputIterator __begin, _Size __n, _Generator __gen, |
d7066497 | 1586 | __gnu_parallel::sequential_tag) |
1acba85b | 1587 | { return _GLIBCXX_STD_P::generate_n(__begin, __n, __gen); } |
c2ba9709 JS |
1588 | |
1589 | // Sequential fallback for input iterator case. | |
4459d22e | 1590 | template<typename _OutputIterator, typename _Size, typename _Generator, |
1acba85b JS |
1591 | typename _IteratorTag> |
1592 | inline _OutputIterator | |
4459d22e | 1593 | __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen, |
15ac3c72 JS |
1594 | _IteratorTag) |
1595 | { return generate_n(__begin, __n, __gen, | |
1596 | __gnu_parallel::sequential_tag()); } | |
c2ba9709 JS |
1597 | |
1598 | // Parallel algorithm for random access iterators. | |
4459d22e | 1599 | template<typename _RAIter, typename _Size, typename _Generator> |
1acba85b | 1600 | inline _RAIter |
4459d22e | 1601 | __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen, |
d7066497 | 1602 | random_access_iterator_tag, |
1acba85b | 1603 | __gnu_parallel::_Parallelism __parallelism_tag |
d7066497 | 1604 | = __gnu_parallel::parallel_balanced) |
531898c3 PC |
1605 | { |
1606 | // XXX parallel version is where? | |
15ac3c72 | 1607 | return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag()); |
531898c3 | 1608 | } |
c2ba9709 JS |
1609 | |
1610 | // Public interface. | |
4459d22e | 1611 | template<typename _OutputIterator, typename _Size, typename _Generator> |
1acba85b | 1612 | inline _OutputIterator |
4459d22e | 1613 | generate_n(_OutputIterator __begin, _Size __n, _Generator __gen, |
1acba85b | 1614 | __gnu_parallel::_Parallelism __parallelism_tag) |
531898c3 | 1615 | { |
1acba85b JS |
1616 | typedef std::iterator_traits<_OutputIterator> _IteratorTraits; |
1617 | typedef typename _IteratorTraits::iterator_category _IteratorCategory; | |
1618 | return __generate_n_switch(__begin, __n, __gen, _IteratorCategory(), | |
1619 | __parallelism_tag); | |
531898c3 | 1620 | } |
6f95a65a | 1621 | |
4459d22e | 1622 | template<typename _OutputIterator, typename _Size, typename _Generator> |
1acba85b | 1623 | inline _OutputIterator |
4459d22e | 1624 | generate_n(_OutputIterator __begin, _Size __n, _Generator __gen) |
531898c3 | 1625 | { |
1acba85b JS |
1626 | typedef std::iterator_traits<_OutputIterator> _IteratorTraits; |
1627 | typedef typename _IteratorTraits::iterator_category _IteratorCategory; | |
1628 | return __generate_n_switch(__begin, __n, __gen, _IteratorCategory()); | |
531898c3 | 1629 | } |
c2ba9709 JS |
1630 | |
1631 | ||
1632 | // Sequential fallback. | |
1acba85b | 1633 | template<typename _RAIter> |
531898c3 | 1634 | inline void |
1acba85b | 1635 | random_shuffle(_RAIter __begin, _RAIter __end, |
d7066497 | 1636 | __gnu_parallel::sequential_tag) |
1acba85b | 1637 | { _GLIBCXX_STD_P::random_shuffle(__begin, __end); } |
c2ba9709 JS |
1638 | |
1639 | // Sequential fallback. | |
4459d22e | 1640 | template<typename _RAIter, typename _RandomNumberGenerator> |
531898c3 | 1641 | inline void |
1acba85b | 1642 | random_shuffle(_RAIter __begin, _RAIter __end, |
4459d22e | 1643 | _RandomNumberGenerator& __rand, |
15ac3c72 | 1644 | __gnu_parallel::sequential_tag) |
1acba85b | 1645 | { _GLIBCXX_STD_P::random_shuffle(__begin, __end, __rand); } |
c2ba9709 JS |
1646 | |
1647 | ||
1648 | /** @brief Functor wrapper for std::rand(). */ | |
1acba85b | 1649 | template<typename _MustBeInt = int> |
54384f7f | 1650 | struct _CRandNumber |
531898c3 PC |
1651 | { |
1652 | int | |
1acba85b JS |
1653 | operator()(int __limit) |
1654 | { return rand() % __limit; } | |
531898c3 | 1655 | }; |
c2ba9709 JS |
1656 | |
1657 | // Fill in random number generator. | |
1acba85b | 1658 | template<typename _RAIter> |
531898c3 | 1659 | inline void |
1acba85b | 1660 | random_shuffle(_RAIter __begin, _RAIter __end) |
531898c3 | 1661 | { |
54384f7f | 1662 | _CRandNumber<> __r; |
531898c3 | 1663 | // Parallelization still possible. |
1acba85b | 1664 | __gnu_parallel::random_shuffle(__begin, __end, __r); |
531898c3 | 1665 | } |
c2ba9709 JS |
1666 | |
1667 | // Parallel algorithm for random access iterators. | |
4459d22e | 1668 | template<typename _RAIter, typename _RandomNumberGenerator> |
531898c3 | 1669 | void |
1acba85b | 1670 | random_shuffle(_RAIter __begin, _RAIter __end, |
4459d22e | 1671 | _RandomNumberGenerator& __rand) |
531898c3 | 1672 | { |
1acba85b | 1673 | if (__begin == __end) |
d7066497 | 1674 | return; |
5817ff8e | 1675 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 1676 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
d7066497 | 1677 | >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n)) |
1acba85b | 1678 | __gnu_parallel::__parallel_random_shuffle(__begin, __end, __rand); |
531898c3 | 1679 | else |
1acba85b | 1680 | __gnu_parallel::__sequential_random_shuffle(__begin, __end, __rand); |
531898c3 | 1681 | } |
c2ba9709 JS |
1682 | |
1683 | // Sequential fallback. | |
15ac3c72 JS |
1684 | template<typename _FIterator, typename _Predicate> |
1685 | inline _FIterator | |
1686 | partition(_FIterator __begin, _FIterator __end, | |
1acba85b JS |
1687 | _Predicate __pred, __gnu_parallel::sequential_tag) |
1688 | { return _GLIBCXX_STD_P::partition(__begin, __end, __pred); } | |
c2ba9709 JS |
1689 | |
1690 | // Sequential fallback for input iterator case. | |
15ac3c72 JS |
1691 | template<typename _FIterator, typename _Predicate, typename _IteratorTag> |
1692 | inline _FIterator | |
1693 | __partition_switch(_FIterator __begin, _FIterator __end, | |
1acba85b | 1694 | _Predicate __pred, _IteratorTag) |
15ac3c72 JS |
1695 | { return partition(__begin, __end, __pred, |
1696 | __gnu_parallel::sequential_tag()); } | |
c2ba9709 JS |
1697 | |
1698 | // Parallel algorithm for random access iterators. | |
1acba85b JS |
1699 | template<typename _RAIter, typename _Predicate> |
1700 | _RAIter | |
1701 | __partition_switch(_RAIter __begin, _RAIter __end, | |
1702 | _Predicate __pred, random_access_iterator_tag) | |
531898c3 | 1703 | { |
5817ff8e | 1704 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 1705 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
d7066497 JS |
1706 | >= __gnu_parallel::_Settings::get().partition_minimal_n)) |
1707 | { | |
1acba85b JS |
1708 | typedef typename std::iterator_traits<_RAIter>:: |
1709 | difference_type _DifferenceType; | |
1710 | _DifferenceType __middle = __gnu_parallel:: | |
1711 | __parallel_partition(__begin, __end, __pred, | |
1712 | __gnu_parallel::__get_max_threads()); | |
1713 | return __begin + __middle; | |
d7066497 | 1714 | } |
531898c3 | 1715 | else |
15ac3c72 JS |
1716 | return partition(__begin, __end, __pred, |
1717 | __gnu_parallel::sequential_tag()); | |
531898c3 | 1718 | } |
c2ba9709 JS |
1719 | |
1720 | // Public interface. | |
15ac3c72 JS |
1721 | template<typename _FIterator, typename _Predicate> |
1722 | inline _FIterator | |
1723 | partition(_FIterator __begin, _FIterator __end, _Predicate __pred) | |
531898c3 | 1724 | { |
15ac3c72 | 1725 | typedef iterator_traits<_FIterator> _TraitsType; |
1acba85b JS |
1726 | typedef typename _TraitsType::iterator_category _IteratorCategory; |
1727 | return __partition_switch(__begin, __end, __pred, _IteratorCategory()); | |
531898c3 | 1728 | } |
c2ba9709 | 1729 | |
d7066497 JS |
1730 | // sort interface |
1731 | ||
c2ba9709 | 1732 | // Sequential fallback |
1acba85b | 1733 | template<typename _RAIter> |
531898c3 | 1734 | inline void |
1acba85b | 1735 | sort(_RAIter __begin, _RAIter __end, |
d7066497 | 1736 | __gnu_parallel::sequential_tag) |
1acba85b | 1737 | { _GLIBCXX_STD_P::sort(__begin, __end); } |
c2ba9709 JS |
1738 | |
1739 | // Sequential fallback | |
1acba85b | 1740 | template<typename _RAIter, typename _Compare> |
531898c3 | 1741 | inline void |
1acba85b | 1742 | sort(_RAIter __begin, _RAIter __end, _Compare __comp, |
d7066497 | 1743 | __gnu_parallel::sequential_tag) |
1acba85b JS |
1744 | { _GLIBCXX_STD_P::sort<_RAIter, _Compare>(__begin, __end, |
1745 | __comp); } | |
d7066497 JS |
1746 | |
1747 | // Public interface | |
1acba85b JS |
1748 | template<typename _RAIter, typename _Compare, |
1749 | typename _Parallelism> | |
d7066497 | 1750 | void |
1acba85b JS |
1751 | sort(_RAIter __begin, _RAIter __end, _Compare __comp, |
1752 | _Parallelism __parallelism) | |
d7066497 | 1753 | { |
1acba85b JS |
1754 | typedef iterator_traits<_RAIter> _TraitsType; |
1755 | typedef typename _TraitsType::value_type _ValueType; | |
d7066497 | 1756 | |
1acba85b | 1757 | if (__begin != __end) |
d7066497 JS |
1758 | { |
1759 | if (_GLIBCXX_PARALLEL_CONDITION( | |
1acba85b | 1760 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >= |
d7066497 | 1761 | __gnu_parallel::_Settings::get().sort_minimal_n)) |
4459d22e | 1762 | __gnu_parallel::__parallel_sort<false>( |
15ac3c72 | 1763 | __begin, __end, __comp, __parallelism); |
d7066497 | 1764 | else |
1acba85b | 1765 | sort(__begin, __end, __comp, __gnu_parallel::sequential_tag()); |
d7066497 JS |
1766 | } |
1767 | } | |
c2ba9709 JS |
1768 | |
1769 | // Public interface, insert default comparator | |
1acba85b | 1770 | template<typename _RAIter> |
531898c3 | 1771 | inline void |
1acba85b | 1772 | sort(_RAIter __begin, _RAIter __end) |
531898c3 | 1773 | { |
1acba85b JS |
1774 | typedef iterator_traits<_RAIter> _TraitsType; |
1775 | typedef typename _TraitsType::value_type _ValueType; | |
1776 | sort(__begin, __end, std::less<_ValueType>(), | |
d7066497 | 1777 | __gnu_parallel::default_parallel_tag()); |
531898c3 | 1778 | } |
c2ba9709 | 1779 | |
d7066497 | 1780 | // Public interface, insert default comparator |
1acba85b | 1781 | template<typename _RAIter> |
d7066497 | 1782 | inline void |
1acba85b JS |
1783 | sort(_RAIter __begin, _RAIter __end, |
1784 | __gnu_parallel::default_parallel_tag __parallelism) | |
d7066497 | 1785 | { |
1acba85b JS |
1786 | typedef iterator_traits<_RAIter> _TraitsType; |
1787 | typedef typename _TraitsType::value_type _ValueType; | |
1788 | sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1789 | } |
1790 | ||
1791 | // Public interface, insert default comparator | |
1acba85b | 1792 | template<typename _RAIter> |
d7066497 | 1793 | inline void |
1acba85b JS |
1794 | sort(_RAIter __begin, _RAIter __end, |
1795 | __gnu_parallel::parallel_tag __parallelism) | |
d7066497 | 1796 | { |
1acba85b JS |
1797 | typedef iterator_traits<_RAIter> _TraitsType; |
1798 | typedef typename _TraitsType::value_type _ValueType; | |
1799 | sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1800 | } |
1801 | ||
1802 | // Public interface, insert default comparator | |
1acba85b | 1803 | template<typename _RAIter> |
d7066497 | 1804 | inline void |
1acba85b JS |
1805 | sort(_RAIter __begin, _RAIter __end, |
1806 | __gnu_parallel::multiway_mergesort_tag __parallelism) | |
d7066497 | 1807 | { |
1acba85b JS |
1808 | typedef iterator_traits<_RAIter> _TraitsType; |
1809 | typedef typename _TraitsType::value_type _ValueType; | |
1810 | sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1811 | } |
1812 | ||
1813 | // Public interface, insert default comparator | |
1acba85b | 1814 | template<typename _RAIter> |
d7066497 | 1815 | inline void |
1acba85b JS |
1816 | sort(_RAIter __begin, _RAIter __end, |
1817 | __gnu_parallel::multiway_mergesort_sampling_tag __parallelism) | |
d7066497 | 1818 | { |
1acba85b JS |
1819 | typedef iterator_traits<_RAIter> _TraitsType; |
1820 | typedef typename _TraitsType::value_type _ValueType; | |
1821 | sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1822 | } |
1823 | ||
1824 | // Public interface, insert default comparator | |
1acba85b | 1825 | template<typename _RAIter> |
d7066497 | 1826 | inline void |
1acba85b JS |
1827 | sort(_RAIter __begin, _RAIter __end, |
1828 | __gnu_parallel::multiway_mergesort_exact_tag __parallelism) | |
d7066497 | 1829 | { |
1acba85b JS |
1830 | typedef iterator_traits<_RAIter> _TraitsType; |
1831 | typedef typename _TraitsType::value_type _ValueType; | |
1832 | sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1833 | } |
1834 | ||
1835 | // Public interface, insert default comparator | |
1acba85b | 1836 | template<typename _RAIter> |
d7066497 | 1837 | inline void |
1acba85b JS |
1838 | sort(_RAIter __begin, _RAIter __end, |
1839 | __gnu_parallel::quicksort_tag __parallelism) | |
d7066497 | 1840 | { |
1acba85b JS |
1841 | typedef iterator_traits<_RAIter> _TraitsType; |
1842 | typedef typename _TraitsType::value_type _ValueType; | |
1843 | sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1844 | } |
1845 | ||
1846 | // Public interface, insert default comparator | |
1acba85b | 1847 | template<typename _RAIter> |
d7066497 | 1848 | inline void |
1acba85b JS |
1849 | sort(_RAIter __begin, _RAIter __end, |
1850 | __gnu_parallel::balanced_quicksort_tag __parallelism) | |
d7066497 | 1851 | { |
1acba85b JS |
1852 | typedef iterator_traits<_RAIter> _TraitsType; |
1853 | typedef typename _TraitsType::value_type _ValueType; | |
1854 | sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1855 | } |
1856 | ||
1857 | // Public interface | |
1acba85b | 1858 | template<typename _RAIter, typename _Compare> |
531898c3 | 1859 | void |
1acba85b | 1860 | sort(_RAIter __begin, _RAIter __end, _Compare __comp) |
531898c3 | 1861 | { |
1acba85b JS |
1862 | typedef iterator_traits<_RAIter> _TraitsType; |
1863 | typedef typename _TraitsType::value_type _ValueType; | |
1864 | sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag()); | |
d7066497 | 1865 | } |
531898c3 | 1866 | |
c2ba9709 | 1867 | |
d7066497 JS |
1868 | // stable_sort interface |
1869 | ||
1870 | ||
1871 | // Sequential fallback | |
1acba85b | 1872 | template<typename _RAIter> |
d7066497 | 1873 | inline void |
1acba85b | 1874 | stable_sort(_RAIter __begin, _RAIter __end, |
d7066497 | 1875 | __gnu_parallel::sequential_tag) |
1acba85b | 1876 | { _GLIBCXX_STD_P::stable_sort(__begin, __end); } |
c2ba9709 | 1877 | |
d7066497 | 1878 | // Sequential fallback |
1acba85b | 1879 | template<typename _RAIter, typename _Compare> |
d7066497 | 1880 | inline void |
1acba85b JS |
1881 | stable_sort(_RAIter __begin, _RAIter __end, |
1882 | _Compare __comp, __gnu_parallel::sequential_tag) | |
1883 | { _GLIBCXX_STD_P::stable_sort<_RAIter, _Compare>( | |
1884 | __begin, __end, __comp); } | |
d7066497 JS |
1885 | |
1886 | // Public interface | |
1acba85b JS |
1887 | template<typename _RAIter, typename _Compare, |
1888 | typename _Parallelism> | |
d7066497 | 1889 | void |
1acba85b JS |
1890 | stable_sort(_RAIter __begin, _RAIter __end, |
1891 | _Compare __comp, _Parallelism __parallelism) | |
d7066497 | 1892 | { |
1acba85b JS |
1893 | typedef iterator_traits<_RAIter> _TraitsType; |
1894 | typedef typename _TraitsType::value_type _ValueType; | |
d7066497 | 1895 | |
1acba85b | 1896 | if (__begin != __end) |
d7066497 JS |
1897 | { |
1898 | if (_GLIBCXX_PARALLEL_CONDITION( | |
1acba85b | 1899 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >= |
d7066497 | 1900 | __gnu_parallel::_Settings::get().sort_minimal_n)) |
4459d22e | 1901 | __gnu_parallel::__parallel_sort<true>( |
15ac3c72 | 1902 | __begin, __end, __comp, __parallelism); |
d7066497 | 1903 | else |
15ac3c72 JS |
1904 | stable_sort(__begin, __end, __comp, |
1905 | __gnu_parallel::sequential_tag()); | |
d7066497 JS |
1906 | } |
1907 | } | |
c2ba9709 | 1908 | |
d7066497 | 1909 | // Public interface, insert default comparator |
1acba85b | 1910 | template<typename _RAIter> |
d7066497 | 1911 | inline void |
1acba85b | 1912 | stable_sort(_RAIter __begin, _RAIter __end) |
d7066497 | 1913 | { |
1acba85b JS |
1914 | typedef iterator_traits<_RAIter> _TraitsType; |
1915 | typedef typename _TraitsType::value_type _ValueType; | |
1916 | stable_sort(__begin, __end, std::less<_ValueType>(), | |
d7066497 JS |
1917 | __gnu_parallel::default_parallel_tag()); |
1918 | } | |
c2ba9709 | 1919 | |
d7066497 | 1920 | // Public interface, insert default comparator |
1acba85b | 1921 | template<typename _RAIter> |
d7066497 | 1922 | inline void |
1acba85b JS |
1923 | stable_sort(_RAIter __begin, _RAIter __end, |
1924 | __gnu_parallel::default_parallel_tag __parallelism) | |
d7066497 | 1925 | { |
1acba85b JS |
1926 | typedef iterator_traits<_RAIter> _TraitsType; |
1927 | typedef typename _TraitsType::value_type _ValueType; | |
1928 | stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1929 | } |
1930 | ||
1931 | // Public interface, insert default comparator | |
1acba85b | 1932 | template<typename _RAIter> |
d7066497 | 1933 | inline void |
1acba85b JS |
1934 | stable_sort(_RAIter __begin, _RAIter __end, |
1935 | __gnu_parallel::parallel_tag __parallelism) | |
d7066497 | 1936 | { |
1acba85b JS |
1937 | typedef iterator_traits<_RAIter> _TraitsType; |
1938 | typedef typename _TraitsType::value_type _ValueType; | |
1939 | stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1940 | } |
1941 | ||
1942 | // Public interface, insert default comparator | |
1acba85b | 1943 | template<typename _RAIter> |
d7066497 | 1944 | inline void |
1acba85b JS |
1945 | stable_sort(_RAIter __begin, _RAIter __end, |
1946 | __gnu_parallel::multiway_mergesort_tag __parallelism) | |
d7066497 | 1947 | { |
1acba85b JS |
1948 | typedef iterator_traits<_RAIter> _TraitsType; |
1949 | typedef typename _TraitsType::value_type _ValueType; | |
1950 | stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1951 | } |
1952 | ||
1953 | // Public interface, insert default comparator | |
1acba85b | 1954 | template<typename _RAIter> |
d7066497 | 1955 | inline void |
1acba85b JS |
1956 | stable_sort(_RAIter __begin, _RAIter __end, |
1957 | __gnu_parallel::quicksort_tag __parallelism) | |
d7066497 | 1958 | { |
1acba85b JS |
1959 | typedef iterator_traits<_RAIter> _TraitsType; |
1960 | typedef typename _TraitsType::value_type _ValueType; | |
1961 | stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1962 | } |
1963 | ||
1964 | // Public interface, insert default comparator | |
1acba85b | 1965 | template<typename _RAIter> |
d7066497 | 1966 | inline void |
1acba85b JS |
1967 | stable_sort(_RAIter __begin, _RAIter __end, |
1968 | __gnu_parallel::balanced_quicksort_tag __parallelism) | |
d7066497 | 1969 | { |
1acba85b JS |
1970 | typedef iterator_traits<_RAIter> _TraitsType; |
1971 | typedef typename _TraitsType::value_type _ValueType; | |
1972 | stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism); | |
d7066497 JS |
1973 | } |
1974 | ||
1975 | // Public interface | |
1acba85b | 1976 | template<typename _RAIter, typename _Compare> |
d7066497 | 1977 | void |
1acba85b JS |
1978 | stable_sort(_RAIter __begin, _RAIter __end, |
1979 | _Compare __comp) | |
d7066497 | 1980 | { |
1acba85b JS |
1981 | typedef iterator_traits<_RAIter> _TraitsType; |
1982 | typedef typename _TraitsType::value_type _ValueType; | |
15ac3c72 JS |
1983 | stable_sort( |
1984 | __begin, __end, __comp, __gnu_parallel::default_parallel_tag()); | |
d7066497 JS |
1985 | } |
1986 | ||
c2ba9709 | 1987 | // Sequential fallback |
1acba85b JS |
1988 | template<typename _IIter1, typename _IIter2, |
1989 | typename _OutputIterator> | |
1990 | inline _OutputIterator | |
1991 | merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, | |
1992 | _IIter2 __end2, _OutputIterator __result, | |
d7066497 | 1993 | __gnu_parallel::sequential_tag) |
15ac3c72 JS |
1994 | { return _GLIBCXX_STD_P::merge( |
1995 | __begin1, __end1, __begin2, __end2, __result); } | |
c2ba9709 JS |
1996 | |
1997 | // Sequential fallback | |
1acba85b JS |
1998 | template<typename _IIter1, typename _IIter2, |
1999 | typename _OutputIterator, typename _Compare> | |
2000 | inline _OutputIterator | |
2001 | merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, | |
2002 | _IIter2 __end2, _OutputIterator __result, _Compare __comp, | |
d7066497 | 2003 | __gnu_parallel::sequential_tag) |
15ac3c72 JS |
2004 | { return _GLIBCXX_STD_P::merge( |
2005 | __begin1, __end1, __begin2, __end2, __result, __comp); } | |
c2ba9709 JS |
2006 | |
2007 | // Sequential fallback for input iterator case | |
15ac3c72 JS |
2008 | template<typename _IIter1, typename _IIter2, typename _OutputIterator, |
2009 | typename _Compare, typename _IteratorTag1, | |
2010 | typename _IteratorTag2, typename _IteratorTag3> | |
1acba85b JS |
2011 | inline _OutputIterator |
2012 | __merge_switch(_IIter1 __begin1, _IIter1 __end1, | |
2013 | _IIter2 __begin2, _IIter2 __end2, | |
2014 | _OutputIterator __result, _Compare __comp, | |
2015 | _IteratorTag1, _IteratorTag2, _IteratorTag3) | |
2016 | { return _GLIBCXX_STD_P::merge(__begin1, __end1, __begin2, __end2, | |
2017 | __result, __comp); } | |
c2ba9709 JS |
2018 | |
2019 | // Parallel algorithm for random access iterators | |
1acba85b JS |
2020 | template<typename _IIter1, typename _IIter2, |
2021 | typename _OutputIterator, typename _Compare> | |
2022 | _OutputIterator | |
2023 | __merge_switch(_IIter1 __begin1, _IIter1 __end1, | |
2024 | _IIter2 __begin2, _IIter2 __end2, | |
2025 | _OutputIterator __result, _Compare __comp, | |
d7066497 JS |
2026 | random_access_iterator_tag, random_access_iterator_tag, |
2027 | random_access_iterator_tag) | |
531898c3 | 2028 | { |
5817ff8e | 2029 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 2030 | (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1) |
d7066497 | 2031 | >= __gnu_parallel::_Settings::get().merge_minimal_n |
1acba85b | 2032 | || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2) |
d7066497 | 2033 | >= __gnu_parallel::_Settings::get().merge_minimal_n))) |
15ac3c72 JS |
2034 | return __gnu_parallel::__parallel_merge_advance( |
2035 | __begin1, __end1, __begin2, __end2, __result, | |
2036 | (__end1 - __begin1) + (__end2 - __begin2), __comp); | |
531898c3 | 2037 | else |
15ac3c72 JS |
2038 | return __gnu_parallel::__merge_advance( |
2039 | __begin1, __end1, __begin2, __end2, __result, | |
2040 | (__end1 - __begin1) + (__end2 - __begin2), __comp); | |
c2ba9709 JS |
2041 | } |
2042 | ||
2043 | // Public interface | |
1acba85b JS |
2044 | template<typename _IIter1, typename _IIter2, |
2045 | typename _OutputIterator, typename _Compare> | |
2046 | inline _OutputIterator | |
2047 | merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, | |
2048 | _IIter2 __end2, _OutputIterator __result, _Compare __comp) | |
2049 | { | |
2050 | typedef typename iterator_traits<_IIter1>::value_type _ValueType; | |
2051 | ||
2052 | typedef std::iterator_traits<_IIter1> _IIterTraits1; | |
2053 | typedef std::iterator_traits<_IIter2> _IIterTraits2; | |
2054 | typedef std::iterator_traits<_OutputIterator> _OIterTraits; | |
2055 | typedef typename _IIterTraits1::iterator_category | |
2056 | _IIterCategory1; | |
2057 | typedef typename _IIterTraits2::iterator_category | |
2058 | _IIterCategory2; | |
2059 | typedef typename _OIterTraits::iterator_category _OIterCategory; | |
2060 | ||
15ac3c72 JS |
2061 | return __merge_switch( |
2062 | __begin1, __end1, __begin2, __end2, __result, __comp, | |
2063 | _IIterCategory1(), _IIterCategory2(), _OIterCategory()); | |
c2ba9709 JS |
2064 | } |
2065 | ||
2066 | ||
2067 | // Public interface, insert default comparator | |
1acba85b JS |
2068 | template<typename _IIter1, typename _IIter2, |
2069 | typename _OutputIterator> | |
2070 | inline _OutputIterator | |
2071 | merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, | |
2072 | _IIter2 __end2, _OutputIterator __result) | |
531898c3 | 2073 | { |
4459d22e JS |
2074 | typedef std::iterator_traits<_IIter1> _Iterator1Traits; |
2075 | typedef std::iterator_traits<_IIter2> _Iterator2Traits; | |
2076 | typedef typename _Iterator1Traits::value_type _ValueType1; | |
2077 | typedef typename _Iterator2Traits::value_type _ValueType2; | |
531898c3 | 2078 | |
1acba85b JS |
2079 | return merge(__begin1, __end1, __begin2, __end2, __result, |
2080 | __gnu_parallel::_Less<_ValueType1, _ValueType2>()); | |
531898c3 | 2081 | } |
c2ba9709 JS |
2082 | |
2083 | // Sequential fallback | |
1acba85b | 2084 | template<typename _RAIter> |
531898c3 | 2085 | inline void |
1acba85b JS |
2086 | nth_element(_RAIter __begin, _RAIter __nth, |
2087 | _RAIter __end, __gnu_parallel::sequential_tag) | |
2088 | { return _GLIBCXX_STD_P::nth_element(__begin, __nth, __end); } | |
c2ba9709 JS |
2089 | |
2090 | // Sequential fallback | |
1acba85b | 2091 | template<typename _RAIter, typename _Compare> |
531898c3 | 2092 | inline void |
1acba85b JS |
2093 | nth_element(_RAIter __begin, _RAIter __nth, |
2094 | _RAIter __end, _Compare __comp, | |
d7066497 | 2095 | __gnu_parallel::sequential_tag) |
1acba85b | 2096 | { return _GLIBCXX_STD_P::nth_element(__begin, __nth, __end, __comp); } |
c2ba9709 JS |
2097 | |
2098 | // Public interface | |
1acba85b | 2099 | template<typename _RAIter, typename _Compare> |
531898c3 | 2100 | inline void |
1acba85b JS |
2101 | nth_element(_RAIter __begin, _RAIter __nth, |
2102 | _RAIter __end, _Compare __comp) | |
531898c3 | 2103 | { |
5817ff8e | 2104 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 2105 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
d7066497 | 2106 | >= __gnu_parallel::_Settings::get().nth_element_minimal_n)) |
4459d22e | 2107 | __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp); |
531898c3 | 2108 | else |
15ac3c72 JS |
2109 | nth_element(__begin, __nth, __end, __comp, |
2110 | __gnu_parallel::sequential_tag()); | |
531898c3 | 2111 | } |
c2ba9709 JS |
2112 | |
2113 | // Public interface, insert default comparator | |
1acba85b | 2114 | template<typename _RAIter> |
531898c3 | 2115 | inline void |
1acba85b JS |
2116 | nth_element(_RAIter __begin, _RAIter __nth, |
2117 | _RAIter __end) | |
531898c3 | 2118 | { |
1acba85b JS |
2119 | typedef iterator_traits<_RAIter> _TraitsType; |
2120 | typedef typename _TraitsType::value_type _ValueType; | |
2121 | nth_element(__begin, __nth, __end, std::less<_ValueType>()); | |
531898c3 | 2122 | } |
c2ba9709 JS |
2123 | |
2124 | // Sequential fallback | |
1acba85b | 2125 | template<typename _RAIter, typename _Compare> |
531898c3 | 2126 | inline void |
1acba85b JS |
2127 | partial_sort(_RAIter __begin, _RAIter __middle, |
2128 | _RAIter __end, _Compare __comp, | |
d7066497 | 2129 | __gnu_parallel::sequential_tag) |
1acba85b | 2130 | { _GLIBCXX_STD_P::partial_sort(__begin, __middle, __end, __comp); } |
c2ba9709 JS |
2131 | |
2132 | // Sequential fallback | |
1acba85b | 2133 | template<typename _RAIter> |
a4797b34 | 2134 | inline void |
1acba85b JS |
2135 | partial_sort(_RAIter __begin, _RAIter __middle, |
2136 | _RAIter __end, __gnu_parallel::sequential_tag) | |
2137 | { _GLIBCXX_STD_P::partial_sort(__begin, __middle, __end); } | |
c2ba9709 JS |
2138 | |
2139 | // Public interface, parallel algorithm for random access iterators | |
1acba85b | 2140 | template<typename _RAIter, typename _Compare> |
531898c3 | 2141 | void |
1acba85b JS |
2142 | partial_sort(_RAIter __begin, _RAIter __middle, |
2143 | _RAIter __end, _Compare __comp) | |
531898c3 | 2144 | { |
5817ff8e | 2145 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 2146 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
d7066497 | 2147 | >= __gnu_parallel::_Settings::get().partial_sort_minimal_n)) |
15ac3c72 | 2148 | __gnu_parallel:: |
4459d22e | 2149 | __parallel_partial_sort(__begin, __middle, __end, __comp); |
531898c3 | 2150 | else |
1acba85b | 2151 | partial_sort(__begin, __middle, __end, __comp, |
d7066497 | 2152 | __gnu_parallel::sequential_tag()); |
531898c3 | 2153 | } |
c2ba9709 JS |
2154 | |
2155 | // Public interface, insert default comparator | |
1acba85b | 2156 | template<typename _RAIter> |
531898c3 | 2157 | inline void |
1acba85b JS |
2158 | partial_sort(_RAIter __begin, _RAIter __middle, |
2159 | _RAIter __end) | |
531898c3 | 2160 | { |
1acba85b JS |
2161 | typedef iterator_traits<_RAIter> _TraitsType; |
2162 | typedef typename _TraitsType::value_type _ValueType; | |
2163 | partial_sort(__begin, __middle, __end, std::less<_ValueType>()); | |
531898c3 | 2164 | } |
c2ba9709 JS |
2165 | |
2166 | // Sequential fallback | |
15ac3c72 JS |
2167 | template<typename _FIterator> |
2168 | inline _FIterator | |
2169 | max_element(_FIterator __begin, _FIterator __end, | |
d7066497 | 2170 | __gnu_parallel::sequential_tag) |
1acba85b | 2171 | { return _GLIBCXX_STD_P::max_element(__begin, __end); } |
c2ba9709 JS |
2172 | |
2173 | // Sequential fallback | |
15ac3c72 JS |
2174 | template<typename _FIterator, typename _Compare> |
2175 | inline _FIterator | |
2176 | max_element(_FIterator __begin, _FIterator __end, _Compare __comp, | |
d7066497 | 2177 | __gnu_parallel::sequential_tag) |
1acba85b | 2178 | { return _GLIBCXX_STD_P::max_element(__begin, __end, __comp); } |
c2ba9709 JS |
2179 | |
2180 | // Sequential fallback for input iterator case | |
15ac3c72 JS |
2181 | template<typename _FIterator, typename _Compare, typename _IteratorTag> |
2182 | inline _FIterator | |
2183 | __max_element_switch(_FIterator __begin, _FIterator __end, | |
1acba85b | 2184 | _Compare __comp, _IteratorTag) |
15ac3c72 JS |
2185 | { return max_element(__begin, __end, __comp, |
2186 | __gnu_parallel::sequential_tag()); } | |
c2ba9709 | 2187 | |
6f95a65a | 2188 | // Parallel algorithm for random access iterators |
1acba85b JS |
2189 | template<typename _RAIter, typename _Compare> |
2190 | _RAIter | |
2191 | __max_element_switch(_RAIter __begin, _RAIter __end, | |
2192 | _Compare __comp, random_access_iterator_tag, | |
2193 | __gnu_parallel::_Parallelism __parallelism_tag | |
d7066497 | 2194 | = __gnu_parallel::parallel_balanced) |
531898c3 | 2195 | { |
5817ff8e | 2196 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 2197 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
d7066497 | 2198 | >= __gnu_parallel::_Settings::get().max_element_minimal_n |
1acba85b | 2199 | && __gnu_parallel::__is_parallel(__parallelism_tag))) |
d7066497 | 2200 | { |
1acba85b JS |
2201 | _RAIter __res(__begin); |
2202 | __gnu_parallel::__identity_selector<_RAIter> | |
2203 | __functionality; | |
d7066497 | 2204 | __gnu_parallel:: |
15ac3c72 JS |
2205 | __for_each_template_random_access( |
2206 | __begin, __end, __gnu_parallel::_Nothing(), __functionality, | |
2207 | __gnu_parallel::__max_element_reduct<_Compare, _RAIter>(__comp), | |
2208 | __res, __res, -1, __parallelism_tag); | |
1acba85b | 2209 | return __res; |
d7066497 | 2210 | } |
531898c3 | 2211 | else |
15ac3c72 JS |
2212 | return max_element(__begin, __end, __comp, |
2213 | __gnu_parallel::sequential_tag()); | |
531898c3 | 2214 | } |
6f95a65a BK |
2215 | |
2216 | // Public interface, insert default comparator | |
15ac3c72 JS |
2217 | template<typename _FIterator> |
2218 | inline _FIterator | |
2219 | max_element(_FIterator __begin, _FIterator __end, | |
1acba85b | 2220 | __gnu_parallel::_Parallelism __parallelism_tag) |
531898c3 | 2221 | { |
15ac3c72 JS |
2222 | typedef typename iterator_traits<_FIterator>::value_type _ValueType; |
2223 | return max_element(__begin, __end, std::less<_ValueType>(), | |
2224 | __parallelism_tag); | |
531898c3 | 2225 | } |
6f95a65a | 2226 | |
15ac3c72 JS |
2227 | template<typename _FIterator> |
2228 | inline _FIterator | |
2229 | max_element(_FIterator __begin, _FIterator __end) | |
531898c3 | 2230 | { |
15ac3c72 | 2231 | typedef typename iterator_traits<_FIterator>::value_type _ValueType; |
1acba85b | 2232 | return max_element(__begin, __end, std::less<_ValueType>()); |
531898c3 | 2233 | } |
c2ba9709 JS |
2234 | |
2235 | // Public interface | |
15ac3c72 JS |
2236 | template<typename _FIterator, typename _Compare> |
2237 | inline _FIterator | |
2238 | max_element(_FIterator __begin, _FIterator __end, _Compare __comp, | |
1acba85b | 2239 | __gnu_parallel::_Parallelism __parallelism_tag) |
531898c3 | 2240 | { |
15ac3c72 | 2241 | typedef iterator_traits<_FIterator> _TraitsType; |
1acba85b JS |
2242 | typedef typename _TraitsType::iterator_category _IteratorCategory; |
2243 | return __max_element_switch(__begin, __end, __comp, _IteratorCategory(), | |
15ac3c72 | 2244 | __parallelism_tag); |
531898c3 | 2245 | } |
6f95a65a | 2246 | |
15ac3c72 JS |
2247 | template<typename _FIterator, typename _Compare> |
2248 | inline _FIterator | |
2249 | max_element(_FIterator __begin, _FIterator __end, _Compare __comp) | |
531898c3 | 2250 | { |
15ac3c72 | 2251 | typedef iterator_traits<_FIterator> _TraitsType; |
1acba85b JS |
2252 | typedef typename _TraitsType::iterator_category _IteratorCategory; |
2253 | return __max_element_switch(__begin, __end, __comp, _IteratorCategory()); | |
531898c3 | 2254 | } |
c2ba9709 | 2255 | |
6f95a65a | 2256 | |
c2ba9709 | 2257 | // Sequential fallback |
15ac3c72 JS |
2258 | template<typename _FIterator> |
2259 | inline _FIterator | |
2260 | min_element(_FIterator __begin, _FIterator __end, | |
d7066497 | 2261 | __gnu_parallel::sequential_tag) |
1acba85b | 2262 | { return _GLIBCXX_STD_P::min_element(__begin, __end); } |
c2ba9709 JS |
2263 | |
2264 | // Sequential fallback | |
15ac3c72 JS |
2265 | template<typename _FIterator, typename _Compare> |
2266 | inline _FIterator | |
2267 | min_element(_FIterator __begin, _FIterator __end, _Compare __comp, | |
d7066497 | 2268 | __gnu_parallel::sequential_tag) |
1acba85b | 2269 | { return _GLIBCXX_STD_P::min_element(__begin, __end, __comp); } |
c2ba9709 | 2270 | |
c2ba9709 | 2271 | // Sequential fallback for input iterator case |
15ac3c72 JS |
2272 | template<typename _FIterator, typename _Compare, typename _IteratorTag> |
2273 | inline _FIterator | |
2274 | __min_element_switch(_FIterator __begin, _FIterator __end, | |
1acba85b | 2275 | _Compare __comp, _IteratorTag) |
15ac3c72 JS |
2276 | { return min_element(__begin, __end, __comp, |
2277 | __gnu_parallel::sequential_tag()); } | |
c2ba9709 JS |
2278 | |
2279 | // Parallel algorithm for random access iterators | |
1acba85b JS |
2280 | template<typename _RAIter, typename _Compare> |
2281 | _RAIter | |
2282 | __min_element_switch(_RAIter __begin, _RAIter __end, | |
2283 | _Compare __comp, random_access_iterator_tag, | |
2284 | __gnu_parallel::_Parallelism __parallelism_tag | |
d7066497 | 2285 | = __gnu_parallel::parallel_balanced) |
531898c3 | 2286 | { |
5817ff8e | 2287 | if (_GLIBCXX_PARALLEL_CONDITION( |
1acba85b | 2288 | static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) |
d7066497 | 2289 | >= __gnu_parallel::_Settings::get().min_element_minimal_n |
1acba85b | 2290 | && __gnu_parallel::__is_parallel(__parallelism_tag))) |
d7066497 | 2291 | { |
1acba85b JS |
2292 | _RAIter __res(__begin); |
2293 | __gnu_parallel::__identity_selector<_RAIter> | |
2294 | __functionality; | |
d7066497 | 2295 | __gnu_parallel:: |
15ac3c72 JS |
2296 | __for_each_template_random_access( |
2297 | __begin, __end, __gnu_parallel::_Nothing(), __functionality, | |
2298 | __gnu_parallel::__min_element_reduct<_Compare, _RAIter>(__comp), | |
2299 | __res, __res, -1, __parallelism_tag); | |
1acba85b | 2300 | return __res; |
d7066497 | 2301 | } |
531898c3 | 2302 | else |
15ac3c72 JS |
2303 | return min_element(__begin, __end, __comp, |
2304 | __gnu_parallel::sequential_tag()); | |
531898c3 | 2305 | } |
6f95a65a BK |
2306 | |
2307 | // Public interface, insert default comparator | |
15ac3c72 JS |
2308 | template<typename _FIterator> |
2309 | inline _FIterator | |
2310 | min_element(_FIterator __begin, _FIterator __end, | |
1acba85b | 2311 | __gnu_parallel::_Parallelism __parallelism_tag) |
531898c3 | 2312 | { |
15ac3c72 JS |
2313 | typedef typename iterator_traits<_FIterator>::value_type _ValueType; |
2314 | return min_element(__begin, __end, std::less<_ValueType>(), | |
2315 | __parallelism_tag); | |
531898c3 | 2316 | } |
6f95a65a | 2317 | |
15ac3c72 JS |
2318 | template<typename _FIterator> |
2319 | inline _FIterator | |
2320 | min_element(_FIterator __begin, _FIterator __end) | |
531898c3 | 2321 | { |
15ac3c72 | 2322 | typedef typename iterator_traits<_FIterator>::value_type _ValueType; |
1acba85b | 2323 | return min_element(__begin, __end, std::less<_ValueType>()); |
531898c3 | 2324 | } |
c2ba9709 JS |
2325 | |
2326 | // Public interface | |
15ac3c72 JS |
2327 | template<typename _FIterator, typename _Compare> |
2328 | inline _FIterator | |
2329 | min_element(_FIterator __begin, _FIterator __end, _Compare __comp, | |
1acba85b | 2330 | __gnu_parallel::_Parallelism __parallelism_tag) |
531898c3 | 2331 | { |
15ac3c72 | 2332 | typedef iterator_traits<_FIterator> _TraitsType; |
1acba85b JS |
2333 | typedef typename _TraitsType::iterator_category _IteratorCategory; |
2334 | return __min_element_switch(__begin, __end, __comp, _IteratorCategory(), | |
2335 | __parallelism_tag); | |
531898c3 | 2336 | } |
6f95a65a | 2337 | |
15ac3c72 JS |
2338 | template<typename _FIterator, typename _Compare> |
2339 | inline _FIterator | |
2340 | min_element(_FIterator __begin, _FIterator __end, _Compare __comp) | |
531898c3 | 2341 | { |
15ac3c72 | 2342 | typedef iterator_traits<_FIterator> _TraitsType; |
1acba85b JS |
2343 | typedef typename _TraitsType::iterator_category _IteratorCategory; |
2344 | return __min_element_switch(__begin, __end, __comp, _IteratorCategory()); | |
531898c3 | 2345 | } |
c2ba9709 JS |
2346 | } // end namespace |
2347 | } // end namespace | |
2348 | ||
cbcd1e45 | 2349 | #endif /* _GLIBCXX_PARALLEL_ALGO_H */ |