// -*- C++ -*-

// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file parallel/algo.h
 *  @brief Parallel STL function calls corresponding to the stl_algo.h header.
 *
 *  The functions defined here mainly do case switches and
 *  call the actual parallelized versions in other files.
 *  Inlining policy: Functions that basically only contain one function call,
 *  are declared inline.
 *  This file is a GNU parallel extension to the Standard C++ Library.
 */

// Written by Johannes Singler and Felix Putze.

#ifndef _GLIBCXX_PARALLEL_ALGO_H
#define _GLIBCXX_PARALLEL_ALGO_H 1

#include <parallel/algorithmfwd.h>
#include <bits/stl_algobase.h>
#include <bits/stl_algo.h>
#include <parallel/iterator.h>
#include <parallel/base.h>
#include <parallel/sort.h>
#include <parallel/workstealing.h>
#include <parallel/par_loop.h>
#include <parallel/omp_loop.h>
#include <parallel/omp_loop_static.h>
#include <parallel/for_each_selectors.h>
#include <parallel/for_each.h>
#include <parallel/find.h>
#include <parallel/find_selectors.h>
#include <parallel/search.h>
#include <parallel/random_shuffle.h>
#include <parallel/partition.h>
#include <parallel/merge.h>
#include <parallel/unique_copy.h>
#include <parallel/set_operations.h>

namespace std
{
namespace __parallel
{
  // Sequential fallback
  template<typename _IIter, typename _Function>
    inline _Function
    for_each(_IIter __begin, _IIter __end, _Function __f, 
             __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::for_each(__begin, __end, __f); }


  // Sequential fallback for input iterator case
  template<typename _IIter, typename _Function, typename _IteratorTag>
    inline _Function
    __for_each_switch(_IIter __begin, _IIter __end, _Function __f, 
                    _IteratorTag)
    { return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag()); }

