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