| // -*- C++ -*- |
| |
| // Copyright (C) 2007, 2008, 2009 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 InputIterator, typename Function> |
| inline Function |
| for_each(InputIterator begin, InputIterator end, Function f, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::for_each(begin, end, f); } |
| |
| |
| // Sequential fallback for input iterator case |
| template<typename InputIterator, typename Function, typename IteratorTag> |
| inline Function |
| for_each_switch(InputIterator begin, InputIterator end, Function f, |
| IteratorTag) |
| { return for_each(begin, end, f, __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators |
| template<typename RandomAccessIterator, typename Function> |
| Function |
| for_each_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| Function f, random_access_iterator_tag, |
| __gnu_parallel::_Parallelism parallelism_tag |
| = __gnu_parallel::parallel_balanced) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().for_each_minimal_n |
| && __gnu_parallel::is_parallel(parallelism_tag))) |
| { |
| bool dummy; |
| __gnu_parallel::for_each_selector<RandomAccessIterator> functionality; |
| |
| return __gnu_parallel:: |
| for_each_template_random_access(begin, end, f, functionality, |
| __gnu_parallel::dummy_reduct(), |
| 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> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| return for_each_switch(begin, end, f, iterator_category(), |
| parallelism_tag); |
| } |
| |
| template<typename Iterator, typename Function> |
| inline Function |
| for_each(Iterator begin, Iterator end, Function f) |
| { |
| typedef std::iterator_traits<Iterator> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| return for_each_switch(begin, end, f, iterator_category()); |
| } |
| |
| |
| // Sequential fallback |
| template<typename InputIterator, typename T> |
| inline InputIterator |
| find(InputIterator begin, InputIterator end, const T& val, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::find(begin, end, val); } |
| |
| // Sequential fallback for input iterator case |
| template<typename InputIterator, typename T, typename IteratorTag> |
| inline InputIterator |
| find_switch(InputIterator begin, InputIterator end, const T& val, |
| IteratorTag) |
| { return _GLIBCXX_STD_P::find(begin, end, val); } |
| |
| // Parallel find for random access iterators |
| template<typename RandomAccessIterator, typename T> |
| RandomAccessIterator |
| find_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| const T& val, random_access_iterator_tag) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| |
| if (_GLIBCXX_PARALLEL_CONDITION(true)) |
| { |
| binder2nd<__gnu_parallel::equal_to<value_type, const T&> > |
| comp(__gnu_parallel::equal_to<value_type, const T&>(), 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 InputIterator, typename T> |
| inline InputIterator |
| find(InputIterator begin, InputIterator end, const T& val) |
| { |
| typedef std::iterator_traits<InputIterator> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| return find_switch(begin, end, val, iterator_category()); |
| } |
| |
| // Sequential fallback |
| template<typename InputIterator, typename Predicate> |
| inline InputIterator |
| find_if(InputIterator begin, InputIterator end, Predicate pred, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::find_if(begin, end, pred); } |
| |
| // Sequential fallback for input iterator case |
| template<typename InputIterator, typename Predicate, typename IteratorTag> |
| inline InputIterator |
| find_if_switch(InputIterator begin, InputIterator end, Predicate pred, |
| IteratorTag) |
| { return _GLIBCXX_STD_P::find_if(begin, end, pred); } |
| |
| // Parallel find_if for random access iterators |
| template<typename RandomAccessIterator, typename Predicate> |
| RandomAccessIterator |
| find_if_switch(RandomAccessIterator begin, RandomAccessIterator 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 InputIterator, typename Predicate> |
| inline InputIterator |
| find_if(InputIterator begin, InputIterator end, Predicate pred) |
| { |
| typedef std::iterator_traits<InputIterator> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| return find_if_switch(begin, end, pred, iterator_category()); |
| } |
| |
| // Sequential fallback |
| template<typename InputIterator, typename ForwardIterator> |
| inline InputIterator |
| find_first_of(InputIterator begin1, InputIterator end1, |
| ForwardIterator begin2, ForwardIterator end2, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2); } |
| |
| // Sequential fallback |
| template<typename InputIterator, typename ForwardIterator, |
| typename BinaryPredicate> |
| inline InputIterator |
| find_first_of(InputIterator begin1, InputIterator end1, |
| ForwardIterator begin2, ForwardIterator 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 InputIterator, typename ForwardIterator, |
| typename IteratorTag1, typename IteratorTag2> |
| inline InputIterator |
| find_first_of_switch(InputIterator begin1, InputIterator end1, |
| ForwardIterator begin2, ForwardIterator end2, |
| IteratorTag1, IteratorTag2) |
| { return find_first_of(begin1, end1, begin2, end2, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators |
| template<typename RandomAccessIterator, typename ForwardIterator, |
| typename BinaryPredicate, typename IteratorTag> |
| inline RandomAccessIterator |
| find_first_of_switch(RandomAccessIterator begin1, |
| RandomAccessIterator end1, |
| ForwardIterator begin2, ForwardIterator end2, |
| BinaryPredicate comp, random_access_iterator_tag, |
| IteratorTag) |
| { |
| return __gnu_parallel:: |
| find_template(begin1, end1, begin1, comp, |
| __gnu_parallel::find_first_of_selector |
| <ForwardIterator>(begin2, end2)).first; |
| } |
| |
| // Sequential fallback for input iterator type |
| template<typename InputIterator, typename ForwardIterator, |
| typename BinaryPredicate, typename IteratorTag1, |
| typename IteratorTag2> |
| inline InputIterator |
| find_first_of_switch(InputIterator begin1, InputIterator end1, |
| ForwardIterator begin2, ForwardIterator end2, |
| BinaryPredicate comp, IteratorTag1, IteratorTag2) |
| { return find_first_of(begin1, end1, begin2, end2, comp, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Public interface |
| template<typename InputIterator, typename ForwardIterator, |
| typename BinaryPredicate> |
| inline InputIterator |
| find_first_of(InputIterator begin1, InputIterator end1, |
| ForwardIterator begin2, ForwardIterator end2, |
| BinaryPredicate comp) |
| { |
| typedef std::iterator_traits<InputIterator> iteratori_traits; |
| typedef std::iterator_traits<ForwardIterator> iteratorf_traits; |
| typedef typename iteratori_traits::iterator_category iteratori_category; |
| typedef typename iteratorf_traits::iterator_category iteratorf_category; |
| |
| return find_first_of_switch(begin1, end1, begin2, end2, comp, |
| iteratori_category(), iteratorf_category()); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename InputIterator, typename ForwardIterator> |
| inline InputIterator |
| find_first_of(InputIterator begin1, InputIterator end1, |
| ForwardIterator begin2, ForwardIterator end2) |
| { |
| typedef std::iterator_traits<InputIterator> iteratori_traits; |
| typedef std::iterator_traits<ForwardIterator> iteratorf_traits; |
| typedef typename iteratori_traits::value_type valuei_type; |
| typedef typename iteratorf_traits::value_type valuef_type; |
| |
| return find_first_of(begin1, end1, begin2, end2, __gnu_parallel:: |
| equal_to<valuei_type, valuef_type>()); |
| } |
| |
| // Sequential fallback |
| template<typename InputIterator, typename OutputIterator> |
| inline OutputIterator |
| unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out); } |
| |
| // Sequential fallback |
| template<typename InputIterator, typename OutputIterator, |
| typename Predicate> |
| inline OutputIterator |
| unique_copy(InputIterator begin1, InputIterator 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 InputIterator, typename OutputIterator, |
| typename Predicate, typename IteratorTag1, typename IteratorTag2> |
| inline OutputIterator |
| unique_copy_switch(InputIterator begin, InputIterator 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 RandomAccessIterator, typename RandomAccessOutputIterator, |
| typename Predicate> |
| RandomAccessOutputIterator |
| unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last, |
| RandomAccessOutputIterator out, Predicate pred, |
| random_access_iterator_tag, random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(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 InputIterator, typename OutputIterator> |
| inline OutputIterator |
| unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out) |
| { |
| typedef std::iterator_traits<InputIterator> iteratori_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori_traits::iterator_category iteratori_category; |
| typedef typename iteratori_traits::value_type value_type; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return unique_copy_switch(begin1, end1, out, equal_to<value_type>(), |
| iteratori_category(), iteratoro_category()); |
| } |
| |
| // Public interface |
| template<typename InputIterator, typename OutputIterator, typename Predicate> |
| inline OutputIterator |
| unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out, |
| Predicate pred) |
| { |
| typedef std::iterator_traits<InputIterator> iteratori_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori_traits::iterator_category iteratori_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return unique_copy_switch(begin1, end1, out, pred, iteratori_category(), |
| iteratoro_category()); |
| } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator> |
| inline OutputIterator |
| set_union(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out); } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Predicate> |
| inline OutputIterator |
| set_union(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 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 InputIterator1, typename InputIterator2, |
| typename Predicate, typename OutputIterator, |
| typename IteratorTag1, typename IteratorTag2, typename IteratorTag3> |
| inline OutputIterator |
| set_union_switch(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, |
| typename OutputRandomAccessIterator, typename Predicate> |
| OutputRandomAccessIterator |
| set_union_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, |
| RandomAccessIterator2 begin2, RandomAccessIterator2 end2, |
| OutputRandomAccessIterator result, Predicate pred, |
| random_access_iterator_tag, random_access_iterator_tag, |
| random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) |
| >= __gnu_parallel::_Settings::get().set_union_minimal_n |
| || static_cast<__gnu_parallel::sequence_index_t>(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 InputIterator1, typename InputIterator2, |
| typename OutputIterator> |
| inline OutputIterator |
| set_union(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, OutputIterator out) |
| { |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| typedef typename iteratori1_traits::value_type value1_type; |
| typedef typename iteratori2_traits::value_type value2_type; |
| |
| return set_union_switch(begin1, end1, begin2, end2, out, |
| __gnu_parallel::less<value1_type, value2_type>(), |
| iteratori1_category(), iteratori2_category(), |
| iteratoro_category()); |
| } |
| |
| // Public interface |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Predicate> |
| inline OutputIterator |
| set_union(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out, Predicate pred) |
| { |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return set_union_switch(begin1, end1, begin2, end2, out, pred, |
| iteratori1_category(), iteratori2_category(), |
| iteratoro_category()); |
| } |
| |
| // Sequential fallback. |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator> |
| inline OutputIterator |
| set_intersection(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::set_intersection(begin1, end1, |
| begin2, end2, out); } |
| |
| // Sequential fallback. |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Predicate> |
| inline OutputIterator |
| set_intersection(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 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 InputIterator1, typename InputIterator2, |
| typename Predicate, typename OutputIterator, |
| typename IteratorTag1, typename IteratorTag2, |
| typename IteratorTag3> |
| inline OutputIterator |
| set_intersection_switch(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, |
| typename OutputRandomAccessIterator, typename Predicate> |
| OutputRandomAccessIterator |
| set_intersection_switch(RandomAccessIterator1 begin1, |
| RandomAccessIterator1 end1, |
| RandomAccessIterator2 begin2, |
| RandomAccessIterator2 end2, |
| OutputRandomAccessIterator result, |
| Predicate pred, |
| random_access_iterator_tag, |
| random_access_iterator_tag, |
| random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) |
| >= __gnu_parallel::_Settings::get().set_union_minimal_n |
| || static_cast<__gnu_parallel::sequence_index_t>(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 InputIterator1, typename InputIterator2, |
| typename OutputIterator> |
| inline OutputIterator |
| set_intersection(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out) |
| { |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| typedef typename iteratori1_traits::value_type value1_type; |
| typedef typename iteratori2_traits::value_type value2_type; |
| |
| return set_intersection_switch(begin1, end1, begin2, end2, out, |
| __gnu_parallel:: |
| less<value1_type, value2_type>(), |
| iteratori1_category(), |
| iteratori2_category(), |
| iteratoro_category()); |
| } |
| |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Predicate> |
| inline OutputIterator |
| set_intersection(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out, Predicate pred) |
| { |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return set_intersection_switch(begin1, end1, begin2, end2, out, pred, |
| iteratori1_category(), |
| iteratori2_category(), |
| iteratoro_category()); |
| } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator> |
| inline OutputIterator |
| set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1, |
| begin2, end2, out); } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Predicate> |
| inline OutputIterator |
| set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 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 InputIterator1, typename InputIterator2, |
| typename Predicate, typename OutputIterator, |
| typename IteratorTag1, typename IteratorTag2, |
| typename IteratorTag3> |
| inline OutputIterator |
| set_symmetric_difference_switch(InputIterator1 begin1, |
| InputIterator1 end1, |
| InputIterator2 begin2, |
| InputIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, |
| typename OutputRandomAccessIterator, typename Predicate> |
| OutputRandomAccessIterator |
| set_symmetric_difference_switch(RandomAccessIterator1 begin1, |
| RandomAccessIterator1 end1, |
| RandomAccessIterator2 begin2, |
| RandomAccessIterator2 end2, |
| OutputRandomAccessIterator result, |
| Predicate pred, |
| random_access_iterator_tag, |
| random_access_iterator_tag, |
| random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) |
| >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n |
| || static_cast<__gnu_parallel::sequence_index_t>(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 InputIterator1, typename InputIterator2, |
| typename OutputIterator> |
| inline OutputIterator |
| set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out) |
| { |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| typedef typename iteratori1_traits::value_type value1_type; |
| typedef typename iteratori2_traits::value_type value2_type; |
| |
| return set_symmetric_difference_switch(begin1, end1, begin2, end2, out, |
| __gnu_parallel:: |
| less<value1_type, value2_type>(), |
| iteratori1_category(), |
| iteratori2_category(), |
| iteratoro_category()); |
| } |
| |
| // Public interface. |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Predicate> |
| inline OutputIterator |
| set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out, Predicate pred) |
| { |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return set_symmetric_difference_switch(begin1, end1, begin2, end2, out, |
| pred, iteratori1_category(), |
| iteratori2_category(), |
| iteratoro_category()); |
| } |
| |
| // Sequential fallback. |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator> |
| inline OutputIterator |
| set_difference(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out); } |
| |
| // Sequential fallback. |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Predicate> |
| inline OutputIterator |
| set_difference(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 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 InputIterator1, typename InputIterator2, |
| typename Predicate, typename OutputIterator, |
| typename IteratorTag1, typename IteratorTag2, typename IteratorTag3> |
| inline OutputIterator |
| set_difference_switch(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, |
| typename OutputRandomAccessIterator, typename Predicate> |
| OutputRandomAccessIterator |
| set_difference_switch(RandomAccessIterator1 begin1, |
| RandomAccessIterator1 end1, |
| RandomAccessIterator2 begin2, |
| RandomAccessIterator2 end2, |
| OutputRandomAccessIterator result, Predicate pred, |
| random_access_iterator_tag, |
| random_access_iterator_tag, |
| random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) |
| >= __gnu_parallel::_Settings::get().set_difference_minimal_n |
| || static_cast<__gnu_parallel::sequence_index_t>(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 InputIterator1, typename InputIterator2, |
| typename OutputIterator> |
| inline OutputIterator |
| set_difference(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out) |
| { |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| typedef typename iteratori1_traits::value_type value1_type; |
| typedef typename iteratori2_traits::value_type value2_type; |
| |
| return set_difference_switch(begin1, end1, begin2, end2, out, |
| __gnu_parallel:: |
| less<value1_type, value2_type>(), |
| iteratori1_category(), |
| iteratori2_category(), |
| iteratoro_category()); |
| } |
| |
| // Public interface |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Predicate> |
| inline OutputIterator |
| set_difference(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator out, Predicate pred) |
| { |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return set_difference_switch(begin1, end1, begin2, end2, out, pred, |
| iteratori1_category(), |
| iteratori2_category(), |
| iteratoro_category()); |
| } |
| |
| // Sequential fallback |
| template<typename ForwardIterator> |
| inline ForwardIterator |
| adjacent_find(ForwardIterator begin, ForwardIterator end, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::adjacent_find(begin, end); } |
| |
| // Sequential fallback |
| template<typename ForwardIterator, typename BinaryPredicate> |
| inline ForwardIterator |
| adjacent_find(ForwardIterator begin, ForwardIterator 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 RandomAccessIterator> |
| RandomAccessIterator |
| adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| random_access_iterator_tag) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| |
| if (_GLIBCXX_PARALLEL_CONDITION(true)) |
| { |
| RandomAccessIterator spot = __gnu_parallel:: |
| find_template(begin, end - 1, begin, equal_to<value_type>(), |
| __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 ForwardIterator, typename IteratorTag> |
| inline ForwardIterator |
| adjacent_find_switch(ForwardIterator begin, ForwardIterator end, |
| IteratorTag) |
| { return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); } |
| |
| // Public interface |
| template<typename ForwardIterator> |
| inline ForwardIterator |
| adjacent_find(ForwardIterator begin, ForwardIterator end) |
| { |
| typedef iterator_traits<ForwardIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return adjacent_find_switch(begin, end, iterator_category()); |
| } |
| |
| // Sequential fallback for input iterator case |
| template<typename ForwardIterator, typename BinaryPredicate, |
| typename IteratorTag> |
| inline ForwardIterator |
| adjacent_find_switch(ForwardIterator begin, ForwardIterator end, |
| BinaryPredicate pred, IteratorTag) |
| { return adjacent_find(begin, end, pred, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators |
| template<typename RandomAccessIterator, typename BinaryPredicate> |
| RandomAccessIterator |
| adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator 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 ForwardIterator, typename BinaryPredicate> |
| inline ForwardIterator |
| adjacent_find(ForwardIterator begin, ForwardIterator end, |
| BinaryPredicate pred) |
| { |
| typedef iterator_traits<ForwardIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return adjacent_find_switch(begin, end, pred, iterator_category()); |
| } |
| |
| // Sequential fallback |
| template<typename InputIterator, typename T> |
| inline typename iterator_traits<InputIterator>::difference_type |
| count(InputIterator begin, InputIterator end, const T& value, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::count(begin, end, value); } |
| |
| // Parallel code for random access iterators |
| template<typename RandomAccessIterator, typename T> |
| typename iterator_traits<RandomAccessIterator>::difference_type |
| count_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| const T& value, random_access_iterator_tag, |
| __gnu_parallel::_Parallelism parallelism_tag |
| = __gnu_parallel::parallel_unbalanced) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| typedef typename traits_type::difference_type difference_type; |
| typedef __gnu_parallel::sequence_index_t sequence_index_t; |
| |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().count_minimal_n |
| && __gnu_parallel::is_parallel(parallelism_tag))) |
| { |
| __gnu_parallel::count_selector<RandomAccessIterator, difference_type> |
| functionality; |
| difference_type res = 0; |
| __gnu_parallel:: |
| for_each_template_random_access(begin, end, value, |
| functionality, |
| std::plus<sequence_index_t>(), |
| 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 InputIterator, typename T, typename IteratorTag> |
| inline typename iterator_traits<InputIterator>::difference_type |
| count_switch(InputIterator begin, InputIterator end, const T& value, |
| IteratorTag) |
| { return count(begin, end, value, __gnu_parallel::sequential_tag()); } |
| |
| // Public interface. |
| template<typename InputIterator, typename T> |
| inline typename iterator_traits<InputIterator>::difference_type |
| count(InputIterator begin, InputIterator end, const T& value, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef iterator_traits<InputIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return count_switch(begin, end, value, iterator_category(), |
| parallelism_tag); |
| } |
| |
| template<typename InputIterator, typename T> |
| inline typename iterator_traits<InputIterator>::difference_type |
| count(InputIterator begin, InputIterator end, const T& value) |
| { |
| typedef iterator_traits<InputIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return count_switch(begin, end, value, iterator_category()); |
| } |
| |
| |
| // Sequential fallback. |
| template<typename InputIterator, typename Predicate> |
| inline typename iterator_traits<InputIterator>::difference_type |
| count_if(InputIterator begin, InputIterator 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 RandomAccessIterator, typename Predicate> |
| typename iterator_traits<RandomAccessIterator>::difference_type |
| count_if_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| Predicate pred, random_access_iterator_tag, |
| __gnu_parallel::_Parallelism parallelism_tag |
| = __gnu_parallel::parallel_unbalanced) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| typedef typename traits_type::difference_type difference_type; |
| typedef __gnu_parallel::sequence_index_t sequence_index_t; |
| |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().count_minimal_n |
| && __gnu_parallel::is_parallel(parallelism_tag))) |
| { |
| difference_type res = 0; |
| __gnu_parallel:: |
| count_if_selector<RandomAccessIterator, difference_type> |
| functionality; |
| __gnu_parallel:: |
| for_each_template_random_access(begin, end, pred, |
| functionality, |
| std::plus<sequence_index_t>(), |
| 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 InputIterator, typename Predicate, typename IteratorTag> |
| inline typename iterator_traits<InputIterator>::difference_type |
| count_if_switch(InputIterator begin, InputIterator end, Predicate pred, |
| IteratorTag) |
| { return count_if(begin, end, pred, __gnu_parallel::sequential_tag()); } |
| |
| // Public interface. |
| template<typename InputIterator, typename Predicate> |
| inline typename iterator_traits<InputIterator>::difference_type |
| count_if(InputIterator begin, InputIterator end, Predicate pred, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef iterator_traits<InputIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return count_if_switch(begin, end, pred, iterator_category(), |
| parallelism_tag); |
| } |
| |
| template<typename InputIterator, typename Predicate> |
| inline typename iterator_traits<InputIterator>::difference_type |
| count_if(InputIterator begin, InputIterator end, Predicate pred) |
| { |
| typedef iterator_traits<InputIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return count_if_switch(begin, end, pred, iterator_category()); |
| } |
| |
| |
| // Sequential fallback. |
| template<typename ForwardIterator1, typename ForwardIterator2> |
| inline ForwardIterator1 |
| search(ForwardIterator1 begin1, ForwardIterator1 end1, |
| ForwardIterator2 begin2, ForwardIterator2 end2, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2); } |
| |
| // Parallel algorithm for random access iterator |
| template<typename RandomAccessIterator1, typename RandomAccessIterator2> |
| RandomAccessIterator1 |
| search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, |
| RandomAccessIterator2 begin2, RandomAccessIterator2 end2, |
| random_access_iterator_tag, random_access_iterator_tag) |
| { |
| typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits; |
| typedef typename iterator1_traits::value_type value1_type; |
| typedef std::iterator_traits<RandomAccessIterator2> iterator2_traits; |
| typedef typename iterator2_traits::value_type value2_type; |
| |
| if (_GLIBCXX_PARALLEL_CONDITION(true)) |
| return __gnu_parallel:: |
| search_template(begin1, end1, begin2, end2, __gnu_parallel:: |
| equal_to<value1_type, value2_type>()); |
| else |
| return search(begin1, end1, begin2, end2, |
| __gnu_parallel::sequential_tag()); |
| } |
| |
| // Sequential fallback for input iterator case |
| template<typename ForwardIterator1, typename ForwardIterator2, |
| typename IteratorTag1, typename IteratorTag2> |
| inline ForwardIterator1 |
| search_switch(ForwardIterator1 begin1, ForwardIterator1 end1, |
| ForwardIterator2 begin2, ForwardIterator2 end2, |
| IteratorTag1, IteratorTag2) |
| { return search(begin1, end1, begin2, end2, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Public interface. |
| template<typename ForwardIterator1, typename ForwardIterator2> |
| inline ForwardIterator1 |
| search(ForwardIterator1 begin1, ForwardIterator1 end1, |
| ForwardIterator2 begin2, ForwardIterator2 end2) |
| { |
| typedef std::iterator_traits<ForwardIterator1> iterator1_traits; |
| typedef typename iterator1_traits::iterator_category iterator1_category; |
| typedef std::iterator_traits<ForwardIterator2> iterator2_traits; |
| typedef typename iterator2_traits::iterator_category iterator2_category; |
| |
| return search_switch(begin1, end1, begin2, end2, |
| iterator1_category(), iterator2_category()); |
| } |
| |
| // Public interface. |
| template<typename ForwardIterator1, typename ForwardIterator2, |
| typename BinaryPredicate> |
| inline ForwardIterator1 |
| search(ForwardIterator1 begin1, ForwardIterator1 end1, |
| ForwardIterator2 begin2, ForwardIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, |
| typename BinaryPredicate> |
| RandomAccessIterator1 |
| search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, |
| RandomAccessIterator2 begin2, RandomAccessIterator2 end2, |
| BinaryPredicate pred, |
| random_access_iterator_tag, random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION(true)) |
| 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 ForwardIterator1, typename ForwardIterator2, |
| typename BinaryPredicate, typename IteratorTag1, |
| typename IteratorTag2> |
| inline ForwardIterator1 |
| search_switch(ForwardIterator1 begin1, ForwardIterator1 end1, |
| ForwardIterator2 begin2, ForwardIterator2 end2, |
| BinaryPredicate pred, IteratorTag1, IteratorTag2) |
| { return search(begin1, end1, begin2, end2, pred, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Public interface |
| template<typename ForwardIterator1, typename ForwardIterator2, |
| typename BinaryPredicate> |
| inline ForwardIterator1 |
| search(ForwardIterator1 begin1, ForwardIterator1 end1, |
| ForwardIterator2 begin2, ForwardIterator2 end2, |
| BinaryPredicate pred) |
| { |
| typedef std::iterator_traits<ForwardIterator1> iterator1_traits; |
| typedef typename iterator1_traits::iterator_category iterator1_category; |
| typedef std::iterator_traits<ForwardIterator2> iterator2_traits; |
| typedef typename iterator2_traits::iterator_category iterator2_category; |
| return search_switch(begin1, end1, begin2, end2, pred, |
| iterator1_category(), iterator2_category()); |
| } |
| |
| // Sequential fallback |
| template<typename ForwardIterator, typename Integer, typename T> |
| inline ForwardIterator |
| search_n(ForwardIterator begin, ForwardIterator end, Integer count, |
| const T& val, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::search_n(begin, end, count, val); } |
| |
| // Sequential fallback |
| template<typename ForwardIterator, typename Integer, typename T, |
| typename BinaryPredicate> |
| inline ForwardIterator |
| search_n(ForwardIterator begin, ForwardIterator end, Integer count, |
| const T& val, BinaryPredicate binary_pred, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred); } |
| |
| // Public interface. |
| template<typename ForwardIterator, typename Integer, typename T> |
| inline ForwardIterator |
| search_n(ForwardIterator begin, ForwardIterator end, Integer count, |
| const T& val) |
| { |
| typedef typename iterator_traits<ForwardIterator>::value_type value_type; |
| return search_n(begin, end, count, val, |
| __gnu_parallel::equal_to<value_type, T>()); |
| } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename RandomAccessIterator, typename Integer, |
| typename T, typename BinaryPredicate> |
| RandomAccessIterator |
| search_n_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| Integer count, const T& val, BinaryPredicate binary_pred, |
| random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION(true)) |
| { |
| __gnu_parallel::pseudo_sequence<T, Integer> ps(val, count); |
| return __gnu_parallel::search_template(begin, end, ps.begin(), |
| ps.end(), binary_pred); |
| } |
| else |
| return std::__search_n(begin, end, count, val, |
| binary_pred, random_access_iterator_tag()); |
| } |
| |
| // Sequential fallback for input iterator case. |
| template<typename ForwardIterator, typename Integer, typename T, |
| typename BinaryPredicate, typename IteratorTag> |
| inline ForwardIterator |
| search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count, |
| const T& val, BinaryPredicate binary_pred, IteratorTag) |
| { return __search_n(begin, end, count, val, binary_pred, IteratorTag()); } |
| |
| // Public interface. |
| template<typename ForwardIterator, typename Integer, typename T, |
| typename BinaryPredicate> |
| inline ForwardIterator |
| search_n(ForwardIterator begin, ForwardIterator end, Integer count, |
| const T& val, BinaryPredicate binary_pred) |
| { |
| return search_n_switch(begin, end, count, val, binary_pred, |
| typename std::iterator_traits<ForwardIterator>:: |
| iterator_category()); |
| } |
| |
| |
| // Sequential fallback. |
| template<typename InputIterator, typename OutputIterator, |
| typename UnaryOperation> |
| inline OutputIterator |
| transform(InputIterator begin, InputIterator 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 RandomAccessIterator1, typename RandomAccessIterator2, |
| typename UnaryOperation> |
| RandomAccessIterator2 |
| transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, |
| RandomAccessIterator2 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::sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().transform_minimal_n |
| && __gnu_parallel::is_parallel(parallelism_tag))) |
| { |
| bool dummy = true; |
| typedef __gnu_parallel::iterator_pair<RandomAccessIterator1, |
| RandomAccessIterator2, random_access_iterator_tag> ip; |
| ip begin_pair(begin, result), end_pair(end, result + (end - begin)); |
| __gnu_parallel::transform1_selector<ip> functionality; |
| __gnu_parallel:: |
| for_each_template_random_access(begin_pair, end_pair, |
| unary_op, functionality, |
| __gnu_parallel::dummy_reduct(), |
| dummy, dummy, -1, parallelism_tag); |
| return functionality.finish_iterator; |
| } |
| else |
| return transform(begin, end, result, unary_op, |
| __gnu_parallel::sequential_tag()); |
| } |
| |
| // Sequential fallback for input iterator case. |
| template<typename RandomAccessIterator1, typename RandomAccessIterator2, |
| typename UnaryOperation, typename IteratorTag1, |
| typename IteratorTag2> |
| inline RandomAccessIterator2 |
| transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end, |
| RandomAccessIterator2 result, UnaryOperation unary_op, |
| IteratorTag1, IteratorTag2) |
| { return transform(begin, end, result, unary_op, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Public interface. |
| template<typename InputIterator, typename OutputIterator, |
| typename UnaryOperation> |
| inline OutputIterator |
| transform(InputIterator begin, InputIterator end, OutputIterator result, |
| UnaryOperation unary_op, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef std::iterator_traits<InputIterator> iteratori_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori_traits::iterator_category iteratori_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return transform1_switch(begin, end, result, unary_op, |
| iteratori_category(), iteratoro_category(), |
| parallelism_tag); |
| } |
| |
| template<typename InputIterator, typename OutputIterator, |
| typename UnaryOperation> |
| inline OutputIterator |
| transform(InputIterator begin, InputIterator end, OutputIterator result, |
| UnaryOperation unary_op) |
| { |
| typedef std::iterator_traits<InputIterator> iteratori_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori_traits::iterator_category iteratori_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return transform1_switch(begin, end, result, unary_op, |
| iteratori_category(), iteratoro_category()); |
| } |
| |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename BinaryOperation> |
| inline OutputIterator |
| transform(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, |
| typename RandomAccessIterator3, typename BinaryOperation> |
| RandomAccessIterator3 |
| transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, |
| RandomAccessIterator2 begin2, |
| RandomAccessIterator3 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::iterator_triple<RandomAccessIterator1, |
| RandomAccessIterator2, RandomAccessIterator3, |
| random_access_iterator_tag> ip; |
| ip begin_triple(begin1, begin2, result), |
| end_triple(end1, begin2 + (end1 - begin1), |
| result + (end1 - begin1)); |
| __gnu_parallel::transform2_selector<ip> functionality; |
| __gnu_parallel:: |
| for_each_template_random_access(begin_triple, end_triple, |
| binary_op, functionality, |
| __gnu_parallel::dummy_reduct(), |
| dummy, dummy, -1, |
| parallelism_tag); |
| return functionality.finish_iterator; |
| } |
| else |
| return transform(begin1, end1, begin2, result, binary_op, |
| __gnu_parallel::sequential_tag()); |
| } |
| |
| // Sequential fallback for input iterator case. |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename BinaryOperation, |
| typename tag1, typename tag2, typename tag3> |
| inline OutputIterator |
| transform2_switch(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 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 InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename BinaryOperation> |
| inline OutputIterator |
| transform(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, OutputIterator result, |
| BinaryOperation binary_op, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return transform2_switch(begin1, end1, begin2, result, binary_op, |
| iteratori1_category(), iteratori2_category(), |
| iteratoro_category(), parallelism_tag); |
| } |
| |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename BinaryOperation> |
| inline OutputIterator |
| transform(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, OutputIterator result, |
| BinaryOperation binary_op) |
| { |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return transform2_switch(begin1, end1, begin2, result, binary_op, |
| iteratori1_category(), iteratori2_category(), |
| iteratoro_category()); |
| } |
| |
| // Sequential fallback |
| template<typename ForwardIterator, typename T> |
| inline void |
| replace(ForwardIterator begin, ForwardIterator end, const T& old_value, |
| const T& new_value, __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); } |
| |
| // Sequential fallback for input iterator case |
| template<typename ForwardIterator, typename T, typename IteratorTag> |
| inline void |
| replace_switch(ForwardIterator begin, ForwardIterator end, |
| const T& old_value, const T& new_value, IteratorTag) |
| { replace(begin, end, old_value, new_value, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Parallel replace for random access iterators |
| template<typename RandomAccessIterator, typename T> |
| inline void |
| replace_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| const T& old_value, const T& 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 ForwardIterator, typename T> |
| inline void |
| replace(ForwardIterator begin, ForwardIterator end, const T& old_value, |
| const T& new_value, __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef iterator_traits<ForwardIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| replace_switch(begin, end, old_value, new_value, iterator_category(), |
| parallelism_tag); |
| } |
| |
| template<typename ForwardIterator, typename T> |
| inline void |
| replace(ForwardIterator begin, ForwardIterator end, const T& old_value, |
| const T& new_value) |
| { |
| typedef iterator_traits<ForwardIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| replace_switch(begin, end, old_value, new_value, iterator_category()); |
| } |
| |
| |
| // Sequential fallback |
| template<typename ForwardIterator, typename Predicate, typename T> |
| inline void |
| replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred, |
| const T& new_value, __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); } |
| |
| // Sequential fallback for input iterator case |
| template<typename ForwardIterator, typename Predicate, typename T, |
| typename IteratorTag> |
| inline void |
| replace_if_switch(ForwardIterator begin, ForwardIterator end, |
| Predicate pred, const T& new_value, IteratorTag) |
| { replace_if(begin, end, pred, new_value, |
| __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename RandomAccessIterator, typename Predicate, typename T> |
| void |
| replace_if_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| Predicate pred, const T& new_value, |
| random_access_iterator_tag, |
| __gnu_parallel::_Parallelism parallelism_tag |
| = __gnu_parallel::parallel_balanced) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().replace_minimal_n |
| && __gnu_parallel::is_parallel(parallelism_tag))) |
| { |
| bool dummy; |
| __gnu_parallel:: |
| replace_if_selector<RandomAccessIterator, Predicate, T> |
| functionality(new_value); |
| __gnu_parallel:: |
| for_each_template_random_access(begin, end, pred, |
| functionality, |
| __gnu_parallel::dummy_reduct(), |
| true, dummy, -1, parallelism_tag); |
| } |
| else |
| replace_if(begin, end, pred, new_value, |
| __gnu_parallel::sequential_tag()); |
| } |
| |
| // Public interface. |
| template<typename ForwardIterator, typename Predicate, typename T> |
| inline void |
| replace_if(ForwardIterator begin, ForwardIterator end, |
| Predicate pred, const T& new_value, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef std::iterator_traits<ForwardIterator> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| replace_if_switch(begin, end, pred, new_value, iterator_category(), |
| parallelism_tag); |
| } |
| |
| template<typename ForwardIterator, typename Predicate, typename T> |
| inline void |
| replace_if(ForwardIterator begin, ForwardIterator end, |
| Predicate pred, const T& new_value) |
| { |
| typedef std::iterator_traits<ForwardIterator> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| replace_if_switch(begin, end, pred, new_value, iterator_category()); |
| } |
| |
| // Sequential fallback |
| template<typename ForwardIterator, typename Generator> |
| inline void |
| generate(ForwardIterator begin, ForwardIterator end, Generator gen, |
| __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::generate(begin, end, gen); } |
| |
| // Sequential fallback for input iterator case. |
| template<typename ForwardIterator, typename Generator, typename IteratorTag> |
| inline void |
| generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen, |
| IteratorTag) |
| { generate(begin, end, gen, __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename RandomAccessIterator, typename Generator> |
| void |
| generate_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| Generator gen, random_access_iterator_tag, |
| __gnu_parallel::_Parallelism parallelism_tag |
| = __gnu_parallel::parallel_balanced) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().generate_minimal_n |
| && __gnu_parallel::is_parallel(parallelism_tag))) |
| { |
| bool dummy; |
| __gnu_parallel::generate_selector<RandomAccessIterator> |
| functionality; |
| __gnu_parallel:: |
| for_each_template_random_access(begin, end, gen, functionality, |
| __gnu_parallel::dummy_reduct(), |
| true, dummy, -1, parallelism_tag); |
| } |
| else |
| generate(begin, end, gen, __gnu_parallel::sequential_tag()); |
| } |
| |
| // Public interface. |
| template<typename ForwardIterator, typename Generator> |
| inline void |
| generate(ForwardIterator begin, ForwardIterator end, |
| Generator gen, __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef std::iterator_traits<ForwardIterator> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| generate_switch(begin, end, gen, iterator_category(), parallelism_tag); |
| } |
| |
| template<typename ForwardIterator, typename Generator> |
| inline void |
| generate(ForwardIterator begin, ForwardIterator end, Generator gen) |
| { |
| typedef std::iterator_traits<ForwardIterator> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| generate_switch(begin, end, gen, iterator_category()); |
| } |
| |
| |
| // 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 RandomAccessIterator, typename Size, typename Generator> |
| inline RandomAccessIterator |
| generate_n_switch(RandomAccessIterator 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> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| return generate_n_switch(begin, n, gen, iterator_category(), |
| parallelism_tag); |
| } |
| |
| template<typename OutputIterator, typename Size, typename Generator> |
| inline OutputIterator |
| generate_n(OutputIterator begin, Size n, Generator gen) |
| { |
| typedef std::iterator_traits<OutputIterator> iterator_traits; |
| typedef typename iterator_traits::iterator_category iterator_category; |
| return generate_n_switch(begin, n, gen, iterator_category()); |
| } |
| |
| |
| // Sequential fallback. |
| template<typename RandomAccessIterator> |
| inline void |
| random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::random_shuffle(begin, end); } |
| |
| // Sequential fallback. |
| template<typename RandomAccessIterator, typename RandomNumberGenerator> |
| inline void |
| random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, |
| RandomNumberGenerator& rand, __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); } |
| |
| |
| /** @brief Functor wrapper for std::rand(). */ |
| template<typename must_be_int = int> |
| struct c_rand_number |
| { |
| int |
| operator()(int limit) |
| { return rand() % limit; } |
| }; |
| |
| // Fill in random number generator. |
| template<typename RandomAccessIterator> |
| inline void |
| random_shuffle(RandomAccessIterator begin, RandomAccessIterator end) |
| { |
| c_rand_number<> r; |
| // Parallelization still possible. |
| __gnu_parallel::random_shuffle(begin, end, r); |
| } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename RandomAccessIterator, typename RandomNumberGenerator> |
| void |
| random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, |
| RandomNumberGenerator& rand) |
| { |
| if (begin == end) |
| return; |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(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 ForwardIterator, typename Predicate> |
| inline ForwardIterator |
| partition(ForwardIterator begin, ForwardIterator end, |
| Predicate pred, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::partition(begin, end, pred); } |
| |
| // Sequential fallback for input iterator case. |
| template<typename ForwardIterator, typename Predicate, typename IteratorTag> |
| inline ForwardIterator |
| partition_switch(ForwardIterator begin, ForwardIterator end, |
| Predicate pred, IteratorTag) |
| { return partition(begin, end, pred, __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators. |
| template<typename RandomAccessIterator, typename Predicate> |
| RandomAccessIterator |
| partition_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| Predicate pred, random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().partition_minimal_n)) |
| { |
| typedef typename std::iterator_traits<RandomAccessIterator>:: |
| difference_type difference_type; |
| difference_type 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 ForwardIterator, typename Predicate> |
| inline ForwardIterator |
| partition(ForwardIterator begin, ForwardIterator end, Predicate pred) |
| { |
| typedef iterator_traits<ForwardIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return partition_switch(begin, end, pred, iterator_category()); |
| } |
| |
| // sort interface |
| |
| // Sequential fallback |
| template<typename RandomAccessIterator> |
| inline void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::sort(begin, end); } |
| |
| // Sequential fallback |
| template<typename RandomAccessIterator, typename Comparator> |
| inline void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, |
| __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end, |
| comp); } |
| |
| // Public interface |
| template<typename RandomAccessIterator, typename Comparator, |
| typename Parallelism> |
| void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, |
| Parallelism parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| |
| if (begin != end) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(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 RandomAccessIterator> |
| inline void |
| sort(RandomAccessIterator begin, RandomAccessIterator end) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| sort(begin, end, std::less<value_type>(), |
| __gnu_parallel::default_parallel_tag()); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::default_parallel_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::parallel_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::multiway_mergesort_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::multiway_mergesort_sampling_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::multiway_mergesort_exact_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::quicksort_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::balanced_quicksort_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface |
| template<typename RandomAccessIterator, typename Comparator> |
| void |
| sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| sort(begin, end, comp, __gnu_parallel::default_parallel_tag()); |
| } |
| |
| |
| // stable_sort interface |
| |
| |
| // Sequential fallback |
| template<typename RandomAccessIterator> |
| inline void |
| stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::stable_sort(begin, end); } |
| |
| // Sequential fallback |
| template<typename RandomAccessIterator, typename Comparator> |
| inline void |
| stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| Comparator comp, __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::stable_sort<RandomAccessIterator, Comparator>( |
| begin, end, comp); } |
| |
| // Public interface |
| template<typename RandomAccessIterator, typename Comparator, |
| typename Parallelism> |
| void |
| stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| Comparator comp, Parallelism parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| |
| if (begin != end) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(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 RandomAccessIterator> |
| inline void |
| stable_sort(RandomAccessIterator begin, RandomAccessIterator end) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| stable_sort(begin, end, std::less<value_type>(), |
| __gnu_parallel::default_parallel_tag()); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::default_parallel_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| stable_sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::parallel_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| stable_sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::multiway_mergesort_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| stable_sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::quicksort_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| stable_sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface, insert default comparator |
| template<typename RandomAccessIterator> |
| inline void |
| stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| __gnu_parallel::balanced_quicksort_tag parallelism) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| stable_sort(begin, end, std::less<value_type>(), parallelism); |
| } |
| |
| // Public interface |
| template<typename RandomAccessIterator, typename Comparator> |
| void |
| stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| Comparator comp) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| stable_sort(begin, end, comp, __gnu_parallel::default_parallel_tag()); |
| } |
| |
| |
| // // Sequential fallback |
| // template<typename RandomAccessIterator> |
| // inline void |
| // stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| // __gnu_parallel::sequential_tag) |
| // { return _GLIBCXX_STD_P::stable_sort(begin, end); } |
| // |
| // // Sequential fallback |
| // template<typename RandomAccessIterator, typename Comparator> |
| // inline void |
| // stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| // Comparator comp, __gnu_parallel::sequential_tag) |
| // { return _GLIBCXX_STD_P::stable_sort(begin, end, comp); } |
| // |
| // template<typename RandomAccessIterator> |
| // void |
| // stable_sort(RandomAccessIterator begin, RandomAccessIterator end) |
| // { |
| // typedef iterator_traits<RandomAccessIterator> traits_type; |
| // typedef typename traits_type::value_type value_type; |
| // stable_sort(begin, end, std::less<value_type>()); |
| // } |
| // |
| // // Parallel algorithm for random access iterators |
| // template<typename RandomAccessIterator, typename Comparator> |
| // void |
| // stable_sort(RandomAccessIterator begin, RandomAccessIterator end, |
| // Comparator comp) |
| // { |
| // if (begin != end) |
| // { |
| // if (_GLIBCXX_PARALLEL_CONDITION( |
| // static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= |
| // __gnu_parallel::_Settings::get().sort_minimal_n)) |
| // __gnu_parallel::parallel_sort(begin, end, comp, |
| // __gnu_parallel::parallel_tag()); |
| // else |
| // stable_sort(begin, end, comp, __gnu_parallel::sequential_tag()); |
| // } |
| // } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator> |
| inline OutputIterator |
| merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
| InputIterator2 end2, OutputIterator result, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result); } |
| |
| // Sequential fallback |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Comparator> |
| inline OutputIterator |
| merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
| InputIterator2 end2, OutputIterator result, Comparator comp, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp); } |
| |
| // Sequential fallback for input iterator case |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Comparator, |
| typename IteratorTag1, typename IteratorTag2, typename IteratorTag3> |
| inline OutputIterator |
| merge_switch(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator result, Comparator comp, |
| IteratorTag1, IteratorTag2, IteratorTag3) |
| { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, |
| result, comp); } |
| |
| // Parallel algorithm for random access iterators |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Comparator> |
| OutputIterator |
| merge_switch(InputIterator1 begin1, InputIterator1 end1, |
| InputIterator2 begin2, InputIterator2 end2, |
| OutputIterator result, Comparator comp, |
| random_access_iterator_tag, random_access_iterator_tag, |
| random_access_iterator_tag) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| (static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1) |
| >= __gnu_parallel::_Settings::get().merge_minimal_n |
| || static_cast<__gnu_parallel::sequence_index_t>(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 InputIterator1, typename InputIterator2, |
| typename OutputIterator, typename Comparator> |
| inline OutputIterator |
| merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
| InputIterator2 end2, OutputIterator result, Comparator comp) |
| { |
| typedef typename iterator_traits<InputIterator1>::value_type value_type; |
| |
| typedef std::iterator_traits<InputIterator1> iteratori1_traits; |
| typedef std::iterator_traits<InputIterator2> iteratori2_traits; |
| typedef std::iterator_traits<OutputIterator> iteratoro_traits; |
| typedef typename iteratori1_traits::iterator_category |
| iteratori1_category; |
| typedef typename iteratori2_traits::iterator_category |
| iteratori2_category; |
| typedef typename iteratoro_traits::iterator_category iteratoro_category; |
| |
| return merge_switch(begin1, end1, begin2, end2, result, comp, |
| iteratori1_category(), iteratori2_category(), |
| iteratoro_category()); |
| } |
| |
| |
| // Public interface, insert default comparator |
| template<typename InputIterator1, typename InputIterator2, |
| typename OutputIterator> |
| inline OutputIterator |
| merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, |
| InputIterator2 end2, OutputIterator result) |
| { |
| typedef std::iterator_traits<InputIterator1> iterator1_traits; |
| typedef std::iterator_traits<InputIterator2> iterator2_traits; |
| typedef typename iterator1_traits::value_type value1_type; |
| typedef typename iterator2_traits::value_type value2_type; |
| |
| return merge(begin1, end1, begin2, end2, result, |
| __gnu_parallel::less<value1_type, value2_type>()); |
| } |
| |
| // Sequential fallback |
| template<typename RandomAccessIterator> |
| inline void |
| nth_element(RandomAccessIterator begin, RandomAccessIterator nth, |
| RandomAccessIterator end, __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::nth_element(begin, nth, end); } |
| |
| // Sequential fallback |
| template<typename RandomAccessIterator, typename Comparator> |
| inline void |
| nth_element(RandomAccessIterator begin, RandomAccessIterator nth, |
| RandomAccessIterator end, Comparator comp, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); } |
| |
| // Public interface |
| template<typename RandomAccessIterator, typename Comparator> |
| inline void |
| nth_element(RandomAccessIterator begin, RandomAccessIterator nth, |
| RandomAccessIterator end, Comparator comp) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(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 RandomAccessIterator> |
| inline void |
| nth_element(RandomAccessIterator begin, RandomAccessIterator nth, |
| RandomAccessIterator end) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| nth_element(begin, nth, end, std::less<value_type>()); |
| } |
| |
| // Sequential fallback |
| template<typename RandomAccessIterator, typename _Compare> |
| inline void |
| partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, |
| RandomAccessIterator end, _Compare comp, |
| __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); } |
| |
| // Sequential fallback |
| template<typename RandomAccessIterator> |
| inline void |
| partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, |
| RandomAccessIterator end, __gnu_parallel::sequential_tag) |
| { _GLIBCXX_STD_P::partial_sort(begin, middle, end); } |
| |
| // Public interface, parallel algorithm for random access iterators |
| template<typename RandomAccessIterator, typename _Compare> |
| void |
| partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, |
| RandomAccessIterator end, _Compare comp) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(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 RandomAccessIterator> |
| inline void |
| partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, |
| RandomAccessIterator end) |
| { |
| typedef iterator_traits<RandomAccessIterator> traits_type; |
| typedef typename traits_type::value_type value_type; |
| partial_sort(begin, middle, end, std::less<value_type>()); |
| } |
| |
| // Sequential fallback |
| template<typename ForwardIterator> |
| inline ForwardIterator |
| max_element(ForwardIterator begin, ForwardIterator end, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::max_element(begin, end); } |
| |
| // Sequential fallback |
| template<typename ForwardIterator, typename Comparator> |
| inline ForwardIterator |
| max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::max_element(begin, end, comp); } |
| |
| // Sequential fallback for input iterator case |
| template<typename ForwardIterator, typename Comparator, typename IteratorTag> |
| inline ForwardIterator |
| max_element_switch(ForwardIterator begin, ForwardIterator end, |
| Comparator comp, IteratorTag) |
| { return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators |
| template<typename RandomAccessIterator, typename Comparator> |
| RandomAccessIterator |
| max_element_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| Comparator comp, random_access_iterator_tag, |
| __gnu_parallel::_Parallelism parallelism_tag |
| = __gnu_parallel::parallel_balanced) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().max_element_minimal_n |
| && __gnu_parallel::is_parallel(parallelism_tag))) |
| { |
| RandomAccessIterator res(begin); |
| __gnu_parallel::identity_selector<RandomAccessIterator> |
| functionality; |
| __gnu_parallel:: |
| for_each_template_random_access(begin, end, |
| __gnu_parallel::nothing(), |
| functionality, |
| __gnu_parallel:: |
| max_element_reduct<Comparator, |
| RandomAccessIterator>(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 ForwardIterator> |
| inline ForwardIterator |
| max_element(ForwardIterator begin, ForwardIterator end, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef typename iterator_traits<ForwardIterator>::value_type value_type; |
| return max_element(begin, end, std::less<value_type>(), parallelism_tag); |
| } |
| |
| template<typename ForwardIterator> |
| inline ForwardIterator |
| max_element(ForwardIterator begin, ForwardIterator end) |
| { |
| typedef typename iterator_traits<ForwardIterator>::value_type value_type; |
| return max_element(begin, end, std::less<value_type>()); |
| } |
| |
| // Public interface |
| template<typename ForwardIterator, typename Comparator> |
| inline ForwardIterator |
| max_element(ForwardIterator begin, ForwardIterator end, Comparator comp, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef iterator_traits<ForwardIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return max_element_switch(begin, end, comp, iterator_category(), |
| parallelism_tag); |
| } |
| |
| template<typename ForwardIterator, typename Comparator> |
| inline ForwardIterator |
| max_element(ForwardIterator begin, ForwardIterator end, Comparator comp) |
| { |
| typedef iterator_traits<ForwardIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return max_element_switch(begin, end, comp, iterator_category()); |
| } |
| |
| |
| // Sequential fallback |
| template<typename ForwardIterator> |
| inline ForwardIterator |
| min_element(ForwardIterator begin, ForwardIterator end, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::min_element(begin, end); } |
| |
| // Sequential fallback |
| template<typename ForwardIterator, typename Comparator> |
| inline ForwardIterator |
| min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, |
| __gnu_parallel::sequential_tag) |
| { return _GLIBCXX_STD_P::min_element(begin, end, comp); } |
| |
| // Sequential fallback for input iterator case |
| template<typename ForwardIterator, typename Comparator, typename IteratorTag> |
| inline ForwardIterator |
| min_element_switch(ForwardIterator begin, ForwardIterator end, |
| Comparator comp, IteratorTag) |
| { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); } |
| |
| // Parallel algorithm for random access iterators |
| template<typename RandomAccessIterator, typename Comparator> |
| RandomAccessIterator |
| min_element_switch(RandomAccessIterator begin, RandomAccessIterator end, |
| Comparator comp, random_access_iterator_tag, |
| __gnu_parallel::_Parallelism parallelism_tag |
| = __gnu_parallel::parallel_balanced) |
| { |
| if (_GLIBCXX_PARALLEL_CONDITION( |
| static_cast<__gnu_parallel::sequence_index_t>(end - begin) |
| >= __gnu_parallel::_Settings::get().min_element_minimal_n |
| && __gnu_parallel::is_parallel(parallelism_tag))) |
| { |
| RandomAccessIterator res(begin); |
| __gnu_parallel::identity_selector<RandomAccessIterator> |
| functionality; |
| __gnu_parallel:: |
| for_each_template_random_access(begin, end, |
| __gnu_parallel::nothing(), |
| functionality, |
| __gnu_parallel:: |
| min_element_reduct<Comparator, |
| RandomAccessIterator>(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 ForwardIterator> |
| inline ForwardIterator |
| min_element(ForwardIterator begin, ForwardIterator end, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef typename iterator_traits<ForwardIterator>::value_type value_type; |
| return min_element(begin, end, std::less<value_type>(), parallelism_tag); |
| } |
| |
| template<typename ForwardIterator> |
| inline ForwardIterator |
| min_element(ForwardIterator begin, ForwardIterator end) |
| { |
| typedef typename iterator_traits<ForwardIterator>::value_type value_type; |
| return min_element(begin, end, std::less<value_type>()); |
| } |
| |
| // Public interface |
| template<typename ForwardIterator, typename Comparator> |
| inline ForwardIterator |
| min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, |
| __gnu_parallel::_Parallelism parallelism_tag) |
| { |
| typedef iterator_traits<ForwardIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return min_element_switch(begin, end, comp, iterator_category(), |
| parallelism_tag); |
| } |
| |
| template<typename ForwardIterator, typename Comparator> |
| inline ForwardIterator |
| min_element(ForwardIterator begin, ForwardIterator end, Comparator comp) |
| { |
| typedef iterator_traits<ForwardIterator> traits_type; |
| typedef typename traits_type::iterator_category iterator_category; |
| return min_element_switch(begin, end, comp, iterator_category()); |
| } |
| } // end namespace |
| } // end namespace |
| |
| #endif /* _GLIBCXX_PARALLEL_ALGO_H */ |
