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

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