41 #ifndef _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 42 #define _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 1 52 template<
typename _T1,
typename _T2,
typename _Compare>
55 std::pair<_T1, _T2>, bool>
79 template<
typename _T1,
typename _T2,
typename _Compare>
119 template<
typename _RanSeqs,
typename _RankType,
typename _RankIterator,
124 _RankIterator __begin_offsets,
126 typename std::iterator_traits<
typename 127 std::iterator_traits<_RanSeqs>::value_type::
128 first_type>::value_type>())
132 typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type
134 typedef typename std::iterator_traits<_RanSeqs>::difference_type
136 typedef typename std::iterator_traits<_It>::difference_type
138 typedef typename std::iterator_traits<_It>::value_type _ValueType;
145 _DifferenceType __m =
std::distance(__begin_seqs, __end_seqs), __nn = 0,
148 for (_SeqNumber __i = 0; __i < __m; __i++)
151 __begin_seqs[__i].second);
152 _GLIBCXX_PARALLEL_ASSERT(
154 __begin_seqs[__i].second) > 0);
159 for (_SeqNumber __i = 0; __i < __m; __i++)
160 __begin_offsets[__i] = __begin_seqs[__i].second;
165 _GLIBCXX_PARALLEL_ASSERT(__m != 0);
166 _GLIBCXX_PARALLEL_ASSERT(__nn != 0);
167 _GLIBCXX_PARALLEL_ASSERT(__rank >= 0);
168 _GLIBCXX_PARALLEL_ASSERT(__rank < __nn);
170 _DifferenceType* __ns =
new _DifferenceType[__m];
171 _DifferenceType* __a =
new _DifferenceType[__m];
172 _DifferenceType* __b =
new _DifferenceType[__m];
175 __ns[0] =
std::distance(__begin_seqs[0].first, __begin_seqs[0].second);
177 for (_SeqNumber __i = 0; __i < __m; __i++)
180 __begin_seqs[__i].second);
181 __nmax =
std::max(__nmax, __ns[__i]);
188 __l = (1ULL << __r) - 1;
190 for (_SeqNumber __i = 0; __i < __m; __i++)
200 #define __S(__i) (__begin_seqs[__i].first) 205 for (_SeqNumber __i = 0; __i < __m; __i++)
208 __gnu_sequential::sort(__sample.
begin(), __sample.
end(), __lcomp);
210 for (_SeqNumber __i = 0; __i < __m; __i++)
211 if (__n >= __ns[__i])
215 _DifferenceType __localrank = __rank / __l;
219 __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]);
221 __a[__sample[__j].second] += __n + 1;
222 for (; __j < __m; __j++)
223 __b[__sample[__j].second] -= __n + 1;
230 _SeqNumber __lmax_seq = -1;
231 const _ValueType* __lmax = 0;
232 for (_SeqNumber __i = 0; __i < __m; __i++)
238 __lmax = &(__S(__i)[__a[__i] - 1]);
244 if (!__comp(__S(__i)[__a[__i] - 1], *__lmax))
246 __lmax = &(__S(__i)[__a[__i] - 1]);
254 for (__i = 0; __i < __m; __i++)
256 _DifferenceType __middle = (__b[__i] + __a[__i]) / 2;
257 if (__lmax && __middle < __ns[__i] &&
260 __a[__i] =
std::min(__a[__i] + __n + 1, __ns[__i]);
265 _DifferenceType __leftsize = 0;
266 for (_SeqNumber __i = 0; __i < __m; __i++)
267 __leftsize += __a[__i] / (__n + 1);
269 _DifferenceType __skew = __rank / (__n + 1) - __leftsize;
279 for (_SeqNumber __i = 0; __i < __m; __i++)
280 if (__b[__i] < __ns[__i])
283 for (; __skew != 0 && !__pq.
empty(); --__skew)
285 _SeqNumber __source = __pq.
top().second;
289 =
std::min(__a[__source] + __n + 1, __ns[__source]);
290 __b[__source] += __n + 1;
292 if (__b[__source] < __ns[__source])
305 for (_SeqNumber __i = 0; __i < __m; __i++)
309 for (; __skew != 0; ++__skew)
311 _SeqNumber __source = __pq.
top().second;
314 __a[__source] -= __n + 1;
315 __b[__source] -= __n + 1;
317 if (__a[__source] > 0)
319 __S(__source)[__a[__source] - 1], __source));
333 _ValueType* __maxleft = 0;
334 _ValueType* __minright = 0;
335 for (_SeqNumber __i = 0; __i < __m; __i++)
340 __maxleft = &(__S(__i)[__a[__i] - 1]);
344 if (!__comp(__S(__i)[__a[__i] - 1], *__maxleft))
345 __maxleft = &(__S(__i)[__a[__i] - 1]);
348 if (__b[__i] < __ns[__i])
351 __minright = &(__S(__i)[__b[__i]]);
355 if (__comp(__S(__i)[__b[__i]], *__minright))
356 __minright = &(__S(__i)[__b[__i]]);
361 _SeqNumber __seq = 0;
362 for (_SeqNumber __i = 0; __i < __m; __i++)
363 __begin_offsets[__i] = __S(__i) + __a[__i];
385 template<
typename _Tp,
typename _RanSeqs,
typename _RankType,
394 typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type
396 typedef typename std::iterator_traits<_RanSeqs>::difference_type
398 typedef typename std::iterator_traits<_It>::difference_type
406 _DifferenceType __m =
std::distance(__begin_seqs, __end_seqs);
407 _DifferenceType __nn = 0;
408 _DifferenceType __nmax, __n, __r;
410 for (_SeqNumber __i = 0; __i < __m; __i++)
412 __begin_seqs[__i].second);
414 if (__m == 0 || __nn == 0 || __rank < 0 || __rank >= __nn)
421 _DifferenceType* __ns =
new _DifferenceType[__m];
422 _DifferenceType* __a =
new _DifferenceType[__m];
423 _DifferenceType* __b =
new _DifferenceType[__m];
426 __ns[0] =
std::distance(__begin_seqs[0].first, __begin_seqs[0].second);
428 for (_SeqNumber __i = 0; __i < __m; ++__i)
431 __begin_seqs[__i].second);
432 __nmax =
std::max(__nmax, __ns[__i]);
441 for (_SeqNumber __i = 0; __i < __m; ++__i)
451 #define __S(__i) (__begin_seqs[__i].first) 456 for (_SeqNumber __i = 0; __i < __m; __i++)
459 __gnu_sequential::sort(__sample.
begin(), __sample.
end(),
463 for (_SeqNumber __i = 0; __i < __m; __i++)
464 if (__n >= __ns[__i])
468 _DifferenceType __localrank = __rank / __l;
472 __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]);
474 __a[__sample[__j].second] += __n + 1;
475 for (; __j < __m; ++__j)
476 __b[__sample[__j].second] -= __n + 1;
483 const _Tp* __lmax = 0;
484 for (_SeqNumber __i = 0; __i < __m; ++__i)
489 __lmax = &(__S(__i)[__a[__i] - 1]);
492 if (__comp(*__lmax, __S(__i)[__a[__i] - 1]))
493 __lmax = &(__S(__i)[__a[__i] - 1]);
499 for (__i = 0; __i < __m; __i++)
501 _DifferenceType __middle = (__b[__i] + __a[__i]) / 2;
502 if (__lmax && __middle < __ns[__i]
503 && __comp(__S(__i)[__middle], *__lmax))
504 __a[__i] =
std::min(__a[__i] + __n + 1, __ns[__i]);
509 _DifferenceType __leftsize = 0;
510 for (_SeqNumber __i = 0; __i < __m; ++__i)
511 __leftsize += __a[__i] / (__n + 1);
513 _DifferenceType __skew = __rank / (__n + 1) - __leftsize;
523 for (_SeqNumber __i = 0; __i < __m; ++__i)
524 if (__b[__i] < __ns[__i])
527 for (; __skew != 0 && !__pq.
empty(); --__skew)
529 _SeqNumber __source = __pq.
top().second;
533 =
std::min(__a[__source] + __n + 1, __ns[__source]);
534 __b[__source] += __n + 1;
536 if (__b[__source] < __ns[__source])
548 for (_SeqNumber __i = 0; __i < __m; ++__i)
552 for (; __skew != 0; ++__skew)
554 _SeqNumber __source = __pq.
top().second;
557 __a[__source] -= __n + 1;
558 __b[__source] -= __n + 1;
560 if (__a[__source] > 0)
562 __S(__source)[__a[__source] - 1], __source));
576 bool __maxleftset =
false, __minrightset =
false;
579 _Tp __maxleft, __minright;
580 for (_SeqNumber __i = 0; __i < __m; ++__i)
586 __maxleft = __S(__i)[__a[__i] - 1];
592 if (__comp(__maxleft, __S(__i)[__a[__i] - 1]))
593 __maxleft = __S(__i)[__a[__i] - 1];
596 if (__b[__i] < __ns[__i])
600 __minright = __S(__i)[__b[__i]];
601 __minrightset =
true;
606 if (__comp(__S(__i)[__b[__i]], __minright))
607 __minright = __S(__i)[__b[__i]];
614 if (!__maxleftset || __comp(__minright, __maxleft))
624 for (_SeqNumber __i = 0; __i < __m; ++__i)
627 = std::lower_bound(__S(__i), __S(__i) + __ns[__i],
630 __offset += __a[__i] - lb;
_T2 second
first is a copy of the first object
A standard container automatically sorting its contents.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
iterator begin() noexcept
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...
Base class for all library exceptions.
One of the comparison functors.
Struct holding two objects of arbitrary type.
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...
void push_back(const value_type &__x)
Add data to the end of the vector.
void pop()
Removes first element.
GNU parallel code for public use.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
Compare __a pair of types lexicographically, ascending.
const_reference top() const
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_Tp __round_up_to_pow2(_Tp __x)
Round up to the next greater power of 2.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
_Size __rd_log2(_Size __n)
Calculates the rounded-down logarithm of __n for base 2.
_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.
Compare __a pair of types lexicographically, descending.
_T1 first
second_type is the second bound type
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
#define _GLIBCXX_CALL(__n)
Macro to produce log message when entering a function.
Forces sequential execution at compile time.