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 | class custom { |
24 | int m_x; |
25 | friend bool operator<(custom const& x, custom const& y); |
26 | public: |
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 | |
33 | bool operator< (custom const& x, custom const& y) |
34 | { |
35 | return x.m_x < y.m_x; |
36 | } |
37 | |
38 | BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(custom) |
39 | |
40 | namespace std { |
41 | |
42 | template <> |
43 | struct 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 | |
51 | template <> |
52 | struct 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 | |
62 | template <class T1, class T2, class T3, class T4> |
63 | void tie(std::pair<T1, T2> p, T3& first, T4& second) |
64 | { |
65 | first = T3(p.first); second = T4(p.second); |
66 | } |
67 | |
68 | template <class Value> |
69 | struct 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 | } |
80 | private: |
81 | int& m_counter; |
82 | }; |
83 | |
84 | inline int opt_min_count(int n) { |
85 | return (n==0) ? 0 : n-1; |
86 | } |
87 | inline 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 | } |
92 | inline 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 ) \ |
99 | BOOST_CHECK_EQUAL( std::distance( first, left ), std::distance( first, right ) ) |
100 | |
101 | template <class CIterator> |
102 | void 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 | |
184 | template <class Container, class Iterator, class Value> |
185 | void 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 | |
193 | template <class Iterator> |
194 | void 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 | |
203 | template <class Value> |
204 | void 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 | |
230 | BOOST_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 | |