boost/algorithm/minmax_element.hpp

//  (C) Copyright Herve Bronnimann 2004.
//
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

/*
 Revision history:
   1 July 2004
      Split the code into two headers to lessen dependence on
      Boost.tuple. (Herve)
   26 June 2004
      Added the code for the boost minmax library. (Herve)
*/

#ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP
#define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP

/* PROPOSED STANDARD EXTENSIONS:
 *
 * minmax_element(first, last)
 * Effect: std::make_pair( std::min_element(first, last),
 *                         std::max_element(first, last) );
 *
 * minmax_element(first, last, comp)
 * Effect: std::make_pair( std::min_element(first, last, comp),
 *                         std::max_element(first, last, comp) );
 */

#include <utility> // for std::pair and std::make_pair

namespace boost {

  namespace detail {  // for obtaining a uniform version of minmax_element
    // that compiles with VC++ 6.0 -- avoid the iterator_traits by
    // having comparison object over iterator, not over dereferenced value

    template <typename Iterator>
    struct less_over_iter {
      bool operator()(Iterator const& it1,
                      Iterator const& it2) const { return *it1 < *it2; }
    };

    template <typename Iterator, class BinaryPredicate>
    struct binary_pred_over_iter {
      explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {}
      bool operator()(Iterator const& it1,
                      Iterator const& it2) const { return m_p(*it1, *it2); }
    private:
      BinaryPredicate m_p;
    };

    // common base for the two minmax_element overloads

    template <typename ForwardIter, class Compare >
    std::pair<ForwardIter,ForwardIter>
    basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp)
    {
      if (first == last)
        return std::make_pair(last,last);

      ForwardIter min_result = first;
      ForwardIter max_result = first;

      // if only one element
      ForwardIter second = first; ++second;
      if (second == last)
        return std::make_pair(min_result, max_result);

      // treat first pair separately (only one comparison for first two elements)
      ForwardIter potential_min_result = last;
      if (comp(first, second))
        max_result = second;
      else {
        min_result = second;
        potential_min_result = first;
      }

      // then each element by pairs, with at most 3 comparisons per pair
      first = ++second; if (first != last) ++second;
      while (second != last) {
        if (comp(first, second)) {
          if (comp(first, min_result)) {
            min_result = first;
            potential_min_result = last;
          }
          if (comp(max_result, second))
            max_result = second;
        } else {
          if (comp(second, min_result)) {
            min_result = second;
            potential_min_result = first;
          }
          if (comp(max_result, first))
            max_result = first;
        }
        first = ++second;
        if (first != last) ++second;
      }

      // if odd number of elements, treat last element
      if (first != last) { // odd number of elements
        if (comp(first, min_result)) {
          min_result = first;
          potential_min_result = last;
          }
        else if (comp(max_result, first))
          max_result = first;
      }

      // resolve min_result being incorrect with one extra comparison
      // (in which case potential_min_result is necessarily the correct result)
      if (potential_min_result != last
        && !comp(min_result, potential_min_result))
        min_result = potential_min_result;

      return std::make_pair(min_result,max_result);
    }

  } // namespace detail

  template <typename ForwardIter>
  std::pair<ForwardIter,ForwardIter>
  minmax_element(ForwardIter first, ForwardIter last)
  {
    return detail::basic_minmax_element(first, last,
             detail::less_over_iter<ForwardIter>() );
  }

  template <typename ForwardIter, class BinaryPredicate>
  std::pair<ForwardIter,ForwardIter>
  minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
  {
    return detail::basic_minmax_element(first, last,
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
  }

}

/* PROPOSED BOOST EXTENSIONS
 * In the description below, [rfirst,rlast) denotes the reversed range
 * of [first,last). Even though the iterator type of first and last may
 * be only a Forward Iterator, it is possible to explain the semantics
 * by assuming that it is a Bidirectional Iterator. In the sequel,
 * reverse(ForwardIterator&) returns the reverse_iterator adaptor.
 * This is not how the functions would be implemented!
 *
 * first_min_element(first, last)
 * Effect: std::min_element(first, last);
 *
 * first_min_element(first, last, comp)
 * Effect: std::min_element(first, last, comp);
 *
 * last_min_element(first, last)
 * Effect: reverse( std::min_element(reverse(last), reverse(first)) );
 *
 * last_min_element(first, last, comp)
 * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) );
 *
 * first_max_element(first, last)
 * Effect: std::max_element(first, last);
 *
 * first_max_element(first, last, comp)
 * Effect: max_element(first, last);
 *
 * last_max_element(first, last)
 * Effect: reverse( std::max_element(reverse(last), reverse(first)) );
 *
 * last_max_element(first, last, comp)
 * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) );
 *
 * first_min_first_max_element(first, last)
 * Effect: std::make_pair( first_min_element(first, last),
 *                         first_max_element(first, last) );
 *
 * first_min_first_max_element(first, last, comp)
 * Effect: std::make_pair( first_min_element(first, last, comp),
 *                         first_max_element(first, last, comp) );
 *
 * first_min_last_max_element(first, last)
 * Effect: std::make_pair( first_min_element(first, last),
 *                         last_max_element(first, last) );
 *
 * first_min_last_max_element(first, last, comp)
 * Effect: std::make_pair( first_min_element(first, last, comp),
 *                         last_max_element(first, last, comp) );
 *
 * last_min_first_max_element(first, last)
 * Effect: std::make_pair( last_min_element(first, last),
 *                         first_max_element(first, last) );
 *
 * last_min_first_max_element(first, last, comp)
 * Effect: std::make_pair( last_min_element(first, last, comp),
 *                         first_max_element(first, last, comp) );
 *
 * last_min_last_max_element(first, last)
 * Effect: std::make_pair( last_min_element(first, last),
 *                         last_max_element(first, last) );
 *
 * last_min_last_max_element(first, last, comp)
 * Effect: std::make_pair( last_min_element(first, last, comp),
 *                         last_max_element(first, last, comp) );
 */

