Chris@16: //  (C) Copyright Herve Bronnimann 2004.
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See accompanying
Chris@16: // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: /*
Chris@16:  Revision history:
Chris@16:    1 July 2004
Chris@16:       Split the code into two headers to lessen dependence on
Chris@16:       Boost.tuple. (Herve)
Chris@16:    26 June 2004
Chris@16:       Added the code for the boost minmax library. (Herve)
Chris@16: */
Chris@16: 
Chris@16: #ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
Chris@16: #define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
Chris@16: 
Chris@16: /* PROPOSED STANDARD EXTENSIONS:
Chris@16:  *
Chris@16:  * minmax_element(first, last)
Chris@16:  * Effect: std::make_pair( std::min_element(first, last),
Chris@16:  *                         std::max_element(first, last) );
Chris@16:  *
Chris@16:  * minmax_element(first, last, comp)
Chris@16:  * Effect: std::make_pair( std::min_element(first, last, comp),
Chris@16:  *                         std::max_element(first, last, comp) );
Chris@16:  */
Chris@16: 
Chris@16: #include <utility> // for std::pair and std::make_pair
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace detail {  // for obtaining a uniform version of minmax_element
Chris@16:     // that compiles with VC++ 6.0 -- avoid the iterator_traits by
Chris@16:     // having comparison object over iterator, not over dereferenced value
Chris@16: 
Chris@16:     template <typename Iterator>
Chris@16:     struct less_over_iter {
Chris@16:       bool operator()(Iterator const& it1,
Chris@16:                       Iterator const& it2) const { return *it1 < *it2; }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Iterator, class BinaryPredicate>
Chris@16:     struct binary_pred_over_iter {
Chris@16:       explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {}
Chris@16:       bool operator()(Iterator const& it1,
Chris@16:                       Iterator const& it2) const { return m_p(*it1, *it2); }
Chris@16:     private:
Chris@16:       BinaryPredicate m_p;
Chris@16:     };
Chris@16: 
Chris@16:     // common base for the two minmax_element overloads
Chris@16: 
Chris@16:     template <typename ForwardIter, class Compare >
Chris@16:     std::pair<ForwardIter,ForwardIter>
Chris@16:     basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp)
Chris@16:     {
Chris@16:       if (first == last)
Chris@16:         return std::make_pair(last,last);
Chris@16: 
Chris@16:       ForwardIter min_result = first;
Chris@16:       ForwardIter max_result = first;
Chris@16: 
Chris@16:       // if only one element
Chris@16:       ForwardIter second = first; ++second;
Chris@16:       if (second == last)
Chris@16:         return std::make_pair(min_result, max_result);
Chris@16: 
Chris@16:       // treat first pair separately (only one comparison for first two elements)
Chris@16:       ForwardIter potential_min_result = last;
Chris@16:       if (comp(first, second))
Chris@16:         max_result = second;
Chris@16:       else {
Chris@16:         min_result = second;
Chris@16:         potential_min_result = first;
Chris@16:       }
Chris@16: 
Chris@16:       // then each element by pairs, with at most 3 comparisons per pair
Chris@16:       first = ++second; if (first != last) ++second;
Chris@16:       while (second != last) {
Chris@16:         if (comp(first, second)) {
Chris@16:           if (comp(first, min_result)) {
Chris@16:             min_result = first;
Chris@16:             potential_min_result = last;
Chris@16:           }
Chris@16:           if (comp(max_result, second))
Chris@16:             max_result = second;
Chris@16:         } else {
Chris@16:           if (comp(second, min_result)) {
Chris@16:             min_result = second;
Chris@16:             potential_min_result = first;
Chris@16:           }
Chris@16:           if (comp(max_result, first))
Chris@16:             max_result = first;
Chris@16:         }
Chris@16:         first = ++second;
Chris@16:         if (first != last) ++second;
Chris@16:       }
Chris@16: 
Chris@16:       // if odd number of elements, treat last element
Chris@16:       if (first != last) { // odd number of elements
Chris@16:         if (comp(first, min_result)) {
Chris@16:           min_result = first;
Chris@16:           potential_min_result = last;
Chris@16:           }
Chris@16:         else if (comp(max_result, first))
Chris@16:           max_result = first;
Chris@16:       }
Chris@16: 
Chris@16:       // resolve min_result being incorrect with one extra comparison
Chris@16:       // (in which case potential_min_result is necessarily the correct result)
Chris@16:       if (potential_min_result != last
Chris@16:         && !comp(min_result, potential_min_result))
Chris@16:         min_result = potential_min_result;
Chris@16: 
Chris@16:       return std::make_pair(min_result,max_result);
Chris@16:     }
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   template <typename ForwardIter>
Chris@16:   std::pair<ForwardIter,ForwardIter>
Chris@16:   minmax_element(ForwardIter first, ForwardIter last)
Chris@16:   {
Chris@16:     return detail::basic_minmax_element(first, last,
Chris@16:              detail::less_over_iter<ForwardIter>() );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   std::pair<ForwardIter,ForwardIter>
Chris@16:   minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
Chris@16:   {
Chris@16:     return detail::basic_minmax_element(first, last,
Chris@16:              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
Chris@16:   }
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: /* PROPOSED BOOST EXTENSIONS
Chris@16:  * In the description below, [rfirst,rlast) denotes the reversed range
Chris@16:  * of [first,last). Even though the iterator type of first and last may
Chris@16:  * be only a Forward Iterator, it is possible to explain the semantics
Chris@16:  * by assuming that it is a Bidirectional Iterator. In the sequel,
Chris@16:  * reverse(ForwardIterator&) returns the reverse_iterator adaptor.
Chris@16:  * This is not how the functions would be implemented!
Chris@16:  *
Chris@16:  * first_min_element(first, last)
Chris@16:  * Effect: std::min_element(first, last);
Chris@16:  *
Chris@16:  * first_min_element(first, last, comp)
Chris@16:  * Effect: std::min_element(first, last, comp);
Chris@16:  *
Chris@16:  * last_min_element(first, last)
Chris@16:  * Effect: reverse( std::min_element(reverse(last), reverse(first)) );
Chris@16:  *
Chris@16:  * last_min_element(first, last, comp)
Chris@16:  * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) );
Chris@16:  *
Chris@16:  * first_max_element(first, last)
Chris@16:  * Effect: std::max_element(first, last);
Chris@16:  *
Chris@16:  * first_max_element(first, last, comp)
Chris@16:  * Effect: max_element(first, last);
Chris@16:  *
Chris@16:  * last_max_element(first, last)
Chris@16:  * Effect: reverse( std::max_element(reverse(last), reverse(first)) );
Chris@16:  *
Chris@16:  * last_max_element(first, last, comp)
Chris@16:  * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) );
Chris@16:  *
Chris@16:  * first_min_first_max_element(first, last)
Chris@16:  * Effect: std::make_pair( first_min_element(first, last),
Chris@16:  *                         first_max_element(first, last) );
Chris@16:  *
Chris@16:  * first_min_first_max_element(first, last, comp)
Chris@16:  * Effect: std::make_pair( first_min_element(first, last, comp),
Chris@16:  *                         first_max_element(first, last, comp) );
Chris@16:  *
Chris@16:  * first_min_last_max_element(first, last)
Chris@16:  * Effect: std::make_pair( first_min_element(first, last),
Chris@16:  *                         last_max_element(first, last) );
Chris@16:  *
Chris@16:  * first_min_last_max_element(first, last, comp)
Chris@16:  * Effect: std::make_pair( first_min_element(first, last, comp),
Chris@16:  *                         last_max_element(first, last, comp) );
Chris@16:  *
Chris@16:  * last_min_first_max_element(first, last)
Chris@16:  * Effect: std::make_pair( last_min_element(first, last),
Chris@16:  *                         first_max_element(first, last) );
Chris@16:  *
Chris@16:  * last_min_first_max_element(first, last, comp)
Chris@16:  * Effect: std::make_pair( last_min_element(first, last, comp),
Chris@16:  *                         first_max_element(first, last, comp) );
Chris@16:  *
Chris@16:  * last_min_last_max_element(first, last)
Chris@16:  * Effect: std::make_pair( last_min_element(first, last),
Chris@16:  *                         last_max_element(first, last) );
Chris@16:  *
Chris@16:  * last_min_last_max_element(first, last, comp)
Chris@16:  * Effect: std::make_pair( last_min_element(first, last, comp),
Chris@16:  *                         last_max_element(first, last, comp) );
Chris@16:  */
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   // Min_element and max_element variants
Chris@16: 
Chris@16:   namespace detail {  // common base for the overloads
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   ForwardIter
Chris@16:   basic_first_min_element(ForwardIter first, ForwardIter last,
Chris@16:                           BinaryPredicate comp)
Chris@16:   {
Chris@16:     if (first == last) return last;
Chris@16:     ForwardIter min_result = first;
Chris@16:     while (++first != last)
Chris@16:       if (comp(first, min_result))
Chris@16:         min_result = first;
Chris@16:     return min_result;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   ForwardIter
Chris@16:   basic_last_min_element(ForwardIter first, ForwardIter last,
Chris@16:                          BinaryPredicate comp)
Chris@16:   {
Chris@16:     if (first == last) return last;
Chris@16:     ForwardIter min_result = first;
Chris@16:     while (++first != last)
Chris@16:       if (!comp(min_result, first))
Chris@16:         min_result = first;
Chris@16:     return min_result;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   ForwardIter
Chris@16:   basic_first_max_element(ForwardIter first, ForwardIter last,
Chris@16:                           BinaryPredicate comp)
Chris@16:   {
Chris@16:     if (first == last) return last;
Chris@16:     ForwardIter max_result = first;
Chris@16:     while (++first != last)
Chris@16:       if (comp(max_result, first))
Chris@16:         max_result = first;
Chris@16:     return max_result;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   ForwardIter
Chris@16:   basic_last_max_element(ForwardIter first, ForwardIter last,
Chris@16:                          BinaryPredicate comp)
Chris@16:   {
Chris@16:     if (first == last) return last;
Chris@16:     ForwardIter max_result = first;
Chris@16:     while (++first != last)
Chris@16:       if (!comp(first, max_result))
Chris@16:         max_result = first;
Chris@16:     return max_result;
Chris@16:   }
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   template <typename ForwardIter>
Chris@16:   ForwardIter
Chris@16:   first_min_element(ForwardIter first, ForwardIter last)
Chris@16:   {
Chris@16:     return detail::basic_first_min_element(first, last,
Chris@16:              detail::less_over_iter<ForwardIter>() );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   ForwardIter
Chris@16:   first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
Chris@16:   {
Chris@16:     return detail::basic_first_min_element(first, last,
Chris@16:              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter>
Chris@16:   ForwardIter
Chris@16:   last_min_element(ForwardIter first, ForwardIter last)
Chris@16:   {
Chris@16:     return detail::basic_last_min_element(first, last,
Chris@16:              detail::less_over_iter<ForwardIter>() );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   ForwardIter
Chris@16:   last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
Chris@16:   {
Chris@16:     return detail::basic_last_min_element(first, last,
Chris@16:              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter>
Chris@16:   ForwardIter
Chris@16:   first_max_element(ForwardIter first, ForwardIter last)
Chris@16:   {
Chris@16:     return detail::basic_first_max_element(first, last,
Chris@16:              detail::less_over_iter<ForwardIter>() );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   ForwardIter
Chris@16:   first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
Chris@16:   {
Chris@16:     return detail::basic_first_max_element(first, last,
Chris@16:              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter>
Chris@16:   ForwardIter
Chris@16:   last_max_element(ForwardIter first, ForwardIter last)
Chris@16:   {
Chris@16:     return detail::basic_last_max_element(first, last,
Chris@16:              detail::less_over_iter<ForwardIter>() );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   ForwardIter
Chris@16:   last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
Chris@16:   {
Chris@16:     return detail::basic_last_max_element(first, last,
Chris@16:              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   // Minmax_element variants -- comments removed
Chris@16: 
Chris@16:   namespace detail {
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   std::pair<ForwardIter,ForwardIter>
Chris@16:   basic_first_min_last_max_element(ForwardIter first, ForwardIter last,
Chris@16:                                    BinaryPredicate comp)
Chris@16:   {
Chris@16:     if (first == last)
Chris@16:       return std::make_pair(last,last);
Chris@16: 
Chris@16:     ForwardIter min_result = first;
Chris@16:     ForwardIter max_result = first;
Chris@16: 
Chris@16:     ForwardIter second = ++first;
Chris@16:     if (second == last)
Chris@16:       return std::make_pair(min_result, max_result);
Chris@16: 
Chris@16:     if (comp(second, min_result))
Chris@16:       min_result = second;
Chris@16:     else
Chris@16:       max_result = second;
Chris@16: 
Chris@16:     first = ++second; if (first != last) ++second;
Chris@16:     while (second != last) {
Chris@16:       if (!comp(second, first)) {
Chris@16:         if (comp(first, min_result))
Chris@16:                  min_result = first;
Chris@16:         if (!comp(second, max_result))
Chris@16:           max_result = second;
Chris@16:       } else {
Chris@16:         if (comp(second, min_result))
Chris@16:           min_result = second;
Chris@16:         if (!comp(first, max_result))
Chris@16:               max_result = first;
Chris@16:       }
Chris@16:       first = ++second; if (first != last) ++second;
Chris@16:     }
Chris@16: 
Chris@16:     if (first != last) {
Chris@16:       if (comp(first, min_result))
Chris@16:          min_result = first;
Chris@16:       else if (!comp(first, max_result))
Chris@16:                max_result = first;
Chris@16:     }
Chris@16: 
Chris@16:     return std::make_pair(min_result, max_result);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   std::pair<ForwardIter,ForwardIter>
Chris@16:   basic_last_min_first_max_element(ForwardIter first, ForwardIter last,
Chris@16:                                    BinaryPredicate comp)
Chris@16:   {
Chris@16:     if (first == last) return std::make_pair(last,last);
Chris@16: 
Chris@16:     ForwardIter min_result = first;
Chris@16:     ForwardIter max_result = first;
Chris@16: 
Chris@16:     ForwardIter second = ++first;
Chris@16:     if (second == last)
Chris@16:       return std::make_pair(min_result, max_result);
Chris@16: 
Chris@16:     if (comp(max_result, second))
Chris@16:       max_result = second;
Chris@16:     else
Chris@16:       min_result = second;
Chris@16: 
Chris@16:     first = ++second; if (first != last) ++second;
Chris@16:     while (second != last)  {
Chris@16:       if (comp(first, second)) {
Chris@16:         if (!comp(min_result, first))
Chris@16:           min_result = first;
Chris@16:         if (comp(max_result, second))
Chris@16:           max_result = second;
Chris@16:       } else {
Chris@16:         if (!comp(min_result, second))
Chris@16:           min_result = second;
Chris@16:         if (comp(max_result, first))
Chris@16:           max_result = first;
Chris@16:       }
Chris@16:       first = ++second; if (first != last) ++second;
Chris@16:     }
Chris@16: 
Chris@16:     if (first != last) {
Chris@16:       if (!comp(min_result, first))
Chris@16:         min_result = first;
Chris@16:       else if (comp(max_result, first))
Chris@16:         max_result = first;
Chris@16:     }
Chris@16: 
Chris@16:     return std::make_pair(min_result, max_result);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   std::pair<ForwardIter,ForwardIter>
Chris@16:   basic_last_min_last_max_element(ForwardIter first, ForwardIter last,
Chris@16:                                   BinaryPredicate comp)
Chris@16:   {
Chris@16:     if (first == last) return std::make_pair(last,last);
Chris@16: 
Chris@16:     ForwardIter min_result = first;
Chris@16:     ForwardIter max_result = first;
Chris@16: 
Chris@16:     ForwardIter second = first; ++second;
Chris@16:     if (second == last)
Chris@16:       return std::make_pair(min_result,max_result);
Chris@16: 
Chris@16:     ForwardIter potential_max_result = last;
Chris@16:     if (comp(first, second))
Chris@16:       max_result = second;
Chris@16:     else {
Chris@16:       min_result = second;
Chris@16:       potential_max_result = second;
Chris@16:     }
Chris@16: 
Chris@16:     first = ++second; if (first != last) ++second;
Chris@16:     while (second != last) {
Chris@16:       if (comp(first, second)) {
Chris@16:         if (!comp(min_result, first))
Chris@16:           min_result = first;
Chris@16:         if (!comp(second, max_result)) {
Chris@16:           max_result = second;
Chris@16:           potential_max_result = last;
Chris@16:         }
Chris@16:       } else {
Chris@16:         if (!comp(min_result, second))
Chris@16:           min_result = second;
Chris@16:         if (!comp(first, max_result)) {
Chris@16:           max_result = first;
Chris@16:           potential_max_result = second;
Chris@16:         }
Chris@16:       }
Chris@16:       first = ++second;
Chris@16:       if (first != last) ++second;
Chris@16:     }
Chris@16: 
Chris@16:     if (first != last) {
Chris@16:       if (!comp(min_result, first))
Chris@16:         min_result = first;
Chris@16:       if (!comp(first, max_result)) {
Chris@16:         max_result = first;
Chris@16:                potential_max_result = last;
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     if (potential_max_result != last
Chris@16:         && !comp(potential_max_result, max_result))
Chris@16:       max_result = potential_max_result;
Chris@16: 
Chris@16:     return std::make_pair(min_result,max_result);
Chris@16:   }
Chris@16: 
Chris@16:   } // namespace detail
Chris@16: 
Chris@16:   template <typename ForwardIter>
Chris@16:   inline std::pair<ForwardIter,ForwardIter>
Chris@16:   first_min_first_max_element(ForwardIter first, ForwardIter last)
Chris@16:   {
Chris@16:     return minmax_element(first, last);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   inline std::pair<ForwardIter,ForwardIter>
Chris@16:   first_min_first_max_element(ForwardIter first, ForwardIter last,
Chris@16:                               BinaryPredicate comp)
Chris@16:   {
Chris@16:     return minmax_element(first, last, comp);
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter>
Chris@16:   std::pair<ForwardIter,ForwardIter>
Chris@16:   first_min_last_max_element(ForwardIter first, ForwardIter last)
Chris@16:   {
Chris@16:     return detail::basic_first_min_last_max_element(first, last,
Chris@16:              detail::less_over_iter<ForwardIter>() );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   inline std::pair<ForwardIter,ForwardIter>
Chris@16:   first_min_last_max_element(ForwardIter first, ForwardIter last,
Chris@16:                               BinaryPredicate comp)
Chris@16:   {
Chris@16:     return detail::basic_first_min_last_max_element(first, last,
Chris@16:              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter>
Chris@16:   std::pair<ForwardIter,ForwardIter>
Chris@16:   last_min_first_max_element(ForwardIter first, ForwardIter last)
Chris@16:   {
Chris@16:     return detail::basic_last_min_first_max_element(first, last,
Chris@16:              detail::less_over_iter<ForwardIter>() );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   inline std::pair<ForwardIter,ForwardIter>
Chris@16:   last_min_first_max_element(ForwardIter first, ForwardIter last,
Chris@16:                               BinaryPredicate comp)
Chris@16:   {
Chris@16:     return detail::basic_last_min_first_max_element(first, last,
Chris@16:              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter>
Chris@16:   std::pair<ForwardIter,ForwardIter>
Chris@16:   last_min_last_max_element(ForwardIter first, ForwardIter last)
Chris@16:   {
Chris@16:     return detail::basic_last_min_last_max_element(first, last,
Chris@16:              detail::less_over_iter<ForwardIter>() );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename ForwardIter, class BinaryPredicate>
Chris@16:   inline std::pair<ForwardIter,ForwardIter>
Chris@16:   last_min_last_max_element(ForwardIter first, ForwardIter last,
Chris@16:                               BinaryPredicate comp)
Chris@16:   {
Chris@16:     return detail::basic_last_min_last_max_element(first, last,
Chris@16:              detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
Chris@16:   }
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP