1 | // (C) Copyright Herve Bronnimann 2004. |
2 | // |
3 | // Distributed under the Boost Software License, Version 1.0. (See accompanying |
4 | // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
5 | |
6 | /* |
7 | Revision history: |
8 | 1 July 2004 |
9 | Split the code into two headers to lessen dependence on |
10 | Boost.tuple. (Herve) |
11 | 26 June 2004 |
12 | Added the code for the boost minmax library. (Herve) |
13 | */ |
14 | |
15 | #ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP |
16 | #define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP |
17 | |
18 | /* PROPOSED STANDARD EXTENSIONS: |
19 | * |
20 | * minmax_element(first, last) |
21 | * Effect: std::make_pair( std::min_element(first, last), |
22 | * std::max_element(first, last) ); |
23 | * |
24 | * minmax_element(first, last, comp) |
25 | * Effect: std::make_pair( std::min_element(first, last, comp), |
26 | * std::max_element(first, last, comp) ); |
27 | */ |
28 | |
29 | #include <utility> // for std::pair and std::make_pair |
30 | |
31 | namespace boost { |
32 | |
33 | namespace detail { // for obtaining a uniform version of minmax_element |
34 | // that compiles with VC++ 6.0 -- avoid the iterator_traits by |
35 | // having comparison object over iterator, not over dereferenced value |
36 | |
37 | template <typename Iterator> |
38 | struct less_over_iter { |
39 | bool operator()(Iterator const& it1, |
40 | Iterator const& it2) const { return *it1 < *it2; } |
41 | }; |
42 | |
43 | template <typename Iterator, class BinaryPredicate> |
44 | struct binary_pred_over_iter { |
45 | explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {} |
46 | bool operator()(Iterator const& it1, |
47 | Iterator const& it2) const { return m_p(*it1, *it2); } |
48 | private: |
49 | BinaryPredicate m_p; |
50 | }; |
51 | |
52 | // common base for the two minmax_element overloads |
53 | |
54 | template <typename ForwardIter, class Compare > |
55 | std::pair<ForwardIter,ForwardIter> |
56 | basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp) |
57 | { |
58 | if (first == last) |
59 | return std::make_pair(last,last); |
60 | |
61 | ForwardIter min_result = first; |
62 | ForwardIter max_result = first; |
63 | |
64 | // if only one element |
65 | ForwardIter second = first; ++second; |
66 | if (second == last) |
67 | return std::make_pair(min_result, max_result); |
68 | |
69 | // treat first pair separately (only one comparison for first two elements) |
70 | ForwardIter potential_min_result = last; |
71 | if (comp(first, second)) |
72 | max_result = second; |
73 | else { |
74 | min_result = second; |
75 | potential_min_result = first; |
76 | } |
77 | |
78 | // then each element by pairs, with at most 3 comparisons per pair |
79 | first = ++second; if (first != last) ++second; |
80 | while (second != last) { |
81 | if (comp(first, second)) { |
82 | if (comp(first, min_result)) { |
83 | min_result = first; |
84 | potential_min_result = last; |
85 | } |
86 | if (comp(max_result, second)) |
87 | max_result = second; |
88 | } else { |
89 | if (comp(second, min_result)) { |
90 | min_result = second; |
91 | potential_min_result = first; |
92 | } |
93 | if (comp(max_result, first)) |
94 | max_result = first; |
95 | } |
96 | first = ++second; |
97 | if (first != last) ++second; |
98 | } |
99 | |
100 | // if odd number of elements, treat last element |
101 | if (first != last) { // odd number of elements |
102 | if (comp(first, min_result)) { |
103 | min_result = first; |
104 | potential_min_result = last; |
105 | } |
106 | else if (comp(max_result, first)) |
107 | max_result = first; |
108 | } |
109 | |
110 | // resolve min_result being incorrect with one extra comparison |
111 | // (in which case potential_min_result is necessarily the correct result) |
112 | if (potential_min_result != last |
113 | && !comp(min_result, potential_min_result)) |
114 | min_result = potential_min_result; |
115 | |
116 | return std::make_pair(min_result,max_result); |
117 | } |
118 | |
119 | } // namespace detail |
120 | |
121 | template <typename ForwardIter> |
122 | std::pair<ForwardIter,ForwardIter> |
123 | minmax_element(ForwardIter first, ForwardIter last) |
124 | { |
125 | return detail::basic_minmax_element(first, last, |
126 | detail::less_over_iter<ForwardIter>() ); |
127 | } |
128 | |
129 | template <typename ForwardIter, class BinaryPredicate> |
130 | std::pair<ForwardIter,ForwardIter> |
131 | minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) |
132 | { |
133 | return detail::basic_minmax_element(first, last, |
134 | detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); |
135 | } |
136 | |
137 | } |
138 | |
139 | /* PROPOSED BOOST EXTENSIONS |
140 | * In the description below, [rfirst,rlast) denotes the reversed range |
141 | * of [first,last). Even though the iterator type of first and last may |
142 | * be only a Forward Iterator, it is possible to explain the semantics |
143 | * by assuming that it is a Bidirectional Iterator. In the sequel, |
144 | * reverse(ForwardIterator&) returns the reverse_iterator adaptor. |
145 | * This is not how the functions would be implemented! |
146 | * |
147 | * first_min_element(first, last) |
148 | * Effect: std::min_element(first, last); |
149 | * |
150 | * first_min_element(first, last, comp) |
151 | * Effect: std::min_element(first, last, comp); |
152 | * |
153 | * last_min_element(first, last) |
154 | * Effect: reverse( std::min_element(reverse(last), reverse(first)) ); |
155 | * |
156 | * last_min_element(first, last, comp) |
157 | * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) ); |
158 | * |
159 | * first_max_element(first, last) |
160 | * Effect: std::max_element(first, last); |
161 | * |
162 | * first_max_element(first, last, comp) |
163 | * Effect: max_element(first, last); |
164 | * |
165 | * last_max_element(first, last) |
166 | * Effect: reverse( std::max_element(reverse(last), reverse(first)) ); |
167 | * |
168 | * last_max_element(first, last, comp) |
169 | * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) ); |
170 | * |
171 | * first_min_first_max_element(first, last) |
172 | * Effect: std::make_pair( first_min_element(first, last), |
173 | * first_max_element(first, last) ); |
174 | * |
175 | * first_min_first_max_element(first, last, comp) |
176 | * Effect: std::make_pair( first_min_element(first, last, comp), |
177 | * first_max_element(first, last, comp) ); |
178 | * |
179 | * first_min_last_max_element(first, last) |
180 | * Effect: std::make_pair( first_min_element(first, last), |
181 | * last_max_element(first, last) ); |
182 | * |
183 | * first_min_last_max_element(first, last, comp) |
184 | * Effect: std::make_pair( first_min_element(first, last, comp), |
185 | * last_max_element(first, last, comp) ); |
186 | * |
187 | * last_min_first_max_element(first, last) |
188 | * Effect: std::make_pair( last_min_element(first, last), |
189 | * first_max_element(first, last) ); |
190 | * |
191 | * last_min_first_max_element(first, last, comp) |
192 | * Effect: std::make_pair( last_min_element(first, last, comp), |
193 | * first_max_element(first, last, comp) ); |
194 | * |
195 | * last_min_last_max_element(first, last) |
196 | * Effect: std::make_pair( last_min_element(first, last), |
197 | * last_max_element(first, last) ); |
198 | * |
199 | * last_min_last_max_element(first, last, comp) |
200 | * Effect: std::make_pair( last_min_element(first, last, comp), |
201 | * last_max_element(first, last, comp) ); |
202 | */ |
203 | |
204 | namespace boost { |
205 | |
206 | // Min_element and max_element variants |
207 | |
208 | namespace detail { // common base for the overloads |
209 | |
210 | template <typename ForwardIter, class BinaryPredicate> |
211 | ForwardIter |
212 | basic_first_min_element(ForwardIter first, ForwardIter last, |
213 | BinaryPredicate comp) |
214 | { |
215 | if (first == last) return last; |
216 | ForwardIter min_result = first; |
217 | while (++first != last) |
218 | if (comp(first, min_result)) |
219 | min_result = first; |
220 | return min_result; |
221 | } |
222 | |
223 | template <typename ForwardIter, class BinaryPredicate> |
224 | ForwardIter |
225 | basic_last_min_element(ForwardIter first, ForwardIter last, |
226 | BinaryPredicate comp) |
227 | { |
228 | if (first == last) return last; |
229 | ForwardIter min_result = first; |
230 | while (++first != last) |
231 | if (!comp(min_result, first)) |
232 | min_result = first; |
233 | return min_result; |
234 | } |
235 | |
236 | template <typename ForwardIter, class BinaryPredicate> |
237 | ForwardIter |
238 | basic_first_max_element(ForwardIter first, ForwardIter last, |
239 | BinaryPredicate comp) |
240 | { |
241 | if (first == last) return last; |
242 | ForwardIter max_result = first; |
243 | while (++first != last) |
244 | if (comp(max_result, first)) |
245 | max_result = first; |
246 | return max_result; |
247 | } |
248 | |
249 | template <typename ForwardIter, class BinaryPredicate> |
250 | ForwardIter |
251 | basic_last_max_element(ForwardIter first, ForwardIter last, |
252 | BinaryPredicate comp) |
253 | { |
254 | if (first == last) return last; |
255 | ForwardIter max_result = first; |
256 | while (++first != last) |
257 | if (!comp(first, max_result)) |
258 | max_result = first; |
259 | return max_result; |
260 | } |
261 | |
262 | } // namespace detail |
263 | |
264 | template <typename ForwardIter> |
265 | ForwardIter |
266 | first_min_element(ForwardIter first, ForwardIter last) |
267 | { |
268 | return detail::basic_first_min_element(first, last, |
269 | detail::less_over_iter<ForwardIter>() ); |
270 | } |
271 | |
272 | template <typename ForwardIter, class BinaryPredicate> |
273 | ForwardIter |
274 | first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) |
275 | { |
276 | return detail::basic_first_min_element(first, last, |
277 | detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); |
278 | } |
279 | |
280 | template <typename ForwardIter> |
281 | ForwardIter |
282 | last_min_element(ForwardIter first, ForwardIter last) |
283 | { |
284 | return detail::basic_last_min_element(first, last, |
285 | detail::less_over_iter<ForwardIter>() ); |
286 | } |
287 | |
288 | template <typename ForwardIter, class BinaryPredicate> |
289 | ForwardIter |
290 | last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) |
291 | { |
292 | return detail::basic_last_min_element(first, last, |
293 | detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); |
294 | } |
295 | |
296 | template <typename ForwardIter> |
297 | ForwardIter |
298 | first_max_element(ForwardIter first, ForwardIter last) |
299 | { |
300 | return detail::basic_first_max_element(first, last, |
301 | detail::less_over_iter<ForwardIter>() ); |
302 | } |
303 | |
304 | template <typename ForwardIter, class BinaryPredicate> |
305 | ForwardIter |
306 | first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) |
307 | { |
308 | return detail::basic_first_max_element(first, last, |
309 | detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); |
310 | } |
311 | |
312 | template <typename ForwardIter> |
313 | ForwardIter |
314 | last_max_element(ForwardIter first, ForwardIter last) |
315 | { |
316 | return detail::basic_last_max_element(first, last, |
317 | detail::less_over_iter<ForwardIter>() ); |
318 | } |
319 | |
320 | template <typename ForwardIter, class BinaryPredicate> |
321 | ForwardIter |
322 | last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) |
323 | { |
324 | return detail::basic_last_max_element(first, last, |
325 | detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); |
326 | } |
327 | |
328 | |
329 | // Minmax_element variants -- comments removed |
330 | |
331 | namespace detail { |
332 | |
333 | template <typename ForwardIter, class BinaryPredicate> |
334 | std::pair<ForwardIter,ForwardIter> |
335 | basic_first_min_last_max_element(ForwardIter first, ForwardIter last, |
336 | BinaryPredicate comp) |
337 | { |
338 | if (first == last) |
339 | return std::make_pair(last,last); |
340 | |
341 | ForwardIter min_result = first; |
342 | ForwardIter max_result = first; |
343 | |
344 | ForwardIter second = ++first; |
345 | if (second == last) |
346 | return std::make_pair(min_result, max_result); |
347 | |
348 | if (comp(second, min_result)) |
349 | min_result = second; |
350 | else |
351 | max_result = second; |
352 | |
353 | first = ++second; if (first != last) ++second; |
354 | while (second != last) { |
355 | if (!comp(second, first)) { |
356 | if (comp(first, min_result)) |
357 | min_result = first; |
358 | if (!comp(second, max_result)) |
359 | max_result = second; |
360 | } else { |
361 | if (comp(second, min_result)) |
362 | min_result = second; |
363 | if (!comp(first, max_result)) |
364 | max_result = first; |
365 | } |
366 | first = ++second; if (first != last) ++second; |
367 | } |
368 | |
369 | if (first != last) { |
370 | if (comp(first, min_result)) |
371 | min_result = first; |
372 | else if (!comp(first, max_result)) |
373 | max_result = first; |
374 | } |
375 | |
376 | return std::make_pair(min_result, max_result); |
377 | } |
378 | |
379 | template <typename ForwardIter, class BinaryPredicate> |
380 | std::pair<ForwardIter,ForwardIter> |
381 | basic_last_min_first_max_element(ForwardIter first, ForwardIter last, |
382 | BinaryPredicate comp) |
383 | { |
384 | if (first == last) return std::make_pair(last,last); |
385 | |
386 | ForwardIter min_result = first; |
387 | ForwardIter max_result = first; |
388 | |
389 | ForwardIter second = ++first; |
390 | if (second == last) |
391 | return std::make_pair(min_result, max_result); |
392 | |
393 | if (comp(max_result, second)) |
394 | max_result = second; |
395 | else |
396 | min_result = second; |
397 | |
398 | first = ++second; if (first != last) ++second; |
399 | while (second != last) { |
400 | if (comp(first, second)) { |
401 | if (!comp(min_result, first)) |
402 | min_result = first; |
403 | if (comp(max_result, second)) |
404 | max_result = second; |
405 | } else { |
406 | if (!comp(min_result, second)) |
407 | min_result = second; |
408 | if (comp(max_result, first)) |
409 | max_result = first; |
410 | } |
411 | first = ++second; if (first != last) ++second; |
412 | } |
413 | |
414 | if (first != last) { |
415 | if (!comp(min_result, first)) |
416 | min_result = first; |
417 | else if (comp(max_result, first)) |
418 | max_result = first; |
419 | } |
420 | |
421 | return std::make_pair(min_result, max_result); |
422 | } |
423 | |
424 | template <typename ForwardIter, class BinaryPredicate> |
425 | std::pair<ForwardIter,ForwardIter> |
426 | basic_last_min_last_max_element(ForwardIter first, ForwardIter last, |
427 | BinaryPredicate comp) |
428 | { |
429 | if (first == last) return std::make_pair(last,last); |
430 | |
431 | ForwardIter min_result = first; |
432 | ForwardIter max_result = first; |
433 | |
434 | ForwardIter second = first; ++second; |
435 | if (second == last) |
436 | return std::make_pair(min_result,max_result); |
437 | |
438 | ForwardIter potential_max_result = last; |
439 | if (comp(first, second)) |
440 | max_result = second; |
441 | else { |
442 | min_result = second; |
443 | potential_max_result = second; |
444 | } |
445 | |
446 | first = ++second; if (first != last) ++second; |
447 | while (second != last) { |
448 | if (comp(first, second)) { |
449 | if (!comp(min_result, first)) |
450 | min_result = first; |
451 | if (!comp(second, max_result)) { |
452 | max_result = second; |
453 | potential_max_result = last; |
454 | } |
455 | } else { |
456 | if (!comp(min_result, second)) |
457 | min_result = second; |
458 | if (!comp(first, max_result)) { |
459 | max_result = first; |
460 | potential_max_result = second; |
461 | } |
462 | } |
463 | first = ++second; |
464 | if (first != last) ++second; |
465 | } |
466 | |
467 | if (first != last) { |
468 | if (!comp(min_result, first)) |
469 | min_result = first; |
470 | if (!comp(first, max_result)) { |
471 | max_result = first; |
472 | potential_max_result = last; |
473 | } |
474 | } |
475 | |
476 | if (potential_max_result != last |
477 | && !comp(potential_max_result, max_result)) |
478 | max_result = potential_max_result; |
479 | |
480 | return std::make_pair(min_result,max_result); |
481 | } |
482 | |
483 | } // namespace detail |
484 | |
485 | template <typename ForwardIter> |
486 | inline std::pair<ForwardIter,ForwardIter> |
487 | first_min_first_max_element(ForwardIter first, ForwardIter last) |
488 | { |
489 | return minmax_element(first, last); |
490 | } |
491 | |
492 | template <typename ForwardIter, class BinaryPredicate> |
493 | inline std::pair<ForwardIter,ForwardIter> |
494 | first_min_first_max_element(ForwardIter first, ForwardIter last, |
495 | BinaryPredicate comp) |
496 | { |
497 | return minmax_element(first, last, comp); |
498 | } |
499 | |
500 | template <typename ForwardIter> |
501 | std::pair<ForwardIter,ForwardIter> |
502 | first_min_last_max_element(ForwardIter first, ForwardIter last) |
503 | { |
504 | return detail::basic_first_min_last_max_element(first, last, |
505 | detail::less_over_iter<ForwardIter>() ); |
506 | } |
507 | |
508 | template <typename ForwardIter, class BinaryPredicate> |
509 | inline std::pair<ForwardIter,ForwardIter> |
510 | first_min_last_max_element(ForwardIter first, ForwardIter last, |
511 | BinaryPredicate comp) |
512 | { |
513 | return detail::basic_first_min_last_max_element(first, last, |
514 | detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); |
515 | } |
516 | |
517 | template <typename ForwardIter> |
518 | std::pair<ForwardIter,ForwardIter> |
519 | last_min_first_max_element(ForwardIter first, ForwardIter last) |
520 | { |
521 | return detail::basic_last_min_first_max_element(first, last, |
522 | detail::less_over_iter<ForwardIter>() ); |
523 | } |
524 | |
525 | template <typename ForwardIter, class BinaryPredicate> |
526 | inline std::pair<ForwardIter,ForwardIter> |
527 | last_min_first_max_element(ForwardIter first, ForwardIter last, |
528 | BinaryPredicate comp) |
529 | { |
530 | return detail::basic_last_min_first_max_element(first, last, |
531 | detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); |
532 | } |
533 | |
534 | template <typename ForwardIter> |
535 | std::pair<ForwardIter,ForwardIter> |
536 | last_min_last_max_element(ForwardIter first, ForwardIter last) |
537 | { |
538 | return detail::basic_last_min_last_max_element(first, last, |
539 | detail::less_over_iter<ForwardIter>() ); |
540 | } |
541 | |
542 | template <typename ForwardIter, class BinaryPredicate> |
543 | inline std::pair<ForwardIter,ForwardIter> |
544 | last_min_last_max_element(ForwardIter first, ForwardIter last, |
545 | BinaryPredicate comp) |
546 | { |
547 | return detail::basic_last_min_last_max_element(first, last, |
548 | detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); |
549 | } |
550 | |
551 | } // namespace boost |
552 | |
553 | #endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP |
554 | |