libstdc++-v3/include/parallel/algo.h

   1 // -*- 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 _GLIBCXX_VISIBILITY(default)
  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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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> _FIterTraits;
 277       typedef typename _IIterTraits::iterator_category _IIteratorCategory;
 278       typedef typename _FIterTraits::iterator_category _FIteratorCategory;
 279
 280       return __find_first_of_switch(__begin1, __end1, __begin2, __end2, __comp,
 281                                   _IIteratorCategory(), _FIteratorCategory());
 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> _FIterTraits;
 292       typedef typename _IIterTraits::value_type _IValueType;
 293       typedef typename _FIterTraits::value_type _FValueType;
 294
 295       return __gnu_parallel::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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 __gnu_parallel::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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 __gnu_parallel::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_A::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_A::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       __gnu_parallel::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_A::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_A::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       __gnu_parallel::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_A::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_A::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 __gnu_parallel::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_A::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_A::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 __gnu_parallel::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 */