// (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 |