Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2007-2015 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the terms
  7. // of the GNU General Public License as published by the Free Software
  8. // Foundation; either version 3, or (at your option) any later
  9. // version.
  10.  
  11. // This library is distributed in the hope that it will be useful, but
  12. // WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14. // General Public License for more details.
  15.  
  16. // Under Section 7 of GPL version 3, you are granted additional
  17. // permissions described in the GCC Runtime Library Exception, version
  18. // 3.1, as published by the Free Software Foundation.
  19.  
  20. // You should have received a copy of the GNU General Public License and
  21. // a copy of the GCC Runtime Library Exception along with this program;
  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23. // <http://www.gnu.org/licenses/>.
  24.  
  25. /** @file parallel/algo.h
  26.  *  @brief Parallel STL function calls corresponding to the stl_algo.h header.
  27.  *
  28.  *  The functions defined here mainly do case switches and
  29.  *  call the actual parallelized versions in other files.
  30.  *  Inlining policy: Functions that basically only contain one function call,
  31.  *  are declared inline.
  32.  *  This file is a GNU parallel extension to the Standard C++ Library.
  33.  */
  34.  
  35. // Written by Johannes Singler and Felix Putze.
  36.  
  37. #ifndef _GLIBCXX_PARALLEL_ALGO_H
  38. #define _GLIBCXX_PARALLEL_ALGO_H 1
  39.  
  40. #include <parallel/algorithmfwd.h>
  41. #include <bits/stl_algobase.h>
  42. #include <bits/stl_algo.h>
  43. #include <parallel/iterator.h>
  44. #include <parallel/base.h>
  45. #include <parallel/sort.h>
  46. #include <parallel/workstealing.h>
  47. #include <parallel/par_loop.h>
  48. #include <parallel/omp_loop.h>
  49. #include <parallel/omp_loop_static.h>
  50. #include <parallel/for_each_selectors.h>
  51. #include <parallel/for_each.h>
  52. #include <parallel/find.h>
  53. #include <parallel/find_selectors.h>
  54. #include <parallel/search.h>
  55. #include <parallel/random_shuffle.h>
  56. #include <parallel/partition.h>
  57. #include <parallel/merge.h>
  58. #include <parallel/unique_copy.h>
  59. #include <parallel/set_operations.h>
  60.  
  61. namespace std _GLIBCXX_VISIBILITY(default)
  62. {
  63. namespace __parallel
  64. {
  65.   // Sequential fallback
  66.   template<typename _IIter, typename _Function>
  67.     inline _Function
  68.     for_each(_IIter __begin, _IIter __end, _Function __f,
  69.              __gnu_parallel::sequential_tag)
  70.     { return _GLIBCXX_STD_A::for_each(__begin, __end, __f); }
  71.  
  72.  
  73.   // Sequential fallback for input iterator case
  74.   template<typename _IIter, typename _Function, typename _IteratorTag>
  75.     inline _Function
  76.     __for_each_switch(_IIter __begin, _IIter __end, _Function __f,
  77.                     _IteratorTag)
  78.     { return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag()); }
  79.  
  80.   // Parallel algorithm for random access iterators
  81.   template<typename _RAIter, typename _Function>
  82.     _Function
  83.     __for_each_switch(_RAIter __begin, _RAIter __end,
  84.                     _Function __f, random_access_iterator_tag,
  85.                     __gnu_parallel::_Parallelism __parallelism_tag)
  86.     {
  87.       if (_GLIBCXX_PARALLEL_CONDITION(
  88.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  89.             >= __gnu_parallel::_Settings::get().for_each_minimal_n
  90.             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  91.         {
  92.           bool __dummy;
  93.     __gnu_parallel::__for_each_selector<_RAIter> __functionality;
  94.  
  95.           return __gnu_parallel::
  96.             __for_each_template_random_access(
  97.               __begin, __end, __f, __functionality,
  98.               __gnu_parallel::_DummyReduct(), true, __dummy, -1,
  99.               __parallelism_tag);
  100.         }
  101.       else
  102.         return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag());
  103.     }
  104.  
  105.   // Public interface
  106.   template<typename _Iterator, typename _Function>
  107.     inline _Function
  108.     for_each(_Iterator __begin, _Iterator __end, _Function __f,
  109.              __gnu_parallel::_Parallelism __parallelism_tag)
  110.     {
  111.       typedef std::iterator_traits<_Iterator> _IteratorTraits;
  112.       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
  113.       return __for_each_switch(__begin, __end, __f, _IteratorCategory(),
  114.                              __parallelism_tag);
  115.     }
  116.  
  117.   template<typename _Iterator, typename _Function>
  118.     inline _Function
  119.     for_each(_Iterator __begin, _Iterator __end, _Function __f)
  120.     {
  121.       typedef std::iterator_traits<_Iterator> _IteratorTraits;
  122.       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
  123.       return __for_each_switch(__begin, __end, __f, _IteratorCategory());
  124.     }
  125.  
  126.  
  127.   // Sequential fallback
  128.   template<typename _IIter, typename _Tp>
  129.     inline _IIter
  130.     find(_IIter __begin, _IIter __end, const _Tp& __val,
  131.          __gnu_parallel::sequential_tag)
  132.     { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
  133.  
  134.   // Sequential fallback for input iterator case
  135.   template<typename _IIter, typename _Tp, typename _IteratorTag>
  136.     inline _IIter
  137.     __find_switch(_IIter __begin, _IIter __end, const _Tp& __val,
  138.                 _IteratorTag)
  139.     { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
  140.  
  141.   // Parallel find for random access iterators
  142.   template<typename _RAIter, typename _Tp>
  143.     _RAIter
  144.     __find_switch(_RAIter __begin, _RAIter __end,
  145.                 const _Tp& __val, random_access_iterator_tag)
  146.     {
  147.       typedef iterator_traits<_RAIter> _TraitsType;
  148.       typedef typename _TraitsType::value_type _ValueType;
  149.  
  150.       if (_GLIBCXX_PARALLEL_CONDITION(true))
  151.         {
  152.           __gnu_parallel::__binder2nd<__gnu_parallel::_EqualTo<_ValueType,
  153.                                                                const _Tp&>,
  154.                                       _ValueType, const _Tp&, bool>
  155.             __comp(__gnu_parallel::_EqualTo<_ValueType, const _Tp&>(), __val);
  156.           return __gnu_parallel::__find_template(
  157.                    __begin, __end, __begin, __comp,
  158.                    __gnu_parallel::__find_if_selector()).first;
  159.         }
  160.       else
  161.         return _GLIBCXX_STD_A::find(__begin, __end, __val);
  162.     }
  163.  
  164.   // Public interface
  165.   template<typename _IIter, typename _Tp>
  166.     inline _IIter
  167.     find(_IIter __begin, _IIter __end, const _Tp& __val)
  168.     {
  169.       typedef std::iterator_traits<_IIter> _IteratorTraits;
  170.       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
  171.       return __find_switch(__begin, __end, __val, _IteratorCategory());
  172.     }
  173.  
  174.   // Sequential fallback
  175.   template<typename _IIter, typename _Predicate>
  176.     inline _IIter
  177.     find_if(_IIter __begin, _IIter __end, _Predicate __pred,
  178.             __gnu_parallel::sequential_tag)
  179.     { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
  180.  
  181.   // Sequential fallback for input iterator case
  182.   template<typename _IIter, typename _Predicate, typename _IteratorTag>
  183.     inline _IIter
  184.     __find_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
  185.                    _IteratorTag)
  186.     { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
  187.  
  188.   // Parallel find_if for random access iterators
  189.   template<typename _RAIter, typename _Predicate>
  190.     _RAIter
  191.     __find_if_switch(_RAIter __begin, _RAIter __end,
  192.                    _Predicate __pred, random_access_iterator_tag)
  193.     {
  194.       if (_GLIBCXX_PARALLEL_CONDITION(true))
  195.         return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
  196.                                              __gnu_parallel::
  197.                                              __find_if_selector()).first;
  198.       else
  199.         return _GLIBCXX_STD_A::find_if(__begin, __end, __pred);
  200.     }
  201.  
  202.   // Public interface
  203.   template<typename _IIter, typename _Predicate>
  204.     inline _IIter
  205.     find_if(_IIter __begin, _IIter __end, _Predicate __pred)
  206.     {
  207.       typedef std::iterator_traits<_IIter> _IteratorTraits;
  208.       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
  209.       return __find_if_switch(__begin, __end, __pred, _IteratorCategory());
  210.     }
  211.  
  212.   // Sequential fallback
  213.   template<typename _IIter, typename _FIterator>
  214.     inline _IIter
  215.     find_first_of(_IIter __begin1, _IIter __end1,
  216.                   _FIterator __begin2, _FIterator __end2,
  217.                   __gnu_parallel::sequential_tag)
  218.     { return _GLIBCXX_STD_A::find_first_of(__begin1, __end1, __begin2, __end2);
  219.       }
  220.  
  221.   // Sequential fallback
  222.   template<typename _IIter, typename _FIterator,
  223.            typename _BinaryPredicate>
  224.     inline _IIter
  225.     find_first_of(_IIter __begin1, _IIter __end1,
  226.                   _FIterator __begin2, _FIterator __end2,
  227.                   _BinaryPredicate __comp, __gnu_parallel::sequential_tag)
  228.   { return _GLIBCXX_STD_A::find_first_of(
  229.              __begin1, __end1, __begin2, __end2, __comp); }
  230.  
  231.   // Sequential fallback for input iterator type
  232.   template<typename _IIter, typename _FIterator,
  233.            typename _IteratorTag1, typename _IteratorTag2>
  234.     inline _IIter
  235.     __find_first_of_switch(_IIter __begin1, _IIter __end1,
  236.                          _FIterator __begin2, _FIterator __end2,
  237.                          _IteratorTag1, _IteratorTag2)
  238.     { return find_first_of(__begin1, __end1, __begin2, __end2,
  239.                            __gnu_parallel::sequential_tag()); }
  240.  
  241.   // Parallel algorithm for random access iterators
  242.   template<typename _RAIter, typename _FIterator,
  243.            typename _BinaryPredicate, typename _IteratorTag>
  244.     inline _RAIter
  245.     __find_first_of_switch(_RAIter __begin1,
  246.                          _RAIter __end1,
  247.                          _FIterator __begin2, _FIterator __end2,
  248.                          _BinaryPredicate __comp, random_access_iterator_tag,
  249.                          _IteratorTag)
  250.     {
  251.       return __gnu_parallel::
  252.         __find_template(__begin1, __end1, __begin1, __comp,
  253.                       __gnu_parallel::__find_first_of_selector
  254.                       <_FIterator>(__begin2, __end2)).first;
  255.     }
  256.  
  257.   // Sequential fallback for input iterator type
  258.   template<typename _IIter, typename _FIterator,
  259.            typename _BinaryPredicate, typename _IteratorTag1,
  260.            typename _IteratorTag2>
  261.     inline _IIter
  262.     __find_first_of_switch(_IIter __begin1, _IIter __end1,
  263.                          _FIterator __begin2, _FIterator __end2,
  264.                          _BinaryPredicate __comp, _IteratorTag1, _IteratorTag2)
  265.     { return find_first_of(__begin1, __end1, __begin2, __end2, __comp,
  266.                            __gnu_parallel::sequential_tag()); }
  267.  
  268.   // Public interface
  269.   template<typename _IIter, typename _FIterator,
  270.            typename _BinaryPredicate>
  271.     inline _IIter
  272.     find_first_of(_IIter __begin1, _IIter __end1,
  273.                   _FIterator __begin2, _FIterator __end2,
  274.                   _BinaryPredicate __comp)
  275.     {
  276.       typedef std::iterator_traits<_IIter> _IIterTraits;
  277.       typedef std::iterator_traits<_FIterator> _FIterTraits;
  278.       typedef typename _IIterTraits::iterator_category _IIteratorCategory;
  279.       typedef typename _FIterTraits::iterator_category _FIteratorCategory;
  280.  
  281.       return __find_first_of_switch(__begin1, __end1, __begin2, __end2, __comp,
  282.                                   _IIteratorCategory(), _FIteratorCategory());
  283.     }
  284.  
  285.   // Public interface, insert default comparator
  286.   template<typename _IIter, typename _FIterator>
  287.     inline _IIter
  288.     find_first_of(_IIter __begin1, _IIter __end1,
  289.                   _FIterator __begin2, _FIterator __end2)
  290.     {
  291.       typedef std::iterator_traits<_IIter> _IIterTraits;
  292.       typedef std::iterator_traits<_FIterator> _FIterTraits;
  293.       typedef typename _IIterTraits::value_type _IValueType;
  294.       typedef typename _FIterTraits::value_type _FValueType;
  295.  
  296.       return __gnu_parallel::find_first_of(__begin1, __end1, __begin2, __end2,
  297.                          __gnu_parallel::_EqualTo<_IValueType, _FValueType>());
  298.     }
  299.  
  300.   // Sequential fallback
  301.   template<typename _IIter, typename _OutputIterator>
  302.     inline _OutputIterator
  303.     unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
  304.                 __gnu_parallel::sequential_tag)
  305.     { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out); }
  306.  
  307.   // Sequential fallback
  308.   template<typename _IIter, typename _OutputIterator,
  309.            typename _Predicate>
  310.     inline _OutputIterator
  311.     unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
  312.                 _Predicate __pred, __gnu_parallel::sequential_tag)
  313.     { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out, __pred); }
  314.  
  315.   // Sequential fallback for input iterator case
  316.   template<typename _IIter, typename _OutputIterator,
  317.            typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
  318.     inline _OutputIterator
  319.     __unique_copy_switch(_IIter __begin, _IIter __last,
  320.                        _OutputIterator __out, _Predicate __pred,
  321.                        _IteratorTag1, _IteratorTag2)
  322.     { return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred); }
  323.  
  324.   // Parallel unique_copy for random access iterators
  325.   template<typename _RAIter, typename RandomAccessOutputIterator,
  326.            typename _Predicate>
  327.     RandomAccessOutputIterator
  328.     __unique_copy_switch(_RAIter __begin, _RAIter __last,
  329.                        RandomAccessOutputIterator __out, _Predicate __pred,
  330.                        random_access_iterator_tag, random_access_iterator_tag)
  331.     {
  332.       if (_GLIBCXX_PARALLEL_CONDITION(
  333.             static_cast<__gnu_parallel::_SequenceIndex>(__last - __begin)
  334.             > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
  335.         return __gnu_parallel::__parallel_unique_copy(
  336.                  __begin, __last, __out, __pred);
  337.       else
  338.         return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred);
  339.     }
  340.  
  341.   // Public interface
  342.   template<typename _IIter, typename _OutputIterator>
  343.     inline _OutputIterator
  344.     unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out)
  345.     {
  346.       typedef std::iterator_traits<_IIter> _IIterTraits;
  347.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  348.       typedef typename _IIterTraits::iterator_category _IIteratorCategory;
  349.       typedef typename _IIterTraits::value_type _ValueType;
  350.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  351.  
  352.       return __unique_copy_switch(
  353.                __begin1, __end1, __out, equal_to<_ValueType>(),
  354.                _IIteratorCategory(), _OIterCategory());
  355.     }
  356.  
  357.   // Public interface
  358.   template<typename _IIter, typename _OutputIterator, typename _Predicate>
  359.     inline _OutputIterator
  360.     unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
  361.                 _Predicate __pred)
  362.     {
  363.       typedef std::iterator_traits<_IIter> _IIterTraits;
  364.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  365.       typedef typename _IIterTraits::iterator_category _IIteratorCategory;
  366.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  367.  
  368.       return __unique_copy_switch(
  369.                __begin1, __end1, __out, __pred,
  370.                _IIteratorCategory(), _OIterCategory());
  371.     }
  372.  
  373.   // Sequential fallback
  374.   template<typename _IIter1, typename _IIter2,
  375.            typename _OutputIterator>
  376.     inline _OutputIterator
  377.     set_union(_IIter1 __begin1, _IIter1 __end1,
  378.               _IIter2 __begin2, _IIter2 __end2,
  379.               _OutputIterator __out, __gnu_parallel::sequential_tag)
  380.     { return _GLIBCXX_STD_A::set_union(
  381.                __begin1, __end1, __begin2, __end2, __out); }
  382.  
  383.   // Sequential fallback
  384.   template<typename _IIter1, typename _IIter2,
  385.            typename _OutputIterator, typename _Predicate>
  386.     inline _OutputIterator
  387.     set_union(_IIter1 __begin1, _IIter1 __end1,
  388.               _IIter2 __begin2, _IIter2 __end2,
  389.               _OutputIterator __out, _Predicate __pred,
  390.               __gnu_parallel::sequential_tag)
  391.     { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
  392.                                        __begin2, __end2, __out, __pred); }
  393.  
  394.   // Sequential fallback for input iterator case
  395.   template<typename _IIter1, typename _IIter2, typename _Predicate,
  396.            typename _OutputIterator, typename _IteratorTag1,
  397.            typename _IteratorTag2, typename _IteratorTag3>
  398.     inline _OutputIterator
  399.     __set_union_switch(
  400.       _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
  401.       _OutputIterator __result, _Predicate __pred,
  402.       _IteratorTag1, _IteratorTag2, _IteratorTag3)
  403.     { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
  404.                                        __begin2, __end2, __result, __pred); }
  405.  
  406.   // Parallel set_union for random access iterators
  407.   template<typename _RAIter1, typename _RAIter2,
  408.            typename _Output_RAIter, typename _Predicate>
  409.     _Output_RAIter
  410.     __set_union_switch(_RAIter1 __begin1, _RAIter1 __end1,
  411.                      _RAIter2 __begin2, _RAIter2 __end2,
  412.                      _Output_RAIter __result, _Predicate __pred,
  413.                      random_access_iterator_tag, random_access_iterator_tag,
  414.                      random_access_iterator_tag)
  415.     {
  416.       if (_GLIBCXX_PARALLEL_CONDITION(
  417.             static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  418.             >= __gnu_parallel::_Settings::get().set_union_minimal_n
  419.             || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
  420.             >= __gnu_parallel::_Settings::get().set_union_minimal_n))
  421.         return __gnu_parallel::__parallel_set_union(
  422.                  __begin1, __end1, __begin2, __end2, __result, __pred);
  423.       else
  424.         return _GLIBCXX_STD_A::set_union(__begin1, __end1,
  425.                                          __begin2, __end2, __result, __pred);
  426.     }
  427.  
  428.   // Public interface
  429.   template<typename _IIter1, typename _IIter2,
  430.            typename _OutputIterator>
  431.     inline _OutputIterator
  432.     set_union(_IIter1 __begin1, _IIter1 __end1,
  433.               _IIter2 __begin2, _IIter2 __end2, _OutputIterator __out)
  434.     {
  435.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  436.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  437.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  438.       typedef typename _IIterTraits1::iterator_category
  439.         _IIterCategory1;
  440.       typedef typename _IIterTraits2::iterator_category
  441.         _IIterCategory2;
  442.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  443.       typedef typename _IIterTraits1::value_type _ValueType1;
  444.       typedef typename _IIterTraits2::value_type _ValueType2;
  445.  
  446.       return __set_union_switch(
  447.                __begin1, __end1, __begin2, __end2, __out,
  448.                __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
  449.                _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  450.     }
  451.  
  452.   // Public interface
  453.   template<typename _IIter1, typename _IIter2,
  454.            typename _OutputIterator, typename _Predicate>
  455.     inline _OutputIterator
  456.     set_union(_IIter1 __begin1, _IIter1 __end1,
  457.               _IIter2 __begin2, _IIter2 __end2,
  458.               _OutputIterator __out, _Predicate __pred)
  459.     {
  460.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  461.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  462.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  463.       typedef typename _IIterTraits1::iterator_category
  464.         _IIterCategory1;
  465.       typedef typename _IIterTraits2::iterator_category
  466.         _IIterCategory2;
  467.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  468.  
  469.       return __set_union_switch(
  470.                __begin1, __end1, __begin2, __end2, __out, __pred,
  471.                _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  472.     }
  473.  
  474.   // Sequential fallback.
  475.   template<typename _IIter1, typename _IIter2,
  476.            typename _OutputIterator>
  477.     inline _OutputIterator
  478.     set_intersection(_IIter1 __begin1, _IIter1 __end1,
  479.                      _IIter2 __begin2, _IIter2 __end2,
  480.                      _OutputIterator __out, __gnu_parallel::sequential_tag)
  481.     { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1,
  482.                                               __begin2, __end2, __out); }
  483.  
  484.   // Sequential fallback.
  485.   template<typename _IIter1, typename _IIter2,
  486.            typename _OutputIterator, typename _Predicate>
  487.     inline _OutputIterator
  488.     set_intersection(_IIter1 __begin1, _IIter1 __end1,
  489.                      _IIter2 __begin2, _IIter2 __end2,
  490.                      _OutputIterator __out, _Predicate __pred,
  491.                      __gnu_parallel::sequential_tag)
  492.     { return _GLIBCXX_STD_A::set_intersection(
  493.                __begin1, __end1, __begin2, __end2, __out, __pred); }
  494.  
  495.   // Sequential fallback for input iterator case
  496.   template<typename _IIter1, typename _IIter2,
  497.            typename _Predicate, typename _OutputIterator,
  498.            typename _IteratorTag1, typename _IteratorTag2,
  499.            typename _IteratorTag3>
  500.     inline _OutputIterator
  501.     __set_intersection_switch(_IIter1 __begin1, _IIter1 __end1,
  502.                               _IIter2 __begin2, _IIter2 __end2,
  503.                               _OutputIterator __result, _Predicate __pred,
  504.                               _IteratorTag1, _IteratorTag2, _IteratorTag3)
  505.     { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1, __begin2,
  506.                                               __end2, __result, __pred); }
  507.  
  508.   // Parallel set_intersection for random access iterators
  509.   template<typename _RAIter1, typename _RAIter2,
  510.            typename _Output_RAIter, typename _Predicate>
  511.     _Output_RAIter
  512.     __set_intersection_switch(_RAIter1 __begin1,
  513.                             _RAIter1 __end1,
  514.                             _RAIter2 __begin2,
  515.                             _RAIter2 __end2,
  516.                             _Output_RAIter __result,
  517.                             _Predicate __pred,
  518.                             random_access_iterator_tag,
  519.                             random_access_iterator_tag,
  520.                             random_access_iterator_tag)
  521.     {
  522.       if (_GLIBCXX_PARALLEL_CONDITION(
  523.             static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  524.             >= __gnu_parallel::_Settings::get().set_union_minimal_n
  525.             || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
  526.             >= __gnu_parallel::_Settings::get().set_union_minimal_n))
  527.         return __gnu_parallel::__parallel_set_intersection(
  528.                  __begin1, __end1, __begin2, __end2, __result, __pred);
  529.       else
  530.         return _GLIBCXX_STD_A::set_intersection(
  531.                  __begin1, __end1, __begin2, __end2, __result, __pred);
  532.     }
  533.  
  534.   // Public interface
  535.   template<typename _IIter1, typename _IIter2,
  536.            typename _OutputIterator>
  537.     inline _OutputIterator
  538.     set_intersection(_IIter1 __begin1, _IIter1 __end1,
  539.                      _IIter2 __begin2, _IIter2 __end2,
  540.                      _OutputIterator __out)
  541.     {
  542.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  543.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  544.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  545.       typedef typename _IIterTraits1::iterator_category
  546.         _IIterCategory1;
  547.       typedef typename _IIterTraits2::iterator_category
  548.         _IIterCategory2;
  549.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  550.       typedef typename _IIterTraits1::value_type _ValueType1;
  551.       typedef typename _IIterTraits2::value_type _ValueType2;
  552.  
  553.       return __set_intersection_switch(
  554.                __begin1, __end1, __begin2, __end2, __out,
  555.                __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
  556.                _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  557.     }
  558.  
  559.   template<typename _IIter1, typename _IIter2,
  560.            typename _OutputIterator, typename _Predicate>
  561.     inline _OutputIterator
  562.     set_intersection(_IIter1 __begin1, _IIter1 __end1,
  563.                      _IIter2 __begin2, _IIter2 __end2,
  564.                      _OutputIterator __out, _Predicate __pred)
  565.     {
  566.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  567.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  568.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  569.       typedef typename _IIterTraits1::iterator_category
  570.         _IIterCategory1;
  571.       typedef typename _IIterTraits2::iterator_category
  572.         _IIterCategory2;
  573.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  574.  
  575.       return __set_intersection_switch(
  576.                __begin1, __end1, __begin2, __end2, __out, __pred,
  577.                _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  578.     }
  579.  
  580.   // Sequential fallback
  581.   template<typename _IIter1, typename _IIter2,
  582.            typename _OutputIterator>
  583.     inline _OutputIterator
  584.     set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
  585.                              _IIter2 __begin2, _IIter2 __end2,
  586.                              _OutputIterator __out,
  587.                              __gnu_parallel::sequential_tag)
  588.     { return _GLIBCXX_STD_A::set_symmetric_difference(
  589.                __begin1, __end1, __begin2, __end2, __out); }
  590.  
  591.   // Sequential fallback
  592.   template<typename _IIter1, typename _IIter2,
  593.            typename _OutputIterator, typename _Predicate>
  594.     inline _OutputIterator
  595.     set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
  596.                              _IIter2 __begin2, _IIter2 __end2,
  597.                              _OutputIterator __out, _Predicate __pred,
  598.                              __gnu_parallel::sequential_tag)
  599.     { return _GLIBCXX_STD_A::set_symmetric_difference(
  600.                __begin1, __end1, __begin2, __end2, __out, __pred); }
  601.  
  602.   // Sequential fallback for input iterator case
  603.   template<typename _IIter1, typename _IIter2,
  604.            typename _Predicate, typename _OutputIterator,
  605.            typename _IteratorTag1, typename _IteratorTag2,
  606.            typename _IteratorTag3>
  607.     inline _OutputIterator
  608.     __set_symmetric_difference_switch(
  609.       _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
  610.       _OutputIterator __result, _Predicate __pred,
  611.       _IteratorTag1, _IteratorTag2, _IteratorTag3)
  612.     { return _GLIBCXX_STD_A::set_symmetric_difference(
  613.                __begin1, __end1, __begin2, __end2, __result, __pred); }
  614.  
  615.   // Parallel set_symmetric_difference for random access iterators
  616.   template<typename _RAIter1, typename _RAIter2,
  617.            typename _Output_RAIter, typename _Predicate>
  618.     _Output_RAIter
  619.     __set_symmetric_difference_switch(_RAIter1 __begin1,
  620.                                     _RAIter1 __end1,
  621.                                     _RAIter2 __begin2,
  622.                                     _RAIter2 __end2,
  623.                                     _Output_RAIter __result,
  624.                                     _Predicate __pred,
  625.                                     random_access_iterator_tag,
  626.                                     random_access_iterator_tag,
  627.                                     random_access_iterator_tag)
  628.     {
  629.       if (_GLIBCXX_PARALLEL_CONDITION(
  630.       static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  631.       >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
  632.       || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
  633.       >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n))
  634.   return __gnu_parallel::__parallel_set_symmetric_difference(
  635.            __begin1, __end1, __begin2, __end2, __result, __pred);
  636.       else
  637.         return _GLIBCXX_STD_A::set_symmetric_difference(
  638.                  __begin1, __end1, __begin2, __end2, __result, __pred);
  639.     }
  640.  
  641.   // Public interface.
  642.   template<typename _IIter1, typename _IIter2,
  643.            typename _OutputIterator>
  644.     inline _OutputIterator
  645.     set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
  646.                              _IIter2 __begin2, _IIter2 __end2,
  647.                              _OutputIterator __out)
  648.     {
  649.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  650.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  651.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  652.       typedef typename _IIterTraits1::iterator_category
  653.         _IIterCategory1;
  654.       typedef typename _IIterTraits2::iterator_category
  655.         _IIterCategory2;
  656.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  657.       typedef typename _IIterTraits1::value_type _ValueType1;
  658.       typedef typename _IIterTraits2::value_type _ValueType2;
  659.  
  660.       return __set_symmetric_difference_switch(
  661.                __begin1, __end1, __begin2, __end2, __out,
  662.                __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
  663.                _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  664.     }
  665.  
  666.   // Public interface.
  667.   template<typename _IIter1, typename _IIter2,
  668.            typename _OutputIterator, typename _Predicate>
  669.     inline _OutputIterator
  670.     set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
  671.                              _IIter2 __begin2, _IIter2 __end2,
  672.                              _OutputIterator __out, _Predicate __pred)
  673.     {
  674.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  675.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  676.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  677.       typedef typename _IIterTraits1::iterator_category
  678.         _IIterCategory1;
  679.       typedef typename _IIterTraits2::iterator_category
  680.         _IIterCategory2;
  681.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  682.  
  683.       return __set_symmetric_difference_switch(
  684.                __begin1, __end1, __begin2, __end2, __out, __pred,
  685.                _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  686.     }
  687.  
  688.   // Sequential fallback.
  689.   template<typename _IIter1, typename _IIter2,
  690.            typename _OutputIterator>
  691.     inline _OutputIterator
  692.     set_difference(_IIter1 __begin1, _IIter1 __end1,
  693.                    _IIter2 __begin2, _IIter2 __end2,
  694.                    _OutputIterator __out, __gnu_parallel::sequential_tag)
  695.     { return _GLIBCXX_STD_A::set_difference(
  696.                __begin1,__end1, __begin2, __end2, __out); }
  697.  
  698.   // Sequential fallback.
  699.   template<typename _IIter1, typename _IIter2,
  700.            typename _OutputIterator, typename _Predicate>
  701.     inline _OutputIterator
  702.     set_difference(_IIter1 __begin1, _IIter1 __end1,
  703.                    _IIter2 __begin2, _IIter2 __end2,
  704.                    _OutputIterator __out, _Predicate __pred,
  705.                    __gnu_parallel::sequential_tag)
  706.     { return _GLIBCXX_STD_A::set_difference(__begin1, __end1,
  707.                                             __begin2, __end2, __out, __pred); }
  708.  
  709.   // Sequential fallback for input iterator case.
  710.   template<typename _IIter1, typename _IIter2, typename _Predicate,
  711.            typename _OutputIterator, typename _IteratorTag1,
  712.            typename _IteratorTag2, typename _IteratorTag3>
  713.     inline _OutputIterator
  714.     __set_difference_switch(_IIter1 __begin1, _IIter1 __end1,
  715.                           _IIter2 __begin2, _IIter2 __end2,
  716.                           _OutputIterator __result, _Predicate __pred,
  717.                           _IteratorTag1, _IteratorTag2, _IteratorTag3)
  718.     { return _GLIBCXX_STD_A::set_difference(
  719.                __begin1, __end1, __begin2, __end2, __result, __pred); }
  720.  
  721.   // Parallel set_difference for random access iterators
  722.   template<typename _RAIter1, typename _RAIter2,
  723.            typename _Output_RAIter, typename _Predicate>
  724.     _Output_RAIter
  725.     __set_difference_switch(_RAIter1 __begin1,
  726.                           _RAIter1 __end1,
  727.                           _RAIter2 __begin2,
  728.                           _RAIter2 __end2,
  729.                           _Output_RAIter __result, _Predicate __pred,
  730.                           random_access_iterator_tag,
  731.                           random_access_iterator_tag,
  732.                           random_access_iterator_tag)
  733.     {
  734.       if (_GLIBCXX_PARALLEL_CONDITION(
  735.             static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  736.             >= __gnu_parallel::_Settings::get().set_difference_minimal_n
  737.             || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
  738.             >= __gnu_parallel::_Settings::get().set_difference_minimal_n))
  739.         return __gnu_parallel::__parallel_set_difference(
  740.                  __begin1, __end1, __begin2, __end2, __result, __pred);
  741.       else
  742.         return _GLIBCXX_STD_A::set_difference(
  743.                  __begin1, __end1, __begin2, __end2, __result, __pred);
  744.     }
  745.  
  746.   // Public interface
  747.   template<typename _IIter1, typename _IIter2,
  748.            typename _OutputIterator>
  749.     inline _OutputIterator
  750.     set_difference(_IIter1 __begin1, _IIter1 __end1,
  751.                    _IIter2 __begin2, _IIter2 __end2,
  752.                    _OutputIterator __out)
  753.     {
  754.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  755.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  756.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  757.       typedef typename _IIterTraits1::iterator_category
  758.         _IIterCategory1;
  759.       typedef typename _IIterTraits2::iterator_category
  760.         _IIterCategory2;
  761.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  762.       typedef typename _IIterTraits1::value_type _ValueType1;
  763.       typedef typename _IIterTraits2::value_type _ValueType2;
  764.  
  765.       return __set_difference_switch(
  766.                __begin1, __end1, __begin2, __end2, __out,
  767.                __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
  768.                _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  769.     }
  770.  
  771.   // Public interface
  772.   template<typename _IIter1, typename _IIter2,
  773.            typename _OutputIterator, typename _Predicate>
  774.     inline _OutputIterator
  775.     set_difference(_IIter1 __begin1, _IIter1 __end1,
  776.                    _IIter2 __begin2, _IIter2 __end2,
  777.                    _OutputIterator __out, _Predicate __pred)
  778.     {
  779.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  780.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  781.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  782.       typedef typename _IIterTraits1::iterator_category
  783.         _IIterCategory1;
  784.       typedef typename _IIterTraits2::iterator_category
  785.         _IIterCategory2;
  786.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  787.  
  788.       return __set_difference_switch(
  789.                __begin1, __end1, __begin2, __end2, __out, __pred,
  790.                _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  791.     }
  792.  
  793.   // Sequential fallback
  794.   template<typename _FIterator>
  795.     inline _FIterator
  796.     adjacent_find(_FIterator __begin, _FIterator __end,
  797.                   __gnu_parallel::sequential_tag)
  798.     { return _GLIBCXX_STD_A::adjacent_find(__begin, __end); }
  799.  
  800.   // Sequential fallback
  801.   template<typename _FIterator, typename _BinaryPredicate>
  802.     inline _FIterator
  803.     adjacent_find(_FIterator __begin, _FIterator __end,
  804.                   _BinaryPredicate __binary_pred,
  805.                   __gnu_parallel::sequential_tag)
  806.     { return _GLIBCXX_STD_A::adjacent_find(__begin, __end, __binary_pred); }
  807.  
  808.   // Parallel algorithm for random access iterators
  809.   template<typename _RAIter>
  810.     _RAIter
  811.     __adjacent_find_switch(_RAIter __begin, _RAIter __end,
  812.                          random_access_iterator_tag)
  813.     {
  814.       typedef iterator_traits<_RAIter> _TraitsType;
  815.       typedef typename _TraitsType::value_type _ValueType;
  816.  
  817.       if (_GLIBCXX_PARALLEL_CONDITION(true))
  818.         {
  819.           _RAIter __spot = __gnu_parallel::
  820.               __find_template(
  821.                 __begin, __end - 1, __begin, equal_to<_ValueType>(),
  822.                 __gnu_parallel::__adjacent_find_selector())
  823.             .first;
  824.           if (__spot == (__end - 1))
  825.             return __end;
  826.           else
  827.             return __spot;
  828.         }
  829.       else
  830.         return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag());
  831.     }
  832.  
  833.   // Sequential fallback for input iterator case
  834.   template<typename _FIterator, typename _IteratorTag>
  835.     inline _FIterator
  836.     __adjacent_find_switch(_FIterator __begin, _FIterator __end,
  837.                          _IteratorTag)
  838.     { return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag()); }
  839.  
  840.   // Public interface
  841.   template<typename _FIterator>
  842.     inline _FIterator
  843.     adjacent_find(_FIterator __begin, _FIterator __end)
  844.     {
  845.       typedef iterator_traits<_FIterator> _TraitsType;
  846.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  847.       return __adjacent_find_switch(__begin, __end, _IteratorCategory());
  848.     }
  849.  
  850.   // Sequential fallback for input iterator case
  851.   template<typename _FIterator, typename _BinaryPredicate,
  852.            typename _IteratorTag>
  853.     inline _FIterator
  854.     __adjacent_find_switch(_FIterator __begin, _FIterator __end,
  855.                          _BinaryPredicate __pred, _IteratorTag)
  856.     { return adjacent_find(__begin, __end, __pred,
  857.                            __gnu_parallel::sequential_tag()); }
  858.  
  859.   // Parallel algorithm for random access iterators
  860.   template<typename _RAIter, typename _BinaryPredicate>
  861.     _RAIter
  862.     __adjacent_find_switch(_RAIter __begin, _RAIter __end,
  863.                          _BinaryPredicate __pred, random_access_iterator_tag)
  864.     {
  865.       if (_GLIBCXX_PARALLEL_CONDITION(true))
  866.         return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
  867.                                              __gnu_parallel::
  868.                                              __adjacent_find_selector()).first;
  869.       else
  870.         return adjacent_find(__begin, __end, __pred,
  871.                              __gnu_parallel::sequential_tag());
  872.     }
  873.  
  874.   // Public interface
  875.   template<typename _FIterator, typename _BinaryPredicate>
  876.     inline _FIterator
  877.     adjacent_find(_FIterator __begin, _FIterator __end,
  878.                   _BinaryPredicate __pred)
  879.     {
  880.       typedef iterator_traits<_FIterator> _TraitsType;
  881.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  882.       return __adjacent_find_switch(__begin, __end, __pred,
  883.                                     _IteratorCategory());
  884.     }
  885.  
  886.   // Sequential fallback
  887.   template<typename _IIter, typename _Tp>
  888.     inline typename iterator_traits<_IIter>::difference_type
  889.     count(_IIter __begin, _IIter __end, const _Tp& __value,
  890.           __gnu_parallel::sequential_tag)
  891.     { return _GLIBCXX_STD_A::count(__begin, __end, __value); }
  892.  
  893.   // Parallel code for random access iterators
  894.   template<typename _RAIter, typename _Tp>
  895.     typename iterator_traits<_RAIter>::difference_type
  896.     __count_switch(_RAIter __begin, _RAIter __end,
  897.                  const _Tp& __value, random_access_iterator_tag,
  898.                  __gnu_parallel::_Parallelism __parallelism_tag)
  899.     {
  900.       typedef iterator_traits<_RAIter> _TraitsType;
  901.       typedef typename _TraitsType::value_type _ValueType;
  902.       typedef typename _TraitsType::difference_type _DifferenceType;
  903.       typedef __gnu_parallel::_SequenceIndex _SequenceIndex;
  904.  
  905.       if (_GLIBCXX_PARALLEL_CONDITION(
  906.             static_cast<_SequenceIndex>(__end - __begin)
  907.             >= __gnu_parallel::_Settings::get().count_minimal_n
  908.             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  909.         {
  910.           __gnu_parallel::__count_selector<_RAIter, _DifferenceType>
  911.             __functionality;
  912.           _DifferenceType __res = 0;
  913.           __gnu_parallel::
  914.             __for_each_template_random_access(
  915.               __begin, __end, __value, __functionality,
  916.               std::plus<_SequenceIndex>(), __res, __res, -1,
  917.               __parallelism_tag);
  918.           return __res;
  919.         }
  920.       else
  921.         return count(__begin, __end, __value,
  922.                      __gnu_parallel::sequential_tag());
  923.     }
  924.  
  925.   // Sequential fallback for input iterator case.
  926.   template<typename _IIter, typename _Tp, typename _IteratorTag>
  927.     inline typename iterator_traits<_IIter>::difference_type
  928.     __count_switch(_IIter __begin, _IIter __end, const _Tp& __value,
  929.                  _IteratorTag)
  930.     { return count(__begin, __end, __value, __gnu_parallel::sequential_tag());
  931.       }
  932.  
  933.   // Public interface.
  934.   template<typename _IIter, typename _Tp>
  935.     inline typename iterator_traits<_IIter>::difference_type
  936.     count(_IIter __begin, _IIter __end, const _Tp& __value,
  937.           __gnu_parallel::_Parallelism __parallelism_tag)
  938.     {
  939.       typedef iterator_traits<_IIter> _TraitsType;
  940.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  941.       return __count_switch(__begin, __end, __value, _IteratorCategory(),
  942.                             __parallelism_tag);
  943.     }
  944.  
  945.   template<typename _IIter, typename _Tp>
  946.     inline typename iterator_traits<_IIter>::difference_type
  947.     count(_IIter __begin, _IIter __end, const _Tp& __value)
  948.     {
  949.       typedef iterator_traits<_IIter> _TraitsType;
  950.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  951.       return __count_switch(__begin, __end, __value, _IteratorCategory());
  952.     }
  953.  
  954.  
  955.   // Sequential fallback.
  956.   template<typename _IIter, typename _Predicate>
  957.     inline typename iterator_traits<_IIter>::difference_type
  958.     count_if(_IIter __begin, _IIter __end, _Predicate __pred,
  959.              __gnu_parallel::sequential_tag)
  960.     { return _GLIBCXX_STD_A::count_if(__begin, __end, __pred); }
  961.  
  962.   // Parallel count_if for random access iterators
  963.   template<typename _RAIter, typename _Predicate>
  964.     typename iterator_traits<_RAIter>::difference_type
  965.     __count_if_switch(_RAIter __begin, _RAIter __end,
  966.                     _Predicate __pred, random_access_iterator_tag,
  967.                     __gnu_parallel::_Parallelism __parallelism_tag)
  968.     {
  969.       typedef iterator_traits<_RAIter> _TraitsType;
  970.       typedef typename _TraitsType::value_type _ValueType;
  971.       typedef typename _TraitsType::difference_type _DifferenceType;
  972.       typedef __gnu_parallel::_SequenceIndex _SequenceIndex;
  973.  
  974.       if (_GLIBCXX_PARALLEL_CONDITION(
  975.             static_cast<_SequenceIndex>(__end - __begin)
  976.             >= __gnu_parallel::_Settings::get().count_minimal_n
  977.             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  978.         {
  979.           _DifferenceType __res = 0;
  980.           __gnu_parallel::
  981.             __count_if_selector<_RAIter, _DifferenceType>
  982.             __functionality;
  983.           __gnu_parallel::
  984.             __for_each_template_random_access(
  985.               __begin, __end, __pred, __functionality,
  986.               std::plus<_SequenceIndex>(), __res, __res, -1,
  987.               __parallelism_tag);
  988.           return __res;
  989.         }
  990.       else
  991.         return count_if(__begin, __end, __pred,
  992.                         __gnu_parallel::sequential_tag());
  993.     }
  994.  
  995.   // Sequential fallback for input iterator case.
  996.   template<typename _IIter, typename _Predicate, typename _IteratorTag>
  997.     inline typename iterator_traits<_IIter>::difference_type
  998.     __count_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
  999.                     _IteratorTag)
  1000.     { return count_if(__begin, __end, __pred,
  1001.                       __gnu_parallel::sequential_tag()); }
  1002.  
  1003.   // Public interface.
  1004.   template<typename _IIter, typename _Predicate>
  1005.     inline typename iterator_traits<_IIter>::difference_type
  1006.     count_if(_IIter __begin, _IIter __end, _Predicate __pred,
  1007.              __gnu_parallel::_Parallelism __parallelism_tag)
  1008.     {
  1009.       typedef iterator_traits<_IIter> _TraitsType;
  1010.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  1011.       return __count_if_switch(__begin, __end, __pred, _IteratorCategory(),
  1012.                              __parallelism_tag);
  1013.     }
  1014.  
  1015.   template<typename _IIter, typename _Predicate>
  1016.     inline typename iterator_traits<_IIter>::difference_type
  1017.     count_if(_IIter __begin, _IIter __end, _Predicate __pred)
  1018.     {
  1019.       typedef iterator_traits<_IIter> _TraitsType;
  1020.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  1021.       return __count_if_switch(__begin, __end, __pred, _IteratorCategory());
  1022.     }
  1023.  
  1024.  
  1025.   // Sequential fallback.
  1026.   template<typename _FIterator1, typename _FIterator2>
  1027.     inline _FIterator1
  1028.     search(_FIterator1 __begin1, _FIterator1 __end1,
  1029.            _FIterator2 __begin2, _FIterator2 __end2,
  1030.            __gnu_parallel::sequential_tag)
  1031.     { return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2); }
  1032.  
  1033.   // Parallel algorithm for random access iterator
  1034.   template<typename _RAIter1, typename _RAIter2>
  1035.     _RAIter1
  1036.     __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
  1037.                   _RAIter2 __begin2, _RAIter2 __end2,
  1038.                   random_access_iterator_tag, random_access_iterator_tag)
  1039.     {
  1040.       typedef std::iterator_traits<_RAIter1> _Iterator1Traits;
  1041.       typedef typename _Iterator1Traits::value_type _ValueType1;
  1042.       typedef std::iterator_traits<_RAIter2> _Iterator2Traits;
  1043.       typedef typename _Iterator2Traits::value_type _ValueType2;
  1044.  
  1045.       if (_GLIBCXX_PARALLEL_CONDITION(
  1046.                 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  1047.             >= __gnu_parallel::_Settings::get().search_minimal_n))
  1048.         return __gnu_parallel::
  1049.           __search_template(
  1050.             __begin1, __end1, __begin2, __end2,
  1051.             __gnu_parallel::_EqualTo<_ValueType1, _ValueType2>());
  1052.       else
  1053.         return search(__begin1, __end1, __begin2, __end2,
  1054.                       __gnu_parallel::sequential_tag());
  1055.     }
  1056.  
  1057.   // Sequential fallback for input iterator case
  1058.   template<typename _FIterator1, typename _FIterator2,
  1059.            typename _IteratorTag1, typename _IteratorTag2>
  1060.     inline _FIterator1
  1061.     __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
  1062.                   _FIterator2 __begin2, _FIterator2 __end2,
  1063.                   _IteratorTag1, _IteratorTag2)
  1064.     { return search(__begin1, __end1, __begin2, __end2,
  1065.                     __gnu_parallel::sequential_tag()); }
  1066.  
  1067.   // Public interface.
  1068.   template<typename _FIterator1, typename _FIterator2>
  1069.     inline _FIterator1
  1070.     search(_FIterator1 __begin1, _FIterator1 __end1,
  1071.            _FIterator2 __begin2, _FIterator2 __end2)
  1072.     {
  1073.       typedef std::iterator_traits<_FIterator1> _Iterator1Traits;
  1074.       typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
  1075.       typedef std::iterator_traits<_FIterator2> _Iterator2Traits;
  1076.       typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
  1077.  
  1078.       return __search_switch(__begin1, __end1, __begin2, __end2,
  1079.                            _IteratorCategory1(), _IteratorCategory2());
  1080.     }
  1081.  
  1082.   // Public interface.
  1083.   template<typename _FIterator1, typename _FIterator2,
  1084.            typename _BinaryPredicate>
  1085.     inline _FIterator1
  1086.     search(_FIterator1 __begin1, _FIterator1 __end1,
  1087.            _FIterator2 __begin2, _FIterator2 __end2,
  1088.            _BinaryPredicate __pred, __gnu_parallel::sequential_tag)
  1089.     { return _GLIBCXX_STD_A::search(
  1090.                                __begin1, __end1, __begin2, __end2, __pred); }
  1091.  
  1092.   // Parallel algorithm for random access iterator.
  1093.   template<typename _RAIter1, typename _RAIter2,
  1094.            typename _BinaryPredicate>
  1095.     _RAIter1
  1096.     __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
  1097.                   _RAIter2 __begin2, _RAIter2 __end2,
  1098.                   _BinaryPredicate __pred,
  1099.                   random_access_iterator_tag, random_access_iterator_tag)
  1100.     {
  1101.       if (_GLIBCXX_PARALLEL_CONDITION(
  1102.                 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  1103.             >= __gnu_parallel::_Settings::get().search_minimal_n))
  1104.         return __gnu_parallel::__search_template(__begin1, __end1,
  1105.                                                __begin2, __end2, __pred);
  1106.       else
  1107.         return search(__begin1, __end1, __begin2, __end2, __pred,
  1108.                       __gnu_parallel::sequential_tag());
  1109.     }
  1110.  
  1111.   // Sequential fallback for input iterator case
  1112.   template<typename _FIterator1, typename _FIterator2,
  1113.            typename _BinaryPredicate, typename _IteratorTag1,
  1114.            typename _IteratorTag2>
  1115.     inline _FIterator1
  1116.     __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
  1117.                   _FIterator2 __begin2, _FIterator2 __end2,
  1118.                   _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2)
  1119.     { return search(__begin1, __end1, __begin2, __end2, __pred,
  1120.                     __gnu_parallel::sequential_tag()); }
  1121.  
  1122.   // Public interface
  1123.   template<typename _FIterator1, typename _FIterator2,
  1124.            typename _BinaryPredicate>
  1125.     inline _FIterator1
  1126.     search(_FIterator1 __begin1, _FIterator1 __end1,
  1127.            _FIterator2 __begin2, _FIterator2 __end2,
  1128.            _BinaryPredicate  __pred)
  1129.     {
  1130.       typedef std::iterator_traits<_FIterator1> _Iterator1Traits;
  1131.       typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
  1132.       typedef std::iterator_traits<_FIterator2> _Iterator2Traits;
  1133.       typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
  1134.       return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
  1135.                            _IteratorCategory1(), _IteratorCategory2());
  1136.     }
  1137.  
  1138.   // Sequential fallback
  1139.   template<typename _FIterator, typename _Integer, typename _Tp>
  1140.     inline _FIterator
  1141.     search_n(_FIterator __begin, _FIterator __end, _Integer __count,
  1142.              const _Tp& __val, __gnu_parallel::sequential_tag)
  1143.     { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val); }
  1144.  
  1145.   // Sequential fallback
  1146.   template<typename _FIterator, typename _Integer, typename _Tp,
  1147.            typename _BinaryPredicate>
  1148.     inline _FIterator
  1149.     search_n(_FIterator __begin, _FIterator __end, _Integer __count,
  1150.              const _Tp& __val, _BinaryPredicate __binary_pred,
  1151.              __gnu_parallel::sequential_tag)
  1152.     { return _GLIBCXX_STD_A::search_n(
  1153.                __begin, __end, __count, __val, __binary_pred); }
  1154.  
  1155.   // Public interface.
  1156.   template<typename _FIterator, typename _Integer, typename _Tp>
  1157.     inline _FIterator
  1158.     search_n(_FIterator __begin, _FIterator __end, _Integer __count,
  1159.              const _Tp& __val)
  1160.     {
  1161.       typedef typename iterator_traits<_FIterator>::value_type _ValueType;
  1162.       return __gnu_parallel::search_n(__begin, __end, __count, __val,
  1163.                       __gnu_parallel::_EqualTo<_ValueType, _Tp>());
  1164.     }
  1165.  
  1166.   // Parallel algorithm for random access iterators.
  1167.   template<typename _RAIter, typename _Integer,
  1168.            typename _Tp, typename _BinaryPredicate>
  1169.     _RAIter
  1170.     __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count,
  1171.                       const _Tp& __val, _BinaryPredicate __binary_pred,
  1172.                       random_access_iterator_tag)
  1173.     {
  1174.       if (_GLIBCXX_PARALLEL_CONDITION(
  1175.                 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1176.             >= __gnu_parallel::_Settings::get().search_minimal_n))
  1177.         {
  1178.           __gnu_parallel::_PseudoSequence<_Tp, _Integer> __ps(__val, __count);
  1179.           return __gnu_parallel::__search_template(
  1180.                    __begin, __end, __ps.begin(), __ps.end(), __binary_pred);
  1181.         }
  1182.       else
  1183.         return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
  1184.                                         __binary_pred);
  1185.     }
  1186.  
  1187.   // Sequential fallback for input iterator case.
  1188.   template<typename _FIterator, typename _Integer, typename _Tp,
  1189.            typename _BinaryPredicate, typename _IteratorTag>
  1190.     inline _FIterator
  1191.     __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count,
  1192.                       const _Tp& __val, _BinaryPredicate __binary_pred,
  1193.                       _IteratorTag)
  1194.     { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
  1195.                                       __binary_pred); }
  1196.  
  1197.   // Public interface.
  1198.   template<typename _FIterator, typename _Integer, typename _Tp,
  1199.            typename _BinaryPredicate>
  1200.     inline _FIterator
  1201.     search_n(_FIterator __begin, _FIterator __end, _Integer __count,
  1202.              const _Tp& __val, _BinaryPredicate __binary_pred)
  1203.     {
  1204.       return __search_n_switch(__begin, __end, __count, __val, __binary_pred,
  1205.                              typename std::iterator_traits<_FIterator>::
  1206.                              iterator_category());
  1207.     }
  1208.  
  1209.  
  1210.   // Sequential fallback.
  1211.   template<typename _IIter, typename _OutputIterator,
  1212.            typename _UnaryOperation>
  1213.     inline _OutputIterator
  1214.     transform(_IIter __begin, _IIter __end, _OutputIterator __result,
  1215.               _UnaryOperation __unary_op, __gnu_parallel::sequential_tag)
  1216.     { return _GLIBCXX_STD_A::transform(__begin, __end, __result, __unary_op); }
  1217.  
  1218.   // Parallel unary transform for random access iterators.
  1219.   template<typename _RAIter1, typename _RAIter2,
  1220.            typename _UnaryOperation>
  1221.     _RAIter2
  1222.     __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
  1223.                       _RAIter2 __result, _UnaryOperation __unary_op,
  1224.                       random_access_iterator_tag, random_access_iterator_tag,
  1225.                       __gnu_parallel::_Parallelism __parallelism_tag)
  1226.     {
  1227.       if (_GLIBCXX_PARALLEL_CONDITION(
  1228.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1229.             >= __gnu_parallel::_Settings::get().transform_minimal_n
  1230.             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  1231.         {
  1232.           bool __dummy = true;
  1233.           typedef __gnu_parallel::_IteratorPair<_RAIter1,
  1234.             _RAIter2, random_access_iterator_tag> _ItTrip;
  1235.           _ItTrip __begin_pair(__begin, __result),
  1236.                   __end_pair(__end, __result + (__end - __begin));
  1237.           __gnu_parallel::__transform1_selector<_ItTrip> __functionality;
  1238.           __gnu_parallel::
  1239.             __for_each_template_random_access(
  1240.               __begin_pair, __end_pair, __unary_op, __functionality,
  1241.               __gnu_parallel::_DummyReduct(),
  1242.               __dummy, __dummy, -1, __parallelism_tag);
  1243.           return __functionality._M_finish_iterator;
  1244.         }
  1245.       else
  1246.         return transform(__begin, __end, __result, __unary_op,
  1247.                          __gnu_parallel::sequential_tag());
  1248.     }
  1249.  
  1250.   // Sequential fallback for input iterator case.
  1251.   template<typename _RAIter1, typename _RAIter2,
  1252.            typename _UnaryOperation, typename _IteratorTag1,
  1253.            typename _IteratorTag2>
  1254.     inline _RAIter2
  1255.     __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
  1256.                       _RAIter2 __result, _UnaryOperation __unary_op,
  1257.                       _IteratorTag1, _IteratorTag2)
  1258.     { return transform(__begin, __end, __result, __unary_op,
  1259.                        __gnu_parallel::sequential_tag()); }
  1260.  
  1261.   // Public interface.
  1262.   template<typename _IIter, typename _OutputIterator,
  1263.            typename _UnaryOperation>
  1264.     inline _OutputIterator
  1265.     transform(_IIter __begin, _IIter __end, _OutputIterator __result,
  1266.               _UnaryOperation __unary_op,
  1267.               __gnu_parallel::_Parallelism __parallelism_tag)
  1268.     {
  1269.       typedef std::iterator_traits<_IIter> _IIterTraits;
  1270.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  1271.       typedef typename _IIterTraits::iterator_category _IIteratorCategory;
  1272.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  1273.  
  1274.       return __transform1_switch(__begin, __end, __result, __unary_op,
  1275.                                _IIteratorCategory(), _OIterCategory(),
  1276.                                __parallelism_tag);
  1277.     }
  1278.  
  1279.   template<typename _IIter, typename _OutputIterator,
  1280.            typename _UnaryOperation>
  1281.     inline _OutputIterator
  1282.     transform(_IIter __begin, _IIter __end, _OutputIterator __result,
  1283.               _UnaryOperation __unary_op)
  1284.     {
  1285.       typedef std::iterator_traits<_IIter> _IIterTraits;
  1286.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  1287.       typedef typename _IIterTraits::iterator_category _IIteratorCategory;
  1288.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  1289.  
  1290.       return __transform1_switch(__begin, __end, __result, __unary_op,
  1291.                                _IIteratorCategory(), _OIterCategory());
  1292.     }
  1293.  
  1294.  
  1295.   // Sequential fallback
  1296.   template<typename _IIter1, typename _IIter2,
  1297.            typename _OutputIterator, typename _BinaryOperation>
  1298.     inline _OutputIterator
  1299.     transform(_IIter1 __begin1, _IIter1 __end1,
  1300.               _IIter2 __begin2, _OutputIterator __result,
  1301.               _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
  1302.     { return _GLIBCXX_STD_A::transform(__begin1, __end1,
  1303.                                        __begin2, __result, __binary_op); }
  1304.  
  1305.   // Parallel binary transform for random access iterators.
  1306.   template<typename _RAIter1, typename _RAIter2,
  1307.            typename _RAIter3, typename _BinaryOperation>
  1308.     _RAIter3
  1309.     __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1,
  1310.                       _RAIter2 __begin2,
  1311.                       _RAIter3 __result, _BinaryOperation __binary_op,
  1312.                       random_access_iterator_tag, random_access_iterator_tag,
  1313.                       random_access_iterator_tag,
  1314.                       __gnu_parallel::_Parallelism __parallelism_tag)
  1315.     {
  1316.       if (_GLIBCXX_PARALLEL_CONDITION(
  1317.             (__end1 - __begin1) >=
  1318.                 __gnu_parallel::_Settings::get().transform_minimal_n
  1319.             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  1320.         {
  1321.           bool __dummy = true;
  1322.           typedef __gnu_parallel::_IteratorTriple<_RAIter1,
  1323.             _RAIter2, _RAIter3,
  1324.             random_access_iterator_tag> _ItTrip;
  1325.           _ItTrip __begin_triple(__begin1, __begin2, __result),
  1326.             __end_triple(__end1, __begin2 + (__end1 - __begin1),
  1327.                        __result + (__end1 - __begin1));
  1328.           __gnu_parallel::__transform2_selector<_ItTrip> __functionality;
  1329.           __gnu_parallel::
  1330.             __for_each_template_random_access(__begin_triple, __end_triple,
  1331.                                             __binary_op, __functionality,
  1332.                                             __gnu_parallel::_DummyReduct(),
  1333.                                             __dummy, __dummy, -1,
  1334.                                             __parallelism_tag);
  1335.           return __functionality._M_finish_iterator;
  1336.         }
  1337.       else
  1338.         return transform(__begin1, __end1, __begin2, __result, __binary_op,
  1339.                          __gnu_parallel::sequential_tag());
  1340.     }
  1341.  
  1342.   // Sequential fallback for input iterator case.
  1343.   template<typename _IIter1, typename _IIter2,
  1344.            typename _OutputIterator, typename _BinaryOperation,
  1345.            typename _Tag1, typename _Tag2, typename _Tag3>
  1346.     inline _OutputIterator
  1347.     __transform2_switch(_IIter1 __begin1, _IIter1 __end1,
  1348.                       _IIter2 __begin2, _OutputIterator __result,
  1349.                       _BinaryOperation __binary_op, _Tag1, _Tag2, _Tag3)
  1350.     { return transform(__begin1, __end1, __begin2, __result, __binary_op,
  1351.                        __gnu_parallel::sequential_tag()); }
  1352.  
  1353.   // Public interface.
  1354.   template<typename _IIter1, typename _IIter2,
  1355.            typename _OutputIterator, typename _BinaryOperation>
  1356.     inline _OutputIterator
  1357.     transform(_IIter1 __begin1, _IIter1 __end1,
  1358.               _IIter2 __begin2, _OutputIterator __result,
  1359.               _BinaryOperation __binary_op,
  1360.               __gnu_parallel::_Parallelism __parallelism_tag)
  1361.     {
  1362.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  1363.       typedef typename _IIterTraits1::iterator_category
  1364.         _IIterCategory1;
  1365.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  1366.       typedef typename _IIterTraits2::iterator_category
  1367.         _IIterCategory2;
  1368.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  1369.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  1370.  
  1371.       return __transform2_switch(
  1372.                __begin1, __end1, __begin2, __result, __binary_op,
  1373.                _IIterCategory1(), _IIterCategory2(), _OIterCategory(),
  1374.                __parallelism_tag);
  1375.     }
  1376.  
  1377.   template<typename _IIter1, typename _IIter2,
  1378.            typename _OutputIterator, typename _BinaryOperation>
  1379.     inline _OutputIterator
  1380.     transform(_IIter1 __begin1, _IIter1 __end1,
  1381.               _IIter2 __begin2, _OutputIterator __result,
  1382.               _BinaryOperation __binary_op)
  1383.     {
  1384.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  1385.       typedef typename _IIterTraits1::iterator_category
  1386.         _IIterCategory1;
  1387.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  1388.       typedef typename _IIterTraits2::iterator_category
  1389.         _IIterCategory2;
  1390.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  1391.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  1392.  
  1393.       return __transform2_switch(
  1394.                __begin1, __end1, __begin2, __result, __binary_op,
  1395.                _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  1396.     }
  1397.  
  1398.   // Sequential fallback
  1399.   template<typename _FIterator, typename _Tp>
  1400.     inline void
  1401.     replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
  1402.             const _Tp& __new_value, __gnu_parallel::sequential_tag)
  1403.     { _GLIBCXX_STD_A::replace(__begin, __end, __old_value, __new_value); }
  1404.  
  1405.   // Sequential fallback for input iterator case
  1406.   template<typename _FIterator, typename _Tp, typename _IteratorTag>
  1407.     inline void
  1408.     __replace_switch(_FIterator __begin, _FIterator __end,
  1409.                      const _Tp& __old_value, const _Tp& __new_value,
  1410.                      _IteratorTag)
  1411.     { replace(__begin, __end, __old_value, __new_value,
  1412.               __gnu_parallel::sequential_tag()); }
  1413.  
  1414.   // Parallel replace for random access iterators
  1415.   template<typename _RAIter, typename _Tp>
  1416.     inline void
  1417.     __replace_switch(_RAIter __begin, _RAIter __end,
  1418.                    const _Tp& __old_value, const _Tp& __new_value,
  1419.                    random_access_iterator_tag,
  1420.                    __gnu_parallel::_Parallelism __parallelism_tag)
  1421.     {
  1422.       // XXX parallel version is where?
  1423.       replace(__begin, __end, __old_value, __new_value,
  1424.               __gnu_parallel::sequential_tag());
  1425.     }
  1426.  
  1427.   // Public interface
  1428.   template<typename _FIterator, typename _Tp>
  1429.     inline void
  1430.     replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
  1431.             const _Tp& __new_value,
  1432.             __gnu_parallel::_Parallelism __parallelism_tag)
  1433.     {
  1434.       typedef iterator_traits<_FIterator> _TraitsType;
  1435.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  1436.       __replace_switch(__begin, __end, __old_value, __new_value,
  1437.                        _IteratorCategory(),
  1438.                      __parallelism_tag);
  1439.     }
  1440.  
  1441.   template<typename _FIterator, typename _Tp>
  1442.     inline void
  1443.     replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
  1444.             const _Tp& __new_value)
  1445.     {
  1446.       typedef iterator_traits<_FIterator> _TraitsType;
  1447.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  1448.       __replace_switch(__begin, __end, __old_value, __new_value,
  1449.                        _IteratorCategory());
  1450.     }
  1451.  
  1452.  
  1453.   // Sequential fallback
  1454.   template<typename _FIterator, typename _Predicate, typename _Tp>
  1455.     inline void
  1456.     replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred,
  1457.                const _Tp& __new_value, __gnu_parallel::sequential_tag)
  1458.     { _GLIBCXX_STD_A::replace_if(__begin, __end, __pred, __new_value); }
  1459.  
  1460.   // Sequential fallback for input iterator case
  1461.   template<typename _FIterator, typename _Predicate, typename _Tp,
  1462.            typename _IteratorTag>
  1463.     inline void
  1464.     __replace_if_switch(_FIterator __begin, _FIterator __end,
  1465.                       _Predicate __pred, const _Tp& __new_value, _IteratorTag)
  1466.     { replace_if(__begin, __end, __pred, __new_value,
  1467.                  __gnu_parallel::sequential_tag()); }
  1468.  
  1469.   // Parallel algorithm for random access iterators.
  1470.   template<typename _RAIter, typename _Predicate, typename _Tp>
  1471.     void
  1472.     __replace_if_switch(_RAIter __begin, _RAIter __end,
  1473.                       _Predicate __pred, const _Tp& __new_value,
  1474.                       random_access_iterator_tag,
  1475.                       __gnu_parallel::_Parallelism __parallelism_tag)
  1476.     {
  1477.       if (_GLIBCXX_PARALLEL_CONDITION(
  1478.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1479.             >= __gnu_parallel::_Settings::get().replace_minimal_n
  1480.             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  1481.         {
  1482.           bool __dummy;
  1483.           __gnu_parallel::
  1484.             __replace_if_selector<_RAIter, _Predicate, _Tp>
  1485.             __functionality(__new_value);
  1486.           __gnu_parallel::
  1487.             __for_each_template_random_access(
  1488.               __begin, __end, __pred, __functionality,
  1489.               __gnu_parallel::_DummyReduct(),
  1490.               true, __dummy, -1, __parallelism_tag);
  1491.         }
  1492.       else
  1493.         replace_if(__begin, __end, __pred, __new_value,
  1494.                    __gnu_parallel::sequential_tag());
  1495.     }
  1496.  
  1497.   // Public interface.
  1498.   template<typename _FIterator, typename _Predicate, typename _Tp>
  1499.     inline void
  1500.     replace_if(_FIterator __begin, _FIterator __end,
  1501.                _Predicate __pred, const _Tp& __new_value,
  1502.                __gnu_parallel::_Parallelism __parallelism_tag)
  1503.     {
  1504.       typedef std::iterator_traits<_FIterator> _IteratorTraits;
  1505.       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
  1506.       __replace_if_switch(__begin, __end, __pred, __new_value,
  1507.                           _IteratorCategory(), __parallelism_tag);
  1508.     }
  1509.  
  1510.   template<typename _FIterator, typename _Predicate, typename _Tp>
  1511.     inline void
  1512.     replace_if(_FIterator __begin, _FIterator __end,
  1513.                _Predicate __pred, const _Tp& __new_value)
  1514.     {
  1515.       typedef std::iterator_traits<_FIterator> _IteratorTraits;
  1516.       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
  1517.       __replace_if_switch(__begin, __end, __pred, __new_value,
  1518.                           _IteratorCategory());
  1519.     }
  1520.  
  1521.   // Sequential fallback
  1522.   template<typename _FIterator, typename _Generator>
  1523.     inline void
  1524.     generate(_FIterator __begin, _FIterator __end, _Generator __gen,
  1525.              __gnu_parallel::sequential_tag)
  1526.     { _GLIBCXX_STD_A::generate(__begin, __end, __gen); }
  1527.  
  1528.   // Sequential fallback for input iterator case.
  1529.   template<typename _FIterator, typename _Generator, typename _IteratorTag>
  1530.     inline void
  1531.     __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen,
  1532.                     _IteratorTag)
  1533.     { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); }
  1534.  
  1535.   // Parallel algorithm for random access iterators.
  1536.   template<typename _RAIter, typename _Generator>
  1537.     void
  1538.     __generate_switch(_RAIter __begin, _RAIter __end,
  1539.                     _Generator __gen, random_access_iterator_tag,
  1540.                     __gnu_parallel::_Parallelism __parallelism_tag)
  1541.     {
  1542.       if (_GLIBCXX_PARALLEL_CONDITION(
  1543.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1544.             >= __gnu_parallel::_Settings::get().generate_minimal_n
  1545.             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  1546.         {
  1547.           bool __dummy;
  1548.           __gnu_parallel::__generate_selector<_RAIter>
  1549.             __functionality;
  1550.           __gnu_parallel::
  1551.             __for_each_template_random_access(
  1552.               __begin, __end, __gen, __functionality,
  1553.               __gnu_parallel::_DummyReduct(),
  1554.               true, __dummy, -1, __parallelism_tag);
  1555.         }
  1556.       else
  1557.         generate(__begin, __end, __gen, __gnu_parallel::sequential_tag());
  1558.     }
  1559.  
  1560.   // Public interface.
  1561.   template<typename _FIterator, typename _Generator>
  1562.     inline void
  1563.     generate(_FIterator __begin, _FIterator __end,
  1564.              _Generator __gen, __gnu_parallel::_Parallelism __parallelism_tag)
  1565.     {
  1566.       typedef std::iterator_traits<_FIterator> _IteratorTraits;
  1567.       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
  1568.       __generate_switch(__begin, __end, __gen, _IteratorCategory(),
  1569.                         __parallelism_tag);
  1570.     }
  1571.  
  1572.   template<typename _FIterator, typename _Generator>
  1573.     inline void
  1574.     generate(_FIterator __begin, _FIterator __end, _Generator __gen)
  1575.     {
  1576.       typedef std::iterator_traits<_FIterator> _IteratorTraits;
  1577.       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
  1578.       __generate_switch(__begin, __end, __gen, _IteratorCategory());
  1579.     }
  1580.  
  1581.  
  1582.   // Sequential fallback.
  1583.   template<typename _OutputIterator, typename _Size, typename _Generator>
  1584.     inline _OutputIterator
  1585.     generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
  1586.                __gnu_parallel::sequential_tag)
  1587.     { return _GLIBCXX_STD_A::generate_n(__begin, __n, __gen); }
  1588.  
  1589.   // Sequential fallback for input iterator case.
  1590.   template<typename _OutputIterator, typename _Size, typename _Generator,
  1591.            typename _IteratorTag>
  1592.     inline _OutputIterator
  1593.     __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen,
  1594.                         _IteratorTag)
  1595.     { return generate_n(__begin, __n, __gen,
  1596.                         __gnu_parallel::sequential_tag()); }
  1597.  
  1598.   // Parallel algorithm for random access iterators.
  1599.   template<typename _RAIter, typename _Size, typename _Generator>
  1600.     inline _RAIter
  1601.     __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen,
  1602.                       random_access_iterator_tag,
  1603.                       __gnu_parallel::_Parallelism __parallelism_tag)
  1604.     {
  1605.       // XXX parallel version is where?
  1606.       return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag());
  1607.     }
  1608.  
  1609.   // Public interface.
  1610.   template<typename _OutputIterator, typename _Size, typename _Generator>
  1611.     inline _OutputIterator
  1612.     generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
  1613.                __gnu_parallel::_Parallelism __parallelism_tag)
  1614.     {
  1615.       typedef std::iterator_traits<_OutputIterator> _IteratorTraits;
  1616.       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
  1617.       return __generate_n_switch(__begin, __n, __gen, _IteratorCategory(),
  1618.                                __parallelism_tag);
  1619.     }
  1620.  
  1621.   template<typename _OutputIterator, typename _Size, typename _Generator>
  1622.     inline _OutputIterator
  1623.     generate_n(_OutputIterator __begin, _Size __n, _Generator __gen)
  1624.     {
  1625.       typedef std::iterator_traits<_OutputIterator> _IteratorTraits;
  1626.       typedef typename _IteratorTraits::iterator_category _IteratorCategory;
  1627.       return __generate_n_switch(__begin, __n, __gen, _IteratorCategory());
  1628.     }
  1629.  
  1630.  
  1631.   // Sequential fallback.
  1632.   template<typename _RAIter>
  1633.     inline void
  1634.     random_shuffle(_RAIter __begin, _RAIter __end,
  1635.                    __gnu_parallel::sequential_tag)
  1636.     { _GLIBCXX_STD_A::random_shuffle(__begin, __end); }
  1637.  
  1638.   // Sequential fallback.
  1639.   template<typename _RAIter, typename _RandomNumberGenerator>
  1640.     inline void
  1641.     random_shuffle(_RAIter __begin, _RAIter __end,
  1642.                    _RandomNumberGenerator& __rand,
  1643.                    __gnu_parallel::sequential_tag)
  1644.     { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); }
  1645.  
  1646.  
  1647.   /** @brief Functor wrapper for std::rand(). */
  1648.   template<typename _MustBeInt = int>
  1649.     struct _CRandNumber
  1650.     {
  1651.       int
  1652.       operator()(int __limit)
  1653.       { return rand() % __limit; }
  1654.     };
  1655.  
  1656.   // Fill in random number generator.
  1657.   template<typename _RAIter>
  1658.     inline void
  1659.     random_shuffle(_RAIter __begin, _RAIter __end)
  1660.     {
  1661.       _CRandNumber<> __r;
  1662.       // Parallelization still possible.
  1663.       __gnu_parallel::random_shuffle(__begin, __end, __r);
  1664.     }
  1665.  
  1666.   // Parallel algorithm for random access iterators.
  1667.   template<typename _RAIter, typename _RandomNumberGenerator>
  1668.     void
  1669.     random_shuffle(_RAIter __begin, _RAIter __end,
  1670. #if __cplusplus >= 201103L
  1671.                    _RandomNumberGenerator&& __rand)
  1672. #else
  1673.                    _RandomNumberGenerator& __rand)
  1674. #endif
  1675.     {
  1676.       if (__begin == __end)
  1677.         return;
  1678.       if (_GLIBCXX_PARALLEL_CONDITION(
  1679.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1680.             >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
  1681.         __gnu_parallel::__parallel_random_shuffle(__begin, __end, __rand);
  1682.       else
  1683.         __gnu_parallel::__sequential_random_shuffle(__begin, __end, __rand);
  1684.     }
  1685.  
  1686.   // Sequential fallback.
  1687.   template<typename _FIterator, typename _Predicate>
  1688.     inline _FIterator
  1689.     partition(_FIterator __begin, _FIterator __end,
  1690.               _Predicate __pred, __gnu_parallel::sequential_tag)
  1691.     { return _GLIBCXX_STD_A::partition(__begin, __end, __pred); }
  1692.  
  1693.   // Sequential fallback for input iterator case.
  1694.   template<typename _FIterator, typename _Predicate, typename _IteratorTag>
  1695.     inline _FIterator
  1696.     __partition_switch(_FIterator __begin, _FIterator __end,
  1697.                      _Predicate __pred, _IteratorTag)
  1698.     { return partition(__begin, __end, __pred,
  1699.                        __gnu_parallel::sequential_tag()); }
  1700.  
  1701.   // Parallel algorithm for random access iterators.
  1702.   template<typename _RAIter, typename _Predicate>
  1703.     _RAIter
  1704.     __partition_switch(_RAIter __begin, _RAIter __end,
  1705.                      _Predicate __pred, random_access_iterator_tag)
  1706.     {
  1707.       if (_GLIBCXX_PARALLEL_CONDITION(
  1708.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1709.             >= __gnu_parallel::_Settings::get().partition_minimal_n))
  1710.         {
  1711.           typedef typename std::iterator_traits<_RAIter>::
  1712.             difference_type _DifferenceType;
  1713.           _DifferenceType __middle = __gnu_parallel::
  1714.             __parallel_partition(__begin, __end, __pred,
  1715.                                __gnu_parallel::__get_max_threads());
  1716.           return __begin + __middle;
  1717.         }
  1718.       else
  1719.         return partition(__begin, __end, __pred,
  1720.                          __gnu_parallel::sequential_tag());
  1721.     }
  1722.  
  1723.   // Public interface.
  1724.   template<typename _FIterator, typename _Predicate>
  1725.     inline _FIterator
  1726.     partition(_FIterator __begin, _FIterator __end, _Predicate __pred)
  1727.     {
  1728.       typedef iterator_traits<_FIterator> _TraitsType;
  1729.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  1730.       return __partition_switch(__begin, __end, __pred, _IteratorCategory());
  1731.     }
  1732.  
  1733.   // sort interface
  1734.  
  1735.   // Sequential fallback
  1736.   template<typename _RAIter>
  1737.     inline void
  1738.     sort(_RAIter __begin, _RAIter __end,
  1739.          __gnu_parallel::sequential_tag)
  1740.     { _GLIBCXX_STD_A::sort(__begin, __end); }
  1741.  
  1742.   // Sequential fallback
  1743.   template<typename _RAIter, typename _Compare>
  1744.     inline void
  1745.     sort(_RAIter __begin, _RAIter __end, _Compare __comp,
  1746.          __gnu_parallel::sequential_tag)
  1747.     { _GLIBCXX_STD_A::sort<_RAIter, _Compare>(__begin, __end,
  1748.                                                              __comp); }
  1749.  
  1750.   // Public interface
  1751.   template<typename _RAIter, typename _Compare,
  1752.            typename _Parallelism>
  1753.   void
  1754.   sort(_RAIter __begin, _RAIter __end, _Compare __comp,
  1755.        _Parallelism __parallelism)
  1756.   {
  1757.     typedef iterator_traits<_RAIter> _TraitsType;
  1758.     typedef typename _TraitsType::value_type _ValueType;
  1759.  
  1760.     if (__begin != __end)
  1761.       {
  1762.         if (_GLIBCXX_PARALLEL_CONDITION(
  1763.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
  1764.               __gnu_parallel::_Settings::get().sort_minimal_n))
  1765.           __gnu_parallel::__parallel_sort<false>(
  1766.                             __begin, __end, __comp, __parallelism);
  1767.         else
  1768.           sort(__begin, __end, __comp, __gnu_parallel::sequential_tag());
  1769.       }
  1770.   }
  1771.  
  1772.   // Public interface, insert default comparator
  1773.   template<typename _RAIter>
  1774.     inline void
  1775.     sort(_RAIter __begin, _RAIter __end)
  1776.     {
  1777.       typedef iterator_traits<_RAIter> _TraitsType;
  1778.       typedef typename _TraitsType::value_type _ValueType;
  1779.       sort(__begin, __end, std::less<_ValueType>(),
  1780.            __gnu_parallel::default_parallel_tag());
  1781.     }
  1782.  
  1783.   // Public interface, insert default comparator
  1784.   template<typename _RAIter>
  1785.   inline void
  1786.   sort(_RAIter __begin, _RAIter __end,
  1787.        __gnu_parallel::default_parallel_tag __parallelism)
  1788.   {
  1789.     typedef iterator_traits<_RAIter> _TraitsType;
  1790.     typedef typename _TraitsType::value_type _ValueType;
  1791.     sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1792.   }
  1793.  
  1794.   // Public interface, insert default comparator
  1795.   template<typename _RAIter>
  1796.   inline void
  1797.   sort(_RAIter __begin, _RAIter __end,
  1798.        __gnu_parallel::parallel_tag __parallelism)
  1799.   {
  1800.     typedef iterator_traits<_RAIter> _TraitsType;
  1801.     typedef typename _TraitsType::value_type _ValueType;
  1802.     sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1803.   }
  1804.  
  1805.   // Public interface, insert default comparator
  1806.   template<typename _RAIter>
  1807.   inline void
  1808.   sort(_RAIter __begin, _RAIter __end,
  1809.        __gnu_parallel::multiway_mergesort_tag __parallelism)
  1810.   {
  1811.     typedef iterator_traits<_RAIter> _TraitsType;
  1812.     typedef typename _TraitsType::value_type _ValueType;
  1813.     sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1814.   }
  1815.  
  1816.   // Public interface, insert default comparator
  1817.   template<typename _RAIter>
  1818.   inline void
  1819.   sort(_RAIter __begin, _RAIter __end,
  1820.        __gnu_parallel::multiway_mergesort_sampling_tag __parallelism)
  1821.   {
  1822.     typedef iterator_traits<_RAIter> _TraitsType;
  1823.     typedef typename _TraitsType::value_type _ValueType;
  1824.     sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1825.   }
  1826.  
  1827.   // Public interface, insert default comparator
  1828.   template<typename _RAIter>
  1829.   inline void
  1830.   sort(_RAIter __begin, _RAIter __end,
  1831.        __gnu_parallel::multiway_mergesort_exact_tag __parallelism)
  1832.   {
  1833.     typedef iterator_traits<_RAIter> _TraitsType;
  1834.     typedef typename _TraitsType::value_type _ValueType;
  1835.     sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1836.   }
  1837.  
  1838.   // Public interface, insert default comparator
  1839.   template<typename _RAIter>
  1840.   inline void
  1841.   sort(_RAIter __begin, _RAIter __end,
  1842.        __gnu_parallel::quicksort_tag __parallelism)
  1843.   {
  1844.     typedef iterator_traits<_RAIter> _TraitsType;
  1845.     typedef typename _TraitsType::value_type _ValueType;
  1846.     sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1847.   }
  1848.  
  1849.   // Public interface, insert default comparator
  1850.   template<typename _RAIter>
  1851.   inline void
  1852.   sort(_RAIter __begin, _RAIter __end,
  1853.        __gnu_parallel::balanced_quicksort_tag __parallelism)
  1854.   {
  1855.     typedef iterator_traits<_RAIter> _TraitsType;
  1856.     typedef typename _TraitsType::value_type _ValueType;
  1857.     sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1858.   }
  1859.  
  1860.   // Public interface
  1861.   template<typename _RAIter, typename _Compare>
  1862.     void
  1863.     sort(_RAIter __begin, _RAIter __end, _Compare __comp)
  1864.     {
  1865.       typedef iterator_traits<_RAIter> _TraitsType;
  1866.       typedef typename _TraitsType::value_type _ValueType;
  1867.     sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag());
  1868.   }
  1869.  
  1870.  
  1871.   // stable_sort interface
  1872.  
  1873.  
  1874.   // Sequential fallback
  1875.   template<typename _RAIter>
  1876.   inline void
  1877.   stable_sort(_RAIter __begin, _RAIter __end,
  1878.        __gnu_parallel::sequential_tag)
  1879.   { _GLIBCXX_STD_A::stable_sort(__begin, __end); }
  1880.  
  1881.   // Sequential fallback
  1882.   template<typename _RAIter, typename _Compare>
  1883.   inline void
  1884.   stable_sort(_RAIter __begin, _RAIter __end,
  1885.               _Compare __comp, __gnu_parallel::sequential_tag)
  1886.   { _GLIBCXX_STD_A::stable_sort<_RAIter, _Compare>(
  1887.       __begin, __end, __comp); }
  1888.  
  1889.   // Public interface
  1890.   template<typename _RAIter, typename _Compare,
  1891.            typename _Parallelism>
  1892.   void
  1893.   stable_sort(_RAIter __begin, _RAIter __end,
  1894.               _Compare __comp, _Parallelism __parallelism)
  1895.   {
  1896.     typedef iterator_traits<_RAIter> _TraitsType;
  1897.     typedef typename _TraitsType::value_type _ValueType;
  1898.  
  1899.     if (__begin != __end)
  1900.       {
  1901.         if (_GLIBCXX_PARALLEL_CONDITION(
  1902.               static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
  1903.               __gnu_parallel::_Settings::get().sort_minimal_n))
  1904.           __gnu_parallel::__parallel_sort<true>(
  1905.                             __begin, __end, __comp, __parallelism);
  1906.         else
  1907.           stable_sort(__begin, __end, __comp,
  1908.                       __gnu_parallel::sequential_tag());
  1909.       }
  1910.   }
  1911.  
  1912.   // Public interface, insert default comparator
  1913.   template<typename _RAIter>
  1914.   inline void
  1915.   stable_sort(_RAIter __begin, _RAIter __end)
  1916.   {
  1917.     typedef iterator_traits<_RAIter> _TraitsType;
  1918.     typedef typename _TraitsType::value_type _ValueType;
  1919.     stable_sort(__begin, __end, std::less<_ValueType>(),
  1920.                 __gnu_parallel::default_parallel_tag());
  1921.   }
  1922.  
  1923.   // Public interface, insert default comparator
  1924.   template<typename _RAIter>
  1925.   inline void
  1926.   stable_sort(_RAIter __begin, _RAIter __end,
  1927.               __gnu_parallel::default_parallel_tag __parallelism)
  1928.   {
  1929.     typedef iterator_traits<_RAIter> _TraitsType;
  1930.     typedef typename _TraitsType::value_type _ValueType;
  1931.     stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1932.   }
  1933.  
  1934.   // Public interface, insert default comparator
  1935.   template<typename _RAIter>
  1936.   inline void
  1937.   stable_sort(_RAIter __begin, _RAIter __end,
  1938.               __gnu_parallel::parallel_tag __parallelism)
  1939.   {
  1940.     typedef iterator_traits<_RAIter> _TraitsType;
  1941.     typedef typename _TraitsType::value_type _ValueType;
  1942.     stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1943.   }
  1944.  
  1945.   // Public interface, insert default comparator
  1946.   template<typename _RAIter>
  1947.   inline void
  1948.   stable_sort(_RAIter __begin, _RAIter __end,
  1949.               __gnu_parallel::multiway_mergesort_tag __parallelism)
  1950.   {
  1951.     typedef iterator_traits<_RAIter> _TraitsType;
  1952.     typedef typename _TraitsType::value_type _ValueType;
  1953.     stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1954.   }
  1955.  
  1956.   // Public interface, insert default comparator
  1957.   template<typename _RAIter>
  1958.   inline void
  1959.   stable_sort(_RAIter __begin, _RAIter __end,
  1960.               __gnu_parallel::quicksort_tag __parallelism)
  1961.   {
  1962.     typedef iterator_traits<_RAIter> _TraitsType;
  1963.     typedef typename _TraitsType::value_type _ValueType;
  1964.     stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1965.   }
  1966.  
  1967.   // Public interface, insert default comparator
  1968.   template<typename _RAIter>
  1969.   inline void
  1970.   stable_sort(_RAIter __begin, _RAIter __end,
  1971.               __gnu_parallel::balanced_quicksort_tag __parallelism)
  1972.   {
  1973.     typedef iterator_traits<_RAIter> _TraitsType;
  1974.     typedef typename _TraitsType::value_type _ValueType;
  1975.     stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1976.   }
  1977.  
  1978.   // Public interface
  1979.   template<typename _RAIter, typename _Compare>
  1980.   void
  1981.   stable_sort(_RAIter __begin, _RAIter __end,
  1982.               _Compare __comp)
  1983.   {
  1984.     typedef iterator_traits<_RAIter> _TraitsType;
  1985.     typedef typename _TraitsType::value_type _ValueType;
  1986.     stable_sort(
  1987.       __begin, __end, __comp, __gnu_parallel::default_parallel_tag());
  1988.   }
  1989.  
  1990.   // Sequential fallback
  1991.   template<typename _IIter1, typename _IIter2,
  1992.            typename _OutputIterator>
  1993.     inline _OutputIterator
  1994.     merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  1995.           _IIter2 __end2, _OutputIterator __result,
  1996.           __gnu_parallel::sequential_tag)
  1997.     { return _GLIBCXX_STD_A::merge(
  1998.                __begin1, __end1, __begin2, __end2, __result); }
  1999.  
  2000.   // Sequential fallback
  2001.   template<typename _IIter1, typename _IIter2,
  2002.            typename _OutputIterator, typename _Compare>
  2003.     inline _OutputIterator
  2004.     merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  2005.           _IIter2 __end2, _OutputIterator __result, _Compare __comp,
  2006.           __gnu_parallel::sequential_tag)
  2007.     { return _GLIBCXX_STD_A::merge(
  2008.                 __begin1, __end1, __begin2, __end2, __result, __comp); }
  2009.  
  2010.   // Sequential fallback for input iterator case
  2011.   template<typename _IIter1, typename _IIter2, typename _OutputIterator,
  2012.            typename _Compare, typename _IteratorTag1,
  2013.            typename _IteratorTag2, typename _IteratorTag3>
  2014.     inline _OutputIterator
  2015.     __merge_switch(_IIter1 __begin1, _IIter1 __end1,
  2016.                  _IIter2 __begin2, _IIter2 __end2,
  2017.                  _OutputIterator __result, _Compare __comp,
  2018.                  _IteratorTag1, _IteratorTag2, _IteratorTag3)
  2019.      { return _GLIBCXX_STD_A::merge(__begin1, __end1, __begin2, __end2,
  2020.                                     __result, __comp); }
  2021.  
  2022.   // Parallel algorithm for random access iterators
  2023.   template<typename _IIter1, typename _IIter2,
  2024.            typename _OutputIterator, typename _Compare>
  2025.     _OutputIterator
  2026.     __merge_switch(_IIter1 __begin1, _IIter1 __end1,
  2027.                  _IIter2 __begin2, _IIter2 __end2,
  2028.                  _OutputIterator __result, _Compare __comp,
  2029.                  random_access_iterator_tag, random_access_iterator_tag,
  2030.                  random_access_iterator_tag)
  2031.     {
  2032.       if (_GLIBCXX_PARALLEL_CONDITION(
  2033.             (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  2034.              >= __gnu_parallel::_Settings::get().merge_minimal_n
  2035.              || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
  2036.              >= __gnu_parallel::_Settings::get().merge_minimal_n)))
  2037.         return __gnu_parallel::__parallel_merge_advance(
  2038.                  __begin1, __end1, __begin2, __end2, __result,
  2039.                  (__end1 - __begin1) + (__end2 - __begin2), __comp);
  2040.       else
  2041.         return __gnu_parallel::__merge_advance(
  2042.                  __begin1, __end1, __begin2, __end2, __result,
  2043.                  (__end1 - __begin1) + (__end2 - __begin2), __comp);
  2044.   }
  2045.  
  2046.   // Public interface
  2047.   template<typename _IIter1, typename _IIter2,
  2048.            typename _OutputIterator, typename _Compare>
  2049.     inline _OutputIterator
  2050.     merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  2051.           _IIter2 __end2, _OutputIterator __result, _Compare __comp)
  2052.     {
  2053.       typedef typename iterator_traits<_IIter1>::value_type _ValueType;
  2054.  
  2055.       typedef std::iterator_traits<_IIter1> _IIterTraits1;
  2056.       typedef std::iterator_traits<_IIter2> _IIterTraits2;
  2057.       typedef std::iterator_traits<_OutputIterator> _OIterTraits;
  2058.       typedef typename _IIterTraits1::iterator_category
  2059.         _IIterCategory1;
  2060.       typedef typename _IIterTraits2::iterator_category
  2061.         _IIterCategory2;
  2062.       typedef typename _OIterTraits::iterator_category _OIterCategory;
  2063.  
  2064.       return __merge_switch(
  2065.               __begin1, __end1, __begin2, __end2, __result, __comp,
  2066.               _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  2067.   }
  2068.  
  2069.  
  2070.   // Public interface, insert default comparator
  2071.   template<typename _IIter1, typename _IIter2,
  2072.            typename _OutputIterator>
  2073.     inline _OutputIterator
  2074.     merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  2075.           _IIter2 __end2, _OutputIterator __result)
  2076.     {
  2077.       typedef std::iterator_traits<_IIter1> _Iterator1Traits;
  2078.       typedef std::iterator_traits<_IIter2> _Iterator2Traits;
  2079.       typedef typename _Iterator1Traits::value_type _ValueType1;
  2080.       typedef typename _Iterator2Traits::value_type _ValueType2;
  2081.  
  2082.       return __gnu_parallel::merge(__begin1, __end1, __begin2, __end2,
  2083.                   __result, __gnu_parallel::_Less<_ValueType1, _ValueType2>());
  2084.     }
  2085.  
  2086.   // Sequential fallback
  2087.   template<typename _RAIter>
  2088.     inline void
  2089.     nth_element(_RAIter __begin, _RAIter __nth,
  2090.                 _RAIter __end, __gnu_parallel::sequential_tag)
  2091.     { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end); }
  2092.  
  2093.   // Sequential fallback
  2094.   template<typename _RAIter, typename _Compare>
  2095.     inline void
  2096.     nth_element(_RAIter __begin, _RAIter __nth,
  2097.                 _RAIter __end, _Compare __comp,
  2098.               __gnu_parallel::sequential_tag)
  2099.     { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end, __comp); }
  2100.  
  2101.   // Public interface
  2102.   template<typename _RAIter, typename _Compare>
  2103.     inline void
  2104.     nth_element(_RAIter __begin, _RAIter __nth,
  2105.                 _RAIter __end, _Compare __comp)
  2106.     {
  2107.       if (_GLIBCXX_PARALLEL_CONDITION(
  2108.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  2109.             >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
  2110.         __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp);
  2111.       else
  2112.         nth_element(__begin, __nth, __end, __comp,
  2113.                     __gnu_parallel::sequential_tag());
  2114.     }
  2115.  
  2116.   // Public interface, insert default comparator
  2117.   template<typename _RAIter>
  2118.     inline void
  2119.     nth_element(_RAIter __begin, _RAIter __nth,
  2120.                 _RAIter __end)
  2121.     {
  2122.       typedef iterator_traits<_RAIter> _TraitsType;
  2123.       typedef typename _TraitsType::value_type _ValueType;
  2124.       __gnu_parallel::nth_element(__begin, __nth, __end,
  2125.                                   std::less<_ValueType>());
  2126.     }
  2127.  
  2128.   // Sequential fallback
  2129.   template<typename _RAIter, typename _Compare>
  2130.     inline void
  2131.     partial_sort(_RAIter __begin, _RAIter __middle,
  2132.                  _RAIter __end, _Compare __comp,
  2133.                  __gnu_parallel::sequential_tag)
  2134.     { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end, __comp); }
  2135.  
  2136.   // Sequential fallback
  2137.   template<typename _RAIter>
  2138.     inline void
  2139.     partial_sort(_RAIter __begin, _RAIter __middle,
  2140.                  _RAIter __end, __gnu_parallel::sequential_tag)
  2141.     { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end); }
  2142.  
  2143.   // Public interface, parallel algorithm for random access iterators
  2144.   template<typename _RAIter, typename _Compare>
  2145.     void
  2146.     partial_sort(_RAIter __begin, _RAIter __middle,
  2147.                  _RAIter __end, _Compare __comp)
  2148.     {
  2149.       if (_GLIBCXX_PARALLEL_CONDITION(
  2150.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  2151.             >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
  2152.         __gnu_parallel::
  2153.           __parallel_partial_sort(__begin, __middle, __end, __comp);
  2154.       else
  2155.         partial_sort(__begin, __middle, __end, __comp,
  2156.                      __gnu_parallel::sequential_tag());
  2157.     }
  2158.  
  2159.   // Public interface, insert default comparator
  2160.   template<typename _RAIter>
  2161.     inline void
  2162.     partial_sort(_RAIter __begin, _RAIter __middle,
  2163.                  _RAIter __end)
  2164.     {
  2165.       typedef iterator_traits<_RAIter> _TraitsType;
  2166.       typedef typename _TraitsType::value_type _ValueType;
  2167.       __gnu_parallel::partial_sort(__begin, __middle, __end,
  2168.                                    std::less<_ValueType>());
  2169.     }
  2170.  
  2171.   // Sequential fallback
  2172.   template<typename _FIterator>
  2173.     inline _FIterator
  2174.     max_element(_FIterator __begin, _FIterator __end,
  2175.                 __gnu_parallel::sequential_tag)
  2176.     { return _GLIBCXX_STD_A::max_element(__begin, __end); }
  2177.  
  2178.   // Sequential fallback
  2179.   template<typename _FIterator, typename _Compare>
  2180.     inline _FIterator
  2181.     max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
  2182.                 __gnu_parallel::sequential_tag)
  2183.     { return _GLIBCXX_STD_A::max_element(__begin, __end, __comp); }
  2184.  
  2185.   // Sequential fallback for input iterator case
  2186.   template<typename _FIterator, typename _Compare, typename _IteratorTag>
  2187.     inline _FIterator
  2188.     __max_element_switch(_FIterator __begin, _FIterator __end,
  2189.                        _Compare __comp, _IteratorTag)
  2190.     { return max_element(__begin, __end, __comp,
  2191.                          __gnu_parallel::sequential_tag()); }
  2192.  
  2193.   // Parallel algorithm for random access iterators
  2194.   template<typename _RAIter, typename _Compare>
  2195.     _RAIter
  2196.     __max_element_switch(_RAIter __begin, _RAIter __end,
  2197.                        _Compare __comp, random_access_iterator_tag,
  2198.                          __gnu_parallel::_Parallelism __parallelism_tag)
  2199.     {
  2200.       if (_GLIBCXX_PARALLEL_CONDITION(
  2201.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  2202.             >= __gnu_parallel::_Settings::get().max_element_minimal_n
  2203.             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  2204.         {
  2205.           _RAIter __res(__begin);
  2206.           __gnu_parallel::__identity_selector<_RAIter>
  2207.             __functionality;
  2208.           __gnu_parallel::
  2209.             __for_each_template_random_access(
  2210.               __begin, __end, __gnu_parallel::_Nothing(), __functionality,
  2211.               __gnu_parallel::__max_element_reduct<_Compare, _RAIter>(__comp),
  2212.               __res, __res, -1, __parallelism_tag);
  2213.           return __res;
  2214.         }
  2215.       else
  2216.         return max_element(__begin, __end, __comp,
  2217.                            __gnu_parallel::sequential_tag());
  2218.     }
  2219.  
  2220.   // Public interface, insert default comparator
  2221.   template<typename _FIterator>
  2222.     inline _FIterator
  2223.     max_element(_FIterator __begin, _FIterator __end,
  2224.                 __gnu_parallel::_Parallelism __parallelism_tag)
  2225.     {
  2226.       typedef typename iterator_traits<_FIterator>::value_type _ValueType;
  2227.       return max_element(__begin, __end, std::less<_ValueType>(),
  2228.                          __parallelism_tag);
  2229.     }
  2230.  
  2231.   template<typename _FIterator>
  2232.     inline _FIterator
  2233.     max_element(_FIterator __begin, _FIterator __end)
  2234.     {
  2235.       typedef typename iterator_traits<_FIterator>::value_type _ValueType;
  2236.       return __gnu_parallel::max_element(__begin, __end,
  2237.                                          std::less<_ValueType>());
  2238.     }
  2239.  
  2240.   // Public interface
  2241.   template<typename _FIterator, typename _Compare>
  2242.     inline _FIterator
  2243.     max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
  2244.                 __gnu_parallel::_Parallelism __parallelism_tag)
  2245.     {
  2246.       typedef iterator_traits<_FIterator> _TraitsType;
  2247.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  2248.       return __max_element_switch(__begin, __end, __comp, _IteratorCategory(),
  2249.                                   __parallelism_tag);
  2250.     }
  2251.  
  2252.   template<typename _FIterator, typename _Compare>
  2253.     inline _FIterator
  2254.     max_element(_FIterator __begin, _FIterator __end, _Compare __comp)
  2255.     {
  2256.       typedef iterator_traits<_FIterator> _TraitsType;
  2257.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  2258.       return __max_element_switch(__begin, __end, __comp, _IteratorCategory());
  2259.     }
  2260.  
  2261.  
  2262.   // Sequential fallback
  2263.   template<typename _FIterator>
  2264.     inline _FIterator
  2265.     min_element(_FIterator __begin, _FIterator __end,
  2266.                 __gnu_parallel::sequential_tag)
  2267.     { return _GLIBCXX_STD_A::min_element(__begin, __end); }
  2268.  
  2269.   // Sequential fallback
  2270.   template<typename _FIterator, typename _Compare>
  2271.     inline _FIterator
  2272.     min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
  2273.                 __gnu_parallel::sequential_tag)
  2274.     { return _GLIBCXX_STD_A::min_element(__begin, __end, __comp); }
  2275.  
  2276.   // Sequential fallback for input iterator case
  2277.   template<typename _FIterator, typename _Compare, typename _IteratorTag>
  2278.     inline _FIterator
  2279.     __min_element_switch(_FIterator __begin, _FIterator __end,
  2280.                        _Compare __comp, _IteratorTag)
  2281.     { return min_element(__begin, __end, __comp,
  2282.                          __gnu_parallel::sequential_tag()); }
  2283.  
  2284.   // Parallel algorithm for random access iterators
  2285.   template<typename _RAIter, typename _Compare>
  2286.     _RAIter
  2287.     __min_element_switch(_RAIter __begin, _RAIter __end,
  2288.                        _Compare __comp, random_access_iterator_tag,
  2289.                        __gnu_parallel::_Parallelism __parallelism_tag)
  2290.     {
  2291.       if (_GLIBCXX_PARALLEL_CONDITION(
  2292.             static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  2293.             >= __gnu_parallel::_Settings::get().min_element_minimal_n
  2294.             && __gnu_parallel::__is_parallel(__parallelism_tag)))
  2295.         {
  2296.           _RAIter __res(__begin);
  2297.           __gnu_parallel::__identity_selector<_RAIter>
  2298.             __functionality;
  2299.           __gnu_parallel::
  2300.             __for_each_template_random_access(
  2301.               __begin, __end, __gnu_parallel::_Nothing(), __functionality,
  2302.               __gnu_parallel::__min_element_reduct<_Compare, _RAIter>(__comp),
  2303.               __res, __res, -1, __parallelism_tag);
  2304.           return __res;
  2305.         }
  2306.       else
  2307.         return min_element(__begin, __end, __comp,
  2308.                            __gnu_parallel::sequential_tag());
  2309.     }
  2310.  
  2311.   // Public interface, insert default comparator
  2312.   template<typename _FIterator>
  2313.     inline _FIterator
  2314.     min_element(_FIterator __begin, _FIterator __end,
  2315.                 __gnu_parallel::_Parallelism __parallelism_tag)
  2316.     {
  2317.       typedef typename iterator_traits<_FIterator>::value_type _ValueType;
  2318.       return min_element(__begin, __end, std::less<_ValueType>(),
  2319.                          __parallelism_tag);
  2320.     }
  2321.  
  2322.   template<typename _FIterator>
  2323.     inline _FIterator
  2324.     min_element(_FIterator __begin, _FIterator __end)
  2325.     {
  2326.       typedef typename iterator_traits<_FIterator>::value_type _ValueType;
  2327.       return __gnu_parallel::min_element(__begin, __end,
  2328.                                          std::less<_ValueType>());
  2329.     }
  2330.  
  2331.   // Public interface
  2332.   template<typename _FIterator, typename _Compare>
  2333.     inline _FIterator
  2334.     min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
  2335.                 __gnu_parallel::_Parallelism __parallelism_tag)
  2336.     {
  2337.       typedef iterator_traits<_FIterator> _TraitsType;
  2338.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  2339.       return __min_element_switch(__begin, __end, __comp, _IteratorCategory(),
  2340.                                 __parallelism_tag);
  2341.     }
  2342.  
  2343.   template<typename _FIterator, typename _Compare>
  2344.     inline _FIterator
  2345.     min_element(_FIterator __begin, _FIterator __end, _Compare __comp)
  2346.     {
  2347.       typedef iterator_traits<_FIterator> _TraitsType;
  2348.       typedef typename _TraitsType::iterator_category _IteratorCategory;
  2349.       return __min_element_switch(__begin, __end, __comp, _IteratorCategory());
  2350.     }
  2351. } // end namespace
  2352. } // end namespace
  2353.  
  2354. #endif /* _GLIBCXX_PARALLEL_ALGO_H */
  2355.