]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
8d9254fc | 3 | // Copyright (C) 2007-2020 Free Software Foundation, Inc. |
c2ba9709 JS |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
c2ba9709 JS |
9 | // version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
c2ba9709 | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
c2ba9709 JS |
24 | |
25 | /** @file parallel/multiseq_selection.h | |
1acba85b | 26 | * @brief Functions to find elements of a certain global __rank in |
c2ba9709 JS |
27 | * multiple sorted sequences. Also serves for splitting such |
28 | * sequence sets. | |
1904bef1 JS |
29 | * |
30 | * The algorithm description can be found in | |
31 | * | |
32 | * P. J. Varman, S. D. Scheufler, B. R. Iyer, and G. R. Ricard. | |
33 | * Merging Multiple Lists on Hierarchical-Memory Multiprocessors. | |
3c732e6f | 34 | * Journal of Parallel and Distributed Computing, 12(2):171-177, 1991. |
1904bef1 | 35 | * |
c2ba9709 JS |
36 | * This file is a GNU parallel extension to the Standard C++ Library. |
37 | */ | |
38 | ||
39 | // Written by Johannes Singler. | |
40 | ||
41 | #ifndef _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H | |
42 | #define _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 1 | |
43 | ||
44 | #include <vector> | |
45 | #include <queue> | |
46 | ||
47 | #include <bits/stl_algo.h> | |
48 | ||
c2ba9709 JS |
49 | namespace __gnu_parallel |
50 | { | |
1acba85b JS |
51 | /** @brief Compare __a pair of types lexicographically, ascending. */ |
52 | template<typename _T1, typename _T2, typename _Compare> | |
53 | class _Lexicographic | |
77d16198 PC |
54 | : public std::binary_function<std::pair<_T1, _T2>, |
55 | std::pair<_T1, _T2>, bool> | |
531898c3 PC |
56 | { |
57 | private: | |
54384f7f | 58 | _Compare& _M_comp; |
c2ba9709 | 59 | |
531898c3 | 60 | public: |
54384f7f | 61 | _Lexicographic(_Compare& __comp) : _M_comp(__comp) { } |
c2ba9709 | 62 | |
531898c3 | 63 | bool |
1acba85b | 64 | operator()(const std::pair<_T1, _T2>& __p1, |
15ac3c72 | 65 | const std::pair<_T1, _T2>& __p2) const |
531898c3 | 66 | { |
15ac3c72 JS |
67 | if (_M_comp(__p1.first, __p2.first)) |
68 | return true; | |
c2ba9709 | 69 | |
15ac3c72 JS |
70 | if (_M_comp(__p2.first, __p1.first)) |
71 | return false; | |
c2ba9709 | 72 | |
15ac3c72 JS |
73 | // Firsts are equal. |
74 | return __p1.second < __p2.second; | |
531898c3 PC |
75 | } |
76 | }; | |
c2ba9709 | 77 | |
1acba85b JS |
78 | /** @brief Compare __a pair of types lexicographically, descending. */ |
79 | template<typename _T1, typename _T2, typename _Compare> | |
80 | class _LexicographicReverse : public std::binary_function<_T1, _T2, bool> | |
531898c3 PC |
81 | { |
82 | private: | |
54384f7f | 83 | _Compare& _M_comp; |
c2ba9709 | 84 | |
531898c3 | 85 | public: |
54384f7f | 86 | _LexicographicReverse(_Compare& __comp) : _M_comp(__comp) { } |
c2ba9709 | 87 | |
531898c3 | 88 | bool |
1acba85b | 89 | operator()(const std::pair<_T1, _T2>& __p1, |
15ac3c72 | 90 | const std::pair<_T1, _T2>& __p2) const |
531898c3 | 91 | { |
15ac3c72 JS |
92 | if (_M_comp(__p2.first, __p1.first)) |
93 | return true; | |
c2ba9709 | 94 | |
15ac3c72 JS |
95 | if (_M_comp(__p1.first, __p2.first)) |
96 | return false; | |
c2ba9709 | 97 | |
15ac3c72 JS |
98 | // Firsts are equal. |
99 | return __p2.second < __p1.second; | |
531898c3 PC |
100 | } |
101 | }; | |
c2ba9709 JS |
102 | |
103 | /** | |
4459d22e | 104 | * @brief Splits several sorted sequences at a certain global __rank, |
c2ba9709 | 105 | * resulting in a splitting point for each sequence. |
4459d22e | 106 | * The sequences are passed via a sequence of random-access |
c2ba9709 JS |
107 | * iterator pairs, none of the sequences may be empty. If there |
108 | * are several equal elements across the split, the ones on the | |
1acba85b JS |
109 | * __left side will be chosen from sequences with smaller number. |
110 | * @param __begin_seqs Begin of the sequence of iterator pairs. | |
111 | * @param __end_seqs End of the sequence of iterator pairs. | |
4459d22e | 112 | * @param __rank The global rank to partition at. |
1acba85b JS |
113 | * @param __begin_offsets A random-access __sequence __begin where the |
114 | * __result will be stored in. Each element of the sequence is an | |
c2ba9709 | 115 | * iterator that points to the first element on the greater part of |
1acba85b JS |
116 | * the respective __sequence. |
117 | * @param __comp The ordering functor, defaults to std::less<_Tp>. | |
c2ba9709 | 118 | */ |
1acba85b JS |
119 | template<typename _RanSeqs, typename _RankType, typename _RankIterator, |
120 | typename _Compare> | |
531898c3 | 121 | void |
1acba85b JS |
122 | multiseq_partition(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, |
123 | _RankType __rank, | |
124 | _RankIterator __begin_offsets, | |
125 | _Compare __comp = std::less< | |
214ece29 | 126 | typename std::iterator_traits<typename |
1acba85b JS |
127 | std::iterator_traits<_RanSeqs>::value_type:: |
128 | first_type>::value_type>()) // std::less<_Tp> | |
531898c3 | 129 | { |
1acba85b | 130 | _GLIBCXX_CALL(__end_seqs - __begin_seqs) |
531898c3 | 131 | |
1acba85b JS |
132 | typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type |
133 | _It; | |
8b0c13a8 JS |
134 | typedef typename std::iterator_traits<_RanSeqs>::difference_type |
135 | _SeqNumber; | |
1acba85b | 136 | typedef typename std::iterator_traits<_It>::difference_type |
15ac3c72 | 137 | _DifferenceType; |
1acba85b | 138 | typedef typename std::iterator_traits<_It>::value_type _ValueType; |
531898c3 | 139 | |
8b0c13a8 JS |
140 | _Lexicographic<_ValueType, _SeqNumber, _Compare> __lcomp(__comp); |
141 | _LexicographicReverse<_ValueType, _SeqNumber, _Compare> __lrcomp(__comp); | |
531898c3 PC |
142 | |
143 | // Number of sequences, number of elements in total (possibly | |
144 | // including padding). | |
77d16198 | 145 | _DifferenceType __m = std::distance(__begin_seqs, __end_seqs), __nn = 0, |
1acba85b | 146 | __nmax, __n, __r; |
531898c3 | 147 | |
8b0c13a8 | 148 | for (_SeqNumber __i = 0; __i < __m; __i++) |
214ece29 | 149 | { |
77d16198 | 150 | __nn += std::distance(__begin_seqs[__i].first, |
15ac3c72 | 151 | __begin_seqs[__i].second); |
214ece29 | 152 | _GLIBCXX_PARALLEL_ASSERT( |
15ac3c72 JS |
153 | std::distance(__begin_seqs[__i].first, |
154 | __begin_seqs[__i].second) > 0); | |
214ece29 | 155 | } |
531898c3 | 156 | |
77d16198 | 157 | if (__rank == __nn) |
214ece29 | 158 | { |
8b0c13a8 | 159 | for (_SeqNumber __i = 0; __i < __m; __i++) |
1acba85b JS |
160 | __begin_offsets[__i] = __begin_seqs[__i].second; // Very end. |
161 | // Return __m - 1; | |
214ece29 JS |
162 | return; |
163 | } | |
164 | ||
1acba85b | 165 | _GLIBCXX_PARALLEL_ASSERT(__m != 0); |
77d16198 | 166 | _GLIBCXX_PARALLEL_ASSERT(__nn != 0); |
1acba85b | 167 | _GLIBCXX_PARALLEL_ASSERT(__rank >= 0); |
77d16198 | 168 | _GLIBCXX_PARALLEL_ASSERT(__rank < __nn); |
531898c3 | 169 | |
1acba85b JS |
170 | _DifferenceType* __ns = new _DifferenceType[__m]; |
171 | _DifferenceType* __a = new _DifferenceType[__m]; | |
172 | _DifferenceType* __b = new _DifferenceType[__m]; | |
173 | _DifferenceType __l; | |
531898c3 | 174 | |
1acba85b JS |
175 | __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second); |
176 | __nmax = __ns[0]; | |
8b0c13a8 | 177 | for (_SeqNumber __i = 0; __i < __m; __i++) |
15ac3c72 JS |
178 | { |
179 | __ns[__i] = std::distance(__begin_seqs[__i].first, | |
180 | __begin_seqs[__i].second); | |
181 | __nmax = std::max(__nmax, __ns[__i]); | |
182 | } | |
531898c3 | 183 | |
4459d22e | 184 | __r = __rd_log2(__nmax) + 1; |
531898c3 | 185 | |
1acba85b JS |
186 | // Pad all lists to this length, at least as long as any ns[__i], |
187 | // equality iff __nmax = 2^__k - 1. | |
188 | __l = (1ULL << __r) - 1; | |
531898c3 | 189 | |
8b0c13a8 | 190 | for (_SeqNumber __i = 0; __i < __m; __i++) |
15ac3c72 JS |
191 | { |
192 | __a[__i] = 0; | |
193 | __b[__i] = __l; | |
194 | } | |
1acba85b | 195 | __n = __l / 2; |
531898c3 PC |
196 | |
197 | // Invariants: | |
1acba85b | 198 | // 0 <= __a[__i] <= __ns[__i], 0 <= __b[__i] <= __l |
c2ba9709 | 199 | |
1acba85b | 200 | #define __S(__i) (__begin_seqs[__i].first) |
c2ba9709 | 201 | |
531898c3 | 202 | // Initial partition. |
8b0c13a8 | 203 | std::vector<std::pair<_ValueType, _SeqNumber> > __sample; |
531898c3 | 204 | |
8b0c13a8 | 205 | for (_SeqNumber __i = 0; __i < __m; __i++) |
15ac3c72 JS |
206 | if (__n < __ns[__i]) //__sequence long enough |
207 | __sample.push_back(std::make_pair(__S(__i)[__n], __i)); | |
1acba85b | 208 | __gnu_sequential::sort(__sample.begin(), __sample.end(), __lcomp); |
531898c3 | 209 | |
8b0c13a8 | 210 | for (_SeqNumber __i = 0; __i < __m; __i++) //conceptual infinity |
15ac3c72 JS |
211 | if (__n >= __ns[__i]) //__sequence too short, conceptual infinity |
212 | __sample.push_back( | |
213 | std::make_pair(__S(__i)[0] /*__dummy element*/, __i)); | |
531898c3 | 214 | |
15e2a6c0 | 215 | _DifferenceType __localrank = __rank / __l; |
531898c3 | 216 | |
8b0c13a8 | 217 | _SeqNumber __j; |
15ac3c72 | 218 | for (__j = 0; |
4459d22e JS |
219 | __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]); |
220 | ++__j) | |
15ac3c72 | 221 | __a[__sample[__j].second] += __n + 1; |
1acba85b | 222 | for (; __j < __m; __j++) |
15ac3c72 | 223 | __b[__sample[__j].second] -= __n + 1; |
531898c3 PC |
224 | |
225 | // Further refinement. | |
1acba85b | 226 | while (__n > 0) |
15ac3c72 JS |
227 | { |
228 | __n /= 2; | |
229 | ||
8b0c13a8 | 230 | _SeqNumber __lmax_seq = -1; // to avoid warning |
8fc81078 | 231 | const _ValueType* __lmax = 0; // impossible to avoid the warning? |
8b0c13a8 | 232 | for (_SeqNumber __i = 0; __i < __m; __i++) |
15ac3c72 JS |
233 | { |
234 | if (__a[__i] > 0) | |
235 | { | |
236 | if (!__lmax) | |
237 | { | |
238 | __lmax = &(__S(__i)[__a[__i] - 1]); | |
239 | __lmax_seq = __i; | |
240 | } | |
241 | else | |
242 | { | |
243 | // Max, favor rear sequences. | |
244 | if (!__comp(__S(__i)[__a[__i] - 1], *__lmax)) | |
245 | { | |
246 | __lmax = &(__S(__i)[__a[__i] - 1]); | |
247 | __lmax_seq = __i; | |
248 | } | |
249 | } | |
250 | } | |
251 | } | |
252 | ||
8b0c13a8 | 253 | _SeqNumber __i; |
15ac3c72 JS |
254 | for (__i = 0; __i < __m; __i++) |
255 | { | |
256 | _DifferenceType __middle = (__b[__i] + __a[__i]) / 2; | |
257 | if (__lmax && __middle < __ns[__i] && | |
258 | __lcomp(std::make_pair(__S(__i)[__middle], __i), | |
259 | std::make_pair(*__lmax, __lmax_seq))) | |
260 | __a[__i] = std::min(__a[__i] + __n + 1, __ns[__i]); | |
261 | else | |
262 | __b[__i] -= __n + 1; | |
263 | } | |
264 | ||
15e2a6c0 | 265 | _DifferenceType __leftsize = 0; |
8b0c13a8 | 266 | for (_SeqNumber __i = 0; __i < __m; __i++) |
15ac3c72 | 267 | __leftsize += __a[__i] / (__n + 1); |
15e2a6c0 JS |
268 | |
269 | _DifferenceType __skew = __rank / (__n + 1) - __leftsize; | |
15ac3c72 JS |
270 | |
271 | if (__skew > 0) | |
272 | { | |
273 | // Move to the left, find smallest. | |
8b0c13a8 JS |
274 | std::priority_queue<std::pair<_ValueType, _SeqNumber>, |
275 | std::vector<std::pair<_ValueType, _SeqNumber> >, | |
276 | _LexicographicReverse<_ValueType, _SeqNumber, _Compare> > | |
15ac3c72 JS |
277 | __pq(__lrcomp); |
278 | ||
8b0c13a8 | 279 | for (_SeqNumber __i = 0; __i < __m; __i++) |
15ac3c72 JS |
280 | if (__b[__i] < __ns[__i]) |
281 | __pq.push(std::make_pair(__S(__i)[__b[__i]], __i)); | |
282 | ||
283 | for (; __skew != 0 && !__pq.empty(); --__skew) | |
284 | { | |
8b0c13a8 | 285 | _SeqNumber __source = __pq.top().second; |
15ac3c72 JS |
286 | __pq.pop(); |
287 | ||
4459d22e JS |
288 | __a[__source] |
289 | = std::min(__a[__source] + __n + 1, __ns[__source]); | |
290 | __b[__source] += __n + 1; | |
15ac3c72 | 291 | |
4459d22e | 292 | if (__b[__source] < __ns[__source]) |
15ac3c72 | 293 | __pq.push( |
4459d22e | 294 | std::make_pair(__S(__source)[__b[__source]], __source)); |
15ac3c72 JS |
295 | } |
296 | } | |
297 | else if (__skew < 0) | |
298 | { | |
299 | // Move to the right, find greatest. | |
8b0c13a8 JS |
300 | std::priority_queue<std::pair<_ValueType, _SeqNumber>, |
301 | std::vector<std::pair<_ValueType, _SeqNumber> >, | |
302 | _Lexicographic<_ValueType, _SeqNumber, _Compare> > | |
303 | __pq(__lcomp); | |
15ac3c72 | 304 | |
8b0c13a8 | 305 | for (_SeqNumber __i = 0; __i < __m; __i++) |
15ac3c72 JS |
306 | if (__a[__i] > 0) |
307 | __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i)); | |
308 | ||
309 | for (; __skew != 0; ++__skew) | |
310 | { | |
8b0c13a8 | 311 | _SeqNumber __source = __pq.top().second; |
15ac3c72 JS |
312 | __pq.pop(); |
313 | ||
4459d22e JS |
314 | __a[__source] -= __n + 1; |
315 | __b[__source] -= __n + 1; | |
15ac3c72 | 316 | |
4459d22e JS |
317 | if (__a[__source] > 0) |
318 | __pq.push(std::make_pair( | |
319 | __S(__source)[__a[__source] - 1], __source)); | |
15ac3c72 JS |
320 | } |
321 | } | |
322 | } | |
531898c3 PC |
323 | |
324 | // Postconditions: | |
15ac3c72 JS |
325 | // __a[__i] == __b[__i] in most cases, except when __a[__i] has been |
326 | // clamped because of having reached the boundary | |
531898c3 PC |
327 | |
328 | // Now return the result, calculate the offset. | |
329 | ||
330 | // Compare the keys on both edges of the border. | |
331 | ||
332 | // Maximum of left edge, minimum of right edge. | |
8fc81078 PC |
333 | _ValueType* __maxleft = 0; |
334 | _ValueType* __minright = 0; | |
8b0c13a8 | 335 | for (_SeqNumber __i = 0; __i < __m; __i++) |
15ac3c72 JS |
336 | { |
337 | if (__a[__i] > 0) | |
338 | { | |
339 | if (!__maxleft) | |
340 | __maxleft = &(__S(__i)[__a[__i] - 1]); | |
341 | else | |
342 | { | |
343 | // Max, favor rear sequences. | |
344 | if (!__comp(__S(__i)[__a[__i] - 1], *__maxleft)) | |
345 | __maxleft = &(__S(__i)[__a[__i] - 1]); | |
346 | } | |
347 | } | |
348 | if (__b[__i] < __ns[__i]) | |
349 | { | |
350 | if (!__minright) | |
351 | __minright = &(__S(__i)[__b[__i]]); | |
352 | else | |
353 | { | |
354 | // Min, favor fore sequences. | |
355 | if (__comp(__S(__i)[__b[__i]], *__minright)) | |
356 | __minright = &(__S(__i)[__b[__i]]); | |
357 | } | |
358 | } | |
359 | } | |
531898c3 | 360 | |
8b0c13a8 JS |
361 | _SeqNumber __seq = 0; |
362 | for (_SeqNumber __i = 0; __i < __m; __i++) | |
15ac3c72 | 363 | __begin_offsets[__i] = __S(__i) + __a[__i]; |
531898c3 | 364 | |
1acba85b JS |
365 | delete[] __ns; |
366 | delete[] __a; | |
367 | delete[] __b; | |
531898c3 | 368 | } |
c2ba9709 JS |
369 | |
370 | ||
c2ba9709 | 371 | /** |
4459d22e | 372 | * @brief Selects the element at a certain global __rank from several |
c2ba9709 JS |
373 | * sorted sequences. |
374 | * | |
4459d22e | 375 | * The sequences are passed via a sequence of random-access |
c2ba9709 | 376 | * iterator pairs, none of the sequences may be empty. |
1acba85b JS |
377 | * @param __begin_seqs Begin of the sequence of iterator pairs. |
378 | * @param __end_seqs End of the sequence of iterator pairs. | |
4459d22e | 379 | * @param __rank The global rank to partition at. |
1acba85b | 380 | * @param __offset The rank of the selected element in the global |
c2ba9709 JS |
381 | * subsequence of elements equal to the selected element. If the |
382 | * selected element is unique, this number is 0. | |
1acba85b | 383 | * @param __comp The ordering functor, defaults to std::less. |
c2ba9709 | 384 | */ |
1acba85b | 385 | template<typename _Tp, typename _RanSeqs, typename _RankType, |
15ac3c72 | 386 | typename _Compare> |
1acba85b | 387 | _Tp |
15ac3c72 JS |
388 | multiseq_selection(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, |
389 | _RankType __rank, | |
390 | _RankType& __offset, _Compare __comp = std::less<_Tp>()) | |
531898c3 | 391 | { |
1acba85b | 392 | _GLIBCXX_CALL(__end_seqs - __begin_seqs) |
c2ba9709 | 393 | |
1acba85b | 394 | typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type |
15ac3c72 | 395 | _It; |
8b0c13a8 JS |
396 | typedef typename std::iterator_traits<_RanSeqs>::difference_type |
397 | _SeqNumber; | |
1acba85b | 398 | typedef typename std::iterator_traits<_It>::difference_type |
15ac3c72 | 399 | _DifferenceType; |
c2ba9709 | 400 | |
8b0c13a8 JS |
401 | _Lexicographic<_Tp, _SeqNumber, _Compare> __lcomp(__comp); |
402 | _LexicographicReverse<_Tp, _SeqNumber, _Compare> __lrcomp(__comp); | |
c2ba9709 | 403 | |
531898c3 PC |
404 | // Number of sequences, number of elements in total (possibly |
405 | // including padding). | |
1acba85b | 406 | _DifferenceType __m = std::distance(__begin_seqs, __end_seqs); |
77d16198 | 407 | _DifferenceType __nn = 0; |
1acba85b | 408 | _DifferenceType __nmax, __n, __r; |
c2ba9709 | 409 | |
8b0c13a8 | 410 | for (_SeqNumber __i = 0; __i < __m; __i++) |
77d16198 PC |
411 | __nn += std::distance(__begin_seqs[__i].first, |
412 | __begin_seqs[__i].second); | |
c2ba9709 | 413 | |
77d16198 | 414 | if (__m == 0 || __nn == 0 || __rank < 0 || __rank >= __nn) |
15ac3c72 JS |
415 | { |
416 | // result undefined if there is no data or __rank is outside bounds | |
417 | throw std::exception(); | |
418 | } | |
c2ba9709 JS |
419 | |
420 | ||
1acba85b JS |
421 | _DifferenceType* __ns = new _DifferenceType[__m]; |
422 | _DifferenceType* __a = new _DifferenceType[__m]; | |
423 | _DifferenceType* __b = new _DifferenceType[__m]; | |
424 | _DifferenceType __l; | |
c2ba9709 | 425 | |
1acba85b JS |
426 | __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second); |
427 | __nmax = __ns[0]; | |
8b0c13a8 | 428 | for (_SeqNumber __i = 0; __i < __m; ++__i) |
15ac3c72 JS |
429 | { |
430 | __ns[__i] = std::distance(__begin_seqs[__i].first, | |
431 | __begin_seqs[__i].second); | |
432 | __nmax = std::max(__nmax, __ns[__i]); | |
433 | } | |
c2ba9709 | 434 | |
4459d22e | 435 | __r = __rd_log2(__nmax) + 1; |
c2ba9709 | 436 | |
1acba85b JS |
437 | // Pad all lists to this length, at least as long as any ns[__i], |
438 | // equality iff __nmax = 2^__k - 1 | |
77d16198 | 439 | __l = __round_up_to_pow2(__r) - 1; |
c2ba9709 | 440 | |
8b0c13a8 | 441 | for (_SeqNumber __i = 0; __i < __m; ++__i) |
15ac3c72 JS |
442 | { |
443 | __a[__i] = 0; | |
444 | __b[__i] = __l; | |
445 | } | |
1acba85b | 446 | __n = __l / 2; |
c2ba9709 | 447 | |
531898c3 | 448 | // Invariants: |
1acba85b | 449 | // 0 <= __a[__i] <= __ns[__i], 0 <= __b[__i] <= __l |
c2ba9709 | 450 | |
1acba85b | 451 | #define __S(__i) (__begin_seqs[__i].first) |
c2ba9709 | 452 | |
531898c3 | 453 | // Initial partition. |
8b0c13a8 | 454 | std::vector<std::pair<_Tp, _SeqNumber> > __sample; |
c2ba9709 | 455 | |
8b0c13a8 | 456 | for (_SeqNumber __i = 0; __i < __m; __i++) |
15ac3c72 JS |
457 | if (__n < __ns[__i]) |
458 | __sample.push_back(std::make_pair(__S(__i)[__n], __i)); | |
1acba85b | 459 | __gnu_sequential::sort(__sample.begin(), __sample.end(), |
15ac3c72 | 460 | __lcomp, sequential_tag()); |
c2ba9709 | 461 | |
531898c3 | 462 | // Conceptual infinity. |
8b0c13a8 | 463 | for (_SeqNumber __i = 0; __i < __m; __i++) |
15ac3c72 JS |
464 | if (__n >= __ns[__i]) |
465 | __sample.push_back( | |
466 | std::make_pair(__S(__i)[0] /*__dummy element*/, __i)); | |
c2ba9709 | 467 | |
15e2a6c0 | 468 | _DifferenceType __localrank = __rank / __l; |
c2ba9709 | 469 | |
8b0c13a8 | 470 | _SeqNumber __j; |
15ac3c72 | 471 | for (__j = 0; |
4459d22e JS |
472 | __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]); |
473 | ++__j) | |
15ac3c72 | 474 | __a[__sample[__j].second] += __n + 1; |
1acba85b | 475 | for (; __j < __m; ++__j) |
15ac3c72 | 476 | __b[__sample[__j].second] -= __n + 1; |
c2ba9709 | 477 | |
531898c3 | 478 | // Further refinement. |
1acba85b | 479 | while (__n > 0) |
15ac3c72 JS |
480 | { |
481 | __n /= 2; | |
482 | ||
8fc81078 | 483 | const _Tp* __lmax = 0; |
8b0c13a8 | 484 | for (_SeqNumber __i = 0; __i < __m; ++__i) |
15ac3c72 JS |
485 | { |
486 | if (__a[__i] > 0) | |
487 | { | |
488 | if (!__lmax) | |
489 | __lmax = &(__S(__i)[__a[__i] - 1]); | |
490 | else | |
491 | { | |
492 | if (__comp(*__lmax, __S(__i)[__a[__i] - 1])) //max | |
493 | __lmax = &(__S(__i)[__a[__i] - 1]); | |
494 | } | |
495 | } | |
496 | } | |
497 | ||
8b0c13a8 | 498 | _SeqNumber __i; |
15ac3c72 JS |
499 | for (__i = 0; __i < __m; __i++) |
500 | { | |
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]); | |
505 | else | |
506 | __b[__i] -= __n + 1; | |
507 | } | |
508 | ||
15e2a6c0 | 509 | _DifferenceType __leftsize = 0; |
8b0c13a8 | 510 | for (_SeqNumber __i = 0; __i < __m; ++__i) |
15ac3c72 | 511 | __leftsize += __a[__i] / (__n + 1); |
15ac3c72 | 512 | |
15e2a6c0 | 513 | _DifferenceType __skew = __rank / (__n + 1) - __leftsize; |
15ac3c72 JS |
514 | |
515 | if (__skew > 0) | |
516 | { | |
517 | // Move to the left, find smallest. | |
8b0c13a8 JS |
518 | std::priority_queue<std::pair<_Tp, _SeqNumber>, |
519 | std::vector<std::pair<_Tp, _SeqNumber> >, | |
520 | _LexicographicReverse<_Tp, _SeqNumber, _Compare> > | |
521 | __pq(__lrcomp); | |
15ac3c72 | 522 | |
8b0c13a8 | 523 | for (_SeqNumber __i = 0; __i < __m; ++__i) |
15ac3c72 JS |
524 | if (__b[__i] < __ns[__i]) |
525 | __pq.push(std::make_pair(__S(__i)[__b[__i]], __i)); | |
526 | ||
527 | for (; __skew != 0 && !__pq.empty(); --__skew) | |
528 | { | |
8b0c13a8 | 529 | _SeqNumber __source = __pq.top().second; |
15ac3c72 JS |
530 | __pq.pop(); |
531 | ||
4459d22e JS |
532 | __a[__source] |
533 | = std::min(__a[__source] + __n + 1, __ns[__source]); | |
534 | __b[__source] += __n + 1; | |
15ac3c72 | 535 | |
4459d22e | 536 | if (__b[__source] < __ns[__source]) |
15ac3c72 | 537 | __pq.push( |
4459d22e | 538 | std::make_pair(__S(__source)[__b[__source]], __source)); |
15ac3c72 JS |
539 | } |
540 | } | |
541 | else if (__skew < 0) | |
542 | { | |
543 | // Move to the right, find greatest. | |
8b0c13a8 JS |
544 | std::priority_queue<std::pair<_Tp, _SeqNumber>, |
545 | std::vector<std::pair<_Tp, _SeqNumber> >, | |
546 | _Lexicographic<_Tp, _SeqNumber, _Compare> > __pq(__lcomp); | |
15ac3c72 | 547 | |
8b0c13a8 | 548 | for (_SeqNumber __i = 0; __i < __m; ++__i) |
15ac3c72 JS |
549 | if (__a[__i] > 0) |
550 | __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i)); | |
551 | ||
552 | for (; __skew != 0; ++__skew) | |
553 | { | |
8b0c13a8 | 554 | _SeqNumber __source = __pq.top().second; |
15ac3c72 JS |
555 | __pq.pop(); |
556 | ||
4459d22e JS |
557 | __a[__source] -= __n + 1; |
558 | __b[__source] -= __n + 1; | |
15ac3c72 | 559 | |
4459d22e JS |
560 | if (__a[__source] > 0) |
561 | __pq.push(std::make_pair( | |
562 | __S(__source)[__a[__source] - 1], __source)); | |
15ac3c72 JS |
563 | } |
564 | } | |
565 | } | |
531898c3 PC |
566 | |
567 | // Postconditions: | |
15ac3c72 JS |
568 | // __a[__i] == __b[__i] in most cases, except when __a[__i] has been |
569 | // clamped because of having reached the boundary | |
531898c3 PC |
570 | |
571 | // Now return the result, calculate the offset. | |
572 | ||
573 | // Compare the keys on both edges of the border. | |
574 | ||
575 | // Maximum of left edge, minimum of right edge. | |
1acba85b | 576 | bool __maxleftset = false, __minrightset = false; |
531898c3 PC |
577 | |
578 | // Impossible to avoid the warning? | |
1acba85b | 579 | _Tp __maxleft, __minright; |
8b0c13a8 | 580 | for (_SeqNumber __i = 0; __i < __m; ++__i) |
15ac3c72 JS |
581 | { |
582 | if (__a[__i] > 0) | |
583 | { | |
584 | if (!__maxleftset) | |
585 | { | |
586 | __maxleft = __S(__i)[__a[__i] - 1]; | |
587 | __maxleftset = true; | |
588 | } | |
589 | else | |
590 | { | |
591 | // Max. | |
592 | if (__comp(__maxleft, __S(__i)[__a[__i] - 1])) | |
593 | __maxleft = __S(__i)[__a[__i] - 1]; | |
594 | } | |
595 | } | |
596 | if (__b[__i] < __ns[__i]) | |
597 | { | |
598 | if (!__minrightset) | |
599 | { | |
600 | __minright = __S(__i)[__b[__i]]; | |
601 | __minrightset = true; | |
602 | } | |
603 | else | |
604 | { | |
605 | // Min. | |
606 | if (__comp(__S(__i)[__b[__i]], __minright)) | |
607 | __minright = __S(__i)[__b[__i]]; | |
608 | } | |
609 | } | |
c2ba9709 JS |
610 | } |
611 | ||
4459d22e | 612 | // Minright is the __splitter, in any case. |
531898c3 | 613 | |
1acba85b | 614 | if (!__maxleftset || __comp(__minright, __maxleft)) |
15ac3c72 JS |
615 | { |
616 | // Good luck, everything is split unambiguously. | |
617 | __offset = 0; | |
618 | } | |
531898c3 | 619 | else |
15ac3c72 JS |
620 | { |
621 | // We have to calculate an offset. | |
622 | __offset = 0; | |
623 | ||
8b0c13a8 | 624 | for (_SeqNumber __i = 0; __i < __m; ++__i) |
15ac3c72 JS |
625 | { |
626 | _DifferenceType lb | |
627 | = std::lower_bound(__S(__i), __S(__i) + __ns[__i], | |
628 | __minright, | |
629 | __comp) - __S(__i); | |
630 | __offset += __a[__i] - lb; | |
631 | } | |
632 | } | |
531898c3 | 633 | |
1acba85b JS |
634 | delete[] __ns; |
635 | delete[] __a; | |
636 | delete[] __b; | |
531898c3 | 637 | |
1acba85b | 638 | return __minright; |
531898c3 | 639 | } |
c2ba9709 JS |
640 | } |
641 | ||
1acba85b | 642 | #undef __S |
c2ba9709 | 643 | |
cbcd1e45 | 644 | #endif /* _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H */ |