diff options
Diffstat (limited to 'libstdc++-v3/include/parallel/algo.h')
| -rw-r--r-- | libstdc++-v3/include/parallel/algo.h | 2363 |
1 files changed, 2363 insertions, 0 deletions
diff --git a/libstdc++-v3/include/parallel/algo.h b/libstdc++-v3/include/parallel/algo.h new file mode 100644 index 000000000..b27de9b37 --- /dev/null +++ b/libstdc++-v3/include/parallel/algo.h @@ -0,0 +1,2363 @@ +// -*- C++ -*- + +// Copyright (C) 2007, 2008, 2009, 2010, 2011 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 _GLIBCXX_VISIBILITY(default) +{ +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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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> _FIterTraits; + typedef typename _IIterTraits::iterator_category _IIteratorCategory; + typedef typename _FIterTraits::iterator_category _FIteratorCategory; + + return __find_first_of_switch(__begin1, __end1, __begin2, __end2, __comp, + _IIteratorCategory(), _FIteratorCategory()); + } + + // 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> _FIterTraits; + typedef typename _IIterTraits::value_type _IValueType; + typedef typename _FIterTraits::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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_A::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 */ |