Frobby 0.9.5
RawSquareFreeTermTest.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 "RawSquareFreeTerm.h"
20#include "tests.h"
21
22TEST_SUITE(RawSquareFreeTerm)
23
24using namespace SquareFreeTermOps;
25namespace Ops = SquareFreeTermOps;
26
27TEST(RawSquareFreeTerm, getWordCount) {
28 ASSERT_EQ(getWordCount(0), 1u);
29 ASSERT_EQ(getWordCount(1), 1u);
30
34
35 ASSERT_EQ(getWordCount(10 * BitsPerWord - 1), 10u);
37 ASSERT_EQ(getWordCount(10 * BitsPerWord + 1), 11u);
38}
39
40TEST(RawSquareFreeTerm, SetAndGetExponent) {
41 const size_t varCount = BitsPerWord * 2;
42 Word* term = newTerm(varCount);
43
44 for (size_t var = 0; var < varCount; ++var) {
45 ASSERT_FALSE(getExponent(term, var));
46 setExponent(term, var, true);
47 ASSERT_TRUE(getExponent(term, var));
48 }
49
50 for (size_t var = 0; var < varCount; ++var) {
51 ASSERT_TRUE(getExponent(term, var));
52 setExponent(term, var, false);
53 ASSERT_FALSE(getExponent(term, var));
54 }
55}
56
57TEST(RawSquareFreeTerm, Assign) {
58 const size_t varCount = BitsPerWord * 2;
59 const size_t wordCount = getWordCount(varCount);
62
63 setExponent(a, 1, true);
64
67
68 assign(b, b + wordCount, a);
69
72
73 setExponent(a, 1, false);
74
77
80}
81
82TEST(RawSquareFreeTerm, HasFullSupport) {
83 const size_t maxVarCount = 2 * BitsPerWord + 1;
84
85 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
86 Word* term = newTerm(varCount);
87
88 for (size_t var = 0; var < varCount; ++var) {
90 setExponent(term, var, true);
91 }
93
94 for (size_t var = 0; var < varCount; ++var) {
96 setExponent(term, var, false);
98 setExponent(term, var, true);
99 }
101
102 deleteTerm(term);
103 }
104}
105
106TEST(RawSquareFreeTerm, IsIdentity) {
107 const size_t maxVarCount = 2 * BitsPerWord + 1;
108 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
109 Word* term = newTerm(varCount);
111
113 for (size_t var = 0; var < varCount; ++var) {
115 setExponent(term, var, true);
117 setExponent(term, var, false);
118 }
120
121 deleteTerm(term);
122 }
123}
124
125TEST(RawSquareFreeTerm, GetSizeOfSupport) {
126 const size_t maxVarCount = 2 * BitsPerWord + 1;
127 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
128 Word* term = newTerm(varCount);
129
131 for (size_t var = 0; var < varCount; ++var) {
132 setExponent(term, var, 1);
134 setExponent(term, var, 0);
135 }
136
137 for (size_t var = 0; var < varCount; ++var) {
138 setExponent(term, var, 1);
140 }
141
142 deleteTerm(term);
143 }
144}
145
146TEST(RawSquareFreeTerm, SetToIdentity) {
147 const size_t maxVarCount = 2 * BitsPerWord + 1;
148 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
149 Word* term = newTerm(varCount);
151
153 for (size_t var = 0; var < varCount; ++var) {
154 setExponent(term, var, true);
155 setToIdentity(term, termEnd);
157
158 setExponent(term, var, true);
159 setToIdentity(term, varCount);
161 }
162
163 deleteTerm(term);
164 }
165}
166
167TEST(RawSquareFreeTerm, SetToAllVarProd) {
168 const size_t maxVarCount = 2 * BitsPerWord + 1;
169 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
170 Word* term = newTerm(varCount);
171
174 for (size_t var = 0; var < varCount; ++var) {
175 setExponent(term, var, false);
179 }
180
181 deleteTerm(term);
182 }
183}
184
185TEST(RawSquareFreeTerm, IsRelativelyPrime) {
186 const size_t maxVarCount = 2 * BitsPerWord + 1;
187 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
192
195 for (size_t var = 0; var < varCount; ++var) {
196 setExponent(a, var, true);
199 setExponent(b, var, true);
202 setExponent(a, var, false);
203 }
204
205 deleteTerm(a);
206 deleteTerm(b);
207 }
208}
209
210TEST(RawSquareFreeTerm, Lcm) {
211 const size_t maxVarCount = 2 * BitsPerWord + 1;
212 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
217
218 lcm(c, cEnd, a, b);
220 if (varCount < 4)
221 continue;
222
223 // a becomes 1001 at end.
224 // b becomes 1100 at end.
225 setExponent(a, varCount - 1, true);
226 setExponent(a, varCount - 4, true);
227 setExponent(b, varCount - 3, true);
228 setExponent(b, varCount - 4, true);
229 lcm(c, cEnd, a, b);
230
231 // c should be 1101 at end.
236
237 // no other bits should be set.
238 setExponent(c, varCount - 1, false);
239 setExponent(c, varCount - 3, false);
240 setExponent(c, varCount - 4, false);
242
243 deleteTerm(a);
244 deleteTerm(b);
245 deleteTerm(c);
246 }
247}
248
249TEST(RawSquareFreeTerm, Gcd) {
250 const size_t maxVarCount = 2 * BitsPerWord + 1;
251 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
256
257 gcd(c, cEnd, a, b);
259 if (varCount < 4)
260 continue;
261
262 // a becomes 1001 at end.
263 // b becomes 1100 at end.
264 setExponent(a, varCount - 1, true);
265 setExponent(a, varCount - 4, true);
266 setExponent(b, varCount - 3, true);
267 setExponent(b, varCount - 4, true);
268 gcd(c, cEnd, a, b);
269
270 // c should be 1000 at end.
275
276 // no other bits should be set.
277 setExponent(c, varCount - 4, false);
279
280 deleteTerm(a);
281 deleteTerm(b);
282 deleteTerm(c);
283 }
284}
285
286TEST(RawSquareFreeTerm, Colon) {
287 const size_t maxVarCount = 2 * BitsPerWord + 1;
288 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
293
294 colon(c, cEnd, a, b);
296 if (varCount < 4)
297 continue;
298
299 // a becomes 1001 at end.
300 // b becomes 1100 at end.
301 setExponent(a, varCount - 1, true);
302 setExponent(a, varCount - 4, true);
303 setExponent(b, varCount - 3, true);
304 setExponent(b, varCount - 4, true);
305 colon(c, cEnd, a, b);
306
307 // c should be 0001 at end.
312
313 // no other bits should be set.
314 setExponent(c, varCount - 1, false);
316
317 deleteTerm(a);
318 deleteTerm(b);
319 deleteTerm(c);
320 }
321}
322
323TEST(RawSquareFreeTerm, Divides) {
324 const size_t maxVarCount = 2 * BitsPerWord + 1;
325 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
330
332 for (size_t var = 0; var < varCount; ++var) {
333 setExponent(a, var, true);
336 setExponent(b, var, true);
338 }
339
340 deleteTerm(a);
341 deleteTerm(b);
342 }
343}
344
345TEST(RawSquareFreeTerm, LexLess) {
346 const size_t maxVarCount = 2 * BitsPerWord + 1;
347 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
350
352 if (varCount == 0)
353 continue;
354 setExponent(b, varCount - 1, 1);
357
358 for (size_t var = 0; var < varCount - 1; ++var) {
359 setExponent(a, var, 1);
362
363 setExponent(b, var, 1);
366
367 if (var % 3 == 1) {
368 // vary the pattern of the vars we've already been at.
369 setExponent(a, var, 0);
370 setExponent(b, var, 0);
371 }
372 }
373
374 deleteTerm(a);
375 deleteTerm(b);
376 }
377}
378
379TEST(RawSquareFreeTerm, Invert) {
380 const size_t maxVarCount = 2 * BitsPerWord + 1;
381 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
383
385 invert(a, varCount);
388
389 if (varCount < 1)
390 continue;
391
392 setExponent(a, 0, false);
393 setExponent(a, varCount - 1, false);
394 invert(a, varCount);
397
398 invert(a, varCount);
401
402 deleteTerm(a);
403 }
404}
405
406TEST(RawSquareFreeTerm, GetVarIfPure) {
407 const size_t maxVarCount = 2 * BitsPerWord + 1;
408 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
410
412 for (size_t v1 = 0; v1 < varCount; ++v1) {
413 setExponent(a, v1, 1);
415 for (size_t v2 = 0; v2 < varCount; ++v2) {
416 if (v1 != v2) {
417 setExponent(a, v2, 1);
419 setExponent(a, v2, 0);
420 }
421 }
422 setExponent(a, v1, 0);
423 }
424
425 deleteTerm(a);
426 }
427}
428
429/*
430TEST(RawSquareFreeTerm, IncrementAtSupport) {
431 const size_t maxVarCount = 2 * BitsPerWord + 1;
432 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
433 Word* every = newTerm(varCount);
434 Word* second = newTerm(varCount);
435 Word* third = newTerm(varCount);
436
437 vector<size_t> counts(varCount);
438 vector<size_t> countsCorrect(varCount);
439 size_t* countsPtr = &counts.front();
440
441 incrementAtSupport(every, countsPtr, varCount);
442 ASSERT_TRUE_SILENT(counts == vector<size_t>(varCount));
443
444 for (size_t var = 0; var < varCount; ++var) {
445 setExponent(every, var, 1);
446 countsCorrect[var] += 1;
447 if (var % 2 == 0) {
448 setExponent(second, var, 1);
449 countsCorrect[var] += 1;
450 }
451 if (var % 3 == 0) {
452 setExponent(third, var, 1);
453 countsCorrect[var] += 1;
454 }
455 }
456
457 incrementAtSupport(every, countsPtr, varCount);
458 incrementAtSupport(second, countsPtr, varCount);
459 incrementAtSupport(third, countsPtr, varCount);
460
461 ASSERT_TRUE(counts == countsCorrect);
462
463 deleteTerm(every);
464 deleteTerm(second);
465 deleteTerm(third);
466 }
467}
468*/
469TEST(RawSquareFreeTerm, IsValid) {
470 const size_t varCount = 2 * BitsPerWord;
473
474 setExponent(a, 1, true);
476 ASSERT_TRUE(isValid(a, 2));
477
478 setExponent(a, BitsPerWord, true);
481
482 setExponent(a, BitsPerWord + 1, true);
485
486 setExponent(a, varCount - 1, true);
489
490 deleteTerm(a);
491}
492
493TEST(RawSquareFreeTerm, NewTermParse) {
494 Word* ref = newTerm(65);
495 setExponent(ref, 0, 1);
496 setExponent(ref, 1, 1);
497 setExponent(ref, 3, 1);
498 setExponent(ref, 4, 1);
499 setExponent(ref, 64, 1);
500
501 // 0 1 2 3 4 5 6 7
502 // 1234567890123456789012345678901234567890123456789012345678901234567890
504 ("11011000000000000000000000000000000000000000000000000000000000001");
508
509 ref = newTerm(1);
510 setExponent(ref, 0, 1);
511 parsed = newTermParse("1");
514
516}
517
518TEST(RawSquareFreeTerm, Equals) {
519 const size_t maxVarCount = 2 * BitsPerWord + 1;
520 for (size_t varCount = 0; varCount <= maxVarCount; ++varCount) {
523
525 for (size_t var = 0; var < varCount; ++var) {
526 setExponent(a, var, 1);
529
530 setExponent(b, var, 1);
533 }
534
535 deleteTerm(a);
536 deleteTerm(b);
537 }
538}
539
540#define TEST_COMPACT(A,B,C) { \
541 size_t varCount = strlen(A); \
542 Word* a = newTermParse(A); \
543 Word* b = newTermParse(B); \
544 Word* c = newTermParse(C); \
545 size_t varCountAfter = strlen(C); \
546 Word* d = newTerm(varCountAfter); \
547 compact(d, a, b, varCount); \
548 ASSERT_TRUE(equals(d, c, varCountAfter)); \
549 compact(a, a, b, varCount); \
550 ASSERT_TRUE(equals(a, c, varCountAfter)); \
551 deleteTerm(a); \
552 deleteTerm(b); \
553 deleteTerm(c); \
554 deleteTerm(d); \
555 }
556TEST(RawSquareFreeTerm, Compact) {
557 TEST_COMPACT("0", "0", "0");
558 TEST_COMPACT("1", "0", "1");
559 TEST_COMPACT("0", "1", "");
560 TEST_COMPACT("1", "1", "");
561 TEST_COMPACT("001", "010", "01");
562 TEST_COMPACT("000000000000000000001111111111111111111111111111",
563 "000000000000000000000000000000000000000000000000",
564 "000000000000000000001111111111111111111111111111");
565 TEST_COMPACT("000000000000000000001111111111111111111111111111",
566 "111111111111111111111111111111111111111111111111",
567 "");
568 TEST_COMPACT("111100001111000011110000111100001111000011110000",
569 "101010101010101010101010101010101010101010101010",
570 "110011001100110011001100");
571 TEST_COMPACT("000000000000000000000000000000100000000000000001",
572 "011111111111111111111111111111011111111111111101",
573 "010");
574 TEST_COMPACT("011111111111111111111111111111011111111111111101",
575 "000000000000000000000000000000100000000000000001",
576 "0111111111111111111111111111111111111111111110");
577}
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
#define TEST_COMPACT(A, B, C)
#define ASSERT_TRUE_SILENT(VALUE)
Definition asserts.h:74
#define ASSERT_EQ_SILENT(A, B)
Definition asserts.h:149
#define ASSERT_TRUE(VALUE)
Definition asserts.h:72
#define ASSERT_EQ(A, B)
Definition asserts.h:147
#define ASSERT_FALSE_SILENT(VALUE)
Definition asserts.h:121
#define ASSERT_FALSE(VALUE)
Definition asserts.h:119
#define TEST(SUITE, TEST_NAME)
Definition macroes.h:41
#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.
bool isValid(const Word *a, size_t varCount)
The unused bits at the end of the last word must be zero for the functions here to work correctly.
size_t getWordCount(size_t varCount)
void colon(Word *res, const Word *resEnd, const Word *a, const Word *b)
size_t getVarIfPure(const Word *const a, size_t varCount)
Returns var if a equals var.
Word * newTermParse(const char *strParam)
Allocates and returns a term based on str.
void invert(Word *a, size_t varCount)
Make 0 exponents 1 and make 1 exponents 0.
bool lexLess(const Word *a, const Word *b, size_t varCount)
bool isIdentity(const Word *a, Word *aEnd)
bool hasFullSupport(const Word *a, size_t varCount)
size_t getSizeOfSupport(const Word *a, size_t varCount)
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
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.
bool divides(const Word *a, const Word *aEnd, const Word *b)
Returns true if a divides b.
void deleteTerm(Word *term)
Deletes term previously returned by newTerm().
void assign(Word *a, const Word *b, size_t varCount)
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
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