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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 /** @file parallel/algo.h
  32  *  @brief Parallel STL function calls corresponding to the stl_algo.h header.
  33  *
  34  *  The functions defined here mainly do case switches and
  35  *  call the actual parallelized versions in other files.
  36  *  Inlining policy: Functions that basically only contain one function call,
  37  *  are declared inline.
  38  *  This file is a GNU parallel extension to the Standard C++ Library.
  39  */
  40
  41 // Written by Johannes Singler and Felix Putze.
  42
  43 #ifndef _GLIBCXX_PARALLEL_ALGO_H
  44 #define _GLIBCXX_PARALLEL_ALGO_H 1
  45
  46 #include <parallel/algorithmfwd.h>
  47 #include <bits/stl_algobase.h>
  48 #include <bits/stl_algo.h>
  49 #include <parallel/iterator.h>
  50 #include <parallel/base.h>
  51 #include <parallel/sort.h>
  52 #include <parallel/workstealing.h>
  53 #include <parallel/par_loop.h>
  54 #include <parallel/omp_loop.h>
  55 #include <parallel/omp_loop_static.h>
  56 #include <parallel/for_each_selectors.h>
  57 #include <parallel/for_each.h>
  58 #include <parallel/find.h>
  59 #include <parallel/find_selectors.h>
  60 #include <parallel/search.h>
  61 #include <parallel/random_shuffle.h>
  62 #include <parallel/partition.h>
  63 #include <parallel/merge.h>
  64 #include <parallel/unique_copy.h>
  65 #include <parallel/set_operations.h>
  66
  67 namespace std
  68 {
  69 namespace __parallel
  70 {
  71   // Sequential fallback
  72   template<typename InputIterator, typename Function>
  73   inline Function
  74   for_each(InputIterator begin, InputIterator end, Function f, __gnu_parallel::sequential_tag)
  75   {
  76     return _GLIBCXX_STD_P::for_each<InputIterator, Function>(begin, end, f);
  77   }
  78
  79   // Sequential fallback for input iterator case
  80   template<typename InputIterator, typename Function, typename IteratorTag>
  81   Function
  82   for_each_switch(InputIterator begin, InputIterator end, Function f, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
  83   {
  84     return for_each<InputIterator, Function>(begin, end, f, __gnu_parallel::sequential_tag());
  85   }
  86
  87   // Parallel algorithm for random access iterators
  88   template<typename RandomAccessIterator, typename Function>
  89   Function
  90   for_each_switch(RandomAccessIterator begin, RandomAccessIterator end, Function f, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
  91   {
  92     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::for_each_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
  93       {
  94         bool dummy;
  95         __gnu_parallel::for_each_selector<RandomAccessIterator> functionality;
  96         return __gnu_parallel::for_each_template_random_access(begin, end, f, functionality, __gnu_parallel::dummy_reduct(), true, dummy, -1, parallelism_tag);
  97       }
  98     else
  99       return for_each<RandomAccessIterator, Function>(begin, end, f, __gnu_parallel::sequential_tag());
 100   }
 101
 102   // Public interface
 103   template<typename Iterator, typename Function>
 104   inline Function
 105   for_each(Iterator begin, Iterator end, Function f, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
 106   {
 107     typedef std::iterator_traits<Iterator> iterator_traits;
 108     typedef typename iterator_traits::iterator_category iterator_category;
 109
 110     return for_each_switch(begin, end, f, iterator_category(), parallelism_tag);
 111   }
 112
 113
 114   // Sequential fallback
 115   template<typename InputIterator, typename T>
 116   inline InputIterator
 117   find(InputIterator begin, InputIterator end, const T& val, __gnu_parallel::sequential_tag)
 118   { return _GLIBCXX_STD_P::find<InputIterator, T>(begin, end, val); }
 119
 120   // Sequential fallback for input iterator case
 121   template<typename InputIterator, typename T, typename IteratorTag>
 122   inline InputIterator
 123   find_switch(InputIterator begin, InputIterator end, const T& val, IteratorTag)
 124   { return _GLIBCXX_STD_P::find(begin, end, val); }
 125
 126   // Parallel find for random access iterators
 127   template<typename RandomAccessIterator, typename T>
 128   RandomAccessIterator
 129   find_switch(RandomAccessIterator begin, RandomAccessIterator end, const T& val, random_access_iterator_tag)
 130   {
 131     typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
 132
 133     if (_GLIBCXX_PARALLEL_CONDITION(true))
 134       {
 135         binder2nd<__gnu_parallel::equal_to<value_type, T> > comp(__gnu_parallel::equal_to<value_type, T>(), val);
 136         return __gnu_parallel::find_template(begin, end, begin, comp, __gnu_parallel::find_if_selector()).first;
 137       }
 138     else
 139       return _GLIBCXX_STD_P::find(begin, end, val);
 140   }
 141
 142   // Public interface
 143   template<typename InputIterator, typename T>
 144   inline InputIterator
 145   find(InputIterator begin, InputIterator end, const T& val)
 146   {
 147     typedef std::iterator_traits<InputIterator> iterator_traits;
 148     typedef typename iterator_traits::iterator_category iterator_category;
 149     return find_switch(begin, end, val, iterator_category());
 150   }
 151
 152   // Sequential fallback
 153   template<typename InputIterator, typename Predicate>
 154   inline InputIterator
 155   find_if(InputIterator begin, InputIterator end, Predicate pred, __gnu_parallel::sequential_tag)
 156   {
 157     return _GLIBCXX_STD_P::find_if<InputIterator, Predicate>(begin, end, pred);
 158   }
 159
 160   // Sequential fallback for input iterator case
 161   template<typename InputIterator, typename Predicate, typename IteratorTag>
 162   inline InputIterator
 163   find_if_switch(InputIterator begin, InputIterator end, Predicate pred, IteratorTag)
 164   {
 165     return _GLIBCXX_STD_P::find_if(begin, end, pred);
 166   }
 167
 168   // Parallel find_if for random access iterators
 169   template<typename RandomAccessIterator, typename Predicate>
 170   RandomAccessIterator
 171   find_if_switch(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, random_access_iterator_tag)
 172   {
 173     if (_GLIBCXX_PARALLEL_CONDITION(true))
 174       return __gnu_parallel::find_template(begin, end, begin, pred, __gnu_parallel::find_if_selector()).first;
 175     else
 176       return _GLIBCXX_STD_P::find_if(begin, end, pred);
 177   }
 178
 179   // Public interface
 180   template<typename InputIterator, typename Predicate>
 181   inline InputIterator
 182   find_if (InputIterator begin, InputIterator end, Predicate pred)
 183   {
 184     typedef std::iterator_traits<InputIterator> iterator_traits;
 185     typedef typename iterator_traits::iterator_category iterator_category;
 186     return find_if_switch(begin, end, pred, iterator_category());
 187   }
 188
 189   // Sequential fallback
 190   template<typename InputIterator, typename ForwardIterator>
 191   inline InputIterator
 192   find_first_of(InputIterator begin1, InputIterator end1, ForwardIterator begin2, ForwardIterator end2, __gnu_parallel::sequential_tag)
 193   {
 194     return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2);
 195   }
 196
 197   // Sequential fallback
 198   template<typename InputIterator, typename ForwardIterator,
 199            typename BinaryPredicate>
 200   inline InputIterator
 201   find_first_of(InputIterator begin1, InputIterator end1,
 202                 ForwardIterator begin2, ForwardIterator end2,
 203                 BinaryPredicate comp, __gnu_parallel::sequential_tag)
 204   {
 205     return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2, comp);
 206   }
 207
 208   // Sequential fallback for input iterator type
 209   template<typename InputIterator, typename ForwardIterator, typename IteratorTag1, typename IteratorTag2>
 210   inline InputIterator
 211   find_first_of_switch(InputIterator begin1, InputIterator end1,
 212                        ForwardIterator begin2, ForwardIterator end2, IteratorTag1, IteratorTag2)
 213   {
 214     return find_first_of(begin1, end1, begin2, end2, __gnu_parallel::sequential_tag());
 215   }
 216
 217   // Parallel algorithm for random access iterators
 218   template<typename RandomAccessIterator, typename ForwardIterator, typename BinaryPredicate, typename IteratorTag>
 219   inline RandomAccessIterator
 220   find_first_of_switch(RandomAccessIterator begin1, RandomAccessIterator end1,
 221                        ForwardIterator begin2, ForwardIterator end2, BinaryPredicate comp, random_access_iterator_tag, IteratorTag)
 222   {
 223     return __gnu_parallel::find_template(begin1, end1, begin1, comp, __gnu_parallel::find_first_of_selector<ForwardIterator>(begin2, end2)).first;
 224   }
 225
 226   // Sequential fallback for input iterator type
 227   template<typename InputIterator, typename ForwardIterator, typename BinaryPredicate, typename IteratorTag1, typename IteratorTag2>
 228   inline
 229   InputIterator
 230   find_first_of_switch(InputIterator begin1, InputIterator end1,
 231                        ForwardIterator begin2, ForwardIterator end2, BinaryPredicate comp, IteratorTag1, IteratorTag2)
 232   {
 233     return find_first_of(begin1, end1, begin2, end2, comp, __gnu_parallel::sequential_tag());
 234   }
 235
 236   // Public interface
 237   template<typename InputIterator, typename ForwardIterator, typename BinaryPredicate>
 238   inline InputIterator
 239   find_first_of(InputIterator begin1, InputIterator end1,
 240                 ForwardIterator begin2, ForwardIterator end2, BinaryPredicate comp)
 241   {
 242     typedef std::iterator_traits<InputIterator> iteratori_traits;
 243     typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
 244     typedef typename iteratori_traits::iterator_category iteratori_category;
 245     typedef typename iteratorf_traits::iterator_category iteratorf_category;
 246
 247     return find_first_of_switch(begin1, end1, begin2, end2, comp, iteratori_category(), iteratorf_category());
 248   }
 249
 250   // Public interface, insert default comparator
 251   template<typename InputIterator, typename ForwardIterator>
 252   InputIterator
 253   find_first_of(InputIterator begin1, InputIterator end1, ForwardIterator begin2, ForwardIterator end2)
 254   {
 255     typedef std::iterator_traits<InputIterator> iteratori_traits;
 256     typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
 257     typedef typename iteratori_traits::value_type valuei_type;
 258     typedef typename iteratorf_traits::value_type valuef_type;
 259
 260     return find_first_of(begin1, end1, begin2, end2, __gnu_parallel::equal_to<valuei_type, valuef_type>());
 261   }
 262
 263   // Sequential fallback
 264   template<typename InputIterator, typename OutputIterator>
 265   inline OutputIterator
 266   unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
 267               __gnu_parallel::sequential_tag)
 268   {
 269     return _GLIBCXX_STD_P::unique_copy<InputIterator, OutputIterator>(begin1, end1, out);
 270   }
 271
 272   // Sequential fallback
 273   template<typename InputIterator, typename OutputIterator, typename Predicate>
 274   inline OutputIterator
 275   unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
 276               Predicate pred, __gnu_parallel::sequential_tag)
 277   {
 278     return _GLIBCXX_STD_P::unique_copy<InputIterator, OutputIterator, Predicate>(begin1, end1, out, pred);
 279   }
 280
 281   // Sequential fallback for input iterator case
 282   template<typename InputIterator, typename OutputIterator, typename Predicate, typename IteratorTag1, typename IteratorTag2>
 283   inline OutputIterator
 284   unique_copy_switch(InputIterator begin, InputIterator last, OutputIterator out,
 285                      Predicate pred, IteratorTag1, IteratorTag2)
 286   {
 287     return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
 288   }
 289
 290   // Parallel unique_copy for random access iterators
 291   template<typename RandomAccessIterator, typename RandomAccessOutputIterator, typename Predicate>
 292   RandomAccessOutputIterator
 293   unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last, RandomAccessOutputIterator out,
 294                      Predicate pred, random_access_iterator_tag, random_access_iterator_tag)
 295   {
 296     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(last - begin) > __gnu_parallel::Settings::unique_copy_minimal_n))
 297       return __gnu_parallel::parallel_unique_copy(begin, last, out, pred);
 298     else
 299       return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
 300   }
 301
 302   // Public interface
 303   template<typename InputIterator, typename OutputIterator>
 304   inline OutputIterator
 305   unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out)
 306   {
 307     typedef std::iterator_traits<InputIterator> iteratori_traits;
 308     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
 309     typedef typename iteratori_traits::iterator_category iteratori_category;
 310     typedef typename iteratori_traits::value_type value_type;
 311     typedef typename iteratoro_traits::iterator_category iteratoro_category;
 312
 313     return unique_copy_switch(begin1, end1, out, equal_to<value_type>(),
 314                               iteratori_category(), iteratoro_category());
 315   }
 316
 317   // Public interface
 318   template<typename InputIterator, typename OutputIterator, typename Predicate>
 319   inline OutputIterator
 320   unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
 321               Predicate pred)
 322   {
 323     typedef std::iterator_traits<InputIterator> iteratori_traits;
 324     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
 325     typedef typename iteratori_traits::iterator_category iteratori_category;
 326     typedef typename iteratoro_traits::iterator_category iteratoro_category;
 327
 328     return unique_copy_switch(begin1, end1, out, pred, iteratori_category(), iteratoro_category());
 329   }
 330
 331   // Sequential fallback
 332   template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
 333   inline OutputIterator
 334   set_union(InputIterator1 begin1, InputIterator1 end1,
 335             InputIterator2 begin2, InputIterator2 end2,
 336             OutputIterator out, __gnu_parallel::sequential_tag)
 337   {
 338     return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out);
 339   }
 340
 341   // Sequential fallback
 342   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
 343   inline OutputIterator
 344   set_union(InputIterator1 begin1, InputIterator1 end1,
 345             InputIterator2 begin2, InputIterator2 end2,
 346             OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
 347   {
 348     return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out, pred);
 349   }
 350
 351   // Sequential fallback for input iterator case
 352   template<typename InputIterator1, typename InputIterator2, typename Predicate,
 353            typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
 354   inline OutputIterator
 355   set_union_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 356                    InputIterator2 end2, OutputIterator result, Predicate pred, IteratorTag1,
 357                    IteratorTag2, IteratorTag3)
 358   {
 359     return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, result, pred);
 360   }
 361
 362   // Parallel set_union for random access iterators
 363   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 364            typename OutputRandomAccessIterator, typename Predicate>
 365   OutputRandomAccessIterator
 366   set_union_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2,
 367                    RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred,
 368                    random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
 369   {
 370     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_union_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_union_minimal_n))
 371       return __gnu_parallel::parallel_set_union(begin1, end1, begin2, end2, result, pred);
 372     else
 373       return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, result, pred);
 374   }
 375
 376   // Public interface
 377   template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
 378   inline OutputIterator
 379   set_union(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
 380   {
 381     typedef std::iterator_traits<InputIterator1> iteratori1_traits;
 382     typedef std::iterator_traits<InputIterator2> iteratori2_traits;
 383     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
 384     typedef typename iteratori1_traits::iterator_category iteratori1_category;
 385     typedef typename iteratori2_traits::iterator_category iteratori2_category;
 386     typedef typename iteratoro_traits::iterator_category iteratoro_category;
 387     typedef typename iteratori1_traits::value_type value1_type;
 388     typedef typename iteratori2_traits::value_type value2_type;
 389
 390     return set_union_switch(begin1, end1, begin2, end2, out, __gnu_parallel::less<value1_type, value2_type>(),
 391                             iteratori1_category(), iteratori2_category(), iteratoro_category());
 392   }
 393
 394   // Public interface
 395   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
 396   inline OutputIterator
 397   set_union(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 398             InputIterator2 end2, OutputIterator out, Predicate pred)
 399   {
 400     typedef std::iterator_traits<InputIterator1> iteratori1_traits;
 401     typedef std::iterator_traits<InputIterator2> iteratori2_traits;
 402     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
 403     typedef typename iteratori1_traits::iterator_category iteratori1_category;
 404     typedef typename iteratori2_traits::iterator_category iteratori2_category;
 405     typedef typename iteratoro_traits::iterator_category iteratoro_category;
 406
 407     return set_union_switch(begin1, end1, begin2, end2, out, pred,
 408                             iteratori1_category(), iteratori2_category(), iteratoro_category());
 409   }
 410
 411   // Sequential fallback.
 412   template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
 413   inline OutputIterator
 414   set_intersection(InputIterator1 begin1, InputIterator1 end1,
 415                    InputIterator2 begin2, InputIterator2 end2,
 416                    OutputIterator out, __gnu_parallel::sequential_tag)
 417   {
 418     return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, out);
 419   }
 420
 421   // Sequential fallback.
 422   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
 423   inline OutputIterator
 424   set_intersection(InputIterator1 begin1, InputIterator1 end1,
 425                    InputIterator2 begin2, InputIterator2 end2,
 426                    OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
 427   {
 428     return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, out, pred);
 429   }
 430
 431   // Sequential fallback for input iterator case
 432   template<typename InputIterator1, typename InputIterator2, typename Predicate,
 433            typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
 434   inline OutputIterator
 435   set_intersection_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 436                           InputIterator2 end2, OutputIterator result, Predicate pred, IteratorTag1,
 437                           IteratorTag2, IteratorTag3)
 438   {
 439     return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, result, pred);
 440   }
 441
 442   // Parallel set_intersection for random access iterators
 443   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 444            typename OutputRandomAccessIterator, typename Predicate>
 445   OutputRandomAccessIterator
 446   set_intersection_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2,
 447                           RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred,
 448                           random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
 449   {
 450     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_union_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_union_minimal_n))
 451       return __gnu_parallel::parallel_set_intersection(begin1, end1, begin2, end2, result, pred);
 452     else
 453       return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, result, pred);
 454   }
 455
 456   // Public interface
 457   template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
 458   inline OutputIterator
 459   set_intersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
 460   {
 461     typedef std::iterator_traits<InputIterator1> iteratori1_traits;
 462     typedef std::iterator_traits<InputIterator2> iteratori2_traits;
 463     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
 464     typedef typename iteratori1_traits::iterator_category iteratori1_category;
 465     typedef typename iteratori2_traits::iterator_category iteratori2_category;
 466     typedef typename iteratoro_traits::iterator_category iteratoro_category;
 467     typedef typename iteratori1_traits::value_type value1_type;
 468     typedef typename iteratori2_traits::value_type value2_type;
 469
 470     return set_intersection_switch(begin1, end1, begin2, end2, out, __gnu_parallel::less<value1_type, value2_type>(),
 471                                    iteratori1_category(), iteratori2_category(), iteratoro_category());
 472   }
 473
 474   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
 475   inline OutputIterator
 476   set_intersection(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 477                    InputIterator2 end2, OutputIterator out, Predicate pred)
 478   {
 479     typedef std::iterator_traits<InputIterator1> iteratori1_traits;
 480     typedef std::iterator_traits<InputIterator2> iteratori2_traits;
 481     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
 482     typedef typename iteratori1_traits::iterator_category iteratori1_category;
 483     typedef typename iteratori2_traits::iterator_category iteratori2_category;
 484     typedef typename iteratoro_traits::iterator_category iteratoro_category;
 485
 486     return set_intersection_switch(begin1, end1, begin2, end2, out, pred,
 487                                    iteratori1_category(), iteratori2_category(), iteratoro_category());
 488   }
 489
 490   // Sequential fallback
 491   template<typename InputIterator1, typename InputIterator2,
 492            typename OutputIterator>
 493   inline OutputIterator
 494   set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
 495                            InputIterator2 begin2, InputIterator2 end2,
 496                            OutputIterator out, __gnu_parallel::sequential_tag)
 497   {
 498     return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1, begin2, end2, out);
 499   }
 500
 501   // Sequential fallback
 502   template<typename InputIterator1, typename InputIterator2,
 503            typename OutputIterator, typename Predicate>
 504   inline OutputIterator
 505   set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
 506                            InputIterator2 begin2, InputIterator2 end2,
 507                            OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
 508   {
 509     return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2, end2, out, pred);
 510   }
 511
 512   // Sequential fallback for input iterator case
 513   template<typename InputIterator1, typename InputIterator2, typename Predicate, typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
 514   inline OutputIterator
 515   set_symmetric_difference_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Predicate pred, IteratorTag1, IteratorTag2, IteratorTag3)
 516   {
 517     return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2, end2, result, pred);
 518   }
 519
 520   // Parallel set_symmetric_difference for random access iterators
 521   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 522            typename OutputRandomAccessIterator, typename Predicate>
 523   OutputRandomAccessIterator
 524   set_symmetric_difference_switch(RandomAccessIterator1 begin1,
 525                                   RandomAccessIterator1 end1, RandomAccessIterator2 begin2,
 526                                   RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred,
 527                                   random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
 528   {
 529     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_symmetric_difference_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_symmetric_difference_minimal_n))
 530       return __gnu_parallel::parallel_set_symmetric_difference(begin1, end1, begin2, end2, result, pred);
 531     else
 532       return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2, end2, result, pred);
 533   }
 534
 535   // Public interface.
 536   template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
 537   inline OutputIterator
 538   set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
 539   {
 540     typedef std::iterator_traits<InputIterator1> iteratori1_traits;
 541     typedef std::iterator_traits<InputIterator2> iteratori2_traits;
 542     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
 543     typedef typename iteratori1_traits::iterator_category iteratori1_category;
 544     typedef typename iteratori2_traits::iterator_category iteratori2_category;
 545     typedef typename iteratoro_traits::iterator_category iteratoro_category;
 546     typedef typename iteratori1_traits::value_type value1_type;
 547     typedef typename iteratori2_traits::value_type value2_type;
 548
 549     return set_symmetric_difference_switch(begin1, end1, begin2, end2, out, __gnu_parallel::less<value1_type, value2_type>(),
 550                                            iteratori1_category(), iteratori2_category(), iteratoro_category());
 551   }
 552
 553   // Public interface.
 554   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
 555   inline OutputIterator
 556   set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 557                            InputIterator2 end2, OutputIterator out, Predicate pred)
 558   {
 559     typedef std::iterator_traits<InputIterator1> iteratori1_traits;
 560     typedef std::iterator_traits<InputIterator2> iteratori2_traits;
 561     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
 562     typedef typename iteratori1_traits::iterator_category iteratori1_category;
 563     typedef typename iteratori2_traits::iterator_category iteratori2_category;
 564     typedef typename iteratoro_traits::iterator_category iteratoro_category;
 565
 566    return set_symmetric_difference_switch(begin1, end1, begin2, end2, out, pred,
 567                                           iteratori1_category(), iteratori2_category(), iteratoro_category());
 568   }
 569
 570   // Sequential fallback.
 571   template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
 572   inline OutputIterator
 573   set_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out, __gnu_parallel::sequential_tag)
 574   {
 575     return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out);
 576   }
 577
 578   // Sequential fallback.
 579   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
 580   inline OutputIterator
 581   set_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out, Predicate pred, __gnu_parallel::sequential_tag)
 582   {
 583     return _GLIBCXX_STD_P::set_difference(begin1, end1, begin2, end2, out, pred);
 584   }
 585
 586   // Sequential fallback for input iterator case.
 587   template<typename InputIterator1, typename InputIterator2, typename Predicate,
 588            typename OutputIterator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
 589   inline OutputIterator
 590   set_difference_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 591                         InputIterator2 end2, OutputIterator result, Predicate pred, IteratorTag1, IteratorTag2, IteratorTag3)
 592   {
 593     return _GLIBCXX_STD_P::set_difference(begin1, end1, begin2, end2, result, pred);
 594   }
 595
 596   // Parallel set_difference for random access iterators
 597   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 598            typename OutputRandomAccessIterator, typename Predicate>
 599   OutputRandomAccessIterator
 600   set_difference_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2,
 601                         RandomAccessIterator2 end2, OutputRandomAccessIterator result, Predicate pred,
 602                         random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
 603   {
 604     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::set_difference_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::set_difference_minimal_n))
 605       return __gnu_parallel::parallel_set_difference(begin1, end1, begin2, end2, result, pred);
 606     else
 607       return _GLIBCXX_STD_P::set_difference(begin1, end1, begin2, end2, result, pred);
 608   }
 609
 610   // Public interface
 611   template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
 612   inline OutputIterator
 613   set_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
 614   {
 615     typedef std::iterator_traits<InputIterator1> iteratori1_traits;
 616     typedef std::iterator_traits<InputIterator2> iteratori2_traits;
 617     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
 618     typedef typename iteratori1_traits::iterator_category iteratori1_category;
 619     typedef typename iteratori2_traits::iterator_category iteratori2_category;
 620     typedef typename iteratoro_traits::iterator_category iteratoro_category;
 621     typedef typename iteratori1_traits::value_type value1_type;
 622     typedef typename iteratori2_traits::value_type value2_type;
 623
 624     return set_difference_switch(begin1, end1, begin2, end2, out, __gnu_parallel::less<value1_type, value2_type>(),
 625                                  iteratori1_category(), iteratori2_category(), iteratoro_category());
 626   }
 627
 628   // Public interface
 629   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Predicate>
 630   inline OutputIterator
 631   set_difference(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
 632                  InputIterator2 end2, OutputIterator out, Predicate pred)
 633   {
 634     typedef std::iterator_traits<InputIterator1> iteratori1_traits;
 635     typedef std::iterator_traits<InputIterator2> iteratori2_traits;
 636     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
 637     typedef typename iteratori1_traits::iterator_category iteratori1_category;
 638     typedef typename iteratori2_traits::iterator_category iteratori2_category;
 639     typedef typename iteratoro_traits::iterator_category iteratoro_category;
 640
 641     return set_difference_switch(begin1, end1, begin2, end2, out, pred,
 642                                  iteratori1_category(), iteratori2_category(), iteratoro_category());
 643   }
 644
 645   // Sequential fallback
 646   template<typename ForwardIterator>
 647   inline ForwardIterator
 648   adjacent_find(ForwardIterator begin, ForwardIterator end, __gnu_parallel::sequential_tag)
 649   {
 650     return _GLIBCXX_STD_P::adjacent_find<ForwardIterator>(begin, end);
 651   }
 652
 653   // Sequential fallback
 654   template<typename ForwardIterator, typename BinaryPredicate>
 655   inline ForwardIterator
 656   adjacent_find(ForwardIterator begin, ForwardIterator end, BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
 657   {
 658     return _GLIBCXX_STD_P::adjacent_find<ForwardIterator, BinaryPredicate>(begin, end, binary_pred);
 659   }
 660
 661   // Parallel algorithm for random access iterators
 662   template<typename RandomAccessIterator>
 663   RandomAccessIterator
 664   adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end, random_access_iterator_tag)
 665   {
 666     typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
 667
 668     if (_GLIBCXX_PARALLEL_CONDITION(true))
 669       {
 670         RandomAccessIterator spot = __gnu_parallel::find_template(begin, end - 1, begin, equal_to<value_type>(), __gnu_parallel::adjacent_find_selector()).first;
 671         if (spot == (end - 1))
 672           return end;
 673         else
 674           return spot;
 675       }
 676     else
 677       return adjacent_find<RandomAccessIterator>(begin, end, __gnu_parallel::sequential_tag());
 678   }
 679
 680   // Sequential fallback for input iterator case
 681   template<typename ForwardIterator, typename IteratorTag>
 682   inline ForwardIterator
 683   adjacent_find_switch(ForwardIterator begin, ForwardIterator end, IteratorTag)
 684   {
 685     return adjacent_find<ForwardIterator>(begin, end, __gnu_parallel::sequential_tag());
 686   }
 687
 688   // Public interface
 689   template<typename ForwardIterator>
 690   inline ForwardIterator
 691   adjacent_find(ForwardIterator begin, ForwardIterator end)
 692   {
 693     return adjacent_find_switch(begin, end, typename std::iterator_traits<ForwardIterator>::iterator_category());
 694   }
 695
 696   // Sequential fallback for input iterator case
 697   template<typename ForwardIterator, typename BinaryPredicate, typename IteratorTag>
 698   inline ForwardIterator
 699   adjacent_find_switch(ForwardIterator begin, ForwardIterator end, BinaryPredicate binary_pred, IteratorTag)
 700   {
 701     return adjacent_find<ForwardIterator, BinaryPredicate>(begin, end, binary_pred, __gnu_parallel::sequential_tag());
 702   }
 703
 704   // Parallel algorithm for random access iterators
 705   template<typename RandomAccessIterator, typename BinaryPredicate>
 706   RandomAccessIterator
 707   adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end, BinaryPredicate binary_pred, random_access_iterator_tag)
 708   {
 709     if (_GLIBCXX_PARALLEL_CONDITION(true))
 710       return __gnu_parallel::find_template(begin, end, begin, binary_pred, __gnu_parallel::adjacent_find_selector()).first;
 711     else
 712       return adjacent_find(begin, end, binary_pred, __gnu_parallel::sequential_tag());
 713   }
 714
 715   // Public interface
 716   template<typename ForwardIterator, typename BinaryPredicate>
 717   inline ForwardIterator
 718   adjacent_find(ForwardIterator begin, ForwardIterator end, BinaryPredicate binary_pred)
 719   {
 720     return adjacent_find_switch<ForwardIterator, BinaryPredicate>(begin, end, binary_pred, typename std::iterator_traits<ForwardIterator>::iterator_category());
 721   }
 722
 723   // Sequential fallback
 724   template<typename InputIterator, typename T>
 725   inline typename iterator_traits<InputIterator>::difference_type
 726   count(InputIterator begin, InputIterator end, const T& value, __gnu_parallel::sequential_tag)
 727   {
 728     return _GLIBCXX_STD_P::count<InputIterator, T>(begin, end, value);
 729   }
 730
 731   // Parallel code for random access iterators
 732   template<typename RandomAccessIterator, typename T>
 733   typename iterator_traits<RandomAccessIterator>::difference_type
 734   count_switch(RandomAccessIterator begin, RandomAccessIterator end, const T& value, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
 735   {
 736     typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
 737     typedef typename iterator_traits<RandomAccessIterator>::difference_type difference_type;
 738
 739     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::count_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
 740       {
 741         difference_type res = 0;
 742         __gnu_parallel::count_selector<RandomAccessIterator, difference_type> functionality;
 743         __gnu_parallel::for_each_template_random_access(begin, end, value, functionality, std::plus<__gnu_parallel::sequence_index_t>(), res, res, -1, parallelism_tag);
 744         return res;
 745       }
 746     else
 747       return count<RandomAccessIterator, T>(begin, end, value, __gnu_parallel::sequential_tag());
 748   }
 749
 750   // Sequential fallback for input iterator case.
 751   template<typename InputIterator, typename T, typename IteratorTag>
 752   typename iterator_traits<InputIterator>::difference_type
 753   count_switch(InputIterator begin, InputIterator end, const T& value, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
 754   {
 755     return count<InputIterator, T>(begin, end, value, __gnu_parallel::sequential_tag());
 756   }
 757
 758   // Public interface.
 759   template<typename InputIterator, typename T>
 760   inline typename iterator_traits<InputIterator>::difference_type
 761   count(InputIterator begin, InputIterator end, const T& value, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_unbalanced)
 762   {
 763     return count_switch(begin, end, value, typename std::iterator_traits<InputIterator>::iterator_category(), parallelism_tag);
 764   }
 765
 766   // Sequential fallback.
 767   template<typename InputIterator, typename Predicate>
 768   inline typename iterator_traits<InputIterator>::difference_type
 769   count_if(InputIterator begin, InputIterator end, Predicate pred, __gnu_parallel::sequential_tag)
 770   {
 771     return _GLIBCXX_STD_P::count_if(begin, end, pred);
 772   }
 773
 774   // Parallel count_if for random access iterators
 775   template<typename RandomAccessIterator, typename Predicate>
 776   typename iterator_traits<RandomAccessIterator>::difference_type
 777   count_if_switch(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
 778   {
 779     typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
 780     typedef typename iterator_traits<RandomAccessIterator>::difference_type difference_type;
 781
 782     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::count_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
 783       {
 784         difference_type res = 0;
 785         __gnu_parallel::count_if_selector<RandomAccessIterator, difference_type> functionality;
 786         __gnu_parallel::for_each_template_random_access(begin, end, pred, functionality, std::plus<__gnu_parallel::sequence_index_t>(), res, res, -1, parallelism_tag);
 787         return res;
 788       }
 789     else
 790       return count_if<RandomAccessIterator, Predicate>(begin, end, pred, __gnu_parallel::sequential_tag());
 791   }
 792
 793   // Sequential fallback for input iterator case.
 794   template<typename InputIterator, typename Predicate, typename IteratorTag>
 795   typename iterator_traits<InputIterator>::difference_type
 796   count_if_switch(InputIterator begin, InputIterator end, Predicate pred, IteratorTag, __gnu_parallel::parallelism)
 797   {
 798     return count_if<InputIterator, Predicate>(begin, end, pred, __gnu_parallel::sequential_tag());
 799   }
 800
 801   // Public interface.
 802   template<typename InputIterator, typename Predicate>
 803   inline typename iterator_traits<InputIterator>::difference_type
 804   count_if(InputIterator begin, InputIterator end, Predicate pred, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_unbalanced)
 805   {
 806     typedef iterator_traits<InputIterator> traits_type;
 807     typedef typename traits_type::iterator_category iterator_category;
 808     return count_if_switch(begin, end, pred, iterator_category(), parallelism_tag);
 809   }
 810
 811
 812   // Sequential fallback.
 813   template<typename ForwardIterator1, typename ForwardIterator2>
 814   inline ForwardIterator1
 815   search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, __gnu_parallel::sequential_tag)
 816   {
 817     return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2);
 818   }
 819
 820   // Parallel algorithm for random access iterator
 821   template<typename RandomAccessIterator1, typename RandomAccessIterator2>
 822   RandomAccessIterator1
 823   search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator2 end2, random_access_iterator_tag, random_access_iterator_tag)
 824   {
 825     typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits;
 826     typedef typename iterator1_traits::value_type value1_type;
 827     typedef std::iterator_traits<RandomAccessIterator2> iterator2_traits;
 828     typedef typename iterator2_traits::value_type value2_type;
 829
 830     if (_GLIBCXX_PARALLEL_CONDITION(true))
 831       return __gnu_parallel::search_template(begin1, end1, begin2, end2, __gnu_parallel::equal_to<value1_type, value2_type>());
 832     else
 833       return search(begin1, end1, begin2, end2, __gnu_parallel::sequential_tag());
 834   }
 835
 836   // Sequential fallback for input iterator case
 837   template<typename ForwardIterator1, typename ForwardIterator2, typename IteratorTag1, typename IteratorTag2>
 838   inline ForwardIterator1
 839   search_switch(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, IteratorTag1, IteratorTag2)
 840   {
 841     return search(begin1, end1, begin2, end2, __gnu_parallel::sequential_tag());
 842   }
 843
 844   // Public interface.
 845   template<typename ForwardIterator1, typename ForwardIterator2>
 846   inline ForwardIterator1
 847   search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2)
 848   {
 849     typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
 850     typedef typename iterator1_traits::iterator_category iterator1_category;
 851     typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
 852     typedef typename iterator2_traits::iterator_category iterator2_category;
 853
 854     return search_switch(begin1, end1, begin2, end2, iterator1_category(), iterator2_category());
 855   }
 856
 857   // Public interface.
 858   template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
 859   inline ForwardIterator1
 860   search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred, __gnu_parallel::sequential_tag)
 861   {
 862     return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred);
 863   }
 864
 865   // Parallel algorithm for random access iterator.
 866   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
 867            typename BinaryPredicate>
 868   RandomAccessIterator1
 869   search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
 870                 RandomAccessIterator2 begin2, RandomAccessIterator2 end2, BinaryPredicate  pred, random_access_iterator_tag, random_access_iterator_tag)
 871   {
 872     if (_GLIBCXX_PARALLEL_CONDITION(true))
 873       return __gnu_parallel::search_template(begin1, end1, begin2, end2, pred);
 874     else
 875       return search(begin1, end1, begin2, end2, pred, __gnu_parallel::sequential_tag());
 876   }
 877
 878   // Sequential fallback for input iterator case
 879   template<typename ForwardIterator1, typename ForwardIterator2,
 880            typename BinaryPredicate, typename IteratorTag1, typename IteratorTag2>
 881   inline ForwardIterator1
 882   search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
 883                 ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate pred, IteratorTag1, IteratorTag2)
 884   {
 885     return search(begin1, end1, begin2, end2, pred, __gnu_parallel::sequential_tag());
 886   }
 887
 888   // Public interface
 889   template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
 890   inline ForwardIterator1
 891   search(ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2, BinaryPredicate  pred)
 892   {
 893     typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
 894     typedef typename iterator1_traits::iterator_category iterator1_category;
 895     typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
 896     typedef typename iterator2_traits::iterator_category iterator2_category;
 897     return search_switch(begin1, end1, begin2, end2, pred, iterator1_category(), iterator2_category());
 898   }
 899
 900   // Sequential fallback
 901   template<typename ForwardIterator, typename Integer, typename T>
 902   inline ForwardIterator
 903   search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, __gnu_parallel::sequential_tag)
 904   { return _GLIBCXX_STD_P::search_n(begin, end, count, val); }
 905
 906   // Sequential fallback
 907   template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate>
 908   inline ForwardIterator
 909   search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
 910   {
 911     return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred);
 912   }
 913
 914   // Public interface.
 915   template<typename ForwardIterator, typename Integer, typename T>
 916   inline ForwardIterator
 917   search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val)
 918   {
 919     typedef typename iterator_traits<ForwardIterator>::value_type value_type;
 920     return search_n(begin, end, count, val, __gnu_parallel::equal_to<value_type, T>());
 921   }
 922
 923   // Parallel algorithm for random access iterators.
 924   template<typename RandomAccessIterator, typename Integer, typename T, typename BinaryPredicate>
 925   RandomAccessIterator
 926   search_n_switch(RandomAccessIterator begin, RandomAccessIterator end, Integer count, const T& val, BinaryPredicate binary_pred, random_access_iterator_tag)
 927   {
 928     if (_GLIBCXX_PARALLEL_CONDITION(true))
 929       {
 930         __gnu_parallel::pseudo_sequence<T, Integer> ps(val, count);
 931         return __gnu_parallel::search_template(begin, end, ps.begin(), ps.end(), binary_pred);
 932       }
 933     else
 934       return std::__search_n(begin, end, count, val, binary_pred, random_access_iterator_tag());
 935   }
 936
 937   // Sequential fallback for input iterator case.
 938   template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate, typename IteratorTag>
 939   inline ForwardIterator
 940   search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, BinaryPredicate binary_pred, IteratorTag)
 941   {
 942     return __search_n(begin, end, count, val, binary_pred, IteratorTag());
 943   }
 944
 945   // Public interface.
 946   template<typename ForwardIterator, typename Integer, typename T, typename BinaryPredicate>
 947   inline ForwardIterator
 948   search_n(ForwardIterator begin, ForwardIterator end, Integer count, const T& val, BinaryPredicate binary_pred)
 949   {
 950     return search_n_switch(begin, end, count, val, binary_pred, typename std::iterator_traits<ForwardIterator>::iterator_category());
 951   }
 952
 953   // Sequential fallback.
 954   template<typename InputIterator, typename OutputIterator, typename UnaryOperation>
 955   inline OutputIterator
 956   transform(InputIterator begin, InputIterator end, OutputIterator result, UnaryOperation unary_op, __gnu_parallel::sequential_tag)
 957   {
 958     return _GLIBCXX_STD_P::transform(begin, end, result, unary_op);
 959   }
 960
 961   // Sequential fallback
 962   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation>
 963   inline OutputIterator
 964   transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, OutputIterator result, BinaryOperation binary_op, __gnu_parallel::sequential_tag)
 965   {
 966     return _GLIBCXX_STD_P::transform(begin1, end1, begin2, result, binary_op);
 967   }
 968
 969   // Parallel unary transform for random access iterators.
 970   template<typename RandomAccessIterator1, typename RandomAccessIterator3, typename UnaryOperation>
 971   RandomAccessIterator3
 972   transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, RandomAccessIterator3 result, UnaryOperation unary_op, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
 973   {
 974     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::transform_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
 975       {
 976         bool dummy = true;
 977         typedef __gnu_parallel::iterator_pair<RandomAccessIterator1, RandomAccessIterator3, random_access_iterator_tag> ip;
 978         ip begin_pair(begin, result), end_pair(end, result + (end - begin));
 979         __gnu_parallel::transform1_selector<ip> functionality;
 980         __gnu_parallel::for_each_template_random_access(begin_pair, end_pair, unary_op, functionality, __gnu_parallel::dummy_reduct(), dummy, dummy, -1, parallelism_tag);
 981         return functionality.finish_iterator;
 982       }
 983     else
 984       return transform(begin, end, result, unary_op, __gnu_parallel::sequential_tag());
 985   }
 986
 987   // Sequential fallback for input iterator case.
 988   template<typename RandomAccessIterator1, typename RandomAccessIterator3, typename UnaryOperation, typename IteratorTag1, typename IteratorTag2>
 989   inline RandomAccessIterator3
 990   transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, RandomAccessIterator3 result, UnaryOperation unary_op, IteratorTag1, IteratorTag2, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
 991   {
 992     return _GLIBCXX_STD_P::transform(begin, end, result, unary_op);
 993   }
 994
 995
 996   // Parallel binary transform for random access iterators.
 997   template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename BinaryOperation>
 998   RandomAccessIterator3
 999   transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator3 result, BinaryOperation binary_op, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1000   {
1001     if (_GLIBCXX_PARALLEL_CONDITION((end1 - begin1) >= __gnu_parallel::Settings::transform_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
1002       {
1003         bool dummy = true;
1004         typedef __gnu_parallel::iterator_triple<RandomAccessIterator1, RandomAccessIterator2, RandomAccessIterator3, random_access_iterator_tag> ip;
1005         ip begin_triple(begin1, begin2, result), end_triple(end1, begin2 + (end1 - begin1), result + (end1 - begin1));
1006         __gnu_parallel::transform2_selector<ip> functionality;
1007         __gnu_parallel::for_each_template_random_access(begin_triple, end_triple, binary_op, functionality, __gnu_parallel::dummy_reduct(), dummy, dummy, -1, parallelism_tag);
1008         return functionality.finish_iterator;
1009       }
1010     else
1011       return transform(begin1, end1, begin2, result, binary_op, __gnu_parallel::sequential_tag());
1012   }
1013
1014   // Sequential fallback for input iterator case.
1015   template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename BinaryOperation, typename tag1, typename tag2, typename tag3>
1016   inline RandomAccessIterator3
1017   transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, RandomAccessIterator3 result, BinaryOperation binary_op, tag1, tag2, tag3, __gnu_parallel::parallelism)
1018   {
1019     return _GLIBCXX_STD_P::transform(begin1, end1, begin2, result, binary_op);
1020   }
1021
1022   // Public interface.
1023   template<typename InputIterator, typename OutputIterator, typename UnaryOperation>
1024   inline OutputIterator
1025   transform(InputIterator begin, InputIterator end, OutputIterator result,
1026             UnaryOperation unary_op, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1027   {
1028     typedef std::iterator_traits<InputIterator> iteratori_traits;
1029     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1030     typedef typename iteratori_traits::iterator_category iteratori_category;
1031     typedef typename iteratoro_traits::iterator_category iteratoro_category;
1032
1033     return transform1_switch(begin, end, result, unary_op,
1034                              iteratori_category(), iteratoro_category(), parallelism_tag);
1035   }
1036
1037   // Public interface.
1038   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation>
1039   inline OutputIterator
1040   transform(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, OutputIterator result, BinaryOperation binary_op, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1041   {
1042     typedef std::iterator_traits<InputIterator1> iteratori1_traits;
1043     typedef typename iteratori1_traits::iterator_category iteratori1_category;
1044     typedef std::iterator_traits<InputIterator2> iteratori2_traits;
1045     typedef typename iteratori2_traits::iterator_category iteratori2_category;
1046     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1047     typedef typename iteratoro_traits::iterator_category iteratoro_category;
1048
1049
1050     return transform2_switch(begin1, end1, begin2, result, binary_op,
1051                              iteratori1_category(), iteratori2_category(), iteratoro_category(), parallelism_tag);
1052   }
1053
1054   // Sequential fallback
1055   template<typename ForwardIterator, typename T>
1056   inline void
1057   replace(ForwardIterator begin, ForwardIterator end, const T& old_value, const T& new_value, __gnu_parallel::sequential_tag)
1058   { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); }
1059
1060   // Sequential fallback for input iterator case
1061   template<typename ForwardIterator, typename T, typename IteratorTag>
1062   void
1063   replace_switch(ForwardIterator begin, ForwardIterator end, const T& old_value, const T& new_value, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
1064   { replace(begin, end, old_value, new_value, __gnu_parallel::sequential_tag()); }
1065
1066   // Parallel replace for random access iterators
1067   template<typename RandomAccessIterator, typename T>
1068   void
1069   replace_switch(RandomAccessIterator begin, RandomAccessIterator end, const T& old_value, const T& new_value, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1070   { replace(begin, end, old_value, new_value, __gnu_parallel::sequential_tag()); }
1071
1072   // Public interface
1073   template<typename ForwardIterator, typename T>
1074   inline void
1075   replace(ForwardIterator begin, ForwardIterator end, const T& old_value, const T& new_value, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1076   {
1077     replace_switch(begin, end, old_value, new_value, typename std::iterator_traits<ForwardIterator>::iterator_category(), parallelism_tag);
1078   }
1079
1080
1081   // Sequential fallback
1082   template<typename ForwardIterator, typename Predicate, typename T>
1083   inline void
1084   replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred, const T& new_value, __gnu_parallel::sequential_tag)
1085   { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); }
1086
1087   // Sequential fallback for input iterator case
1088   template<typename ForwardIterator, typename Predicate, typename T, typename IteratorTag>
1089   void
1090   replace_if_switch(ForwardIterator begin, ForwardIterator end, Predicate pred, const T& new_value, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
1091   { replace_if(begin, end, pred, new_value, __gnu_parallel::sequential_tag()); }
1092
1093   // Parallel algorithm for random access iterators.
1094   template<typename RandomAccessIterator, typename Predicate, typename T>
1095   void
1096   replace_if_switch(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, const T& new_value, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1097   {
1098     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::replace_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
1099       {
1100         bool dummy;
1101         __gnu_parallel::replace_if_selector<RandomAccessIterator, Predicate, T> functionality(new_value);
1102         __gnu_parallel::for_each_template_random_access(begin, end, pred, functionality, __gnu_parallel::dummy_reduct(), true, dummy, -1, parallelism_tag);
1103       }
1104     else
1105       replace_if(begin, end, pred, new_value, __gnu_parallel::sequential_tag());
1106   }
1107
1108   // Public interface.
1109   template<typename ForwardIterator, typename Predicate, typename T>
1110   inline void
1111   replace_if(ForwardIterator begin, ForwardIterator end,
1112              Predicate pred, const T& new_value, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1113   {
1114     typedef std::iterator_traits<ForwardIterator> iterator_traits;
1115     typedef typename iterator_traits::iterator_category iterator_category;
1116
1117     replace_if_switch(begin, end, pred, new_value, iterator_category(), parallelism_tag);
1118   }
1119
1120   // Sequential fallback
1121   template<typename ForwardIterator, typename Generator>
1122   inline void
1123   generate(ForwardIterator begin, ForwardIterator end, Generator gen, __gnu_parallel::sequential_tag)
1124   { _GLIBCXX_STD_P::generate<ForwardIterator, Generator>(begin, end, gen); }
1125
1126   // Sequential fallback for input iterator case.
1127   template<typename ForwardIterator, typename Generator, typename IteratorTag>
1128   void
1129   generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
1130   { generate(begin, end, gen, __gnu_parallel::sequential_tag()); }
1131
1132   // Parallel algorithm for random access iterators.
1133   template<typename RandomAccessIterator, typename Generator>
1134   void
1135   generate_switch(RandomAccessIterator begin, RandomAccessIterator end,
1136                   Generator gen, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1137   {
1138     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::generate_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
1139       {
1140         bool dummy;
1141         __gnu_parallel::generate_selector<RandomAccessIterator> functionality;
1142         __gnu_parallel::for_each_template_random_access(begin, end, gen, functionality, __gnu_parallel::dummy_reduct(), true, dummy, -1, parallelism_tag);
1143       }
1144     else
1145       generate(begin, end, gen, __gnu_parallel::sequential_tag());
1146   }
1147
1148   // Public interface.
1149   template<typename ForwardIterator, typename Generator>
1150   inline void
1151   generate(ForwardIterator begin, ForwardIterator end,
1152            Generator gen, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1153   {
1154     typedef std::iterator_traits<ForwardIterator> iterator_traits;
1155     typedef typename iterator_traits::iterator_category iterator_category;
1156     generate_switch(begin, end, gen, iterator_category(), parallelism_tag);
1157   }
1158
1159
1160   // Sequential fallback.
1161   template<typename OutputIterator, typename Size, typename Generator>
1162   inline OutputIterator
1163   generate_n(OutputIterator begin, Size n, Generator gen, __gnu_parallel::sequential_tag)
1164   { return _GLIBCXX_STD_P::generate_n(begin, n, gen); }
1165
1166   // Sequential fallback for input iterator case.
1167   template<typename OutputIterator, typename Size, typename Generator, typename IteratorTag>
1168   OutputIterator
1169   generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag, __gnu_parallel::parallelism)
1170   { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
1171
1172   // Parallel algorithm for random access iterators.
1173   template<typename RandomAccessIterator, typename Size, typename Generator>
1174   RandomAccessIterator
1175   generate_n_switch(RandomAccessIterator begin, Size n, Generator gen, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1176   { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
1177
1178   // Public interface.
1179   template<typename OutputIterator, typename Size, typename Generator>
1180   inline OutputIterator
1181   generate_n(OutputIterator begin, Size n, Generator gen, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1182   {
1183     typedef std::iterator_traits<OutputIterator> iterator_traits;
1184     typedef typename iterator_traits::iterator_category iterator_category;
1185     return generate_n_switch(begin, n, gen, iterator_category(), parallelism_tag);
1186   }
1187
1188
1189   // Sequential fallback.
1190   template<typename RandomAccessIterator>
1191   inline void
1192   random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::sequential_tag)
1193   { _GLIBCXX_STD_P::random_shuffle(begin, end); }
1194
1195   // Sequential fallback.
1196   template<typename RandomAccessIterator, typename RandomNumberGenerator>
1197   inline void
1198   random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator& rand, __gnu_parallel::sequential_tag)
1199   { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); }
1200
1201
1202   /** @brief Functor wrapper for std::rand(). */
1203   template<typename must_be_int = int>
1204   struct c_rand_number
1205   {
1206     inline int operator()(int limit)
1207     { return rand() % limit; }
1208   };
1209
1210   // Fill in random number generator.
1211   template<typename RandomAccessIterator>
1212   inline void
1213   random_shuffle(RandomAccessIterator begin, RandomAccessIterator end)
1214   {
1215     c_rand_number<> r;
1216     // Parallelization still possible.
1217     random_shuffle(begin, end, r);
1218   }
1219
1220   // Parallel algorithm for random access iterators.
1221   template<typename RandomAccessIterator, typename RandomNumberGenerator>
1222   void
1223   random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator& rand)
1224   {
1225     if (begin == end)
1226       return;
1227     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::random_shuffle_minimal_n))
1228       __gnu_parallel::parallel_random_shuffle(begin, end, rand);
1229     else
1230       __gnu_parallel::sequential_random_shuffle(begin, end, rand);
1231   }
1232
1233   // Sequential fallback.
1234   template<typename ForwardIterator, typename Predicate>
1235   inline ForwardIterator
1236   partition(ForwardIterator begin, ForwardIterator end, Predicate pred, __gnu_parallel::sequential_tag)
1237   { return _GLIBCXX_STD_P::partition(begin, end, pred); }
1238
1239   // Sequential fallback for input iterator case.
1240   template<typename ForwardIterator, typename Predicate, typename IteratorTag>
1241   inline ForwardIterator
1242   partition_switch(ForwardIterator begin, ForwardIterator end, Predicate pred, IteratorTag)
1243   { return partition(begin, end, pred, __gnu_parallel::sequential_tag()); }
1244
1245   // Parallel algorithm for random access iterators.
1246   template<typename RandomAccessIterator, typename Predicate>
1247   RandomAccessIterator
1248   partition_switch(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, random_access_iterator_tag)
1249   {
1250     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::partition_minimal_n))
1251       {
1252         typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_type;
1253         difference_type middle = __gnu_parallel::parallel_partition(begin, end, pred, __gnu_parallel::get_max_threads());
1254         return begin + middle;
1255       }
1256     else
1257       return partition(begin, end, pred, __gnu_parallel::sequential_tag());
1258   }
1259
1260   // Public interface.
1261   template<typename ForwardIterator, typename Predicate>
1262   inline ForwardIterator
1263   partition(ForwardIterator begin, ForwardIterator end, Predicate pred)
1264   {
1265     return partition_switch(begin, end, pred, typename std::iterator_traits<ForwardIterator>::iterator_category());
1266   }
1267
1268   // Sequential fallback
1269   template<typename RandomAccessIterator>
1270   inline void
1271   sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::sequential_tag)
1272   { _GLIBCXX_STD_P::sort<RandomAccessIterator>(begin, end); }
1273
1274   // Sequential fallback
1275   template<typename RandomAccessIterator, typename Comparator>
1276   inline void
1277   sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, __gnu_parallel::sequential_tag)
1278   { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end, comp); }
1279
1280   // Public interface, insert default comparator
1281   template<typename RandomAccessIterator>
1282   inline void
1283   sort(RandomAccessIterator begin, RandomAccessIterator end)
1284   {
1285     typedef iterator_traits<RandomAccessIterator> traits_type;
1286     typedef typename traits_type::value_type value_type;
1287     sort(begin, end, std::less<value_type>());
1288   }
1289
1290   template<typename RandomAccessIterator, typename Comparator>
1291   void
1292   sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
1293   {
1294     typedef iterator_traits<RandomAccessIterator> traits_type;
1295     typedef typename traits_type::value_type value_type;
1296
1297     if (begin != end)
1298       {
1299         if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::sort_minimal_n))
1300           __gnu_parallel::parallel_sort(begin, end, comp, false);
1301         else
1302           sort<RandomAccessIterator, Comparator>(begin, end, comp, __gnu_parallel::sequential_tag());
1303       }
1304   }
1305
1306   // Sequential fallback.
1307   template<typename RandomAccessIterator>
1308   inline void
1309   stable_sort(RandomAccessIterator begin, RandomAccessIterator end, __gnu_parallel::sequential_tag)
1310   {
1311     return _GLIBCXX_STD_P::stable_sort<RandomAccessIterator>(begin, end);
1312   }
1313
1314   // Sequential fallback.
1315   template<typename RandomAccessIterator, typename Comparator>
1316   inline void
1317   stable_sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, __gnu_parallel::sequential_tag)
1318   {
1319     return _GLIBCXX_STD_P::stable_sort<RandomAccessIterator, Comparator>(begin, end, comp);
1320   }
1321
1322   template<typename RandomAccessIterator>
1323   void
1324   stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
1325   {
1326     typedef iterator_traits<RandomAccessIterator> traits_type;
1327     typedef typename traits_type::value_type value_type;
1328
1329     stable_sort(begin, end, std::less<value_type>());
1330   }
1331
1332   // Parallel algorithm for random access iterators
1333   template<typename RandomAccessIterator, typename Comparator>
1334   void
1335   stable_sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
1336   {
1337     if (begin != end)
1338       {
1339         if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::sort_minimal_n))
1340           __gnu_parallel::parallel_sort(begin, end, comp, true);
1341         else
1342           stable_sort<RandomAccessIterator, Comparator>(begin, end, comp, __gnu_parallel::sequential_tag());
1343       }
1344   }
1345
1346   // Sequential fallback
1347   template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
1348   inline OutputIterator
1349   merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result,
1350         __gnu_parallel::sequential_tag)
1351   {
1352     return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result);
1353   }
1354
1355   // Sequential fallback
1356   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
1357   inline OutputIterator
1358   merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Comparator comp,
1359         __gnu_parallel::sequential_tag)
1360   {
1361     return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp);
1362   }
1363
1364   // Sequential fallback for input iterator case
1365   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator, typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
1366   inline OutputIterator
1367   merge_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Comparator comp, IteratorTag1, IteratorTag2, IteratorTag3)
1368   {
1369     return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp);
1370   }
1371
1372   // Parallel algorithm for random access iterators
1373   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
1374   OutputIterator
1375   merge_switch(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Comparator comp, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag)
1376   {
1377     if (_GLIBCXX_PARALLEL_CONDITION((static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) >= __gnu_parallel::Settings::merge_minimal_n || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2) >= __gnu_parallel::Settings::merge_minimal_n)))
1378       return __gnu_parallel::parallel_merge_advance(begin1, end1, begin2, end2, result, (end1 - begin1) + (end2 - begin2), comp);
1379     else
1380       return __gnu_parallel::merge_advance(begin1, end1, begin2, end2, result, (end1 - begin1) + (end2 - begin2), comp);
1381   }
1382
1383   // Public interface
1384   template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comparator>
1385   inline OutputIterator
1386   merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result, Comparator comp)
1387   {
1388     typedef typename iterator_traits<InputIterator1>::value_type value_type;
1389
1390     typedef std::iterator_traits<InputIterator1> iteratori1_traits;
1391     typedef std::iterator_traits<InputIterator2> iteratori2_traits;
1392     typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1393     typedef typename iteratori1_traits::iterator_category iteratori1_category;
1394     typedef typename iteratori2_traits::iterator_category iteratori2_category;
1395     typedef typename iteratoro_traits::iterator_category iteratoro_category;
1396
1397     return merge_switch(begin1, end1, begin2, end2, result, comp, iteratori1_category(), iteratori2_category(), iteratoro_category());
1398   }
1399
1400
1401   // Public interface, insert default comparator
1402   template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
1403   inline OutputIterator
1404   merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, InputIterator2 end2, OutputIterator result)
1405   {
1406     typedef std::iterator_traits<InputIterator1> iterator1_traits;
1407     typedef std::iterator_traits<InputIterator2> iterator2_traits;
1408     typedef typename iterator1_traits::value_type value1_type;
1409     typedef typename iterator2_traits::value_type value2_type;
1410
1411     return merge(begin1, end1, begin2, end2, result, __gnu_parallel::less<value1_type, value2_type>());
1412   }
1413
1414   // Sequential fallback
1415   template<typename RandomAccessIterator>
1416   inline void
1417   nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, __gnu_parallel::sequential_tag)
1418   { return _GLIBCXX_STD_P::nth_element(begin, nth, end); }
1419
1420   // Sequential fallback
1421   template<typename RandomAccessIterator, typename Comparator>
1422   void
1423   nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp, __gnu_parallel::sequential_tag)
1424   { return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); }
1425
1426   // Public interface
1427   template<typename RandomAccessIterator, typename Comparator>
1428   inline void
1429   nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp)
1430   {
1431     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::nth_element_minimal_n))
1432       __gnu_parallel::parallel_nth_element(begin, nth, end, comp);
1433     else
1434       nth_element(begin, nth, end, comp, __gnu_parallel::sequential_tag());
1435   }
1436
1437   // Public interface, insert default comparator
1438   template<typename RandomAccessIterator>
1439   void
1440   nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end)
1441   {
1442     typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
1443     nth_element(begin, nth, end, std::less<value_type>());
1444   }
1445
1446   // Sequential fallback
1447   template<typename _RandomAccessIterator, typename _Compare>
1448   void
1449   partial_sort(_RandomAccessIterator begin, _RandomAccessIterator middle, _RandomAccessIterator end, _Compare comp, __gnu_parallel::sequential_tag)
1450   { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); }
1451
1452   // Sequential fallback
1453   template<typename _RandomAccessIterator>
1454   void
1455   partial_sort(_RandomAccessIterator begin, _RandomAccessIterator middle, _RandomAccessIterator end, __gnu_parallel::sequential_tag)
1456   { _GLIBCXX_STD_P::partial_sort(begin, middle, end); }
1457
1458   // Public interface, parallel algorithm for random access iterators
1459   template<typename _RandomAccessIterator, typename _Compare>
1460   void
1461   partial_sort(_RandomAccessIterator begin, _RandomAccessIterator middle, _RandomAccessIterator end, _Compare comp)
1462   {
1463     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::partial_sort_minimal_n))
1464       __gnu_parallel::parallel_partial_sort(begin, middle, end, comp);
1465     else
1466       partial_sort(begin, middle, end, comp, __gnu_parallel::sequential_tag());
1467   }
1468
1469   // Public interface, insert default comparator
1470   template<typename _RandomAccessIterator>
1471   void
1472   partial_sort(_RandomAccessIterator begin, _RandomAccessIterator middle, _RandomAccessIterator end)
1473   {
1474     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
1475     partial_sort(begin, middle, end, std::less<value_type>());
1476   }
1477
1478   // Sequential fallback
1479   template<typename ForwardIterator>
1480   inline ForwardIterator
1481   max_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::sequential_tag)
1482   { return _GLIBCXX_STD_P::max_element(begin, end); }
1483
1484   // Sequential fallback
1485   template<typename ForwardIterator, typename Comparator>
1486   inline ForwardIterator
1487   max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::sequential_tag)
1488   { return _GLIBCXX_STD_P::max_element(begin, end, comp); }
1489
1490   // Sequential fallback for input iterator case
1491   template<typename ForwardIterator, typename Comparator, typename IteratorTag>
1492   ForwardIterator
1493   max_element_switch(ForwardIterator begin, ForwardIterator end, Comparator comp, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
1494   { return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
1495
1496   // Public interface, insert default comparator
1497   template<typename ForwardIterator>
1498   inline ForwardIterator
1499   max_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1500   {
1501     typedef typename iterator_traits<ForwardIterator>::value_type value_type;
1502     return max_element(begin, end, std::less<value_type>(), parallelism_tag);
1503   }
1504
1505   template<typename RandomAccessIterator, typename Comparator>
1506   RandomAccessIterator
1507   max_element_switch(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1508   {
1509     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::max_element_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
1510       {
1511         RandomAccessIterator res(begin);
1512         __gnu_parallel::identity_selector<RandomAccessIterator> functionality;
1513         __gnu_parallel::for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel::max_element_reduct<Comparator, RandomAccessIterator>(comp), res, res, -1, parallelism_tag);
1514         return res;
1515       }
1516     else
1517       return max_element(begin, end, __gnu_parallel::sequential_tag());
1518   }
1519
1520   // Public interface
1521   template<typename ForwardIterator, typename Comparator>
1522   inline ForwardIterator
1523   max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1524   {
1525     return max_element_switch(begin, end, comp, typename std::iterator_traits<ForwardIterator>::iterator_category(), parallelism_tag);
1526   }
1527
1528   // Sequential fallback
1529   template<typename ForwardIterator>
1530   inline
1531   ForwardIterator
1532   min_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::sequential_tag)
1533   { return _GLIBCXX_STD_P::min_element(begin, end); }
1534
1535   // Sequential fallback
1536   template<typename ForwardIterator, typename Comparator>
1537   inline ForwardIterator
1538   min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::sequential_tag)
1539   { return _GLIBCXX_STD_P::min_element(begin, end, comp); }
1540
1541   // Public interface
1542   template<typename ForwardIterator>
1543   inline ForwardIterator
1544   min_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::parallelism parallelism_tag  = __gnu_parallel::parallel_balanced)
1545   {
1546     typedef typename iterator_traits<ForwardIterator>::value_type value_type;
1547     return min_element(begin, end, std::less<value_type>(), parallelism_tag);
1548   }
1549
1550   // Sequential fallback for input iterator case
1551   template<typename ForwardIterator, typename Comparator, typename IteratorTag>
1552   ForwardIterator
1553   min_element_switch(ForwardIterator begin, ForwardIterator end, Comparator comp, IteratorTag, __gnu_parallel::parallelism parallelism_tag)
1554   { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
1555
1556   // Parallel algorithm for random access iterators
1557   template<typename RandomAccessIterator, typename Comparator>
1558   RandomAccessIterator
1559   min_element_switch(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, random_access_iterator_tag, __gnu_parallel::parallelism parallelism_tag)
1560   {
1561     if (_GLIBCXX_PARALLEL_CONDITION(static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::Settings::min_element_minimal_n && __gnu_parallel::is_parallel(parallelism_tag)))
1562       {
1563         RandomAccessIterator res(begin);
1564         __gnu_parallel::identity_selector<RandomAccessIterator> functionality;
1565         __gnu_parallel::for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel::min_element_reduct<Comparator, RandomAccessIterator>(comp), res, res, -1, parallelism_tag);
1566         return res;
1567       }
1568     else
1569       return min_element(begin, end, __gnu_parallel::sequential_tag());
1570   }
1571
1572   // Public interface
1573   template<typename ForwardIterator, typename Comparator>
1574   inline ForwardIterator
1575   min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::parallelism parallelism_tag = __gnu_parallel::parallel_balanced)
1576   {
1577     typedef iterator_traits<ForwardIterator> traits_type;
1578     typedef typename traits_type::iterator_category iterator_category;
1579     return min_element_switch(begin, end, comp, iterator_category(), parallelism_tag);
1580   }
1581 } // end namespace
1582 } // end namespace
1583
1584 #endif /* _GLIBCXX_ALGORITHM_H */
1585