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