namespace boost {

  // Min_element and max_element variants

  namespace detail {  // common base for the overloads

  template <typename ForwardIter, class BinaryPredicate>
  ForwardIter
  basic_first_min_element(ForwardIter first, ForwardIter last,
                          BinaryPredicate comp)
  {
    if (first == last) return last;
    ForwardIter min_result = first;
    while (++first != last)
      if (comp(first, min_result))
        min_result = first;
    return min_result;
  }

  template <typename ForwardIter, class BinaryPredicate>
  ForwardIter
  basic_last_min_element(ForwardIter first, ForwardIter last,
                         BinaryPredicate comp)
  {
    if (first == last) return last;
    ForwardIter min_result = first;
    while (++first != last)
      if (!comp(min_result, first))
        min_result = first;
    return min_result;
  }

  template <typename ForwardIter, class BinaryPredicate>
  ForwardIter
  basic_first_max_element(ForwardIter first, ForwardIter last,
                          BinaryPredicate comp)
  {
    if (first == last) return last;
    ForwardIter max_result = first;
    while (++first != last)
      if (comp(max_result, first))
        max_result = first;
    return max_result;
  }

  template <typename ForwardIter, class BinaryPredicate>
  ForwardIter
  basic_last_max_element(ForwardIter first, ForwardIter last,
                         BinaryPredicate comp)
  {
    if (first == last) return last;
    ForwardIter max_result = first;
    while (++first != last)
      if (!comp(first, max_result))
        max_result = first;
    return max_result;
  }

  } // namespace detail

  template <typename ForwardIter>
  ForwardIter
  first_min_element(ForwardIter first, ForwardIter last)
  {
    return detail::basic_first_min_element(first, last,
             detail::less_over_iter<ForwardIter>() );
  }

