41 #ifndef _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H
42 #define _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 1
51 namespace __gnu_parallel
54 template<
typename T1,
typename T2,
typename Comparator>
80 template<
typename T1,
typename T2,
typename Comparator>
120 template<
typename RanSeqs,
typename RankType,
typename RankIterator,
125 RankIterator begin_offsets,
128 std::iterator_traits<RanSeqs>::value_type::
129 first_type>::value_type>())
135 typedef typename std::iterator_traits<It>::difference_type
137 typedef typename std::iterator_traits<It>::value_type value_type;
144 difference_type m =
std::distance(begin_seqs, end_seqs), N = 0,
147 for (
int i = 0; i < m; i++)
149 N +=
std::distance(begin_seqs[i].first, begin_seqs[i].second);
150 _GLIBCXX_PARALLEL_ASSERT(
151 std::distance(begin_seqs[i].first, begin_seqs[i].second) > 0);
156 for (
int i = 0; i < m; i++)
157 begin_offsets[i] = begin_seqs[i].second;
162 _GLIBCXX_PARALLEL_ASSERT(m != 0);
163 _GLIBCXX_PARALLEL_ASSERT(N != 0);
164 _GLIBCXX_PARALLEL_ASSERT(rank >= 0);
165 _GLIBCXX_PARALLEL_ASSERT(rank < N);
167 difference_type* ns =
new difference_type[m];
168 difference_type* a =
new difference_type[m];
169 difference_type* b =
new difference_type[m];
172 ns[0] =
std::distance(begin_seqs[0].first, begin_seqs[0].second);
174 for (
int i = 0; i < m; i++)
176 ns[i] =
std::distance(begin_seqs[i].first, begin_seqs[i].second);
186 for (
int i = 0; i < m; i++)
196 #define S(i) (begin_seqs[i].first)
201 for (
int i = 0; i < m; i++)
203 sample.
push_back(std::make_pair(S(i)[n], i));
204 __gnu_sequential::sort(sample.
begin(), sample.
end(), lcomp);
206 for (
int i = 0; i < m; i++)
208 sample.
push_back(std::make_pair(S(i)[0] , i));
210 difference_type localrank = rank / l;
213 for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); ++j)
214 a[sample[j].second] += n + 1;
216 b[sample[j].second] -= n + 1;
224 const value_type* lmax = NULL;
225 for (
int i = 0; i < m; i++)
231 lmax = &(S(i)[a[i] - 1]);
237 if (!comp(S(i)[a[i] - 1], *lmax))
239 lmax = &(S(i)[a[i] - 1]);
247 for (i = 0; i < m; i++)
249 difference_type middle = (b[i] + a[i]) / 2;
250 if (lmax && middle < ns[i] &&
251 lcomp(std::make_pair(S(i)[middle], i),
252 std::make_pair(*lmax, lmax_seq)))
253 a[i] =
std::min(a[i] + n + 1, ns[i]);
258 difference_type leftsize = 0;
259 for (
int i = 0; i < m; i++)
260 leftsize += a[i] / (n + 1);
262 difference_type skew = rank / (n + 1) - leftsize;
272 for (
int i = 0; i < m; i++)
274 pq.
push(std::make_pair(S(i)[b[i]], i));
276 for (; skew != 0 && !pq.
empty(); --skew)
278 int source = pq.
top().second;
281 a[source] =
std::min(a[source] + n + 1, ns[source]);
284 if (b[source] < ns[source])
285 pq.
push(std::make_pair(S(source)[b[source]], source));
295 for (
int i = 0; i < m; i++)
297 pq.
push(std::make_pair(S(i)[a[i] - 1], i));
299 for (; skew != 0; ++skew)
301 int source = pq.
top().second;
308 pq.
push(std::make_pair(S(source)[a[source] - 1], source));
322 value_type* maxleft = NULL;
323 value_type* minright = NULL;
324 for (
int i = 0; i < m; i++)
329 maxleft = &(S(i)[a[i] - 1]);
333 if (!comp(S(i)[a[i] - 1], *maxleft))
334 maxleft = &(S(i)[a[i] - 1]);
340 minright = &(S(i)[b[i]]);
344 if (comp(S(i)[b[i]], *minright))
345 minright = &(S(i)[b[i]]);
351 for (
int i = 0; i < m; i++)
352 begin_offsets[i] = S(i) + a[i];
374 template<
typename T,
typename RanSeqs,
typename RankType,
384 typedef typename std::iterator_traits<It>::difference_type
393 difference_type N = 0;
394 difference_type nmax, n, r;
396 for (
int i = 0; i < m; i++)
397 N +=
std::distance(begin_seqs[i].first, begin_seqs[i].second);
399 if (m == 0 || N == 0 || rank < 0 || rank >= N)
406 difference_type* ns =
new difference_type[m];
407 difference_type* a =
new difference_type[m];
408 difference_type* b =
new difference_type[m];
411 ns[0] =
std::distance(begin_seqs[0].first, begin_seqs[0].second);
413 for (
int i = 0; i < m; ++i)
415 ns[i] =
std::distance(begin_seqs[i].first, begin_seqs[i].second);
425 for (
int i = 0; i < m; ++i)
435 #define S(i) (begin_seqs[i].first)
440 for (
int i = 0; i < m; i++)
442 sample.
push_back(std::make_pair(S(i)[n], i));
443 __gnu_sequential::sort(sample.
begin(), sample.
end(),
447 for (
int i = 0; i < m; i++)
449 sample.
push_back(std::make_pair(S(i)[0] , i));
451 difference_type localrank = rank / l;
454 for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); ++j)
455 a[sample[j].second] += n + 1;
457 b[sample[j].second] -= n + 1;
464 const T* lmax = NULL;
465 for (
int i = 0; i < m; ++i)
470 lmax = &(S(i)[a[i] - 1]);
473 if (comp(*lmax, S(i)[a[i] - 1]))
474 lmax = &(S(i)[a[i] - 1]);
480 for (i = 0; i < m; i++)
482 difference_type middle = (b[i] + a[i]) / 2;
483 if (lmax && middle < ns[i] && comp(S(i)[middle], *lmax))
484 a[i] =
std::min(a[i] + n + 1, ns[i]);
489 difference_type leftsize = 0;
490 for (
int i = 0; i < m; ++i)
491 leftsize += a[i] / (n + 1);
493 difference_type skew = rank / (n + 1) - leftsize;
502 for (
int i = 0; i < m; ++i)
504 pq.
push(std::make_pair(S(i)[b[i]], i));
506 for (; skew != 0 && !pq.
empty(); --skew)
508 int source = pq.
top().second;
511 a[source] =
std::min(a[source] + n + 1, ns[source]);
514 if (b[source] < ns[source])
515 pq.
push(std::make_pair(S(source)[b[source]], source));
525 for (
int i = 0; i < m; ++i)
527 pq.
push(std::make_pair(S(i)[a[i] - 1], i));
529 for (; skew != 0; ++skew)
531 int source = pq.
top().second;
538 pq.
push(std::make_pair(S(source)[a[source] - 1], source));
552 bool maxleftset =
false, minrightset =
false;
556 for (
int i = 0; i < m; ++i)
562 maxleft = S(i)[a[i] - 1];
568 if (comp(maxleft, S(i)[a[i] - 1]))
569 maxleft = S(i)[a[i] - 1];
576 minright = S(i)[b[i]];
582 if (comp(S(i)[b[i]], minright))
583 minright = S(i)[b[i]];
590 if (!maxleftset || comp(minright, maxleft))
600 for (
int i = 0; i < m; ++i)
602 difference_type lb = std::lower_bound(S(i), S(i) + ns[i],