source: NonGTP/Boost/boost/algorithm/minmax_element.hpp @ 857

Revision 857, 17.6 KB checked in by igarcia, 19 years ago (diff)
Line 
1//  (C) Copyright Herve Bronnimann 2004.
2//  Use, modification and distribution are subject to the
3//  Boost Software License, Version 1.0. (See accompanying file
4//  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, potential_min_result = last;
104        else if (comp(max_result, first))
105          max_result = first;
106      }
107
108      // resolve min_result being incorrect with one extra comparison
109      // (in which case potential_min_result is necessarily the correct result)
110      if (potential_min_result != last
111        && !comp(min_result, potential_min_result))
112        min_result = potential_min_result;
113
114      return std::make_pair(min_result,max_result);
115    }
116
117  } // namespace detail
118
119  template <typename ForwardIter>
120  std::pair<ForwardIter,ForwardIter>
121  minmax_element(ForwardIter first, ForwardIter last)
122  {
123    return detail::basic_minmax_element(first, last,
124             detail::less_over_iter<ForwardIter>() );
125  }
126
127  template <typename ForwardIter, class BinaryPredicate>
128  std::pair<ForwardIter,ForwardIter>
129  minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
130  {
131    return detail::basic_minmax_element(first, last,
132             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
133  }
134
135}
136
137/* PROPOSED BOOST EXTENSIONS
138 * In the description below, [rfirst,rlast) denotes the reversed range
139 * of [first,last). Even though the iterator type of first and last may
140 * be only a Forward Iterator, it is possible to explain the semantics
141 * by assuming that it is a Bidirectional Iterator. In the sequel,
142 * reverse(ForwardIterator&) returns the reverse_iterator adaptor.
143 * This is not how the functions would be implemented!
144 *
145 * first_min_element(first, last)
146 * Effect: std::min_element(first, last);
147 *
148 * first_min_element(first, last, comp)
149 * Effect: std::min_element(first, last, comp);
150 *
151 * last_min_element(first, last)
152 * Effect: reverse( std::min_element(reverse(last), reverse(first)) );
153 *
154 * last_min_element(first, last, comp)
155 * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) );
156 *
157 * first_max_element(first, last)
158 * Effect: std::max_element(first, last);
159 *
160 * first_max_element(first, last, comp)
161 * Effect: max_element(first, last);
162 *
163 * last_max_element(first, last)
164 * Effect: reverse( std::max_element(reverse(last), reverse(first)) );
165 *
166 * last_max_element(first, last, comp)
167 * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) );
168 *
169 * first_min_first_max_element(first, last)
170 * Effect: std::make_pair( first_min_element(first, last),
171 *                         first_max_element(first, last) );
172 *
173 * first_min_first_max_element(first, last, comp)
174 * Effect: std::make_pair( first_min_element(first, last, comp),
175 *                         first_max_element(first, last, comp) );
176 *
177 * first_min_last_max_element(first, last)
178 * Effect: std::make_pair( first_min_element(first, last),
179 *                         last_max_element(first, last) );
180 *
181 * first_min_last_max_element(first, last, comp)
182 * Effect: std::make_pair( first_min_element(first, last, comp),
183 *                         last_max_element(first, last, comp) );
184 *
185 * last_min_first_max_element(first, last)
186 * Effect: std::make_pair( last_min_element(first, last),
187 *                         first_max_element(first, last) );
188 *
189 * last_min_first_max_element(first, last, comp)
190 * Effect: std::make_pair( last_min_element(first, last, comp),
191 *                         first_max_element(first, last, comp) );
192 *
193 * last_min_last_max_element(first, last)
194 * Effect: std::make_pair( last_min_element(first, last),
195 *                         last_max_element(first, last) );
196 *
197 * last_min_last_max_element(first, last, comp)
198 * Effect: std::make_pair( last_min_element(first, last, comp),
199 *                         last_max_element(first, last, comp) );
200 */
201
202namespace boost {
203
204  // Min_element and max_element variants
205
206  namespace detail {  // common base for the overloads
207
208  template <typename ForwardIter, class BinaryPredicate>
209  ForwardIter
210  basic_first_min_element(ForwardIter first, ForwardIter last,
211                          BinaryPredicate comp)
212  {
213    if (first == last) return last;
214    ForwardIter min_result = first;
215    while (++first != last)
216      if (comp(first, min_result))
217        min_result = first;
218    return min_result;
219  }
220
221  template <typename ForwardIter, class BinaryPredicate>
222  ForwardIter
223  basic_last_min_element(ForwardIter first, ForwardIter last,
224                         BinaryPredicate comp)
225  {
226    if (first == last) return last;
227    ForwardIter min_result = first;
228    while (++first != last)
229      if (!comp(min_result, first))
230        min_result = first;
231    return min_result;
232  }
233
234  template <typename ForwardIter, class BinaryPredicate>
235  ForwardIter
236  basic_first_max_element(ForwardIter first, ForwardIter last,
237                          BinaryPredicate comp)
238  {
239    if (first == last) return last;
240    ForwardIter max_result = first;
241    while (++first != last)
242      if (comp(max_result, first))
243        max_result = first;
244    return max_result;
245  }
246
247  template <typename ForwardIter, class BinaryPredicate>
248  ForwardIter
249  basic_last_max_element(ForwardIter first, ForwardIter last,
250                         BinaryPredicate comp)
251  {
252    if (first == last) return last;
253    ForwardIter max_result = first;
254    while (++first != last)
255      if (!comp(first, max_result))
256        max_result = first;
257    return max_result;
258  }
259
260  } // namespace detail
261
262  template <typename ForwardIter>
263  ForwardIter
264  first_min_element(ForwardIter first, ForwardIter last)
265  {
266    return detail::basic_first_min_element(first, last,
267             detail::less_over_iter<ForwardIter>() );
268  }
269
270  template <typename ForwardIter, class BinaryPredicate>
271  ForwardIter
272  first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
273  {
274    return detail::basic_first_min_element(first, last,
275             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
276  }
277
278  template <typename ForwardIter>
279  ForwardIter
280  last_min_element(ForwardIter first, ForwardIter last)
281  {
282    return detail::basic_last_min_element(first, last,
283             detail::less_over_iter<ForwardIter>() );
284  }
285
286  template <typename ForwardIter, class BinaryPredicate>
287  ForwardIter
288  last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
289  {
290    return detail::basic_last_min_element(first, last,
291             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
292  }
293
294  template <typename ForwardIter>
295  ForwardIter
296  first_max_element(ForwardIter first, ForwardIter last)
297  {
298    return detail::basic_first_max_element(first, last,
299             detail::less_over_iter<ForwardIter>() );
300  }
301
302  template <typename ForwardIter, class BinaryPredicate>
303  ForwardIter
304  first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
305  {
306    return detail::basic_first_max_element(first, last,
307             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
308  }
309
310  template <typename ForwardIter>
311  ForwardIter
312  last_max_element(ForwardIter first, ForwardIter last)
313  {
314    return detail::basic_last_max_element(first, last,
315             detail::less_over_iter<ForwardIter>() );
316  }
317
318  template <typename ForwardIter, class BinaryPredicate>
319  ForwardIter
320  last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
321  {
322    return detail::basic_last_max_element(first, last,
323             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
324  }
325
326
327  // Minmax_element variants -- comments removed
328
329  namespace detail {
330
331  template <typename ForwardIter, class BinaryPredicate>
332  std::pair<ForwardIter,ForwardIter>
333  basic_first_min_last_max_element(ForwardIter first, ForwardIter last,
334                                   BinaryPredicate comp)
335  {
336    if (first == last)
337      return std::make_pair(last,last);
338
339    ForwardIter min_result = first;
340    ForwardIter max_result = first;
341
342    ForwardIter second = ++first;
343    if (second == last)
344      return std::make_pair(min_result, max_result);
345
346    if (comp(second, min_result))
347      min_result = second;
348    else
349      max_result = second;
350
351    first = ++second; if (first != last) ++second;
352    while (second != last) {
353      if (!comp(second, first)) {
354        if (comp(first, min_result))
355                 min_result = first;
356        if (!comp(second, max_result))
357          max_result = second;
358      } else {
359        if (comp(second, min_result))
360          min_result = second;
361        if (!comp(first, max_result))
362              max_result = first;
363      }
364      first = ++second; if (first != last) ++second;
365    }
366
367    if (first != last) {
368      if (comp(first, min_result))
369         min_result = first;
370      else if (!comp(first, max_result))
371               max_result = first;
372    }
373
374    return std::make_pair(min_result, max_result);
375  }
376
377  template <typename ForwardIter, class BinaryPredicate>
378  std::pair<ForwardIter,ForwardIter>
379  basic_last_min_first_max_element(ForwardIter first, ForwardIter last,
380                                   BinaryPredicate comp)
381  {
382    if (first == last) return std::make_pair(last,last);
383
384    ForwardIter min_result = first;
385    ForwardIter max_result = first;
386
387    ForwardIter second = ++first;
388    if (second == last)
389      return std::make_pair(min_result, max_result);
390
391    if (comp(max_result, second))
392      max_result = second;
393    else
394      min_result = second;
395
396    first = ++second; if (first != last) ++second;
397    while (second != last)  {
398      if (comp(first, second)) {
399        if (!comp(min_result, first))
400          min_result = first;
401        if (comp(max_result, second))
402          max_result = second;
403      } else {
404        if (!comp(min_result, second))
405          min_result = second;
406        if (comp(max_result, first))
407          max_result = first;
408      }
409      first = ++second; if (first != last) ++second;
410    }
411
412    if (first != last) {
413      if (!comp(min_result, first))
414        min_result = first;
415      else if (comp(max_result, first))
416        max_result = first;
417    }
418
419    return std::make_pair(min_result, max_result);
420  }
421
422  template <typename ForwardIter, class BinaryPredicate>
423  std::pair<ForwardIter,ForwardIter>
424  basic_last_min_last_max_element(ForwardIter first, ForwardIter last,
425                                  BinaryPredicate comp)
426  {
427    if (first == last) return std::make_pair(last,last);
428
429    ForwardIter min_result = first;
430    ForwardIter max_result = first;
431
432    ForwardIter second = first; ++second;
433    if (second == last)
434      return std::make_pair(min_result,max_result);
435
436    ForwardIter potential_max_result = last;
437    if (comp(first, second))
438      max_result = second;
439    else {
440      min_result = second;
441      potential_max_result = second;
442    }
443
444    first = ++second; if (first != last) ++second;
445    while (second != last) {
446      if (comp(first, second)) {
447        if (!comp(min_result, first))
448          min_result = first;
449        if (!comp(second, max_result)) {
450          max_result = second;
451          potential_max_result = last;
452        }
453      } else {
454        if (!comp(min_result, second))
455          min_result = second;
456        if (!comp(first, max_result)) {
457          max_result = first;
458          potential_max_result = second;
459        }
460      }
461      first = ++second;
462      if (first != last) ++second;
463    }
464
465    if (first != last) {
466      if (!comp(min_result, first))
467        min_result = first;
468      if (!comp(first, max_result)) {
469        max_result = first;
470               potential_max_result = last;
471      }
472    }
473
474    if (potential_max_result != last
475        && !comp(potential_max_result, max_result))
476      max_result = potential_max_result;
477
478    return std::make_pair(min_result,max_result);
479  }
480
481  } // namespace detail
482
483  template <typename ForwardIter>
484  inline std::pair<ForwardIter,ForwardIter>
485  first_min_first_max_element(ForwardIter first, ForwardIter last)
486  {
487    return minmax_element(first, last);
488  }
489
490  template <typename ForwardIter, class BinaryPredicate>
491  inline std::pair<ForwardIter,ForwardIter>
492  first_min_first_max_element(ForwardIter first, ForwardIter last,
493                              BinaryPredicate comp)
494  {
495    return minmax_element(first, last, comp);
496  }
497
498  template <typename ForwardIter>
499  std::pair<ForwardIter,ForwardIter>
500  first_min_last_max_element(ForwardIter first, ForwardIter last)
501  {
502    return detail::basic_first_min_last_max_element(first, last,
503             detail::less_over_iter<ForwardIter>() );
504  }
505
506  template <typename ForwardIter, class BinaryPredicate>
507  inline std::pair<ForwardIter,ForwardIter>
508  first_min_last_max_element(ForwardIter first, ForwardIter last,
509                              BinaryPredicate comp)
510  {
511    return detail::basic_first_min_last_max_element(first, last,
512             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
513  }
514
515  template <typename ForwardIter>
516  std::pair<ForwardIter,ForwardIter>
517  last_min_first_max_element(ForwardIter first, ForwardIter last)
518  {
519    return detail::basic_last_min_first_max_element(first, last,
520             detail::less_over_iter<ForwardIter>() );
521  }
522
523  template <typename ForwardIter, class BinaryPredicate>
524  inline std::pair<ForwardIter,ForwardIter>
525  last_min_first_max_element(ForwardIter first, ForwardIter last,
526                              BinaryPredicate comp)
527  {
528    return detail::basic_last_min_first_max_element(first, last,
529             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
530  }
531
532  template <typename ForwardIter>
533  std::pair<ForwardIter,ForwardIter>
534  last_min_last_max_element(ForwardIter first, ForwardIter last)
535  {
536    return detail::basic_last_min_last_max_element(first, last,
537             detail::less_over_iter<ForwardIter>() );
538  }
539
540  template <typename ForwardIter, class BinaryPredicate>
541  inline std::pair<ForwardIter,ForwardIter>
542  last_min_last_max_element(ForwardIter first, ForwardIter last,
543                              BinaryPredicate comp)
544  {
545    return detail::basic_last_min_last_max_element(first, last,
546             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
547  }
548
549} // namespace boost
550
551#endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
Note: See TracBrowser for help on using the repository browser.