1// (C) Copyright Herve Bronnimann 2004.
2// Use, modification and distribution are subject to the
3// Boost Software License, Version 1.0. (See accompanying file
4// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6#include <utility>
7#include <functional>
8#include <algorithm>
9#include <numeric>
10#include <iterator>
11#include <vector>
12#include <list>
13#include <set>
14#include <cstdlib>
15
16#include <boost/config.hpp> /* prevents some nasty warns in MSVC */
17#include <boost/algorithm/minmax_element.hpp>
18#include <boost/iterator/reverse_iterator.hpp>
19
20#define BOOST_TEST_MAIN
21#include <boost/test/unit_test.hpp>
22
23#if (__cplusplus >= 201103L) || defined(BOOST_NO_CXX98_RANDOM_SHUFFLE)
24#include <random>
25
26std::default_random_engine gen;
27template<typename RandomIt>
28void do_shuffle(RandomIt first, RandomIt last)
29{ std::shuffle(first, last, gen); }
30#else
31template<typename RandomIt>
32void do_shuffle(RandomIt first, RandomIt last)
33{ std::random_shuffle(first, last); }
34#endif
35
36class custom {
37 int m_x;
38 friend bool operator<(custom const& x, custom const& y);
39public:
40 explicit custom(int x = 0) : m_x(x) {}
41 custom(custom const& y) : m_x(y.m_x) {}
42 custom operator+(custom const& y) const { return custom(m_x+y.m_x); }
43 custom& operator+=(custom const& y) { m_x += y.m_x; return *this; }
44};
45
46bool operator< (custom const& x, custom const& y)
47{
48 return x.m_x < y.m_x;
49}
50
51BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(custom)
52
53namespace std {
54
55template <>
56struct iterator_traits<int*> {
57 typedef random_access_iterator_tag iterator_category;
58 typedef int value_type;
59 typedef ptrdiff_t difference_type;
60 typedef value_type* pointer;
61 typedef value_type& reference;
62};
63
64template <>
65struct iterator_traits<custom*> {
66 typedef random_access_iterator_tag iterator_category;
67 typedef custom value_type;
68 typedef ptrdiff_t difference_type;
69 typedef value_type* pointer;
70 typedef value_type& reference;
71};
72
73}
74
75template <class T1, class T2, class T3, class T4>
76void tie(std::pair<T1, T2> p, T3& first, T4& second)
77{
78 first = T3(p.first); second = T4(p.second);
79}
80
81template <class Value>
82struct less_count : std::less<Value> {
83 typedef std::less<Value> Base;
84 less_count(less_count<Value> const& lc) : m_counter(lc.m_counter) {}
85 less_count(int& counter) : m_counter(counter) {}
86 bool operator()(Value const& a, Value const& b) const {
87 ++m_counter;
88 return Base::operator()(a,b);
89 }
90 void reset() {
91 m_counter = 0;
92 }
93private:
94 int& m_counter;
95};
96
97inline int opt_min_count(int n) {
98 return (n==0) ? 0 : n-1;
99}
100inline int opt_minmax_count(int n) {
101 if (n < 2) return 0;
102 if (n == 2) return 2;
103 return (n%2 == 0) ? 3*(n/2)-1 : 3*(n/2)+1;
104}
105inline int opt_boost_minmax_count(int n) {
106 if (n < 2) return 0;
107 if (n == 2) return 1;
108 return (n%2 == 0) ? 3*(n/2)-2 : 3*(n/2);
109}
110
111#define CHECK_EQUAL_ITERATORS( left, right, first ) \
112BOOST_CHECK_EQUAL( std::distance( first, left ), std::distance( first, right ) )
113
114template <class CIterator>
115void test_minmax(CIterator first, CIterator last, int n)
116{
117 using namespace boost;
118
119 typedef typename std::iterator_traits<CIterator>::value_type Value;
120 typedef boost::reverse_iterator<CIterator> RCIterator;
121 // assume that CIterator is BidirectionalIter
122 CIterator min, max;
123 RCIterator rfirst(last), rlast(first), rmin, rmax;
124 int counter = 0;
125 less_count<Value> lc(counter);
126
127 // standard extensions
128 // first version, operator<
129 tie( boost::minmax_element(first, last), min, max );
130
131 CHECK_EQUAL_ITERATORS( min, std::min_element(first, last), first );
132 CHECK_EQUAL_ITERATORS( max, std::max_element(first, last), first );
133
134 // second version, comp function object (keeps a counter!)
135 lc.reset();
136 tie( boost::minmax_element(first, last, lc), min, max );
137 BOOST_CHECK( counter <= opt_minmax_count(n) );
138 CHECK_EQUAL_ITERATORS( min, std::min_element(first, last, lc), first );
139 CHECK_EQUAL_ITERATORS( max, std::max_element(first, last, lc), first );
140
141 // boost extensions
142 // first version, operator<
143 CHECK_EQUAL_ITERATORS( boost::first_min_element(first, last), std::min_element(first, last), first );
144 rmin = RCIterator(boost::last_min_element(first, last));
145 rmin = (rmin == rfirst) ? rlast : --rmin;
146 CHECK_EQUAL_ITERATORS( rmin, std::min_element(rfirst, rlast), rfirst );
147 CHECK_EQUAL_ITERATORS( boost::first_max_element(first, last), std::max_element(first, last), first );
148 rmax = RCIterator(boost::last_max_element(first, last));
149 rmax = (rmax == rfirst) ? rlast : --rmax;
150 CHECK_EQUAL_ITERATORS( rmax, std::max_element(rfirst, rlast), rfirst );
151 tie( boost::first_min_last_max_element(first, last), min, max );
152 CHECK_EQUAL_ITERATORS( min, boost::first_min_element(first, last), first );
153 CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last), first );
154 tie( boost::last_min_first_max_element(first, last), min, max );
155 CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last), first );
156 CHECK_EQUAL_ITERATORS( max, boost::first_max_element(first, last), first );
157 tie( boost::last_min_last_max_element(first, last), min, max );
158 CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last), first );
159 CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last), first );
160
161 // second version, comp function object (keeps a counter!)
162 lc.reset();
163 min = boost::first_min_element(first, last, lc);
164 BOOST_CHECK( counter <= opt_min_count(n) );
165 CHECK_EQUAL_ITERATORS( min, std::min_element(first, last, lc), first );
166 lc.reset();
167 rmin = RCIterator(boost::last_min_element(first, last, lc));
168 rmin = (rmin == rfirst) ? rlast : --rmin;
169 BOOST_CHECK( counter <= opt_min_count(n) );
170 CHECK_EQUAL_ITERATORS( rmin, std::min_element(rfirst, rlast, lc), rfirst );
171 lc.reset();
172 max = boost::first_max_element(first, last, lc);
173 BOOST_CHECK( counter <= opt_min_count(n) );
174 CHECK_EQUAL_ITERATORS( max, std::max_element(first, last, lc), first );
175 lc.reset();
176 rmax = RCIterator(boost::last_max_element(first, last, lc));
177 rmax = (rmax == rfirst) ? rlast : --rmax;
178 BOOST_CHECK( counter <= opt_min_count(n) );
179 CHECK_EQUAL_ITERATORS( rmax, std::max_element(rfirst, rlast, lc), rfirst );
180 lc.reset();
181 tie( boost::first_min_last_max_element(first, last, lc), min, max );
182 BOOST_CHECK( counter <= opt_boost_minmax_count(n) );
183 CHECK_EQUAL_ITERATORS( min, boost::first_min_element(first, last, lc), first );
184 CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last, lc), first );
185 lc.reset();
186 tie( boost::last_min_first_max_element(first, last, lc), min, max );
187 BOOST_CHECK( counter <= opt_boost_minmax_count(n) );
188 BOOST_CHECK( min == boost::last_min_element(first, last, lc) );
189 CHECK_EQUAL_ITERATORS( max, boost::first_max_element(first, last, lc), first );
190 lc.reset();
191 tie( boost::last_min_last_max_element(first, last, lc), min, max );
192 BOOST_CHECK( counter <= opt_minmax_count(n) );
193 CHECK_EQUAL_ITERATORS( min, boost::last_min_element(first, last, lc), first );
194 CHECK_EQUAL_ITERATORS( max, boost::last_max_element(first, last, lc), first );
195}
196
197template <class Container, class Iterator, class Value>
198void test_container(Iterator first, Iterator last, int n,
199 Container* /* dummy */ = 0
200 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Value) )
201{
202 Container c(first, last);
203 test_minmax(c.begin(), c.end(), n);
204}
205
206template <class Iterator>
207void test_range(Iterator first, Iterator last, int n)
208{
209 typedef typename std::iterator_traits<Iterator>::value_type Value;
210 // Test various containers with these values
211 test_container< std::vector<Value>, Iterator, Value >(first, last, n);
212 test_container< std::list<Value>, Iterator, Value >(first, last, n);
213 test_container< std::set<Value>, Iterator, Value >(first, last, n);
214}
215
216template <class Value>
217void test(int n BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Value))
218{
219 // Populate test vector with identical values
220 std::vector<Value> test_vector(n, Value(1));
221 typename std::vector<Value>::iterator first( test_vector.begin() );
222 typename std::vector<Value>::iterator last( test_vector.end() );
223 test_range(first, last, n);
224
225 // Populate test vector with two values
226 typename std::vector<Value>::iterator middle( first + n/2 );
227 std::fill(middle, last, Value(2));
228 test_range(first, last, n);
229
230 // Populate test vector with increasing values
231 std::accumulate(first, last, Value(0));
232 test_range(first, last, n);
233
234 // Populate test vector with decreasing values
235 std::reverse(first, last);
236 test_range(first, last, n);
237
238 // Populate test vector with random values
239 do_shuffle(first, last);
240 test_range(first, last, n);
241}
242
243BOOST_AUTO_TEST_CASE( test_main )
244{
245#ifndef BOOST_NO_STDC_NAMESPACE
246 using std::atoi;
247#endif
248
249 int n = 100;
250
251 test<int>(n);
252 test<custom>(n);
253}
254

source code of boost/libs/algorithm/minmax/test/minmax_element_test.cpp