1
2 //
3 // This source file is part of appleseed.
4 // Visit https://appleseedhq.net/ for additional information and resources.
5 //
6 // This software is released under the MIT license.
7 //
8 // Copyright (c) 2010-2013 Francois Beaune, Jupiter Jazz Limited
9 // Copyright (c) 2014-2018 Francois Beaune, The appleseedhq Organization
10 //
11 // Permission is hereby granted, free of charge, to any person obtaining a copy
12 // of this software and associated documentation files (the "Software"), to deal
13 // in the Software without restriction, including without limitation the rights
14 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15 // copies of the Software, and to permit persons to whom the Software is
16 // furnished to do so, subject to the following conditions:
17 //
18 // The above copyright notice and this permission notice shall be included in
19 // all copies or substantial portions of the Software.
20 //
21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
27 // THE SOFTWARE.
28 //
29
30 // appleseed.foundation headers.
31 #include "foundation/math/permutation.h"
32 #include "foundation/math/rng/mersennetwister.h"
33 #include "foundation/utility/test.h"
34
35 // Standard headers.
36 #include <cstddef>
37 #include <cstdlib>
38 #include <cstring>
39
40 using namespace foundation;
41 using namespace std;
42
TEST_SUITE(Foundation_Math_Permutation)43 TEST_SUITE(Foundation_Math_Permutation)
44 {
45 TEST_CASE(TestIsPermutationOnValidPermutation1)
46 {
47 const size_t Size = 5;
48 const size_t Permutation[Size] = { 0, 1, 2, 3, 4 };
49
50 EXPECT_TRUE(is_permutation(Size, Permutation));
51 }
52
53 TEST_CASE(TestIsPermutationOnValidPermutation2)
54 {
55 const size_t Size = 5;
56 const size_t Permutation[Size] = { 3, 2, 4, 0, 1 };
57
58 EXPECT_TRUE(is_permutation(Size, Permutation));
59 }
60
61 TEST_CASE(TestIsPermutationOnValidPermutation3)
62 {
63 const size_t Size = 5;
64 const size_t Permutation[Size] = { 4, 3, 2, 1, 0 };
65
66 EXPECT_TRUE(is_permutation(Size, Permutation));
67 }
68
69 TEST_CASE(TestIsPermutationOnInvalidPermutation1)
70 {
71 const size_t Size = 5;
72 const size_t Permutation[Size] = { 0, 1, 2, 3, 3 };
73
74 EXPECT_FALSE(is_permutation(Size, Permutation));
75 }
76
77 TEST_CASE(TestIsPermutationOnInvalidPermutation2)
78 {
79 const size_t Size = 5;
80 const size_t Permutation[Size] = { 0, 1, 2, 3, 5 };
81
82 EXPECT_FALSE(is_permutation(Size, Permutation));
83 }
84
85 TEST_CASE(TestIdentityPermutation)
86 {
87 const size_t Size = 5;
88 const size_t Expected[Size] = { 0, 1, 2, 3, 4 };
89
90 size_t perm[Size];
91 identity_permutation(Size, perm);
92
93 EXPECT_ARRAY_EQ(Expected, perm);
94 }
95
96 TEST_CASE(TestRandomPermutation)
97 {
98 const size_t Size = 5;
99
100 size_t perm[Size];
101 MersenneTwister rng;
102 random_permutation(Size, perm, rng);
103
104 EXPECT_TRUE(is_permutation(Size, perm));
105 }
106
107 TEST_CASE(TestReverseQMCPermutationSize1)
108 {
109 const size_t Size = 1;
110 const size_t Expected[Size] = { 0 };
111
112 size_t perm[Size];
113 reverse_qmc_permutation(Size, perm);
114
115 EXPECT_ARRAY_EQ(Expected, perm);
116 }
117
118 TEST_CASE(TestReverseQMCPermutationSize5)
119 {
120 const size_t Size = 5;
121 const size_t Expected[Size] = { 0, 4, 3, 2, 1 };
122
123 size_t perm[Size];
124 reverse_qmc_permutation(Size, perm);
125
126 EXPECT_ARRAY_EQ(Expected, perm);
127 }
128
129 TEST_CASE(TestFaureQMCPermutationSize2)
130 {
131 const size_t Size = 2;
132 const size_t Expected[Size] = { 0, 1 };
133
134 size_t perm[Size];
135 faure_qmc_permutation(Size, perm);
136
137 EXPECT_ARRAY_EQ(Expected, perm);
138 }
139
140 TEST_CASE(TestFaureQMCPermutationSize3)
141 {
142 const size_t Size = 3;
143 const size_t Expected[Size] = { 0, 1, 2 };
144
145 size_t perm[Size];
146 faure_qmc_permutation(Size, perm);
147
148 EXPECT_ARRAY_EQ(Expected, perm);
149 }
150
151 TEST_CASE(TestFaureQMCPermutationSize4)
152 {
153 const size_t Size = 4;
154 const size_t Expected[Size] = { 0, 2, 1, 3 };
155
156 size_t perm[Size];
157 faure_qmc_permutation(Size, perm);
158
159 EXPECT_ARRAY_EQ(Expected, perm);
160 }
161
162 TEST_CASE(TestFaureQMCPermutationSize5)
163 {
164 const size_t Size = 5;
165 const size_t Expected[Size] = { 0, 3, 2, 1, 4 };
166
167 size_t perm[Size];
168 faure_qmc_permutation(Size, perm);
169
170 EXPECT_ARRAY_EQ(Expected, perm);
171 }
172
173 TEST_CASE(TestFaureQMCPermutationSize6)
174 {
175 const size_t Size = 6;
176 const size_t Expected[Size] = { 0, 2, 4, 1, 3, 5 };
177
178 size_t perm[Size];
179 faure_qmc_permutation(Size, perm);
180
181 EXPECT_ARRAY_EQ(Expected, perm);
182 }
183
184 TEST_CASE(TestSmallItemReorder)
185 {
186 const size_t Size = 10;
187 const size_t Order[Size] = { 1, 3, 5, 2, 7, 6, 0, 4, 9, 8 };
188
189 size_t items[Size] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
190
191 size_t temp[Size];
192 small_item_reorder(items, temp, Order, Size);
193
194 EXPECT_ARRAY_EQ(Order, items);
195 }
196
197 TEST_CASE(TestLargeItemReorderFirstVariant)
198 {
199 const size_t Size = 10;
200 const size_t Order[Size] = { 1, 3, 5, 2, 7, 6, 0, 4, 9, 8 };
201
202 size_t items[Size] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
203
204 size_t temp[Size];
205 large_item_reorder(items, temp, Order, Size);
206
207 EXPECT_ARRAY_EQ(Order, items);
208 }
209
210 TEST_CASE(TestLargeItemReorderSecondVariant)
211 {
212 const size_t Size = 10;
213 const size_t Order[Size] = { 1, 3, 5, 2, 7, 6, 0, 4, 9, 8 };
214
215 size_t items[Size] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
216
217 size_t order[Size];
218 memcpy(order, Order, sizeof(Order));
219 large_item_reorder(items, order, Size);
220
221 EXPECT_ARRAY_EQ(Order, items);
222 }
223 }
224