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)
5 //
6 //
7 // For more information, see http://www.boost.org/libs/range/
8 //
9 #include <boost/range/algorithm/random_shuffle.hpp>
10
11 #include <boost/test/test_tools.hpp>
12 #include <boost/test/unit_test.hpp>
13
14 #include <boost/assign.hpp>
15 #include "../test_function/counted_function.hpp"
16 #include <algorithm>
17 #include <functional>
18 #include <list>
19 #include <numeric>
20 #include <deque>
21 #include <vector>
22
23 namespace boost
24 {
25 namespace
26 {
27 template<class Int>
28 class counted_generator
29 : private range_test_function::counted_function
30 {
31 public:
32 typedef Int result_type;
33 typedef Int argument_type;
34
35 using range_test_function::counted_function::invocation_count;
36
operator ()(argument_type modulo_value)37 result_type operator()(argument_type modulo_value)
38 {
39 invoked();
40 return static_cast<result_type>(std::rand() % modulo_value);
41 }
42 };
43
44 template<class Container>
test_shuffle_result(const Container & old_cont,const Container & new_cont)45 bool test_shuffle_result(
46 const Container& old_cont,
47 const Container& new_cont
48 )
49 {
50 typedef BOOST_DEDUCED_TYPENAME range_iterator<const Container>::type iterator_t;
51
52 // The size must remain equal
53 BOOST_CHECK_EQUAL( old_cont.size(), new_cont.size() );
54 if (old_cont.size() != new_cont.size())
55 return false;
56
57 if (new_cont.size() < 2)
58 {
59 BOOST_CHECK_EQUAL_COLLECTIONS(
60 old_cont.begin(), old_cont.end(),
61 new_cont.begin(), new_cont.end()
62 );
63
64 return std::equal(old_cont.begin(), old_cont.end(),
65 new_cont.begin());
66 }
67
68 // Elements must only be moved around. This is tested by
69 // ensuring the count of each element remains the
70 // same.
71 bool failed = false;
72 iterator_t last = old_cont.end();
73 for (iterator_t it = old_cont.begin(); !failed && (it != last); ++it)
74 {
75 const std::size_t old_count
76 = std::count(old_cont.begin(), old_cont.end(), *it);
77
78 const std::size_t new_count
79 = std::count(new_cont.begin(), new_cont.end(), *it);
80
81 BOOST_CHECK_EQUAL( old_count, new_count );
82
83 failed = (old_count != new_count);
84 }
85
86 return !failed;
87 }
88
89 template<class Container>
test_random_shuffle_nogen_impl(Container & cont)90 void test_random_shuffle_nogen_impl(Container& cont)
91 {
92 typedef BOOST_DEDUCED_TYPENAME range_iterator<Container>::type
93 iterator_t BOOST_RANGE_UNUSED;
94
95 const int MAX_RETRIES = 10000;
96
97 bool shuffled = false;
98 for (int attempt = 0; !shuffled && (attempt < MAX_RETRIES); ++attempt)
99 {
100 Container test(cont);
101 boost::random_shuffle(test);
102 bool ok = test_shuffle_result(cont, test);
103 if (!ok)
104 break;
105
106 // Since the counts are equal, then if they are
107 // not equal the contents must have been shuffled
108 if (cont.size() == test.size()
109 && !std::equal(cont.begin(), cont.end(), test.begin()))
110 {
111 shuffled = true;
112 }
113
114 // Verify that the shuffle can be performed on a
115 // temporary range
116 Container test2(cont);
117 boost::random_shuffle(boost::make_iterator_range(test2));
118 ok = test_shuffle_result(cont, test2);
119 if (!ok)
120 break;
121 }
122 }
123
124 template<class RandomGenerator, class Container>
test_random_shuffle_gen_impl(Container & cont)125 void test_random_shuffle_gen_impl(Container& cont)
126 {
127 RandomGenerator gen;
128 Container old_cont(cont);
129 boost::random_shuffle(cont, gen);
130 test_shuffle_result(cont, old_cont);
131 if (cont.size() > 2)
132 {
133 BOOST_CHECK( gen.invocation_count() > 0 );
134 }
135
136 // Test that random shuffle works when
137 // passed a temporary range
138 RandomGenerator gen2;
139 Container cont2(old_cont);
140 boost::random_shuffle(boost::make_iterator_range(cont2), gen2);
141 test_shuffle_result(cont2, old_cont);
142 if (cont2.size() > 2)
143 {
144 BOOST_CHECK( gen2.invocation_count() > 0 );
145 }
146 }
147
148 template<class Container>
test_random_shuffle_impl(Container & cont)149 void test_random_shuffle_impl(Container& cont)
150 {
151 Container old_cont(cont);
152 boost::random_shuffle(cont);
153 test_shuffle_result(cont, old_cont);
154 }
155
156 template<class Container>
test_random_shuffle_impl()157 void test_random_shuffle_impl()
158 {
159 using namespace boost::assign;
160
161 typedef counted_generator<
162 BOOST_DEDUCED_TYPENAME range_difference<Container>::type > generator_t;
163
164 Container cont;
165 test_random_shuffle_nogen_impl(cont);
166 test_random_shuffle_gen_impl<generator_t>(cont);
167
168 cont.clear();
169 cont += 1;
170 test_random_shuffle_nogen_impl(cont);
171 test_random_shuffle_gen_impl<generator_t>(cont);
172
173 cont.clear();
174 cont += 1,2,3,4,5,6,7,8,9;
175 test_random_shuffle_nogen_impl(cont);
176 test_random_shuffle_gen_impl<generator_t>(cont);
177 }
178
test_random_shuffle()179 void test_random_shuffle()
180 {
181 test_random_shuffle_impl< std::vector<int> >();
182 test_random_shuffle_impl< std::deque<int> >();
183 }
184 }
185 }
186
187
188 boost::unit_test::test_suite*
init_unit_test_suite(int argc,char * argv[])189 init_unit_test_suite(int argc, char* argv[])
190 {
191 boost::unit_test::test_suite* test
192 = BOOST_TEST_SUITE( "RangeTestSuite.algorithm.random_shuffle" );
193
194 test->add( BOOST_TEST_CASE( &boost::test_random_shuffle ) );
195
196 return test;
197 }
198