]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
531898c3 | 3 | // Copyright (C) 2007, 2008 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 | |
8 | // Foundation; either version 2, or (at your option) any later | |
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 | ||
16 | // You should have received a copy of the GNU General Public License | |
17 | // along with this library; see the file COPYING. If not, write to | |
18 | // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, | |
19 | // MA 02111-1307, USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free | |
22 | // software library without restriction. Specifically, if other files | |
23 | // instantiate templates or use macros or inline functions from this | |
24 | // file, or you compile this file and link it with other files to | |
25 | // produce an executable, this file does not by itself cause the | |
26 | // resulting executable to be covered by the GNU General Public | |
27 | // License. This exception does not however invalidate any other | |
28 | // reasons why the executable file might be covered by the GNU General | |
29 | // Public License. | |
30 | ||
31 | /** @file parallel/multiseq_selection.h | |
32 | * @brief Functions to find elements of a certain global rank in | |
33 | * multiple sorted sequences. Also serves for splitting such | |
34 | * sequence sets. | |
1904bef1 JS |
35 | * |
36 | * The algorithm description can be found in | |
37 | * | |
38 | * P. J. Varman, S. D. Scheufler, B. R. Iyer, and G. R. Ricard. | |
39 | * Merging Multiple Lists on Hierarchical-Memory Multiprocessors. | |
40 | * Journal of Parallel and Distributed Computing, 12(2):171–177, 1991. | |
41 | * | |
c2ba9709 JS |
42 | * This file is a GNU parallel extension to the Standard C++ Library. |
43 | */ | |
44 | ||
45 | // Written by Johannes Singler. | |
46 | ||
47 | #ifndef _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H | |
48 | #define _GLIBCXX_PARALLEL_MULTISEQ_SELECTION_H 1 | |
49 | ||
50 | #include <vector> | |
51 | #include <queue> | |
52 | ||
53 | #include <bits/stl_algo.h> | |
54 | ||
55 | #include <parallel/sort.h> | |
56 | ||
57 | namespace __gnu_parallel | |
58 | { | |
59 | /** @brief Compare a pair of types lexicographically, ascending. */ | |
60 | template<typename T1, typename T2, typename Comparator> | |
531898c3 PC |
61 | class lexicographic |
62 | : public std::binary_function<std::pair<T1, T2>, std::pair<T1, T2>, bool> | |
63 | { | |
64 | private: | |
65 | Comparator& comp; | |
c2ba9709 | 66 | |
531898c3 PC |
67 | public: |
68 | lexicographic(Comparator& _comp) : comp(_comp) { } | |
c2ba9709 | 69 | |
531898c3 PC |
70 | // XXX const |
71 | bool | |
72 | operator()(const std::pair<T1, T2>& p1, | |
73 | const std::pair<T1, T2>& p2) const | |
74 | { | |
75 | if (comp(p1.first, p2.first)) | |
76 | return true; | |
c2ba9709 | 77 | |
531898c3 PC |
78 | if (comp(p2.first, p1.first)) |
79 | return false; | |
c2ba9709 | 80 | |
531898c3 PC |
81 | // Firsts are equal. |
82 | return p1.second < p2.second; | |
83 | } | |
84 | }; | |
c2ba9709 JS |
85 | |
86 | /** @brief Compare a pair of types lexicographically, descending. */ | |
87 | template<typename T1, typename T2, typename Comparator> | |
531898c3 PC |
88 | class lexicographic_reverse : public std::binary_function<T1, T2, bool> |
89 | { | |
90 | private: | |
91 | Comparator& comp; | |
c2ba9709 | 92 | |
531898c3 PC |
93 | public: |
94 | lexicographic_reverse(Comparator& _comp) : comp(_comp) { } | |
c2ba9709 | 95 | |
531898c3 PC |
96 | bool |
97 | operator()(const std::pair<T1, T2>& p1, | |
98 | const std::pair<T1, T2>& p2) const | |
99 | { | |
100 | if (comp(p2.first, p1.first)) | |
101 | return true; | |
c2ba9709 | 102 | |
531898c3 PC |
103 | if (comp(p1.first, p2.first)) |
104 | return false; | |
c2ba9709 | 105 | |
531898c3 PC |
106 | // Firsts are equal. |
107 | return p2.second < p1.second; | |
108 | } | |
109 | }; | |
c2ba9709 JS |
110 | |
111 | /** | |
112 | * @brief Splits several sorted sequences at a certain global rank, | |
113 | * resulting in a splitting point for each sequence. | |
114 | * The sequences are passed via a sequence of random-access | |
115 | * iterator pairs, none of the sequences may be empty. If there | |
116 | * are several equal elements across the split, the ones on the | |
117 | * left side will be chosen from sequences with smaller number. | |
118 | * @param begin_seqs Begin of the sequence of iterator pairs. | |
119 | * @param end_seqs End of the sequence of iterator pairs. | |
120 | * @param rank The global rank to partition at. | |
121 | * @param begin_offsets A random-access sequence begin where the | |
122 | * result will be stored in. Each element of the sequence is an | |
123 | * iterator that points to the first element on the greater part of | |
124 | * the respective sequence. | |
125 | * @param comp The ordering functor, defaults to std::less<T>. | |
126 | */ | |
531898c3 PC |
127 | template<typename RanSeqs, typename RankType, typename RankIterator, |
128 | typename Comparator> | |
129 | void | |
130 | multiseq_partition(RanSeqs begin_seqs, RanSeqs end_seqs, | |
131 | RankType rank, | |
132 | RankIterator begin_offsets, | |
133 | Comparator comp = std::less< | |
134 | typename std::iterator_traits<typename | |
135 | std::iterator_traits<RanSeqs>::value_type:: | |
136 | first_type>::value_type>()) // std::less<T> | |
137 | { | |
138 | _GLIBCXX_CALL(end_seqs - begin_seqs) | |
139 | ||
140 | typedef typename std::iterator_traits<RanSeqs>::value_type::first_type | |
141 | It; | |
142 | typedef typename std::iterator_traits<It>::difference_type | |
143 | difference_type; | |
144 | typedef typename std::iterator_traits<It>::value_type value_type; | |
145 | ||
146 | lexicographic<value_type, int, Comparator> lcomp(comp); | |
147 | lexicographic_reverse<value_type, int, Comparator> lrcomp(comp); | |
148 | ||
149 | // Number of sequences, number of elements in total (possibly | |
150 | // including padding). | |
151 | difference_type m = std::distance(begin_seqs, end_seqs), N = 0, | |
152 | nmax, n, r; | |
153 | ||
154 | for (int i = 0; i < m; i++) | |
155 | N += std::distance(begin_seqs[i].first, begin_seqs[i].second); | |
156 | ||
157 | if (rank == N) | |
158 | { | |
159 | for (int i = 0; i < m; i++) | |
160 | begin_offsets[i] = begin_seqs[i].second; // Very end. | |
161 | // Return m - 1; | |
162 | } | |
163 | ||
164 | _GLIBCXX_PARALLEL_ASSERT(m != 0 && N != 0 && rank >= 0 && rank < N); | |
165 | ||
166 | difference_type* ns = new difference_type[m]; | |
167 | difference_type* a = new difference_type[m]; | |
168 | difference_type* b = new difference_type[m]; | |
169 | difference_type l; | |
170 | ||
171 | ns[0] = std::distance(begin_seqs[0].first, begin_seqs[0].second); | |
172 | nmax = ns[0]; | |
173 | for (int i = 0; i < m; i++) | |
174 | { | |
175 | ns[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second); | |
176 | nmax = std::max(nmax, ns[i]); | |
177 | } | |
178 | ||
179 | r = log2(nmax) + 1; | |
180 | ||
181 | // Pad all lists to this length, at least as long as any ns[i], | |
182 | // equality iff nmax = 2^k - 1. | |
183 | l = (1ULL << r) - 1; | |
184 | ||
185 | // From now on, including padding. | |
186 | N = l * m; | |
187 | ||
188 | for (int i = 0; i < m; i++) | |
189 | { | |
190 | a[i] = 0; | |
191 | b[i] = l; | |
192 | } | |
193 | n = l / 2; | |
194 | ||
195 | // Invariants: | |
196 | // 0 <= a[i] <= ns[i], 0 <= b[i] <= l | |
c2ba9709 JS |
197 | |
198 | #define S(i) (begin_seqs[i].first) | |
199 | ||
531898c3 PC |
200 | // Initial partition. |
201 | std::vector<std::pair<value_type, int> > sample; | |
202 | ||
203 | for (int i = 0; i < m; i++) | |
204 | if (n < ns[i]) //sequence long enough | |
205 | sample.push_back(std::make_pair(S(i)[n], i)); | |
206 | __gnu_sequential::sort(sample.begin(), sample.end(), lcomp); | |
207 | ||
208 | for (int i = 0; i < m; i++) //conceptual infinity | |
209 | if (n >= ns[i]) //sequence too short, conceptual infinity | |
210 | sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i)); | |
211 | ||
212 | difference_type localrank = rank * m / N ; | |
213 | ||
214 | int j; | |
5817ff8e | 215 | for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); ++j) |
531898c3 PC |
216 | a[sample[j].second] += n + 1; |
217 | for (; j < m; j++) | |
218 | b[sample[j].second] -= n + 1; | |
219 | ||
220 | // Further refinement. | |
221 | while (n > 0) | |
222 | { | |
223 | n /= 2; | |
224 | ||
225 | int lmax_seq = -1; // to avoid warning | |
226 | const value_type* lmax = NULL; // impossible to avoid the warning? | |
227 | for (int i = 0; i < m; i++) | |
228 | { | |
c2ba9709 | 229 | if (a[i] > 0) |
531898c3 PC |
230 | { |
231 | if (!lmax) | |
232 | { | |
233 | lmax = &(S(i)[a[i] - 1]); | |
234 | lmax_seq = i; | |
235 | } | |
236 | else | |
237 | { | |
238 | // Max, favor rear sequences. | |
239 | if (!comp(S(i)[a[i] - 1], *lmax)) | |
240 | { | |
241 | lmax = &(S(i)[a[i] - 1]); | |
242 | lmax_seq = i; | |
243 | } | |
244 | } | |
245 | } | |
246 | } | |
247 | ||
248 | int i; | |
249 | for (i = 0; i < m; i++) | |
250 | { | |
251 | difference_type middle = (b[i] + a[i]) / 2; | |
252 | if (lmax && middle < ns[i] && | |
253 | lcomp(std::make_pair(S(i)[middle], i), | |
254 | std::make_pair(*lmax, lmax_seq))) | |
255 | a[i] = std::min(a[i] + n + 1, ns[i]); | |
256 | else | |
257 | b[i] -= n + 1; | |
258 | } | |
259 | ||
260 | difference_type leftsize = 0, total = 0; | |
261 | for (int i = 0; i < m; i++) | |
262 | { | |
263 | leftsize += a[i] / (n + 1); | |
264 | total += l / (n + 1); | |
265 | } | |
266 | ||
267 | difference_type skew = static_cast<difference_type> | |
268 | (static_cast<uint64>(total) * rank / N - leftsize); | |
269 | ||
270 | if (skew > 0) | |
271 | { | |
272 | // Move to the left, find smallest. | |
273 | std::priority_queue<std::pair<value_type, int>, | |
274 | std::vector<std::pair<value_type, int> >, | |
275 | lexicographic_reverse<value_type, int, Comparator> > | |
276 | pq(lrcomp); | |
277 | ||
278 | for (int i = 0; i < m; i++) | |
279 | if (b[i] < ns[i]) | |
280 | pq.push(std::make_pair(S(i)[b[i]], i)); | |
281 | ||
5817ff8e | 282 | for (; skew != 0 && !pq.empty(); --skew) |
531898c3 PC |
283 | { |
284 | int source = pq.top().second; | |
285 | pq.pop(); | |
286 | ||
287 | a[source] = std::min(a[source] + n + 1, ns[source]); | |
288 | b[source] += n + 1; | |
289 | ||
290 | if (b[source] < ns[source]) | |
291 | pq.push(std::make_pair(S(source)[b[source]], source)); | |
292 | } | |
293 | } | |
294 | else if (skew < 0) | |
295 | { | |
296 | // Move to the right, find greatest. | |
297 | std::priority_queue<std::pair<value_type, int>, | |
298 | std::vector<std::pair<value_type, int> >, | |
299 | lexicographic<value_type, int, Comparator> > pq(lcomp); | |
300 | ||
301 | for (int i = 0; i < m; i++) | |
302 | if (a[i] > 0) | |
303 | pq.push(std::make_pair(S(i)[a[i] - 1], i)); | |
304 | ||
5817ff8e | 305 | for (; skew != 0; ++skew) |
531898c3 PC |
306 | { |
307 | int source = pq.top().second; | |
308 | pq.pop(); | |
309 | ||
310 | a[source] -= n + 1; | |
311 | b[source] -= n + 1; | |
312 | ||
313 | if (a[source] > 0) | |
314 | pq.push(std::make_pair(S(source)[a[source] - 1], source)); | |
315 | } | |
316 | } | |
317 | } | |
318 | ||
319 | // Postconditions: | |
320 | // a[i] == b[i] in most cases, except when a[i] has been clamped | |
321 | // because of having reached the boundary | |
322 | ||
323 | // Now return the result, calculate the offset. | |
324 | ||
325 | // Compare the keys on both edges of the border. | |
326 | ||
327 | // Maximum of left edge, minimum of right edge. | |
328 | value_type* maxleft = NULL; | |
329 | value_type* minright = NULL; | |
330 | for (int i = 0; i < m; i++) | |
331 | { | |
332 | if (a[i] > 0) | |
333 | { | |
334 | if (!maxleft) | |
335 | maxleft = &(S(i)[a[i] - 1]); | |
336 | else | |
337 | { | |
338 | // Max, favor rear sequences. | |
339 | if (!comp(S(i)[a[i] - 1], *maxleft)) | |
340 | maxleft = &(S(i)[a[i] - 1]); | |
341 | } | |
342 | } | |
343 | if (b[i] < ns[i]) | |
344 | { | |
345 | if (!minright) | |
346 | minright = &(S(i)[b[i]]); | |
347 | else | |
348 | { | |
349 | // Min, favor fore sequences. | |
350 | if (comp(S(i)[b[i]], *minright)) | |
351 | minright = &(S(i)[b[i]]); | |
352 | } | |
353 | } | |
354 | } | |
355 | ||
356 | int seq = 0; | |
357 | for (int i = 0; i < m; i++) | |
358 | begin_offsets[i] = S(i) + a[i]; | |
359 | ||
360 | delete[] ns; | |
361 | delete[] a; | |
362 | delete[] b; | |
363 | } | |
c2ba9709 JS |
364 | |
365 | ||
c2ba9709 JS |
366 | /** |
367 | * @brief Selects the element at a certain global rank from several | |
368 | * sorted sequences. | |
369 | * | |
370 | * The sequences are passed via a sequence of random-access | |
371 | * iterator pairs, none of the sequences may be empty. | |
372 | * @param begin_seqs Begin of the sequence of iterator pairs. | |
373 | * @param end_seqs End of the sequence of iterator pairs. | |
374 | * @param rank The global rank to partition at. | |
375 | * @param offset The rank of the selected element in the global | |
376 | * subsequence of elements equal to the selected element. If the | |
377 | * selected element is unique, this number is 0. | |
378 | * @param comp The ordering functor, defaults to std::less. | |
379 | */ | |
531898c3 PC |
380 | template<typename T, typename RanSeqs, typename RankType, |
381 | typename Comparator> | |
382 | T | |
383 | multiseq_selection(RanSeqs begin_seqs, RanSeqs end_seqs, RankType rank, | |
384 | RankType& offset, Comparator comp = std::less<T>()) | |
385 | { | |
386 | _GLIBCXX_CALL(end_seqs - begin_seqs) | |
c2ba9709 | 387 | |
531898c3 PC |
388 | typedef typename std::iterator_traits<RanSeqs>::value_type::first_type |
389 | It; | |
390 | typedef typename std::iterator_traits<It>::difference_type | |
391 | difference_type; | |
c2ba9709 | 392 | |
531898c3 PC |
393 | lexicographic<T, int, Comparator> lcomp(comp); |
394 | lexicographic_reverse<T, int, Comparator> lrcomp(comp); | |
c2ba9709 | 395 | |
531898c3 PC |
396 | // Number of sequences, number of elements in total (possibly |
397 | // including padding). | |
398 | difference_type m = std::distance(begin_seqs, end_seqs); | |
399 | difference_type N = 0; | |
400 | difference_type nmax, n, r; | |
c2ba9709 | 401 | |
531898c3 PC |
402 | for (int i = 0; i < m; i++) |
403 | N += std::distance(begin_seqs[i].first, begin_seqs[i].second); | |
c2ba9709 | 404 | |
531898c3 PC |
405 | if (m == 0 || N == 0 || rank < 0 || rank >= N) |
406 | { | |
407 | // Result undefined when there is no data or rank is outside bounds. | |
408 | throw std::exception(); | |
409 | } | |
c2ba9709 JS |
410 | |
411 | ||
531898c3 PC |
412 | difference_type* ns = new difference_type[m]; |
413 | difference_type* a = new difference_type[m]; | |
414 | difference_type* b = new difference_type[m]; | |
415 | difference_type l; | |
c2ba9709 | 416 | |
531898c3 PC |
417 | ns[0] = std::distance(begin_seqs[0].first, begin_seqs[0].second); |
418 | nmax = ns[0]; | |
5817ff8e | 419 | for (int i = 0; i < m; ++i) |
531898c3 PC |
420 | { |
421 | ns[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second); | |
422 | nmax = std::max(nmax, ns[i]); | |
423 | } | |
c2ba9709 | 424 | |
531898c3 | 425 | r = log2(nmax) + 1; |
c2ba9709 | 426 | |
531898c3 PC |
427 | // Pad all lists to this length, at least as long as any ns[i], |
428 | // equality iff nmax = 2^k - 1 | |
429 | l = pow2(r) - 1; | |
c2ba9709 | 430 | |
531898c3 PC |
431 | // From now on, including padding. |
432 | N = l * m; | |
c2ba9709 | 433 | |
5817ff8e | 434 | for (int i = 0; i < m; ++i) |
531898c3 PC |
435 | { |
436 | a[i] = 0; | |
437 | b[i] = l; | |
438 | } | |
439 | n = l / 2; | |
c2ba9709 | 440 | |
531898c3 PC |
441 | // Invariants: |
442 | // 0 <= a[i] <= ns[i], 0 <= b[i] <= l | |
c2ba9709 JS |
443 | |
444 | #define S(i) (begin_seqs[i].first) | |
445 | ||
531898c3 PC |
446 | // Initial partition. |
447 | std::vector<std::pair<T, int> > sample; | |
c2ba9709 | 448 | |
531898c3 PC |
449 | for (int i = 0; i < m; i++) |
450 | if (n < ns[i]) | |
451 | sample.push_back(std::make_pair(S(i)[n], i)); | |
452 | __gnu_sequential::sort(sample.begin(), sample.end(), | |
453 | lcomp, sequential_tag()); | |
c2ba9709 | 454 | |
531898c3 PC |
455 | // Conceptual infinity. |
456 | for (int i = 0; i < m; i++) | |
457 | if (n >= ns[i]) | |
458 | sample.push_back(std::make_pair(S(i)[0] /*dummy element*/, i)); | |
c2ba9709 | 459 | |
531898c3 | 460 | difference_type localrank = rank * m / N ; |
c2ba9709 | 461 | |
531898c3 | 462 | int j; |
5817ff8e | 463 | for (j = 0; j < localrank && ((n + 1) <= ns[sample[j].second]); ++j) |
531898c3 | 464 | a[sample[j].second] += n + 1; |
5817ff8e | 465 | for (; j < m; ++j) |
531898c3 | 466 | b[sample[j].second] -= n + 1; |
c2ba9709 | 467 | |
531898c3 PC |
468 | // Further refinement. |
469 | while (n > 0) | |
470 | { | |
471 | n /= 2; | |
c2ba9709 | 472 | |
531898c3 | 473 | const T* lmax = NULL; |
5817ff8e | 474 | for (int i = 0; i < m; ++i) |
531898c3 PC |
475 | { |
476 | if (a[i] > 0) | |
477 | { | |
478 | if (!lmax) | |
479 | lmax = &(S(i)[a[i] - 1]); | |
480 | else | |
481 | { | |
482 | if (comp(*lmax, S(i)[a[i] - 1])) //max | |
483 | lmax = &(S(i)[a[i] - 1]); | |
484 | } | |
485 | } | |
486 | } | |
487 | ||
488 | int i; | |
489 | for (i = 0; i < m; i++) | |
490 | { | |
491 | difference_type middle = (b[i] + a[i]) / 2; | |
492 | if (lmax && middle < ns[i] && comp(S(i)[middle], *lmax)) | |
493 | a[i] = std::min(a[i] + n + 1, ns[i]); | |
494 | else | |
495 | b[i] -= n + 1; | |
496 | } | |
497 | ||
498 | difference_type leftsize = 0, total = 0; | |
5817ff8e | 499 | for (int i = 0; i < m; ++i) |
531898c3 PC |
500 | { |
501 | leftsize += a[i] / (n + 1); | |
502 | total += l / (n + 1); | |
503 | } | |
504 | ||
505 | difference_type skew = ((unsigned long long)total * rank / N | |
506 | - leftsize); | |
507 | ||
508 | if (skew > 0) | |
509 | { | |
510 | // Move to the left, find smallest. | |
511 | std::priority_queue<std::pair<T, int>, | |
512 | std::vector<std::pair<T, int> >, | |
513 | lexicographic_reverse<T, int, Comparator> > pq(lrcomp); | |
514 | ||
5817ff8e | 515 | for (int i = 0; i < m; ++i) |
531898c3 PC |
516 | if (b[i] < ns[i]) |
517 | pq.push(std::make_pair(S(i)[b[i]], i)); | |
518 | ||
519 | for (; skew != 0 && !pq.empty(); --skew) | |
520 | { | |
521 | int source = pq.top().second; | |
522 | pq.pop(); | |
523 | ||
524 | a[source] = std::min(a[source] + n + 1, ns[source]); | |
525 | b[source] += n + 1; | |
526 | ||
527 | if (b[source] < ns[source]) | |
528 | pq.push(std::make_pair(S(source)[b[source]], source)); | |
529 | } | |
530 | } | |
531 | else if (skew < 0) | |
532 | { | |
533 | // Move to the right, find greatest. | |
534 | std::priority_queue<std::pair<T, int>, | |
535 | std::vector<std::pair<T, int> >, | |
536 | lexicographic<T, int, Comparator> > pq(lcomp); | |
537 | ||
5817ff8e | 538 | for (int i = 0; i < m; ++i) |
531898c3 PC |
539 | if (a[i] > 0) |
540 | pq.push(std::make_pair(S(i)[a[i] - 1], i)); | |
541 | ||
542 | for (; skew != 0; ++skew) | |
543 | { | |
544 | int source = pq.top().second; | |
545 | pq.pop(); | |
546 | ||
547 | a[source] -= n + 1; | |
548 | b[source] -= n + 1; | |
549 | ||
550 | if (a[source] > 0) | |
551 | pq.push(std::make_pair(S(source)[a[source] - 1], source)); | |
552 | } | |
553 | } | |
554 | } | |
555 | ||
556 | // Postconditions: | |
557 | // a[i] == b[i] in most cases, except when a[i] has been clamped | |
558 | // because of having reached the boundary | |
559 | ||
560 | // Now return the result, calculate the offset. | |
561 | ||
562 | // Compare the keys on both edges of the border. | |
563 | ||
564 | // Maximum of left edge, minimum of right edge. | |
565 | bool maxleftset = false, minrightset = false; | |
566 | ||
567 | // Impossible to avoid the warning? | |
568 | T maxleft, minright; | |
5817ff8e | 569 | for (int i = 0; i < m; ++i) |
531898c3 PC |
570 | { |
571 | if (a[i] > 0) | |
572 | { | |
573 | if (!maxleftset) | |
574 | { | |
c2ba9709 | 575 | maxleft = S(i)[a[i] - 1]; |
531898c3 PC |
576 | maxleftset = true; |
577 | } | |
578 | else | |
579 | { | |
580 | // Max. | |
581 | if (comp(maxleft, S(i)[a[i] - 1])) | |
582 | maxleft = S(i)[a[i] - 1]; | |
583 | } | |
584 | } | |
585 | if (b[i] < ns[i]) | |
586 | { | |
587 | if (!minrightset) | |
588 | { | |
c2ba9709 | 589 | minright = S(i)[b[i]]; |
531898c3 PC |
590 | minrightset = true; |
591 | } | |
592 | else | |
593 | { | |
594 | // Min. | |
595 | if (comp(S(i)[b[i]], minright)) | |
596 | minright = S(i)[b[i]]; | |
597 | } | |
598 | } | |
c2ba9709 JS |
599 | } |
600 | ||
531898c3 PC |
601 | // Minright is the splitter, in any case. |
602 | ||
603 | if (!maxleftset || comp(minright, maxleft)) | |
604 | { | |
28dac70a | 605 | // Good luck, everything is split unambiguously. |
531898c3 PC |
606 | offset = 0; |
607 | } | |
608 | else | |
609 | { | |
610 | // We have to calculate an offset. | |
611 | offset = 0; | |
612 | ||
5817ff8e | 613 | for (int i = 0; i < m; ++i) |
531898c3 PC |
614 | { |
615 | difference_type lb = std::lower_bound(S(i), S(i) + ns[i], | |
616 | minright, | |
617 | comp) - S(i); | |
618 | offset += a[i] - lb; | |
619 | } | |
620 | } | |
621 | ||
622 | delete[] ns; | |
623 | delete[] a; | |
624 | delete[] b; | |
625 | ||
626 | return minright; | |
627 | } | |
c2ba9709 JS |
628 | } |
629 | ||
630 | #undef S | |
631 | ||
632 | #endif | |
633 |