1 /******************************************************************************/
2 /* Copyright (C) 2014 Florent Hivert <Florent.Hivert@lri.fr>, */
3 /* */
4 /* Distributed under the terms of the GNU General Public License (GPL) */
5 /* */
6 /* This code is distributed in the hope that it will be useful, */
7 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
8 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU */
9 /* General Public License for more details. */
10 /* */
11 /* The full text of the GPL is available at: */
12 /* */
13 /* http://www.gnu.org/licenses/ */
14 /******************************************************************************/
15
16 #define BOOST_TEST_MODULE perm_generic
17
18 #include <iomanip>
19 #include <vector>
20
21 #include <boost/functional.hpp>
22 #include <boost/mpl/list.hpp>
23 #include <boost/test/test_case_template.hpp>
24 #include <boost/test/unit_test.hpp>
25
26 //____________________________________________________________________________//
27
28 template <class VectType> struct IsPermFunctions {
is_permIsPermFunctions29 static bool is_perm(const VectType a) { return a.is_permutation(); };
is_perm2IsPermFunctions30 static bool is_perm2(const VectType a, size_t i) {
31 return a.is_permutation(i);
32 };
33 };
34
35 #include "perm16.hpp"
36 #include "perm_generic.hpp"
37
38 //____________________________________________________________________________//
39
40 template <class _PermType>
41 struct Fixture : public IsPermFunctions<typename _PermType::vect> {
42
43 using VectType = typename _PermType::vect;
44 using PermType = _PermType;
45
FixtureFixture46 Fixture()
47 : zero({0}), V01({0, 1}), V10({1, 0}), V11({1, 1}),
48 V1({}, 1), PPa({1, 2, 3, 4, 0, 5}),
49 PPb({1, 2, 3, 6, 0, 5}), czero(zero), cV01(V01),
50 RandPerm({3, 1, 0, 5, 10, 2, 6, 7, 4, 8, 9}),
51 Plist({PPa, PPb, RandPerm}),
52 Vlist({zero, V01, V10, V11, V1, PPa, PPb, RandPerm}) {
53 BOOST_TEST_MESSAGE("setup fixture");
54 }
~FixtureFixture55 ~Fixture() { BOOST_TEST_MESSAGE("teardown fixture"); }
56
57 VectType zero, V01, V10, V11, V1;
58 PermType PPa, PPb;
59 const VectType czero, cV01;
60 const PermType RandPerm;
61 const std::vector<PermType> Plist;
62 const std::vector<VectType> Vlist;
63
lessFixture64 static bool less(const VectType a, const VectType b) { return a < b; };
not_lessFixture65 static bool not_less(const VectType a, const VectType b) {
66 return not(a < b);
67 };
68 };
69
70 //____________________________________________________________________________//
71
72 typedef boost::mpl::list<
73 Fixture<HPCombi::Perm16>,
74 Fixture<HPCombi::PermGeneric<12>>,
75 Fixture<HPCombi::PermGeneric<16>>,
76 Fixture<HPCombi::PermGeneric<32>>,
77 Fixture<HPCombi::PermGeneric<42>>,
78 Fixture<HPCombi::PermGeneric<49>>,
79 Fixture<HPCombi::PermGeneric<350, uint32_t>>>
80 Fixtures;
81
82 //____________________________________________________________________________//
83
84 BOOST_AUTO_TEST_SUITE(VectType_test)
85 //____________________________________________________________________________//
86
BOOST_FIXTURE_TEST_CASE_TEMPLATE(sizeof_test,F,Fixtures,F)87 BOOST_FIXTURE_TEST_CASE_TEMPLATE(sizeof_test, F, Fixtures, F) {
88 BOOST_TEST(sizeof(F::zero) == F::VectType::Size()*sizeof(F::zero[0]));
89 }
90
BOOST_FIXTURE_TEST_CASE_TEMPLATE(equal_test,F,Fixtures,F)91 BOOST_FIXTURE_TEST_CASE_TEMPLATE(equal_test, F, Fixtures, F) {
92 BOOST_TEST(F::zero == F::zero);
93 BOOST_TEST(F::zero != F::V01);
94 for (unsigned i = 0; i < F::Plist.size(); i++)
95 for (unsigned j = 0; j < F::Plist.size(); j++)
96 if (i == j)
97 BOOST_TEST(F::Plist[i] == F::Plist[j]);
98 else
99 BOOST_TEST(F::Plist[i] != F::Plist[j]);
100 }
101
BOOST_FIXTURE_TEST_CASE_TEMPLATE(operator_bracket_const_test,F,Fixtures,F)102 BOOST_FIXTURE_TEST_CASE_TEMPLATE(operator_bracket_const_test, F, Fixtures, F) {
103 BOOST_TEST(F::czero[0] == 0u);
104 BOOST_TEST(F::czero[1] == 0u);
105 BOOST_TEST(F::czero[15] == 0u);
106 BOOST_TEST(F::cV01[0] == 0u);
107 BOOST_TEST(F::cV01[1] == 1u);
108 BOOST_TEST(F::cV01[2] == 0u);
109 }
110
BOOST_FIXTURE_TEST_CASE_TEMPLATE(operator_bracket_test,F,Fixtures,F)111 BOOST_FIXTURE_TEST_CASE_TEMPLATE(operator_bracket_test, F, Fixtures, F) {
112 BOOST_TEST(F::zero[0] == 0u);
113 BOOST_TEST(F::zero[1] == 0u);
114 BOOST_TEST(F::zero[15] == 0u);
115 BOOST_TEST(F::V01[0] == 0u);
116 BOOST_TEST(F::V01[1] == 1u);
117 BOOST_TEST(F::V01[2] == 0u);
118 BOOST_TEST(F::PPa[4] == 0u);
119 BOOST_TEST(F::PPa[5] == 5u);
120 F::zero[0] = 3;
121 BOOST_TEST(F::zero[0] == 3u);
122 BOOST_TEST(F::zero[1] == 0u);
123 BOOST_TEST(F::zero[15] == 0u);
124 F::PPa[2] = 0;
125 BOOST_TEST(F::PPa[1] == 2u);
126 BOOST_TEST(F::PPa[2] == 0u);
127 BOOST_TEST(F::PPa[3] == 4u);
128 }
129
BOOST_FIXTURE_TEST_CASE_TEMPLATE(operator_less_test,F,Fixtures,F)130 BOOST_FIXTURE_TEST_CASE_TEMPLATE(operator_less_test, F, Fixtures, F) {
131 for (unsigned i = 0; i < F::Plist.size(); i++)
132 for (unsigned j = 0; j < F::Plist.size(); j++)
133 if (i < j)
134 BOOST_CHECK_PREDICATE(F::less, (F::Plist[i])(F::Plist[j]));
135 else
136 BOOST_CHECK_PREDICATE(F::not_less, (F::Plist[i])(F::Plist[j]));
137 }
138
BOOST_FIXTURE_TEST_CASE_TEMPLATE(operator_less_partial_test,F,Fixtures,F)139 BOOST_FIXTURE_TEST_CASE_TEMPLATE(operator_less_partial_test, F, Fixtures, F) {
140 for (auto p : F::Plist)
141 for (unsigned k = 0; k < F::PermType::size(); k++)
142 BOOST_TEST(p.less_partial(p, k) == 0);
143 for (auto p : F::Plist)
144 for (auto q : F::Plist)
145 BOOST_TEST(p.less_partial(q, 0) == 0);
146
147 BOOST_TEST(F::zero.less_partial(F::V01, 1) == 0);
148 BOOST_TEST(F::V01.less_partial(F::zero, 1) == 0);
149 BOOST_TEST(F::zero.less_partial(F::V01, 2) < 0);
150 BOOST_TEST(F::V01.less_partial(F::zero, 2) > 0);
151
152 BOOST_TEST(F::zero.less_partial(F::V10, 1) < 0);
153 BOOST_TEST(F::zero.less_partial(F::V10, 2) < 0);
154 BOOST_TEST(F::V10.less_partial(F::zero, 1) > 0);
155 BOOST_TEST(F::V10.less_partial(F::zero, 2) > 0);
156
157 BOOST_TEST(F::PPa.less_partial(F::PPb, 1) == 0);
158 BOOST_TEST(F::PPa.less_partial(F::PPb, 2) == 0);
159 BOOST_TEST(F::PPa.less_partial(F::PPb, 3) == 0);
160 BOOST_TEST(F::PPa.less_partial(F::PPb, 4) < 0);
161 BOOST_TEST(F::PPa.less_partial(F::PPb, 5) < 0);
162 BOOST_TEST(F::PPb.less_partial(F::PPa, 4) > 0);
163 BOOST_TEST(F::PPb.less_partial(F::PPa, 5) > 0);
164 }
165
166
BOOST_FIXTURE_TEST_CASE_TEMPLATE(first_zero_test,F,Fixtures,F)167 BOOST_FIXTURE_TEST_CASE_TEMPLATE(first_zero_test, F, Fixtures, F) {
168 BOOST_TEST(F::zero.first_zero() == 0u);
169 BOOST_TEST(F::V01.first_zero() == 0u);
170 BOOST_TEST(F::PPa.first_zero() == 4u);
171 BOOST_TEST(F::V10.first_zero() == 1u);
172 BOOST_TEST(F::V1.first_zero() == F::VectType::Size());
173 BOOST_TEST(F::V10.first_zero(1) == F::VectType::Size());
174 BOOST_TEST(F::PPa.first_zero(5) == 4u);
175 BOOST_TEST(F::PPa.first_zero(3) == F::VectType::Size());
176 }
177
BOOST_FIXTURE_TEST_CASE_TEMPLATE(last_zero_test,F,Fixtures,F)178 BOOST_FIXTURE_TEST_CASE_TEMPLATE(last_zero_test, F, Fixtures, F) {
179 BOOST_TEST(F::zero.last_zero() == F::VectType::Size() - 1);
180 BOOST_TEST(F::V01.last_zero() == F::VectType::Size() - 1);
181 BOOST_TEST(F::PPa.last_zero() == 4u);
182 BOOST_TEST(F::V1.last_zero() == F::VectType::Size());
183 BOOST_TEST(F::V01.last_zero(1) == 0u);
184 BOOST_TEST(F::V10.last_zero(1) == F::VectType::Size());
185 BOOST_TEST(F::PPa.last_zero(5) == 4u);
186 BOOST_TEST(F::PPa.last_zero(3) == F::VectType::Size());
187 }
188
BOOST_FIXTURE_TEST_CASE_TEMPLATE(first_non_zero_test,F,Fixtures,F)189 BOOST_FIXTURE_TEST_CASE_TEMPLATE(first_non_zero_test, F, Fixtures, F) {
190 BOOST_TEST(F::zero.first_non_zero() == F::VectType::Size());
191 BOOST_TEST(F::V01.first_non_zero() == 1u);
192 BOOST_TEST(F::PPa.first_non_zero() == 0u);
193 BOOST_TEST(F::V01.first_non_zero() == 1u);
194 BOOST_TEST(F::V01.first_non_zero(1) == F::VectType::Size());
195 BOOST_TEST(F::PPa.first_non_zero(5) == 0u);
196 BOOST_TEST(F::PPa.first_non_zero(3) == 0u);
197 }
198
BOOST_FIXTURE_TEST_CASE_TEMPLATE(last_non_zero_test,F,Fixtures,F)199 BOOST_FIXTURE_TEST_CASE_TEMPLATE(last_non_zero_test, F, Fixtures, F) {
200 BOOST_TEST(F::zero.last_non_zero() == F::VectType::Size());
201 BOOST_TEST(F::V01.last_non_zero() == 1u);
202 BOOST_TEST(F::PPa.last_non_zero() == F::VectType::Size() - 1);
203 BOOST_TEST(F::V01.last_non_zero() == 1u);
204 BOOST_TEST(F::V01.last_non_zero(1) == F::VectType::Size());
205 BOOST_TEST(F::PPa.last_non_zero(5) == 3u);
206 BOOST_TEST(F::PPa.last_non_zero(3) == 2u);
207 }
208
BOOST_FIXTURE_TEST_CASE_TEMPLATE(permuted_test,F,Fixtures,F)209 BOOST_FIXTURE_TEST_CASE_TEMPLATE(permuted_test, F, Fixtures, F) {
210 BOOST_TEST(F::zero.permuted(F::zero) == F::zero);
211 BOOST_TEST(F::V01.permuted(F::V01) == F::V01);
212 BOOST_TEST(F::V10.permuted(F::V10) == typename F::VectType({0, 1}, 1));
213 BOOST_TEST(F::V10.permuted(F::V01) == typename F::VectType({1, 0}, 1));
214 BOOST_TEST(F::V01.permuted(F::V10) == F::V10);
215 }
216
BOOST_FIXTURE_TEST_CASE_TEMPLATE(operator_insert_test,F,Fixtures,F)217 BOOST_FIXTURE_TEST_CASE_TEMPLATE(operator_insert_test, F, Fixtures, F) {
218 std::ostringstream out, out2;
219 out << F::zero;
220 out2 << "[ 0";
221 for (size_t i = 1; i < F::VectType::Size(); i++)
222 out2 << ", 0";
223 out2 << "]";
224 BOOST_TEST(out.str() == out2.str());
225
226 out.str("");
227 out2.str("");
228 out << F::V01;
229 out2 << "[ 0, 1";
230 for (size_t i = 2; i < F::VectType::Size(); i++)
231 out2 << ", 0";
232 out2 << "]";
233 BOOST_TEST(out.str() == out2.str());
234
235 out.str("");
236 out2.str("");
237 out << F::PPa;
238 out2 << "[ 1, 2, 3, 4, 0";
239 for (size_t i = 5; i < F::VectType::Size(); i++)
240 out2 << "," << std::setw(2) << i;
241 out2 << "]";
242 BOOST_TEST(out.str() == out2.str());
243 }
244
BOOST_FIXTURE_TEST_CASE_TEMPLATE(is_permutation_test,F,Fixtures,F)245 BOOST_FIXTURE_TEST_CASE_TEMPLATE(is_permutation_test, F, Fixtures, F) {
246 BOOST_CHECK_PREDICATE(boost::not1(F::is_perm), (F::zero));
247 BOOST_CHECK_PREDICATE(F::is_perm, (F::PPa));
248 BOOST_CHECK_PREDICATE(boost::not1(F::is_perm), (F::PPb));
249 BOOST_CHECK_PREDICATE(F::is_perm, (F::RandPerm));
250 BOOST_CHECK_PREDICATE(
251 boost::not1(F::is_perm),
252 (typename F::VectType({3, 1, 0, 9, 3, 10, 2, 11, 6, 7, 4, 8})));
253 BOOST_CHECK_PREDICATE(F::is_perm2, (F::PPa)(16));
254 BOOST_CHECK_PREDICATE(boost::not2(F::is_perm2), (F::RandPerm)(4));
255 BOOST_CHECK_PREDICATE(F::is_perm2, (F::PPa)(5));
256 BOOST_CHECK_PREDICATE(boost::not2(F::is_perm2), (F::PPa)(4));
257 }
258
259 BOOST_AUTO_TEST_SUITE_END()
260
261 //____________________________________________________________________________//
262 //____________________________________________________________________________//
263
264 template <class _Perm> struct PermFixture : public IsPermFunctions<_Perm> {
265 using PermType = _Perm;
PermFixturePermFixture266 PermFixture()
267 : id(PermType::one()), RandPerm({3, 1, 0, 5, 10, 2, 11, 6, 7, 4, 8, 9}),
268 Plist({id, RandPerm}) {
269 for (uint64_t i = 0; i < std::min<size_t>(PermType::size(), 30) - 1; i++)
270 Plist.push_back(PermType::elementary_transposition(i));
271 for (uint64_t i = std::max<size_t>(30, PermType::size() - 20);
272 i < PermType::size() - 1; i++)
273 Plist.push_back(PermType::elementary_transposition(i));
274 for (uint64_t i = 0; i < 10; i++)
275 Plist.push_back(PermType::random());
276 BOOST_TEST_MESSAGE("setup fixture");
277 }
278
~PermFixturePermFixture279 ~PermFixture() { BOOST_TEST_MESSAGE("teardown fixture"); }
280
281 PermType id, s1, s2, s3;
282 const PermType RandPerm;
283 std::vector<PermType> Plist;
284 };
285
286 //____________________________________________________________________________//
287
288 typedef boost::mpl::list<
289 PermFixture<HPCombi::Perm16>,
290 PermFixture<HPCombi::PermGeneric<12>>,
291 PermFixture<HPCombi::PermGeneric<16>>,
292 PermFixture<HPCombi::PermGeneric<32>>,
293 PermFixture<HPCombi::PermGeneric<42>>,
294 PermFixture<HPCombi::PermGeneric<49>>,
295 PermFixture<HPCombi::PermGeneric<350, uint32_t>>>
296 PermFixtures;
297
298 //____________________________________________________________________________//
299
300 BOOST_AUTO_TEST_SUITE(PermType_test)
301 //____________________________________________________________________________//
302
BOOST_FIXTURE_TEST_CASE_TEMPLATE(constructor_is_permutation_test,F,PermFixtures,F)303 BOOST_FIXTURE_TEST_CASE_TEMPLATE(constructor_is_permutation_test, F,
304 PermFixtures, F) {
305 for (auto x : F::Plist)
306 BOOST_CHECK_PREDICATE(F::is_perm, (x));
307
308 // Default constructor doesn't initialize
309 // BOOST_CHECK_PREDICATE(F::is_perm, (typename F::PermType()));
310 BOOST_CHECK_PREDICATE(F::is_perm, (typename F::PermType({})));
311 BOOST_CHECK_PREDICATE(F::is_perm, (typename F::PermType({1, 0})));
312 BOOST_CHECK_PREDICATE(F::is_perm, (typename F::PermType({1, 2, 0})));
313 BOOST_CHECK_PREDICATE(boost::not1(F::is_perm),
314 (typename F::PermType({1, 2})));
315 }
316
BOOST_FIXTURE_TEST_CASE_TEMPLATE(std_hash_test,F,PermFixtures,F)317 BOOST_FIXTURE_TEST_CASE_TEMPLATE(std_hash_test, F, PermFixtures, F) {
318 for (auto x : F::Plist)
319 BOOST_TEST(std::hash<typename F::PermType>()(x) != 0);
320 }
321
BOOST_FIXTURE_TEST_CASE_TEMPLATE(mult_coxeter_test,F,PermFixtures,F)322 BOOST_FIXTURE_TEST_CASE_TEMPLATE(mult_coxeter_test, F, PermFixtures, F) {
323 for (uint64_t i = 0; i < F::PermType::Size() - 1; i++) {
324 auto si = F::PermType::elementary_transposition(i);
325 BOOST_TEST(si != F::id);
326 BOOST_TEST(si * si == F::id);
327 if (i + 1 < F::PermType::Size() - 1) {
328 auto si1 = F::PermType::elementary_transposition(i + 1);
329 BOOST_TEST(si * si1 * si == si1 * si * si1);
330 }
331 for (uint64_t j = i + 2; j < F::PermType::Size() - 1; j++) {
332 auto sj = F::PermType::elementary_transposition(j);
333 BOOST_TEST(sj * si == si * sj);
334 }
335 }
336 }
337
BOOST_FIXTURE_TEST_CASE_TEMPLATE(mult_test,F,PermFixtures,F)338 BOOST_FIXTURE_TEST_CASE_TEMPLATE(mult_test, F, PermFixtures, F) {
339 for (auto x : F::Plist) {
340 BOOST_TEST(F::id * x == x);
341 BOOST_TEST(x * F::id == x);
342 }
343 BOOST_TEST(F::RandPerm * F::RandPerm ==
344 typename F::PermType({5, 1, 3, 2, 8, 0, 9, 11, 6, 10, 7, 4}));
345
346 for (auto x : F::Plist)
347 for (auto y : F::Plist)
348 for (auto z : F::Plist)
349 BOOST_TEST((x * y) * z == x * (y * z));
350 }
351
BOOST_FIXTURE_TEST_CASE_TEMPLATE(inverse_test,F,PermFixtures,F)352 BOOST_FIXTURE_TEST_CASE_TEMPLATE(inverse_test, F, PermFixtures, F) {
353 for (auto x : F::Plist) {
354 BOOST_TEST(x.inverse() * x == F::id);
355 BOOST_TEST(x * x.inverse() == F::id);
356 BOOST_TEST(x.inverse().inverse() == x);
357 }
358 }
359
BOOST_FIXTURE_TEST_CASE_TEMPLATE(random_test,F,PermFixtures,F)360 BOOST_FIXTURE_TEST_CASE_TEMPLATE(random_test, F, PermFixtures, F) {
361 for (int i = 0; i < 100; i++) {
362 BOOST_CHECK_PREDICATE(F::is_perm, (F::PermType::random()));
363 }
364 }
365
366 BOOST_AUTO_TEST_SUITE_END()
367