include » parallel

algo.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file parallel/algo.h
00026  *  @brief Parallel STL function calls corresponding to the stl_algo.h header.
00027  *
00028  *  The functions defined here mainly do case switches and
00029  *  call the actual parallelized versions in other files.
00030  *  Inlining policy: Functions that basically only contain one function call,
00031  *  are declared inline.
00032  *  This file is a GNU parallel extension to the Standard C++ Library.
00033  */
00034 
00035 // Written by Johannes Singler and Felix Putze.
00036 
00037 #ifndef _GLIBCXX_PARALLEL_ALGO_H
00038 #define _GLIBCXX_PARALLEL_ALGO_H 1
00039 
00040 #include <parallel/algorithmfwd.h>
00041 #include <bits/stl_algobase.h>
00042 #include <bits/stl_algo.h>
00043 #include <parallel/iterator.h>
00044 #include <parallel/base.h>
00045 #include <parallel/sort.h>
00046 #include <parallel/workstealing.h>
00047 #include <parallel/par_loop.h>
00048 #include <parallel/omp_loop.h>
00049 #include <parallel/omp_loop_static.h>
00050 #include <parallel/for_each_selectors.h>
00051 #include <parallel/for_each.h>
00052 #include <parallel/find.h>
00053 #include <parallel/find_selectors.h>
00054 #include <parallel/search.h>
00055 #include <parallel/random_shuffle.h>
00056 #include <parallel/partition.h>
00057 #include <parallel/merge.h>
00058 #include <parallel/unique_copy.h>
00059 #include <parallel/set_operations.h>
00060 
00061 namespace std
00062 {
00063 namespace __parallel
00064 {
00065   // Sequential fallback
00066   template<typename InputIterator, typename Function>
00067     inline Function
00068     for_each(InputIterator begin, InputIterator end, Function f, 
00069              __gnu_parallel::sequential_tag)
00070     { return _GLIBCXX_STD_P::for_each(begin, end, f); }
00071 
00072 
00073   // Sequential fallback for input iterator case
00074   template<typename InputIterator, typename Function, typename IteratorTag>
00075     inline Function
00076     for_each_switch(InputIterator begin, InputIterator end, Function f, 
00077                     IteratorTag)
00078     { return for_each(begin, end, f, __gnu_parallel::sequential_tag()); }
00079 
00080   // Parallel algorithm for random access iterators
00081   template<typename RandomAccessIterator, typename Function>
00082     Function
00083     for_each_switch(RandomAccessIterator begin, RandomAccessIterator end, 
00084                     Function f, random_access_iterator_tag, 
00085                     __gnu_parallel::_Parallelism parallelism_tag
00086                     = __gnu_parallel::parallel_balanced)
00087     {
00088       if (_GLIBCXX_PARALLEL_CONDITION(
00089             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
00090             >= __gnu_parallel::_Settings::get().for_each_minimal_n
00091             && __gnu_parallel::is_parallel(parallelism_tag)))
00092         {
00093           bool dummy;
00094     __gnu_parallel::for_each_selector<RandomAccessIterator> functionality;
00095 
00096           return __gnu_parallel::
00097             for_each_template_random_access(begin, end, f, functionality,
00098                                             __gnu_parallel::dummy_reduct(),
00099                                             true, dummy, -1, parallelism_tag);
00100         }
00101       else
00102         return for_each(begin, end, f, __gnu_parallel::sequential_tag());
00103     }
00104 
00105   // Public interface
00106   template<typename Iterator, typename Function>
00107     inline Function
00108     for_each(Iterator begin, Iterator end, Function f, 
00109              __gnu_parallel::_Parallelism parallelism_tag)
00110     {
00111       typedef std::iterator_traits<Iterator> iterator_traits;
00112       typedef typename iterator_traits::iterator_category iterator_category;
00113       return for_each_switch(begin, end, f, iterator_category(), 
00114                              parallelism_tag);
00115     }
00116 
00117   template<typename Iterator, typename Function>
00118     inline Function
00119     for_each(Iterator begin, Iterator end, Function f) 
00120     {
00121       typedef std::iterator_traits<Iterator> iterator_traits;
00122       typedef typename iterator_traits::iterator_category iterator_category;
00123       return for_each_switch(begin, end, f, iterator_category());
00124     }
00125 
00126 
00127   // Sequential fallback
00128   template<typename InputIterator, typename T>
00129     inline InputIterator
00130     find(InputIterator begin, InputIterator end, const T& val, 
00131          __gnu_parallel::sequential_tag)
00132     { return _GLIBCXX_STD_P::find(begin, end, val); }
00133 
00134   // Sequential fallback for input iterator case
00135   template<typename InputIterator, typename T, typename IteratorTag>
00136     inline InputIterator
00137     find_switch(InputIterator begin, InputIterator end, const T& val,
00138                 IteratorTag)
00139     { return _GLIBCXX_STD_P::find(begin, end, val); }
00140 
00141   // Parallel find for random access iterators
00142   template<typename RandomAccessIterator, typename T>
00143     RandomAccessIterator
00144     find_switch(RandomAccessIterator begin, RandomAccessIterator end,
00145                 const T& val, random_access_iterator_tag)
00146     {
00147       typedef iterator_traits<RandomAccessIterator> traits_type;
00148       typedef typename traits_type::value_type value_type;
00149 
00150       if (_GLIBCXX_PARALLEL_CONDITION(true))
00151         {
00152           binder2nd<__gnu_parallel::equal_to<value_type, T> >
00153             comp(__gnu_parallel::equal_to<value_type, T>(), val);
00154           return __gnu_parallel::find_template(begin, end, begin, comp,
00155                                                __gnu_parallel::
00156                                                find_if_selector()).first;
00157         }
00158       else
00159         return _GLIBCXX_STD_P::find(begin, end, val);
00160     }
00161 
00162   // Public interface
00163   template<typename InputIterator, typename T>
00164     inline InputIterator
00165     find(InputIterator begin, InputIterator end, const T& val)
00166     {
00167       typedef std::iterator_traits<InputIterator> iterator_traits;
00168       typedef typename iterator_traits::iterator_category iterator_category;
00169       return find_switch(begin, end, val, iterator_category());
00170     }
00171 
00172   // Sequential fallback
00173   template<typename InputIterator, typename Predicate>
00174     inline InputIterator
00175     find_if(InputIterator begin, InputIterator end, Predicate pred, 
00176             __gnu_parallel::sequential_tag)
00177     { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
00178 
00179   // Sequential fallback for input iterator case
00180   template<typename InputIterator, typename Predicate, typename IteratorTag>
00181     inline InputIterator
00182     find_if_switch(InputIterator begin, InputIterator end, Predicate pred, 
00183                    IteratorTag)
00184     { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
00185 
00186   // Parallel find_if for random access iterators
00187   template<typename RandomAccessIterator, typename Predicate>
00188     RandomAccessIterator
00189     find_if_switch(RandomAccessIterator begin, RandomAccessIterator end, 
00190                    Predicate pred, random_access_iterator_tag)
00191     {
00192       if (_GLIBCXX_PARALLEL_CONDITION(true))
00193         return __gnu_parallel::find_template(begin, end, begin, pred, 
00194                                              __gnu_parallel::
00195                                              find_if_selector()).first;
00196       else
00197         return _GLIBCXX_STD_P::find_if(begin, end, pred);
00198     }
00199 
00200   // Public interface
00201   template<typename InputIterator, typename Predicate>
00202     inline InputIterator
00203     find_if(InputIterator begin, InputIterator end, Predicate pred)
00204     {
00205       typedef std::iterator_traits<InputIterator> iterator_traits;
00206       typedef typename iterator_traits::iterator_category iterator_category;
00207       return find_if_switch(begin, end, pred, iterator_category());
00208     }
00209 
00210   // Sequential fallback
00211   template<typename InputIterator, typename ForwardIterator>
00212     inline InputIterator
00213     find_first_of(InputIterator begin1, InputIterator end1, 
00214                   ForwardIterator begin2, ForwardIterator end2, 
00215                   __gnu_parallel::sequential_tag)
00216     { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2); }
00217 
00218   // Sequential fallback
00219   template<typename InputIterator, typename ForwardIterator,
00220            typename BinaryPredicate>
00221     inline InputIterator
00222     find_first_of(InputIterator begin1, InputIterator end1,
00223                   ForwardIterator begin2, ForwardIterator end2,
00224                   BinaryPredicate comp, __gnu_parallel::sequential_tag)
00225   { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2, comp); }
00226 
00227   // Sequential fallback for input iterator type
00228   template<typename InputIterator, typename ForwardIterator,
00229            typename IteratorTag1, typename IteratorTag2>
00230     inline InputIterator
00231     find_first_of_switch(InputIterator begin1, InputIterator end1,
00232                          ForwardIterator begin2, ForwardIterator end2, 
00233                          IteratorTag1, IteratorTag2)
00234     { return find_first_of(begin1, end1, begin2, end2, 
00235                            __gnu_parallel::sequential_tag()); }
00236 
00237   // Parallel algorithm for random access iterators
00238   template<typename RandomAccessIterator, typename ForwardIterator,
00239            typename BinaryPredicate, typename IteratorTag>
00240     inline RandomAccessIterator
00241     find_first_of_switch(RandomAccessIterator begin1,
00242                          RandomAccessIterator end1,
00243                          ForwardIterator begin2, ForwardIterator end2, 
00244                          BinaryPredicate comp, random_access_iterator_tag, 
00245                          IteratorTag)
00246     {
00247       return __gnu_parallel::
00248         find_template(begin1, end1, begin1, comp,
00249                       __gnu_parallel::find_first_of_selector
00250                       <ForwardIterator>(begin2, end2)).first;
00251     }
00252 
00253   // Sequential fallback for input iterator type
00254   template<typename InputIterator, typename ForwardIterator,
00255            typename BinaryPredicate, typename IteratorTag1,
00256            typename IteratorTag2>
00257     inline InputIterator
00258     find_first_of_switch(InputIterator begin1, InputIterator end1,
00259                          ForwardIterator begin2, ForwardIterator end2, 
00260                          BinaryPredicate comp, IteratorTag1, IteratorTag2)
00261     { return find_first_of(begin1, end1, begin2, end2, comp, 
00262                            __gnu_parallel::sequential_tag()); }
00263 
00264   // Public interface
00265   template<typename InputIterator, typename ForwardIterator,
00266            typename BinaryPredicate>
00267     inline InputIterator
00268     find_first_of(InputIterator begin1, InputIterator end1,
00269                   ForwardIterator begin2, ForwardIterator end2, 
00270                   BinaryPredicate comp)
00271     {
00272       typedef std::iterator_traits<InputIterator> iteratori_traits;
00273       typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
00274       typedef typename iteratori_traits::iterator_category iteratori_category;
00275       typedef typename iteratorf_traits::iterator_category iteratorf_category;
00276 
00277       return find_first_of_switch(begin1, end1, begin2, end2, comp,
00278                                   iteratori_category(), iteratorf_category());
00279     }
00280 
00281   // Public interface, insert default comparator
00282   template<typename InputIterator, typename ForwardIterator>
00283     inline InputIterator
00284     find_first_of(InputIterator begin1, InputIterator end1, 
00285                   ForwardIterator begin2, ForwardIterator end2)
00286     {
00287       typedef std::iterator_traits<InputIterator> iteratori_traits;
00288       typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
00289       typedef typename iteratori_traits::value_type valuei_type;
00290       typedef typename iteratorf_traits::value_type valuef_type;
00291 
00292       return find_first_of(begin1, end1, begin2, end2, __gnu_parallel::
00293                            equal_to<valuei_type, valuef_type>());
00294     }
00295 
00296   // Sequential fallback
00297   template<typename InputIterator, typename OutputIterator>
00298     inline OutputIterator
00299     unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
00300                 __gnu_parallel::sequential_tag)
00301     { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out); }
00302 
00303   // Sequential fallback
00304   template<typename InputIterator, typename OutputIterator,
00305            typename Predicate>
00306     inline OutputIterator
00307     unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
00308                 Predicate pred, __gnu_parallel::sequential_tag)
00309     { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out, pred); }
00310 
00311   // Sequential fallback for input iterator case
00312   template<typename InputIterator, typename OutputIterator,
00313            typename Predicate, typename IteratorTag1, typename IteratorTag2>
00314     inline OutputIterator
00315     unique_copy_switch(InputIterator begin, InputIterator last, 
00316                        OutputIterator out, Predicate pred, 
00317                        IteratorTag1, IteratorTag2)
00318     { return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred); }
00319 
00320   // Parallel unique_copy for random access iterators
00321   template<typename RandomAccessIterator, typename RandomAccessOutputIterator,
00322            typename Predicate>
00323     RandomAccessOutputIterator
00324     unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last, 
00325                        RandomAccessOutputIterator out, Predicate pred, 
00326                        random_access_iterator_tag, random_access_iterator_tag)
00327     {
00328       if (_GLIBCXX_PARALLEL_CONDITION(
00329             static_cast<__gnu_parallel::sequence_index_t>(last - begin)
00330             > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
00331         return __gnu_parallel::parallel_unique_copy(begin, last, out, pred);
00332       else
00333         return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
00334     }
00335 
00336   // Public interface
00337   template<typename InputIterator, typename OutputIterator>
00338     inline OutputIterator
00339     unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out)
00340     {
00341       typedef std::iterator_traits<InputIterator> iteratori_traits;
00342       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00343       typedef typename iteratori_traits::iterator_category iteratori_category;
00344       typedef typename iteratori_traits::value_type value_type;
00345       typedef typename iteratoro_traits::iterator_category iteratoro_category;
00346 
00347       return unique_copy_switch(begin1, end1, out, equal_to<value_type>(),
00348                                 iteratori_category(), iteratoro_category());
00349     }
00350 
00351   // Public interface
00352   template<typename InputIterator, typename OutputIterator, typename Predicate>
00353     inline OutputIterator
00354     unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
00355                 Predicate pred)
00356     {
00357       typedef std::iterator_traits<InputIterator> iteratori_traits;
00358       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00359       typedef typename iteratori_traits::iterator_category iteratori_category;
00360       typedef typename iteratoro_traits::iterator_category iteratoro_category;
00361 
00362       return unique_copy_switch(begin1, end1, out, pred, iteratori_category(), 
00363                                 iteratoro_category());
00364     }
00365 
00366   // Sequential fallback
00367   template<typename InputIterator1, typename InputIterator2,
00368            typename OutputIterator>
00369     inline OutputIterator
00370     set_union(InputIterator1 begin1, InputIterator1 end1,
00371               InputIterator2 begin2, InputIterator2 end2,
00372               OutputIterator out, __gnu_parallel::sequential_tag)
00373     { return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out); }
00374 
00375   // Sequential fallback
00376   template<typename InputIterator1, typename InputIterator2,
00377            typename OutputIterator, typename Predicate>
00378     inline OutputIterator
00379     set_union(InputIterator1 begin1, InputIterator1 end1,
00380               InputIterator2 begin2, InputIterator2 end2,
00381               OutputIterator out, Predicate pred,
00382               __gnu_parallel::sequential_tag)
00383     { return _GLIBCXX_STD_P::set_union(begin1, end1,
00384                                        begin2, end2, out, pred); }
00385 
00386   // Sequential fallback for input iterator case
00387   template<typename InputIterator1, typename InputIterator2,
00388            typename Predicate, typename OutputIterator,
00389            typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
00390     inline OutputIterator
00391     set_union_switch(InputIterator1 begin1, InputIterator1 end1, 
00392                      InputIterator2 begin2, InputIterator2 end2, 
00393                      OutputIterator result, Predicate pred, IteratorTag1,
00394                      IteratorTag2, IteratorTag3)
00395     { return _GLIBCXX_STD_P::set_union(begin1, end1,
00396                                        begin2, end2, result, pred); }
00397 
00398   // Parallel set_union for random access iterators
00399   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00400            typename OutputRandomAccessIterator, typename Predicate>
00401     OutputRandomAccessIterator
00402     set_union_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, 
00403                      RandomAccessIterator2 begin2, RandomAccessIterator2 end2, 
00404                      OutputRandomAccessIterator result, Predicate pred,
00405                      random_access_iterator_tag, random_access_iterator_tag, 
00406                      random_access_iterator_tag)
00407     {
00408       if (_GLIBCXX_PARALLEL_CONDITION(
00409             static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
00410             >= __gnu_parallel::_Settings::get().set_union_minimal_n
00411             || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
00412             >= __gnu_parallel::_Settings::get().set_union_minimal_n))
00413         return __gnu_parallel::parallel_set_union(begin1, end1,
00414                                                   begin2, end2, result, pred);
00415       else
00416         return _GLIBCXX_STD_P::set_union(begin1, end1,
00417                                          begin2, end2, result, pred);
00418     }
00419 
00420   // Public interface
00421   template<typename InputIterator1, typename InputIterator2,
00422            typename OutputIterator>
00423     inline OutputIterator 
00424     set_union(InputIterator1 begin1, InputIterator1 end1,
00425               InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
00426     {
00427       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00428       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00429       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00430       typedef typename iteratori1_traits::iterator_category
00431         iteratori1_category;
00432       typedef typename iteratori2_traits::iterator_category
00433         iteratori2_category;
00434       typedef typename iteratoro_traits::iterator_category iteratoro_category;
00435       typedef typename iteratori1_traits::value_type value1_type;
00436       typedef typename iteratori2_traits::value_type value2_type;
00437 
00438       return set_union_switch(begin1, end1, begin2, end2, out, 
00439                               __gnu_parallel::less<value1_type, value2_type>(),
00440                               iteratori1_category(), iteratori2_category(),
00441                               iteratoro_category());
00442     }
00443 
00444   // Public interface
00445   template<typename InputIterator1, typename InputIterator2,
00446            typename OutputIterator, typename Predicate>
00447     inline OutputIterator 
00448     set_union(InputIterator1 begin1, InputIterator1 end1,
00449               InputIterator2 begin2, InputIterator2 end2,
00450               OutputIterator out, Predicate pred)
00451     {
00452       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00453       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00454       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00455       typedef typename iteratori1_traits::iterator_category
00456         iteratori1_category;
00457       typedef typename iteratori2_traits::iterator_category
00458         iteratori2_category;
00459       typedef typename iteratoro_traits::iterator_category iteratoro_category;
00460 
00461       return set_union_switch(begin1, end1, begin2, end2, out, pred,
00462                               iteratori1_category(), iteratori2_category(),
00463                               iteratoro_category());
00464     }
00465 
00466   // Sequential fallback.
00467   template<typename InputIterator1, typename InputIterator2,
00468            typename OutputIterator>
00469     inline OutputIterator
00470     set_intersection(InputIterator1 begin1, InputIterator1 end1,
00471                      InputIterator2 begin2, InputIterator2 end2,
00472                      OutputIterator out, __gnu_parallel::sequential_tag)
00473     { return _GLIBCXX_STD_P::set_intersection(begin1, end1,
00474                                               begin2, end2, out); }
00475 
00476   // Sequential fallback.
00477   template<typename InputIterator1, typename InputIterator2,
00478            typename OutputIterator, typename Predicate>
00479     inline OutputIterator
00480     set_intersection(InputIterator1 begin1, InputIterator1 end1,
00481                      InputIterator2 begin2, InputIterator2 end2,
00482                      OutputIterator out, Predicate pred, 
00483                      __gnu_parallel::sequential_tag)
00484     { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2, 
00485                                               out, pred); }
00486 
00487   // Sequential fallback for input iterator case
00488   template<typename InputIterator1, typename InputIterator2,
00489            typename Predicate, typename OutputIterator,
00490            typename IteratorTag1, typename IteratorTag2,
00491            typename IteratorTag3>
00492     inline OutputIterator 
00493     set_intersection_switch(InputIterator1 begin1, InputIterator1 end1, 
00494                             InputIterator2 begin2, InputIterator2 end2, 
00495                             OutputIterator result, Predicate pred, 
00496                             IteratorTag1, IteratorTag2, IteratorTag3)
00497     { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, 
00498                                               end2, result, pred); }
00499 
00500   // Parallel set_intersection for random access iterators
00501   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00502            typename OutputRandomAccessIterator, typename Predicate>
00503     OutputRandomAccessIterator
00504     set_intersection_switch(RandomAccessIterator1 begin1,
00505                             RandomAccessIterator1 end1,
00506                             RandomAccessIterator2 begin2,
00507                             RandomAccessIterator2 end2,
00508                             OutputRandomAccessIterator result,
00509                             Predicate pred,
00510                             random_access_iterator_tag,
00511                             random_access_iterator_tag,
00512                             random_access_iterator_tag)
00513     {
00514       if (_GLIBCXX_PARALLEL_CONDITION(
00515             static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
00516             >= __gnu_parallel::_Settings::get().set_union_minimal_n
00517             || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
00518             >= __gnu_parallel::_Settings::get().set_union_minimal_n))
00519         return __gnu_parallel::parallel_set_intersection(begin1, end1, begin2, 
00520                                                          end2, result, pred);
00521       else
00522         return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, 
00523                                                 end2, result, pred);
00524     }
00525 
00526   // Public interface
00527   template<typename InputIterator1, typename InputIterator2,
00528            typename OutputIterator>
00529     inline OutputIterator 
00530     set_intersection(InputIterator1 begin1, InputIterator1 end1, 
00531                      InputIterator2 begin2, InputIterator2 end2, 
00532                      OutputIterator out)
00533     {
00534       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00535       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00536       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00537       typedef typename iteratori1_traits::iterator_category
00538         iteratori1_category;
00539       typedef typename iteratori2_traits::iterator_category
00540         iteratori2_category;
00541       typedef typename iteratoro_traits::iterator_category iteratoro_category;
00542       typedef typename iteratori1_traits::value_type value1_type;
00543       typedef typename iteratori2_traits::value_type value2_type;
00544 
00545       return set_intersection_switch(begin1, end1, begin2, end2, out,
00546                                      __gnu_parallel::
00547                                      less<value1_type, value2_type>(),
00548                                      iteratori1_category(),
00549                                      iteratori2_category(), 
00550                                      iteratoro_category());
00551     }
00552 
00553   template<typename InputIterator1, typename InputIterator2,
00554            typename OutputIterator, typename Predicate>
00555     inline OutputIterator 
00556     set_intersection(InputIterator1 begin1, InputIterator1 end1,
00557                      InputIterator2 begin2, InputIterator2 end2,
00558                      OutputIterator out, Predicate pred)
00559     {
00560       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00561       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00562       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00563       typedef typename iteratori1_traits::iterator_category
00564         iteratori1_category;
00565       typedef typename iteratori2_traits::iterator_category
00566         iteratori2_category;
00567       typedef typename iteratoro_traits::iterator_category iteratoro_category;
00568 
00569       return set_intersection_switch(begin1, end1, begin2, end2, out, pred,
00570                                      iteratori1_category(),
00571                                      iteratori2_category(),
00572                                      iteratoro_category());
00573     }
00574 
00575   // Sequential fallback
00576   template<typename InputIterator1, typename InputIterator2,
00577            typename OutputIterator>
00578     inline OutputIterator
00579     set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
00580                              InputIterator2 begin2, InputIterator2 end2,
00581                              OutputIterator out,
00582                              __gnu_parallel::sequential_tag)
00583     { return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1,
00584                                                       begin2, end2, out); }
00585 
00586   // Sequential fallback
00587   template<typename InputIterator1, typename InputIterator2,
00588            typename OutputIterator, typename Predicate>
00589     inline OutputIterator
00590     set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
00591                              InputIterator2 begin2, InputIterator2 end2,
00592                              OutputIterator out, Predicate pred,
00593                              __gnu_parallel::sequential_tag)
00594     { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2,
00595                                                       end2, out, pred); }
00596 
00597   // Sequential fallback for input iterator case
00598   template<typename InputIterator1, typename InputIterator2,
00599            typename Predicate, typename OutputIterator,
00600            typename IteratorTag1, typename IteratorTag2,
00601            typename IteratorTag3>
00602     inline OutputIterator 
00603     set_symmetric_difference_switch(InputIterator1 begin1,
00604                                     InputIterator1 end1,
00605                                     InputIterator2 begin2,
00606                                     InputIterator2 end2,
00607                                     OutputIterator result, Predicate pred,
00608                                     IteratorTag1, IteratorTag2, IteratorTag3)
00609     { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
00610                                                       begin2, end2,
00611                                                       result, pred); }
00612 
00613   // Parallel set_symmetric_difference for random access iterators
00614   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00615            typename OutputRandomAccessIterator, typename Predicate>
00616     OutputRandomAccessIterator
00617     set_symmetric_difference_switch(RandomAccessIterator1 begin1,
00618                                     RandomAccessIterator1 end1,
00619                                     RandomAccessIterator2 begin2,
00620                                     RandomAccessIterator2 end2,
00621                                     OutputRandomAccessIterator result,
00622                                     Predicate pred,
00623                                     random_access_iterator_tag,
00624                                     random_access_iterator_tag,
00625                                     random_access_iterator_tag)
00626     {
00627       if (_GLIBCXX_PARALLEL_CONDITION(
00628       static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
00629       >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
00630       || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
00631       >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n))
00632   return __gnu_parallel::parallel_set_symmetric_difference(begin1, end1,
00633                                                                  begin2, end2,
00634                                                                  result, pred);
00635       else
00636         return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
00637                                                         begin2, end2,
00638                                                         result, pred);
00639     }
00640 
00641   // Public interface.
00642   template<typename InputIterator1, typename InputIterator2,
00643            typename OutputIterator>
00644     inline OutputIterator 
00645     set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
00646                              InputIterator2 begin2, InputIterator2 end2,
00647                              OutputIterator out)
00648     {
00649       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00650       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00651       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00652       typedef typename iteratori1_traits::iterator_category
00653         iteratori1_category;
00654       typedef typename iteratori2_traits::iterator_category
00655         iteratori2_category;
00656       typedef typename iteratoro_traits::iterator_category iteratoro_category;
00657       typedef typename iteratori1_traits::value_type value1_type;
00658       typedef typename iteratori2_traits::value_type value2_type;
00659 
00660       return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
00661                                              __gnu_parallel::
00662                                              less<value1_type, value2_type>(),
00663                                              iteratori1_category(),
00664                                              iteratori2_category(),
00665                                              iteratoro_category());
00666     }
00667 
00668   // Public interface.
00669   template<typename InputIterator1, typename InputIterator2,
00670            typename OutputIterator, typename Predicate>
00671     inline OutputIterator 
00672     set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
00673                              InputIterator2 begin2, InputIterator2 end2,
00674                              OutputIterator out, Predicate pred)
00675     {
00676       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00677       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00678       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00679       typedef typename iteratori1_traits::iterator_category
00680         iteratori1_category;
00681       typedef typename iteratori2_traits::iterator_category
00682         iteratori2_category;
00683       typedef typename iteratoro_traits::iterator_category iteratoro_category;
00684 
00685       return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
00686                                              pred, iteratori1_category(),
00687                                              iteratori2_category(),
00688                                              iteratoro_category());
00689     }
00690 
00691   // Sequential fallback.
00692   template<typename InputIterator1, typename InputIterator2,
00693            typename OutputIterator>
00694     inline OutputIterator
00695     set_difference(InputIterator1 begin1, InputIterator1 end1, 
00696                    InputIterator2 begin2, InputIterator2 end2, 
00697                    OutputIterator out, __gnu_parallel::sequential_tag)
00698     { return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out); }
00699 
00700   // Sequential fallback.
00701   template<typename InputIterator1, typename InputIterator2,
00702            typename OutputIterator, typename Predicate>
00703     inline OutputIterator
00704     set_difference(InputIterator1 begin1, InputIterator1 end1, 
00705                    InputIterator2 begin2, InputIterator2 end2, 
00706                    OutputIterator out, Predicate pred, 
00707                    __gnu_parallel::sequential_tag)
00708     { return _GLIBCXX_STD_P::set_difference(begin1, end1,
00709                                             begin2, end2, out, pred); }
00710 
00711   // Sequential fallback for input iterator case.
00712   template<typename InputIterator1, typename InputIterator2,
00713            typename Predicate, typename OutputIterator,
00714            typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
00715     inline OutputIterator
00716     set_difference_switch(InputIterator1 begin1, InputIterator1 end1, 
00717                           InputIterator2 begin2, InputIterator2 end2, 
00718                           OutputIterator result, Predicate pred, 
00719                           IteratorTag1, IteratorTag2, IteratorTag3)
00720     { return _GLIBCXX_STD_P::set_difference(begin1, end1,
00721                                             begin2, end2, result, pred); }
00722 
00723   // Parallel set_difference for random access iterators
00724   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00725            typename OutputRandomAccessIterator, typename Predicate>
00726     OutputRandomAccessIterator
00727     set_difference_switch(RandomAccessIterator1 begin1,
00728                           RandomAccessIterator1 end1,
00729                           RandomAccessIterator2 begin2,
00730                           RandomAccessIterator2 end2,
00731                           OutputRandomAccessIterator result, Predicate pred,
00732                           random_access_iterator_tag,
00733                           random_access_iterator_tag,
00734                           random_access_iterator_tag)
00735     {
00736       if (_GLIBCXX_PARALLEL_CONDITION(
00737             static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
00738             >= __gnu_parallel::_Settings::get().set_difference_minimal_n
00739             || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
00740             >= __gnu_parallel::_Settings::get().set_difference_minimal_n))
00741         return __gnu_parallel::parallel_set_difference(begin1, end1,
00742                                                        begin2, end2,
00743                                                        result, pred);
00744       else
00745         return _GLIBCXX_STD_P::set_difference(begin1, end1,
00746                                               begin2, end2, result, pred);
00747     }
00748 
00749   // Public interface
00750   template<typename InputIterator1, typename InputIterator2,
00751            typename OutputIterator>
00752     inline OutputIterator
00753     set_difference(InputIterator1 begin1, InputIterator1 end1, 
00754                    InputIterator2 begin2, InputIterator2 end2, 
00755                    OutputIterator out)
00756     {
00757       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00758       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00759       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00760       typedef typename iteratori1_traits::iterator_category
00761         iteratori1_category;
00762       typedef typename iteratori2_traits::iterator_category
00763         iteratori2_category;
00764       typedef typename iteratoro_traits::iterator_category iteratoro_category;
00765       typedef typename iteratori1_traits::value_type value1_type;
00766       typedef typename iteratori2_traits::value_type value2_type;
00767 
00768       return set_difference_switch(begin1, end1, begin2, end2, out,
00769                                    __gnu_parallel::
00770                                    less<value1_type, value2_type>(), 
00771                                    iteratori1_category(),
00772                                    iteratori2_category(), 
00773                                    iteratoro_category());
00774     }
00775 
00776   // Public interface
00777   template<typename InputIterator1, typename InputIterator2,
00778            typename OutputIterator, typename Predicate>
00779     inline OutputIterator
00780     set_difference(InputIterator1 begin1, InputIterator1 end1, 
00781                    InputIterator2 begin2, InputIterator2 end2, 
00782                    OutputIterator out, Predicate pred)
00783     {
00784       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
00785       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
00786       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
00787       typedef typename iteratori1_traits::iterator_category
00788         iteratori1_category;
00789       typedef typename iteratori2_traits::iterator_category
00790         iteratori2_category;
00791       typedef typename iteratoro_traits::iterator_category iteratoro_category;
00792 
00793       return set_difference_switch(begin1, end1, begin2, end2, out, pred,
00794                                    iteratori1_category(),
00795                                    iteratori2_category(), 
00796                                    iteratoro_category());
00797     }
00798 
00799   // Sequential fallback
00800   template<typename ForwardIterator>
00801     inline ForwardIterator
00802     adjacent_find(ForwardIterator begin, ForwardIterator end, 
00803                   __gnu_parallel::sequential_tag)
00804     { return _GLIBCXX_STD_P::adjacent_find(begin, end); }
00805 
00806   // Sequential fallback
00807   template<typename ForwardIterator, typename BinaryPredicate>
00808     inline ForwardIterator
00809     adjacent_find(ForwardIterator begin, ForwardIterator end, 
00810                   BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
00811     { return _GLIBCXX_STD_P::adjacent_find(begin, end, binary_pred); }
00812 
00813   // Parallel algorithm for random access iterators
00814   template<typename RandomAccessIterator>
00815     RandomAccessIterator
00816     adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end, 
00817                          random_access_iterator_tag)
00818     {
00819       typedef iterator_traits<RandomAccessIterator> traits_type;
00820       typedef typename traits_type::value_type value_type;
00821 
00822       if (_GLIBCXX_PARALLEL_CONDITION(true))
00823         {
00824           RandomAccessIterator spot = __gnu_parallel::
00825             find_template(begin, end - 1, begin, equal_to<value_type>(),
00826                           __gnu_parallel::adjacent_find_selector()).first;
00827           if (spot == (end - 1))
00828             return end;
00829           else
00830             return spot;
00831         }
00832       else
00833         return adjacent_find(begin, end, __gnu_parallel::sequential_tag());
00834     }
00835 
00836   // Sequential fallback for input iterator case
00837   template<typename ForwardIterator, typename IteratorTag>
00838     inline ForwardIterator
00839     adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
00840                          IteratorTag)
00841     { return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); }
00842 
00843   // Public interface
00844   template<typename ForwardIterator>
00845     inline ForwardIterator
00846     adjacent_find(ForwardIterator begin, ForwardIterator end)
00847     {
00848       typedef iterator_traits<ForwardIterator> traits_type;
00849       typedef typename traits_type::iterator_category iterator_category;
00850       return adjacent_find_switch(begin, end, iterator_category());
00851     }
00852 
00853   // Sequential fallback for input iterator case
00854   template<typename ForwardIterator, typename BinaryPredicate,
00855            typename IteratorTag>
00856     inline ForwardIterator
00857     adjacent_find_switch(ForwardIterator begin, ForwardIterator end, 
00858                          BinaryPredicate pred, IteratorTag)
00859     { return adjacent_find(begin, end, pred,
00860                            __gnu_parallel::sequential_tag()); }
00861 
00862   // Parallel algorithm for random access iterators
00863   template<typename RandomAccessIterator, typename BinaryPredicate>
00864     RandomAccessIterator
00865     adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end, 
00866                          BinaryPredicate pred, random_access_iterator_tag)
00867     {
00868       if (_GLIBCXX_PARALLEL_CONDITION(true))
00869         return __gnu_parallel::find_template(begin, end, begin, pred, 
00870                                              __gnu_parallel::
00871                                              adjacent_find_selector()).first;
00872       else
00873         return adjacent_find(begin, end, pred,
00874                              __gnu_parallel::sequential_tag());
00875     }
00876 
00877   // Public interface
00878   template<typename ForwardIterator, typename BinaryPredicate>
00879     inline ForwardIterator
00880     adjacent_find(ForwardIterator begin, ForwardIterator end, 
00881                   BinaryPredicate pred)
00882     {
00883       typedef iterator_traits<ForwardIterator> traits_type;
00884       typedef typename traits_type::iterator_category iterator_category;
00885       return adjacent_find_switch(begin, end, pred, iterator_category());
00886     }
00887 
00888   // Sequential fallback
00889   template<typename InputIterator, typename T>
00890     inline typename iterator_traits<InputIterator>::difference_type
00891     count(InputIterator begin, InputIterator end, const T& value, 
00892           __gnu_parallel::sequential_tag)
00893     { return _GLIBCXX_STD_P::count(begin, end, value); }
00894 
00895   // Parallel code for random access iterators
00896   template<typename RandomAccessIterator, typename T>
00897     typename iterator_traits<RandomAccessIterator>::difference_type
00898     count_switch(RandomAccessIterator begin, RandomAccessIterator end, 
00899                  const T& value, random_access_iterator_tag, 
00900                  __gnu_parallel::_Parallelism parallelism_tag 
00901                  = __gnu_parallel::parallel_unbalanced)
00902     {
00903       typedef iterator_traits<RandomAccessIterator> traits_type;
00904       typedef typename traits_type::value_type value_type;
00905       typedef typename traits_type::difference_type difference_type;
00906       typedef __gnu_parallel::sequence_index_t sequence_index_t;
00907 
00908       if (_GLIBCXX_PARALLEL_CONDITION(
00909             static_cast<sequence_index_t>(end - begin)
00910             >= __gnu_parallel::_Settings::get().count_minimal_n
00911             && __gnu_parallel::is_parallel(parallelism_tag)))
00912         {
00913           __gnu_parallel::count_selector<RandomAccessIterator, difference_type>
00914             functionality;
00915           difference_type res = 0;
00916           __gnu_parallel::
00917             for_each_template_random_access(begin, end, value,
00918                                             functionality,
00919                                             std::plus<sequence_index_t>(),
00920                                             res, res, -1, parallelism_tag);
00921           return res;
00922         }
00923       else
00924         return count(begin, end, value, __gnu_parallel::sequential_tag());
00925     }
00926 
00927   // Sequential fallback for input iterator case.
00928   template<typename InputIterator, typename T, typename IteratorTag>
00929     inline typename iterator_traits<InputIterator>::difference_type
00930     count_switch(InputIterator begin, InputIterator end, const T& value, 
00931                  IteratorTag)
00932     { return count(begin, end, value, __gnu_parallel::sequential_tag()); }
00933 
00934   // Public interface.
00935   template<typename InputIterator, typename T>
00936     inline typename iterator_traits<InputIterator>::difference_type
00937     count(InputIterator begin, InputIterator end, const T& value, 
00938           __gnu_parallel::_Parallelism parallelism_tag)
00939     {
00940       typedef iterator_traits<InputIterator> traits_type;
00941       typedef typename traits_type::iterator_category iterator_category;
00942       return count_switch(begin, end, value, iterator_category(), 
00943                           parallelism_tag);
00944     }
00945 
00946   template<typename InputIterator, typename T>
00947     inline typename iterator_traits<InputIterator>::difference_type
00948     count(InputIterator begin, InputIterator end, const T& value)
00949     {
00950       typedef iterator_traits<InputIterator> traits_type;
00951       typedef typename traits_type::iterator_category iterator_category;
00952       return count_switch(begin, end, value, iterator_category());
00953     }
00954 
00955 
00956   // Sequential fallback.
00957   template<typename InputIterator, typename Predicate>
00958     inline typename iterator_traits<InputIterator>::difference_type
00959     count_if(InputIterator begin, InputIterator end, Predicate pred, 
00960              __gnu_parallel::sequential_tag)
00961     { return _GLIBCXX_STD_P::count_if(begin, end, pred); }
00962 
00963   // Parallel count_if for random access iterators
00964   template<typename RandomAccessIterator, typename Predicate>
00965     typename iterator_traits<RandomAccessIterator>::difference_type
00966     count_if_switch(RandomAccessIterator begin, RandomAccessIterator end, 
00967                     Predicate pred, random_access_iterator_tag, 
00968                     __gnu_parallel::_Parallelism parallelism_tag
00969                     = __gnu_parallel::parallel_unbalanced)
00970     {
00971       typedef iterator_traits<RandomAccessIterator> traits_type;
00972       typedef typename traits_type::value_type value_type;
00973       typedef typename traits_type::difference_type difference_type;
00974       typedef __gnu_parallel::sequence_index_t sequence_index_t;
00975 
00976       if (_GLIBCXX_PARALLEL_CONDITION(
00977             static_cast<sequence_index_t>(end - begin)
00978             >= __gnu_parallel::_Settings::get().count_minimal_n
00979             && __gnu_parallel::is_parallel(parallelism_tag)))
00980         {
00981           difference_type res = 0;
00982           __gnu_parallel::
00983             count_if_selector<RandomAccessIterator, difference_type>
00984             functionality;
00985           __gnu_parallel::
00986             for_each_template_random_access(begin, end, pred,
00987                                             functionality,
00988                                             std::plus<sequence_index_t>(),
00989                                             res, res, -1, parallelism_tag);
00990           return res;
00991         }
00992       else
00993         return count_if(begin, end, pred, __gnu_parallel::sequential_tag());
00994     }
00995 
00996   // Sequential fallback for input iterator case.
00997   template<typename InputIterator, typename Predicate, typename IteratorTag>
00998     inline typename iterator_traits<InputIterator>::difference_type
00999     count_if_switch(InputIterator begin, InputIterator end, Predicate pred, 
01000                     IteratorTag)
01001     { return count_if(begin, end, pred, __gnu_parallel::sequential_tag()); }
01002 
01003   // Public interface.
01004   template<typename InputIterator, typename Predicate>
01005     inline typename iterator_traits<InputIterator>::difference_type
01006     count_if(InputIterator begin, InputIterator end, Predicate pred, 
01007              __gnu_parallel::_Parallelism parallelism_tag)
01008     {
01009       typedef iterator_traits<InputIterator> traits_type;
01010       typedef typename traits_type::iterator_category iterator_category;
01011       return count_if_switch(begin, end, pred, iterator_category(), 
01012                              parallelism_tag);
01013     }
01014 
01015   template<typename InputIterator, typename Predicate>
01016     inline typename iterator_traits<InputIterator>::difference_type
01017     count_if(InputIterator begin, InputIterator end, Predicate pred)
01018     {
01019       typedef iterator_traits<InputIterator> traits_type;
01020       typedef typename traits_type::iterator_category iterator_category;
01021       return count_if_switch(begin, end, pred, iterator_category());
01022     }
01023 
01024 
01025   // Sequential fallback.
01026   template<typename ForwardIterator1, typename ForwardIterator2>
01027     inline ForwardIterator1
01028     search(ForwardIterator1 begin1, ForwardIterator1 end1,
01029            ForwardIterator2 begin2, ForwardIterator2 end2,
01030            __gnu_parallel::sequential_tag)
01031     { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2); }
01032 
01033   // Parallel algorithm for random access iterator
01034   template<typename RandomAccessIterator1, typename RandomAccessIterator2>
01035     RandomAccessIterator1
01036     search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
01037                   RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
01038                   random_access_iterator_tag, random_access_iterator_tag)
01039     {
01040       typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits;
01041       typedef typename iterator1_traits::value_type value1_type;
01042       typedef std::iterator_traits<RandomAccessIterator2> iterator2_traits;
01043       typedef typename iterator2_traits::value_type value2_type;
01044 
01045       if (_GLIBCXX_PARALLEL_CONDITION(true))
01046         return __gnu_parallel::
01047           search_template(begin1, end1, begin2, end2, __gnu_parallel::
01048                           equal_to<value1_type, value2_type>());
01049       else
01050         return search(begin1, end1, begin2, end2,
01051                       __gnu_parallel::sequential_tag());
01052     }
01053 
01054   // Sequential fallback for input iterator case
01055   template<typename ForwardIterator1, typename ForwardIterator2,
01056            typename IteratorTag1, typename IteratorTag2>
01057     inline ForwardIterator1
01058     search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
01059                   ForwardIterator2 begin2, ForwardIterator2 end2,
01060                   IteratorTag1, IteratorTag2)
01061     { return search(begin1, end1, begin2, end2,
01062                     __gnu_parallel::sequential_tag()); }
01063 
01064   // Public interface.
01065   template<typename ForwardIterator1, typename ForwardIterator2>
01066     inline ForwardIterator1
01067     search(ForwardIterator1 begin1, ForwardIterator1 end1,
01068            ForwardIterator2 begin2, ForwardIterator2 end2)
01069     {
01070       typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
01071       typedef typename iterator1_traits::iterator_category iterator1_category;
01072       typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
01073       typedef typename iterator2_traits::iterator_category iterator2_category;
01074 
01075       return search_switch(begin1, end1, begin2, end2,
01076                            iterator1_category(), iterator2_category());
01077     }
01078 
01079   // Public interface.
01080   template<typename ForwardIterator1, typename ForwardIterator2,
01081            typename BinaryPredicate>
01082     inline ForwardIterator1
01083     search(ForwardIterator1 begin1, ForwardIterator1 end1,
01084            ForwardIterator2 begin2, ForwardIterator2 end2,
01085            BinaryPredicate pred, __gnu_parallel::sequential_tag)
01086     { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred); }
01087 
01088   // Parallel algorithm for random access iterator.
01089   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
01090            typename BinaryPredicate>
01091     RandomAccessIterator1
01092     search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
01093                   RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
01094                   BinaryPredicate pred,
01095                   random_access_iterator_tag, random_access_iterator_tag)
01096     {
01097       if (_GLIBCXX_PARALLEL_CONDITION(true))
01098         return __gnu_parallel::search_template(begin1, end1,
01099                                                begin2, end2, pred);
01100       else
01101         return search(begin1, end1, begin2, end2, pred,
01102                       __gnu_parallel::sequential_tag());
01103     }
01104 
01105   // Sequential fallback for input iterator case
01106   template<typename ForwardIterator1, typename ForwardIterator2,
01107            typename BinaryPredicate, typename IteratorTag1,
01108            typename IteratorTag2>
01109     inline ForwardIterator1
01110     search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
01111                   ForwardIterator2 begin2, ForwardIterator2 end2,
01112                   BinaryPredicate pred, IteratorTag1, IteratorTag2)
01113     { return search(begin1, end1, begin2, end2, pred,
01114                     __gnu_parallel::sequential_tag()); }
01115 
01116   // Public interface
01117   template<typename ForwardIterator1, typename ForwardIterator2,
01118            typename BinaryPredicate>
01119     inline ForwardIterator1
01120     search(ForwardIterator1 begin1, ForwardIterator1 end1,
01121            ForwardIterator2 begin2, ForwardIterator2 end2,
01122            BinaryPredicate  pred)
01123     {
01124       typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
01125       typedef typename iterator1_traits::iterator_category iterator1_category;
01126       typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
01127       typedef typename iterator2_traits::iterator_category iterator2_category;
01128       return search_switch(begin1, end1, begin2, end2, pred,
01129                            iterator1_category(), iterator2_category());
01130     }
01131 
01132   // Sequential fallback
01133   template<typename ForwardIterator, typename Integer, typename T>
01134     inline ForwardIterator
01135     search_n(ForwardIterator begin, ForwardIterator end, Integer count,
01136              const T& val, __gnu_parallel::sequential_tag)
01137     { return _GLIBCXX_STD_P::search_n(begin, end, count, val); }
01138 
01139   // Sequential fallback
01140   template<typename ForwardIterator, typename Integer, typename T,
01141            typename BinaryPredicate>
01142     inline ForwardIterator
01143     search_n(ForwardIterator begin, ForwardIterator end, Integer count,
01144              const T& val, BinaryPredicate binary_pred,
01145              __gnu_parallel::sequential_tag)
01146     { return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred); }
01147 
01148   // Public interface.
01149   template<typename ForwardIterator, typename Integer, typename T>
01150     inline ForwardIterator
01151     search_n(ForwardIterator begin, ForwardIterator end, Integer count,
01152              const T& val)
01153     {
01154       typedef typename iterator_traits<ForwardIterator>::value_type value_type;
01155       return search_n(begin, end, count, val,
01156                       __gnu_parallel::equal_to<value_type, T>());
01157     }
01158 
01159   // Parallel algorithm for random access iterators.
01160   template<typename RandomAccessIterator, typename Integer,
01161            typename T, typename BinaryPredicate>
01162     RandomAccessIterator
01163     search_n_switch(RandomAccessIterator begin, RandomAccessIterator end,
01164                     Integer count, const T& val, BinaryPredicate binary_pred,
01165                     random_access_iterator_tag)
01166     {
01167       if (_GLIBCXX_PARALLEL_CONDITION(true))
01168         {
01169           __gnu_parallel::pseudo_sequence<T, Integer> ps(val, count);
01170           return __gnu_parallel::search_template(begin, end, ps.begin(),
01171                                                  ps.end(), binary_pred);
01172         }
01173       else
01174         return std::__search_n(begin, end, count, val,
01175                                binary_pred, random_access_iterator_tag());
01176     }
01177 
01178   // Sequential fallback for input iterator case.
01179   template<typename ForwardIterator, typename Integer, typename T,
01180            typename BinaryPredicate, typename IteratorTag>
01181     inline ForwardIterator
01182     search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count,
01183                     const T& val, BinaryPredicate binary_pred, IteratorTag)
01184     { return __search_n(begin, end, count, val, binary_pred, IteratorTag()); }
01185 
01186   // Public interface.
01187   template<typename ForwardIterator, typename Integer, typename T,
01188            typename BinaryPredicate>
01189     inline ForwardIterator
01190     search_n(ForwardIterator begin, ForwardIterator end, Integer count,
01191              const T& val, BinaryPredicate binary_pred)
01192     {
01193       return search_n_switch(begin, end, count, val, binary_pred,
01194                              typename std::iterator_traits<ForwardIterator>::
01195                              iterator_category());
01196     }
01197 
01198 
01199   // Sequential fallback.
01200   template<typename InputIterator, typename OutputIterator,
01201            typename UnaryOperation>
01202     inline OutputIterator
01203     transform(InputIterator begin, InputIterator end, OutputIterator result, 
01204               UnaryOperation unary_op, __gnu_parallel::sequential_tag)
01205     { return _GLIBCXX_STD_P::transform(begin, end, result, unary_op); }
01206 
01207   // Parallel unary transform for random access iterators.
01208   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
01209            typename UnaryOperation>
01210     RandomAccessIterator2
01211     transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
01212                       RandomAccessIterator2 result, UnaryOperation unary_op,
01213                       random_access_iterator_tag, random_access_iterator_tag,
01214                       __gnu_parallel::_Parallelism parallelism_tag
01215                       = __gnu_parallel::parallel_balanced)
01216     {
01217       if (_GLIBCXX_PARALLEL_CONDITION(
01218             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01219             >= __gnu_parallel::_Settings::get().transform_minimal_n
01220             && __gnu_parallel::is_parallel(parallelism_tag)))
01221         {
01222           bool dummy = true;
01223           typedef __gnu_parallel::iterator_pair<RandomAccessIterator1,
01224             RandomAccessIterator2, random_access_iterator_tag> ip;
01225           ip begin_pair(begin, result), end_pair(end, result + (end - begin));
01226           __gnu_parallel::transform1_selector<ip> functionality;
01227           __gnu_parallel::
01228             for_each_template_random_access(begin_pair, end_pair,
01229                                             unary_op, functionality,
01230                                             __gnu_parallel::dummy_reduct(),
01231                                             dummy, dummy, -1, parallelism_tag);
01232           return functionality.finish_iterator;
01233         }
01234       else
01235         return transform(begin, end, result, unary_op, 
01236                          __gnu_parallel::sequential_tag());
01237     }
01238 
01239   // Sequential fallback for input iterator case.
01240   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
01241            typename UnaryOperation, typename IteratorTag1,
01242            typename IteratorTag2>
01243     inline RandomAccessIterator2
01244     transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
01245                       RandomAccessIterator2 result, UnaryOperation unary_op,
01246                       IteratorTag1, IteratorTag2)
01247     { return transform(begin, end, result, unary_op, 
01248                        __gnu_parallel::sequential_tag()); }
01249 
01250   // Public interface.
01251   template<typename InputIterator, typename OutputIterator,
01252            typename UnaryOperation>
01253     inline OutputIterator
01254     transform(InputIterator begin, InputIterator end, OutputIterator result,
01255               UnaryOperation unary_op, 
01256               __gnu_parallel::_Parallelism parallelism_tag)
01257     {
01258       typedef std::iterator_traits<InputIterator> iteratori_traits;
01259       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
01260       typedef typename iteratori_traits::iterator_category iteratori_category;
01261       typedef typename iteratoro_traits::iterator_category iteratoro_category;
01262 
01263       return transform1_switch(begin, end, result, unary_op,
01264                                iteratori_category(), iteratoro_category(), 
01265                                parallelism_tag);
01266     }
01267 
01268   template<typename InputIterator, typename OutputIterator,
01269            typename UnaryOperation>
01270     inline OutputIterator
01271     transform(InputIterator begin, InputIterator end, OutputIterator result,
01272               UnaryOperation unary_op)
01273     {
01274       typedef std::iterator_traits<InputIterator> iteratori_traits;
01275       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
01276       typedef typename iteratori_traits::iterator_category iteratori_category;
01277       typedef typename iteratoro_traits::iterator_category iteratoro_category;
01278 
01279       return transform1_switch(begin, end, result, unary_op,
01280                                iteratori_category(), iteratoro_category());
01281     }
01282 
01283 
01284   // Sequential fallback
01285   template<typename InputIterator1, typename InputIterator2,
01286            typename OutputIterator, typename BinaryOperation>
01287     inline OutputIterator
01288     transform(InputIterator1 begin1, InputIterator1 end1,
01289               InputIterator2 begin2, OutputIterator result,
01290               BinaryOperation binary_op, __gnu_parallel::sequential_tag)
01291     { return _GLIBCXX_STD_P::transform(begin1, end1,
01292                                        begin2, result, binary_op); }
01293 
01294   // Parallel binary transform for random access iterators.
01295   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
01296            typename RandomAccessIterator3, typename BinaryOperation>
01297     RandomAccessIterator3
01298     transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
01299                       RandomAccessIterator2 begin2,
01300                       RandomAccessIterator3 result, BinaryOperation binary_op,
01301                       random_access_iterator_tag, random_access_iterator_tag,
01302                       random_access_iterator_tag,
01303                       __gnu_parallel::_Parallelism parallelism_tag 
01304                       = __gnu_parallel::parallel_balanced)
01305     {
01306       if (_GLIBCXX_PARALLEL_CONDITION(
01307             (end1 - begin1) >=
01308                 __gnu_parallel::_Settings::get().transform_minimal_n
01309             && __gnu_parallel::is_parallel(parallelism_tag)))
01310         {
01311           bool dummy = true;
01312           typedef __gnu_parallel::iterator_triple<RandomAccessIterator1,
01313             RandomAccessIterator2, RandomAccessIterator3,
01314             random_access_iterator_tag> ip;
01315           ip begin_triple(begin1, begin2, result),
01316             end_triple(end1, begin2 + (end1 - begin1),
01317                        result + (end1 - begin1));
01318           __gnu_parallel::transform2_selector<ip> functionality;
01319           __gnu_parallel::
01320             for_each_template_random_access(begin_triple, end_triple,
01321                                             binary_op, functionality,
01322                                             __gnu_parallel::dummy_reduct(),
01323                                             dummy, dummy, -1,
01324                                             parallelism_tag);
01325           return functionality.finish_iterator;
01326         }
01327       else
01328         return transform(begin1, end1, begin2, result, binary_op, 
01329                          __gnu_parallel::sequential_tag());
01330     }
01331 
01332   // Sequential fallback for input iterator case.
01333   template<typename InputIterator1, typename InputIterator2,
01334            typename OutputIterator, typename BinaryOperation,
01335            typename tag1, typename tag2, typename tag3>
01336     inline OutputIterator
01337     transform2_switch(InputIterator1 begin1, InputIterator1 end1, 
01338                       InputIterator2 begin2, OutputIterator result, 
01339                       BinaryOperation binary_op, tag1, tag2, tag3)
01340     { return transform(begin1, end1, begin2, result, binary_op,
01341                        __gnu_parallel::sequential_tag()); }
01342 
01343   // Public interface.
01344   template<typename InputIterator1, typename InputIterator2,
01345            typename OutputIterator, typename BinaryOperation>
01346     inline OutputIterator
01347     transform(InputIterator1 begin1, InputIterator1 end1,
01348               InputIterator2 begin2, OutputIterator result,
01349               BinaryOperation binary_op, 
01350               __gnu_parallel::_Parallelism parallelism_tag)
01351     {
01352       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
01353       typedef typename iteratori1_traits::iterator_category
01354         iteratori1_category;
01355       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
01356       typedef typename iteratori2_traits::iterator_category
01357         iteratori2_category;
01358       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
01359       typedef typename iteratoro_traits::iterator_category iteratoro_category;
01360 
01361       return transform2_switch(begin1, end1, begin2, result, binary_op,
01362                                iteratori1_category(), iteratori2_category(), 
01363                                iteratoro_category(), parallelism_tag);
01364     }
01365 
01366   template<typename InputIterator1, typename InputIterator2,
01367            typename OutputIterator, typename BinaryOperation>
01368     inline OutputIterator
01369     transform(InputIterator1 begin1, InputIterator1 end1,
01370               InputIterator2 begin2, OutputIterator result,
01371               BinaryOperation binary_op)
01372     {
01373       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
01374       typedef typename iteratori1_traits::iterator_category
01375         iteratori1_category;
01376       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
01377       typedef typename iteratori2_traits::iterator_category
01378         iteratori2_category;
01379       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
01380       typedef typename iteratoro_traits::iterator_category iteratoro_category;
01381 
01382       return transform2_switch(begin1, end1, begin2, result, binary_op,
01383                                iteratori1_category(), iteratori2_category(),
01384                                iteratoro_category());
01385     }
01386 
01387   // Sequential fallback
01388   template<typename ForwardIterator, typename T>
01389     inline void
01390     replace(ForwardIterator begin, ForwardIterator end, const T& old_value, 
01391             const T& new_value, __gnu_parallel::sequential_tag)
01392     { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); }
01393 
01394   // Sequential fallback for input iterator case
01395   template<typename ForwardIterator, typename T, typename IteratorTag>
01396     inline void
01397     replace_switch(ForwardIterator begin, ForwardIterator end, 
01398                    const T& old_value, const T& new_value, IteratorTag)
01399     { replace(begin, end, old_value, new_value, 
01400               __gnu_parallel::sequential_tag()); }
01401 
01402   // Parallel replace for random access iterators
01403   template<typename RandomAccessIterator, typename T>
01404     inline void
01405     replace_switch(RandomAccessIterator begin, RandomAccessIterator end, 
01406                    const T& old_value, const T& new_value, 
01407                    random_access_iterator_tag, 
01408                    __gnu_parallel::_Parallelism parallelism_tag
01409                    = __gnu_parallel::parallel_balanced)
01410     {
01411       // XXX parallel version is where?
01412       replace(begin, end, old_value, new_value, 
01413               __gnu_parallel::sequential_tag()); 
01414     }
01415 
01416   // Public interface
01417   template<typename ForwardIterator, typename T>
01418     inline void
01419     replace(ForwardIterator begin, ForwardIterator end, const T& old_value, 
01420             const T& new_value, __gnu_parallel::_Parallelism parallelism_tag)
01421     {
01422       typedef iterator_traits<ForwardIterator> traits_type;
01423       typedef typename traits_type::iterator_category iterator_category;
01424       replace_switch(begin, end, old_value, new_value, iterator_category(), 
01425                      parallelism_tag);
01426     }
01427 
01428   template<typename ForwardIterator, typename T>
01429     inline void
01430     replace(ForwardIterator begin, ForwardIterator end, const T& old_value, 
01431             const T& new_value)
01432     {
01433       typedef iterator_traits<ForwardIterator> traits_type;
01434       typedef typename traits_type::iterator_category iterator_category;
01435       replace_switch(begin, end, old_value, new_value, iterator_category());
01436     }
01437 
01438 
01439   // Sequential fallback
01440   template<typename ForwardIterator, typename Predicate, typename T>
01441     inline void
01442     replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred, 
01443                const T& new_value, __gnu_parallel::sequential_tag)
01444     { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); }
01445 
01446   // Sequential fallback for input iterator case
01447   template<typename ForwardIterator, typename Predicate, typename T,
01448            typename IteratorTag>
01449     inline void
01450     replace_if_switch(ForwardIterator begin, ForwardIterator end,
01451                       Predicate pred, const T& new_value, IteratorTag)
01452     { replace_if(begin, end, pred, new_value,
01453                  __gnu_parallel::sequential_tag()); }
01454 
01455   // Parallel algorithm for random access iterators.
01456   template<typename RandomAccessIterator, typename Predicate, typename T>
01457     void
01458     replace_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
01459                       Predicate pred, const T& new_value,
01460                       random_access_iterator_tag,
01461                       __gnu_parallel::_Parallelism parallelism_tag
01462                       = __gnu_parallel::parallel_balanced)
01463     {
01464       if (_GLIBCXX_PARALLEL_CONDITION(
01465             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01466             >= __gnu_parallel::_Settings::get().replace_minimal_n
01467             && __gnu_parallel::is_parallel(parallelism_tag)))
01468         {
01469           bool dummy;
01470           __gnu_parallel::
01471             replace_if_selector<RandomAccessIterator, Predicate, T>
01472             functionality(new_value);
01473           __gnu_parallel::
01474             for_each_template_random_access(begin, end, pred,
01475                                             functionality,
01476                                             __gnu_parallel::dummy_reduct(),
01477                                             true, dummy, -1, parallelism_tag);
01478         }
01479       else
01480         replace_if(begin, end, pred, new_value, 
01481                    __gnu_parallel::sequential_tag());
01482     }
01483 
01484   // Public interface.
01485   template<typename ForwardIterator, typename Predicate, typename T>
01486     inline void
01487     replace_if(ForwardIterator begin, ForwardIterator end,
01488                Predicate pred, const T& new_value, 
01489                __gnu_parallel::_Parallelism parallelism_tag)
01490     {
01491       typedef std::iterator_traits<ForwardIterator> iterator_traits;
01492       typedef typename iterator_traits::iterator_category iterator_category;
01493       replace_if_switch(begin, end, pred, new_value, iterator_category(), 
01494                         parallelism_tag);
01495     }
01496 
01497   template<typename ForwardIterator, typename Predicate, typename T>
01498     inline void
01499     replace_if(ForwardIterator begin, ForwardIterator end,
01500                Predicate pred, const T& new_value)
01501     {
01502       typedef std::iterator_traits<ForwardIterator> iterator_traits;
01503       typedef typename iterator_traits::iterator_category iterator_category;
01504       replace_if_switch(begin, end, pred, new_value, iterator_category());
01505     }
01506 
01507   // Sequential fallback
01508   template<typename ForwardIterator, typename Generator>
01509     inline void
01510     generate(ForwardIterator begin, ForwardIterator end, Generator gen, 
01511              __gnu_parallel::sequential_tag)
01512     { _GLIBCXX_STD_P::generate(begin, end, gen); }
01513 
01514   // Sequential fallback for input iterator case.
01515   template<typename ForwardIterator, typename Generator, typename IteratorTag>
01516     inline void
01517     generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen, 
01518                     IteratorTag)
01519     { generate(begin, end, gen, __gnu_parallel::sequential_tag()); }
01520 
01521   // Parallel algorithm for random access iterators.
01522   template<typename RandomAccessIterator, typename Generator>
01523     void
01524     generate_switch(RandomAccessIterator begin, RandomAccessIterator end,
01525                     Generator gen, random_access_iterator_tag, 
01526                     __gnu_parallel::_Parallelism parallelism_tag
01527                     = __gnu_parallel::parallel_balanced)
01528     {
01529       if (_GLIBCXX_PARALLEL_CONDITION(
01530             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01531             >= __gnu_parallel::_Settings::get().generate_minimal_n
01532             && __gnu_parallel::is_parallel(parallelism_tag)))
01533         {
01534           bool dummy;
01535           __gnu_parallel::generate_selector<RandomAccessIterator>
01536             functionality;
01537           __gnu_parallel::
01538             for_each_template_random_access(begin, end, gen, functionality,
01539                                             __gnu_parallel::dummy_reduct(),
01540                                             true, dummy, -1, parallelism_tag);
01541         }
01542       else
01543         generate(begin, end, gen, __gnu_parallel::sequential_tag());
01544     }
01545 
01546   // Public interface.
01547   template<typename ForwardIterator, typename Generator>
01548     inline void
01549     generate(ForwardIterator begin, ForwardIterator end,
01550              Generator gen, __gnu_parallel::_Parallelism parallelism_tag)
01551     {
01552       typedef std::iterator_traits<ForwardIterator> iterator_traits;
01553       typedef typename iterator_traits::iterator_category iterator_category;
01554       generate_switch(begin, end, gen, iterator_category(), parallelism_tag);
01555     }
01556 
01557   template<typename ForwardIterator, typename Generator>
01558     inline void
01559     generate(ForwardIterator begin, ForwardIterator end, Generator gen)
01560     {
01561       typedef std::iterator_traits<ForwardIterator> iterator_traits;
01562       typedef typename iterator_traits::iterator_category iterator_category;
01563       generate_switch(begin, end, gen, iterator_category());
01564     }
01565 
01566 
01567   // Sequential fallback.
01568   template<typename OutputIterator, typename Size, typename Generator>
01569     inline OutputIterator
01570     generate_n(OutputIterator begin, Size n, Generator gen, 
01571                __gnu_parallel::sequential_tag)
01572     { return _GLIBCXX_STD_P::generate_n(begin, n, gen); }
01573 
01574   // Sequential fallback for input iterator case.
01575   template<typename OutputIterator, typename Size, typename Generator,
01576            typename IteratorTag>
01577     inline OutputIterator
01578     generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag)
01579     { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
01580 
01581   // Parallel algorithm for random access iterators.
01582   template<typename RandomAccessIterator, typename Size, typename Generator>
01583     inline RandomAccessIterator
01584     generate_n_switch(RandomAccessIterator begin, Size n, Generator gen, 
01585                       random_access_iterator_tag, 
01586                       __gnu_parallel::_Parallelism parallelism_tag
01587                       = __gnu_parallel::parallel_balanced)
01588     {
01589       // XXX parallel version is where?
01590       return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); 
01591     }
01592 
01593   // Public interface.
01594   template<typename OutputIterator, typename Size, typename Generator>
01595     inline OutputIterator
01596     generate_n(OutputIterator begin, Size n, Generator gen, 
01597                __gnu_parallel::_Parallelism parallelism_tag)
01598     {
01599       typedef std::iterator_traits<OutputIterator> iterator_traits;
01600       typedef typename iterator_traits::iterator_category iterator_category;
01601       return generate_n_switch(begin, n, gen, iterator_category(), 
01602                                parallelism_tag); 
01603     }
01604 
01605   template<typename OutputIterator, typename Size, typename Generator>
01606     inline OutputIterator
01607     generate_n(OutputIterator begin, Size n, Generator gen)
01608     {
01609       typedef std::iterator_traits<OutputIterator> iterator_traits;
01610       typedef typename iterator_traits::iterator_category iterator_category;
01611       return generate_n_switch(begin, n, gen, iterator_category());
01612     }
01613 
01614 
01615   // Sequential fallback.
01616   template<typename RandomAccessIterator>
01617     inline void
01618     random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, 
01619                    __gnu_parallel::sequential_tag)
01620     { _GLIBCXX_STD_P::random_shuffle(begin, end); }
01621 
01622   // Sequential fallback.
01623   template<typename RandomAccessIterator, typename RandomNumberGenerator>
01624     inline void
01625     random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, 
01626                    RandomNumberGenerator& rand, __gnu_parallel::sequential_tag)
01627     { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); }
01628 
01629 
01630   /** @brief Functor wrapper for std::rand(). */
01631   template<typename must_be_int = int>
01632     struct c_rand_number
01633     {
01634       int
01635       operator()(int limit)
01636       { return rand() % limit; }
01637     };
01638 
01639   // Fill in random number generator.
01640   template<typename RandomAccessIterator>
01641     inline void
01642     random_shuffle(RandomAccessIterator begin, RandomAccessIterator end)
01643     {
01644       c_rand_number<> r;
01645       // Parallelization still possible.
01646       __gnu_parallel::random_shuffle(begin, end, r);
01647     }
01648 
01649   // Parallel algorithm for random access iterators.
01650   template<typename RandomAccessIterator, typename RandomNumberGenerator>
01651     void
01652     random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, 
01653                    RandomNumberGenerator& rand)
01654     {
01655       if (begin == end)
01656         return;
01657       if (_GLIBCXX_PARALLEL_CONDITION(
01658             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01659             >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
01660         __gnu_parallel::parallel_random_shuffle(begin, end, rand);
01661       else
01662         __gnu_parallel::sequential_random_shuffle(begin, end, rand);
01663     }
01664 
01665   // Sequential fallback.
01666   template<typename ForwardIterator, typename Predicate>
01667     inline ForwardIterator
01668     partition(ForwardIterator begin, ForwardIterator end,
01669               Predicate pred, __gnu_parallel::sequential_tag)
01670     { return _GLIBCXX_STD_P::partition(begin, end, pred); }
01671 
01672   // Sequential fallback for input iterator case.
01673   template<typename ForwardIterator, typename Predicate, typename IteratorTag>
01674     inline ForwardIterator
01675     partition_switch(ForwardIterator begin, ForwardIterator end,
01676                      Predicate pred, IteratorTag)
01677     { return partition(begin, end, pred, __gnu_parallel::sequential_tag()); }
01678 
01679   // Parallel algorithm for random access iterators.
01680   template<typename RandomAccessIterator, typename Predicate>
01681     RandomAccessIterator
01682     partition_switch(RandomAccessIterator begin, RandomAccessIterator end,
01683                      Predicate pred, random_access_iterator_tag)
01684     {
01685       if (_GLIBCXX_PARALLEL_CONDITION(
01686             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
01687             >= __gnu_parallel::_Settings::get().partition_minimal_n))
01688         {
01689           typedef typename std::iterator_traits<RandomAccessIterator>::
01690             difference_type difference_type;
01691           difference_type middle = __gnu_parallel::
01692             parallel_partition(begin, end, pred,
01693                                __gnu_parallel::get_max_threads());
01694           return begin + middle;
01695         }
01696       else
01697         return partition(begin, end, pred, __gnu_parallel::sequential_tag());
01698     }
01699 
01700   // Public interface.
01701   template<typename ForwardIterator, typename Predicate>
01702     inline ForwardIterator
01703     partition(ForwardIterator begin, ForwardIterator end, Predicate pred)
01704     {
01705       typedef iterator_traits<ForwardIterator> traits_type;
01706       typedef typename traits_type::iterator_category iterator_category;
01707       return partition_switch(begin, end, pred, iterator_category());
01708     }
01709 
01710   // sort interface
01711 
01712   // Sequential fallback
01713   template<typename RandomAccessIterator>
01714     inline void
01715     sort(RandomAccessIterator begin, RandomAccessIterator end, 
01716          __gnu_parallel::sequential_tag)
01717     { _GLIBCXX_STD_P::sort(begin, end); }
01718 
01719   // Sequential fallback
01720   template<typename RandomAccessIterator, typename Comparator>
01721     inline void
01722     sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
01723          __gnu_parallel::sequential_tag)
01724     { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end,
01725                                                              comp); }
01726 
01727   // Public interface
01728   template<typename RandomAccessIterator, typename Comparator,
01729            typename Parallelism>
01730   void
01731   sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
01732        Parallelism parallelism)
01733   {
01734     typedef iterator_traits<RandomAccessIterator> traits_type;
01735     typedef typename traits_type::value_type value_type;
01736 
01737     if (begin != end)
01738       {
01739         if (_GLIBCXX_PARALLEL_CONDITION(
01740             static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
01741               __gnu_parallel::_Settings::get().sort_minimal_n))
01742           __gnu_parallel::parallel_sort<false>(begin, end, comp, parallelism);
01743         else
01744           sort(begin, end, comp, __gnu_parallel::sequential_tag());
01745       }
01746   }
01747 
01748   // Public interface, insert default comparator
01749   template<typename RandomAccessIterator>
01750     inline void
01751     sort(RandomAccessIterator begin, RandomAccessIterator end)
01752     {
01753       typedef iterator_traits<RandomAccessIterator> traits_type;
01754       typedef typename traits_type::value_type value_type;
01755       sort(begin, end, std::less<value_type>(),
01756            __gnu_parallel::default_parallel_tag());
01757     }
01758 
01759   // Public interface, insert default comparator
01760   template<typename RandomAccessIterator>
01761   inline void
01762   sort(RandomAccessIterator begin, RandomAccessIterator end,
01763        __gnu_parallel::default_parallel_tag parallelism)
01764   {
01765     typedef iterator_traits<RandomAccessIterator> traits_type;
01766     typedef typename traits_type::value_type value_type;
01767     sort(begin, end, std::less<value_type>(), parallelism);
01768   }
01769 
01770   // Public interface, insert default comparator
01771   template<typename RandomAccessIterator>
01772   inline void
01773   sort(RandomAccessIterator begin, RandomAccessIterator end,
01774        __gnu_parallel::parallel_tag parallelism)
01775   {
01776     typedef iterator_traits<RandomAccessIterator> traits_type;
01777     typedef typename traits_type::value_type value_type;
01778     sort(begin, end, std::less<value_type>(), parallelism);
01779   }
01780 
01781   // Public interface, insert default comparator
01782   template<typename RandomAccessIterator>
01783   inline void
01784   sort(RandomAccessIterator begin, RandomAccessIterator end,
01785        __gnu_parallel::multiway_mergesort_tag parallelism)
01786   {
01787     typedef iterator_traits<RandomAccessIterator> traits_type;
01788     typedef typename traits_type::value_type value_type;
01789     sort(begin, end, std::less<value_type>(), parallelism);
01790   }
01791 
01792   // Public interface, insert default comparator
01793   template<typename RandomAccessIterator>
01794   inline void
01795   sort(RandomAccessIterator begin, RandomAccessIterator end,
01796        __gnu_parallel::multiway_mergesort_sampling_tag parallelism)
01797   {
01798     typedef iterator_traits<RandomAccessIterator> traits_type;
01799     typedef typename traits_type::value_type value_type;
01800     sort(begin, end, std::less<value_type>(), parallelism);
01801   }
01802 
01803   // Public interface, insert default comparator
01804   template<typename RandomAccessIterator>
01805   inline void
01806   sort(RandomAccessIterator begin, RandomAccessIterator end,
01807        __gnu_parallel::multiway_mergesort_exact_tag parallelism)
01808   {
01809     typedef iterator_traits<RandomAccessIterator> traits_type;
01810     typedef typename traits_type::value_type value_type;
01811     sort(begin, end, std::less<value_type>(), parallelism);
01812   }
01813 
01814   // Public interface, insert default comparator
01815   template<typename RandomAccessIterator>
01816   inline void
01817   sort(RandomAccessIterator begin, RandomAccessIterator end,
01818        __gnu_parallel::quicksort_tag parallelism)
01819   {
01820     typedef iterator_traits<RandomAccessIterator> traits_type;
01821     typedef typename traits_type::value_type value_type;
01822     sort(begin, end, std::less<value_type>(), parallelism);
01823   }
01824 
01825   // Public interface, insert default comparator
01826   template<typename RandomAccessIterator>
01827   inline void
01828   sort(RandomAccessIterator begin, RandomAccessIterator end,
01829        __gnu_parallel::balanced_quicksort_tag parallelism)
01830   {
01831     typedef iterator_traits<RandomAccessIterator> traits_type;
01832     typedef typename traits_type::value_type value_type;
01833     sort(begin, end, std::less<value_type>(), parallelism);
01834   }
01835 
01836   // Public interface
01837   template<typename RandomAccessIterator, typename Comparator>
01838     void
01839     sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
01840     {
01841       typedef iterator_traits<RandomAccessIterator> traits_type;
01842       typedef typename traits_type::value_type value_type;
01843     sort(begin, end, comp, __gnu_parallel::default_parallel_tag());
01844   }
01845 
01846 
01847   // stable_sort interface
01848 
01849 
01850   // Sequential fallback
01851   template<typename RandomAccessIterator>
01852   inline void
01853   stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01854        __gnu_parallel::sequential_tag)
01855   { _GLIBCXX_STD_P::stable_sort(begin, end); }
01856 
01857   // Sequential fallback
01858   template<typename RandomAccessIterator, typename Comparator>
01859   inline void
01860   stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01861               Comparator comp, __gnu_parallel::sequential_tag)
01862   { _GLIBCXX_STD_P::stable_sort<RandomAccessIterator, Comparator>(
01863       begin, end, comp); }
01864 
01865   // Public interface
01866   template<typename RandomAccessIterator, typename Comparator,
01867            typename Parallelism>
01868   void
01869   stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01870               Comparator comp, Parallelism parallelism)
01871   {
01872     typedef iterator_traits<RandomAccessIterator> traits_type;
01873     typedef typename traits_type::value_type value_type;
01874 
01875     if (begin != end)
01876       {
01877         if (_GLIBCXX_PARALLEL_CONDITION(
01878               static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
01879               __gnu_parallel::_Settings::get().sort_minimal_n))
01880           __gnu_parallel::parallel_sort<true>(begin, end, comp, parallelism);
01881         else
01882           stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
01883       }
01884   }
01885 
01886   // Public interface, insert default comparator
01887   template<typename RandomAccessIterator>
01888   inline void
01889   stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
01890   {
01891     typedef iterator_traits<RandomAccessIterator> traits_type;
01892     typedef typename traits_type::value_type value_type;
01893     stable_sort(begin, end, std::less<value_type>(),
01894                 __gnu_parallel::default_parallel_tag());
01895   }
01896 
01897   // Public interface, insert default comparator
01898   template<typename RandomAccessIterator>
01899   inline void
01900   stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01901               __gnu_parallel::default_parallel_tag parallelism)
01902   {
01903     typedef iterator_traits<RandomAccessIterator> traits_type;
01904     typedef typename traits_type::value_type value_type;
01905     stable_sort(begin, end, std::less<value_type>(), parallelism);
01906   }
01907 
01908   // Public interface, insert default comparator
01909   template<typename RandomAccessIterator>
01910   inline void
01911   stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01912               __gnu_parallel::parallel_tag parallelism)
01913   {
01914     typedef iterator_traits<RandomAccessIterator> traits_type;
01915     typedef typename traits_type::value_type value_type;
01916     stable_sort(begin, end, std::less<value_type>(), parallelism);
01917   }
01918 
01919   // Public interface, insert default comparator
01920   template<typename RandomAccessIterator>
01921   inline void
01922   stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01923               __gnu_parallel::multiway_mergesort_tag parallelism)
01924   {
01925     typedef iterator_traits<RandomAccessIterator> traits_type;
01926     typedef typename traits_type::value_type value_type;
01927     stable_sort(begin, end, std::less<value_type>(), parallelism);
01928   }
01929 
01930   // Public interface, insert default comparator
01931   template<typename RandomAccessIterator>
01932   inline void
01933   stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01934               __gnu_parallel::quicksort_tag parallelism)
01935   {
01936     typedef iterator_traits<RandomAccessIterator> traits_type;
01937     typedef typename traits_type::value_type value_type;
01938     stable_sort(begin, end, std::less<value_type>(), parallelism);
01939   }
01940 
01941   // Public interface, insert default comparator
01942   template<typename RandomAccessIterator>
01943   inline void
01944   stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01945               __gnu_parallel::balanced_quicksort_tag parallelism)
01946   {
01947     typedef iterator_traits<RandomAccessIterator> traits_type;
01948     typedef typename traits_type::value_type value_type;
01949     stable_sort(begin, end, std::less<value_type>(), parallelism);
01950   }
01951 
01952   // Public interface
01953   template<typename RandomAccessIterator, typename Comparator>
01954   void
01955   stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
01956               Comparator comp)
01957   {
01958     typedef iterator_traits<RandomAccessIterator> traits_type;
01959     typedef typename traits_type::value_type value_type;
01960     stable_sort(begin, end, comp, __gnu_parallel::default_parallel_tag());
01961   }
01962 
01963 
01964 //   // Sequential fallback
01965 //   template<typename RandomAccessIterator>
01966 //   inline void
01967 //   stable_sort(RandomAccessIterator begin, RandomAccessIterator end, 
01968 //            __gnu_parallel::sequential_tag)
01969 //   { return _GLIBCXX_STD_P::stable_sort(begin, end); }
01970 // 
01971 //   // Sequential fallback
01972 //   template<typename RandomAccessIterator, typename Comparator>
01973 //   inline void
01974 //   stable_sort(RandomAccessIterator begin, RandomAccessIterator end, 
01975 //            Comparator comp, __gnu_parallel::sequential_tag)
01976 //   { return _GLIBCXX_STD_P::stable_sort(begin, end, comp); }
01977 // 
01978 //   template<typename RandomAccessIterator>
01979 //   void
01980 //   stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
01981 //   {
01982 //     typedef iterator_traits<RandomAccessIterator> traits_type;
01983 //     typedef typename traits_type::value_type value_type;
01984 //     stable_sort(begin, end, std::less<value_type>());
01985 //   }
01986 // 
01987 //   // Parallel algorithm for random access iterators
01988 //   template<typename RandomAccessIterator, typename Comparator>
01989 //   void
01990 //   stable_sort(RandomAccessIterator begin, RandomAccessIterator end, 
01991 //            Comparator comp)
01992 //   {
01993 //     if (begin != end)
01994 //       {
01995 //      if (_GLIBCXX_PARALLEL_CONDITION(
01996 //            static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
01997 //                __gnu_parallel::_Settings::get().sort_minimal_n))
01998 //        __gnu_parallel::parallel_sort(begin, end, comp,
01999 //                                      __gnu_parallel::parallel_tag());
02000 //      else
02001 //        stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
02002 //       }
02003 //   }
02004 
02005   // Sequential fallback
02006   template<typename InputIterator1, typename InputIterator2,
02007            typename OutputIterator>
02008     inline OutputIterator
02009     merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 
02010           InputIterator2 end2, OutputIterator result,
02011           __gnu_parallel::sequential_tag)
02012     { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result); }
02013 
02014   // Sequential fallback
02015   template<typename InputIterator1, typename InputIterator2,
02016            typename OutputIterator, typename Comparator>
02017     inline OutputIterator
02018     merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
02019           InputIterator2 end2, OutputIterator result, Comparator comp,
02020           __gnu_parallel::sequential_tag)
02021     { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp); }
02022 
02023   // Sequential fallback for input iterator case
02024   template<typename InputIterator1, typename InputIterator2,
02025            typename OutputIterator, typename Comparator,
02026            typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
02027     inline OutputIterator
02028     merge_switch(InputIterator1 begin1, InputIterator1 end1,
02029                  InputIterator2 begin2, InputIterator2 end2,
02030                  OutputIterator result, Comparator comp,
02031                  IteratorTag1, IteratorTag2, IteratorTag3)
02032      { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2,
02033                                     result, comp); }
02034 
02035   // Parallel algorithm for random access iterators
02036   template<typename InputIterator1, typename InputIterator2,
02037            typename OutputIterator, typename Comparator>
02038     OutputIterator
02039     merge_switch(InputIterator1 begin1, InputIterator1 end1, 
02040                  InputIterator2 begin2, InputIterator2 end2, 
02041                  OutputIterator result, Comparator comp, 
02042                  random_access_iterator_tag, random_access_iterator_tag, 
02043                  random_access_iterator_tag)
02044     {
02045       if (_GLIBCXX_PARALLEL_CONDITION(
02046             (static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
02047              >= __gnu_parallel::_Settings::get().merge_minimal_n
02048              || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
02049              >= __gnu_parallel::_Settings::get().merge_minimal_n)))
02050         return __gnu_parallel::parallel_merge_advance(begin1, end1,
02051                                                       begin2, end2,
02052                                                       result, (end1 - begin1)
02053                                                       + (end2 - begin2), comp);
02054       else
02055         return __gnu_parallel::merge_advance(begin1, end1, begin2, end2,
02056                                              result, (end1 - begin1)
02057                                              + (end2 - begin2), comp);
02058   }
02059 
02060   // Public interface
02061   template<typename InputIterator1, typename InputIterator2,
02062            typename OutputIterator, typename Comparator>
02063     inline OutputIterator
02064     merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 
02065           InputIterator2 end2, OutputIterator result, Comparator comp)
02066     {
02067       typedef typename iterator_traits<InputIterator1>::value_type value_type;
02068 
02069       typedef std::iterator_traits<InputIterator1> iteratori1_traits;
02070       typedef std::iterator_traits<InputIterator2> iteratori2_traits;
02071       typedef std::iterator_traits<OutputIterator> iteratoro_traits;
02072       typedef typename iteratori1_traits::iterator_category
02073         iteratori1_category;
02074       typedef typename iteratori2_traits::iterator_category
02075         iteratori2_category;
02076       typedef typename iteratoro_traits::iterator_category iteratoro_category;
02077 
02078       return merge_switch(begin1, end1, begin2, end2, result, comp, 
02079                           iteratori1_category(), iteratori2_category(), 
02080                           iteratoro_category());
02081   }
02082 
02083 
02084   // Public interface, insert default comparator
02085   template<typename InputIterator1, typename InputIterator2,
02086            typename OutputIterator>
02087     inline OutputIterator
02088     merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, 
02089           InputIterator2 end2, OutputIterator result)
02090     {
02091       typedef std::iterator_traits<InputIterator1> iterator1_traits;
02092       typedef std::iterator_traits<InputIterator2> iterator2_traits;
02093       typedef typename iterator1_traits::value_type value1_type;
02094       typedef typename iterator2_traits::value_type value2_type;
02095 
02096       return merge(begin1, end1, begin2, end2, result, 
02097                    __gnu_parallel::less<value1_type, value2_type>());
02098     }
02099 
02100   // Sequential fallback
02101   template<typename RandomAccessIterator>
02102     inline void
02103     nth_element(RandomAccessIterator begin, RandomAccessIterator nth, 
02104                 RandomAccessIterator end, __gnu_parallel::sequential_tag)
02105     { return _GLIBCXX_STD_P::nth_element(begin, nth, end); }
02106 
02107   // Sequential fallback
02108   template<typename RandomAccessIterator, typename Comparator>
02109     inline void
02110     nth_element(RandomAccessIterator begin, RandomAccessIterator nth, 
02111                 RandomAccessIterator end, Comparator comp, 
02112               __gnu_parallel::sequential_tag)
02113     { return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); }
02114 
02115   // Public interface
02116   template<typename RandomAccessIterator, typename Comparator>
02117     inline void
02118     nth_element(RandomAccessIterator begin, RandomAccessIterator nth, 
02119                 RandomAccessIterator end, Comparator comp)
02120     {
02121       if (_GLIBCXX_PARALLEL_CONDITION(
02122             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
02123             >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
02124         __gnu_parallel::parallel_nth_element(begin, nth, end, comp);
02125       else
02126         nth_element(begin, nth, end, comp, __gnu_parallel::sequential_tag());
02127     }
02128 
02129   // Public interface, insert default comparator
02130   template<typename RandomAccessIterator>
02131     inline void
02132     nth_element(RandomAccessIterator begin, RandomAccessIterator nth, 
02133                 RandomAccessIterator end)
02134     {
02135       typedef iterator_traits<RandomAccessIterator> traits_type;
02136       typedef typename traits_type::value_type value_type;
02137       nth_element(begin, nth, end, std::less<value_type>());
02138     }
02139 
02140   // Sequential fallback
02141   template<typename RandomAccessIterator, typename _Compare>
02142     inline void
02143     partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, 
02144                  RandomAccessIterator end, _Compare comp,
02145                  __gnu_parallel::sequential_tag)
02146     { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); }
02147 
02148   // Sequential fallback
02149   template<typename RandomAccessIterator>
02150     inline void
02151     partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, 
02152                  RandomAccessIterator end, __gnu_parallel::sequential_tag)
02153     { _GLIBCXX_STD_P::partial_sort(begin, middle, end); }
02154 
02155   // Public interface, parallel algorithm for random access iterators
02156   template<typename RandomAccessIterator, typename _Compare>
02157     void
02158     partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, 
02159                  RandomAccessIterator end, _Compare comp)
02160     {
02161       if (_GLIBCXX_PARALLEL_CONDITION(
02162             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
02163             >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
02164         __gnu_parallel::parallel_partial_sort(begin, middle, end, comp);
02165       else
02166         partial_sort(begin, middle, end, comp,
02167                      __gnu_parallel::sequential_tag());
02168     }
02169 
02170   // Public interface, insert default comparator
02171   template<typename RandomAccessIterator>
02172     inline void
02173     partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, 
02174                  RandomAccessIterator end)
02175     {
02176       typedef iterator_traits<RandomAccessIterator> traits_type;
02177       typedef typename traits_type::value_type value_type;
02178       partial_sort(begin, middle, end, std::less<value_type>());
02179     }
02180 
02181   // Sequential fallback
02182   template<typename ForwardIterator>
02183     inline ForwardIterator
02184     max_element(ForwardIterator begin, ForwardIterator end, 
02185                 __gnu_parallel::sequential_tag)
02186     { return _GLIBCXX_STD_P::max_element(begin, end); }
02187 
02188   // Sequential fallback
02189   template<typename ForwardIterator, typename Comparator>
02190     inline ForwardIterator
02191     max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, 
02192                 __gnu_parallel::sequential_tag)
02193     { return _GLIBCXX_STD_P::max_element(begin, end, comp); }
02194 
02195   // Sequential fallback for input iterator case
02196   template<typename ForwardIterator, typename Comparator, typename IteratorTag>
02197     inline ForwardIterator
02198     max_element_switch(ForwardIterator begin, ForwardIterator end, 
02199                        Comparator comp, IteratorTag)
02200     { return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
02201 
02202   // Parallel algorithm for random access iterators
02203   template<typename RandomAccessIterator, typename Comparator>
02204     RandomAccessIterator
02205     max_element_switch(RandomAccessIterator begin, RandomAccessIterator end, 
02206                        Comparator comp, random_access_iterator_tag, 
02207                        __gnu_parallel::_Parallelism parallelism_tag
02208                        = __gnu_parallel::parallel_balanced)
02209     {
02210       if (_GLIBCXX_PARALLEL_CONDITION(
02211             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
02212             >= __gnu_parallel::_Settings::get().max_element_minimal_n
02213             && __gnu_parallel::is_parallel(parallelism_tag)))
02214         {
02215           RandomAccessIterator res(begin);
02216           __gnu_parallel::identity_selector<RandomAccessIterator>
02217             functionality;
02218           __gnu_parallel::
02219             for_each_template_random_access(begin, end,
02220                                             __gnu_parallel::nothing(),
02221                                             functionality,
02222                                             __gnu_parallel::
02223                                             max_element_reduct<Comparator,
02224                                             RandomAccessIterator>(comp),
02225                                             res, res, -1, parallelism_tag);
02226           return res;
02227         }
02228       else
02229         return max_element(begin, end, comp, __gnu_parallel::sequential_tag());
02230     }
02231 
02232   // Public interface, insert default comparator
02233   template<typename ForwardIterator>
02234     inline ForwardIterator
02235     max_element(ForwardIterator begin, ForwardIterator end, 
02236                 __gnu_parallel::_Parallelism parallelism_tag)
02237     {
02238       typedef typename iterator_traits<ForwardIterator>::value_type value_type;
02239       return max_element(begin, end, std::less<value_type>(), parallelism_tag);
02240     }
02241 
02242   template<typename ForwardIterator>
02243     inline ForwardIterator
02244     max_element(ForwardIterator begin, ForwardIterator end)
02245     {
02246       typedef typename iterator_traits<ForwardIterator>::value_type value_type;
02247       return max_element(begin, end, std::less<value_type>());
02248     }
02249 
02250   // Public interface
02251   template<typename ForwardIterator, typename Comparator>
02252     inline ForwardIterator
02253     max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
02254                 __gnu_parallel::_Parallelism parallelism_tag)
02255     {
02256       typedef iterator_traits<ForwardIterator> traits_type;
02257       typedef typename traits_type::iterator_category iterator_category;
02258       return max_element_switch(begin, end, comp, iterator_category(), 
02259                                 parallelism_tag);
02260     }
02261 
02262   template<typename ForwardIterator, typename Comparator>
02263     inline ForwardIterator
02264     max_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
02265     {
02266       typedef iterator_traits<ForwardIterator> traits_type;
02267       typedef typename traits_type::iterator_category iterator_category;
02268       return max_element_switch(begin, end, comp, iterator_category());
02269     }
02270 
02271 
02272   // Sequential fallback
02273   template<typename ForwardIterator>
02274     inline ForwardIterator
02275     min_element(ForwardIterator begin, ForwardIterator end, 
02276                 __gnu_parallel::sequential_tag)
02277     { return _GLIBCXX_STD_P::min_element(begin, end); }
02278 
02279   // Sequential fallback
02280   template<typename ForwardIterator, typename Comparator>
02281     inline ForwardIterator
02282     min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, 
02283                 __gnu_parallel::sequential_tag)
02284     { return _GLIBCXX_STD_P::min_element(begin, end, comp); }
02285 
02286   // Sequential fallback for input iterator case
02287   template<typename ForwardIterator, typename Comparator, typename IteratorTag>
02288     inline ForwardIterator
02289     min_element_switch(ForwardIterator begin, ForwardIterator end, 
02290                        Comparator comp, IteratorTag)
02291     { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
02292 
02293   // Parallel algorithm for random access iterators
02294   template<typename RandomAccessIterator, typename Comparator>
02295     RandomAccessIterator
02296     min_element_switch(RandomAccessIterator begin, RandomAccessIterator end, 
02297                        Comparator comp, random_access_iterator_tag, 
02298                        __gnu_parallel::_Parallelism parallelism_tag
02299                        = __gnu_parallel::parallel_balanced)
02300     {
02301       if (_GLIBCXX_PARALLEL_CONDITION(
02302             static_cast<__gnu_parallel::sequence_index_t>(end - begin)
02303             >= __gnu_parallel::_Settings::get().min_element_minimal_n
02304             && __gnu_parallel::is_parallel(parallelism_tag)))
02305         {
02306           RandomAccessIterator res(begin);
02307           __gnu_parallel::identity_selector<RandomAccessIterator>
02308             functionality;
02309           __gnu_parallel::
02310             for_each_template_random_access(begin, end,
02311                                             __gnu_parallel::nothing(),
02312                                             functionality,
02313                                             __gnu_parallel::
02314                                             min_element_reduct<Comparator,
02315                                             RandomAccessIterator>(comp),
02316                                             res, res, -1, parallelism_tag);
02317           return res;
02318         }
02319       else
02320         return min_element(begin, end, comp, __gnu_parallel::sequential_tag());
02321     }
02322 
02323   // Public interface, insert default comparator
02324   template<typename ForwardIterator>
02325     inline ForwardIterator
02326     min_element(ForwardIterator begin, ForwardIterator end, 
02327                 __gnu_parallel::_Parallelism parallelism_tag)
02328     {
02329       typedef typename iterator_traits<ForwardIterator>::value_type value_type;
02330       return min_element(begin, end, std::less<value_type>(), parallelism_tag);
02331     }
02332 
02333   template<typename ForwardIterator>
02334     inline ForwardIterator
02335     min_element(ForwardIterator begin, ForwardIterator end)
02336     {
02337       typedef typename iterator_traits<ForwardIterator>::value_type value_type;
02338       return min_element(begin, end, std::less<value_type>());
02339     }
02340 
02341   // Public interface
02342   template<typename ForwardIterator, typename Comparator>
02343     inline ForwardIterator
02344     min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
02345                 __gnu_parallel::_Parallelism parallelism_tag)
02346     {
02347       typedef iterator_traits<ForwardIterator> traits_type;
02348       typedef typename traits_type::iterator_category iterator_category;
02349       return min_element_switch(begin, end, comp, iterator_category(), 
02350                                 parallelism_tag);
02351     }
02352 
02353   template<typename ForwardIterator, typename Comparator>
02354     inline ForwardIterator
02355     min_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
02356     {
02357       typedef iterator_traits<ForwardIterator> traits_type;
02358       typedef typename traits_type::iterator_category iterator_category;
02359       return min_element_switch(begin, end, comp, iterator_category());
02360     }
02361 } // end namespace
02362 } // end namespace
02363 
02364 #endif /* _GLIBCXX_PARALLEL_ALGO_H */
Generated on Tue Apr 21 13:13:24 2009 for libstdc++ by  doxygen 1.5.8