0,0 → 1,644 |
// -*- C++ -*- |
|
// Copyright (C) 2007-2015 Free Software Foundation, Inc. |
// |
// This file is part of the GNU ISO C++ Library. This library is free |
// software; you can redistribute it and/or modify it under the terms |
// of the GNU General Public License as published by the Free Software |
// Foundation; either version 3, or (at your option) any later |
// version. |
|
// This library is distributed in the hope that it will be useful, but |
// WITHOUT ANY WARRANTY; without even the implied warranty of |
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
// General Public License for more details. |
|
// Under Section 7 of GPL version 3, you are granted additional |
// permissions described in the GCC Runtime Library Exception, version |
// 3.1, as published by the Free Software Foundation. |
|
// You should have received a copy of the GNU General Public License and |
// a copy of the GCC Runtime Library Exception along with this program; |
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
// <http://www.gnu.org/licenses/>. |
|
/** @file parallel/multiseq_selection.h |
* @brief Functions to find elements of a certain global __rank in |
* multiple sorted sequences. Also serves for splitting such |
* sequence sets. |
* |
* The algorithm description can be found in |
* |
* P. J. Varman, S. D. Scheufler, B. R. Iyer, and G. R. Ricard. |
* Merging Multiple Lists on Hierarchical-Memory Multiprocessors. |
* Journal of Parallel and Distributed Computing, 12(2):171–177, 1991. |
* |
* This file is a GNU parallel extension to the Standard C++ Library. |
*/ |
|
// Written by Johannes Singler. |
|
#ifndef _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H |
#define _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 1 |
|
#include <vector> |
#include <queue> |
|
#include <bits/stl_algo.h> |
|
namespace __gnu_parallel |
{ |
/** @brief Compare __a pair of types lexicographically, ascending. */ |
template<typename _T1, typename _T2, typename _Compare> |
class _Lexicographic |
: public std::binary_function<std::pair<_T1, _T2>, |
std::pair<_T1, _T2>, bool> |
{ |
private: |
_Compare& _M_comp; |
|
public: |
_Lexicographic(_Compare& __comp) : _M_comp(__comp) { } |
|
bool |
operator()(const std::pair<_T1, _T2>& __p1, |
const std::pair<_T1, _T2>& __p2) const |
{ |
if (_M_comp(__p1.first, __p2.first)) |
return true; |
|
if (_M_comp(__p2.first, __p1.first)) |
return false; |
|
// Firsts are equal. |
return __p1.second < __p2.second; |
} |
}; |
|
/** @brief Compare __a pair of types lexicographically, descending. */ |
template<typename _T1, typename _T2, typename _Compare> |
class _LexicographicReverse : public std::binary_function<_T1, _T2, bool> |
{ |
private: |
_Compare& _M_comp; |
|
public: |
_LexicographicReverse(_Compare& __comp) : _M_comp(__comp) { } |
|
bool |
operator()(const std::pair<_T1, _T2>& __p1, |
const std::pair<_T1, _T2>& __p2) const |
{ |
if (_M_comp(__p2.first, __p1.first)) |
return true; |
|
if (_M_comp(__p1.first, __p2.first)) |
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<_Tp>. |
*/ |
template<typename _RanSeqs, typename _RankType, typename _RankIterator, |
typename _Compare> |
void |
multiseq_partition(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, |
_RankType __rank, |
_RankIterator __begin_offsets, |
_Compare __comp = std::less< |
typename std::iterator_traits<typename |
std::iterator_traits<_RanSeqs>::value_type:: |
first_type>::value_type>()) // std::less<_Tp> |
{ |
_GLIBCXX_CALL(__end_seqs - __begin_seqs) |
|
typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type |
_It; |
typedef typename std::iterator_traits<_RanSeqs>::difference_type |
_SeqNumber; |
typedef typename std::iterator_traits<_It>::difference_type |
_DifferenceType; |
typedef typename std::iterator_traits<_It>::value_type _ValueType; |
|
_Lexicographic<_ValueType, _SeqNumber, _Compare> __lcomp(__comp); |
_LexicographicReverse<_ValueType, _SeqNumber, _Compare> __lrcomp(__comp); |
|
// Number of sequences, number of elements in total (possibly |
// including padding). |
_DifferenceType __m = std::distance(__begin_seqs, __end_seqs), __nn = 0, |
__nmax, __n, __r; |
|
for (_SeqNumber __i = 0; __i < __m; __i++) |
{ |
__nn += std::distance(__begin_seqs[__i].first, |
__begin_seqs[__i].second); |
_GLIBCXX_PARALLEL_ASSERT( |
std::distance(__begin_seqs[__i].first, |
__begin_seqs[__i].second) > 0); |
} |
|
if (__rank == __nn) |
{ |
for (_SeqNumber __i = 0; __i < __m; __i++) |
__begin_offsets[__i] = __begin_seqs[__i].second; // Very end. |
// Return __m - 1; |
return; |
} |
|
_GLIBCXX_PARALLEL_ASSERT(__m != 0); |
_GLIBCXX_PARALLEL_ASSERT(__nn != 0); |
_GLIBCXX_PARALLEL_ASSERT(__rank >= 0); |
_GLIBCXX_PARALLEL_ASSERT(__rank < __nn); |
|
_DifferenceType* __ns = new _DifferenceType[__m]; |
_DifferenceType* __a = new _DifferenceType[__m]; |
_DifferenceType* __b = new _DifferenceType[__m]; |
_DifferenceType __l; |
|
__ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second); |
__nmax = __ns[0]; |
for (_SeqNumber __i = 0; __i < __m; __i++) |
{ |
__ns[__i] = std::distance(__begin_seqs[__i].first, |
__begin_seqs[__i].second); |
__nmax = std::max(__nmax, __ns[__i]); |
} |
|
__r = __rd_log2(__nmax) + 1; |
|
// Pad all lists to this length, at least as long as any ns[__i], |
// equality iff __nmax = 2^__k - 1. |
__l = (1ULL << __r) - 1; |
|
for (_SeqNumber __i = 0; __i < __m; __i++) |
{ |
__a[__i] = 0; |
__b[__i] = __l; |
} |
__n = __l / 2; |
|
// Invariants: |
// 0 <= __a[__i] <= __ns[__i], 0 <= __b[__i] <= __l |
|
#define __S(__i) (__begin_seqs[__i].first) |
|
// Initial partition. |
std::vector<std::pair<_ValueType, _SeqNumber> > __sample; |
|
for (_SeqNumber __i = 0; __i < __m; __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 (_SeqNumber __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)); |
|
_DifferenceType __localrank = __rank / __l; |
|
_SeqNumber __j; |
for (__j = 0; |
__j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]); |
++__j) |
__a[__sample[__j].second] += __n + 1; |
for (; __j < __m; __j++) |
__b[__sample[__j].second] -= __n + 1; |
|
// Further refinement. |
while (__n > 0) |
{ |
__n /= 2; |
|
_SeqNumber __lmax_seq = -1; // to avoid warning |
const _ValueType* __lmax = 0; // impossible to avoid the warning? |
for (_SeqNumber __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; |
} |
} |
} |
} |
|
_SeqNumber __i; |
for (__i = 0; __i < __m; __i++) |
{ |
_DifferenceType __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; |
} |
|
_DifferenceType __leftsize = 0; |
for (_SeqNumber __i = 0; __i < __m; __i++) |
__leftsize += __a[__i] / (__n + 1); |
|
_DifferenceType __skew = __rank / (__n + 1) - __leftsize; |
|
if (__skew > 0) |
{ |
// Move to the left, find smallest. |
std::priority_queue<std::pair<_ValueType, _SeqNumber>, |
std::vector<std::pair<_ValueType, _SeqNumber> >, |
_LexicographicReverse<_ValueType, _SeqNumber, _Compare> > |
__pq(__lrcomp); |
|
for (_SeqNumber __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) |
{ |
_SeqNumber __source = __pq.top().second; |
__pq.pop(); |
|
__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<_ValueType, _SeqNumber>, |
std::vector<std::pair<_ValueType, _SeqNumber> >, |
_Lexicographic<_ValueType, _SeqNumber, _Compare> > |
__pq(__lcomp); |
|
for (_SeqNumber __i = 0; __i < __m; __i++) |
if (__a[__i] > 0) |
__pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i)); |
|
for (; __skew != 0; ++__skew) |
{ |
_SeqNumber __source = __pq.top().second; |
__pq.pop(); |
|
__a[__source] -= __n + 1; |
__b[__source] -= __n + 1; |
|
if (__a[__source] > 0) |
__pq.push(std::make_pair( |
__S(__source)[__a[__source] - 1], __source)); |
} |
} |
} |
|
// Postconditions: |
// __a[__i] == __b[__i] in most cases, except when __a[__i] has been |
// clamped because of having reached the boundary |
|
// Now return the result, calculate the offset. |
|
// Compare the keys on both edges of the border. |
|
// Maximum of left edge, minimum of right edge. |
_ValueType* __maxleft = 0; |
_ValueType* __minright = 0; |
for (_SeqNumber __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]]); |
} |
} |
} |
|
_SeqNumber __seq = 0; |
for (_SeqNumber __i = 0; __i < __m; __i++) |
__begin_offsets[__i] = __S(__i) + __a[__i]; |
|
delete[] __ns; |
delete[] __a; |
delete[] __b; |
} |
|
|
/** |
* @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 _Tp, typename _RanSeqs, typename _RankType, |
typename _Compare> |
_Tp |
multiseq_selection(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, |
_RankType __rank, |
_RankType& __offset, _Compare __comp = std::less<_Tp>()) |
{ |
_GLIBCXX_CALL(__end_seqs - __begin_seqs) |
|
typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type |
_It; |
typedef typename std::iterator_traits<_RanSeqs>::difference_type |
_SeqNumber; |
typedef typename std::iterator_traits<_It>::difference_type |
_DifferenceType; |
|
_Lexicographic<_Tp, _SeqNumber, _Compare> __lcomp(__comp); |
_LexicographicReverse<_Tp, _SeqNumber, _Compare> __lrcomp(__comp); |
|
// Number of sequences, number of elements in total (possibly |
// including padding). |
_DifferenceType __m = std::distance(__begin_seqs, __end_seqs); |
_DifferenceType __nn = 0; |
_DifferenceType __nmax, __n, __r; |
|
for (_SeqNumber __i = 0; __i < __m; __i++) |
__nn += std::distance(__begin_seqs[__i].first, |
__begin_seqs[__i].second); |
|
if (__m == 0 || __nn == 0 || __rank < 0 || __rank >= __nn) |
{ |
// result undefined if there is no data or __rank is outside bounds |
throw std::exception(); |
} |
|
|
_DifferenceType* __ns = new _DifferenceType[__m]; |
_DifferenceType* __a = new _DifferenceType[__m]; |
_DifferenceType* __b = new _DifferenceType[__m]; |
_DifferenceType __l; |
|
__ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second); |
__nmax = __ns[0]; |
for (_SeqNumber __i = 0; __i < __m; ++__i) |
{ |
__ns[__i] = std::distance(__begin_seqs[__i].first, |
__begin_seqs[__i].second); |
__nmax = std::max(__nmax, __ns[__i]); |
} |
|
__r = __rd_log2(__nmax) + 1; |
|
// Pad all lists to this length, at least as long as any ns[__i], |
// equality iff __nmax = 2^__k - 1 |
__l = __round_up_to_pow2(__r) - 1; |
|
for (_SeqNumber __i = 0; __i < __m; ++__i) |
{ |
__a[__i] = 0; |
__b[__i] = __l; |
} |
__n = __l / 2; |
|
// Invariants: |
// 0 <= __a[__i] <= __ns[__i], 0 <= __b[__i] <= __l |
|
#define __S(__i) (__begin_seqs[__i].first) |
|
// Initial partition. |
std::vector<std::pair<_Tp, _SeqNumber> > __sample; |
|
for (_SeqNumber __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()); |
|
// Conceptual infinity. |
for (_SeqNumber __i = 0; __i < __m; __i++) |
if (__n >= __ns[__i]) |
__sample.push_back( |
std::make_pair(__S(__i)[0] /*__dummy element*/, __i)); |
|
_DifferenceType __localrank = __rank / __l; |
|
_SeqNumber __j; |
for (__j = 0; |
__j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]); |
++__j) |
__a[__sample[__j].second] += __n + 1; |
for (; __j < __m; ++__j) |
__b[__sample[__j].second] -= __n + 1; |
|
// Further refinement. |
while (__n > 0) |
{ |
__n /= 2; |
|
const _Tp* __lmax = 0; |
for (_SeqNumber __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]); |
} |
} |
} |
|
_SeqNumber __i; |
for (__i = 0; __i < __m; __i++) |
{ |
_DifferenceType __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; |
} |
|
_DifferenceType __leftsize = 0; |
for (_SeqNumber __i = 0; __i < __m; ++__i) |
__leftsize += __a[__i] / (__n + 1); |
|
_DifferenceType __skew = __rank / (__n + 1) - __leftsize; |
|
if (__skew > 0) |
{ |
// Move to the left, find smallest. |
std::priority_queue<std::pair<_Tp, _SeqNumber>, |
std::vector<std::pair<_Tp, _SeqNumber> >, |
_LexicographicReverse<_Tp, _SeqNumber, _Compare> > |
__pq(__lrcomp); |
|
for (_SeqNumber __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) |
{ |
_SeqNumber __source = __pq.top().second; |
__pq.pop(); |
|
__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<_Tp, _SeqNumber>, |
std::vector<std::pair<_Tp, _SeqNumber> >, |
_Lexicographic<_Tp, _SeqNumber, _Compare> > __pq(__lcomp); |
|
for (_SeqNumber __i = 0; __i < __m; ++__i) |
if (__a[__i] > 0) |
__pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i)); |
|
for (; __skew != 0; ++__skew) |
{ |
_SeqNumber __source = __pq.top().second; |
__pq.pop(); |
|
__a[__source] -= __n + 1; |
__b[__source] -= __n + 1; |
|
if (__a[__source] > 0) |
__pq.push(std::make_pair( |
__S(__source)[__a[__source] - 1], __source)); |
} |
} |
} |
|
// Postconditions: |
// __a[__i] == __b[__i] in most cases, except when __a[__i] has been |
// clamped because of having reached the boundary |
|
// Now return the result, calculate the offset. |
|
// Compare the keys on both edges of the border. |
|
// Maximum of left edge, minimum of right edge. |
bool __maxleftset = false, __minrightset = false; |
|
// Impossible to avoid the warning? |
_Tp __maxleft, __minright; |
for (_SeqNumber __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]]; |
} |
} |
} |
|
// Minright is the __splitter, in any case. |
|
if (!__maxleftset || __comp(__minright, __maxleft)) |
{ |
// Good luck, everything is split unambiguously. |
__offset = 0; |
} |
else |
{ |
// We have to calculate an offset. |
__offset = 0; |
|
for (_SeqNumber __i = 0; __i < __m; ++__i) |
{ |
_DifferenceType lb |
= std::lower_bound(__S(__i), __S(__i) + __ns[__i], |
__minright, |
__comp) - __S(__i); |
__offset += __a[__i] - lb; |
} |
} |
|
delete[] __ns; |
delete[] __a; |
delete[] __b; |
|
return __minright; |
} |
} |
|
#undef __S |
|
#endif /* _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H */ |