Frobby 0.9.5
RawSquareFreeIdealTest.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2010 University of Aarhus
3 Contact Bjarke Hammersholt Roune for license information (www.broune.com)
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see http://www.gnu.org/licenses/.
17*/
18#include "stdinc.h"
19#include "RawSquareFreeIdeal.h"
20#include "tests.h"
21
22#include "RawSquareFreeTerm.h"
23
24using namespace SquareFreeTermOps;
25
27
29
30namespace {
31 bool sortedEqual(const RawSquareFreeIdeal& a, const RawSquareFreeIdeal& b) {
34 aCopy->sortLexAscending();
35 bCopy->sortLexAscending();
36 bool equal = (*aCopy == *bCopy);
39 return equal;
40 }
41}
42
43TEST(RawSquareFreeIdeal, Insert_Term) {
44 const size_t varCount = 5;
45 Word* a = newTermParse("11111");
46 Word* b = newTermParse("00000");
47 Word* c = newTermParse("10101");
48
49 RSFIdeal* ideal = newRawSquareFreeIdeal(5, 3);
50 ASSERT_TRUE(ideal->getGeneratorCount() == 0);
51 ideal->insert(a);
52 ideal->insert(b);
53 ideal->insert(c);
54
55 ASSERT_TRUE(ideal->getGeneratorCount() == 3);
56 ASSERT_TRUE(equals(ideal->getGenerator(0), a, varCount));
57 ASSERT_TRUE(equals(ideal->getGenerator(1), b, varCount));
58 ASSERT_TRUE(equals(ideal->getGenerator(2), c, varCount));
59
61 deleteTerm(a);
62 deleteTerm(b);
63 deleteTerm(c);
64}
65
66TEST(RawSquareFreeIdeal, NewIdealParse) {
67 const size_t varCount = 5;
68 Word* a = newTermParse("11111");
69 Word* b = newTermParse("00000");
70
71 RSFIdeal* ideal = newRawSquareFreeIdealParse("11111\n00000\n");
72 ASSERT_TRUE(ideal->getGeneratorCount() == 2);
73 ASSERT_TRUE(equals(ideal->getGenerator(0), a, varCount));
74 ASSERT_TRUE(equals(ideal->getGenerator(1), b, varCount));
75
77 deleteTerm(a);
78 deleteTerm(b);
79}
80
82 vector<RawSquareFreeIdeal*> ideals;
83 ideals.push_back
85 ("000\n"
86 "001\n"
87 "010\n"
88 "011\n"
89 "100\n"
90 "101\n"
91 "110\n"
92 "111\n"));
93 ideals.push_back
95 ("001\n"
96 "000\n"
97 "010\n"
98 "011\n"
99 "100\n"
100 "101\n"
101 "110\n"
102 "111\n"));
103 ideals.push_back(newRawSquareFreeIdealParse("1"));
104 ideals.push_back(newRawSquareFreeIdealParse("0"));
105 ideals.push_back(newRawSquareFreeIdealParse(""));
106
107 for (size_t i = 0; i < ideals.size(); ++i) {
108 for (size_t j = 0; j < ideals.size(); ++j) {
109 if (i == j)
110 ASSERT_EQ(*ideals[i], *ideals[j]);
111 else
112 ASSERT_NEQ(*ideals[i], *ideals[j]);
113 }
114 }
115
116 for (size_t i = 0; i < ideals.size(); ++i)
117 deleteRawSquareFreeIdeal(ideals[i]);
118}
119
120TEST(RawSquareFreeIdeal, SortLexAscending) {
122 ("000\n"
123 "001\n"
124 "010\n"
125 "011\n"
126 "100\n"
127 "101\n"
128 "110\n"
129 "111\n");
131 ("111\n"
132 "000\n"
133 "101\n"
134 "011\n"
135 "100\n"
136 "001\n"
137 "110\n"
138 "010\n");
139 shuffled->sortLexAscending();
140 ASSERT_EQ(*sorted, *shuffled);
141
143 deleteRawSquareFreeIdeal(shuffled);
144}
145
146#define TEST_MINIMIZE(idealStr, minimizedStr) { \
147 RSFIdeal* ideal = newRawSquareFreeIdealParse(idealStr); \
148 RSFIdeal* minimized = newRawSquareFreeIdealParse(minimizedStr); \
149 ASSERT_FALSE(ideal->isMinimallyGenerated()); \
150 ideal->minimize(); \
151 ASSERT_TRUE(sortedEqual(*ideal, *minimized)); \
152 ASSERT_TRUE(ideal->isMinimallyGenerated()); \
153 ideal->minimize(); \
154 ASSERT_TRUE(sortedEqual(*ideal, *minimized)); \
155 deleteRawSquareFreeIdeal(ideal); \
156 deleteRawSquareFreeIdeal(minimized); \
157 }
158
159TEST(RawSquareFreeIdeal, MinimizeAndMinimizable) {
160 TEST_MINIMIZE("000\n000\n000\n001\n001\n001\n001", "000");
161 TEST_MINIMIZE("111\n111\n111\n111\n111\n111", "111");
162 TEST_MINIMIZE("0\n1", "0");
163 TEST_MINIMIZE("1\n0", "0");
165 ("111111111111111111110000000000000000000000011111111111111111111111101\n"
166 "111111111111111111111111111111111111111111111111111111111111111111111\n"
167 "000000000000000000000000000000000000000000000000000000000000000000010\n",
168 "111111111111111111110000000000000000000000011111111111111111111111101\n"
169 "000000000000000000000000000000000000000000000000000000000000000000010\n");
171 ("1001\n"
172 "1010\n"
173 "1100\n"
174 "0101\n"
175 "0100\n"
176 "0001\n"
177 "0110\n"
178 "0011\n",
179 "1010\n"
180 "0100\n"
181 "0001\n");
182}
183
184#define TEST_COLON_REMINIMIZE_TERM(idealStr, colonStr, minimizedStr) { \
185 RSFIdeal* ideal = newRawSquareFreeIdealParse(idealStr); \
186 Word* colon = newTermParse(colonStr); \
187 RSFIdeal* minimized = newRawSquareFreeIdealParse(minimizedStr); \
188 ideal->colonReminimize(colon); \
189 ASSERT_TRUE2(sortedEqual(*ideal, *minimized), *ideal, *minimized); \
190 ASSERT_TRUE(ideal->isMinimallyGenerated()); \
191 deleteRawSquareFreeIdeal(ideal); \
192 deleteTerm(colon); \
193 deleteRawSquareFreeIdeal(minimized); \
194 }
195
196#define TEST_COLON_REMINIMIZE_VAR(idealStr, colonVar, minimizedStr) { \
197 RSFIdeal* idealVar = newRawSquareFreeIdealParse(idealStr); \
198 RSFIdeal* idealTerm = newRawSquareFreeIdealParse(idealStr); \
199 Word* colon = newTerm(idealTerm->getVarCount()); \
200 setExponent(colon, colonVar, 1); \
201 RSFIdeal* minimized = newRawSquareFreeIdealParse(minimizedStr); \
202 idealVar->colonReminimize((size_t)colonVar); \
203 ASSERT_TRUE2(sortedEqual(*idealVar, *minimized), *idealVar, *minimized); \
204 idealTerm->colonReminimize(colon); \
205 ASSERT_TRUE2(sortedEqual(*idealTerm, *minimized), *idealVar, *minimized); \
206 deleteRawSquareFreeIdeal(idealVar); \
207 deleteRawSquareFreeIdeal(idealTerm); \
208 deleteTerm(colon); \
209 deleteRawSquareFreeIdeal(minimized); \
210 }
211
212TEST(RawSquareFreeIdeal, ColonReminimizeMinimize_VarAndTerm) {
213 TEST_COLON_REMINIMIZE_VAR("0", 0, "0");
214 TEST_COLON_REMINIMIZE_VAR("1", 0, "0");
215 TEST_COLON_REMINIMIZE_VAR("111", 1, "101");
216 TEST_COLON_REMINIMIZE_VAR("101\n110", 1, "100");
217 TEST_COLON_REMINIMIZE_VAR("110\n101\n011", 2, "100\n010");
218 TEST_COLON_REMINIMIZE_VAR("1100\n1010\n0110", 3, "1100\n1010\n0110");
219 TEST_COLON_REMINIMIZE_VAR("1101\n1011\n0111", 3, "1100\n1010\n0110");
221 ("011111111111111111110000000000000000000000011111111111111111111111101\n"
222 "011111111111111111111111111111111111111111111011111111111111111111101\n"
223 "000000000000000000000000000000000000000000000100000000000000000000010\n", 67,
224 "011111111111111111111111111111111111111111111011111111111111111111101\n"
225 "000000000000000000000000000000000000000000000100000000000000000000000\n");
227 ("100000000000000\n"
228 "010000000000000\n"
229 "001000000000000\n"
230 "000100000000000\n"
231 "000010000000000\n"
232 "000001000000000\n"
233 "000000100000000\n"
234 "000000010000000\n"
235 "000000001000000\n"
236 "000000000100000\n"
237 "000000000010000\n"
238 "000000000001000\n"
239 "000000000000100\n"
240 "000000000000010\n"
241 "000000000000001\n", 0,
242 "000000000000000\n");
243
244
245 TEST_COLON_REMINIMIZE_TERM("", "", "");
246 TEST_COLON_REMINIMIZE_TERM("0", "0", "0");
247 TEST_COLON_REMINIMIZE_TERM("0", "1", "0");
248 TEST_COLON_REMINIMIZE_TERM("1", "0", "1");
249 TEST_COLON_REMINIMIZE_TERM("1", "1", "0");
250 TEST_COLON_REMINIMIZE_TERM("111", "001", "110");
251 TEST_COLON_REMINIMIZE_TERM("111", "110", "001");
252 TEST_COLON_REMINIMIZE_TERM("1101\n1110", "1001", "0100");
253 TEST_COLON_REMINIMIZE_TERM("1101\n1011\n0110", "0011", "1000\n0100");
254 TEST_COLON_REMINIMIZE_TERM("11000\n10100\n01100", "00011",
255 "11000\n10100\n01100");
256 TEST_COLON_REMINIMIZE_TERM("11011\n10111\n01111", "00011",
257 "11000\n10100\n01100");
259 ("011111111111111111110000000000000000000000011111111111111111111111101\n"
260 "011111111111111111111111111111111111111111111011111111111111111111101\n"
261 "100000000000000000000000000000000000000000000100000000000000000000010\n",
262 "100000000000000000000000000000000000000000000000000000100000000000010",
263 "011111111111111111111111111111111111111111111011111111011111111111101\n"
264 "000000000000000000000000000000000000000000000100000000000000000000000\n");
266 ("100000000000000\n"
267 "010000000000000\n"
268 "001000000000000\n"
269 "000100000000000\n"
270 "000010000000000\n"
271 "000001000000000\n"
272 "000000100000000\n"
273 "000000010000000\n"
274 "000000001000000\n"
275 "000000000100000\n"
276 "000000000010000\n"
277 "000000000001000\n"
278 "000000000000100\n"
279 "000000000000010\n"
280 "000000000000001\n",
281 "100000000000001",
282 "000000000000000\n");
283}
284
285TEST(RawSquareFreeIdeal, GetVarDividesCounts) {
286 const size_t varCount = 2 * BitsPerWord + 1;
287 RSFIdeal* ideal = newRawSquareFreeIdeal(varCount, varCount + 33);
288 Word* term = newTerm(varCount);
289 vector<size_t> countsCorrect(varCount);
290 vector<size_t> counts;
291
292 ideal->getVarDividesCounts(counts);
293 ASSERT_EQ(counts, countsCorrect);
294
295 setToAllVarProd(term, varCount);
296 const size_t insertAllOnesCount = varCount < 33 ? varCount : 33;
297 for (size_t i = 0; i < insertAllOnesCount; ++i) {
298 ideal->insert(term);
299 for (size_t var = 0; var < varCount; ++var)
300 countsCorrect[var] += 1;
301 ideal->getVarDividesCounts(counts);
302 ASSERT_EQ(counts, countsCorrect);
303 }
304
305 ASSERT(ideal->getGeneratorCount() <= varCount);
306 setToIdentity(term, varCount);
307 for (size_t i = 0; i < varCount; ++i) {
308 setExponent(ideal->getGenerator(i % insertAllOnesCount), i, 0);
309 ideal->insert(term);
310 countsCorrect[i] -= 1;
311 ideal->getVarDividesCounts(counts);
312 ASSERT_EQ(counts, countsCorrect);
313 }
314
316 deleteTerm(term);
317}
318
319#define TEST_HASFULLSUPPORT(idealStr, _extraStr, value) { \
320 const char* extraStr = _extraStr; \
321 Word* extra = extraStr == 0 ? 0 : newTermParse(extraStr); \
322 RSFIdeal* ideal = newRawSquareFreeIdealParse(idealStr); \
323 if (value) { \
324 ASSERT_TRUE2(ideal->hasFullSupport(extra), *ideal, extraStr); \
325 } else { \
326 ASSERT_FALSE2(ideal->hasFullSupport(extra), *ideal, extraStr); \
327 } \
328 deleteRawSquareFreeIdeal(ideal); \
329 deleteTerm(extra); \
330 }
331TEST(RawSquareFreeIdeal, HasFullSupport) {
332 TEST_HASFULLSUPPORT("", "", true);
333 TEST_HASFULLSUPPORT("0", "0", false);
334
335 TEST_HASFULLSUPPORT("0\n0", "0", false);
336 TEST_HASFULLSUPPORT("1\n0", "0", true);
337 TEST_HASFULLSUPPORT("0\n1", "0", true);
338 TEST_HASFULLSUPPORT("1\n1", "0", true);
339
340 TEST_HASFULLSUPPORT("0\n0", "1", true);
341 TEST_HASFULLSUPPORT("1\n0", "1", true);
342 TEST_HASFULLSUPPORT("0\n1", "1", true);
343 TEST_HASFULLSUPPORT("1\n1", "1", true);
344
346 ("011111111111111111110000000000000000000000011011111111111111111111101\n"
347 "111111111111111111111111111111111111111111111011111111111111111111101\n"
348 "000000000000000000000000000000000000000000000000000000000000000000010\n",
349 "000000000000000000000000000000000000000000000100000000000000000000000",
350 true);
351
353 ("011111111111111111110000000000000000000000011011111111111111111111101\n"
354 "111111111111111111111111111111111111111111111011111111111111111111101\n"
355 "000000000000000000000000000000000000000000000000000000000000000000010\n",
356 "000000000000000000000000000000000000000000000000000000000000000000000",
357 false);
359 ("011111111111111111110000000000000000000000011011111111111111111111101\n"
360 "111111111111111111111111111111111111111111111011111111111111111111101\n"
361 "000000000000000000000000000000000000000000000000000000000000000000000\n",
362 "000000000000000000000000000000000000000000000100000000000000000000000",
363 false);
364
365 TEST_HASFULLSUPPORT // this triggered a bug
366 ("11111111111111111111111111111111\n",
367 "00000000000000000000000000000000",
368 true);
369}
370
371#define TEST_COMPACT(beforeStr, removeStr, afterStr) { \
372 RSFIdeal* before = newRawSquareFreeIdealParse(beforeStr); \
373 Word* remove = newTermParse(removeStr); \
374 RSFIdeal* after = newRawSquareFreeIdealParse(afterStr); \
375 before->compact(remove); \
376 ASSERT_EQ(*before, *after); \
377 deleteRawSquareFreeIdeal(before); \
378 deleteTerm(remove); \
379 deleteRawSquareFreeIdeal(after); \
380 }
382 TEST_COMPACT("101", "110", "1");
383 TEST_COMPACT("101", "101", "0");
384 TEST_COMPACT("101", "000", "101");
385 TEST_COMPACT("111\n000\n001\n101", "110", "1\n0\n1\n1\n");
386
388 ("011111111111111111110000000000000000000000011011111111111111111111101\n"
389 "111111111111111111111111111111111111111111111011111111111111111111101\n"
390 "000000000000000000000000010000000000000000000000000000000000000000010\n",
391 "111111110000000000000000000000000000000000000000000000000000000000001",
392 "111111111111000000000000000000000001101111111111111111111110\n"
393 "111111111111111111111111111111111111101111111111111111111110\n"
394 "000000000000000001000000000000000000000000000000000000000001\n");
395}
396
397#define TEST_TRANSPOSE(beforeStr, removeStr, afterStr) { \
398 RSFIdeal* before = newRawSquareFreeIdealParse(beforeStr); \
399 Word* remove = removeStr == 0 ? 0 : newTermParse(removeStr);\
400 RSFIdeal* after = newRawSquareFreeIdealParse(afterStr); \
401 const size_t maxDim = before->getGeneratorCount() > before->getVarCount() ?\
402 before->getGeneratorCount() : before->getVarCount(); \
403 RSFIdeal* calculated = newRawSquareFreeIdeal(maxDim, maxDim);\
404 calculated->setToTransposeOf(*before, remove); \
405 ASSERT_EQ(*calculated, *after); \
406 calculated->setToTransposeOf(*calculated); \
407 calculated->transpose(); \
408 ASSERT_EQ(*calculated, *after); \
409 deleteRawSquareFreeIdeal(before); \
410 deleteTerm(remove); \
411 deleteRawSquareFreeIdeal(after); \
412 deleteRawSquareFreeIdeal(calculated); \
413}
414
416 TEST_TRANSPOSE("\n", 0, "\n");
417 TEST_TRANSPOSE("\n", "", "\n");
418 TEST_TRANSPOSE("01\n", 0, "0\n1\n");
419 TEST_TRANSPOSE("01\n", "00", "0\n1\n");
420 TEST_TRANSPOSE("01\n", "10", "1\n");
421 TEST_TRANSPOSE("01\n", "01", "0\n");
422 TEST_TRANSPOSE("11\n01\n", 0, "10\n11\n");
423 TEST_TRANSPOSE("1110101\n"
424 "0011100\n"
425 "1011111\n",
426
427 "0010000",
428
429 "101\n100\n011\n111\n001\n101\n");
430
431 string myBefore;
432 string myRemove;
433 string myAfter;
434 for (size_t i = 0; i < 200; ++i) {
435 myBefore += "0101";
436 myRemove += "0011";
437 myAfter += "0\n1\n";
438 }
439 TEST_TRANSPOSE(myBefore.c_str(), myRemove.c_str(), myAfter.c_str());
440}
TEST(RawSquareFreeIdeal, Insert_Term)
#define TEST_MINIMIZE(idealStr, minimizedStr)
RawSquareFreeIdeal RSFIdeal
#define TEST_COLON_REMINIMIZE_VAR(idealStr, colonVar, minimizedStr)
#define TEST_HASFULLSUPPORT(idealStr, _extraStr, value)
#define TEST_COLON_REMINIMIZE_TERM(idealStr, colonStr, minimizedStr)
#define TEST_TRANSPOSE(beforeStr, removeStr, afterStr)
#define TEST_COMPACT(beforeStr, removeStr, afterStr)
RSFIdeal * newRawSquareFreeIdeal(size_t varCount, size_t capacity)
Allocates object with enough memory for capacity generators in varCount variables.
void deleteRawSquareFreeIdeal(RSFIdeal *ideal)
RawSquareFreeIdeal * newRawSquareFreeIdealParse(const char *str)
Allocates and returns an ideal based on str.
#define ASSERT_NEQ(A, B)
Definition: asserts.h:175
#define ASSERT_TRUE(VALUE)
Definition: asserts.h:72
#define ASSERT_EQ(A, B)
Definition: asserts.h:147
A bit packed square free ideal placed in a pre-allocated buffer.
void sortLexAscending()
Sorts the generators in ascending lex order.
void getVarDividesCounts(vector< size_t > &counts) const
Sets counts[var] to the number of generators that var divides.
Word * getGenerator(size_t index)
Returns the generator at index.
size_t getGeneratorCount() const
size_t insert(const Ideal &ideal)
Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all ...
#define TEST_SUITE(SUITE)
Definition: macroes.h:26
void setExponent(Word *a, size_t var, bool value)
Word * newTerm(size_t varCount)
Returns identity term of varCount variables.
Word * newTermParse(const char *strParam)
Allocates and returns a term based on str.
void setToAllVarProd(Word *res, size_t varCount)
Sets all exponents of res to 1.
bool equals(const Word *a, const Word *b, size_t varCount)
Returns true if a equals b.
void deleteTerm(Word *term)
Deletes term previously returned by newTerm().
void setToIdentity(Word *res, const Word *resEnd)
static const size_t BitsPerWord
Definition: stdinc.h:94
unsigned long Word
The native unsigned type for the CPU.
Definition: stdinc.h:93
#define ASSERT(X)
Definition: stdinc.h:86