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
26 std::default_random_engine gen;
27 template<typename RandomIt>
do_shuffle(RandomIt first,RandomIt last)28 void do_shuffle(RandomIt first, RandomIt last)
29 { std::shuffle(first, last, gen); }
30 #else
31 template<typename RandomIt>
do_shuffle(RandomIt first,RandomIt last)32 void do_shuffle(RandomIt first, RandomIt last)
33 { std::random_shuffle(first, last); }
34 #endif
35
36 class custom {
37 int m_x;
38 friend bool operator<(custom const& x, custom const& y);
39 public:
custom(int x=0)40 explicit custom(int x = 0) : m_x(x) {}
custom(custom const & y)41 custom(custom const& y) : m_x(y.m_x) {}
operator +(custom const & y) const42 custom operator+(custom const& y) const { return custom(m_x+y.m_x); }
operator +=(custom const & y)43 custom& operator+=(custom const& y) { m_x += y.m_x; return *this; }
44 };
45
operator <(custom const & x,custom const & y)46 bool operator< (custom const& x, custom const& y)
47 {
48 return x.m_x < y.m_x;
49 }
50
51 BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(custom)
52
53 namespace std {
54
55 template <>
56 struct 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
64 template <>
65 struct 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
75 template <class T1, class T2, class T3, class T4>
tie(std::pair<T1,T2> p,T3 & first,T4 & second)76 void tie(std::pair<T1, T2> p, T3& first, T4& second)
77 {
78 first = T3(p.first); second = T4(p.second);
79 }
80
81 template <class Value>
82 struct less_count : std::less<Value> {
83 typedef std::less<Value> Base;
less_countless_count84 less_count(less_count<Value> const& lc) : m_counter(lc.m_counter) {}
less_countless_count85 less_count(int& counter) : m_counter(counter) {}
operator ()less_count86 bool operator()(Value const& a, Value const& b) const {
87 ++m_counter;
88 return Base::operator()(a,b);
89 }
resetless_count90 void reset() {
91 m_counter = 0;
92 }
93 private:
94 int& m_counter;
95 };
96
opt_min_count(int n)97 inline int opt_min_count(int n) {
98 return (n==0) ? 0 : n-1;
99 }
opt_minmax_count(int n)100 inline 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 }
opt_boost_minmax_count(int n)105 inline 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 ) \
112 BOOST_CHECK_EQUAL( std::distance( first, left ), std::distance( first, right ) )
113
114 template <class CIterator>
test_minmax(CIterator first,CIterator last,int n)115 void 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
197 template <class Container, class Iterator, class Value>
test_container(Iterator first,Iterator last,int n,Container * =0BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE (Value))198 void 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
206 template <class Iterator>
test_range(Iterator first,Iterator last,int n)207 void 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
216 template <class Value>
test(int n BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE (Value))217 void 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
BOOST_AUTO_TEST_CASE(test_main)243 BOOST_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