l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.9/include/parallel/algo.h

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