41 #ifndef _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H
42 #define _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 1
52 #pragma GCC diagnostic push
53 #pragma GCC diagnostic ignored "-Wdeprecated-declarations"
56 template<
typename _T1,
typename _T2,
typename _Compare>
59 std::pair<_T1, _T2>, bool>
83 template<
typename _T1,
typename _T2,
typename _Compare>
107 #pragma GCC diagnostic pop
125 template<
typename _RanSeqs,
typename _RankType,
typename _RankIterator,
130 _RankIterator __begin_offsets,
134 first_type>::value_type>())
151 _DifferenceType __m =
std::distance(__begin_seqs, __end_seqs), __nn = 0,
154 for (_SeqNumber __i = 0; __i < __m; __i++)
157 __begin_seqs[__i].second);
158 _GLIBCXX_PARALLEL_ASSERT(
160 __begin_seqs[__i].second) > 0);
165 for (_SeqNumber __i = 0; __i < __m; __i++)
166 __begin_offsets[__i] = __begin_seqs[__i].second;
171 _GLIBCXX_PARALLEL_ASSERT(__m != 0);
172 _GLIBCXX_PARALLEL_ASSERT(__nn != 0);
173 _GLIBCXX_PARALLEL_ASSERT(__rank >= 0);
174 _GLIBCXX_PARALLEL_ASSERT(__rank < __nn);
176 _DifferenceType* __ns =
new _DifferenceType[__m];
177 _DifferenceType* __a =
new _DifferenceType[__m];
178 _DifferenceType* __b =
new _DifferenceType[__m];
181 __ns[0] =
std::distance(__begin_seqs[0].first, __begin_seqs[0].second);
183 for (_SeqNumber __i = 0; __i < __m; __i++)
186 __begin_seqs[__i].second);
187 __nmax =
std::max(__nmax, __ns[__i]);
192 #pragma GCC diagnostic push
193 #pragma GCC diagnostic ignored "-Wlong-long"
196 __l = (1ULL << __r) - 1;
197 #pragma GCC diagnostic pop
199 for (_SeqNumber __i = 0; __i < __m; __i++)
209 #define __S(__i) (__begin_seqs[__i].first)
214 for (_SeqNumber __i = 0; __i < __m; __i++)
216 __sample.push_back(std::make_pair(__S(__i)[__n], __i));
219 for (_SeqNumber __i = 0; __i < __m; __i++)
220 if (__n >= __ns[__i])
222 std::make_pair(__S(__i)[0] , __i));
224 _DifferenceType __localrank = __rank / __l;
228 __j < __localrank && ((__n + 1) <= __ns[
__sample[__j].second]);
230 __a[
__sample[__j].second] += __n + 1;
231 for (; __j < __m; __j++)
232 __b[
__sample[__j].second] -= __n + 1;
239 _SeqNumber __lmax_seq = -1;
240 const _ValueType* __lmax = 0;
241 for (_SeqNumber __i = 0; __i < __m; __i++)
247 __lmax = &(__S(__i)[__a[__i] - 1]);
253 if (!__comp(__S(__i)[__a[__i] - 1], *__lmax))
255 __lmax = &(__S(__i)[__a[__i] - 1]);
263 for (__i = 0; __i < __m; __i++)
265 _DifferenceType __middle = (__b[__i] + __a[__i]) / 2;
266 if (__lmax && __middle < __ns[__i] &&
267 __lcomp(std::make_pair(__S(__i)[__middle], __i),
268 std::make_pair(*__lmax, __lmax_seq)))
269 __a[__i] =
std::min(__a[__i] + __n + 1, __ns[__i]);
274 _DifferenceType __leftsize = 0;
275 for (_SeqNumber __i = 0; __i < __m; __i++)
276 __leftsize += __a[__i] / (__n + 1);
278 _DifferenceType __skew = __rank / (__n + 1) - __leftsize;
288 for (_SeqNumber __i = 0; __i < __m; __i++)
289 if (__b[__i] < __ns[__i])
290 __pq.
push(std::make_pair(__S(__i)[__b[__i]], __i));
292 for (; __skew != 0 && !__pq.
empty(); --__skew)
294 _SeqNumber __source = __pq.
top().second;
298 =
std::min(__a[__source] + __n + 1, __ns[__source]);
299 __b[__source] += __n + 1;
301 if (__b[__source] < __ns[__source])
303 std::make_pair(__S(__source)[__b[__source]], __source));
314 for (_SeqNumber __i = 0; __i < __m; __i++)
316 __pq.
push(std::make_pair(__S(__i)[__a[__i] - 1], __i));
318 for (; __skew != 0; ++__skew)
320 _SeqNumber __source = __pq.
top().second;
323 __a[__source] -= __n + 1;
324 __b[__source] -= __n + 1;
326 if (__a[__source] > 0)
327 __pq.
push(std::make_pair(
328 __S(__source)[__a[__source] - 1], __source));
342 _ValueType* __maxleft = 0;
343 _ValueType* __minright = 0;
344 for (_SeqNumber __i = 0; __i < __m; __i++)
349 __maxleft = &(__S(__i)[__a[__i] - 1]);
353 if (!__comp(__S(__i)[__a[__i] - 1], *__maxleft))
354 __maxleft = &(__S(__i)[__a[__i] - 1]);
357 if (__b[__i] < __ns[__i])
360 __minright = &(__S(__i)[__b[__i]]);
364 if (__comp(__S(__i)[__b[__i]], *__minright))
365 __minright = &(__S(__i)[__b[__i]]);
370 _SeqNumber __seq = 0;
371 for (_SeqNumber __i = 0; __i < __m; __i++)
372 __begin_offsets[__i] = __S(__i) + __a[__i];
394 template<
typename _Tp,
typename _RanSeqs,
typename _RankType,
415 _DifferenceType __m =
std::distance(__begin_seqs, __end_seqs);
416 _DifferenceType __nn = 0;
417 _DifferenceType __nmax, __n, __r;
419 for (_SeqNumber __i = 0; __i < __m; __i++)
421 __begin_seqs[__i].second);
423 if (__m == 0 || __nn == 0 || __rank < 0 || __rank >= __nn)
430 _DifferenceType* __ns =
new _DifferenceType[__m];
431 _DifferenceType* __a =
new _DifferenceType[__m];
432 _DifferenceType* __b =
new _DifferenceType[__m];
435 __ns[0] =
std::distance(__begin_seqs[0].first, __begin_seqs[0].second);
437 for (_SeqNumber __i = 0; __i < __m; ++__i)
440 __begin_seqs[__i].second);
441 __nmax =
std::max(__nmax, __ns[__i]);
450 for (_SeqNumber __i = 0; __i < __m; ++__i)
460 #define __S(__i) (__begin_seqs[__i].first)
465 for (_SeqNumber __i = 0; __i < __m; __i++)
467 __sample.push_back(std::make_pair(__S(__i)[__n], __i));
472 for (_SeqNumber __i = 0; __i < __m; __i++)
473 if (__n >= __ns[__i])
475 std::make_pair(__S(__i)[0] , __i));
477 _DifferenceType __localrank = __rank / __l;
481 __j < __localrank && ((__n + 1) <= __ns[
__sample[__j].second]);
483 __a[
__sample[__j].second] += __n + 1;
484 for (; __j < __m; ++__j)
485 __b[
__sample[__j].second] -= __n + 1;
492 const _Tp* __lmax = 0;
493 for (_SeqNumber __i = 0; __i < __m; ++__i)
498 __lmax = &(__S(__i)[__a[__i] - 1]);
501 if (__comp(*__lmax, __S(__i)[__a[__i] - 1]))
502 __lmax = &(__S(__i)[__a[__i] - 1]);
508 for (__i = 0; __i < __m; __i++)
510 _DifferenceType __middle = (__b[__i] + __a[__i]) / 2;
511 if (__lmax && __middle < __ns[__i]
512 && __comp(__S(__i)[__middle], *__lmax))
513 __a[__i] =
std::min(__a[__i] + __n + 1, __ns[__i]);
518 _DifferenceType __leftsize = 0;
519 for (_SeqNumber __i = 0; __i < __m; ++__i)
520 __leftsize += __a[__i] / (__n + 1);
522 _DifferenceType __skew = __rank / (__n + 1) - __leftsize;
532 for (_SeqNumber __i = 0; __i < __m; ++__i)
533 if (__b[__i] < __ns[__i])
534 __pq.
push(std::make_pair(__S(__i)[__b[__i]], __i));
536 for (; __skew != 0 && !__pq.
empty(); --__skew)
538 _SeqNumber __source = __pq.
top().second;
542 =
std::min(__a[__source] + __n + 1, __ns[__source]);
543 __b[__source] += __n + 1;
545 if (__b[__source] < __ns[__source])
547 std::make_pair(__S(__source)[__b[__source]], __source));
557 for (_SeqNumber __i = 0; __i < __m; ++__i)
559 __pq.
push(std::make_pair(__S(__i)[__a[__i] - 1], __i));
561 for (; __skew != 0; ++__skew)
563 _SeqNumber __source = __pq.
top().second;
566 __a[__source] -= __n + 1;
567 __b[__source] -= __n + 1;
569 if (__a[__source] > 0)
570 __pq.
push(std::make_pair(
571 __S(__source)[__a[__source] - 1], __source));
585 bool __maxleftset =
false, __minrightset =
false;
588 _Tp __maxleft, __minright;
589 for (_SeqNumber __i = 0; __i < __m; ++__i)
595 __maxleft = __S(__i)[__a[__i] - 1];
601 if (__comp(__maxleft, __S(__i)[__a[__i] - 1]))
602 __maxleft = __S(__i)[__a[__i] - 1];
605 if (__b[__i] < __ns[__i])
609 __minright = __S(__i)[__b[__i]];
610 __minrightset =
true;
615 if (__comp(__S(__i)[__b[__i]], __minright))
616 __minright = __S(__i)[__b[__i]];
623 if (!__maxleftset || __comp(__minright, __maxleft))
633 for (_SeqNumber __i = 0; __i < __m; ++__i)
636 = std::lower_bound(__S(__i), __S(__i) + __ns[__i],
639 __offset += __a[__i] - lb;
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
GNU parallel code for public use.
_Tp multiseq_selection(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankType &__offset, _Compare __comp=std::less< _Tp >())
Selects the element at a certain global __rank from several sorted sequences.
_Tp __round_up_to_pow2(_Tp __x)
Round up to the next greater power of 2.
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 >())
Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each s...
_Size __rd_log2(_Size __n)
Calculates the rounded-down logarithm of __n for base 2.
Base class for all library exceptions.
One of the comparison functors.
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.
Traits class for iterators.
A standard container automatically sorting its contents.
void pop()
Removes first element.
const_reference top() const
void push(const value_type &__x)
Add data to the queue.
A standard container which offers fixed time access to individual elements in any order.
Compare __a pair of types lexicographically, ascending.
Compare __a pair of types lexicographically, descending.
Forces sequential execution at compile time.