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

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