  template <typename ForwardIter, class BinaryPredicate>
  ForwardIter
  first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
  {
    return detail::basic_first_min_element(first, last,
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
  }

  template <typename ForwardIter>
  ForwardIter
  last_min_element(ForwardIter first, ForwardIter last)
  {
    return detail::basic_last_min_element(first, last,
             detail::less_over_iter<ForwardIter>() );
  }

  template <typename ForwardIter, class BinaryPredicate>
  ForwardIter
  last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
  {
    return detail::basic_last_min_element(first, last,
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
  }

  template <typename ForwardIter>
  ForwardIter
  first_max_element(ForwardIter first, ForwardIter last)
  {
    return detail::basic_first_max_element(first, last,
             detail::less_over_iter<ForwardIter>() );
  }

  template <typename ForwardIter, class BinaryPredicate>
  ForwardIter
  first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
  {
    return detail::basic_first_max_element(first, last,
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
  }

  template <typename ForwardIter>
  ForwardIter
  last_max_element(ForwardIter first, ForwardIter last)
  {
    return detail::basic_last_max_element(first, last,
             detail::less_over_iter<ForwardIter>() );
  }

  template <typename ForwardIter, class BinaryPredicate>
  ForwardIter
  last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp)
  {
    return detail::basic_last_max_element(first, last,
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
  }


  // Minmax_element variants -- comments removed

  namespace detail {

  template <typename ForwardIter, class BinaryPredicate>
  std::pair<ForwardIter,ForwardIter>
  basic_first_min_last_max_element(ForwardIter first, ForwardIter last,
                                   BinaryPredicate comp)
  {
    if (first == last)
      return std::make_pair(last,last);

    ForwardIter min_result = first;
    ForwardIter max_result = first;

    ForwardIter second = ++first;
    if (second == last)
      return std::make_pair(min_result, max_result);

    if (comp(second, min_result))
      min_result = second;
    else
      max_result = second;

    first = ++second; if (first != last) ++second;
    while (second != last) {
      if (!comp(second, first)) {
        if (comp(first, min_result))
                 min_result = first;
        if (!comp(second, max_result))
          max_result = second;
      } else {
        if (comp(second, min_result))
          min_result = second;
        if (!comp(first, max_result))
              max_result = first;
      }
      first = ++second; if (first != last) ++second;
    }

    if (first != last) {
      if (comp(first, min_result))
         min_result = first;
      else if (!comp(first, max_result))
               max_result = first;
    }

    return std::make_pair(min_result, max_result);
  }

  template <typename ForwardIter, class BinaryPredicate>
  std::pair<ForwardIter,ForwardIter>
  basic_last_min_first_max_element(ForwardIter first, ForwardIter last,
                                   BinaryPredicate comp)
  {
    if (first == last) return std::make_pair(last,last);

    ForwardIter min_result = first;
    ForwardIter max_result = first;

    ForwardIter second = ++first;
    if (second == last)
      return std::make_pair(min_result, max_result);

    if (comp(max_result, second))
      max_result = second;
    else
      min_result = second;

    first = ++second; if (first != last) ++second;
    while (second != last)  {
      if (comp(first, second)) {
        if (!comp(min_result, first))
          min_result = first;
        if (comp(max_result, second))
          max_result = second;
      } else {
        if (!comp(min_result, second))
          min_result = second;
        if (comp(max_result, first))
          max_result = first;
      }
      first = ++second; if (first != last) ++second;
    }

    if (first != last) {
      if (!comp(min_result, first))
        min_result = first;
      else if (comp(max_result, first))
        max_result = first;
    }

    return std::make_pair(min_result, max_result);
  }

  template <typename ForwardIter, class BinaryPredicate>
  std::pair<ForwardIter,ForwardIter>
  basic_last_min_last_max_element(ForwardIter first, ForwardIter last,
                                  BinaryPredicate comp)
  {
    if (first == last) return std::make_pair(last,last);

    ForwardIter min_result = first;
    ForwardIter max_result = first;

    ForwardIter second = first; ++second;
    if (second == last)
      return std::make_pair(min_result,max_result);

    ForwardIter potential_max_result = last;
    if (comp(first, second))
      max_result = second;
    else {
      min_result = second;
      potential_max_result = second;
    }

    first = ++second; if (first != last) ++second;
    while (second != last) {
      if (comp(first, second)) {
        if (!comp(min_result, first))
          min_result = first;
        if (!comp(second, max_result)) {
          max_result = second;
          potential_max_result = last;
        }
      } else {
        if (!comp(min_result, second))
          min_result = second;
        if (!comp(first, max_result)) {
          max_result = first;
          potential_max_result = second;
        }
      }
      first = ++second;
      if (first != last) ++second;
    }

    if (first != last) {
      if (!comp(min_result, first))
        min_result = first;
      if (!comp(first, max_result)) {
        max_result = first;
               potential_max_result = last;
      }
    }

    if (potential_max_result != last
        && !comp(potential_max_result, max_result))
      max_result = potential_max_result;

    return std::make_pair(min_result,max_result);
  }

  } // namespace detail

  template <typename ForwardIter>
  inline std::pair<ForwardIter,ForwardIter>
  first_min_first_max_element(ForwardIter first, ForwardIter last)
  {
    return minmax_element(first, last);
  }

  template <typename ForwardIter, class BinaryPredicate>
  inline std::pair<ForwardIter,ForwardIter>
  first_min_first_max_element(ForwardIter first, ForwardIter last,
                              BinaryPredicate comp)
  {
    return minmax_element(first, last, comp);
  }

  template <typename ForwardIter>
  std::pair<ForwardIter,ForwardIter>
  first_min_last_max_element(ForwardIter first, ForwardIter last)
  {
    return detail::basic_first_min_last_max_element(first, last,
             detail::less_over_iter<ForwardIter>() );
  }

  template <typename ForwardIter, class BinaryPredicate>
  inline std::pair<ForwardIter,ForwardIter>
  first_min_last_max_element(ForwardIter first, ForwardIter last,
                              BinaryPredicate comp)
  {
    return detail::basic_first_min_last_max_element(first, last,
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
  }

  template <typename ForwardIter>
  std::pair<ForwardIter,ForwardIter>
  last_min_first_max_element(ForwardIter first, ForwardIter last)
  {
    return detail::basic_last_min_first_max_element(first, last,
             detail::less_over_iter<ForwardIter>() );
  }

  template <typename ForwardIter, class BinaryPredicate>
  inline std::pair<ForwardIter,ForwardIter>
  last_min_first_max_element(ForwardIter first, ForwardIter last,
                              BinaryPredicate comp)
  {
    return detail::basic_last_min_first_max_element(first, last,
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
  }

  template <typename ForwardIter>
  std::pair<ForwardIter,ForwardIter>
  last_min_last_max_element(ForwardIter first, ForwardIter last)
  {
    return detail::basic_last_min_last_max_element(first, last,
             detail::less_over_iter<ForwardIter>() );
  }

  template <typename ForwardIter, class BinaryPredicate>
  inline std::pair<ForwardIter,ForwardIter>
  last_min_last_max_element(ForwardIter first, ForwardIter last,
                              BinaryPredicate comp)
  {
    return detail::basic_last_min_last_max_element(first, last,
             detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) );
  }

} // namespace boost

#endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP