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