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

source code of boost/libs/algorithm/include/boost/algorithm/minmax_element.hpp