contrib/gcc-4.4/libstdc++-v3/include/parallel/algo.h

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