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 
24 using namespace SquareFreeTermOps;
25 
27 
29 
30 namespace {
31  bool sortedEqual(const RawSquareFreeIdeal& a, const RawSquareFreeIdeal& b) {
32  RSFIdeal* aCopy = newRawSquareFreeIdeal(a);
33  RSFIdeal* bCopy = newRawSquareFreeIdeal(b);
34  aCopy->sortLexAscending();
35  bCopy->sortLexAscending();
36  bool equal = (*aCopy == *bCopy);
39  return equal;
40  }
41 }
42 
43 TEST(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 
66 TEST(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 
120 TEST(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 
142  deleteRawSquareFreeIdeal(sorted);
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 
159 TEST(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 
212 TEST(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 
285 TEST(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  }
331 TEST(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