OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [libstdc++-v3/] [include/] [parallel/] [algo.h] - Blame information for rev 816

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.