Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

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