diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:45:59 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:45:59 +0000 |
commit | 19fcec84d8d7d21e796c7624e521b60d28ee21ed (patch) | |
tree | 42d26aa27d1e3f7c0b8bd3fd14e7d7082f5008dc /src/boost/libs/algorithm/minmax | |
parent | Initial commit. (diff) | |
download | ceph-19fcec84d8d7d21e796c7624e521b60d28ee21ed.tar.xz ceph-19fcec84d8d7d21e796c7624e521b60d28ee21ed.zip |
Adding upstream version 16.2.11+ds.upstream/16.2.11+dsupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/boost/libs/algorithm/minmax')
9 files changed, 1378 insertions, 0 deletions
diff --git a/src/boost/libs/algorithm/minmax/example/Jamfile b/src/boost/libs/algorithm/minmax/example/Jamfile new file mode 100644 index 000000000..d8650e042 --- /dev/null +++ b/src/boost/libs/algorithm/minmax/example/Jamfile @@ -0,0 +1,12 @@ +# Boost.Minmax Library Example Jamfile +# +# Copyright (C) 2002--2004, Herve Bronnimann +# +# Use, modification, and distribution is 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) +# + +exe minmax_ex : minmax_ex.cpp ; +exe minmax_timer : minmax_timer.cpp ; + diff --git a/src/boost/libs/algorithm/minmax/example/minmax_ex.cpp b/src/boost/libs/algorithm/minmax/example/minmax_ex.cpp new file mode 100644 index 000000000..d77820b39 --- /dev/null +++ b/src/boost/libs/algorithm/minmax/example/minmax_ex.cpp @@ -0,0 +1,37 @@ +// (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) + +#include <list> +#include <algorithm> +#include <cstdlib> +#include <cassert> +#include <iostream> +#include <iterator> + +#include <boost/algorithm/minmax.hpp> +#include <boost/algorithm/minmax_element.hpp> + +int main() +{ + using namespace std; + + // Demonstrating minmax() + boost::tuple<int const&, int const&> result1 = boost::minmax(1, 0); + assert( result1.get<0>() == 0 ); + assert( result1.get<1>() == 1 ); + + + // Demonstrating minmax_element() + list<int> L; + typedef list<int>::const_iterator iterator; + generate_n(front_inserter(L), 1000, rand); + pair< iterator, iterator > result2 = boost::minmax_element(L.begin(), L.end()); + + cout << "The smallest element is " << *(result2.first) << endl; + cout << "The largest element is " << *(result2.second) << endl; + + assert( result2.first == std::min_element(L.begin(), L.end()) ); + assert( result2.second == std::max_element(L.begin(), L.end()) ); +} diff --git a/src/boost/libs/algorithm/minmax/example/minmax_timer.cpp b/src/boost/libs/algorithm/minmax/example/minmax_timer.cpp new file mode 100644 index 000000000..0ab51a8a4 --- /dev/null +++ b/src/boost/libs/algorithm/minmax/example/minmax_timer.cpp @@ -0,0 +1,212 @@ +// (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) + +#include <utility> +#include <functional> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <vector> +#include <list> +#include <set> +#include <iostream> +// What's the proper BOOST_ flag for <iomanip.h> vs <ios> +#include <iomanip> + +#include <boost/timer.hpp> +#include <boost/algorithm/minmax.hpp> + +template <class T1, class T2> +void tie(std::pair<T1, T2> p, T1& min, T2& max) +{ + min = p.first; max = p.second; +} + +template <class Value> +struct less_count : std::less<Value> { + less_count(less_count<Value> const& lc) : _M_counter(lc._M_counter) {} + less_count(int& counter) : _M_counter(counter) {} + bool operator()(Value const& a, Value const& b) const { + ++_M_counter; + return std::less<Value>::operator()(a,b); + } + void reset() { + _M_counter = 0; + } +private: + int& _M_counter; +}; + +inline int opt_min_count(int n) { + return (n==0) ? 0 : n-1; +} +inline int opt_minmax_count(int n) { + if (n < 2) return 0; + if (n == 2) return 1; + return (n%2 == 0) ? 3*(n/2)-1 : 3*(n/2)+1; +} +inline int opt_boost_minmax_count(int n) { + if (n < 2) return 0; + if (n == 2) return 1; + return (n%2 == 0) ? 3*(n/2)-2 : 3*(n/2); +} + +int repeats = 10; + +#define TIMER( n, cmd , cmdname ) \ + t.restart(); \ + for (int i=0; i<repeats; ++i) { cmd ; } \ + std::cout << " " << std::setprecision(4) \ + << (double)n*repeats/t.elapsed()/1.0E6 \ + << "M items/sec " << cmdname << "\n" + +#define CTIMER( n, cmd , cmdname, count, opt ) \ + t.restart(); lc.reset(); \ + for (int i=0; i<repeats; ++i) { cmd ; } \ + std::cout << " " << std::setprecision(4) \ + << (double)n*repeats/t.elapsed()/1.0E6 \ + << "M items/sec " << cmdname \ + << " ("<< (count)/repeats << " vs " << opt << ")\n" + +template <class CIterator> +void test_minmax_element(CIterator first, CIterator last, int n, char* name) +{ + typedef typename std::iterator_traits<CIterator>::value_type vtype; + boost::timer t; + + std::cout << " ON " << name << " WITH OPERATOR<()\n"; + TIMER( n, std::min_element(first, last), + "std::min_element" << name << ""); + TIMER( n, std::max_element(first, last), + "std::max_element" << name << ""); + TIMER( n, boost::first_min_element(first, last), + "boost::first_min_element" << name << ""); + TIMER( n, boost::last_min_element(first, last), + "boost::last_min_element" << name << " "); + TIMER( n, boost::first_max_element(first, last), + "boost::first_max_element" << name << ""); + TIMER( n, boost::last_max_element(first, last), + "boost::last_max_element" << name << " "); + TIMER( n, boost::minmax_element(first, last), + "boost::minmax_element" << name << " "); + TIMER( n, boost::first_min_last_max_element(first, last), + "boost::first_min_last_max_element" << name << ""); + TIMER( n, boost::last_min_first_max_element(first, last), + "boost::last_min_first_max_element" << name << ""); + TIMER( n, boost::last_min_last_max_element(first, last), + "boost::last_min_last_max_element" << name << " "); + + #define pred std::bind2nd( std::greater<vtype>(), vtype(10) ) + TIMER( n, boost::min_element_if(first, last, pred), + "boost::min_element_if" << name << ""); + TIMER( n, boost::max_element_if(first, last, pred), + "boost::max_element_if" << name << ""); + TIMER( n, std::min_element(boost::make_filter_iterator(first, last, pred), + boost::make_filter_iterator(last, last, pred)), + "std::min_element_with_filter_iterator" << name << ""); + TIMER( n, std::max_element(boost::make_filter_iterator(first, last, pred), + boost::make_filter_iterator(last, last, pred)), + "std::max_element_if_with_filter_iterator" << name << ""); + #undef pred + + int counter = 0; + less_count<vtype> lc(counter); + std::cout << " ON " << name << " WITH LESS<> AND COUNTING COMPARISONS\n"; + CTIMER( n, std::min_element(first, last, lc), + "std::min_element" << name << " ", + counter, opt_min_count(n) ); + CTIMER( n, std::max_element(first, last, lc), + "std::max_element" << name << " ", + counter, opt_min_count(n) ); + CTIMER( n, boost::first_min_element(first, last, lc), + "boost::first_min_element" << name << "", + counter, opt_min_count(n) ); + CTIMER( n, boost::last_min_element(first, last, lc), + "boost::last_max_element" << name << " ", + counter, opt_min_count(n) ); + CTIMER( n, boost::first_max_element(first, last, lc), + "boost::first_min_element" << name << "", + counter, opt_min_count(n) ); + CTIMER( n, boost::last_max_element(first, last, lc), + "boost::last_max_element" << name << " ", + counter, opt_min_count(n) ); + CTIMER( n, boost::minmax_element(first, last, lc), + "boost::minmax_element" << name << " ", + counter, opt_minmax_count(n) ); + CTIMER( n, boost::first_min_last_max_element(first, last, lc), + "boost::first_min_last_max_element" << name << "", + counter, opt_boost_minmax_count(n) ); + CTIMER( n, boost::last_min_first_max_element(first, last, lc), + "boost::last_min_first_max_element" << name << "", + counter, opt_boost_minmax_count(n) ); + CTIMER( n, boost::last_min_last_max_element(first, last, lc), + "boost::last_min_last_max_element" << name << " ", + counter, opt_minmax_count(n) ); +} + +template <class Container, class Iterator, class Value> +void test_container(Iterator first, Iterator last, int n, char* name) +{ + Container c(first, last); + typename Container::iterator fit(c.begin()), lit(c.end()); + test_minmax_element(fit, lit, n, name); +} + +template <class Iterator> +void test_range(Iterator first, Iterator last, int n) +{ + typedef typename std::iterator_traits<Iterator>::value_type Value; + // Test various containers with these values + test_container< std::vector<Value>, Iterator, Value >(first, last, n, "<vector>"); +#ifndef ONLY_VECTOR + test_container< std::list<Value>, Iterator, Value >(first, last, n, "<list> "); + test_container< std::multiset<Value>, Iterator, Value >(first, last, n, "<set> "); +#endif +} + +template <class Value> +void test(int n) +{ + // Populate test vector with identical values + std::cout << "IDENTICAL VALUES... \n"; + std::vector<Value> test_vector(n, Value(1)); + typename std::vector<Value>::iterator first( test_vector.begin() ); + typename std::vector<Value>::iterator last( test_vector.end() ); + test_range(first, last, n); + + // Populate test vector with two values + std::cout << "TWO DISTINCT VALUES...\n"; + typename std::vector<Value>::iterator middle( first + n/2 ); + std::fill(middle, last, Value(2)); + test_range(first, last, n); + + // Populate test vector with increasing values + std::cout << "INCREASING VALUES... \n"; + std::fill(first, last, Value(1)); + std::accumulate(first, last, Value(0)); + test_range(first, last, n); + + // Populate test vector with decreasing values + std::cout << "DECREASING VALUES... \n"; + std::reverse(first, last); + test_range(first, last, n); + + // Populate test vector with random values + std::cout << "RANDOM VALUES... \n"; + std::random_shuffle(first, last); + test_range(first, last, n); +} + +int +main(char argc, char** argv) +{ + int n = 100; + if (argc > 1) n = atoi(argv[1]); + if (argc > 2) repeats = atoi(argv[2]); + + test<int>(n); + + return 0; +} diff --git a/src/boost/libs/algorithm/minmax/fuzzing/minmax_element.fuzz.cpp b/src/boost/libs/algorithm/minmax/fuzzing/minmax_element.fuzz.cpp new file mode 100644 index 000000000..63b6a9b74 --- /dev/null +++ b/src/boost/libs/algorithm/minmax/fuzzing/minmax_element.fuzz.cpp @@ -0,0 +1,81 @@ +// (C) Copyright Marshall Clow 2018 +// 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) + +#include <iterator> // for std::distance +#include <cassert> // for assert + +#include <boost/algorithm/minmax_element.hpp> +#include <boost/algorithm/cxx11/none_of.hpp> + +// Fuzzing tests for: +// +// template <class ForwardIterator> +// std::pair<ForwardIterator,ForwardIterator> +// minmax_element(ForwardIterator first, ForwardIterator last); +// +// template <class ForwardIterator, class BinaryPredicate> +// std::pair<ForwardIterator,ForwardIterator> +// minmax_element(ForwardIterator first, ForwardIterator last, +// BinaryPredicate comp); + + +bool greater(uint8_t lhs, uint8_t rhs) { return lhs > rhs; } + +extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t sz) { + typedef std::pair<const uint8_t *, const uint8_t *> result_t; + if (sz == 0) return 0; // we need at least one element + + { +// Find the min and max + result_t result = boost::minmax_element(data, data + sz); + +// The iterators have to be in the sequence - and not at the end! + assert(std::distance(data, result.first) < sz); + assert(std::distance(data, result.second) < sz); + +// the minimum element can't be bigger than the max element + uint8_t min_value = *result.first; + uint8_t max_value = *result.second; + + assert(min_value <= max_value); + +// None of the elements in the sequence can be less than the min, nor greater than the max + for (size_t i = 0; i < sz; ++i) { + assert(min_value <= data[i]); + assert(data[i] <= max_value); + } + +// We returned the first min element, and the first max element + assert(boost::algorithm::none_of_equal(data, result.first, min_value)); + assert(boost::algorithm::none_of_equal(data, result.second, max_value)); + } + + { +// Find the min and max + result_t result = boost::minmax_element(data, data + sz, greater); + +// The iterators have to be in the sequence - and not at the end! + assert(std::distance(data, result.first) < sz); + assert(std::distance(data, result.second) < sz); + +// the minimum element can't be bigger than the max element + uint8_t min_value = *result.first; + uint8_t max_value = *result.second; + + assert (!greater(max_value, min_value)); + +// None of the elements in the sequence can be less than the min, nor greater than the max + for (size_t i = 0; i < sz; ++i) { + assert(!greater(data[i], min_value)); + assert(!greater(max_value, data[i])); + } + +// We returned the first min element, and the first max element + assert(boost::algorithm::none_of_equal(data, result.first, min_value)); + assert(boost::algorithm::none_of_equal(data, result.second, max_value)); + } + + return 0; +} diff --git a/src/boost/libs/algorithm/minmax/fuzzing/minmax_element_variants.fuzz.cpp b/src/boost/libs/algorithm/minmax/fuzzing/minmax_element_variants.fuzz.cpp new file mode 100644 index 000000000..ba517e22f --- /dev/null +++ b/src/boost/libs/algorithm/minmax/fuzzing/minmax_element_variants.fuzz.cpp @@ -0,0 +1,141 @@ +// (C) Copyright Marshall Clow 2018 +// 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) + +#include <iterator> // for std::distance +#include <cassert> // for assert + +#include <boost/algorithm/minmax_element.hpp> +#include <boost/algorithm/cxx11/none_of.hpp> + +// Fuzzing tests for: +// +// template <class ForwardIterator> +// std::pair<ForwardIterator,ForwardIterator> +// first_min_first_max_element(ForwardIterator first, ForwardIterator last); +// +// template <class ForwardIterator, class BinaryPredicate> +// std::pair<ForwardIterator,ForwardIterator> +// first_min_first_max_element(ForwardIterator first, ForwardIterator last, +// BinaryPredicate comp); +// +// identical signatures for: +// first_min_last_max_element +// last_min_first_max_element +// last_min_last_max_element + +bool greater(uint8_t lhs, uint8_t rhs) { return lhs > rhs; } + +extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t sz) { + typedef std::pair<const uint8_t *, const uint8_t *> result_t; + const uint8_t * const dend = data + sz; + if (sz == 0) return 0; // we need at least one element + + { +// Find the min and max + result_t resultff = boost::first_min_first_max_element(data, dend); + result_t resultfl = boost::first_min_last_max_element (data, dend); + result_t resultlf = boost::last_min_first_max_element (data, dend); + result_t resultll = boost::last_min_last_max_element (data, dend); + +// The iterators have to be in the sequence - and not at the end! + assert(std::distance(data, resultff.first) < sz); + assert(std::distance(data, resultff.second) < sz); + assert(std::distance(data, resultfl.first) < sz); + assert(std::distance(data, resultfl.second) < sz); + assert(std::distance(data, resultlf.first) < sz); + assert(std::distance(data, resultlf.second) < sz); + assert(std::distance(data, resultll.first) < sz); + assert(std::distance(data, resultll.second) < sz); + +// the minimum element can't be bigger than the max element + +// Did we find the same min value and max value? + uint8_t min_value = *resultff.first; + uint8_t max_value = *resultff.second; + assert(min_value <= max_value); + +// Each variant should have found the same min/max values + assert(*resultff.first == min_value); + assert(*resultfl.first == min_value); + assert(*resultlf.first == min_value); + assert(*resultll.first == min_value); + + assert(*resultff.second == max_value); + assert(*resultfl.second == max_value); + assert(*resultlf.second == max_value); + assert(*resultll.second == max_value); + +// None of the elements in the sequence can be less than the min, nor greater than the max + for (size_t i = 0; i < sz; ++i) { + assert(min_value <= data[i]); + assert(data[i] <= max_value); + } + +// Make sure we returned the "right" first and last element + assert(boost::algorithm::none_of_equal(data, resultff.first, min_value)); + assert(boost::algorithm::none_of_equal(data, resultfl.first, min_value)); + assert(boost::algorithm::none_of_equal(resultlf.first + 1, dend, min_value)); + assert(boost::algorithm::none_of_equal(resultll.first + 1, dend, min_value)); + + assert(boost::algorithm::none_of_equal(data, resultff.second, max_value)); + assert(boost::algorithm::none_of_equal(resultfl.second + 1, dend, max_value)); + assert(boost::algorithm::none_of_equal(data, resultlf.second, max_value)); + assert(boost::algorithm::none_of_equal(resultll.second + 1, dend, max_value)); + } + + { +// Find the min and max + result_t resultff = boost::first_min_first_max_element(data, dend, greater); + result_t resultfl = boost::first_min_last_max_element (data, dend, greater); + result_t resultlf = boost::last_min_first_max_element (data, dend, greater); + result_t resultll = boost::last_min_last_max_element (data, dend, greater); + +// The iterators have to be in the sequence - and not at the end! + assert(std::distance(data, resultff.first) < sz); + assert(std::distance(data, resultff.second) < sz); + assert(std::distance(data, resultfl.first) < sz); + assert(std::distance(data, resultfl.second) < sz); + assert(std::distance(data, resultlf.first) < sz); + assert(std::distance(data, resultlf.second) < sz); + assert(std::distance(data, resultll.first) < sz); + assert(std::distance(data, resultll.second) < sz); + +// the minimum element can't be bigger than the max element + uint8_t min_value = *resultff.first; + uint8_t max_value = *resultff.second; + + assert (!greater(max_value, min_value)); + +// Each variant should have found the same min/max values + assert(*resultff.first == min_value); + assert(*resultfl.first == min_value); + assert(*resultlf.first == min_value); + assert(*resultll.first == min_value); + + assert(*resultff.second == max_value); + assert(*resultfl.second == max_value); + assert(*resultlf.second == max_value); + assert(*resultll.second == max_value); + +// None of the elements in the sequence can be less than the min, nor greater than the max + for (size_t i = 0; i < sz; ++i) { + assert(!greater(data[i], min_value)); + assert(!greater(max_value, data[i])); + } + +// We returned the first min element, and the first max element + assert(boost::algorithm::none_of_equal(data, resultff.first, min_value)); + assert(boost::algorithm::none_of_equal(data, resultfl.first, min_value)); + assert(boost::algorithm::none_of_equal(resultlf.first + 1, dend, min_value)); + assert(boost::algorithm::none_of_equal(resultll.first + 1, dend, min_value)); + + assert(boost::algorithm::none_of_equal(data, resultff.second, max_value)); + assert(boost::algorithm::none_of_equal(resultfl.second + 1, dend, max_value)); + assert(boost::algorithm::none_of_equal(data, resultlf.second, max_value)); + assert(boost::algorithm::none_of_equal(resultll.second + 1, dend, max_value)); + } + + return 0; +} diff --git a/src/boost/libs/algorithm/minmax/index.html b/src/boost/libs/algorithm/minmax/index.html new file mode 100644 index 000000000..f58bfe659 --- /dev/null +++ b/src/boost/libs/algorithm/minmax/index.html @@ -0,0 +1,532 @@ +<!DOCTYPE html public "-//w3c//dtd html 4.0 transitional//en"> +<HTML> +<HEAD> + <LINK REL="stylesheet" TYPE="text/css" HREF="../../../boost.css"> + <META http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> + <META name="GENERATOR" content="Mozilla/4.77 [en] (X11; U; Linux 2.2.19 i686) [Netscape]"> + <META name="Author" content="Herve Bronnimann"> + <META name="Description" content="Small library to propose minmax_element algorithm."> + <title>Boost Minmax library</title> +</HEAD> +<body text="#000000" bgcolor="#FFFFFF" link="#0000EE" vlink="#551A8B" alink="#FF0000"> + +<h2><img src="../../../boost.png" WIDTH="276" HEIGHT="86">Header <<A +HREF="../../../boost/algorithm/minmax.hpp">boost/algorithm/minmax.hpp</A>> </H2> + +<quote> +<b> +<a href="#minmax_element">Motivation</a><br> +<a href="#synopsis">Synopsis</a><br> +<a href="#description">Function templates description</a><br> +<a href="#definition">Definition</a><br> +<a href="#reqs">Requirements on types</a><br> +<a href="#precond">Preconditions</a><br> +<a href="#postcond">Postconditions</a><br> +<a href="#complexity">Complexity</a><br> +<a href="#example">Example</a><br> +<a href="#notes">Notes</a><br> +<a href="#rationale">Rationale</a><br> +<a href="#perf">Note about performance</a><br> +<a href="#acks">Acknowledgements</a> +</b> +</quote> + + +<a name="minmax_element"> +<h3> +Motivation</h3> + +<p>The minmax library is composed of two headers, <a +href="../../../boost/algorithm/minmax.hpp"><boost/algorithm/minmax.hpp></a> +and <a +href="../../../boost/algorithm/minmax_element.hpp"><boost/algorithm/minmax_element.hpp></a>. +(See <a href="#two_headers">rationale</a>.) +The problem solved by this library is that simultaneous min and max +computation requires +only one comparison, but using <tt>std::min</tt> and <tt>std::max</tt> +forces two comparisons. Worse, to compute the minimum and +maximum elements of a range of <tt>n</tt> elements requires only +<tt>3n/2+1</tt> comparisons, instead of the <tt>2n</tt> (in two passes) +forced by <tt>std::min_element</tt> and <tt>std::max_element</tt>. +I always thought it is a waste to have to call two functions to compute the +extent of a range, performing two passes over the input, when one should +be enough. The present library solves both problems.</p> + +<p>The first file implements the function templates +<tt>minmax</tt> +as straightforward extensions of the C++ +standard. As it returns a pair of <tt>const&</tt>, we must use the <a +href="../../tuple/index.html">Boost.tuple</a> library to construct such +pairs. (Please note: the intent is not to fix the known defaults of +<tt>std::min</tt> +and <tt>std::max</tt>, but to add one more algorithms that combines both; see the +<a href="#no-fix">rationale</a>.)</p> + +<p>The second file implements the function templates +<tt>minmax_element</tt>. In a +second part, it also proposes variants that can usually not be computed by +the minmax algorithm, and which are more flexible in case some elements are equal. +Those variants could have been also provided with policy-based design, +but I ruled against that (see <a href="#no-policy">rationale</a>). +</p> + +<p>If you are interested about +<a href="doc/minmax_benchs.html">performance</a>, +you will see that <tt>minmax_element</tt> is just slightly less efficient +than a single <tt>min_element</tt> or <tt>max_element</tt>, and thus +twice as efficient as two separate calls to <tt>min_element</tt> and +<tt>max_element</tt>. From a +theoretical standpoint, +all the <tt>minmax_element</tt> functions perform at most +<tt>3n/2+1</tt> +comparisons and exactly n increments of the +<tt>ForwardIterator</tt>.</p> +</a> + +<a name="synopsis"> +<h3> +Synopsis of <tt><boost/algorithm/minmax.hpp></tt></h3> + +<pre>#include <boost/tuple/tuple.hpp> + +namespace boost { + + template <class T> + tuple<T const&, T const&> + minmax(const T& a, const T& b); + + template <class T, class <a href="https://www.boost.org/sgi/stl/BinaryPredicate.html">BinaryPredicate</a>> + tuple<T const&, T const&> + minmax(const T& a, const T& b, BinaryPredicate comp); + +} +</pre> + +<h3> +Synopsis of <tt><boost/algorithm/minmax_element.hpp></tt></h3> + +<pre>#include <utility> // for std::pair + +namespace boost { + + template <class <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">ForwardIterator</a>> + std::pair<ForwardIterator,ForwardIterator> + minmax_element(ForwardIterator first, ForwardIterator last); + + template <class <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">ForwardIterator</a>, class <a href="https://www.boost.org/sgi/stl/BinaryPredicate.html">BinaryPredicate</a>> + std::pair<ForwardIterator,ForwardIterator> + minmax_element(ForwardIterator first, ForwardIterator last, + BinaryPredicate comp); + +} +</pre> + +In addition, there are a bunch of extensions which specify +which element(s) you want to pick in case of equal elements. They are: +<ul> +<li><tt>first_min_element</tt> and <tt>last_min_element</tt></li> +<li><tt>first_max_element</tt> and <tt>last_max_element</tt></li> +<li><tt>first_min_first_max_element</tt>, +<tt>first_min_last_max_element</tt>, +<tt>last_min_first_max_element</tt>, and +<tt>last_min_last_max_element</tt></li> +</ul> +I won't bore you with the complete synopsis, they have exactly the same +declaration as their corresponding <tt>_element</tt> function. Still, +you can find the complete synopsis <a href="doc/minmax_synopsis.html">here</a>. +</a> + +<a name="description"> +<h3> +Function templates description</h3> +The <tt>minmax</tt> algorithm returns a pair <tt>p</tt> containing either +<i>(a,b)</i> +or <i>(b,a)</i>, such that <tt>p.first<p.second</tt> in the first version, +or <tt>comp(p.first,p.second)</tt> in the second version. If the elements +are equivalent, the pair <i>(a,b) </i>is returned. <a href="#Note1">[1]</a> +<p>The <tt>minmax_element </tt>is semantically equivalent to <tt>first_min_first_max_element</tt>. +<p><tt>First_min_element</tt> and <tt>first_max_element</tt> find the smallest +and largest elements in the range <tt>[first, last)</tt>. If there are +several instance of these elements, the first one is returned. They are +identical to +<tt>std::min_element</tt> and <tt>std::max_element</tt>and +are only included in this library for symmetry. +<p><tt>Last_min_element</tt> and <tt>last_max_element</tt> find the smallest +and largest elements in the range <tt>[first, last)</tt>. They are almost +identical to +<tt>std::min_element</tt> and <tt>std::max_element</tt>, except +that they return the last instance of the largest element (and not the +first, as <tt>first_min_element</tt> and <tt>last_max_element</tt> would). +<p>The family of algorithms comprising <tt>first_min_first_max_element</tt>, +<tt>first_min_last_max_element</tt>, +<tt>last_min_first_max_element</tt>, +and <tt>last_min_last_max_element</tt> can be described generically as +follows (using <i><tt>which</tt></i> and +<i><tt>what</tt></i> for <tt>first</tt> +or <tt>last</tt>): <tt><i>which</i>_min_<i>what</i>_max_element</tt> finds +the (first or last, according to <i><tt>which</tt></i>) smallest element +and the (first or last, according to <i><tt>what</tt></i>) largest element +in the range +<tt>[first, last)</tt>. The first version is semantically +equivalent to: +<pre><tt> std::make_pair(boost::<i>which</i>_min_element(first,last), + boost::<i>what</i>_max_element(first,last))</tt>,</pre> +and the second version to: +<pre><tt> std::make_pair(boost::<i>which</i>_min_element(first,last,comp), + boost::<i>what</i>_max_element(first,last,comp))</tt>.</pre> + +<p><br><b><i>Note</i></b>: the <tt>first_min_last_max_element</tt> can also be described +as finding the first and last elements in the range if it were stably sorted. +</a> + +<a name="definition"> +<h3> +Definition</h3> +Defined in <a href="../../../boost/algorithm/minmax.hpp">minmax.hpp</a> +and +in <a href="../../../boost/algorithm/minmax_element.hpp">minmax_element.hpp</a>. +</a> + +<a name="reqs"> +<h3> +Requirements on types</h3> +For minmax, <tt>T</tt> must be a model of <a href="https://www.boost.org/sgi/stl/LessThanComparable.html">LessThan +Comparable</a>. +<p>For all the other function templates, versions with two template parameters: +<ul> +<li> +<tt>ForwardIterator</tt> is a model of <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">Forward +Iterator</a>.</li> + +<li> +<tt>ForwardIterator</tt>'s value type is <a href="https://www.boost.org/sgi/stl/LessThanComparable.html">LessThan +Comparable</a>.</li> +</ul> +For the versions with three template parameters: +<ul> +<li> +<tt>ForwardIterator</tt> is a model of <a href="https://www.boost.org/sgi/stl/ForwardIterator.html">Forward +Iterator</a>.</li> + +<li> +<tt>BinaryPredicate</tt> is a model of <a href="https://www.boost.org/sgi/stl/BinaryPredicate.html">Binary +Predicate</a>.</li> + +<li> +<tt>ForwardIterator</tt>'s value type is convertible to <tt>BinaryPredicate</tt>'s +first argument type and second argument type.</li> +</ul> +</a> + +<a name="precond"> +<h3> +Preconditions</h3> + +<ul> +<li> +<tt>[first, last)</tt> is a valid range.</li> +</ul> +</a> + +<a name="postcond"> +<h3> +Postconditions</h3> +In addition to the semantic description above. for <tt>minmax_element</tt> +and all the <tt><i>which</i>_min_<i>what</i>_max_element</tt> +variants, the return value is +<tt>last</tt> or <tt>std::make_pair(last,last)</tt> +if and only if <tt>[first, last)</tt> is an empty range. Otherwise, the +return value or both members of the resulting pair are iterators in the +range +<tt>[first, last)</tt>. +</a> + +<a name="complexity"> +<h3> +Complexity</h3> +Minmax performs a single comparison and is otherwise of constant complexity. +The use of <tt>boost::tuple<T const&></tt> prevents copy +constructors in case the arguments are passed by reference. +<p>The complexity of all the other algorithms is linear. They all perform +exactly n increment operations, and zero comparisons if <tt>[first,last)</tt> +is empty, otherwise : +<ul> +<li> +all the <tt>min_element</tt> and <tt>max_element</tt> variants perform +exactly<tt>(n-1)</tt> comparisons,</li> + +<li> +<tt>minmax_element</tt> , <tt>first_min_first_max_element</tt>, and <tt>last_min_last_max_element</tt> +perform at most <tt>3(n/2)-1</tt> comparisons if <tt>n</tt> is even and +non-zero, and at most <tt>3(n/2)+1</tt> if <tt>n</tt> is odd, +<a href="#Note2">[2]</a></li> + +<li> +<tt>first_min_last_max_element</tt>, and <tt>last_min_first_max_element</tt> +perform exactly <tt>3n/2-2</tt> comparisons if n is even and non-zero, +and at most <tt>3(n/2)</tt> if <tt>n</tt> is odd, +<a href="#Note1">[3]</a></li> +</ul> +where <tt>n</tt> is the number of elements in <tt>[first,last)</tt>. +</a> + +<a name="example"> +<h3> +Example</h3> +This example is included in the distribution in the examples section of +the library under +<a href="example/minmax_ex.cpp">minmax_ex.cpp</a>. + +<pre>int main() +{ + using namespace std; + boost::tuple<int const&, int const&> result1 = boost::minmax(1, 0); + + assert( result1.get<0>() == 0 ); + assert( result1.get<1>() == 1 ); + + <a href="https://www.boost.org/sgi/stl/List.html">list</a><int> L; + <a href="https://www.boost.org/sgi/stl/generate_n.html">generate_n</a>(<a href="https://www.boost.org/sgi/stl/front_insert_iterator.html">front_inserter</a>(L), 1000, rand); + + typedef list<int>::const_iterator iterator; + pair< iterator, iterator > result2 = boost::minmax_element(L.begin(), L.end()); + cout << "The smallest element is " << *(result2.first) << endl; + cout << "The largest element is " << *(result2.second) << endl; + + assert( result2.first == std::min_element(L.begin(), L.end()); + assert( result2.second == std::max_element(L.begin(), L.end()); +}</pre> +</a> + +<a name="notes"> +<h3> +Notes</h3> +<a NAME="Note1"></a><a href="#Note1">[1]</a> We do not support +idioms such as <tt><a href="../../tuple/doc/tuple_users_guide.html#tiers">tie</a>(a,b)=minmax(a,b)</tt> +to order two elements <tt>a</tt>, <tt>b</tt>, although this would have +the desired effect if we returned a reference instead of a constant +reference. The reason is that two unnecessary assignments are +performed if a and b are in order. It is better to stick to <tt>if (b<a) +swap(a,b)</tt> to achieve that effect. +<p><a NAME="Note2"></a><a href="#Note2">[2]</a> These algorithms always +perform at least <tt>3n/2-2</tt> comparisons, which is a lower bound on +the number of comparisons in any case (Cormen, Leiserson, Rivest: "Introduction +to Algorithms", section 9.1, Exercise 9.1-). The algorithms essentially compare +the elements in pairs, performing 1 comparison for the first two elements, +then 3 comparisons for each remaining pair of elements (one to order the +elements and one for updating each the minimum and and the maximum). When +the number of elements is odd, the last one needs to be compared to the +current minimum and also to the current maximum. In addition, for <tt>minmax</tt>, +in cases where equality of the two members in the pair could occur, and +the update stores the second, we save the first to check at the end if +the update should have stored the first (in case of equality). It's hard +to predict if the last comparison is performed or not, hence the at most +in both cases. +<p><a NAME="Note3"></a><a href="#Note3">[3]</a> These algorithms always +perform at least <tt>3n/2-2</tt> comparisons, which is a lower bound on +the number of comparisons in any case. The method is the same as in note +<a href="#Note2">[2]</a> +above, and like above, when the number of elements is odd, the last one +needs to be compared to the current minimum and also to the current maximum. +We can avoid the latter comparison if the former is successful, hence the +<i>at +most</i> instead of <i>exactly</i> in the odd case. +</a> + +<a name="rationale"> +<h3> +<b>Rationale:</b></h3> + +<a name="two_headers"> +<h4><b>Why not a single header <tt><boost/algorithm/minmax.hpp></tt>?</b></h4> +<p>This was the design originally proposed and approved in the formal +review. As the need for Boost.tuple became clear (due to the limitations +of <tt>std::pair</tt>), it became also annoying to require another +library for <tt>minmax_element</tt> which does not need it. Hence the +separation into two header files.</p> + +<a name="no-fix"> +<h4><b>Your minmax suffers from the same problems as std::min and +std::max.</b></h4> +<p>I am aware of the problems with std::min and +std::max, and all the debate that has been going on (please consult +<a href="#Alexandrescu">Alexandrescu's paper</a> and the links therein). But I don't see the purpose of this +library as fixing something that is part of the C++ standard. I humbly +think it's beyond the scope of this library. Rather, I am +following the way of the standard in simply providing one more function +of the same family. If someone else wants to fix std::min, their fix +would probably apply to boost::minmax as well.</p> +</a> + +<h4><b>Why no <tt>min/max_element_if</tt>?</b></h4> +<p>In a first version of the library, I proposed <tt>_if</tt> versions of +all the algorithms (well, not all, because that would be too much). +However, there is simply no reason to do so, and all the versions I had +were just as fast implemented using the excellent +<tt><boost/iterator_adaptors.hpp></tt> library. Namely, a call to +<tt>min_element_if(first, last, pred)</tt> would be just as well +implemented by: +<pre> + // equivalent to min_element_if(first, last, pred) + min_element(boost::make_filter_iterator(first, last, pred), + boost::make_filter_iterator(last, last, pred)); +</pre> +Arguably, the <tt>min_element_if</tt> version is somewhat shorter, but +the overhead of iterator adaptors is not large, and they get rid of a +lot of code (think of all the combinations between first/last and +doubling them with _if variants!).</p> + +<h4><b>Discussion: about std::max_element</b></h4> +<p>This rationale is somewhat historical, but explains why there are all +these <tt>first/last_min/max_element</tt> functions.</p> +<p>The C++ standard mandates that <tt>std::min_element</tt> and <tt>std::max_element</tt> +return the first instance of the smallest and largest elements (as opposed +to, say, the last). This arbitrary choice has some consistency: In the +case of v of type vector<int>, for instance, it is true that <tt>std::min_element(v.begin(),v.end(),std::less<int>()) +== std::max_element(v.begin(),v.end(),std::greater<int>())</tt>. +<p>There is of course nothing wrong with this: it's simply a matter of +choice. Yet another way to specify min_element and max_element is to define +them as the first and the last elements if the range was stably sorted. +(The <i>stable</i> sort is necessary to disambiguate between iterators +that have the same value.) In that case, min should return the first instance +and max should return the last. Then, both functions are related by +<tt>reverse_iterator(std::first_min_element(v.begin(),v.end(),std::less<int>())) +== +std::last_max_element(v.rbegin(),v.rend(),std::greater<int>())</tt>. +This definition is subtly different from the previous one.</p> +<p>The definition problem surfaces when one tries to design a minmax_element, +using the procedure proposed in (Cormen, Leiserson, Rivest: "Introduction +to Algorithms", section 9.1). It <i>should</i> be possible to derive an +algorithm using only <tt>3n/2</tt> comparisons if <tt>[first,last) </tt>has +<tt>n</tt> +elements, but if one tries to write a function called <tt>first_min_first_max_element()</tt> +which returns both <tt>std::min_element</tt> and <tt>std::max_element</tt> +in a pair, the trivial implementation does not work. The problem, rather +subtly, is about equal elements: I had to think for a while to find a +way to perform only three +comparisons per pair and return the first min and first max elements. +For a long time, it seemed any +attempts at doing so would consume four comparisons per pair in the worst +case. This implementation achieves three.</p> +<p>It is not possible (or even desirable) to change the meaning of +<tt>max_element</tt>, +but it is still beneficial to provide a function called <tt>minmax_element</tt>, +which returns a pair of <tt>min_element</tt> and <tt>max_element</tt>. +Although it is easy enough to call <tt>min_element</tt> and <tt>max_element</tt>, +this performs +<tt>2(n-1)</tt> comparisons, and necessitates <b>two</b> +passes over the input. In contrast, +<tt>minmax_element</tt> will perform +the fewer comparisons and perform a <b>single</b> pass over the input. +The savings can be significant when the iterator type is not a raw pointer, +or even is just a model of the InputIterator concept (although in that +case the interface would have to be +changed, as the return type could not be copied, so one could e.g. +return a value).</p> +<p>In order to benefit from all the variants of the algorithm, I propose +to introduce both <tt>first_min_element</tt> and <tt>last_min_element</tt>, +and their counterparts <tt>first_max_element</tt> and <tt>last_max_element</tt>. +Then I also propose all the variants algorithms: <tt>first_min_last_max_element</tt> +and <tt>last_min_first_max_element</tt>, which perform only at most <tt>3n/2</tt> +comparisons, and only a single pass on the input. In fact, it can be proven +that computing minmax requires at least <tt>3(n/2)-2</tt> comparisons in +any instance of the problem (Cormen, Leiserson, Rivest, 2nd edition, section +9.1). The implementation I give does not perform unnecessary comparisons +(whose result could have been computed by transitivity from previous +comparisons).</p> +<p>It appears that <tt>first_min_last_max_element</tt> may be just a tad +slower than +<tt>first_min_element</tt> alone, still much less than <tt>first_min_element</tt> +and +<tt>last_max_element</tt> called separately. <a href="#Note2">[2]</a> + +<h4><b>Why algorithms and not accumulators?</b></h4> +<p>The minmax algorithms are useful in computing the extent of a range. +In computer graphics, we need a bounding box of a set of objects. +In that case the need for a single pass is even more stringent +as all three directions must be done at once. Food for thoughts: there +is matter for a nice generic programming library with stackable <tt>update_min</tt> +and <tt>update_max</tt> function objects which store a reference to the +<tt>min_result</tt>and +<tt>max_result</tt> variables, in conjunction with the <tt>for_each</tt> +algorithm).</p> +<p>I believe many standard sequential algorithms could be reformulated +with accumulators (and many others, such as in statistics, expectation / +variance / etc.). It seems that there is room for another library, but I +do not see it competing with minmax, rather extending several algorithms +(including minmax) to the accumulator framework. However, I felt it is +beyond the scope of this library to provide such accumulators.</p> + +<a NAME="no-policy"> +<h4><b>This first/last is a perfect application for a policy-based +design.</b></h4> +<p>True, and I could have gone that way, with the default policy for +<tt>min_element</tt> and <tt>max_element</tt> to pick the first +occurence of the result. This would have thinned the number of +combinations of the minmax_element variants. But it would also have +meant to change the interface of <tt>boost::minmax_element</tt>. +One of the goals of the <tt>minmax_element</tt> algorithm is its +eventual addition to the C++ standard, in connection with +<tt>std::min_element</tt> and <tt>std::max_element</tt> +(and I feel that it would be quite natural +given the shortness of the implementation, and the not quite trivial +detail which is needed to get it right). So changing the interface by +adding policies would have meant unfortunately to depart from the +standard and created an obstacle towards that goal. Besides, the code +remains rather readable and simple without policies. So I am quite happy +to keep it like this. +</p></a> +</a> + +<a name="perf"> +<a href="doc/minmax_benchs.html"><h3><b>About performance</b></h3></a> +</a> + +<a name="acks"> +<h3> +Acknowledgements</h3> + +<a name="Alexandrescu"> +<a href="http://www.drdobbs.com/generic-min-and-max-redivivus/184403774">Generic: Min and Max Redivivus, by Andrei Alexandrescu</a> +Dr. Dobbs, April 2001 + +<p>My students in CS903 (Polytechnic Univ., <a href="http://photon.poly.edu/~hbr/cs903/">http://photon.poly.edu/~hbr/cs903/</a>) +who had <tt>minmax_element</tt> as an assignment helped clarify the issues, +and also come up with the optimum number of comparisons for <tt>first_min_last_max_element</tt>. +The identification of the issue surrounding <tt>max_element</tt> is solely +my own. +<p>One <tt>minmax_element</tt> implementation, which performs <tt>3(n/2)+O(log +n)</tt> comparisons on the average when the elements are <tt>random_shuffle</tt>d, +was suggested by my student Marc Glisse. The current one, which performs +<tt>3(n/2)+1</tt> +comparisons in the worst case, was suggested by John Iacono.<p> +<p>Finally, Matthew Wilson and Jeremy Siek contributed pre-review +comments, while Gennadiy Rozental, John Maddock, Craig Henderson, Gary +Powell participated in the review of the library, managed by Thomas +Witt. In particular, Gennadiy suggested a factorization of the code; +while I haven't followed it all the way, his suggestions do make the +code more readable and still work with older compilers. +Late after the review, as I finally scrounged to add the library for a +release, Eric Niebler noted the bad behavior of <tt>std::pair</tt> for +<tt>minmax</tt> and suggested to use Boost.tuple instead. +All my thanks for the excellent advice and reviews from all. +<h3> +See also</h3> +<tt><a href="https://www.boost.org/sgi/stl/min.html">min</a></tt>, <tt><a href="https://www.boost.org/sgi/stl/max.html">max</a></tt>, +<tt><a href="https://www.boost.org/sgi/stl/min_element.html">min_element</a></tt>, +<tt><a href="https://www.boost.org/sgi/stl/max_element.html">max_element</a></tt>, +<tt><a href="https://www.boost.org/sgi/stl/LessThanComparable.html">LessThan +Comparable</a></tt>, +<tt><a href="https://www.boost.org/sgi/stl/sort.html">sort</a></tt>, +<tt><a href="https://www.boost.org/sgi/stl/nth_element.html">nth_element</a></tt> +. +<hr SIZE="6"> +<br>Last modified 2012-12-10 +<p><font face="Arial,Helvetica"><font size=-1>© Copyright Hervé +Brönnimann, Polytechnic University, 2002--2004. +Use, modification, and distribution is subject to the Boost Software +License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">License_1_0.txt</a> or copy at +<a href="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>) +</font></font> +</body> +</html> diff --git a/src/boost/libs/algorithm/minmax/test/Jamfile.v2 b/src/boost/libs/algorithm/minmax/test/Jamfile.v2 new file mode 100644 index 000000000..384b35929 --- /dev/null +++ b/src/boost/libs/algorithm/minmax/test/Jamfile.v2 @@ -0,0 +1,25 @@ +# Boost.Minmax Library test Jamfile +# +# Copyright (C) 2002--2004, Herve Bronnimann +# +# Use, modification, and distribution is 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) +# + +import testing ; + +alias unit_test_framework + : # sources + /boost//unit_test_framework + ; + +{ + test-suite algorithm/minmax + : [ run minmax_element_test.cpp unit_test_framework + : : : : minmax_element ] + [ run minmax_test.cpp unit_test_framework + : : : : minmax ] + ; +} + diff --git a/src/boost/libs/algorithm/minmax/test/minmax_element_test.cpp b/src/boost/libs/algorithm/minmax/test/minmax_element_test.cpp new file mode 100644 index 000000000..11cf2c4cd --- /dev/null +++ b/src/boost/libs/algorithm/minmax/test/minmax_element_test.cpp @@ -0,0 +1,253 @@ +// (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) + +#include <utility> +#include <functional> +#include <algorithm> +#include <numeric> +#include <iterator> +#include <vector> +#include <list> +#include <set> +#include <cstdlib> + +#include <boost/config.hpp> /* prevents some nasty warns in MSVC */ +#include <boost/algorithm/minmax_element.hpp> +#include <boost/iterator/reverse_iterator.hpp> + +#define BOOST_TEST_MAIN +#include <boost/test/unit_test.hpp> + +#if (__cplusplus >= 201103L) || defined(BOOST_NO_CXX98_RANDOM_SHUFFLE) +#include <random> + +std::default_random_engine gen; +template<typename RandomIt> +void do_shuffle(RandomIt first, RandomIt last) +{ std::shuffle(first, last, gen); } +#else +template<typename RandomIt> +void do_shuffle(RandomIt first, RandomIt last) +{ std::random_shuffle(first, last); } +#endif + +class custom { + int m_x; + friend bool operator<(custom const& x, custom const& y); +public: + explicit custom(int x = 0) : m_x(x) {} + custom(custom const& y) : m_x(y.m_x) {} + custom operator+(custom const& y) const { return custom(m_x+y.m_x); } + custom& operator+=(custom const& y) { m_x += y.m_x; return *this; } +}; + +bool operator< (custom const& x, custom const& y) +{ + return x.m_x < y.m_x; +} + +BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(custom) + +namespace std { + +template <> +struct iterator_traits<int*> { + typedef random_access_iterator_tag iterator_category; + typedef int value_type; + typedef ptrdiff_t difference_type; + typedef value_type* pointer; + typedef value_type& reference; +}; + +template <> +struct iterator_traits<custom*> { + typedef random_access_iterator_tag iterator_category; + typedef custom value_type; + typedef ptrdiff_t difference_type; + typedef value_type* pointer; + typedef value_type& reference; +}; + +} + +template <class T1, class T2, class T3, class T4> +void tie(std::pair<T1, T2> p, T3& first, T4& second) +{ + first = T3(p.first); second = T4(p.second); +} + +template <class Value> +struct less_count : std::less<Value> { + typedef std::less<Value> Base; + less_count(less_count<Value> const& lc) : m_counter(lc.m_counter) {} + less_count(int& counter) : m_counter(counter) {} + bool operator()(Value const& a, Value const& b) const { + ++m_counter; + return Base::operator()(a,b); + } + void reset() { + m_counter = 0; + } +private: + int& m_counter; +}; + +inline int opt_min_count(int n) { + return (n==0) ? 0 : n-1; +} +inline int opt_minmax_count(int n) { + if (n < 2) return 0; + if (n == 2) return 2; + return (n%2 == 0) ? 3*(n/2)-1 : 3*(n/2)+1; +} +inline int opt_boost_minmax_count(int n) { + if (n < 2) return 0; + if (n == 2) return 1; + return (n%2 == 0) ? 3*(n/2)-2 : 3*(n/2); +} + +#define CHECK_EQUAL_ITERATORS( left, right, first ) \ +BOOST_CHECK_EQUAL( std::distance( first, left ), std::distance( first, right ) ) + +template <class CIterator> +void test_minmax(CIterator first, CIterator last, int n) +{ + using namespace boost; + + typedef typename std::iterator_traits<CIterator>::value_type Value; + typedef boost::reverse_iterator<CIterator> RCIterator; + // assume that CIterator is BidirectionalIter + CIterator min, max; + RCIterator rfirst(last), rlast(first), rmin, rmax; + int counter = 0; + less_count<Value> lc(counter); + + // standard extensions + // first version, operator< + tie( boost::minmax_element(first, last), min, max ); + + CHECK_EQUAL_ITERATORS( min, std::min_element(first, last), first ); + CHECK_EQUAL_ITERATORS( max, std::max_element(first, last), first ); + + // second version, comp function object (keeps a counter!) + lc.reset(); + tie( boost::minmax_element(first, last, lc), min, max ); + BOOST_CHECK( counter <= opt_minmax_count(n) ); + CHECK_EQUAL_ITERATORS( min, std::min_element(first, last, lc), first ); + CHECK_EQUAL_ITERATORS( max, std::max_element(first, last, lc), first ); + + // boost extensions + // first version, operator< + CHECK_EQUAL_ITERATORS( boost::first_min_element(first, last), std::min_element(first, last), first ); + rmin = RCIterator(boost::last_min_element(first, last)); + rmin = (rmin == rfirst) ? rlast : --rmin; + CHECK_EQUAL_ITERATORS( rmin, std::min_element(rfirst, rlast), rfirst ); + CHECK_EQUAL_ITERATORS( boost::first_max_element(first, last), std::max_element(first, last), first ); + rmax = RCIterator(boost::last_max_element(first, last)); + rmax = (rmax == rfirst) ? rlast : --rmax; + CHECK_EQUAL_ITERATORS( rmax, std::max_element(rfirst, rlast), rfirst ); + tie( boost::first_min_last_max_element(first, last), min, max ); + CHECK_EQUAL_ITERATORS( min, boost::first_min_element(first, last), first ); + CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last), first ); + tie( boost::last_min_first_max_element(first, last), min, max ); + CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last), first ); + CHECK_EQUAL_ITERATORS( max, boost::first_max_element(first, last), first ); + tie( boost::last_min_last_max_element(first, last), min, max ); + CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last), first ); + CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last), first ); + + // second version, comp function object (keeps a counter!) + lc.reset(); + min = boost::first_min_element(first, last, lc); + BOOST_CHECK( counter <= opt_min_count(n) ); + CHECK_EQUAL_ITERATORS( min, std::min_element(first, last, lc), first ); + lc.reset(); + rmin = RCIterator(boost::last_min_element(first, last, lc)); + rmin = (rmin == rfirst) ? rlast : --rmin; + BOOST_CHECK( counter <= opt_min_count(n) ); + CHECK_EQUAL_ITERATORS( rmin, std::min_element(rfirst, rlast, lc), rfirst ); + lc.reset(); + max = boost::first_max_element(first, last, lc); + BOOST_CHECK( counter <= opt_min_count(n) ); + CHECK_EQUAL_ITERATORS( max, std::max_element(first, last, lc), first ); + lc.reset(); + rmax = RCIterator(boost::last_max_element(first, last, lc)); + rmax = (rmax == rfirst) ? rlast : --rmax; + BOOST_CHECK( counter <= opt_min_count(n) ); + CHECK_EQUAL_ITERATORS( rmax, std::max_element(rfirst, rlast, lc), rfirst ); + lc.reset(); + tie( boost::first_min_last_max_element(first, last, lc), min, max ); + BOOST_CHECK( counter <= opt_boost_minmax_count(n) ); + CHECK_EQUAL_ITERATORS( min, boost::first_min_element(first, last, lc), first ); + CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last, lc), first ); + lc.reset(); + tie( boost::last_min_first_max_element(first, last, lc), min, max ); + BOOST_CHECK( counter <= opt_boost_minmax_count(n) ); + BOOST_CHECK( min == boost::last_min_element(first, last, lc) ); + CHECK_EQUAL_ITERATORS( max, boost::first_max_element(first, last, lc), first ); + lc.reset(); + tie( boost::last_min_last_max_element(first, last, lc), min, max ); + BOOST_CHECK( counter <= opt_minmax_count(n) ); + CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last, lc), first ); + CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last, lc), first ); +} + +template <class Container, class Iterator, class Value> +void test_container(Iterator first, Iterator last, int n, + Container* /* dummy */ = 0 + BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Value) ) +{ + Container c(first, last); + test_minmax(c.begin(), c.end(), n); +} + +template <class Iterator> +void test_range(Iterator first, Iterator last, int n) +{ + typedef typename std::iterator_traits<Iterator>::value_type Value; + // Test various containers with these values + test_container< std::vector<Value>, Iterator, Value >(first, last, n); + test_container< std::list<Value>, Iterator, Value >(first, last, n); + test_container< std::set<Value>, Iterator, Value >(first, last, n); +} + +template <class Value> +void test(int n BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Value)) +{ + // Populate test vector with identical values + std::vector<Value> test_vector(n, Value(1)); + typename std::vector<Value>::iterator first( test_vector.begin() ); + typename std::vector<Value>::iterator last( test_vector.end() ); + test_range(first, last, n); + + // Populate test vector with two values + typename std::vector<Value>::iterator middle( first + n/2 ); + std::fill(middle, last, Value(2)); + test_range(first, last, n); + + // Populate test vector with increasing values + std::accumulate(first, last, Value(0)); + test_range(first, last, n); + + // Populate test vector with decreasing values + std::reverse(first, last); + test_range(first, last, n); + + // Populate test vector with random values + do_shuffle(first, last); + test_range(first, last, n); +} + +BOOST_AUTO_TEST_CASE( test_main ) +{ +#ifndef BOOST_NO_STDC_NAMESPACE + using std::atoi; +#endif + + int n = 100; + + test<int>(n); + test<custom>(n); +} diff --git a/src/boost/libs/algorithm/minmax/test/minmax_test.cpp b/src/boost/libs/algorithm/minmax/test/minmax_test.cpp new file mode 100644 index 000000000..151b09684 --- /dev/null +++ b/src/boost/libs/algorithm/minmax/test/minmax_test.cpp @@ -0,0 +1,85 @@ +// (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) + +#include <utility> +#include <functional> + +#include <boost/config.hpp> +#include <boost/algorithm/minmax.hpp> + +#define BOOST_TEST_MAIN +#include <boost/test/unit_test.hpp> + +class custom { + int m_x; + friend std::ostream& operator<<(std::ostream& str, custom const& x); +public: + explicit custom(int x = 0) : m_x(x) {} + custom(custom const& y) : m_x(y.m_x) {} + bool operator==(custom const& y) const { return m_x == y.m_x; } + bool operator<(custom const& y) const { return m_x < y.m_x; } + custom operator+(custom const& y) const { return custom(m_x+y.m_x); } + custom& operator+=(custom const& y) { m_x += y.m_x; return *this; } +}; + +std::ostream& +operator<<(std::ostream& str, custom const& x) +{ + return str << x.m_x; +} + +template <class Value> +struct less_count : std::less<Value> { + typedef std::less<Value> Base; + less_count(less_count<Value> const& lc) : m_counter(lc.m_counter) {} + less_count(int& counter) : m_counter(counter) {} + bool operator()(Value const& a, Value const& b) const { + ++m_counter; + return Base::operator()(a,b); + } + void reset() { + m_counter = 0; + } +private: + int& m_counter; +}; + +using namespace boost; + +template <class Value> +void test(BOOST_EXPLICIT_TEMPLATE_TYPE(Value)) +{ + Value zero(0), one(1); + int counter = 0; + less_count<Value> lc(counter); + + // Test functionality + tuple<Value const&, Value const&> result1 = boost::minmax(zero, one); + BOOST_CHECK_EQUAL( get<0>(result1), zero ); + BOOST_CHECK_EQUAL( get<1>(result1), one ); + + tuple<Value const&, Value const&> result2 = boost::minmax(one, zero); + BOOST_CHECK_EQUAL( get<0>(result2), zero ); + BOOST_CHECK_EQUAL( get<1>(result2), one ); + + // Test functionality and number of comparisons + lc.reset(); + tuple<Value const&, Value const&> result3 = boost::minmax(zero, one, lc ); + BOOST_CHECK_EQUAL( get<0>(result3), zero ); + BOOST_CHECK_EQUAL( get<1>(result3), one ); + BOOST_CHECK_EQUAL( counter, 1 ); + + lc.reset(); + tuple<Value const&, Value const&> result4 = boost::minmax(one, zero, lc ); + BOOST_CHECK_EQUAL( get<0>(result4), zero ); + BOOST_CHECK_EQUAL( get<1>(result4), one ); + BOOST_CHECK_EQUAL( counter, 1); +} + +BOOST_AUTO_TEST_CASE( test_main ) +{ + test<int>(); // ("builtin"); + test<custom>(); // ("custom "); +} |