--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/ossrv_pub/boost_apis/boost/algorithm/minmax_element.hpp Tue Feb 02 02:01:42 2010 +0200
@@ -0,0 +1,551 @@
+// (C) Copyright Herve Bronnimann 2004.
+// Use, modification and distribution are subject to 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