1 // Copyright Neil Groves 2009. Use, modification and
2 // distribution is subject to the Boost Software License, Version
3 // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
7 // For more information, see http://www.boost.org/libs/range/
9 #include <boost/range/algorithm/random_shuffle.hpp>
11 #include <boost/test/test_tools.hpp>
12 #include <boost/test/unit_test.hpp>
14 #include <boost/assign.hpp>
15 #include <boost/bind.hpp>
16 #include "../test_function/counted_function.hpp"
29 class counted_generator
30 : private range_test_function::counted_function
33 typedef Int result_type
;
34 typedef Int argument_type
;
36 using range_test_function::counted_function::invocation_count
;
38 result_type
operator()(argument_type modulo_value
)
41 return static_cast<result_type
>(std::rand() % modulo_value
);
45 template<class Container
>
46 bool test_shuffle_result(
47 const Container
& old_cont
,
48 const Container
& new_cont
51 typedef BOOST_DEDUCED_TYPENAME range_iterator
<const Container
>::type iterator_t
;
53 // The size must remain equal
54 BOOST_CHECK_EQUAL( old_cont
.size(), new_cont
.size() );
55 if (old_cont
.size() != new_cont
.size())
58 if (new_cont
.size() < 2)
60 BOOST_CHECK_EQUAL_COLLECTIONS(
61 old_cont
.begin(), old_cont
.end(),
62 new_cont
.begin(), new_cont
.end()
65 return std::equal(old_cont
.begin(), old_cont
.end(),
69 // Elements must only be moved around. This is tested by
70 // ensuring the count of each element remains the
73 iterator_t last
= old_cont
.end();
74 for (iterator_t it
= old_cont
.begin(); !failed
&& (it
!= last
); ++it
)
76 const std::size_t old_count
77 = std::count(old_cont
.begin(), old_cont
.end(), *it
);
79 const std::size_t new_count
80 = std::count(new_cont
.begin(), new_cont
.end(), *it
);
82 BOOST_CHECK_EQUAL( old_count
, new_count
);
84 failed
= (old_count
!= new_count
);
90 template<class Container
>
91 void test_random_shuffle_nogen_impl(Container
& cont
)
93 typedef BOOST_DEDUCED_TYPENAME range_iterator
<Container
>::type
94 iterator_t BOOST_RANGE_UNUSED
;
96 const int MAX_RETRIES
= 10000;
98 bool shuffled
= false;
99 for (int attempt
= 0; !shuffled
&& (attempt
< MAX_RETRIES
); ++attempt
)
101 Container
test(cont
);
102 boost::random_shuffle(test
);
103 bool ok
= test_shuffle_result(cont
, test
);
107 // Since the counts are equal, then if they are
108 // not equal the contents must have been shuffled
109 if (cont
.size() == test
.size()
110 && !std::equal(cont
.begin(), cont
.end(), test
.begin()))
115 // Verify that the shuffle can be performed on a
117 Container
test2(cont
);
118 boost::random_shuffle(boost::make_iterator_range(test2
));
119 ok
= test_shuffle_result(cont
, test2
);
125 template<class RandomGenerator
, class Container
>
126 void test_random_shuffle_gen_impl(Container
& cont
)
129 Container
old_cont(cont
);
130 boost::random_shuffle(cont
, gen
);
131 test_shuffle_result(cont
, old_cont
);
134 BOOST_CHECK( gen
.invocation_count() > 0 );
137 // Test that random shuffle works when
138 // passed a temporary range
139 RandomGenerator gen2
;
140 Container
cont2(old_cont
);
141 boost::random_shuffle(boost::make_iterator_range(cont2
), gen2
);
142 test_shuffle_result(cont2
, old_cont
);
143 if (cont2
.size() > 2)
145 BOOST_CHECK( gen2
.invocation_count() > 0 );
149 template<class Container
>
150 void test_random_shuffle_impl(Container
& cont
)
152 Container
old_cont(cont
);
153 boost::random_shuffle(cont
);
154 test_shuffle_result(cont
, old_cont
);
157 template<class Container
>
158 void test_random_shuffle_impl()
160 using namespace boost::assign
;
162 typedef counted_generator
<
163 BOOST_DEDUCED_TYPENAME range_difference
<Container
>::type
> generator_t
;
166 test_random_shuffle_nogen_impl(cont
);
167 test_random_shuffle_gen_impl
<generator_t
>(cont
);
171 test_random_shuffle_nogen_impl(cont
);
172 test_random_shuffle_gen_impl
<generator_t
>(cont
);
175 cont
+= 1,2,3,4,5,6,7,8,9;
176 test_random_shuffle_nogen_impl(cont
);
177 test_random_shuffle_gen_impl
<generator_t
>(cont
);
180 void test_random_shuffle()
182 test_random_shuffle_impl
< std::vector
<int> >();
183 test_random_shuffle_impl
< std::deque
<int> >();
189 boost::unit_test::test_suite
*
190 init_unit_test_suite(int argc
, char* argv
[])
192 boost::unit_test::test_suite
* test
193 = BOOST_TEST_SUITE( "RangeTestSuite.algorithm.random_shuffle" );
195 test
->add( BOOST_TEST_CASE( &boost::test_random_shuffle
) );