00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041 #ifndef _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H
00042 #define _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 1
00043
00044 #include <vector>
00045 #include <queue>
00046
00047 #include <bits/stl_algo.h>
00048
00049 #include <parallel/sort.h>
00050
00051 namespace __gnu_parallel
00052 {
00053
00054 template<typename _T1, typename _T2, typename _Compare>
00055 class _Lexicographic
00056 : public std::binary_function<std::pair<_T1, _T2>,
00057 std::pair<_T1, _T2>, bool>
00058 {
00059 private:
00060 _Compare& _M_comp;
00061
00062 public:
00063 _Lexicographic(_Compare& __comp) : _M_comp(__comp) { }
00064
00065 bool
00066 operator()(const std::pair<_T1, _T2>& __p1,
00067 const std::pair<_T1, _T2>& __p2) const
00068 {
00069 if (_M_comp(__p1.first, __p2.first))
00070 return true;
00071
00072 if (_M_comp(__p2.first, __p1.first))
00073 return false;
00074
00075
00076 return __p1.second < __p2.second;
00077 }
00078 };
00079
00080
00081 template<typename _T1, typename _T2, typename _Compare>
00082 class _LexicographicReverse : public std::binary_function<_T1, _T2, bool>
00083 {
00084 private:
00085 _Compare& _M_comp;
00086
00087 public:
00088 _LexicographicReverse(_Compare& __comp) : _M_comp(__comp) { }
00089
00090 bool
00091 operator()(const std::pair<_T1, _T2>& __p1,
00092 const std::pair<_T1, _T2>& __p2) const
00093 {
00094 if (_M_comp(__p2.first, __p1.first))
00095 return true;
00096
00097 if (_M_comp(__p1.first, __p2.first))
00098 return false;
00099
00100
00101 return __p2.second < __p1.second;
00102 }
00103 };
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121 template<typename _RanSeqs, typename _RankType, typename _RankIterator,
00122 typename _Compare>
00123 void
00124 multiseq_partition(_RanSeqs __begin_seqs, _RanSeqs __end_seqs,
00125 _RankType __rank,
00126 _RankIterator __begin_offsets,
00127 _Compare __comp = std::less<
00128 typename std::iterator_traits<typename
00129 std::iterator_traits<_RanSeqs>::value_type::
00130 first_type>::value_type>())
00131 {
00132 _GLIBCXX_CALL(__end_seqs - __begin_seqs)
00133
00134 typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type
00135 _It;
00136 typedef typename std::iterator_traits<_RanSeqs>::difference_type
00137 _SeqNumber;
00138 typedef typename std::iterator_traits<_It>::difference_type
00139 _DifferenceType;
00140 typedef typename std::iterator_traits<_It>::value_type _ValueType;
00141
00142 _Lexicographic<_ValueType, _SeqNumber, _Compare> __lcomp(__comp);
00143 _LexicographicReverse<_ValueType, _SeqNumber, _Compare> __lrcomp(__comp);
00144
00145
00146
00147 _DifferenceType __m = std::distance(__begin_seqs, __end_seqs), __nn = 0,
00148 __nmax, __n, __r;
00149
00150 for (_SeqNumber __i = 0; __i < __m; __i++)
00151 {
00152 __nn += std::distance(__begin_seqs[__i].first,
00153 __begin_seqs[__i].second);
00154 _GLIBCXX_PARALLEL_ASSERT(
00155 std::distance(__begin_seqs[__i].first,
00156 __begin_seqs[__i].second) > 0);
00157 }
00158
00159 if (__rank == __nn)
00160 {
00161 for (_SeqNumber __i = 0; __i < __m; __i++)
00162 __begin_offsets[__i] = __begin_seqs[__i].second;
00163
00164 return;
00165 }
00166
00167 _GLIBCXX_PARALLEL_ASSERT(__m != 0);
00168 _GLIBCXX_PARALLEL_ASSERT(__nn != 0);
00169 _GLIBCXX_PARALLEL_ASSERT(__rank >= 0);
00170 _GLIBCXX_PARALLEL_ASSERT(__rank < __nn);
00171
00172 _DifferenceType* __ns = new _DifferenceType[__m];
00173 _DifferenceType* __a = new _DifferenceType[__m];
00174 _DifferenceType* __b = new _DifferenceType[__m];
00175 _DifferenceType __l;
00176
00177 __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second);
00178 __nmax = __ns[0];
00179 for (_SeqNumber __i = 0; __i < __m; __i++)
00180 {
00181 __ns[__i] = std::distance(__begin_seqs[__i].first,
00182 __begin_seqs[__i].second);
00183 __nmax = std::max(__nmax, __ns[__i]);
00184 }
00185
00186 __r = __rd_log2(__nmax) + 1;
00187
00188
00189
00190 __l = (1ULL << __r) - 1;
00191
00192 for (_SeqNumber __i = 0; __i < __m; __i++)
00193 {
00194 __a[__i] = 0;
00195 __b[__i] = __l;
00196 }
00197 __n = __l / 2;
00198
00199
00200
00201
00202 #define __S(__i) (__begin_seqs[__i].first)
00203
00204
00205 std::vector<std::pair<_ValueType, _SeqNumber> > __sample;
00206
00207 for (_SeqNumber __i = 0; __i < __m; __i++)
00208 if (__n < __ns[__i])
00209 __sample.push_back(std::make_pair(__S(__i)[__n], __i));
00210 __gnu_sequential::sort(__sample.begin(), __sample.end(), __lcomp);
00211
00212 for (_SeqNumber __i = 0; __i < __m; __i++)
00213 if (__n >= __ns[__i])
00214 __sample.push_back(
00215 std::make_pair(__S(__i)[0] , __i));
00216
00217 _DifferenceType __localrank = __rank / __l;
00218
00219 _SeqNumber __j;
00220 for (__j = 0;
00221 __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]);
00222 ++__j)
00223 __a[__sample[__j].second] += __n + 1;
00224 for (; __j < __m; __j++)
00225 __b[__sample[__j].second] -= __n + 1;
00226
00227
00228 while (__n > 0)
00229 {
00230 __n /= 2;
00231
00232 _SeqNumber __lmax_seq = -1;
00233 const _ValueType* __lmax = NULL;
00234 for (_SeqNumber __i = 0; __i < __m; __i++)
00235 {
00236 if (__a[__i] > 0)
00237 {
00238 if (!__lmax)
00239 {
00240 __lmax = &(__S(__i)[__a[__i] - 1]);
00241 __lmax_seq = __i;
00242 }
00243 else
00244 {
00245
00246 if (!__comp(__S(__i)[__a[__i] - 1], *__lmax))
00247 {
00248 __lmax = &(__S(__i)[__a[__i] - 1]);
00249 __lmax_seq = __i;
00250 }
00251 }
00252 }
00253 }
00254
00255 _SeqNumber __i;
00256 for (__i = 0; __i < __m; __i++)
00257 {
00258 _DifferenceType __middle = (__b[__i] + __a[__i]) / 2;
00259 if (__lmax && __middle < __ns[__i] &&
00260 __lcomp(std::make_pair(__S(__i)[__middle], __i),
00261 std::make_pair(*__lmax, __lmax_seq)))
00262 __a[__i] = std::min(__a[__i] + __n + 1, __ns[__i]);
00263 else
00264 __b[__i] -= __n + 1;
00265 }
00266
00267 _DifferenceType __leftsize = 0;
00268 for (_SeqNumber __i = 0; __i < __m; __i++)
00269 __leftsize += __a[__i] / (__n + 1);
00270
00271 _DifferenceType __skew = __rank / (__n + 1) - __leftsize;
00272
00273 if (__skew > 0)
00274 {
00275
00276 std::priority_queue<std::pair<_ValueType, _SeqNumber>,
00277 std::vector<std::pair<_ValueType, _SeqNumber> >,
00278 _LexicographicReverse<_ValueType, _SeqNumber, _Compare> >
00279 __pq(__lrcomp);
00280
00281 for (_SeqNumber __i = 0; __i < __m; __i++)
00282 if (__b[__i] < __ns[__i])
00283 __pq.push(std::make_pair(__S(__i)[__b[__i]], __i));
00284
00285 for (; __skew != 0 && !__pq.empty(); --__skew)
00286 {
00287 _SeqNumber __source = __pq.top().second;
00288 __pq.pop();
00289
00290 __a[__source]
00291 = std::min(__a[__source] + __n + 1, __ns[__source]);
00292 __b[__source] += __n + 1;
00293
00294 if (__b[__source] < __ns[__source])
00295 __pq.push(
00296 std::make_pair(__S(__source)[__b[__source]], __source));
00297 }
00298 }
00299 else if (__skew < 0)
00300 {
00301
00302 std::priority_queue<std::pair<_ValueType, _SeqNumber>,
00303 std::vector<std::pair<_ValueType, _SeqNumber> >,
00304 _Lexicographic<_ValueType, _SeqNumber, _Compare> >
00305 __pq(__lcomp);
00306
00307 for (_SeqNumber __i = 0; __i < __m; __i++)
00308 if (__a[__i] > 0)
00309 __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i));
00310
00311 for (; __skew != 0; ++__skew)
00312 {
00313 _SeqNumber __source = __pq.top().second;
00314 __pq.pop();
00315
00316 __a[__source] -= __n + 1;
00317 __b[__source] -= __n + 1;
00318
00319 if (__a[__source] > 0)
00320 __pq.push(std::make_pair(
00321 __S(__source)[__a[__source] - 1], __source));
00322 }
00323 }
00324 }
00325
00326
00327
00328
00329
00330
00331
00332
00333
00334
00335 _ValueType* __maxleft = NULL;
00336 _ValueType* __minright = NULL;
00337 for (_SeqNumber __i = 0; __i < __m; __i++)
00338 {
00339 if (__a[__i] > 0)
00340 {
00341 if (!__maxleft)
00342 __maxleft = &(__S(__i)[__a[__i] - 1]);
00343 else
00344 {
00345
00346 if (!__comp(__S(__i)[__a[__i] - 1], *__maxleft))
00347 __maxleft = &(__S(__i)[__a[__i] - 1]);
00348 }
00349 }
00350 if (__b[__i] < __ns[__i])
00351 {
00352 if (!__minright)
00353 __minright = &(__S(__i)[__b[__i]]);
00354 else
00355 {
00356
00357 if (__comp(__S(__i)[__b[__i]], *__minright))
00358 __minright = &(__S(__i)[__b[__i]]);
00359 }
00360 }
00361 }
00362
00363 _SeqNumber __seq = 0;
00364 for (_SeqNumber __i = 0; __i < __m; __i++)
00365 __begin_offsets[__i] = __S(__i) + __a[__i];
00366
00367 delete[] __ns;
00368 delete[] __a;
00369 delete[] __b;
00370 }
00371
00372
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387 template<typename _Tp, typename _RanSeqs, typename _RankType,
00388 typename _Compare>
00389 _Tp
00390 multiseq_selection(_RanSeqs __begin_seqs, _RanSeqs __end_seqs,
00391 _RankType __rank,
00392 _RankType& __offset, _Compare __comp = std::less<_Tp>())
00393 {
00394 _GLIBCXX_CALL(__end_seqs - __begin_seqs)
00395
00396 typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type
00397 _It;
00398 typedef typename std::iterator_traits<_RanSeqs>::difference_type
00399 _SeqNumber;
00400 typedef typename std::iterator_traits<_It>::difference_type
00401 _DifferenceType;
00402
00403 _Lexicographic<_Tp, _SeqNumber, _Compare> __lcomp(__comp);
00404 _LexicographicReverse<_Tp, _SeqNumber, _Compare> __lrcomp(__comp);
00405
00406
00407
00408 _DifferenceType __m = std::distance(__begin_seqs, __end_seqs);
00409 _DifferenceType __nn = 0;
00410 _DifferenceType __nmax, __n, __r;
00411
00412 for (_SeqNumber __i = 0; __i < __m; __i++)
00413 __nn += std::distance(__begin_seqs[__i].first,
00414 __begin_seqs[__i].second);
00415
00416 if (__m == 0 || __nn == 0 || __rank < 0 || __rank >= __nn)
00417 {
00418
00419 throw std::exception();
00420 }
00421
00422
00423 _DifferenceType* __ns = new _DifferenceType[__m];
00424 _DifferenceType* __a = new _DifferenceType[__m];
00425 _DifferenceType* __b = new _DifferenceType[__m];
00426 _DifferenceType __l;
00427
00428 __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second);
00429 __nmax = __ns[0];
00430 for (_SeqNumber __i = 0; __i < __m; ++__i)
00431 {
00432 __ns[__i] = std::distance(__begin_seqs[__i].first,
00433 __begin_seqs[__i].second);
00434 __nmax = std::max(__nmax, __ns[__i]);
00435 }
00436
00437 __r = __rd_log2(__nmax) + 1;
00438
00439
00440
00441 __l = __round_up_to_pow2(__r) - 1;
00442
00443 for (_SeqNumber __i = 0; __i < __m; ++__i)
00444 {
00445 __a[__i] = 0;
00446 __b[__i] = __l;
00447 }
00448 __n = __l / 2;
00449
00450
00451
00452
00453 #define __S(__i) (__begin_seqs[__i].first)
00454
00455
00456 std::vector<std::pair<_Tp, _SeqNumber> > __sample;
00457
00458 for (_SeqNumber __i = 0; __i < __m; __i++)
00459 if (__n < __ns[__i])
00460 __sample.push_back(std::make_pair(__S(__i)[__n], __i));
00461 __gnu_sequential::sort(__sample.begin(), __sample.end(),
00462 __lcomp, sequential_tag());
00463
00464
00465 for (_SeqNumber __i = 0; __i < __m; __i++)
00466 if (__n >= __ns[__i])
00467 __sample.push_back(
00468 std::make_pair(__S(__i)[0] , __i));
00469
00470 _DifferenceType __localrank = __rank / __l;
00471
00472 _SeqNumber __j;
00473 for (__j = 0;
00474 __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]);
00475 ++__j)
00476 __a[__sample[__j].second] += __n + 1;
00477 for (; __j < __m; ++__j)
00478 __b[__sample[__j].second] -= __n + 1;
00479
00480
00481 while (__n > 0)
00482 {
00483 __n /= 2;
00484
00485 const _Tp* __lmax = NULL;
00486 for (_SeqNumber __i = 0; __i < __m; ++__i)
00487 {
00488 if (__a[__i] > 0)
00489 {
00490 if (!__lmax)
00491 __lmax = &(__S(__i)[__a[__i] - 1]);
00492 else
00493 {
00494 if (__comp(*__lmax, __S(__i)[__a[__i] - 1]))
00495 __lmax = &(__S(__i)[__a[__i] - 1]);
00496 }
00497 }
00498 }
00499
00500 _SeqNumber __i;
00501 for (__i = 0; __i < __m; __i++)
00502 {
00503 _DifferenceType __middle = (__b[__i] + __a[__i]) / 2;
00504 if (__lmax && __middle < __ns[__i]
00505 && __comp(__S(__i)[__middle], *__lmax))
00506 __a[__i] = std::min(__a[__i] + __n + 1, __ns[__i]);
00507 else
00508 __b[__i] -= __n + 1;
00509 }
00510
00511 _DifferenceType __leftsize = 0;
00512 for (_SeqNumber __i = 0; __i < __m; ++__i)
00513 __leftsize += __a[__i] / (__n + 1);
00514
00515 _DifferenceType __skew = __rank / (__n + 1) - __leftsize;
00516
00517 if (__skew > 0)
00518 {
00519
00520 std::priority_queue<std::pair<_Tp, _SeqNumber>,
00521 std::vector<std::pair<_Tp, _SeqNumber> >,
00522 _LexicographicReverse<_Tp, _SeqNumber, _Compare> >
00523 __pq(__lrcomp);
00524
00525 for (_SeqNumber __i = 0; __i < __m; ++__i)
00526 if (__b[__i] < __ns[__i])
00527 __pq.push(std::make_pair(__S(__i)[__b[__i]], __i));
00528
00529 for (; __skew != 0 && !__pq.empty(); --__skew)
00530 {
00531 _SeqNumber __source = __pq.top().second;
00532 __pq.pop();
00533
00534 __a[__source]
00535 = std::min(__a[__source] + __n + 1, __ns[__source]);
00536 __b[__source] += __n + 1;
00537
00538 if (__b[__source] < __ns[__source])
00539 __pq.push(
00540 std::make_pair(__S(__source)[__b[__source]], __source));
00541 }
00542 }
00543 else if (__skew < 0)
00544 {
00545
00546 std::priority_queue<std::pair<_Tp, _SeqNumber>,
00547 std::vector<std::pair<_Tp, _SeqNumber> >,
00548 _Lexicographic<_Tp, _SeqNumber, _Compare> > __pq(__lcomp);
00549
00550 for (_SeqNumber __i = 0; __i < __m; ++__i)
00551 if (__a[__i] > 0)
00552 __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i));
00553
00554 for (; __skew != 0; ++__skew)
00555 {
00556 _SeqNumber __source = __pq.top().second;
00557 __pq.pop();
00558
00559 __a[__source] -= __n + 1;
00560 __b[__source] -= __n + 1;
00561
00562 if (__a[__source] > 0)
00563 __pq.push(std::make_pair(
00564 __S(__source)[__a[__source] - 1], __source));
00565 }
00566 }
00567 }
00568
00569
00570
00571
00572
00573
00574
00575
00576
00577
00578 bool __maxleftset = false, __minrightset = false;
00579
00580
00581 _Tp __maxleft, __minright;
00582 for (_SeqNumber __i = 0; __i < __m; ++__i)
00583 {
00584 if (__a[__i] > 0)
00585 {
00586 if (!__maxleftset)
00587 {
00588 __maxleft = __S(__i)[__a[__i] - 1];
00589 __maxleftset = true;
00590 }
00591 else
00592 {
00593
00594 if (__comp(__maxleft, __S(__i)[__a[__i] - 1]))
00595 __maxleft = __S(__i)[__a[__i] - 1];
00596 }
00597 }
00598 if (__b[__i] < __ns[__i])
00599 {
00600 if (!__minrightset)
00601 {
00602 __minright = __S(__i)[__b[__i]];
00603 __minrightset = true;
00604 }
00605 else
00606 {
00607
00608 if (__comp(__S(__i)[__b[__i]], __minright))
00609 __minright = __S(__i)[__b[__i]];
00610 }
00611 }
00612 }
00613
00614
00615
00616 if (!__maxleftset || __comp(__minright, __maxleft))
00617 {
00618
00619 __offset = 0;
00620 }
00621 else
00622 {
00623
00624 __offset = 0;
00625
00626 for (_SeqNumber __i = 0; __i < __m; ++__i)
00627 {
00628 _DifferenceType lb
00629 = std::lower_bound(__S(__i), __S(__i) + __ns[__i],
00630 __minright,
00631 __comp) - __S(__i);
00632 __offset += __a[__i] - lb;
00633 }
00634 }
00635
00636 delete[] __ns;
00637 delete[] __a;
00638 delete[] __b;
00639
00640 return __minright;
00641 }
00642 }
00643
00644 #undef __S
00645
00646 #endif