This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
I reformatted on a basic level the remaining files except the ones that
expect significant changes soon:
-Max line length
-Tabs to spaces
-Pragmas consistent
Tested x86_64-unknown-linux-gnu: No regressions
Please approve (necessary in this case?).
2007-11-29 Johannes Singler <singler@ira.uka.de>
* include/parallel/iterator.h: Reformatting.
* include/parallel/find_selectors.h: Reformatting.
* include/parallel/list_partition.h: Reformatting.
* include/parallel/for_each.h: Reformatting.
* include/parallel/multiseq_selection.h: Reformatting.
* include/parallel/algorithmfwd.h: Reformatting.
* include/parallel/for_each_selectors.h: Reformatting.
* include/parallel/balanced_quicksort.h: Reformatting.
* include/parallel/merge.h: Reformatting.
* include/parallel/unique_copy.h: Reformatting.
* include/parallel/settings.h: Reformatting.
* include/parallel/numericfwd.h: Reformatting.
* include/parallel/search.h: Reformatting.
* include/parallel/partition.h: Reformatting.
* include/parallel/algobase.h: Reformatting.
* include/parallel/algo.h: Reformatting.
* include/parallel/queue.h: Reformatting.
* include/parallel/checkers.h: Reformatting.
Johannes
Index: include/parallel/iterator.h
===================================================================
--- include/parallel/iterator.h (revision 130490)
+++ include/parallel/iterator.h (working copy)
@@ -43,10 +43,10 @@
namespace __gnu_parallel
{
- /** @brief A pair of iterators. The usual iterator operations are
- * applied to both child iterators.
- */
- template<typename Iterator1, typename Iterator2, typename IteratorCategory>
+/** @brief A pair of iterators. The usual iterator operations are
+ * applied to both child iterators.
+ */
+template<typename Iterator1, typename Iterator2, typename IteratorCategory>
class iterator_pair : public std::pair<Iterator1, Iterator2>
{
private:
@@ -117,14 +117,16 @@
};
- /** @brief A triple of iterators. The usual iterator operations are
- applied to all three child iterators.
- */
- template<typename Iterator1, typename Iterator2, typename Iterator3, typename IteratorCategory>
+/** @brief A triple of iterators. The usual iterator operations are
+ applied to all three child iterators.
+ */
+template<typename Iterator1, typename Iterator2, typename Iterator3,
+ typename IteratorCategory>
class iterator_triple
{
private:
- typedef iterator_triple<Iterator1, Iterator2, Iterator3, IteratorCategory> type;
+ typedef iterator_triple<Iterator1, Iterator2, Iterator3, IteratorCategory>
+ type;
public:
typedef IteratorCategory iterator_category;
Index: include/parallel/find_selectors.h
===================================================================
--- include/parallel/find_selectors.h (revision 130490)
+++ include/parallel/find_selectors.h (working copy)
@@ -60,7 +60,8 @@
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline bool
operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
{ return pred(*i1); }
@@ -71,11 +72,15 @@
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
+ sequential_algorithm(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Pred pred)
{
- return std::make_pair(find_if(begin1, end1, pred, sequential_tag()), begin2);
+ return std::make_pair(find_if(begin1, end1, pred, sequential_tag()),
+ begin2);
}
};
@@ -87,7 +92,8 @@
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline bool
operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
{
@@ -101,14 +107,18 @@
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
+ sequential_algorithm(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Pred pred)
{
// Passed end iterator is one short.
- RandomAccessIterator1 spot = adjacent_find(begin1, end1 + 1, pred, sequential_tag());
+ RandomAccessIterator1 spot = adjacent_find(begin1, end1 + 1, pred,
+ sequential_tag());
if (spot == (end1 + 1))
- spot = end1;
+ spot = end1;
return std::make_pair(spot, begin2);
}
};
@@ -122,7 +132,8 @@
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline bool
operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
{ return !pred(*i1, *i2); }
@@ -134,9 +145,12 @@
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
+ sequential_algorithm(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Pred pred)
{
return mismatch(begin1, end1, begin2, pred, sequential_tag());
}
@@ -144,7 +158,7 @@
/** @brief Test predicate on several elements. */
- template<typename ForwardIterator>
+template<typename ForwardIterator>
struct find_first_of_selector : public generic_find_selector
{
ForwardIterator begin;
@@ -157,13 +171,16 @@
* @param i1 Iterator on first sequence.
* @param i2 Iterator on second sequence (unused).
* @param pred Find predicate. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline bool
operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
{
- for (ForwardIterator pos_in_candidates = begin; pos_in_candidates != end; pos_in_candidates++)
- if (pred(*i1, *pos_in_candidates))
- return true;
+ for (ForwardIterator pos_in_candidates = begin;
+ pos_in_candidates != end;
+ ++pos_in_candidates)
+ if (pred(*i1, *pos_in_candidates))
+ return true;
return false;
}
@@ -172,11 +189,16 @@
* @param end1 End iterator of first sequence.
* @param begin2 Begin iterator of second sequence.
* @param pred Find predicate. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename Pred>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename Pred>
inline std::pair<RandomAccessIterator1, RandomAccessIterator2>
- sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
+ sequential_algorithm(RandomAccessIterator1 begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2 begin2, Pred pred)
{
- return std::make_pair(find_first_of(begin1, end1, begin, end, pred, sequential_tag()), begin2);
+ return std::make_pair(find_first_of(begin1, end1, begin, end, pred,
+ sequential_tag()),
+ begin2);
}
};
}
Index: include/parallel/list_partition.h
===================================================================
--- include/parallel/list_partition.h (revision 130490)
+++ include/parallel/list_partition.h (working copy)
@@ -44,77 +44,79 @@
namespace __gnu_parallel
{
- /** @brief Shrinks and doubles the ranges.
- * @param os_starts Start positions worked on (oversampled).
- * @param count_to_two Counts up to 2.
- * @param range_length Current length of a chunk.
- * @param make_twice Whether the @c os_starts is allowed to be
- * grown or not
- */
- template<typename InputIterator>
+/** @brief Shrinks and doubles the ranges.
+ * @param os_starts Start positions worked on (oversampled).
+ * @param count_to_two Counts up to 2.
+ * @param range_length Current length of a chunk.
+ * @param make_twice Whether the @c os_starts is allowed to be
+ * grown or not
+ */
+template<typename InputIterator>
void
- shrink_and_double(std::vector<InputIterator>& os_starts, size_t& count_to_two, size_t& range_length, const bool make_twice)
+ shrink_and_double(std::vector<InputIterator>& os_starts,
+ size_t& count_to_two, size_t& range_length,
+ const bool make_twice)
{
++count_to_two;
if (not make_twice or count_to_two < 2)
- {
- shrink(os_starts, count_to_two, range_length);
- }
+ shrink(os_starts, count_to_two, range_length);
else
{
- os_starts.resize((os_starts.size() - 1) * 2 + 1);
- count_to_two = 0;
+ os_starts.resize((os_starts.size() - 1) * 2 + 1);
+ count_to_two = 0;
}
}
- /** @brief Combines two ranges into one and thus halves the number of ranges.
- * @param os_starts Start positions worked on (oversampled).
- * @param count_to_two Counts up to 2.
- * @param range_length Current length of a chunk. */
- template<typename InputIterator>
+/** @brief Combines two ranges into one and thus halves the number of ranges.
+ * @param os_starts Start positions worked on (oversampled).
+ * @param count_to_two Counts up to 2.
+ * @param range_length Current length of a chunk. */
+template<typename InputIterator>
void
shrink(std::vector<InputIterator>& os_starts, size_t& count_to_two,
- size_t& range_length)
+ size_t& range_length)
{
- for (typename std::vector<InputIterator>::size_type i = 0; i <= (os_starts.size() / 2); ++i)
+ for (typename std::vector<InputIterator>::size_type i = 0;
+ i <= (os_starts.size() / 2);
+ ++i)
{
- os_starts[i] = os_starts[i * 2];
+ os_starts[i] = os_starts[i * 2];
}
range_length *= 2;
}
- /** @brief Splits a sequence given by input iterators into parts of
- * almost equal size
- *
- * The function needs only one pass over the sequence.
- * @param begin Begin iterator of input sequence.
- * @param end End iterator of input sequence.
- * @param starts Start iterators for the resulting parts, dimension
- * @c num_parts+1. For convenience, @c starts @c [num_parts]
- * contains the end iterator of the sequence.
- * @param lengths Length of the resulting parts.
- * @param num_parts Number of parts to split the sequence into.
- * @param f Functor to be applied to each element by traversing it
- * @param oversampling Oversampling factor. If 0, then the
- * partitions will differ in at most @f$ \sqrt{\mathrm{end} -
- * \mathrm{begin}} @f$ elements. Otherwise, the ratio between the
- * longest and the shortest part is bounded by @f$
- * 1/(\mathrm{oversampling} \cdot \mathrm{num\_parts}) @f$.
- * @return Length of the whole sequence.
- */
- template<typename InputIterator, typename FunctorType>
+/** @brief Splits a sequence given by input iterators into parts of
+ * almost equal size
+ *
+ * The function needs only one pass over the sequence.
+ * @param begin Begin iterator of input sequence.
+ * @param end End iterator of input sequence.
+ * @param starts Start iterators for the resulting parts, dimension
+ * @c num_parts+1. For convenience, @c starts @c [num_parts]
+ * contains the end iterator of the sequence.
+ * @param lengths Length of the resulting parts.
+ * @param num_parts Number of parts to split the sequence into.
+ * @param f Functor to be applied to each element by traversing it
+ * @param oversampling Oversampling factor. If 0, then the
+ * partitions will differ in at most @f$ \sqrt{\mathrm{end} -
+ * \mathrm{begin}} @f$ elements. Otherwise, the ratio between the
+ * longest and the shortest part is bounded by @f$
+ * 1/(\mathrm{oversampling} \cdot \mathrm{num\_parts}) @f$.
+ * @return Length of the whole sequence.
+ */
+template<typename InputIterator, typename FunctorType>
size_t
list_partition(const InputIterator begin, const InputIterator end,
- InputIterator* starts, size_t* lengths, const int num_parts,
- FunctorType& f, int oversampling = 0)
+ InputIterator* starts, size_t* lengths, const int num_parts,
+ FunctorType& f, int oversampling = 0)
{
bool make_twice = false;
// According to the oversampling factor, the resizing algorithm is chosen.
if (oversampling == 0)
{
- make_twice = true;
- oversampling = 1;
+ make_twice = true;
+ oversampling = 1;
}
std::vector<InputIterator> os_starts(2 * oversampling * num_parts + 1);
@@ -128,19 +130,21 @@
while (it != end){
cur = next;
for (; cur < os_starts.size() and it != end; ++cur)
- {
- for (dist_limit += range_length; dist < dist_limit and it != end; ++dist)
- {
- f(it);
- ++it;
- }
- os_starts[cur] = it;
- }
+ {
+ for (dist_limit += range_length;
+ dist < dist_limit and it != end;
+ ++dist)
+ {
+ f(it);
+ ++it;
+ }
+ os_starts[cur] = it;
+ }
// Must compare for end and not cur < os_starts.size() , because
// cur could be == os_starts.size() as well
if (it == end)
- break;
+ break;
shrink_and_double(os_starts, count_to_two, range_length, make_twice);
next = os_starts.size()/2 + 1;
@@ -158,17 +162,17 @@
// Smallest partitions.
for (int i = 1; i < (num_parts + 1 - size_greater); ++i)
{
- lengths[i-1] = size_part * range_length;
- index += size_part;
- starts[i] = os_starts[index];
+ lengths[i-1] = size_part * range_length;
+ index += size_part;
+ starts[i] = os_starts[index];
}
// Biggest partitions.
for (int i = num_parts + 1 - size_greater; i <= num_parts; ++i)
{
- lengths[i-1] = (size_part+1) * range_length;
- index += (size_part+1);
- starts[i] = os_starts[index];
+ lengths[i-1] = (size_part+1) * range_length;
+ index += (size_part+1);
+ starts[i] = os_starts[index];
}
// Correction of the end size (the end iteration has not finished).
Index: include/parallel/for_each.h
===================================================================
--- include/parallel/for_each.h (revision 130490)
+++ include/parallel/for_each.h (working copy)
@@ -61,22 +61,31 @@
* @param output Output iterator.
* @param bound Maximum number of elements processed.
* @param parallelism_tag Parallelization method */
- template<typename InputIterator, typename UserOp, typename Functionality, typename Red, typename Result>
+
+template<typename InputIterator, typename UserOp, typename Functionality,
+ typename Red, typename Result>
UserOp
for_each_template_random_access(InputIterator begin, InputIterator end,
- UserOp user_op, Functionality& functionality,
- Red reduction, Result reduction_start,
- Result& output,
- typename std::iterator_traits<InputIterator>::difference_type bound, parallelism parallelism_tag)
+ UserOp user_op, Functionality& functionality,
+ Red reduction, Result reduction_start,
+ Result& output,
+ typename std::iterator_traits
+ <InputIterator>
+ ::difference_type bound,
+ parallelism parallelism_tag)
{
if (parallelism_tag == parallel_unbalanced)
- return for_each_template_random_access_ed(begin, end, user_op, functionality, reduction, reduction_start, output, bound);
+ return for_each_template_random_access_ed(begin, end, user_op,
+ functionality, reduction, reduction_start, output, bound);
else if (parallelism_tag == parallel_omp_loop)
- return for_each_template_random_access_omp_loop(begin, end, user_op, functionality, reduction, reduction_start, output, bound);
+ return for_each_template_random_access_omp_loop(begin, end, user_op,
+ functionality, reduction, reduction_start, output, bound);
else if (parallelism_tag == parallel_omp_loop_static)
- return for_each_template_random_access_omp_loop(begin, end, user_op, functionality, reduction, reduction_start, output, bound);
- else //e. g. parallel_balanced
- return for_each_template_random_access_workstealing(begin, end, user_op, functionality, reduction, reduction_start, output, bound);
+ return for_each_template_random_access_omp_loop(begin, end, user_op,
+ functionality, reduction, reduction_start, output, bound);
+ else //e. g. parallel_balanced
+ return for_each_template_random_access_workstealing(begin, end, user_op,
+ functionality, reduction, reduction_start, output, bound);
}
}
Index: include/parallel/multiseq_selection.h
===================================================================
--- include/parallel/multiseq_selection.h (revision 130490)
+++ include/parallel/multiseq_selection.h (working copy)
@@ -56,9 +56,10 @@
namespace __gnu_parallel
{
- /** @brief Compare a pair of types lexicographically, ascending. */
- template<typename T1, typename T2, typename Comparator>
- class lexicographic : public std::binary_function<std::pair<T1, T2>, std::pair<T1, T2>, bool>
+/** @brief Compare a pair of types lexicographically, ascending. */
+template<typename T1, typename T2, typename Comparator>
+ class lexicographic : public std::binary_function<std::pair<T1, T2>,
+ std::pair<T1, T2>, bool>
{
private:
Comparator& comp;
@@ -71,18 +72,18 @@
operator()(const std::pair<T1, T2>& p1, const std::pair<T1, T2>& p2) const
{
if (comp(p1.first, p2.first))
- return true;
+ return true;
if (comp(p2.first, p1.first))
- return false;
+ return false;
// Firsts are equal.
return p1.second < p2.second;
}
};
- /** @brief Compare a pair of types lexicographically, descending. */
- template<typename T1, typename T2, typename Comparator>
+/** @brief Compare a pair of types lexicographically, descending. */
+template<typename T1, typename T2, typename Comparator>
class lexicographic_reverse : public std::binary_function<T1, T2, bool>
{
private:
@@ -95,38 +96,41 @@
operator()(const std::pair<T1, T2>& p1, const std::pair<T1, T2>& p2) const
{
if (comp(p2.first, p1.first))
- return true;
+ return true;
if (comp(p1.first, p2.first))
- return false;
+ return false;
// Firsts are equal.
return p2.second < p1.second;
}
};
- /**
- * @brief Splits several sorted sequences at a certain global rank,
- * resulting in a splitting point for each sequence.
- * The sequences are passed via a sequence of random-access
- * iterator pairs, none of the sequences may be empty. If there
- * are several equal elements across the split, the ones on the
- * left side will be chosen from sequences with smaller number.
- * @param begin_seqs Begin of the sequence of iterator pairs.
- * @param end_seqs End of the sequence of iterator pairs.
- * @param rank The global rank to partition at.
- * @param begin_offsets A random-access sequence begin where the
- * result will be stored in. Each element of the sequence is an
- * iterator that points to the first element on the greater part of
- * the respective sequence.
- * @param comp The ordering functor, defaults to std::less<T>.
- */
- template<typename RanSeqs, typename RankType, typename RankIterator, typename Comparator>
+/**
+ * @brief Splits several sorted sequences at a certain global rank,
+ * resulting in a splitting point for each sequence.
+ * The sequences are passed via a sequence of random-access
+ * iterator pairs, none of the sequences may be empty. If there
+ * are several equal elements across the split, the ones on the
+ * left side will be chosen from sequences with smaller number.
+ * @param begin_seqs Begin of the sequence of iterator pairs.
+ * @param end_seqs End of the sequence of iterator pairs.
+ * @param rank The global rank to partition at.
+ * @param begin_offsets A random-access sequence begin where the
+ * result will be stored in. Each element of the sequence is an
+ * iterator that points to the first element on the greater part of
+ * the respective sequence.
+ * @param comp The ordering functor, defaults to std::less<T>.
+ */
+template<typename RanSeqs, typename RankType, typename RankIterator,
+ typename Comparator>
void
multiseq_partition(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank,
- RankIterator begin_offsets,
- Comparator comp = std::less<
- typename std::iterator_traits<typename std::iterator_traits<RanSeqs>::value_type::first_type>::value_type>()) // std::less<T>
+ RankIterator begin_offsets,
+ Comparator comp = std::less<
+ typename std::iterator_traits
+ <typename std::iterator_traits<RanSeqs>
+ ::value_type::first_type>::value_type>())
{
_GLIBCXX_CALL(end_seqs - begin_seqs)
@@ -146,9 +150,9 @@
if (rank == N)
{
- for (int i = 0; i < m; i++)
- begin_offsets[i] = begin_seqs[i].second; // Very end.
- // Return m - 1;
+ for (int i = 0; i < m; i++)
+ begin_offsets[i] = begin_seqs[i].second; // Very end.
+ // Return m - 1;
}
_GLIBCXX_PARALLEL_ASSERT(m != 0 && N != 0 && rank >= 0 && rank < N);
@@ -162,8 +166,8 @@
nmax = ns[0];
for (int i = 0; i < m; i++)
{
- ns[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second);
- nmax = std::max(nmax, ns[i]);
+ ns[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second);
+ nmax = std::max(nmax, ns[i]);
}
r = log2(nmax) + 1;
@@ -177,8 +181,8 @@
for (int i = 0; i < m; i++)
{
- a[i] = 0;
- b[i] = l;
+ a[i] = 0;
+ b[i] = l;
}
n = l / 2;
@@ -191,13 +195,13 @@
std::vector<std::pair<value_type, int> > sample;
for (int i = 0; i < m; i++)
- if (n < ns[i]) //sequence long enough
- sample.push_back(std::make_pair(S(i)[n], i));
+ if (n < ns[i]) //sequence long enough
+ sample.push_back(std::make_pair(S(i)[n], i));
__gnu_sequential::sort(sample.begin(), sample.end(), lcomp);
- for (int i = 0; i < m; i++) //conceptual infinity
- if (n >= ns[i]) //sequence too short, conceptual infinity
- sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i));
+ for (int i = 0; i < m; i++) //conceptual infinity
+ if (n >= ns[i]) //sequence too short, conceptual infinity
+ sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i));
difference_type localrank = rank * m / N ;
@@ -210,93 +214,103 @@
// Further refinement.
while (n > 0)
{
- n /= 2;
+ n /= 2;
- int lmax_seq = -1; // to avoid warning
- const value_type* lmax = NULL; // impossible to avoid the warning?
- for (int i = 0; i < m; i++)
- {
- if (a[i] > 0)
- {
- if (!lmax)
- {
- lmax = &(S(i)[a[i] - 1]);
- lmax_seq = i;
- }
- else
- {
- // Max, favor rear sequences.
- if (!comp(S(i)[a[i] - 1], *lmax))
- {
- lmax = &(S(i)[a[i] - 1]);
- lmax_seq = i;
- }
- }
- }
- }
+ int lmax_seq = -1; // to avoid warning
+ const value_type* lmax = NULL; // impossible to avoid the warning?
+ for (int i = 0; i < m; i++)
+ {
+ if (a[i] > 0)
+ {
+ if (!lmax)
+ {
+ lmax = &(S(i)[a[i] - 1]);
+ lmax_seq = i;
+ }
+ else
+ {
+ // Max, favor rear sequences.
+ if (!comp(S(i)[a[i] - 1], *lmax))
+ {
+ lmax = &(S(i)[a[i] - 1]);
+ lmax_seq = i;
+ }
+ }
+ }
+ }
- int i;
- for (i = 0; i < m; i++)
- {
- difference_type middle = (b[i] + a[i]) / 2;
- if (lmax && middle < ns[i] &&
- lcomp(std::make_pair(S(i)[middle], i), std::make_pair(*lmax, lmax_seq)))
- a[i] = std::min(a[i] + n + 1, ns[i]);
- else
- b[i] -= n + 1;
- }
+ int i;
+ for (i = 0; i < m; i++)
+ {
+ difference_type middle = (b[i] + a[i]) / 2;
+ if (lmax && middle < ns[i] &&
+ lcomp(std::make_pair(S(i)[middle], i),
+ std::make_pair(*lmax, lmax_seq)))
+ a[i] = std::min(a[i] + n + 1, ns[i]);
+ else
+ b[i] -= n + 1;
+ }
- difference_type leftsize = 0, total = 0;
- for (int i = 0; i < m; i++)
- {
- leftsize += a[i] / (n + 1);
- total += l / (n + 1);
- }
+ difference_type leftsize = 0, total = 0;
+ for (int i = 0; i < m; i++)
+ {
+ leftsize += a[i] / (n + 1);
+ total += l / (n + 1);
+ }
- difference_type skew = static_cast<difference_type>(static_cast<uint64>(total) * rank / N - leftsize);
+ difference_type skew = static_cast<difference_type>
+ (static_cast<uint64>(total) * rank / N - leftsize);
+ // Use integer of maximum size available.
- if (skew > 0)
- {
- // Move to the left, find smallest.
- std::priority_queue<std::pair<value_type, int>, std::vector<std::pair<value_type, int> >, lexicographic_reverse<value_type, int, Comparator> > pq(lrcomp);
+ if (skew > 0)
+ {
+ // Move to the left, find smallest.
+ std::priority_queue<
+ std::pair<value_type, int>,
+ std::vector<std::pair<value_type, int> >,
+ lexicographic_reverse<value_type, int, Comparator> >
+ pq(lrcomp);
- for (int i = 0; i < m; i++)
- if (b[i] < ns[i])
- pq.push(std::make_pair(S(i)[b[i]], i));
+ for (int i = 0; i < m; i++)
+ if (b[i] < ns[i])
+ pq.push(std::make_pair(S(i)[b[i]], i));
- for (; skew != 0 && !pq.empty(); skew--)
- {
- int source = pq.top().second;
- pq.pop();
+ for (; skew != 0 && !pq.empty(); skew--)
+ {
+ int source = pq.top().second;
+ pq.pop();
- a[source] = std::min(a[source] + n + 1, ns[source]);
- b[source] += n + 1;
+ a[source] = std::min(a[source] + n + 1, ns[source]);
+ b[source] += n + 1;
- if (b[source] < ns[source])
- pq.push(std::make_pair(S(source)[b[source]], source));
- }
- }
- else if (skew < 0)
- {
- // Move to the right, find greatest.
- std::priority_queue<std::pair<value_type, int>, std::vector<std::pair<value_type, int> >, lexicographic<value_type, int, Comparator> > pq(lcomp);
+ if (b[source] < ns[source])
+ pq.push(std::make_pair(S(source)[b[source]], source));
+ }
+ }
+ else if (skew < 0)
+ {
+ // Move to the right, find greatest.
+ std::priority_queue<
+ std::pair<value_type, int>,
+ std::vector<std::pair<value_type, int> >,
+ lexicographic<value_type, int, Comparator> > pq(lcomp);
- for (int i = 0; i < m; i++)
- if (a[i] > 0)
- pq.push(std::make_pair(S(i)[a[i] - 1], i));
+ for (int i = 0; i < m; i++)
+ if (a[i] > 0)
+ pq.push(std::make_pair(S(i)[a[i] - 1], i));
- for (; skew != 0; skew++)
- {
- int source = pq.top().second;
- pq.pop();
+ for (; skew != 0; skew++)
+ {
+ int source = pq.top().second;
+ pq.pop();
- a[source] -= n + 1;
- b[source] -= n + 1;
+ a[source] -= n + 1;
+ b[source] -= n + 1;
- if (a[source] > 0)
- pq.push(std::make_pair(S(source)[a[source] - 1], source));
- }
- }
+ if (a[source] > 0)
+ pq.push(std::make_pair(S(source)[a[source] - 1], source));
+ }
+ }
}
// Postconditions:
@@ -312,28 +326,28 @@
value_type* minright = NULL;
for (int i = 0; i < m; i++)
{
- if (a[i] > 0)
- {
- if (!maxleft)
- maxleft = &(S(i)[a[i] - 1]);
- else
- {
- // Max, favor rear sequences.
- if (!comp(S(i)[a[i] - 1], *maxleft))
- maxleft = &(S(i)[a[i] - 1]);
- }
- }
- if (b[i] < ns[i])
- {
- if (!minright)
- minright = &(S(i)[b[i]]);
- else
- {
- // Min, favor fore sequences.
- if (comp(S(i)[b[i]], *minright))
- minright = &(S(i)[b[i]]);
- }
- }
+ if (a[i] > 0)
+ {
+ if (!maxleft)
+ maxleft = &(S(i)[a[i] - 1]);
+ else
+ {
+ // Max, favor rear sequences.
+ if (!comp(S(i)[a[i] - 1], *maxleft))
+ maxleft = &(S(i)[a[i] - 1]);
+ }
+ }
+ if (b[i] < ns[i])
+ {
+ if (!minright)
+ minright = &(S(i)[b[i]]);
+ else
+ {
+ // Min, favor fore sequences.
+ if (comp(S(i)[b[i]], *minright))
+ minright = &(S(i)[b[i]]);
+ }
+ }
}
int seq = 0;
@@ -346,24 +360,25 @@
}
- /**
- * @brief Selects the element at a certain global rank from several
- * sorted sequences.
- *
- * The sequences are passed via a sequence of random-access
- * iterator pairs, none of the sequences may be empty.
- * @param begin_seqs Begin of the sequence of iterator pairs.
- * @param end_seqs End of the sequence of iterator pairs.
- * @param rank The global rank to partition at.
- * @param offset The rank of the selected element in the global
- * subsequence of elements equal to the selected element. If the
- * selected element is unique, this number is 0.
- * @param comp The ordering functor, defaults to std::less.
- */
- template<typename T, typename RanSeqs, typename RankType, typename Comparator>
+/**
+ * @brief Selects the element at a certain global rank from several
+ * sorted sequences.
+ *
+ * The sequences are passed via a sequence of random-access
+ * iterator pairs, none of the sequences may be empty.
+ * @param begin_seqs Begin of the sequence of iterator pairs.
+ * @param end_seqs End of the sequence of iterator pairs.
+ * @param rank The global rank to partition at.
+ * @param offset The rank of the selected element in the global
+ * subsequence of elements equal to the selected element. If the
+ * selected element is unique, this number is 0.
+ * @param comp The ordering functor, defaults to std::less.
+ */
+template<typename T, typename RanSeqs, typename RankType,
+ typename Comparator>
T
multiseq_selection(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank,
- RankType& offset, Comparator comp = std::less<T>())
+ RankType& offset, Comparator comp = std::less<T>())
{
_GLIBCXX_CALL(end_seqs - begin_seqs)
@@ -384,8 +399,8 @@
if (m == 0 || N == 0 || rank < 0 || rank >= N)
{
- // Result undefined when there is no data or rank is outside bounds.
- throw std::exception();
+ // Result undefined when there is no data or rank is outside bounds.
+ throw std::exception();
}
@@ -398,8 +413,8 @@
nmax = ns[0];
for (int i = 0; i < m; i++)
{
- ns[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second);
- nmax = std::max(nmax, ns[i]);
+ ns[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second);
+ nmax = std::max(nmax, ns[i]);
}
r = log2(nmax) + 1;
@@ -413,8 +428,8 @@
for (int i = 0; i < m; i++)
{
- a[i] = 0;
- b[i] = l;
+ a[i] = 0;
+ b[i] = l;
}
n = l / 2;
@@ -428,13 +443,14 @@
for (int i = 0; i < m; i++)
if (n < ns[i])
- sample.push_back(std::make_pair(S(i)[n], i));
- __gnu_sequential::sort(sample.begin(), sample.end(), lcomp, sequential_tag());
+ sample.push_back(std::make_pair(S(i)[n], i));
+ __gnu_sequential::sort(sample.begin(), sample.end(), lcomp,
+ sequential_tag());
// Conceptual infinity.
for (int i = 0; i < m; i++)
if (n >= ns[i])
- sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i));
+ sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i));
difference_type localrank = rank * m / N ;
@@ -447,86 +463,92 @@
// Further refinement.
while (n > 0)
{
- n /= 2;
+ n /= 2;
- const T* lmax = NULL;
- for (int i = 0; i < m; i++)
- {
- if (a[i] > 0)
- {
- if (!lmax)
- {
- lmax = &(S(i)[a[i] - 1]);
- }
- else
- {
- if (comp(*lmax, S(i)[a[i] - 1])) //max
- lmax = &(S(i)[a[i] - 1]);
- }
- }
- }
+ const T* lmax = NULL;
+ for (int i = 0; i < m; i++)
+ {
+ if (a[i] > 0)
+ {
+ if (!lmax)
+ {
+ lmax = &(S(i)[a[i] - 1]);
+ }
+ else
+ {
+ if (comp(*lmax, S(i)[a[i] - 1])) //max
+ lmax = &(S(i)[a[i] - 1]);
+ }
+ }
+ }
- int i;
- for (i = 0; i < m; i++)
- {
- difference_type middle = (b[i] + a[i]) / 2;
- if (lmax && middle < ns[i] && comp(S(i)[middle], *lmax))
- a[i] = std::min(a[i] + n + 1, ns[i]);
- else
- b[i] -= n + 1;
- }
+ int i;
+ for (i = 0; i < m; i++)
+ {
+ difference_type middle = (b[i] + a[i]) / 2;
+ if (lmax && middle < ns[i] && comp(S(i)[middle], *lmax))
+ a[i] = std::min(a[i] + n + 1, ns[i]);
+ else
+ b[i] -= n + 1;
+ }
- difference_type leftsize = 0, total = 0;
- for (int i = 0; i < m; i++)
- {
- leftsize += a[i] / (n + 1);
- total += l / (n + 1);
- }
+ difference_type leftsize = 0, total = 0;
+ for (int i = 0; i < m; i++)
+ {
+ leftsize += a[i] / (n + 1);
+ total += l / (n + 1);
+ }
- difference_type skew = (unsigned long long)total * rank / N - leftsize;
+ difference_type skew = (unsigned long long)total * rank / N - leftsize;
- if (skew > 0)
- {
- // Move to the left, find smallest.
- std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int> >, lexicographic_reverse<T, int, Comparator> > pq(lrcomp);
+ if (skew > 0)
+ {
+ // Move to the left, find smallest.
+ std::priority_queue<
+ std::pair<T, int>,
+ std::vector<std::pair<T, int> >,
+ lexicographic_reverse<T, int, Comparator> > pq(lrcomp);
- for (int i = 0; i < m; i++)
- if (b[i] < ns[i])
- pq.push(std::make_pair(S(i)[b[i]], i));
+ for (int i = 0; i < m; i++)
+ if (b[i] < ns[i])
+ pq.push(std::make_pair(S(i)[b[i]], i));
- for (; skew != 0 && !pq.empty(); skew--)
- {
- int source = pq.top().second;
- pq.pop();
+ for (; skew != 0 && !pq.empty(); skew--)
+ {
+ int source = pq.top().second;
+ pq.pop();
- a[source] = std::min(a[source] + n + 1, ns[source]);
- b[source] += n + 1;
+ a[source] = std::min(a[source] + n + 1, ns[source]);
+ b[source] += n + 1;
- if (b[source] < ns[source])
- pq.push(std::make_pair(S(source)[b[source]], source));
- }
- }
- else if (skew < 0)
- {
- // Move to the right, find greatest.
- std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int> >, lexicographic<T, int, Comparator> > pq(lcomp);
+ if (b[source] < ns[source])
+ pq.push(std::make_pair(S(source)[b[source]], source));
+ }
+ }
+ else if (skew < 0)
+ {
+ // Move to the right, find greatest.
+ std::priority_queue<
+ std::pair<T, int>,
+ std::vector<std::pair<T, int> >,
+ lexicographic<T, int, Comparator> > pq(lcomp);
- for (int i = 0; i < m; i++)
- if (a[i] > 0)
- pq.push(std::make_pair(S(i)[a[i] - 1], i));
+ for (int i = 0; i < m; i++)
+ if (a[i] > 0)
+ pq.push(std::make_pair(S(i)[a[i] - 1], i));
- for (; skew != 0; skew++)
- {
- int source = pq.top().second;
- pq.pop();
+ for (; skew != 0; skew++)
+ {
+ int source = pq.top().second;
+ pq.pop();
- a[source] -= n + 1;
- b[source] -= n + 1;
+ a[source] -= n + 1;
+ b[source] -= n + 1;
- if (a[source] > 0)
- pq.push(std::make_pair(S(source)[a[source] - 1], source));
- }
- }
+ if (a[source] > 0)
+ pq.push(std::make_pair(S(source)[a[source] - 1], source));
+ }
+ }
}
// Postconditions:
@@ -544,54 +566,54 @@
T maxleft, minright;
for (int i = 0; i < m; i++)
{
- if (a[i] > 0)
- {
- if (!maxleftset)
- {
- maxleft = S(i)[a[i] - 1];
- maxleftset = true;
- }
- else
- {
- // Max.
- if (comp(maxleft, S(i)[a[i] - 1]))
- maxleft = S(i)[a[i] - 1];
- }
- }
- if (b[i] < ns[i])
- {
- if (!minrightset)
- {
- minright = S(i)[b[i]];
- minrightset = true;
- }
- else
- {
- // Min.
- if (comp(S(i)[b[i]], minright))
- minright = S(i)[b[i]];
- }
- }
+ if (a[i] > 0)
+ {
+ if (!maxleftset)
+ {
+ maxleft = S(i)[a[i] - 1];
+ maxleftset = true;
+ }
+ else
+ {
+ // Max.
+ if (comp(maxleft, S(i)[a[i] - 1]))
+ maxleft = S(i)[a[i] - 1];
+ }
+ }
+ if (b[i] < ns[i])
+ {
+ if (!minrightset)
+ {
+ minright = S(i)[b[i]];
+ minrightset = true;
+ }
+ else
+ {
+ // Min.
+ if (comp(S(i)[b[i]], minright))
+ minright = S(i)[b[i]];
+ }
+ }
}
// Minright is the splitter, in any case.
if (!maxleftset || comp(minright, maxleft))
{
- // Good luck, everything is split unambigiously.
- offset = 0;
+ // Good luck, everything is split unambigiously.
+ offset = 0;
}
else
{
- // We have to calculate an offset.
- offset = 0;
+ // We have to calculate an offset.
+ offset = 0;
- for (int i = 0; i < m; i++)
- {
- difference_type lb = std::lower_bound(S(i), S(i) + ns[i], minright,
- comp) - S(i);
- offset += a[i] - lb;
- }
+ for (int i = 0; i < m; i++)
+ {
+ difference_type lb = std::lower_bound(S(i), S(i) + ns[i], minright,
+ comp) - S(i);
+ offset += a[i] - lb;
+ }
}
delete[] ns;
Index: include/parallel/algorithmfwd.h
===================================================================
--- include/parallel/algorithmfwd.h (revision 130490)
+++ include/parallel/algorithmfwd.h (working copy)
@@ -44,749 +44,837 @@
{
namespace __parallel
{
- template<typename _FIter>
+template<typename _FIter>
_FIter
adjacent_find(_FIter, _FIter);
- template<typename _FIter>
+template<typename _FIter>
_FIter
adjacent_find(_FIter, _FIter, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename _IterTag>
+template<typename _FIter, typename _IterTag>
_FIter
adjacent_find_switch(_FIter, _FIter, _IterTag);
- template<typename _RAIter>
+template<typename _RAIter>
_RAIter
adjacent_find_switch(_RAIter, _RAIter, random_access_iterator_tag);
- template<typename _FIter, typename _BiPredicate>
+template<typename _FIter, typename _BiPredicate>
_FIter
adjacent_find(_FIter, _FIter, _BiPredicate);
- template<typename _FIter, typename _BiPredicate>
+template<typename _FIter, typename _BiPredicate>
_FIter
adjacent_find(_FIter, _FIter, _BiPredicate,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _FIter, typename _BiPredicate, typename _IterTag>
+template<typename _FIter, typename _BiPredicate, typename _IterTag>
_FIter
adjacent_find_switch(_FIter, _FIter, _BiPredicate, _IterTag);
- template<typename _RAIter, typename _BiPredicate>
+template<typename _RAIter, typename _BiPredicate>
_RAIter
adjacent_find_switch(_RAIter, _RAIter, _BiPredicate,
- random_access_iterator_tag);
+ random_access_iterator_tag);
- template<typename _IIter, typename _Tp>
+template<typename _IIter, typename _Tp>
typename iterator_traits<_IIter>::difference_type
count(_IIter, _IIter, const _Tp&);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
typename iterator_traits<_IIter>::difference_type
count(_IIter, _IIter, const T&, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
typename iterator_traits<_IIter>::difference_type
count(_IIter, _IIter, const T&, __gnu_parallel::parallelism);
- template<typename _IIter, typename T, typename _IterTag>
+template<typename _IIter, typename T, typename _IterTag>
typename iterator_traits<_IIter>::difference_type
count_switch(_IIter, _IIter, const T&, _IterTag);
- template<typename _RAIter, typename T>
+template<typename _RAIter, typename T>
typename iterator_traits<_RAIter>::difference_type
count_switch(_RAIter, _RAIter, const T&, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _IIter, typename Predicate>
+template<typename _IIter, typename Predicate>
typename iterator_traits<_IIter>::difference_type
count_if(_IIter, _IIter, Predicate);
- template<typename _IIter, typename Predicate>
+template<typename _IIter, typename Predicate>
typename iterator_traits<_IIter>::difference_type
count_if(_IIter, _IIter, Predicate, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename Predicate>
+template<typename _IIter, typename Predicate>
typename iterator_traits<_IIter>::difference_type
count_if(_IIter, _IIter, Predicate, __gnu_parallel::parallelism);
- template<typename _IIter, typename Predicate, typename _IterTag>
+template<typename _IIter, typename Predicate, typename _IterTag>
typename iterator_traits<_IIter>::difference_type
count_if_switch(_IIter, _IIter, Predicate, _IterTag);
- template<typename _RAIter, typename Predicate>
+template<typename _RAIter, typename Predicate>
typename iterator_traits<_RAIter>::difference_type
count_if_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
// algobase.h
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
bool
equal(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
bool
equal(_IIter1, _IIter1, _IIter2, Predicate, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
bool
equal(_IIter1, _IIter1, _IIter2);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
bool
equal(_IIter1, _IIter1, _IIter2, Predicate);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
_IIter
find(_IIter, _IIter, const T&, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
_IIter
find(_IIter, _IIter, const T& val);
- template<typename _IIter, typename T, typename _IterTag>
+template<typename _IIter, typename T, typename _IterTag>
_IIter
find_switch(_IIter, _IIter, const T&, _IterTag);
- template<typename _RAIter, typename T>
+template<typename _RAIter, typename T>
_RAIter
find_switch(_RAIter, _RAIter, const T&, random_access_iterator_tag);
- template<typename _IIter, typename Predicate>
+template<typename _IIter, typename Predicate>
_IIter
find_if(_IIter, _IIter, Predicate, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename Predicate>
+template<typename _IIter, typename Predicate>
_IIter
find_if(_IIter, _IIter, Predicate);
- template<typename _IIter, typename Predicate, typename _IterTag>
+template<typename _IIter, typename Predicate, typename _IterTag>
_IIter
find_if_switch(_IIter, _IIter, Predicate, _IterTag);
- template<typename _RAIter, typename Predicate>
+template<typename _RAIter, typename Predicate>
_RAIter
find_if_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag);
- template<typename _IIter, typename _FIter>
+template<typename _IIter, typename _FIter>
_IIter
- find_first_of(_IIter, _IIter, _FIter, _FIter, __gnu_parallel::sequential_tag);
+ find_first_of(_IIter, _IIter, _FIter, _FIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _FIter, typename _BiPredicate>
+template<typename _IIter, typename _FIter, typename _BiPredicate>
_IIter
- find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate, __gnu_parallel::sequential_tag);
+ find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _FIter, typename _BiPredicate>
+template<typename _IIter, typename _FIter, typename _BiPredicate>
_IIter
find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate);
- template<typename _IIter, typename _FIter>
+template<typename _IIter, typename _FIter>
_IIter
find_first_of(_IIter, _IIter, _FIter, _FIter);
- template<typename _IIter, typename _FIter, typename _IterTag1, typename _IterTag2>
+template<typename _IIter, typename _FIter, typename _IterTag1,
+ typename _IterTag2>
_IIter
find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _IterTag1, _IterTag2);
- template<typename _RAIter, typename _FIter, typename _BiPredicate, typename _IterTag>
+template<typename _RAIter, typename _FIter, typename _BiPredicate,
+ typename _IterTag>
_RAIter
- find_first_of_switch(_RAIter, _RAIter, _FIter, _FIter, _BiPredicate, random_access_iterator_tag, _IterTag);
+ find_first_of_switch(_RAIter, _RAIter, _FIter, _FIter, _BiPredicate,
+ random_access_iterator_tag, _IterTag);
- template<typename _IIter, typename _FIter, typename _BiPredicate, typename _IterTag1, typename _IterTag2>
+template<typename _IIter, typename _FIter, typename _BiPredicate,
+ typename _IterTag1, typename _IterTag2>
_IIter
- find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _BiPredicate, _IterTag1, _IterTag2);
+ find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _BiPredicate,
+ _IterTag1, _IterTag2);
- template<typename _IIter, typename Function>
+template<typename _IIter, typename Function>
Function
for_each(_IIter, _IIter, Function);
- template<typename _IIter, typename Function>
+template<typename _IIter, typename Function>
Function
for_each(_IIter, _IIter, Function, __gnu_parallel::sequential_tag);
- template<typename Iterator, typename Function>
+template<typename Iterator, typename Function>
Function
for_each(Iterator, Iterator, Function, __gnu_parallel::parallelism);
- template<typename _IIter, typename Function, typename _IterTag>
+template<typename _IIter, typename Function, typename _IterTag>
Function
for_each_switch(_IIter, _IIter, Function, _IterTag);
- template<typename _RAIter, typename Function>
+template<typename _RAIter, typename Function>
Function
for_each_switch(_RAIter, _RAIter, Function, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _FIter, typename Generator>
+template<typename _FIter, typename Generator>
void
generate(_FIter, _FIter, Generator);
- template<typename _FIter, typename Generator>
+template<typename _FIter, typename Generator>
void
generate(_FIter, _FIter, Generator, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename Generator>
+template<typename _FIter, typename Generator>
void
generate(_FIter, _FIter, Generator, __gnu_parallel::parallelism);
- template<typename _FIter, typename Generator, typename _IterTag>
+template<typename _FIter, typename Generator, typename _IterTag>
void
generate_switch(_FIter, _FIter, Generator, _IterTag);
- template<typename _RAIter, typename Generator>
+template<typename _RAIter, typename Generator>
void
generate_switch(_RAIter, _RAIter, Generator, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _OIter, typename Size, typename Generator>
+template<typename _OIter, typename Size, typename Generator>
_OIter
generate_n(_OIter, Size, Generator);
- template<typename _OIter, typename Size, typename Generator>
+template<typename _OIter, typename Size, typename Generator>
_OIter
generate_n(_OIter, Size, Generator, __gnu_parallel::sequential_tag);
- template<typename _OIter, typename Size, typename Generator>
+template<typename _OIter, typename Size, typename Generator>
_OIter
generate_n(_OIter, Size, Generator, __gnu_parallel::parallelism);
- template<typename _OIter, typename Size, typename Generator, typename _IterTag>
+template<typename _OIter, typename Size, typename Generator, typename _IterTag>
_OIter
generate_n_switch(_OIter, Size, Generator, _IterTag);
- template<typename _RAIter, typename Size, typename Generator>
+template<typename _RAIter, typename Size, typename Generator>
_RAIter
generate_n_switch(_RAIter, Size, Generator, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
bool
- lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, __gnu_parallel::sequential_tag);
+ lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
bool
- lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, Predicate, __gnu_parallel::sequential_tag);
+ lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
bool
lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
bool
lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _IterTag1, typename _IterTag2>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _IterTag1, typename _IterTag2>
bool
- lexicographical_compare_switch(_IIter1, _IIter1, _IIter2, _IIter2, Predicate, _IterTag1, _IterTag2);
+ lexicographical_compare_switch(_IIter1, _IIter1, _IIter2, _IIter2,
+ Predicate, _IterTag1, _IterTag2);
- template<typename _RAIter1, typename _RAIter2, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Predicate>
bool
- lexicographical_compare_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Predicate, random_access_iterator_tag, random_access_iterator_tag);
+ lexicographical_compare_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ Predicate, random_access_iterator_tag,
+ random_access_iterator_tag);
// algo.h
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
pair<_IIter1, _IIter2>
mismatch(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
pair<_IIter1, _IIter2>
- mismatch(_IIter1, _IIter1, _IIter2, Predicate, __gnu_parallel::sequential_tag);
+ mismatch(_IIter1, _IIter1, _IIter2, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2>
+template<typename _IIter1, typename _IIter2>
pair<_IIter1, _IIter2>
mismatch(_IIter1, _IIter1, _IIter2);
- template<typename _IIter1, typename _IIter2, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename Predicate>
pair<_IIter1, _IIter2>
mismatch(_IIter1, _IIter1, _IIter2, Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _IterTag1, typename _IterTag2>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _IterTag1, typename _IterTag2>
pair<_IIter1, _IIter2>
mismatch_switch(_IIter1, _IIter1, _IIter2, Predicate, _IterTag1, _IterTag2);
- template<typename _RAIter1, typename _RAIter2, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Predicate>
pair<_RAIter1, _RAIter2>
- mismatch_switch(_RAIter1, _RAIter1, _RAIter2, Predicate, random_access_iterator_tag, random_access_iterator_tag);
+ mismatch_switch(_RAIter1, _RAIter1, _RAIter2, Predicate,
+ random_access_iterator_tag, random_access_iterator_tag);
- template<typename _FIter1, typename _FIter2>
+template<typename _FIter1, typename _FIter2>
_FIter1
search(_FIter1, _FIter1, _FIter2, _FIter2, __gnu_parallel::sequential_tag);
- template<typename _FIter1, typename _FIter2>
+template<typename _FIter1, typename _FIter2>
_FIter1
search(_FIter1, _FIter1, _FIter2, _FIter2);
- template<typename _FIter1, typename _FIter2, typename _BiPredicate>
+template<typename _FIter1, typename _FIter2, typename _BiPredicate>
_FIter1
- search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate, __gnu_parallel::sequential_tag);
+ search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate,
+ __gnu_parallel::sequential_tag);
- template<typename _FIter1, typename _FIter2, typename _BiPredicate>
+template<typename _FIter1, typename _FIter2, typename _BiPredicate>
_FIter1
search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate);
- template<typename _RAIter1, typename _RAIter2>
+template<typename _RAIter1, typename _RAIter2>
_RAIter1
- search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, random_access_iterator_tag, random_access_iterator_tag);
+ search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ random_access_iterator_tag, random_access_iterator_tag);
- template<typename _FIter1, typename _FIter2, typename _IterTag1, typename _IterTag2>
+template<typename _FIter1, typename _FIter2, typename _IterTag1,
+ typename _IterTag2>
_FIter1
search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _IterTag1, _IterTag2);
- template<typename _RAIter1, typename _RAIter2, typename _BiPredicate>
+template<typename _RAIter1, typename _RAIter2, typename _BiPredicate>
_RAIter1
- search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _BiPredicate , random_access_iterator_tag, random_access_iterator_tag);
+ search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _BiPredicate,
+ random_access_iterator_tag, random_access_iterator_tag);
- template<typename _FIter1, typename _FIter2, typename _BiPredicate, typename _IterTag1, typename _IterTag2>
+template<typename _FIter1, typename _FIter2, typename _BiPredicate,
+ typename _IterTag1, typename _IterTag2>
_FIter1
- search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate, _IterTag1, _IterTag2);
+ search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate,
+ _IterTag1, _IterTag2);
- template<typename _FIter, typename Integer, typename T>
+template<typename _FIter, typename Integer, typename T>
_FIter
search_n(_FIter, _FIter, Integer, const T&, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename Integer, typename T, typename _BiPredicate>
+template<typename _FIter, typename Integer, typename T, typename _BiPredicate>
_FIter
- search_n(_FIter, _FIter, Integer, const T&, _BiPredicate, __gnu_parallel::sequential_tag);
-
- template<typename _FIter, typename Integer, typename T>
+ search_n(_FIter, _FIter, Integer, const T&, _BiPredicate,
+ __gnu_parallel::sequential_tag);
+
+template<typename _FIter, typename Integer, typename T>
_FIter
search_n(_FIter, _FIter, Integer, const T& val);
- template<typename _FIter, typename Integer, typename T, typename _BiPredicate>
+template<typename _FIter, typename Integer, typename T, typename _BiPredicate>
_FIter
search_n(_FIter, _FIter, Integer, const T&, _BiPredicate);
- template<typename _RAIter, typename Integer, typename T, typename _BiPredicate>
+template<typename _RAIter, typename Integer, typename T, typename _BiPredicate>
_RAIter
- search_n_switch(_RAIter, _RAIter, Integer, const T&, _BiPredicate, random_access_iterator_tag);
+ search_n_switch(_RAIter, _RAIter, Integer, const T&, _BiPredicate,
+ random_access_iterator_tag);
- template<typename _FIter, typename Integer, typename T, typename _BiPredicate, typename _IterTag>
+template<typename _FIter, typename Integer, typename T, typename _BiPredicate,
+ typename _IterTag>
_FIter
search_n_switch(_FIter, _FIter, Integer, const T&, _BiPredicate, _IterTag);
- template<typename _IIter, typename _OIter, typename UnaryOperation>
+template<typename _IIter, typename _OIter, typename UnaryOperation>
_OIter
transform(_IIter, _IIter, _OIter, UnaryOperation);
- template<typename _IIter, typename _OIter, typename UnaryOperation>
+template<typename _IIter, typename _OIter, typename UnaryOperation>
_OIter
transform(_IIter, _IIter, _OIter, UnaryOperation,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter, typename UnaryOperation>
+template<typename _IIter, typename _OIter, typename UnaryOperation>
_OIter
transform(_IIter, _IIter, _OIter, UnaryOperation,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _IIter, typename _OIter, typename UnaryOperation, typename _IterTag1, typename _IterTag2>
+template<typename _IIter, typename _OIter, typename UnaryOperation,
+ typename _IterTag1, typename _IterTag2>
_OIter
transform1_switch(_IIter, _IIter, _OIter, UnaryOperation,
- _IterTag1, _IterTag2);
+ _IterTag1, _IterTag2);
- template<typename _RAIIter, typename _RAOIter, typename UnaryOperation>
+template<typename _RAIIter, typename _RAOIter, typename UnaryOperation>
_RAOIter
transform1_switch(_RAIIter, _RAIIter, _RAOIter, UnaryOperation,
- random_access_iterator_tag, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ random_access_iterator_tag, random_access_iterator_tag,
+ __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation>
_OIter
transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation>
_OIter
transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation>
_OIter
transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _RAIter1, typename _RAIter2, typename _RAIter3, typename _BiOperation>
+template<typename _RAIter1, typename _RAIter2, typename _RAIter3,
+ typename _BiOperation>
_RAIter3
transform2_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter3, _BiOperation,
- random_access_iterator_tag, random_access_iterator_tag,
- random_access_iterator_tag,
- __gnu_parallel::parallelism parallelism_tag);
+ random_access_iterator_tag, random_access_iterator_tag,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism parallelism_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _BiOperation, typename tag1, typename tag2, typename tag3>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _BiOperation, typename tag1, typename tag2, typename tag3>
_OIter
transform2_switch(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation,
- tag1, tag2, tag3);
+ tag1, tag2, tag3);
- template<typename _FIter, typename T>
+template<typename _FIter, typename T>
void
replace(_FIter, _FIter, const T&, const T&);
- template<typename _FIter, typename T>
+template<typename _FIter, typename T>
void
replace(_FIter, _FIter, const T&, const T&,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _FIter, typename T>
+template<typename _FIter, typename T>
void
replace(_FIter, _FIter, const T&, const T&, __gnu_parallel::parallelism);
- template<typename _FIter, typename T, typename _IterTag>
+template<typename _FIter, typename T, typename _IterTag>
void
replace_switch(_FIter, _FIter, const T&, const T&, _IterTag);
- template<typename _RAIter, typename T>
+template<typename _RAIter, typename T>
void
replace_switch(_RAIter, _RAIter, const T&, const T&,
- random_access_iterator_tag, __gnu_parallel::parallelism);
+ random_access_iterator_tag, __gnu_parallel::parallelism);
- template<typename _FIter, typename Predicate, typename T>
+template<typename _FIter, typename Predicate, typename T>
void
replace_if(_FIter, _FIter, Predicate, const T&);
- template<typename _FIter, typename Predicate, typename T>
+template<typename _FIter, typename Predicate, typename T>
void
replace_if(_FIter, _FIter, Predicate, const T&,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _FIter, typename Predicate, typename T>
+template<typename _FIter, typename Predicate, typename T>
void
replace_if(_FIter, _FIter, Predicate, const T&,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _FIter, typename Predicate, typename T, typename _IterTag>
+template<typename _FIter, typename Predicate, typename T, typename _IterTag>
void
replace_if_switch(_FIter, _FIter, Predicate, const T&, _IterTag);
- template<typename _RAIter, typename Predicate, typename T>
+template<typename _RAIter, typename Predicate, typename T>
void
replace_if_switch(_RAIter, _RAIter, Predicate, const T&,
- random_access_iterator_tag, __gnu_parallel::parallelism);
+ random_access_iterator_tag, __gnu_parallel::parallelism);
- template<typename _FIter>
+template<typename _FIter>
_FIter
max_element(_FIter, _FIter);
- template<typename _FIter>
+template<typename _FIter>
_FIter
max_element(_FIter, _FIter, __gnu_parallel::sequential_tag);
- template<typename _FIter>
+template<typename _FIter>
_FIter
max_element(_FIter, _FIter, __gnu_parallel::parallelism parallelism_tag);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
max_element(_FIter, _FIter, _Compare);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
max_element(_FIter, _FIter, _Compare, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
max_element(_FIter, _FIter, _Compare, __gnu_parallel::parallelism);
- template<typename _FIter, typename _Compare, typename _IterTag>
+template<typename _FIter, typename _Compare, typename _IterTag>
_FIter
max_element_switch(_FIter, _FIter, _Compare, _IterTag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
_RAIter
max_element_switch(_RAIter, _RAIter, _Compare, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare>
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare>
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare,
+ typename _IterTag1, typename _IterTag2, typename _IterTag3>
_OIter
merge_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare,
- _IterTag1, _IterTag2, _IterTag3);
+ _IterTag1, _IterTag2, _IterTag3);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename _Compare>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename _Compare>
_OIter
merge_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare,
- random_access_iterator_tag, random_access_iterator_tag,
- random_access_iterator_tag);
+ random_access_iterator_tag, random_access_iterator_tag,
+ random_access_iterator_tag);
- template<typename _FIter>
+template<typename _FIter>
_FIter
min_element(_FIter, _FIter);
- template<typename _FIter>
+template<typename _FIter>
_FIter
min_element(_FIter, _FIter, __gnu_parallel::sequential_tag);
- template<typename _FIter>
+template<typename _FIter>
_FIter
min_element(_FIter, _FIter, __gnu_parallel::parallelism parallelism_tag);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
min_element(_FIter, _FIter, _Compare);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
min_element(_FIter, _FIter, _Compare, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename _Compare>
+template<typename _FIter, typename _Compare>
_FIter
min_element(_FIter, _FIter, _Compare, __gnu_parallel::parallelism);
- template<typename _FIter, typename _Compare, typename _IterTag>
+template<typename _FIter, typename _Compare, typename _IterTag>
_FIter
min_element_switch(_FIter, _FIter, _Compare, _IterTag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
_RAIter
min_element_switch(_RAIter, _RAIter, _Compare, random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _RAIter>
+template<typename _RAIter>
void
nth_element(_RAIter, _RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
- nth_element(_RAIter, _RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
+ nth_element(_RAIter, _RAIter, _RAIter, _Compare,
+ __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
nth_element(_RAIter, _RAIter, _RAIter, _Compare);
- template<typename _RAIter>
+template<typename _RAIter>
void
nth_element(_RAIter, _RAIter, _RAIter);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
- partial_sort(_RAIter, _RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
+ partial_sort(_RAIter, _RAIter, _RAIter, _Compare,
+ __gnu_parallel::sequential_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
partial_sort(_RAIter, _RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
partial_sort(_RAIter, _RAIter, _RAIter, _Compare);
- template<typename _RAIter>
+template<typename _RAIter>
void
partial_sort(_RAIter, _RAIter, _RAIter);
- template<typename _FIter, typename Predicate>
+template<typename _FIter, typename Predicate>
_FIter
partition(_FIter, _FIter, Predicate, __gnu_parallel::sequential_tag);
- template<typename _FIter, typename Predicate>
+template<typename _FIter, typename Predicate>
_FIter
partition(_FIter, _FIter, Predicate);
- template<typename _FIter, typename Predicate, typename _IterTag>
+template<typename _FIter, typename Predicate, typename _IterTag>
_FIter
partition_switch(_FIter, _FIter, Predicate, _IterTag);
- template<typename _RAIter, typename Predicate>
+template<typename _RAIter, typename Predicate>
_RAIter
partition_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
random_shuffle(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename RandomNumberGenerator>
+template<typename _RAIter, typename RandomNumberGenerator>
void
- random_shuffle(_RAIter, _RAIter, RandomNumberGenerator& rand, __gnu_parallel::sequential_tag);
+ random_shuffle(_RAIter, _RAIter, RandomNumberGenerator& rand,
+ __gnu_parallel::sequential_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
random_shuffle(_RAIter, _RAIter);
- template<typename _RAIter, typename RandomNumberGenerator>
+template<typename _RAIter, typename RandomNumberGenerator>
void
random_shuffle(_RAIter, _RAIter, RandomNumberGenerator& rand);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
- set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
- set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _OIter,
+ typename _IterTag1, typename _IterTag2, typename _IterTag3>
_OIter
- set_union_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
+ set_union_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ _IterTag1, _IterTag2, _IterTag3);
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Output_RAIter,
+ typename Predicate>
Output_RAIter
- set_union_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ set_union_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter,
+ Predicate, random_access_iterator_tag,
+ random_access_iterator_tag, random_access_iterator_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
- set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
- set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _OIter,
+ typename _IterTag1, typename _IterTag2, typename _IterTag3>
_OIter
- set_intersection_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
+ set_intersection_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ Predicate, _IterTag1, _IterTag2, _IterTag3);
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Output_RAIter,
+ typename Predicate>
Output_RAIter
- set_intersection_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ set_intersection_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ Output_RAIter, Predicate,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
- set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
- set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ Predicate, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
- set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
+ set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _OIter,
+ typename _IterTag1, typename _IterTag2, typename _IterTag3>
_OIter
- set_symmetric_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
+ set_symmetric_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ Predicate, _IterTag1, _IterTag2, _IterTag3);
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Output_RAIter,
+ typename Predicate>
Output_RAIter
- set_symmetric_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ set_symmetric_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ Output_RAIter, Predicate,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
- set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag);
+ set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
- set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename _OIter>
+template<typename _IIter1, typename _IIter2, typename _OIter>
_OIter
set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter);
- template<typename _IIter1, typename _IIter2, typename _OIter, typename Predicate>
+template<typename _IIter1, typename _IIter2, typename _OIter,
+ typename Predicate>
_OIter
set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate);
- template<typename _IIter1, typename _IIter2, typename Predicate, typename _OIter, typename _IterTag1, typename _IterTag2, typename _IterTag3>
+template<typename _IIter1, typename _IIter2, typename Predicate,
+ typename _OIter,
+ typename _IterTag1, typename _IterTag2, typename _IterTag3>
_OIter
- set_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, _IterTag1, _IterTag2, _IterTag3);
+ set_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate,
+ _IterTag1, _IterTag2, _IterTag3);
- template<typename _RAIter1, typename _RAIter2, typename Output_RAIter, typename Predicate>
+template<typename _RAIter1, typename _RAIter2, typename Output_RAIter,
+ typename Predicate>
Output_RAIter
- set_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, Output_RAIter, Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag);
+ set_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2,
+ Output_RAIter, Predicate,
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ random_access_iterator_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
sort(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
sort(_RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
sort(_RAIter, _RAIter);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
sort(_RAIter, _RAIter, _Compare);
- template<typename _RAIter>
+template<typename _RAIter>
void
stable_sort(_RAIter, _RAIter, __gnu_parallel::sequential_tag);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
stable_sort(_RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag);
- template<typename _RAIter>
+template<typename _RAIter>
void
stable_sort(_RAIter, _RAIter);
- template<typename _RAIter, typename _Compare>
+template<typename _RAIter, typename _Compare>
void
stable_sort(_RAIter, _RAIter, _Compare);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
_OIter
unique_copy(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter, typename Predicate>
+template<typename _IIter, typename _OIter, typename Predicate>
_OIter
- unique_copy(_IIter, _IIter, _OIter, Predicate, __gnu_parallel::sequential_tag);
+ unique_copy(_IIter, _IIter, _OIter, Predicate,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
_OIter
unique_copy(_IIter, _IIter, _OIter);
- template<typename _IIter, typename _OIter, typename Predicate>
+template<typename _IIter, typename _OIter, typename Predicate>
_OIter
unique_copy(_IIter, _IIter, _OIter, Predicate);
- template<typename _IIter, typename _OIter, typename Predicate, typename _IterTag1, typename _IterTag2>
+template<typename _IIter, typename _OIter, typename Predicate,
+ typename _IterTag1, typename _IterTag2>
_OIter
unique_copy_switch(_IIter, _IIter, _OIter, Predicate, _IterTag1, _IterTag2);
- template<typename _RAIter, typename RandomAccess_OIter, typename Predicate>
+template<typename _RAIter, typename RandomAccess_OIter, typename Predicate>
RandomAccess_OIter
unique_copy_switch(_RAIter, _RAIter, RandomAccess_OIter, Predicate,
- random_access_iterator_tag, random_access_iterator_tag);
+ random_access_iterator_tag, random_access_iterator_tag);
} // end namespace __parallel
} // end namespace std
Index: include/parallel/for_each_selectors.h
===================================================================
--- include/parallel/for_each_selectors.h (revision 130490)
+++ include/parallel/for_each_selectors.h (working copy)
@@ -45,7 +45,7 @@
{
/** @brief Generic selector for embarrassingly parallel functions. */
- template<typename It>
+template<typename It>
struct generic_for_each_selector
{
/** @brief Iterator on last element processed; needed for some
@@ -56,13 +56,13 @@
/** @brief std::for_each() selector. */
- template<typename It>
+template<typename It>
struct for_each_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object. */
- template<typename Op>
+ template<typename Op>
inline bool operator()(Op& o, It i)
{
o(*i);
@@ -71,13 +71,13 @@
};
/** @brief std::generate() selector. */
- template<typename It>
+template<typename It>
struct generate_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object. */
- template<typename Op>
+ template<typename Op>
inline bool operator()(Op& o, It i)
{
*i = o();
@@ -86,13 +86,13 @@
};
/** @brief std::fill() selector. */
- template<typename It>
+template<typename It>
struct fill_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param v Current value.
* @param i Iterator referencing object. */
- template<typename Val>
+ template<typename Val>
inline bool operator()(Val& v, It i)
{
*i = v;
@@ -101,13 +101,13 @@
};
/** @brief std::transform() selector, one input sequence variant. */
- template<typename It>
+template<typename It>
struct transform1_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object. */
- template<typename Op>
+ template<typename Op>
inline bool operator()(Op& o, It i)
{
*i.second = o(*i.first);
@@ -116,13 +116,13 @@
};
/** @brief std::transform() selector, two input sequences variant. */
- template<typename It>
+template<typename It>
struct transform2_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object. */
- template<typename Op>
+ template<typename Op>
inline bool operator()(Op& o, It i)
{
*i.third = o(*i.first, *i.second);
@@ -131,7 +131,7 @@
};
/** @brief std::replace() selector. */
- template<typename It, typename T>
+template<typename It, typename T>
struct replace_selector : public generic_for_each_selector<It>
{
/** @brief Value to replace with. */
@@ -153,7 +153,7 @@
};
/** @brief std::replace() selector. */
- template<typename It, typename Op, typename T>
+template<typename It, typename Op, typename T>
struct replace_if_selector : public generic_for_each_selector<It>
{
/** @brief Value to replace with. */
@@ -175,46 +175,47 @@
};
/** @brief std::count() selector. */
- template<typename It, typename Diff>
+template<typename It, typename Diff>
struct count_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param v Current value.
* @param i Iterator referencing object.
* @return 1 if count, 0 if does not count. */
- template<typename Val>
+ template<typename Val>
inline Diff operator()(Val& v, It i)
{ return (v == *i) ? 1 : 0; }
};
/** @brief std::count_if () selector. */
- template<typename It, typename Diff>
+template<typename It, typename Diff>
struct count_if_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator.
* @param i Iterator referencing object.
* @return 1 if count, 0 if does not count. */
- template<typename Op>
+ template<typename Op>
inline Diff operator()(Op& o, It i)
{ return (o(*i)) ? 1 : 0; }
};
/** @brief std::accumulate() selector. */
- template<typename It>
+template<typename It>
struct accumulate_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator (unused).
* @param i Iterator referencing object.
* @return The current value. */
- template<typename Op>
- inline typename std::iterator_traits<It>::value_type operator()(Op o, It i)
+ template<typename Op>
+ inline typename std::iterator_traits<It>::value_type operator()
+ (Op o, It i)
{ return *i; }
};
/** @brief std::inner_product() selector. */
- template<typename It, typename It2, typename T>
+template<typename It, typename It2, typename T>
struct inner_product_selector : public generic_for_each_selector<It>
{
/** @brief Begin iterator of first sequence. */
@@ -226,29 +227,31 @@
/** @brief Constructor.
* @param b1 Begin iterator of first sequence.
* @param b2 Begin iterator of second sequence. */
- explicit inner_product_selector(It b1, It2 b2) : begin1_iterator(b1), begin2_iterator(b2) { }
+ explicit inner_product_selector(It b1, It2 b2) : begin1_iterator(b1),
+ begin2_iterator(b2) { }
/** @brief Functor execution.
* @param mult Multiplication functor.
* @param current Iterator referencing object.
* @return Inner product elemental result. */
- template<typename Op>
+ template<typename Op>
inline T operator()(Op mult, It current)
{
- typename std::iterator_traits<It>::difference_type position = current - begin1_iterator;
+ typename std::iterator_traits<It>::difference_type position
+ = current - begin1_iterator;
return mult(*current, *(begin2_iterator + position));
}
};
/** @brief Selector that just returns the passed iterator. */
- template<typename It>
+template<typename It>
struct identity_selector : public generic_for_each_selector<It>
{
/** @brief Functor execution.
* @param o Operator (unused).
* @param i Iterator referencing object.
* @return Passed iterator. */
- template<typename Op>
+ template<typename Op>
inline It operator()(Op o, It i)
{ return i; }
};
@@ -256,10 +259,10 @@
/** @brief Selector that returns the difference between two adjacent
* elements.
*/
- template<typename It>
+template<typename It>
struct adjacent_difference_selector : public generic_for_each_selector<It>
{
- template<typename Op>
+ template<typename Op>
inline bool operator()(Op& o, It i)
{
typename It::first_type go_back_one = i.first;
@@ -279,7 +282,7 @@
{
/** @brief Functor execution.
* @param i Iterator referencing object. */
- template<typename It>
+ template<typename It>
inline void operator()(It i)
{ }
};
@@ -292,7 +295,7 @@
};
/** @brief Reduction for finding the maximum element, using a comparator. */
- template<typename Comp, typename It>
+template<typename Comp, typename It>
struct min_element_reduct
{
Comp& comp;
@@ -310,7 +313,7 @@
};
/** @brief Reduction for finding the maximum element, using a comparator. */
- template<typename Comp, typename It>
+template<typename Comp, typename It>
struct max_element_reduct
{
Comp& comp;
@@ -328,14 +331,14 @@
};
/** @brief General reduction, using a binary operator. */
- template<typename BinOp>
+template<typename BinOp>
struct accumulate_binop_reduct
{
BinOp& binop;
explicit accumulate_binop_reduct(BinOp& b) : binop(b) {}
- template<typename Result, typename Addend>
+ template<typename Result, typename Addend>
Result operator()(const Result& x, const Addend& y) { return binop(x, y); }
};
}
Index: include/parallel/balanced_quicksort.h
===================================================================
--- include/parallel/balanced_quicksort.h (revision 130490)
+++ include/parallel/balanced_quicksort.h (working copy)
@@ -329,7 +329,8 @@
{
// Right side larger.
if ((split_pos2) != end)
- tl.leftover_parts.push_front(std::make_pair(split_pos2, end));
+ tl.leftover_parts.push_front
+ (std::make_pair(split_pos2, end));
//current.first = begin; //already set anyway
current.second = split_pos1;
Index: include/parallel/merge.h
===================================================================
--- include/parallel/merge.h (revision 130490)
+++ include/parallel/merge.h (working copy)
@@ -56,30 +56,37 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename _DifferenceTp, typename Comparator>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputIterator, typename _DifferenceTp,
+ typename Comparator>
OutputIterator
- merge_advance_usual(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
+ merge_advance_usual(RandomAccessIterator1& begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2,
+ RandomAccessIterator2 end2,
+ OutputIterator target,
+ _DifferenceTp max_length, Comparator comp)
{
typedef _DifferenceTp difference_type;
while (begin1 != end1 && begin2 != end2 && max_length > 0)
{
- // array1[i1] < array0[i0]
- if (comp(*begin2, *begin1))
- *target++ = *begin2++;
- else
- *target++ = *begin1++;
- max_length--;
+ // array1[i1] < array0[i0]
+ if (comp(*begin2, *begin1))
+ *target++ = *begin2++;
+ else
+ *target++ = *begin1++;
+ max_length--;
}
if (begin1 != end1)
{
- target = std::copy(begin1, begin1 + max_length, target);
- begin1 += max_length;
+ target = std::copy(begin1, begin1 + max_length, target);
+ begin1 += max_length;
}
else
{
- target = std::copy(begin2, begin2 + max_length, target);
- begin2 += max_length;
+ target = std::copy(begin2, begin2 + max_length, target);
+ begin2 += max_length;
}
return target;
}
@@ -99,13 +106,20 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename _DifferenceTp, typename Comparator>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputIterator, typename _DifferenceTp,
+ typename Comparator>
OutputIterator
- merge_advance_movc(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
+ merge_advance_movc(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
+ OutputIterator target, _DifferenceTp max_length,
+ Comparator comp)
{
typedef _DifferenceTp difference_type;
- typedef typename std::iterator_traits<RandomAccessIterator1>::value_type value_type1;
- typedef typename std::iterator_traits<RandomAccessIterator2>::value_type value_type2;
+ typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
+ value_type1;
+ typedef typename std::iterator_traits<RandomAccessIterator2>::value_type
+ value_type2;
#if _GLIBCXX_ASSERTIONS
_GLIBCXX_PARALLEL_ASSERT(max_length >= 0);
@@ -113,35 +127,35 @@
while (begin1 != end1 && begin2 != end2 && max_length > 0)
{
- RandomAccessIterator1 next1 = begin1 + 1;
- RandomAccessIterator2 next2 = begin2 + 1;
- value_type1 element1 = *begin1;
- value_type2 element2 = *begin2;
+ RandomAccessIterator1 next1 = begin1 + 1;
+ RandomAccessIterator2 next2 = begin2 + 1;
+ value_type1 element1 = *begin1;
+ value_type2 element2 = *begin2;
- if (comp(element2, element1))
- {
- element1 = element2;
- begin2 = next2;
- }
- else
- {
- begin1 = next1;
- }
+ if (comp(element2, element1))
+ {
+ element1 = element2;
+ begin2 = next2;
+ }
+ else
+ {
+ begin1 = next1;
+ }
- *target = element1;
+ *target = element1;
- target++;
- max_length--;
+ target++;
+ max_length--;
}
if (begin1 != end1)
{
- target = std::copy(begin1, begin1 + max_length, target);
- begin1 += max_length;
+ target = std::copy(begin1, begin1 + max_length, target);
+ begin1 += max_length;
}
else
{
- target = std::copy(begin2, begin2 + max_length, target);
- begin2 += max_length;
+ target = std::copy(begin2, begin2 + max_length, target);
+ begin2 += max_length;
}
return target;
}
@@ -160,13 +174,19 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename OutputIterator, typename _DifferenceTp, typename Comparator>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename OutputIterator, typename _DifferenceTp,
+ typename Comparator>
inline OutputIterator
- merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
+ merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
+ OutputIterator target, _DifferenceTp max_length,
+ Comparator comp)
{
_GLIBCXX_CALL(max_length)
- return merge_advance_movc(begin1, end1, begin2, end2, target, max_length, comp);
+ return merge_advance_movc
+ (begin1, end1, begin2, end2, target, max_length, comp);
}
/** @brief Merge routine fallback to sequential in case the
@@ -179,12 +199,17 @@
* @param max_length Maximum number of elements to merge.
* @param comp Comparator.
* @return Output end iterator. */
- template<typename RandomAccessIterator1, typename RandomAccessIterator2, typename RandomAccessIterator3, typename Comparator>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator2,
+ typename RandomAccessIterator3, typename Comparator>
inline RandomAccessIterator3
- parallel_merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
- RandomAccessIterator2& begin2, RandomAccessIterator2 end2, //different iterators, parallel implementation not available
- RandomAccessIterator3 target,
- typename std::iterator_traits<RandomAccessIterator1>::difference_type max_length, Comparator comp)
+ parallel_merge_advance(RandomAccessIterator1& begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator2& begin2,
+ //different iterators, parallelism not available
+ RandomAccessIterator2 end2,
+ RandomAccessIterator3 target,
+ typename std::iterator_traits<RandomAccessIterator1>
+ ::difference_type max_length, Comparator comp)
{
return merge_advance(begin1, end1, begin2, end2, target, max_length, comp);
}
@@ -204,22 +229,31 @@
* @param comp Comparator.
* @return Output end iterator.
*/
- template<typename RandomAccessIterator1, typename RandomAccessIterator3, typename Comparator>
+ template<typename RandomAccessIterator1, typename RandomAccessIterator3,
+ typename Comparator>
inline RandomAccessIterator3
- parallel_merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator1& begin2, RandomAccessIterator1 end2, RandomAccessIterator3 target, typename std::iterator_traits<RandomAccessIterator1>::difference_type max_length, Comparator comp)
+ parallel_merge_advance(RandomAccessIterator1& begin1,
+ RandomAccessIterator1 end1,
+ RandomAccessIterator1& begin2,
+ RandomAccessIterator1 end2,
+ RandomAccessIterator3 target,
+ typename std::iterator_traits<RandomAccessIterator1>
+ ::difference_type max_length, Comparator comp)
{
typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
value_type;
- typedef typename std::iterator_traits<RandomAccessIterator1>::difference_type
- difference_type1 /* == difference_type2 */;
- typedef typename std::iterator_traits<RandomAccessIterator3>::difference_type
- difference_type3;
+ typedef typename std::iterator_traits<RandomAccessIterator1>
+ ::difference_type difference_type1 /* == difference_type2 */;
+ typedef typename std::iterator_traits<RandomAccessIterator3>
+ ::difference_type difference_type3;
- std::pair<RandomAccessIterator1, RandomAccessIterator1> seqs[2] = { std::make_pair(begin1, end1), std::make_pair(begin2, end2) };
- RandomAccessIterator3 target_end = parallel_multiway_merge(seqs, seqs + 2, target, comp, max_length, true, false);
+ std::pair<RandomAccessIterator1, RandomAccessIterator1> seqs[2]
+ = { std::make_pair(begin1, end1), std::make_pair(begin2, end2) };
+ RandomAccessIterator3 target_end = parallel_multiway_merge
+ (seqs, seqs + 2, target, comp, max_length, true, false);
return target_end;
}
-} //namespace __gnu_parallel
+} //namespace __gnu_parallel
#endif
Index: include/parallel/unique_copy.h
===================================================================
--- include/parallel/unique_copy.h (revision 130490)
+++ include/parallel/unique_copy.h (working copy)
@@ -192,9 +192,11 @@
parallel_unique_copy(InputIterator first, InputIterator last,
OutputIterator result)
{
- typedef typename std::iterator_traits<InputIterator>::value_type value_type;
+ typedef typename std::iterator_traits<InputIterator>::value_type
+ value_type;
- return parallel_unique_copy(first, last, result, std::equal_to<value_type>());
+ return parallel_unique_copy(first, last, result,
+ std::equal_to<value_type>());
}
}//namespace __gnu_parallel
Index: include/parallel/settings.h
===================================================================
--- include/parallel/settings.h (revision 130490)
+++ include/parallel/settings.h (working copy)
@@ -33,7 +33,8 @@
* whether to use parallelized algorithms.
* This file is a GNU parallel extension to the Standard C++ Library.
*
- * @section parallelization_decision The decision whether to run an algorithm in parallel.
+ * @section parallelization_decision
+ * The decision whether to run an algorithm in parallel.
*
* There are several ways the user can switch on and off the
* parallel execution of an algorithm, both at compile- and
@@ -104,7 +105,10 @@
* __gnu_parallel::Settings::force_parallel, i. e. usually a decision based on
* the input size.
*/
-#define _GLIBCXX_PARALLEL_CONDITION(c) (!(__gnu_parallel::Settings::force_sequential) && ((__gnu_parallel::get_max_threads() > 1 && (c)) || __gnu_parallel::Settings::force_parallel))
+#define _GLIBCXX_PARALLEL_CONDITION(c) \
+ (!(__gnu_parallel::Settings::force_sequential) \
+ && ((__gnu_parallel::get_max_threads() > 1 && (c)) \
+ || __gnu_parallel::Settings::force_parallel))
namespace __gnu_parallel
{
@@ -131,7 +135,8 @@
/** @brief Different merging algorithms: bubblesort-alike,
loser-tree variants, enum sentinel */
enum MultiwayMergeAlgorithm
- { BUBBLE, LOSER_TREE_EXPLICIT, LOSER_TREE, LOSER_TREE_COMBINED, LOSER_TREE_SENTINEL, MWM_ALGORITHM_LAST };
+ { BUBBLE, LOSER_TREE_EXPLICIT, LOSER_TREE, LOSER_TREE_COMBINED,
+ LOSER_TREE_SENTINEL, MWM_ALGORITHM_LAST };
/** @brief Different splitting strategies for sorting/merging:
by sampling, exact */
@@ -340,7 +345,8 @@
volatile sequence_index_t Settings::partition_chunk_size = 1000;
volatile double Settings::partition_chunk_share = 0.0;
volatile unsigned int Settings::adjacent_difference_minimal_n = 1000;
- volatile Settings::PartialSumAlgorithm Settings::partial_sum_algorithm = Settings::LINEAR;
+ volatile Settings::PartialSumAlgorithm Settings::partial_sum_algorithm
+ = Settings::LINEAR;
volatile unsigned int Settings::partial_sum_minimal_n = 1000;
volatile float Settings::partial_sum_dilatation = 1.0f;
volatile unsigned int Settings::random_shuffle_minimal_n = 1000;
@@ -352,10 +358,13 @@
// unique copy
volatile sequence_index_t Settings::unique_copy_minimal_n = 10000;
- volatile Settings::MultiwayMergeAlgorithm Settings::multiway_merge_algorithm = Settings::LOSER_TREE;
- volatile Settings::Splitting Settings::multiway_merge_splitting = Settings::EXACT;
+ volatile Settings::MultiwayMergeAlgorithm Settings::multiway_merge_algorithm
+ = Settings::LOSER_TREE;
+ volatile Settings::Splitting Settings::multiway_merge_splitting
+ = Settings::EXACT;
volatile unsigned int Settings::multiway_merge_oversampling = 10;
- volatile Settings::FindDistribution Settings::find_distribution = Settings::CONSTANT_SIZE_BLOCKS;
+ volatile Settings::FindDistribution Settings::find_distribution
+ = Settings::CONSTANT_SIZE_BLOCKS;
volatile sequence_index_t Settings::find_sequential_search_size = 256;
volatile sequence_index_t Settings::find_initial_block_size = 256;
volatile sequence_index_t Settings::find_maximum_block_size = 8192;
@@ -375,7 +384,8 @@
volatile sequence_index_t Settings::set_union_minimal_n = 1000;
volatile sequence_index_t Settings::set_intersection_minimal_n = 1000;
volatile sequence_index_t Settings::set_difference_minimal_n = 1000;
- volatile sequence_index_t Settings::set_symmetric_difference_minimal_n = 1000;
+ volatile sequence_index_t Settings::set_symmetric_difference_minimal_n
+ = 1000;
volatile unsigned long long Settings::L1_cache_size = 16 << 10;
volatile unsigned long long Settings::L2_cache_size = 256 << 10;
volatile unsigned int Settings::TLB_size = 128;
Index: include/parallel/numericfwd.h
===================================================================
--- include/parallel/numericfwd.h (revision 130490)
+++ include/parallel/numericfwd.h (working copy)
@@ -44,146 +44,158 @@
{
namespace __parallel
{
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
inline T
accumulate(_IIter, _IIter, T);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
inline T
accumulate(_IIter, _IIter, T, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename T>
+template<typename _IIter, typename T>
inline T
accumulate(_IIter, _IIter, T, __gnu_parallel::parallelism parallelism_tag);
- template<typename _IIter, typename T, typename _Tag>
+template<typename _IIter, typename T, typename _Tag>
inline T
accumulate_switch(_IIter, _IIter, T, _Tag);
- template<typename _IIter, typename T, typename _BinaryOper>
+template<typename _IIter, typename T, typename _BinaryOper>
inline T
accumulate(_IIter, _IIter, T, _BinaryOper);
- template<typename _IIter, typename T, typename _BinaryOper>
+template<typename _IIter, typename T, typename _BinaryOper>
inline T
accumulate(_IIter, _IIter, T, _BinaryOper, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename T, typename _BinaryOper>
+template<typename _IIter, typename T, typename _BinaryOper>
inline T
accumulate(_IIter, _IIter, T, _BinaryOper,
- __gnu_parallel::parallelism parallelism_tag);
+ __gnu_parallel::parallelism parallelism_tag);
- template<typename _IIter, typename T, typename _BinaryOper, typename _Tag>
+template<typename _IIter, typename T, typename _BinaryOper, typename _Tag>
T
accumulate_switch(_IIter, _IIter, T, _BinaryOper, _Tag);
- template<typename _RAIter, typename T, typename _BinaryOper>
+template<typename _RAIter, typename T, typename _BinaryOper>
T
accumulate_switch(_RAIter, _RAIter, T, _BinaryOper,
- random_access_iterator_tag, __gnu_parallel::parallelism);
+ random_access_iterator_tag, __gnu_parallel::parallelism);
template<typename _IIter, typename _OIter>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter, _BinaryOper);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter, _BinaryOper,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter, __gnu_parallel::parallelism);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
inline _OIter
adjacent_difference(_IIter, _IIter, _OIter, _BinaryOper,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _IIter, typename _OIter, typename _BinaryOper, typename _Tag1, typename _Tag2>
+template<typename _IIter, typename _OIter, typename _BinaryOper,
+ typename _Tag1, typename _Tag2>
inline _OIter
- adjacent_difference_switch(_IIter, _IIter, _OIter, _BinaryOper, _Tag1, _Tag2);
+ adjacent_difference_switch(_IIter, _IIter, _OIter, _BinaryOper,
+ _Tag1, _Tag2);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
_OIter
adjacent_difference_switch(_IIter, _IIter, _OIter, _BinaryOper,
- random_access_iterator_tag,
- random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ random_access_iterator_tag,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename T>
+template<typename _IIter1, typename _IIter2, typename T>
inline T
inner_product(_IIter1, _IIter1, _IIter2, T);
- template<typename _IIter1, typename _IIter2, typename T>
+template<typename _IIter1, typename _IIter2, typename T>
inline T
inner_product(_IIter1, _IIter1, _IIter2, T, __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename T>
+template<typename _IIter1, typename _IIter2, typename T>
inline T
inner_product(_IIter1, _IIter1, _IIter2, T, __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename T, typename BinaryFunction1, typename BinaryFunction2>
+template<typename _IIter1, typename _IIter2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
inline T
- inner_product(_IIter1, _IIter1, _IIter2, T, BinaryFunction1, BinaryFunction2);
+ inner_product(_IIter1, _IIter1, _IIter2, T,
+ BinaryFunction1, BinaryFunction2);
- template<typename _IIter1, typename _IIter2, typename T, typename BinaryFunction1, typename BinaryFunction2>
+template<typename _IIter1, typename _IIter2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
inline T
inner_product(_IIter1, _IIter1, _IIter2, T, BinaryFunction1, BinaryFunction2,
- __gnu_parallel::sequential_tag);
+ __gnu_parallel::sequential_tag);
- template<typename _IIter1, typename _IIter2, typename T, typename BinaryFunction1, typename BinaryFunction2>
+template<typename _IIter1, typename _IIter2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
inline T
inner_product(_IIter1, _IIter1, _IIter2, T, BinaryFunction1, BinaryFunction2,
- __gnu_parallel::parallelism);
+ __gnu_parallel::parallelism);
- template<typename _RAIter1, typename _RAIter2, typename T, typename BinaryFunction1, typename BinaryFunction2>
+template<typename _RAIter1, typename _RAIter2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2>
T
inner_product_switch(_RAIter1, _RAIter1, _RAIter2, T, BinaryFunction1,
- BinaryFunction2, random_access_iterator_tag,
- random_access_iterator_tag,
- __gnu_parallel::parallelism);
+ BinaryFunction2, random_access_iterator_tag,
+ random_access_iterator_tag,
+ __gnu_parallel::parallelism);
- template<typename _IIter1, typename _IIter2, typename T, typename BinaryFunction1, typename BinaryFunction2, typename _Tag1, typename _Tag2>
+template<typename _IIter1, typename _IIter2, typename T,
+ typename BinaryFunction1, typename BinaryFunction2,
+ typename _Tag1, typename _Tag2>
inline T
inner_product_switch(_IIter1, _IIter1, _IIter2, T, BinaryFunction1,
- BinaryFunction2, _Tag1, _Tag2);
+ BinaryFunction2, _Tag1, _Tag2);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
inline _OIter
partial_sum(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
inline _OIter
- partial_sum(_IIter, _IIter, _OIter, _BinaryOper, __gnu_parallel::sequential_tag);
+ partial_sum(_IIter, _IIter, _OIter, _BinaryOper,
+ __gnu_parallel::sequential_tag);
- template<typename _IIter, typename _OIter>
+template<typename _IIter, typename _OIter>
inline _OIter
partial_sum(_IIter, _IIter, _OIter result);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
inline _OIter
partial_sum(_IIter, _IIter, _OIter, _BinaryOper);
- template<typename _IIter, typename _OIter, typename _BinaryOper, typename _Tag1, typename _Tag2>
+template<typename _IIter, typename _OIter, typename _BinaryOper,
+ typename _Tag1, typename _Tag2>
inline _OIter
partial_sum_switch(_IIter, _IIter, _OIter, _BinaryOper, _Tag1, _Tag2);
- template<typename _IIter, typename _OIter, typename _BinaryOper>
+template<typename _IIter, typename _OIter, typename _BinaryOper>
_OIter
- partial_sum_switch(_IIter, _IIter, _OIter, _BinaryOper, random_access_iterator_tag, random_access_iterator_tag);
+ partial_sum_switch(_IIter, _IIter, _OIter, _BinaryOper,
+ random_access_iterator_tag, random_access_iterator_tag);
} // end namespace
} // end namespace
Index: include/parallel/search.h
===================================================================
--- include/parallel/search.h (revision 130490)
+++ include/parallel/search.h (working copy)
@@ -152,9 +152,9 @@
if (pos_in_pattern == pattern_length)
{
// Found new candidate for result.
- omp_set_lock(&result_lock);
+ omp_set_lock(&result_lock);
result = std::min(result, start);
- omp_unset_lock(&result_lock);
+ omp_unset_lock(&result_lock);
found_pattern = true;
break;
Index: include/parallel/partition.h
===================================================================
--- include/parallel/partition.h (revision 130490)
+++ include/parallel/partition.h (working copy)
@@ -51,11 +51,11 @@
namespace __gnu_parallel
{
/** @brief Parallel implementation of std::partition.
- * @param begin Begin iterator of input sequence to split.
- * @param end End iterator of input sequence to split.
- * @param pred Partition predicate, possibly including some kind of pivot.
- * @param num_threads Maximum number of threads to use for this task.
- * @return Number of elements not fulfilling the predicate. */
+ * @param begin Begin iterator of input sequence to split.
+ * @param end End iterator of input sequence to split.
+ * @param pred Partition predicate, possibly including some kind of pivot.
+ * @param num_threads Maximum number of threads to use for this task.
+ * @return Number of elements not fulfilling the predicate. */
template<typename RandomAccessIterator, typename Predicate>
typename std::iterator_traits<RandomAccessIterator>::difference_type
parallel_partition(RandomAccessIterator begin, RandomAccessIterator end,
@@ -106,7 +106,7 @@
{
difference_type num_chunks = (right - left + 1) / chunk_size;
- for (int r = 0; r < num_threads; r++)
+ for (int r = 0; r < num_threads; ++r)
{
reserved_left[r] = false;
reserved_right[r] = false;
@@ -164,10 +164,10 @@
{
while (pred(begin[thread_left])
&& thread_left <= thread_left_border)
- thread_left++;
+ ++thread_left;
while (!pred(begin[thread_right])
&& thread_right >= thread_right_border)
- thread_right--;
+ --thread_right;
if (thread_left > thread_left_border
|| thread_right < thread_right_border)
@@ -175,18 +175,18 @@
break;
std::swap(begin[thread_left], begin[thread_right]);
- thread_left++;
- thread_right--;
+ ++thread_left;
+ --thread_right;
}
}
// Now swap the leftover chunks to the right places.
if (thread_left <= thread_left_border)
# pragma omp atomic
- leftover_left++;
+ ++leftover_left;
if (thread_right >= thread_right_border)
# pragma omp atomic
- leftover_right++;
+ ++leftover_right;
# pragma omp barrier
@@ -225,7 +225,7 @@
// Find spot and swap.
difference_type swapstart = -1;
omp_set_lock(&result_lock);
- for (int r = 0; r < leftover_left; r