  // Parallel algorithm for random access iterators
  template<typename _RAIter, typename _Function>
    _Function
    __for_each_switch(_RAIter __begin, _RAIter __end, 
                    _Function __f, random_access_iterator_tag, 
                    __gnu_parallel::_Parallelism __parallelism_tag
                    = __gnu_parallel::parallel_balanced)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().for_each_minimal_n
            && __gnu_parallel::__is_parallel(__parallelism_tag)))
        {
          bool __dummy;
    __gnu_parallel::__for_each_selector<_RAIter> __functionality;

          return __gnu_parallel::
            __for_each_template_random_access(
              __begin, __end, __f, __functionality,
              __gnu_parallel::_DummyReduct(), true, __dummy, -1,
              __parallelism_tag);
        }
      else
        return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag());
    }

  // Public interface
  template<typename _Iterator, typename _Function>
    inline _Function
    for_each(_Iterator __begin, _Iterator __end, _Function __f, 
             __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef std::iterator_traits<_Iterator> _IteratorTraits;
      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
      return __for_each_switch(__begin, __end, __f, _IteratorCategory(), 
                             __parallelism_tag);
    }

  template<typename _Iterator, typename _Function>
    inline _Function
    for_each(_Iterator __begin, _Iterator __end, _Function __f) 
    {
      typedef std::iterator_traits<_Iterator> _IteratorTraits;
      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
      return __for_each_switch(__begin, __end, __f, _IteratorCategory());
    }


  // Sequential fallback
  template<typename _IIter, typename _Tp>
    inline _IIter
    find(_IIter __begin, _IIter __end, const _Tp& __val, 
         __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::find(__begin, __end, __val); }

  // Sequential fallback for input iterator case
  template<typename _IIter, typename _Tp, typename _IteratorTag>
    inline _IIter
    __find_switch(_IIter __begin, _IIter __end, const _Tp& __val,
                _IteratorTag)
    { return _GLIBCXX_STD_P::find(__begin, __end, __val); }

  // Parallel find for random access iterators
  template<typename _RAIter, typename _Tp>
    _RAIter
    __find_switch(_RAIter __begin, _RAIter __end,
                const _Tp& __val, random_access_iterator_tag)
    {
      typedef iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;

      if (_GLIBCXX_PARALLEL_CONDITION(true))
        {
	  std::binder2nd<__gnu_parallel::_EqualTo<_ValueType, const _Tp&> >
            __comp(__gnu_parallel::_EqualTo<_ValueType, const _Tp&>(), __val);
          return __gnu_parallel::__find_template(
                   __begin, __end, __begin, __comp,
                   __gnu_parallel::__find_if_selector()).first;
        }
      else
        return _GLIBCXX_STD_P::find(__begin, __end, __val);
    }

  // Public interface
  template<typename _IIter, typename _Tp>
    inline _IIter
    find(_IIter __begin, _IIter __end, const _Tp& __val)
    {
      typedef std::iterator_traits<_IIter> _IteratorTraits;
      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
      return __find_switch(__begin, __end, __val, _IteratorCategory());
    }

  // Sequential fallback
  template<typename _IIter, typename _Predicate>
    inline _IIter
    find_if(_IIter __begin, _IIter __end, _Predicate __pred, 
            __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::find_if(__begin, __end, __pred); }

  // Sequential fallback for input iterator case
  template<typename _IIter, typename _Predicate, typename _IteratorTag>
    inline _IIter
    __find_if_switch(_IIter __begin, _IIter __end, _Predicate __pred, 
                   _IteratorTag)
    { return _GLIBCXX_STD_P::find_if(__begin, __end, __pred); }

  // Parallel find_if for random access iterators
  template<typename _RAIter, typename _Predicate>
    _RAIter
    __find_if_switch(_RAIter __begin, _RAIter __end, 
                   _Predicate __pred, random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(true))
        return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
                                             __gnu_parallel::
                                             __find_if_selector()).first;
      else
        return _GLIBCXX_STD_P::find_if(__begin, __end, __pred);
    }

  // Public interface
  template<typename _IIter, typename _Predicate>
    inline _IIter
    find_if(_IIter __begin, _IIter __end, _Predicate __pred)
    {
      typedef std::iterator_traits<_IIter> _IteratorTraits;
      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
      return __find_if_switch(__begin, __end, __pred, _IteratorCategory());
    }

  // Sequential fallback
  template<typename _IIter, typename _FIterator>
    inline _IIter
    find_first_of(_IIter __begin1, _IIter __end1, 
                  _FIterator __begin2, _FIterator __end2, 
                  __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::find_first_of(__begin1, __end1, __begin2, __end2);
      }

  // Sequential fallback
  template<typename _IIter, typename _FIterator,
           typename _BinaryPredicate>
    inline _IIter
    find_first_of(_IIter __begin1, _IIter __end1,
                  _FIterator __begin2, _FIterator __end2,
                  _BinaryPredicate __comp, __gnu_parallel::sequential_tag)
  { return _GLIBCXX_STD_P::find_first_of(
             __begin1, __end1, __begin2, __end2, __comp); }

  // Sequential fallback for input iterator type
  template<typename _IIter, typename _FIterator,
           typename _IteratorTag1, typename _IteratorTag2>
    inline _IIter
    __find_first_of_switch(_IIter __begin1, _IIter __end1,
                         _FIterator __begin2, _FIterator __end2, 
                         _IteratorTag1, _IteratorTag2)
    { return find_first_of(__begin1, __end1, __begin2, __end2, 
                           __gnu_parallel::sequential_tag()); }

  // Parallel algorithm for random access iterators
  template<typename _RAIter, typename _FIterator,
           typename _BinaryPredicate, typename _IteratorTag>
    inline _RAIter
    __find_first_of_switch(_RAIter __begin1,
                         _RAIter __end1,
                         _FIterator __begin2, _FIterator __end2, 
                         _BinaryPredicate __comp, random_access_iterator_tag, 
                         _IteratorTag)
    {
      return __gnu_parallel::
        __find_template(__begin1, __end1, __begin1, __comp,
                      __gnu_parallel::__find_first_of_selector
                      <_FIterator>(__begin2, __end2)).first;
    }

  // Sequential fallback for input iterator type
  template<typename _IIter, typename _FIterator,
           typename _BinaryPredicate, typename _IteratorTag1,
           typename _IteratorTag2>
    inline _IIter
    __find_first_of_switch(_IIter __begin1, _IIter __end1,
                         _FIterator __begin2, _FIterator __end2, 
                         _BinaryPredicate __comp, _IteratorTag1, _IteratorTag2)
    { return find_first_of(__begin1, __end1, __begin2, __end2, __comp, 
                           __gnu_parallel::sequential_tag()); }

  // Public interface
  template<typename _IIter, typename _FIterator,
           typename _BinaryPredicate>
    inline _IIter
    find_first_of(_IIter __begin1, _IIter __end1,
                  _FIterator __begin2, _FIterator __end2, 
                  _BinaryPredicate __comp)
    {
      typedef std::iterator_traits<_IIter> _IIterTraits;
      typedef std::iterator_traits<_FIterator> iteratorf_traits;
      typedef typename _IIterTraits::iterator_category _IIteratorCategory;
      typedef typename iteratorf_traits::iterator_category iteratorf_category;

      return __find_first_of_switch(__begin1, __end1, __begin2, __end2, __comp,
                                  _IIteratorCategory(), iteratorf_category());
    }

  // Public interface, insert default comparator
  template<typename _IIter, typename _FIterator>
    inline _IIter
    find_first_of(_IIter __begin1, _IIter __end1, 
                  _FIterator __begin2, _FIterator __end2)
    {
      typedef std::iterator_traits<_IIter> _IIterTraits;
      typedef std::iterator_traits<_FIterator> iteratorf_traits;
      typedef typename _IIterTraits::value_type _IValueType;
      typedef typename iteratorf_traits::value_type _FValueType;

      return __gnu_parallel::find_first_of(__begin1, __end1, __begin2, __end2,
                         __gnu_parallel::_EqualTo<_IValueType, _FValueType>());
    }

  // Sequential fallback
  template<typename _IIter, typename _OutputIterator>
    inline _OutputIterator
    unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
                __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::unique_copy(__begin1, __end1, __out); }

  // Sequential fallback
  template<typename _IIter, typename _OutputIterator,
           typename _Predicate>
    inline _OutputIterator
    unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
                _Predicate __pred, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::unique_copy(__begin1, __end1, __out, __pred); }

  // Sequential fallback for input iterator case
  template<typename _IIter, typename _OutputIterator,
           typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
    inline _OutputIterator
    __unique_copy_switch(_IIter __begin, _IIter __last, 
                       _OutputIterator __out, _Predicate __pred, 
                       _IteratorTag1, _IteratorTag2)
    { return _GLIBCXX_STD_P::unique_copy(__begin, __last, __out, __pred); }

  // Parallel unique_copy for random access iterators
  template<typename _RAIter, typename RandomAccessOutputIterator,
           typename _Predicate>
    RandomAccessOutputIterator
    __unique_copy_switch(_RAIter __begin, _RAIter __last, 
                       RandomAccessOutputIterator __out, _Predicate __pred, 
                       random_access_iterator_tag, random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__last - __begin)
            > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
        return __gnu_parallel::__parallel_unique_copy(
                 __begin, __last, __out, __pred);
      else
        return _GLIBCXX_STD_P::unique_copy(__begin, __last, __out, __pred);
    }

  // Public interface
  template<typename _IIter, typename _OutputIterator>
    inline _OutputIterator
    unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out)
    {
      typedef std::iterator_traits<_IIter> _IIterTraits;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits::iterator_category _IIteratorCategory;
      typedef typename _IIterTraits::value_type _ValueType;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __unique_copy_switch(
               __begin1, __end1, __out, equal_to<_ValueType>(),
               _IIteratorCategory(), _OIterCategory());
    }

  // Public interface
  template<typename _IIter, typename _OutputIterator, typename _Predicate>
    inline _OutputIterator
    unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
                _Predicate __pred)
    {
      typedef std::iterator_traits<_IIter> _IIterTraits;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits::iterator_category _IIteratorCategory;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __unique_copy_switch(
               __begin1, __end1, __out, __pred,
               _IIteratorCategory(), _OIterCategory());
    }

  // Sequential fallback
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator>
    inline _OutputIterator
    set_union(_IIter1 __begin1, _IIter1 __end1,
              _IIter2 __begin2, _IIter2 __end2,
              _OutputIterator __out, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::set_union(
               __begin1, __end1, __begin2, __end2, __out); }

  // Sequential fallback
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Predicate>
    inline _OutputIterator
    set_union(_IIter1 __begin1, _IIter1 __end1,
              _IIter2 __begin2, _IIter2 __end2,
              _OutputIterator __out, _Predicate __pred,
              __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::set_union(__begin1, __end1,
                                       __begin2, __end2, __out, __pred); }

  // Sequential fallback for input iterator case
  template<typename _IIter1, typename _IIter2, typename _Predicate,
           typename _OutputIterator, typename _IteratorTag1,
           typename _IteratorTag2, typename _IteratorTag3>
    inline _OutputIterator
    __set_union_switch(
      _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
      _OutputIterator __result, _Predicate __pred,
      _IteratorTag1, _IteratorTag2, _IteratorTag3)
    { return _GLIBCXX_STD_P::set_union(__begin1, __end1,
                                       __begin2, __end2, __result, __pred); }

  // Parallel set_union for random access iterators
  template<typename _RAIter1, typename _RAIter2,
           typename _Output_RAIter, typename _Predicate>
    _Output_RAIter
    __set_union_switch(_RAIter1 __begin1, _RAIter1 __end1, 
                     _RAIter2 __begin2, _RAIter2 __end2, 
                     _Output_RAIter __result, _Predicate __pred,
                     random_access_iterator_tag, random_access_iterator_tag, 
                     random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
            >= __gnu_parallel::_Settings::get().set_union_minimal_n
            || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
            >= __gnu_parallel::_Settings::get().set_union_minimal_n))
        return __gnu_parallel::__parallel_set_union(
                 __begin1, __end1, __begin2, __end2, __result, __pred);
      else
        return _GLIBCXX_STD_P::set_union(__begin1, __end1,
                                         __begin2, __end2, __result, __pred);
    }

  // Public interface
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator>
    inline _OutputIterator 
    set_union(_IIter1 __begin1, _IIter1 __end1,
              _IIter2 __begin2, _IIter2 __end2, _OutputIterator __out)
    {
      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef typename _OIterTraits::iterator_category _OIterCategory;
      typedef typename _IIterTraits1::value_type _ValueType1;
      typedef typename _IIterTraits2::value_type _ValueType2;

      return __set_union_switch(
               __begin1, __end1, __begin2, __end2, __out,
               __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
               _IIterCategory1(), _IIterCategory2(), _OIterCategory());
    }

  // Public interface
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Predicate>
    inline _OutputIterator 
    set_union(_IIter1 __begin1, _IIter1 __end1,
              _IIter2 __begin2, _IIter2 __end2,
              _OutputIterator __out, _Predicate __pred)
    {
      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __set_union_switch(
               __begin1, __end1, __begin2, __end2, __out, __pred,
               _IIterCategory1(), _IIterCategory2(), _OIterCategory());
    }

  // Sequential fallback.
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator>
    inline _OutputIterator
    set_intersection(_IIter1 __begin1, _IIter1 __end1,
                     _IIter2 __begin2, _IIter2 __end2,
                     _OutputIterator __out, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::set_intersection(__begin1, __end1,
                                              __begin2, __end2, __out); }

  // Sequential fallback.
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Predicate>
    inline _OutputIterator
    set_intersection(_IIter1 __begin1, _IIter1 __end1,
                     _IIter2 __begin2, _IIter2 __end2,
                     _OutputIterator __out, _Predicate __pred, 
                     __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::set_intersection(
               __begin1, __end1, __begin2, __end2, __out, __pred); }

  // Sequential fallback for input iterator case
  template<typename _IIter1, typename _IIter2,
           typename _Predicate, typename _OutputIterator,
           typename _IteratorTag1, typename _IteratorTag2,
           typename _IteratorTag3>
    inline _OutputIterator 
    __set_intersection_switch(_IIter1 __begin1, _IIter1 __end1,
                              _IIter2 __begin2, _IIter2 __end2,
                              _OutputIterator __result, _Predicate __pred,
                              _IteratorTag1, _IteratorTag2, _IteratorTag3)
    { return _GLIBCXX_STD_P::set_intersection(__begin1, __end1, __begin2,
                                              __end2, __result, __pred); }

  // Parallel set_intersection for random access iterators
  template<typename _RAIter1, typename _RAIter2,
           typename _Output_RAIter, typename _Predicate>
    _Output_RAIter
    __set_intersection_switch(_RAIter1 __begin1,
                            _RAIter1 __end1,
                            _RAIter2 __begin2,
                            _RAIter2 __end2,
                            _Output_RAIter __result,
                            _Predicate __pred,
                            random_access_iterator_tag,
                            random_access_iterator_tag,
                            random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
            >= __gnu_parallel::_Settings::get().set_union_minimal_n
            || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
            >= __gnu_parallel::_Settings::get().set_union_minimal_n))
        return __gnu_parallel::__parallel_set_intersection(
                 __begin1, __end1, __begin2, __end2, __result, __pred);
      else
        return _GLIBCXX_STD_P::set_intersection(
                 __begin1, __end1, __begin2, __end2, __result, __pred);
    }

  // Public interface
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator>
    inline _OutputIterator 
    set_intersection(_IIter1 __begin1, _IIter1 __end1, 
                     _IIter2 __begin2, _IIter2 __end2, 
                     _OutputIterator __out)
    {
      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef typename _OIterTraits::iterator_category _OIterCategory;
      typedef typename _IIterTraits1::value_type _ValueType1;
      typedef typename _IIterTraits2::value_type _ValueType2;

      return __set_intersection_switch(
               __begin1, __end1, __begin2, __end2, __out,
               __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
               _IIterCategory1(), _IIterCategory2(), _OIterCategory());
    }

  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Predicate>
    inline _OutputIterator 
    set_intersection(_IIter1 __begin1, _IIter1 __end1,
                     _IIter2 __begin2, _IIter2 __end2,
                     _OutputIterator __out, _Predicate __pred)
    {
      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __set_intersection_switch(
               __begin1, __end1, __begin2, __end2, __out, __pred,
               _IIterCategory1(), _IIterCategory2(), _OIterCategory());
    }

  // Sequential fallback
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator>
    inline _OutputIterator
    set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
                             _IIter2 __begin2, _IIter2 __end2,
                             _OutputIterator __out,
                             __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::set_symmetric_difference(
               __begin1, __end1, __begin2, __end2, __out); }

  // Sequential fallback
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Predicate>
    inline _OutputIterator
    set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
                             _IIter2 __begin2, _IIter2 __end2,
                             _OutputIterator __out, _Predicate __pred,
                             __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::set_symmetric_difference(
               __begin1, __end1, __begin2, __end2, __out, __pred); }

  // Sequential fallback for input iterator case
  template<typename _IIter1, typename _IIter2,
           typename _Predicate, typename _OutputIterator,
           typename _IteratorTag1, typename _IteratorTag2,
           typename _IteratorTag3>
    inline _OutputIterator 
    __set_symmetric_difference_switch(
      _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
      _OutputIterator __result, _Predicate __pred,
      _IteratorTag1, _IteratorTag2, _IteratorTag3)
    { return _GLIBCXX_STD_P::set_symmetric_difference(
               __begin1, __end1, __begin2, __end2, __result, __pred); }

  // Parallel set_symmetric_difference for random access iterators
  template<typename _RAIter1, typename _RAIter2,
           typename _Output_RAIter, typename _Predicate>
    _Output_RAIter
    __set_symmetric_difference_switch(_RAIter1 __begin1,
                                    _RAIter1 __end1,
                                    _RAIter2 __begin2,
                                    _RAIter2 __end2,
                                    _Output_RAIter __result,
                                    _Predicate __pred,
                                    random_access_iterator_tag,
                                    random_access_iterator_tag,
                                    random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
      static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
      >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
      || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
      >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n))
  return __gnu_parallel::__parallel_set_symmetric_difference(
           __begin1, __end1, __begin2, __end2, __result, __pred);
      else
        return _GLIBCXX_STD_P::set_symmetric_difference(
                 __begin1, __end1, __begin2, __end2, __result, __pred);
    }

  // Public interface.
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator>
    inline _OutputIterator 
    set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
                             _IIter2 __begin2, _IIter2 __end2,
                             _OutputIterator __out)
    {
      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef typename _OIterTraits::iterator_category _OIterCategory;
      typedef typename _IIterTraits1::value_type _ValueType1;
      typedef typename _IIterTraits2::value_type _ValueType2;

      return __set_symmetric_difference_switch(
               __begin1, __end1, __begin2, __end2, __out,
               __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
               _IIterCategory1(), _IIterCategory2(), _OIterCategory());
    }

  // Public interface.
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Predicate>
    inline _OutputIterator 
    set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
                             _IIter2 __begin2, _IIter2 __end2,
                             _OutputIterator __out, _Predicate __pred)
    {
      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __set_symmetric_difference_switch(
               __begin1, __end1, __begin2, __end2, __out, __pred,
               _IIterCategory1(), _IIterCategory2(), _OIterCategory());
    }

  // Sequential fallback.
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator>
    inline _OutputIterator
    set_difference(_IIter1 __begin1, _IIter1 __end1, 
                   _IIter2 __begin2, _IIter2 __end2, 
                   _OutputIterator __out, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::set_difference(
               __begin1,__end1, __begin2, __end2, __out); }

  // Sequential fallback.
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Predicate>
    inline _OutputIterator
    set_difference(_IIter1 __begin1, _IIter1 __end1, 
                   _IIter2 __begin2, _IIter2 __end2, 
                   _OutputIterator __out, _Predicate __pred, 
                   __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::set_difference(__begin1, __end1,
                                            __begin2, __end2, __out, __pred); }

  // Sequential fallback for input iterator case.
  template<typename _IIter1, typename _IIter2, typename _Predicate,
           typename _OutputIterator, typename _IteratorTag1,
           typename _IteratorTag2, typename _IteratorTag3>
    inline _OutputIterator
    __set_difference_switch(_IIter1 __begin1, _IIter1 __end1, 
                          _IIter2 __begin2, _IIter2 __end2, 
                          _OutputIterator __result, _Predicate __pred, 
                          _IteratorTag1, _IteratorTag2, _IteratorTag3)
    { return _GLIBCXX_STD_P::set_difference(
               __begin1, __end1, __begin2, __end2, __result, __pred); }

  // Parallel set_difference for random access iterators
  template<typename _RAIter1, typename _RAIter2,
           typename _Output_RAIter, typename _Predicate>
    _Output_RAIter
    __set_difference_switch(_RAIter1 __begin1,
                          _RAIter1 __end1,
                          _RAIter2 __begin2,
                          _RAIter2 __end2,
                          _Output_RAIter __result, _Predicate __pred,
                          random_access_iterator_tag,
                          random_access_iterator_tag,
                          random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
            >= __gnu_parallel::_Settings::get().set_difference_minimal_n
            || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
            >= __gnu_parallel::_Settings::get().set_difference_minimal_n))
        return __gnu_parallel::__parallel_set_difference(
                 __begin1, __end1, __begin2, __end2, __result, __pred);
      else
        return _GLIBCXX_STD_P::set_difference(
                 __begin1, __end1, __begin2, __end2, __result, __pred);
    }

  // Public interface
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator>
    inline _OutputIterator
    set_difference(_IIter1 __begin1, _IIter1 __end1, 
                   _IIter2 __begin2, _IIter2 __end2, 
                   _OutputIterator __out)
    {
      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef typename _OIterTraits::iterator_category _OIterCategory;
      typedef typename _IIterTraits1::value_type _ValueType1;
      typedef typename _IIterTraits2::value_type _ValueType2;

      return __set_difference_switch(
               __begin1, __end1, __begin2, __end2, __out,
               __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
               _IIterCategory1(), _IIterCategory2(), _OIterCategory());
    }

  // Public interface
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Predicate>
    inline _OutputIterator
    set_difference(_IIter1 __begin1, _IIter1 __end1, 
                   _IIter2 __begin2, _IIter2 __end2, 
                   _OutputIterator __out, _Predicate __pred)
    {
      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __set_difference_switch(
               __begin1, __end1, __begin2, __end2, __out, __pred,
               _IIterCategory1(), _IIterCategory2(), _OIterCategory());
    }

  // Sequential fallback
  template<typename _FIterator>
    inline _FIterator
    adjacent_find(_FIterator __begin, _FIterator __end, 
                  __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::adjacent_find(__begin, __end); }

  // Sequential fallback
  template<typename _FIterator, typename _BinaryPredicate>
    inline _FIterator
    adjacent_find(_FIterator __begin, _FIterator __end, 
                  _BinaryPredicate __binary_pred,
                  __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::adjacent_find(__begin, __end, __binary_pred); }

  // Parallel algorithm for random access iterators
  template<typename _RAIter>
    _RAIter
    __adjacent_find_switch(_RAIter __begin, _RAIter __end, 
                         random_access_iterator_tag)
    {
      typedef iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;

      if (_GLIBCXX_PARALLEL_CONDITION(true))
        {
          _RAIter __spot = __gnu_parallel::
              __find_template(
                __begin, __end - 1, __begin, equal_to<_ValueType>(),
                __gnu_parallel::__adjacent_find_selector())
            .first;
          if (__spot == (__end - 1))
            return __end;
          else
            return __spot;
        }
      else
        return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag());
    }

  // Sequential fallback for input iterator case
  template<typename _FIterator, typename _IteratorTag>
    inline _FIterator
    __adjacent_find_switch(_FIterator __begin, _FIterator __end,
                         _IteratorTag)
    { return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag()); }

  // Public interface
  template<typename _FIterator>
    inline _FIterator
    adjacent_find(_FIterator __begin, _FIterator __end)
    {
      typedef iterator_traits<_FIterator> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __adjacent_find_switch(__begin, __end, _IteratorCategory());
    }

  // Sequential fallback for input iterator case
  template<typename _FIterator, typename _BinaryPredicate,
           typename _IteratorTag>
    inline _FIterator
    __adjacent_find_switch(_FIterator __begin, _FIterator __end, 
                         _BinaryPredicate __pred, _IteratorTag)
    { return adjacent_find(__begin, __end, __pred,
                           __gnu_parallel::sequential_tag()); }

  // Parallel algorithm for random access iterators
  template<typename _RAIter, typename _BinaryPredicate>
    _RAIter
    __adjacent_find_switch(_RAIter __begin, _RAIter __end, 
                         _BinaryPredicate __pred, random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(true))
        return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
                                             __gnu_parallel::
                                             __adjacent_find_selector()).first;
      else
        return adjacent_find(__begin, __end, __pred,
                             __gnu_parallel::sequential_tag());
    }

  // Public interface
  template<typename _FIterator, typename _BinaryPredicate>
    inline _FIterator
    adjacent_find(_FIterator __begin, _FIterator __end, 
                  _BinaryPredicate __pred)
    {
      typedef iterator_traits<_FIterator> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __adjacent_find_switch(__begin, __end, __pred,
                                    _IteratorCategory());
    }

  // Sequential fallback
  template<typename _IIter, typename _Tp>
    inline typename iterator_traits<_IIter>::difference_type
    count(_IIter __begin, _IIter __end, const _Tp& __value, 
          __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::count(__begin, __end, __value); }

  // Parallel code for random access iterators
  template<typename _RAIter, typename _Tp>
    typename iterator_traits<_RAIter>::difference_type
    __count_switch(_RAIter __begin, _RAIter __end, 
                 const _Tp& __value, random_access_iterator_tag, 
                 __gnu_parallel::_Parallelism __parallelism_tag 
                 = __gnu_parallel::parallel_unbalanced)
    {
      typedef iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      typedef __gnu_parallel::_SequenceIndex _SequenceIndex;

      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().count_minimal_n
            && __gnu_parallel::__is_parallel(__parallelism_tag)))
        {
          __gnu_parallel::__count_selector<_RAIter, _DifferenceType>
            __functionality;
          _DifferenceType __res = 0;
          __gnu_parallel::
            __for_each_template_random_access(
              __begin, __end, __value, __functionality,
              std::plus<_SequenceIndex>(), __res, __res, -1,
              __parallelism_tag);
          return __res;
        }
      else
        return count(__begin, __end, __value,
                     __gnu_parallel::sequential_tag());
    }

  // Sequential fallback for input iterator case.
  template<typename _IIter, typename _Tp, typename _IteratorTag>
    inline typename iterator_traits<_IIter>::difference_type
    __count_switch(_IIter __begin, _IIter __end, const _Tp& __value, 
                 _IteratorTag)
    { return count(__begin, __end, __value, __gnu_parallel::sequential_tag());
      }

  // Public interface.
  template<typename _IIter, typename _Tp>
    inline typename iterator_traits<_IIter>::difference_type
    count(_IIter __begin, _IIter __end, const _Tp& __value, 
          __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __count_switch(__begin, __end, __value, _IteratorCategory(),
                            __parallelism_tag);
    }

  template<typename _IIter, typename _Tp>
    inline typename iterator_traits<_IIter>::difference_type
    count(_IIter __begin, _IIter __end, const _Tp& __value)
    {
      typedef iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __count_switch(__begin, __end, __value, _IteratorCategory());
    }


  // Sequential fallback.
  template<typename _IIter, typename _Predicate>
    inline typename iterator_traits<_IIter>::difference_type
    count_if(_IIter __begin, _IIter __end, _Predicate __pred, 
             __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::count_if(__begin, __end, __pred); }

  // Parallel count_if for random access iterators
  template<typename _RAIter, typename _Predicate>
    typename iterator_traits<_RAIter>::difference_type
    __count_if_switch(_RAIter __begin, _RAIter __end, 
                    _Predicate __pred, random_access_iterator_tag,
                    __gnu_parallel::_Parallelism __parallelism_tag
                    = __gnu_parallel::parallel_unbalanced)
    {
      typedef iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      typedef typename _TraitsType::difference_type _DifferenceType;
      typedef __gnu_parallel::_SequenceIndex _SequenceIndex;

      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().count_minimal_n
            && __gnu_parallel::__is_parallel(__parallelism_tag)))
        {
          _DifferenceType __res = 0;
          __gnu_parallel::
            __count_if_selector<_RAIter, _DifferenceType>
            __functionality;
          __gnu_parallel::
            __for_each_template_random_access(
              __begin, __end, __pred, __functionality,
              std::plus<_SequenceIndex>(), __res, __res, -1,
              __parallelism_tag);
          return __res;
        }
      else
        return count_if(__begin, __end, __pred,
                        __gnu_parallel::sequential_tag());
    }

  // Sequential fallback for input iterator case.
  template<typename _IIter, typename _Predicate, typename _IteratorTag>
    inline typename iterator_traits<_IIter>::difference_type
    __count_if_switch(_IIter __begin, _IIter __end, _Predicate __pred, 
                    _IteratorTag)
    { return count_if(__begin, __end, __pred,
                      __gnu_parallel::sequential_tag()); }

  // Public interface.
  template<typename _IIter, typename _Predicate>
    inline typename iterator_traits<_IIter>::difference_type
    count_if(_IIter __begin, _IIter __end, _Predicate __pred, 
             __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __count_if_switch(__begin, __end, __pred, _IteratorCategory(), 
                             __parallelism_tag);
    }

  template<typename _IIter, typename _Predicate>
    inline typename iterator_traits<_IIter>::difference_type
    count_if(_IIter __begin, _IIter __end, _Predicate __pred)
    {
      typedef iterator_traits<_IIter> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __count_if_switch(__begin, __end, __pred, _IteratorCategory());
    }


  // Sequential fallback.
  template<typename _FIterator1, typename _FIterator2>
    inline _FIterator1
    search(_FIterator1 __begin1, _FIterator1 __end1,
           _FIterator2 __begin2, _FIterator2 __end2,
           __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::search(__begin1, __end1, __begin2, __end2); }

  // Parallel algorithm for random access iterator
  template<typename _RAIter1, typename _RAIter2>
    _RAIter1
    __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
                  _RAIter2 __begin2, _RAIter2 __end2,
                  random_access_iterator_tag, random_access_iterator_tag)
    {
      typedef std::iterator_traits<_RAIter1> _Iterator1Traits;
      typedef typename _Iterator1Traits::value_type _ValueType1;
      typedef std::iterator_traits<_RAIter2> _Iterator2Traits;
      typedef typename _Iterator2Traits::value_type _ValueType2;

      if (_GLIBCXX_PARALLEL_CONDITION(
                static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
            >= __gnu_parallel::_Settings::get().search_minimal_n))
        return __gnu_parallel::
          __search_template(
            __begin1, __end1, __begin2, __end2,
            __gnu_parallel::_EqualTo<_ValueType1, _ValueType2>());
      else
        return search(__begin1, __end1, __begin2, __end2,
                      __gnu_parallel::sequential_tag());
    }

  // Sequential fallback for input iterator case
  template<typename _FIterator1, typename _FIterator2,
           typename _IteratorTag1, typename _IteratorTag2>
    inline _FIterator1
    __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
                  _FIterator2 __begin2, _FIterator2 __end2,
                  _IteratorTag1, _IteratorTag2)
    { return search(__begin1, __end1, __begin2, __end2,
                    __gnu_parallel::sequential_tag()); }

  // Public interface.
  template<typename _FIterator1, typename _FIterator2>
    inline _FIterator1
    search(_FIterator1 __begin1, _FIterator1 __end1,
           _FIterator2 __begin2, _FIterator2 __end2)
    {
      typedef std::iterator_traits<_FIterator1> _Iterator1Traits;
      typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
      typedef std::iterator_traits<_FIterator2> _Iterator2Traits;
      typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;

      return __search_switch(__begin1, __end1, __begin2, __end2,
                           _IteratorCategory1(), _IteratorCategory2());
    }

  // Public interface.
  template<typename _FIterator1, typename _FIterator2,
           typename _BinaryPredicate>
    inline _FIterator1
    search(_FIterator1 __begin1, _FIterator1 __end1,
           _FIterator2 __begin2, _FIterator2 __end2,
           _BinaryPredicate __pred, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::search(
                               __begin1, __end1, __begin2, __end2, __pred); }

  // Parallel algorithm for random access iterator.
  template<typename _RAIter1, typename _RAIter2,
           typename _BinaryPredicate>
    _RAIter1
    __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
                  _RAIter2 __begin2, _RAIter2 __end2,
                  _BinaryPredicate __pred,
                  random_access_iterator_tag, random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
                static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
            >= __gnu_parallel::_Settings::get().search_minimal_n))
        return __gnu_parallel::__search_template(__begin1, __end1,
                                               __begin2, __end2, __pred);
      else
        return search(__begin1, __end1, __begin2, __end2, __pred,
                      __gnu_parallel::sequential_tag());
    }

  // Sequential fallback for input iterator case
  template<typename _FIterator1, typename _FIterator2,
           typename _BinaryPredicate, typename _IteratorTag1,
           typename _IteratorTag2>
    inline _FIterator1
    __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
                  _FIterator2 __begin2, _FIterator2 __end2,
                  _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2)
    { return search(__begin1, __end1, __begin2, __end2, __pred,
                    __gnu_parallel::sequential_tag()); }

  // Public interface
  template<typename _FIterator1, typename _FIterator2,
           typename _BinaryPredicate>
    inline _FIterator1
    search(_FIterator1 __begin1, _FIterator1 __end1,
           _FIterator2 __begin2, _FIterator2 __end2,
           _BinaryPredicate  __pred)
    {
      typedef std::iterator_traits<_FIterator1> _Iterator1Traits;
      typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
      typedef std::iterator_traits<_FIterator2> _Iterator2Traits;
      typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
      return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
                           _IteratorCategory1(), _IteratorCategory2());
    }

  // Sequential fallback
  template<typename _FIterator, typename _Integer, typename _Tp>
    inline _FIterator
    search_n(_FIterator __begin, _FIterator __end, _Integer __count,
             const _Tp& __val, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::search_n(__begin, __end, __count, __val); }

  // Sequential fallback
  template<typename _FIterator, typename _Integer, typename _Tp,
           typename _BinaryPredicate>
    inline _FIterator
    search_n(_FIterator __begin, _FIterator __end, _Integer __count,
             const _Tp& __val, _BinaryPredicate __binary_pred,
             __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::search_n(
               __begin, __end, __count, __val, __binary_pred); }

  // Public interface.
  template<typename _FIterator, typename _Integer, typename _Tp>
    inline _FIterator
    search_n(_FIterator __begin, _FIterator __end, _Integer __count,
             const _Tp& __val)
    {
      typedef typename iterator_traits<_FIterator>::value_type _ValueType;
      return __gnu_parallel::search_n(__begin, __end, __count, __val,
                      __gnu_parallel::_EqualTo<_ValueType, _Tp>());
    }

  // Parallel algorithm for random access iterators.
  template<typename _RAIter, typename _Integer,
           typename _Tp, typename _BinaryPredicate>
    _RAIter
    __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count,
                      const _Tp& __val, _BinaryPredicate __binary_pred,
                      random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
                static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().search_minimal_n))
        {
          __gnu_parallel::_PseudoSequence<_Tp, _Integer> __ps(__val, __count);
          return __gnu_parallel::__search_template(
                   __begin, __end, __ps.begin(), __ps.end(), __binary_pred);
        }
      else
        return _GLIBCXX_STD_P::search_n(__begin, __end, __count, __val,
                                        __binary_pred);
    }

  // Sequential fallback for input iterator case.
  template<typename _FIterator, typename _Integer, typename _Tp,
           typename _BinaryPredicate, typename _IteratorTag>
    inline _FIterator
    __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count,
                      const _Tp& __val, _BinaryPredicate __binary_pred,
                      _IteratorTag)
    { return _GLIBCXX_STD_P::search_n(__begin, __end, __count, __val,
                                      __binary_pred); }

  // Public interface.
  template<typename _FIterator, typename _Integer, typename _Tp,
           typename _BinaryPredicate>
    inline _FIterator
    search_n(_FIterator __begin, _FIterator __end, _Integer __count,
             const _Tp& __val, _BinaryPredicate __binary_pred)
    {
      return __search_n_switch(__begin, __end, __count, __val, __binary_pred,
                             typename std::iterator_traits<_FIterator>::
                             iterator_category());
    }


  // Sequential fallback.
  template<typename _IIter, typename _OutputIterator,
           typename _UnaryOperation>
    inline _OutputIterator
    transform(_IIter __begin, _IIter __end, _OutputIterator __result, 
              _UnaryOperation __unary_op, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::transform(__begin, __end, __result, __unary_op); }

  // Parallel unary transform for random access iterators.
  template<typename _RAIter1, typename _RAIter2,
           typename _UnaryOperation>
    _RAIter2
    __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
                      _RAIter2 __result, _UnaryOperation __unary_op,
                      random_access_iterator_tag, random_access_iterator_tag,
                      __gnu_parallel::_Parallelism __parallelism_tag
                      = __gnu_parallel::parallel_balanced)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().transform_minimal_n
            && __gnu_parallel::__is_parallel(__parallelism_tag)))
        {
          bool __dummy = true;
          typedef __gnu_parallel::_IteratorPair<_RAIter1,
            _RAIter2, random_access_iterator_tag> _ItTrip;
          _ItTrip __begin_pair(__begin, __result),
                  __end_pair(__end, __result + (__end - __begin));
          __gnu_parallel::__transform1_selector<_ItTrip> __functionality;
          __gnu_parallel::
            __for_each_template_random_access(
              __begin_pair, __end_pair, __unary_op, __functionality,
              __gnu_parallel::_DummyReduct(),
              __dummy, __dummy, -1, __parallelism_tag);
          return __functionality._M_finish_iterator;
        }
      else
        return transform(__begin, __end, __result, __unary_op, 
                         __gnu_parallel::sequential_tag());
    }

  // Sequential fallback for input iterator case.
  template<typename _RAIter1, typename _RAIter2,
           typename _UnaryOperation, typename _IteratorTag1,
           typename _IteratorTag2>
    inline _RAIter2
    __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
                      _RAIter2 __result, _UnaryOperation __unary_op,
                      _IteratorTag1, _IteratorTag2)
    { return transform(__begin, __end, __result, __unary_op, 
                       __gnu_parallel::sequential_tag()); }

  // Public interface.
  template<typename _IIter, typename _OutputIterator,
           typename _UnaryOperation>
    inline _OutputIterator
    transform(_IIter __begin, _IIter __end, _OutputIterator __result,
              _UnaryOperation __unary_op, 
              __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef std::iterator_traits<_IIter> _IIterTraits;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits::iterator_category _IIteratorCategory;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __transform1_switch(__begin, __end, __result, __unary_op,
                               _IIteratorCategory(), _OIterCategory(), 
                               __parallelism_tag);
    }

  template<typename _IIter, typename _OutputIterator,
           typename _UnaryOperation>
    inline _OutputIterator
    transform(_IIter __begin, _IIter __end, _OutputIterator __result,
              _UnaryOperation __unary_op)
    {
      typedef std::iterator_traits<_IIter> _IIterTraits;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits::iterator_category _IIteratorCategory;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __transform1_switch(__begin, __end, __result, __unary_op,
                               _IIteratorCategory(), _OIterCategory());
    }


  // Sequential fallback
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _BinaryOperation>
    inline _OutputIterator
    transform(_IIter1 __begin1, _IIter1 __end1,
              _IIter2 __begin2, _OutputIterator __result,
              _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::transform(__begin1, __end1,
                                       __begin2, __result, __binary_op); }

  // Parallel binary transform for random access iterators.
  template<typename _RAIter1, typename _RAIter2,
           typename _RAIter3, typename _BinaryOperation>
    _RAIter3
    __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1,
                      _RAIter2 __begin2,
                      _RAIter3 __result, _BinaryOperation __binary_op,
                      random_access_iterator_tag, random_access_iterator_tag,
                      random_access_iterator_tag,
                      __gnu_parallel::_Parallelism __parallelism_tag 
                      = __gnu_parallel::parallel_balanced)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            (__end1 - __begin1) >=
                __gnu_parallel::_Settings::get().transform_minimal_n
            && __gnu_parallel::__is_parallel(__parallelism_tag)))
        {
          bool __dummy = true;
          typedef __gnu_parallel::_IteratorTriple<_RAIter1,
            _RAIter2, _RAIter3,
            random_access_iterator_tag> _ItTrip;
          _ItTrip __begin_triple(__begin1, __begin2, __result),
            __end_triple(__end1, __begin2 + (__end1 - __begin1),
                       __result + (__end1 - __begin1));
          __gnu_parallel::__transform2_selector<_ItTrip> __functionality;
          __gnu_parallel::
            __for_each_template_random_access(__begin_triple, __end_triple,
                                            __binary_op, __functionality,
                                            __gnu_parallel::_DummyReduct(),
                                            __dummy, __dummy, -1,
                                            __parallelism_tag);
          return __functionality._M_finish_iterator;
        }
      else
        return transform(__begin1, __end1, __begin2, __result, __binary_op, 
                         __gnu_parallel::sequential_tag());
    }

  // Sequential fallback for input iterator case.
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _BinaryOperation,
           typename _Tag1, typename _Tag2, typename _Tag3>
    inline _OutputIterator
    __transform2_switch(_IIter1 __begin1, _IIter1 __end1, 
                      _IIter2 __begin2, _OutputIterator __result, 
                      _BinaryOperation __binary_op, _Tag1, _Tag2, _Tag3)
    { return transform(__begin1, __end1, __begin2, __result, __binary_op,
                       __gnu_parallel::sequential_tag()); }

  // Public interface.
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _BinaryOperation>
    inline _OutputIterator
    transform(_IIter1 __begin1, _IIter1 __end1,
              _IIter2 __begin2, _OutputIterator __result,
              _BinaryOperation __binary_op, 
              __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __transform2_switch(
               __begin1, __end1, __begin2, __result, __binary_op,
               _IIterCategory1(), _IIterCategory2(), _OIterCategory(),
               __parallelism_tag);
    }

  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _BinaryOperation>
    inline _OutputIterator
    transform(_IIter1 __begin1, _IIter1 __end1,
              _IIter2 __begin2, _OutputIterator __result,
              _BinaryOperation __binary_op)
    {
      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __transform2_switch(
               __begin1, __end1, __begin2, __result, __binary_op,
               _IIterCategory1(), _IIterCategory2(), _OIterCategory());
    }

  // Sequential fallback
  template<typename _FIterator, typename _Tp>
    inline void
    replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 
            const _Tp& __new_value, __gnu_parallel::sequential_tag)
    { _GLIBCXX_STD_P::replace(__begin, __end, __old_value, __new_value); }

  // Sequential fallback for input iterator case
  template<typename _FIterator, typename _Tp, typename _IteratorTag>
    inline void
    __replace_switch(_FIterator __begin, _FIterator __end, 
                     const _Tp& __old_value, const _Tp& __new_value,
                     _IteratorTag)
    { replace(__begin, __end, __old_value, __new_value, 
              __gnu_parallel::sequential_tag()); }

  // Parallel replace for random access iterators
  template<typename _RAIter, typename _Tp>
    inline void
    __replace_switch(_RAIter __begin, _RAIter __end, 
                   const _Tp& __old_value, const _Tp& __new_value, 
                   random_access_iterator_tag, 
                   __gnu_parallel::_Parallelism __parallelism_tag
                   = __gnu_parallel::parallel_balanced)
    {
      // XXX parallel version is where?
      replace(__begin, __end, __old_value, __new_value, 
              __gnu_parallel::sequential_tag()); 
    }

  // Public interface
  template<typename _FIterator, typename _Tp>
    inline void
    replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 
            const _Tp& __new_value,
            __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef iterator_traits<_FIterator> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      __replace_switch(__begin, __end, __old_value, __new_value,
                       _IteratorCategory(),
                     __parallelism_tag);
    }

  template<typename _FIterator, typename _Tp>
    inline void
    replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value, 
            const _Tp& __new_value)
    {
      typedef iterator_traits<_FIterator> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      __replace_switch(__begin, __end, __old_value, __new_value,
                       _IteratorCategory());
    }


  // Sequential fallback
  template<typename _FIterator, typename _Predicate, typename _Tp>
    inline void
    replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred, 
               const _Tp& __new_value, __gnu_parallel::sequential_tag)
    { _GLIBCXX_STD_P::replace_if(__begin, __end, __pred, __new_value); }

  // Sequential fallback for input iterator case
  template<typename _FIterator, typename _Predicate, typename _Tp,
           typename _IteratorTag>
    inline void
    __replace_if_switch(_FIterator __begin, _FIterator __end,
                      _Predicate __pred, const _Tp& __new_value, _IteratorTag)
    { replace_if(__begin, __end, __pred, __new_value,
                 __gnu_parallel::sequential_tag()); }

  // Parallel algorithm for random access iterators.
  template<typename _RAIter, typename _Predicate, typename _Tp>
    void
    __replace_if_switch(_RAIter __begin, _RAIter __end,
                      _Predicate __pred, const _Tp& __new_value,
                      random_access_iterator_tag,
                      __gnu_parallel::_Parallelism __parallelism_tag
                      = __gnu_parallel::parallel_balanced)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().replace_minimal_n
            && __gnu_parallel::__is_parallel(__parallelism_tag)))
        {
          bool __dummy;
          __gnu_parallel::
            __replace_if_selector<_RAIter, _Predicate, _Tp>
            __functionality(__new_value);
          __gnu_parallel::
            __for_each_template_random_access(
              __begin, __end, __pred, __functionality,
              __gnu_parallel::_DummyReduct(),
              true, __dummy, -1, __parallelism_tag);
        }
      else
        replace_if(__begin, __end, __pred, __new_value, 
                   __gnu_parallel::sequential_tag());
    }

  // Public interface.
  template<typename _FIterator, typename _Predicate, typename _Tp>
    inline void
    replace_if(_FIterator __begin, _FIterator __end,
               _Predicate __pred, const _Tp& __new_value, 
               __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef std::iterator_traits<_FIterator> _IteratorTraits;
      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
      __replace_if_switch(__begin, __end, __pred, __new_value,
                          _IteratorCategory(), __parallelism_tag);
    }

  template<typename _FIterator, typename _Predicate, typename _Tp>
    inline void
    replace_if(_FIterator __begin, _FIterator __end,
               _Predicate __pred, const _Tp& __new_value)
    {
      typedef std::iterator_traits<_FIterator> _IteratorTraits;
      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
      __replace_if_switch(__begin, __end, __pred, __new_value,
                          _IteratorCategory());
    }

  // Sequential fallback
  template<typename _FIterator, typename _Generator>
    inline void
    generate(_FIterator __begin, _FIterator __end, _Generator __gen, 
             __gnu_parallel::sequential_tag)
    { _GLIBCXX_STD_P::generate(__begin, __end, __gen); }

  // Sequential fallback for input iterator case.
  template<typename _FIterator, typename _Generator, typename _IteratorTag>
    inline void
    __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen,
                    _IteratorTag)
    { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); }

  // Parallel algorithm for random access iterators.
  template<typename _RAIter, typename _Generator>
    void
    __generate_switch(_RAIter __begin, _RAIter __end,
                    _Generator __gen, random_access_iterator_tag, 
                    __gnu_parallel::_Parallelism __parallelism_tag
                    = __gnu_parallel::parallel_balanced)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().generate_minimal_n
            && __gnu_parallel::__is_parallel(__parallelism_tag)))
        {
          bool __dummy;
          __gnu_parallel::__generate_selector<_RAIter>
            __functionality;
          __gnu_parallel::
            __for_each_template_random_access(
              __begin, __end, __gen, __functionality,
              __gnu_parallel::_DummyReduct(),
              true, __dummy, -1, __parallelism_tag);
        }
      else
        generate(__begin, __end, __gen, __gnu_parallel::sequential_tag());
    }

  // Public interface.
  template<typename _FIterator, typename _Generator>
    inline void
    generate(_FIterator __begin, _FIterator __end,
             _Generator __gen, __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef std::iterator_traits<_FIterator> _IteratorTraits;
      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
      __generate_switch(__begin, __end, __gen, _IteratorCategory(),
                        __parallelism_tag);
    }

  template<typename _FIterator, typename _Generator>
    inline void
    generate(_FIterator __begin, _FIterator __end, _Generator __gen)
    {
      typedef std::iterator_traits<_FIterator> _IteratorTraits;
      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
      __generate_switch(__begin, __end, __gen, _IteratorCategory());
    }


  // Sequential fallback.
  template<typename _OutputIterator, typename _Size, typename _Generator>
    inline _OutputIterator
    generate_n(_OutputIterator __begin, _Size __n, _Generator __gen, 
               __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::generate_n(__begin, __n, __gen); }

  // Sequential fallback for input iterator case.
  template<typename _OutputIterator, typename _Size, typename _Generator,
           typename _IteratorTag>
    inline _OutputIterator
    __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen,
                        _IteratorTag)
    { return generate_n(__begin, __n, __gen,
                        __gnu_parallel::sequential_tag()); }

  // Parallel algorithm for random access iterators.
  template<typename _RAIter, typename _Size, typename _Generator>
    inline _RAIter
    __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen, 
                      random_access_iterator_tag, 
                      __gnu_parallel::_Parallelism __parallelism_tag
                      = __gnu_parallel::parallel_balanced)
    {
      // XXX parallel version is where?
      return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag());
    }

  // Public interface.
  template<typename _OutputIterator, typename _Size, typename _Generator>
    inline _OutputIterator
    generate_n(_OutputIterator __begin, _Size __n, _Generator __gen, 
               __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef std::iterator_traits<_OutputIterator> _IteratorTraits;
      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
      return __generate_n_switch(__begin, __n, __gen, _IteratorCategory(), 
                               __parallelism_tag); 
    }

  template<typename _OutputIterator, typename _Size, typename _Generator>
    inline _OutputIterator
    generate_n(_OutputIterator __begin, _Size __n, _Generator __gen)
    {
      typedef std::iterator_traits<_OutputIterator> _IteratorTraits;
      typedef typename _IteratorTraits::iterator_category _IteratorCategory;
      return __generate_n_switch(__begin, __n, __gen, _IteratorCategory());
    }


  // Sequential fallback.
  template<typename _RAIter>
    inline void
    random_shuffle(_RAIter __begin, _RAIter __end, 
                   __gnu_parallel::sequential_tag)
    { _GLIBCXX_STD_P::random_shuffle(__begin, __end); }

  // Sequential fallback.
  template<typename _RAIter, typename _RandomNumberGenerator>
    inline void
    random_shuffle(_RAIter __begin, _RAIter __end,
                   _RandomNumberGenerator& __rand,
                   __gnu_parallel::sequential_tag)
    { _GLIBCXX_STD_P::random_shuffle(__begin, __end, __rand); }


  /** @brief Functor wrapper for std::rand(). */
  template<typename _MustBeInt = int>
    struct _CRandNumber
    {
      int
      operator()(int __limit)
      { return rand() % __limit; }
    };

  // Fill in random number generator.
  template<typename _RAIter>
    inline void
    random_shuffle(_RAIter __begin, _RAIter __end)
    {
      _CRandNumber<> __r;
      // Parallelization still possible.
      __gnu_parallel::random_shuffle(__begin, __end, __r);
    }

  // Parallel algorithm for random access iterators.
  template<typename _RAIter, typename _RandomNumberGenerator>
    void
    random_shuffle(_RAIter __begin, _RAIter __end,
#ifdef __GXX_EXPERIMENTAL_CXX0X__
                   _RandomNumberGenerator&& __rand)
