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

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