algo.h

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

Generated on Sat Dec 12 09:40:08 2009 for libstdc++ by  doxygen 1.5.6