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
31namespace 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
204namespace 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