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