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)
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>
20 #define BOOST_TEST_MAIN
21 #include <boost/test/unit_test.hpp>
23 #if (__cplusplus >= 201103L) || defined(BOOST_NO_CXX98_RANDOM_SHUFFLE)
26 std::default_random_engine gen
;
27 template<typename RandomIt
>
28 void do_shuffle(RandomIt first
, RandomIt last
)
29 { std::shuffle(first
, last
, gen
); }
31 template<typename RandomIt
>
32 void do_shuffle(RandomIt first
, RandomIt last
)
33 { std::random_shuffle(first
, last
); }
38 friend bool operator<(custom
const& x
, custom
const& y
);
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; }
46 bool operator< (custom
const& x
, custom
const& y
)
51 BOOST_BROKEN_COMPILER_TYPE_TRAITS_SPECIALIZATION(custom
)
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
;
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
;
75 template <class T1
, class T2
, class T3
, class T4
>
76 void tie(std::pair
<T1
, T2
> p
, T3
& first
, T4
& second
)
78 first
= T3(p
.first
); second
= T4(p
.second
);
81 template <class Value
>
82 struct 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 {
88 return Base::operator()(a
,b
);
97 inline int opt_min_count(int n
) {
98 return (n
==0) ? 0 : n
-1;
100 inline int opt_minmax_count(int n
) {
102 if (n
== 2) return 2;
103 return (n
%2 == 0) ? 3*(n
/2)-1 : 3*(n
/2)+1;
105 inline int opt_boost_minmax_count(int n
) {
107 if (n
== 2) return 1;
108 return (n
%2 == 0) ? 3*(n
/2)-2 : 3*(n
/2);
111 #define CHECK_EQUAL_ITERATORS( left, right, first ) \
112 BOOST_CHECK_EQUAL( std::distance( first, left ), std::distance( first, right ) )
114 template <class CIterator
>
115 void test_minmax(CIterator first
, CIterator last
, int n
)
117 using namespace boost
;
119 typedef typename
std::iterator_traits
<CIterator
>::value_type Value
;
120 typedef boost::reverse_iterator
<CIterator
> RCIterator
;
121 // assume that CIterator is BidirectionalIter
123 RCIterator
rfirst(last
), rlast(first
), rmin
, rmax
;
125 less_count
<Value
> lc(counter
);
127 // standard extensions
128 // first version, operator<
129 tie( boost::minmax_element(first
, last
), min
, max
);
131 CHECK_EQUAL_ITERATORS( min
, std::min_element(first
, last
), first
);
132 CHECK_EQUAL_ITERATORS( max
, std::max_element(first
, last
), first
);
134 // second version, comp function object (keeps a counter!)
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
);
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
);
161 // second version, comp function object (keeps a counter!)
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
);
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
);
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
);
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
);
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
);
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
);
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
);
197 template <class Container
, class Iterator
, class Value
>
198 void test_container(Iterator first
, Iterator last
, int n
,
199 Container
* /* dummy */ = 0
200 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Value
) )
202 Container
c(first
, last
);
203 test_minmax(c
.begin(), c
.end(), n
);
206 template <class Iterator
>
207 void test_range(Iterator first
, Iterator last
, int n
)
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
);
216 template <class Value
>
217 void test(int n
BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Value
))
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
);
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
);
230 // Populate test vector with increasing values
231 std::accumulate(first
, last
, Value(0));
232 test_range(first
, last
, n
);
234 // Populate test vector with decreasing values
235 std::reverse(first
, last
);
236 test_range(first
, last
, n
);
238 // Populate test vector with random values
239 do_shuffle(first
, last
);
240 test_range(first
, last
, n
);
243 BOOST_AUTO_TEST_CASE( test_main
)
245 #ifndef BOOST_NO_STDC_NAMESPACE