#else
                   _RandomNumberGenerator& __rand)
#endif
    {
      if (__begin == __end)
        return;
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
        __gnu_parallel::__parallel_random_shuffle(__begin, __end, __rand);
      else
        __gnu_parallel::__sequential_random_shuffle(__begin, __end, __rand);
    }

  // Sequential fallback.
  template<typename _FIterator, typename _Predicate>
    inline _FIterator
    partition(_FIterator __begin, _FIterator __end,
              _Predicate __pred, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::partition(__begin, __end, __pred); }

  // Sequential fallback for input iterator case.
  template<typename _FIterator, typename _Predicate, typename _IteratorTag>
    inline _FIterator
    __partition_switch(_FIterator __begin, _FIterator __end,
                     _Predicate __pred, _IteratorTag)
    { return partition(__begin, __end, __pred,
                       __gnu_parallel::sequential_tag()); }

  // Parallel algorithm for random access iterators.
  template<typename _RAIter, typename _Predicate>
    _RAIter
    __partition_switch(_RAIter __begin, _RAIter __end,
                     _Predicate __pred, random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().partition_minimal_n))
        {
          typedef typename std::iterator_traits<_RAIter>::
            difference_type _DifferenceType;
          _DifferenceType __middle = __gnu_parallel::
            __parallel_partition(__begin, __end, __pred,
                               __gnu_parallel::__get_max_threads());
          return __begin + __middle;
        }
      else
        return partition(__begin, __end, __pred,
                         __gnu_parallel::sequential_tag());
    }

  // Public interface.
  template<typename _FIterator, typename _Predicate>
    inline _FIterator
    partition(_FIterator __begin, _FIterator __end, _Predicate __pred)
    {
      typedef iterator_traits<_FIterator> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __partition_switch(__begin, __end, __pred, _IteratorCategory());
    }

  // sort interface

  // Sequential fallback
  template<typename _RAIter>
    inline void
    sort(_RAIter __begin, _RAIter __end, 
         __gnu_parallel::sequential_tag)
    { _GLIBCXX_STD_P::sort(__begin, __end); }

  // Sequential fallback
  template<typename _RAIter, typename _Compare>
    inline void
    sort(_RAIter __begin, _RAIter __end, _Compare __comp,
         __gnu_parallel::sequential_tag)
    { _GLIBCXX_STD_P::sort<_RAIter, _Compare>(__begin, __end,
                                                             __comp); }

  // Public interface
  template<typename _RAIter, typename _Compare,
           typename _Parallelism>
  void
  sort(_RAIter __begin, _RAIter __end, _Compare __comp,
       _Parallelism __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;

    if (__begin != __end)
      {
        if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
              __gnu_parallel::_Settings::get().sort_minimal_n))
          __gnu_parallel::__parallel_sort<false>(
                            __begin, __end, __comp, __parallelism);
        else
          sort(__begin, __end, __comp, __gnu_parallel::sequential_tag());
      }
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
    inline void
    sort(_RAIter __begin, _RAIter __end)
    {
      typedef iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      sort(__begin, __end, std::less<_ValueType>(),
           __gnu_parallel::default_parallel_tag());
    }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  sort(_RAIter __begin, _RAIter __end,
       __gnu_parallel::default_parallel_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  sort(_RAIter __begin, _RAIter __end,
       __gnu_parallel::parallel_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  sort(_RAIter __begin, _RAIter __end,
       __gnu_parallel::multiway_mergesort_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  sort(_RAIter __begin, _RAIter __end,
       __gnu_parallel::multiway_mergesort_sampling_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  sort(_RAIter __begin, _RAIter __end,
       __gnu_parallel::multiway_mergesort_exact_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  sort(_RAIter __begin, _RAIter __end,
       __gnu_parallel::quicksort_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  sort(_RAIter __begin, _RAIter __end,
       __gnu_parallel::balanced_quicksort_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface
  template<typename _RAIter, typename _Compare>
    void
    sort(_RAIter __begin, _RAIter __end, _Compare __comp)
    {
      typedef iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
    sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag());
  }


  // stable_sort interface


  // Sequential fallback
  template<typename _RAIter>
  inline void
  stable_sort(_RAIter __begin, _RAIter __end,
       __gnu_parallel::sequential_tag)
  { _GLIBCXX_STD_P::stable_sort(__begin, __end); }

  // Sequential fallback
  template<typename _RAIter, typename _Compare>
  inline void
  stable_sort(_RAIter __begin, _RAIter __end,
              _Compare __comp, __gnu_parallel::sequential_tag)
  { _GLIBCXX_STD_P::stable_sort<_RAIter, _Compare>(
      __begin, __end, __comp); }

  // Public interface
  template<typename _RAIter, typename _Compare,
           typename _Parallelism>
  void
  stable_sort(_RAIter __begin, _RAIter __end,
              _Compare __comp, _Parallelism __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;

    if (__begin != __end)
      {
        if (_GLIBCXX_PARALLEL_CONDITION(
              static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
              __gnu_parallel::_Settings::get().sort_minimal_n))
          __gnu_parallel::__parallel_sort<true>(
                            __begin, __end, __comp, __parallelism);
        else
          stable_sort(__begin, __end, __comp,
                      __gnu_parallel::sequential_tag());
      }
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  stable_sort(_RAIter __begin, _RAIter __end)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    stable_sort(__begin, __end, std::less<_ValueType>(),
                __gnu_parallel::default_parallel_tag());
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  stable_sort(_RAIter __begin, _RAIter __end,
              __gnu_parallel::default_parallel_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  stable_sort(_RAIter __begin, _RAIter __end,
              __gnu_parallel::parallel_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  stable_sort(_RAIter __begin, _RAIter __end,
              __gnu_parallel::multiway_mergesort_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  stable_sort(_RAIter __begin, _RAIter __end,
              __gnu_parallel::quicksort_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface, insert default comparator
  template<typename _RAIter>
  inline void
  stable_sort(_RAIter __begin, _RAIter __end,
              __gnu_parallel::balanced_quicksort_tag __parallelism)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  }

  // Public interface
  template<typename _RAIter, typename _Compare>
  void
  stable_sort(_RAIter __begin, _RAIter __end,
              _Compare __comp)
  {
    typedef iterator_traits<_RAIter> _TraitsType;
    typedef typename _TraitsType::value_type _ValueType;
    stable_sort(
      __begin, __end, __comp, __gnu_parallel::default_parallel_tag());
  }

  // Sequential fallback
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator>
    inline _OutputIterator
    merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
          _IIter2 __end2, _OutputIterator __result,
          __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::merge(
               __begin1, __end1, __begin2, __end2, __result); }

  // Sequential fallback
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Compare>
    inline _OutputIterator
    merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
          _IIter2 __end2, _OutputIterator __result, _Compare __comp,
          __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::merge(
                __begin1, __end1, __begin2, __end2, __result, __comp); }

  // Sequential fallback for input iterator case
  template<typename _IIter1, typename _IIter2, typename _OutputIterator,
           typename _Compare, typename _IteratorTag1,
           typename _IteratorTag2, typename _IteratorTag3>
    inline _OutputIterator
    __merge_switch(_IIter1 __begin1, _IIter1 __end1,
                 _IIter2 __begin2, _IIter2 __end2,
                 _OutputIterator __result, _Compare __comp,
                 _IteratorTag1, _IteratorTag2, _IteratorTag3)
     { return _GLIBCXX_STD_P::merge(__begin1, __end1, __begin2, __end2,
                                    __result, __comp); }

  // Parallel algorithm for random access iterators
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Compare>
    _OutputIterator
    __merge_switch(_IIter1 __begin1, _IIter1 __end1, 
                 _IIter2 __begin2, _IIter2 __end2, 
                 _OutputIterator __result, _Compare __comp, 
                 random_access_iterator_tag, random_access_iterator_tag, 
                 random_access_iterator_tag)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
             >= __gnu_parallel::_Settings::get().merge_minimal_n
             || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
             >= __gnu_parallel::_Settings::get().merge_minimal_n)))
        return __gnu_parallel::__parallel_merge_advance(
                 __begin1, __end1, __begin2, __end2, __result,
                 (__end1 - __begin1) + (__end2 - __begin2), __comp);
      else
        return __gnu_parallel::__merge_advance(
                 __begin1, __end1, __begin2, __end2, __result,
                 (__end1 - __begin1) + (__end2 - __begin2), __comp);
  }

  // Public interface
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator, typename _Compare>
    inline _OutputIterator
    merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
          _IIter2 __end2, _OutputIterator __result, _Compare __comp)
    {
      typedef typename iterator_traits<_IIter1>::value_type _ValueType;

      typedef std::iterator_traits<_IIter1> _IIterTraits1;
      typedef std::iterator_traits<_IIter2> _IIterTraits2;
      typedef std::iterator_traits<_OutputIterator> _OIterTraits;
      typedef typename _IIterTraits1::iterator_category
        _IIterCategory1;
      typedef typename _IIterTraits2::iterator_category
        _IIterCategory2;
      typedef typename _OIterTraits::iterator_category _OIterCategory;

      return __merge_switch(
              __begin1, __end1, __begin2, __end2, __result, __comp,
              _IIterCategory1(), _IIterCategory2(), _OIterCategory());
  }


  // Public interface, insert default comparator
  template<typename _IIter1, typename _IIter2,
           typename _OutputIterator>
    inline _OutputIterator
    merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, 
          _IIter2 __end2, _OutputIterator __result)
    {
      typedef std::iterator_traits<_IIter1> _Iterator1Traits;
      typedef std::iterator_traits<_IIter2> _Iterator2Traits;
      typedef typename _Iterator1Traits::value_type _ValueType1;
      typedef typename _Iterator2Traits::value_type _ValueType2;

      return __gnu_parallel::merge(__begin1, __end1, __begin2, __end2,
                  __result, __gnu_parallel::_Less<_ValueType1, _ValueType2>());
    }

  // Sequential fallback
  template<typename _RAIter>
    inline void
    nth_element(_RAIter __begin, _RAIter __nth, 
                _RAIter __end, __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::nth_element(__begin, __nth, __end); }

  // Sequential fallback
  template<typename _RAIter, typename _Compare>
    inline void
    nth_element(_RAIter __begin, _RAIter __nth, 
                _RAIter __end, _Compare __comp, 
              __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::nth_element(__begin, __nth, __end, __comp); }

  // Public interface
  template<typename _RAIter, typename _Compare>
    inline void
    nth_element(_RAIter __begin, _RAIter __nth, 
                _RAIter __end, _Compare __comp)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
        __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp);
      else
        nth_element(__begin, __nth, __end, __comp,
                    __gnu_parallel::sequential_tag());
    }

  // Public interface, insert default comparator
  template<typename _RAIter>
    inline void
    nth_element(_RAIter __begin, _RAIter __nth, 
                _RAIter __end)
    {
      typedef iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      __gnu_parallel::nth_element(__begin, __nth, __end,
                                  std::less<_ValueType>());
    }

  // Sequential fallback
  template<typename _RAIter, typename _Compare>
    inline void
    partial_sort(_RAIter __begin, _RAIter __middle, 
                 _RAIter __end, _Compare __comp,
                 __gnu_parallel::sequential_tag)
    { _GLIBCXX_STD_P::partial_sort(__begin, __middle, __end, __comp); }

  // Sequential fallback
  template<typename _RAIter>
    inline void
    partial_sort(_RAIter __begin, _RAIter __middle, 
                 _RAIter __end, __gnu_parallel::sequential_tag)
    { _GLIBCXX_STD_P::partial_sort(__begin, __middle, __end); }

  // Public interface, parallel algorithm for random access iterators
  template<typename _RAIter, typename _Compare>
    void
    partial_sort(_RAIter __begin, _RAIter __middle, 
                 _RAIter __end, _Compare __comp)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
        __gnu_parallel::
          __parallel_partial_sort(__begin, __middle, __end, __comp);
      else
        partial_sort(__begin, __middle, __end, __comp,
                     __gnu_parallel::sequential_tag());
    }

  // Public interface, insert default comparator
  template<typename _RAIter>
    inline void
    partial_sort(_RAIter __begin, _RAIter __middle, 
                 _RAIter __end)
    {
      typedef iterator_traits<_RAIter> _TraitsType;
      typedef typename _TraitsType::value_type _ValueType;
      __gnu_parallel::partial_sort(__begin, __middle, __end,
                                   std::less<_ValueType>());
    }

  // Sequential fallback
  template<typename _FIterator>
    inline _FIterator
    max_element(_FIterator __begin, _FIterator __end, 
                __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::max_element(__begin, __end); }

  // Sequential fallback
  template<typename _FIterator, typename _Compare>
    inline _FIterator
    max_element(_FIterator __begin, _FIterator __end, _Compare __comp, 
                __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::max_element(__begin, __end, __comp); }

  // Sequential fallback for input iterator case
  template<typename _FIterator, typename _Compare, typename _IteratorTag>
    inline _FIterator
    __max_element_switch(_FIterator __begin, _FIterator __end, 
                       _Compare __comp, _IteratorTag)
    { return max_element(__begin, __end, __comp,
                         __gnu_parallel::sequential_tag()); }

  // Parallel algorithm for random access iterators
  template<typename _RAIter, typename _Compare>
    _RAIter
    __max_element_switch(_RAIter __begin, _RAIter __end, 
                       _Compare __comp, random_access_iterator_tag, 
                       __gnu_parallel::_Parallelism __parallelism_tag
                       = __gnu_parallel::parallel_balanced)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().max_element_minimal_n
            && __gnu_parallel::__is_parallel(__parallelism_tag)))
        {
          _RAIter __res(__begin);
          __gnu_parallel::__identity_selector<_RAIter>
            __functionality;
          __gnu_parallel::
            __for_each_template_random_access(
              __begin, __end, __gnu_parallel::_Nothing(), __functionality,
              __gnu_parallel::__max_element_reduct<_Compare, _RAIter>(__comp),
              __res, __res, -1, __parallelism_tag);
          return __res;
        }
      else
        return max_element(__begin, __end, __comp,
                           __gnu_parallel::sequential_tag());
    }

  // Public interface, insert default comparator
  template<typename _FIterator>
    inline _FIterator
    max_element(_FIterator __begin, _FIterator __end, 
                __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef typename iterator_traits<_FIterator>::value_type _ValueType;
      return max_element(__begin, __end, std::less<_ValueType>(),
                         __parallelism_tag);
    }

  template<typename _FIterator>
    inline _FIterator
    max_element(_FIterator __begin, _FIterator __end)
    {
      typedef typename iterator_traits<_FIterator>::value_type _ValueType;
      return __gnu_parallel::max_element(__begin, __end,
                                         std::less<_ValueType>());
    }

  // Public interface
  template<typename _FIterator, typename _Compare>
    inline _FIterator
    max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
                __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef iterator_traits<_FIterator> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __max_element_switch(__begin, __end, __comp, _IteratorCategory(), 
                                  __parallelism_tag);
    }

  template<typename _FIterator, typename _Compare>
    inline _FIterator
    max_element(_FIterator __begin, _FIterator __end, _Compare __comp)
    {
      typedef iterator_traits<_FIterator> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __max_element_switch(__begin, __end, __comp, _IteratorCategory());
    }


  // Sequential fallback
  template<typename _FIterator>
    inline _FIterator
    min_element(_FIterator __begin, _FIterator __end, 
                __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::min_element(__begin, __end); }

  // Sequential fallback
  template<typename _FIterator, typename _Compare>
    inline _FIterator
    min_element(_FIterator __begin, _FIterator __end, _Compare __comp, 
                __gnu_parallel::sequential_tag)
    { return _GLIBCXX_STD_P::min_element(__begin, __end, __comp); }

  // Sequential fallback for input iterator case
  template<typename _FIterator, typename _Compare, typename _IteratorTag>
    inline _FIterator
    __min_element_switch(_FIterator __begin, _FIterator __end, 
                       _Compare __comp, _IteratorTag)
    { return min_element(__begin, __end, __comp,
                         __gnu_parallel::sequential_tag()); }

  // Parallel algorithm for random access iterators
  template<typename _RAIter, typename _Compare>
    _RAIter
    __min_element_switch(_RAIter __begin, _RAIter __end, 
                       _Compare __comp, random_access_iterator_tag, 
                       __gnu_parallel::_Parallelism __parallelism_tag
                       = __gnu_parallel::parallel_balanced)
    {
      if (_GLIBCXX_PARALLEL_CONDITION(
            static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
            >= __gnu_parallel::_Settings::get().min_element_minimal_n
            && __gnu_parallel::__is_parallel(__parallelism_tag)))
        {
          _RAIter __res(__begin);
          __gnu_parallel::__identity_selector<_RAIter>
            __functionality;
          __gnu_parallel::
            __for_each_template_random_access(
              __begin, __end, __gnu_parallel::_Nothing(), __functionality,
              __gnu_parallel::__min_element_reduct<_Compare, _RAIter>(__comp),
              __res, __res, -1, __parallelism_tag);
          return __res;
        }
      else
        return min_element(__begin, __end, __comp,
                           __gnu_parallel::sequential_tag());
    }

  // Public interface, insert default comparator
  template<typename _FIterator>
    inline _FIterator
    min_element(_FIterator __begin, _FIterator __end, 
                __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef typename iterator_traits<_FIterator>::value_type _ValueType;
      return min_element(__begin, __end, std::less<_ValueType>(),
                         __parallelism_tag);
    }

  template<typename _FIterator>
    inline _FIterator
    min_element(_FIterator __begin, _FIterator __end)
    {
      typedef typename iterator_traits<_FIterator>::value_type _ValueType;
      return __gnu_parallel::min_element(__begin, __end,
                                         std::less<_ValueType>());
    }

  // Public interface
  template<typename _FIterator, typename _Compare>
    inline _FIterator
    min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
                __gnu_parallel::_Parallelism __parallelism_tag)
    {
      typedef iterator_traits<_FIterator> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __min_element_switch(__begin, __end, __comp, _IteratorCategory(), 
                                __parallelism_tag);
    }

  template<typename _FIterator, typename _Compare>
    inline _FIterator
    min_element(_FIterator __begin, _FIterator __end, _Compare __comp)
    {
      typedef iterator_traits<_FIterator> _TraitsType;
      typedef typename _TraitsType::iterator_category _IteratorCategory;
      return __min_element_switch(__begin, __end, __comp, _IteratorCategory());
    }
} // end namespace
} // end namespace

#endif /* _GLIBCXX_PARALLEL_ALGO_H */