41 template<
class Iter,
class Pred>
42 inline Iter RsfPartition(Iter begin, Iter end, Pred pred,
size_t varCount) {
70 const size_t wordCount) {
73 if (
Ops::divides(*div, *div + wordCount, *it) && div != it) {
120 size_t bytesForStruct =
sizeof(
RSFIdeal) -
sizeof(
Word);
121 if (generatorCount == 0)
122 return bytesForStruct;
125 size_t bytesPerGenUnaligned = varCount == 0 ? 1 : (varCount - 1) / 8 + 1;
126 size_t wordsPerGen = (bytesPerGenUnaligned - 1) /
sizeof(
Word) + 1;
127 if (wordsPerGen > numeric_limits<size_t>::max() /
sizeof(
Word))
129 size_t bytesPerGen = wordsPerGen *
sizeof(
Word);
132 if (bytesPerGen > numeric_limits<size_t>::max() / generatorCount)
134 size_t bytesForGens = bytesPerGen * generatorCount;
135 if (bytesForGens > numeric_limits<size_t>::max() - bytesForStruct)
137 return bytesForStruct + bytesForGens;
141 if (
this == &ideal) {
149 _varCount = idealGenCount;
152 _memoryEnd = _memory;
154 for (
size_t var = 0; var < idealVarCount; ++var) {
158 Word* newTransposedGen = back();
159 for (
size_t gen = 0; gen < idealGenCount; ++gen) {
169 const size_t varCount = getVarCount();
170 const size_t genCount = getGeneratorCount();
173 void* buffer = arena.
alloc(bytes);
175 setToTransposeOf(*copy, eraseVars);
182 fputs(out.str().c_str(), file);
186 const size_t varCount = getVarCount();
187 out <<
"//------------ Ideal (Square Free):\n";
188 for (
size_t gen = 0; gen < getGeneratorCount(); ++gen) {
189 for (
size_t var = 0; var < varCount; ++var)
193 out <<
"------------\\\\\n";
204 _memoryEnd += getWordsPerTerm();
218 _memoryEnd += getWordsPerTerm();
232 ASSERT(term.size() == getVarCount());
237 _memoryEnd += getWordsPerTerm();
243 iterator newEnd = ::minimize(begin(), end(), getWordsPerTerm());
244 _genCount = newEnd - begin();
245 _memoryEnd = *newEnd;
250 const size_t wordCount = getWordsPerTerm();
252 for (
iterator it = begin(); it != stop; ++it)
259 for (
iterator it = begin(); it != stop; ++it)
265 const size_t oldVarCount = getVarCount();
270 size_t varCompact = 0;
271 for (
size_t var = 0; var < oldVarCount; ++var) {
274 for (
iterator oldIt = oldBegin; oldIt != oldStop; ++oldIt)
284 if (bitOffset != 0) {
285 const Word mask = (((
Word)1) << bitOffset) - 1;
286 for (
iterator oldIt = oldBegin; oldIt != oldStop; ++oldIt)
287 *(*oldIt + wordOffset) &= mask;
294 iterator newIt(_memory, newWordCount);
295 for (
iterator oldIt = oldBegin; oldIt != oldStop; ++oldIt, ++newIt)
296 Ops::assign(*newIt, (*newIt) + newWordCount, *oldIt);
298 _varCount = varCompact;
299 _wordsPerTerm = newWordCount;
305 ASSERT(var < getVarCount());
307 const Word*
const lcmEnd = lcm + getWordsPerTerm();
319 const size_t wordsPerTerm,
322 const Word mask = ~((
Word)0u) / 15u;
325 if ((genCount & 1) == 1) {
328 a1 = (a >> 1) & mask;
329 a2 = (a >> 2) & mask;
330 a3 = (a >> 3) & mask;
333 a0 = a1 = a2 = a3 = 0;
336 for (
size_t i = 0; i < genCount; ++i) {
343 a1 += (a >> 1) & mask;
344 a2 += (a >> 2) & mask;
345 a3 += (a >> 3) & mask;
348 a1 += (aa >> 1) & mask;
349 a2 += (aa >> 2) & mask;
350 a3 += (aa >> 3) & mask;
354 *(counts + 0) += a0 & 0xF;
355 *(counts + 1) += a1 & 0xF;
356 *(counts + 2) += a2 & 0xF;
357 *(counts + 3) += a3 & 0xF;
367 const size_t varCount = getVarCount();
368 const size_t wordCount = getWordsPerTerm();
373 divCounts.resize(getVarCount());
374 size_t* divCountsBasePtr = &(divCounts.front());
375 size_t* divCountsEnd = divCountsBasePtr +
BitsPerWord * wordCount;
376 memset(divCountsBasePtr, 0,
sizeof(
size_t) * varCount);
378 size_t generatorsToGo = getGeneratorCount();
380 while (generatorsToGo > 0) {
381 const size_t blockSize = generatorsToGo >= 15 ? 15 : generatorsToGo;
383 size_t* counts = divCountsBasePtr;
384 const Word* genOffset = *blockBegin;
385 for (; counts != divCountsEnd; counts +=
BitsPerWord, ++genOffset)
388 generatorsToGo -= blockSize;
389 blockBegin = blockBegin + blockSize;
394 ASSERT(var < getVarCount());
401 return getGeneratorCount();
405 ASSERT(var < getVarCount());
412 return getGeneratorCount();
421 const size_t varCount = getVarCount();
425 for (++it; it != stop; ++it) {
427 if (maxSupp < supp) {
432 return maxSuppIt - begin();
441 const size_t varCount = getVarCount();
445 for (++it; it != stop; ++it) {
447 if (minSupp > supp) {
452 return minSuppIt - begin();
456 ASSERT(var < getVarCount());
458 const Word*
const gcdEnd = gcd + getWordsPerTerm();
468 const size_t varCount = getVarCount();
469 const size_t wordCount = getWordsPerTerm();
470 const Word*
const gcdEnd = gcd + wordCount;
471 const Word* divEnd = div + wordCount;
481 Word* term = getGenerator(gen);
482 Word* last = _memoryEnd - getWordsPerTerm();
486 _memoryEnd -= getWordsPerTerm();
494 const Word* termEnd = term + getWordsPerTerm();
514 const size_t wordCount = getWordsPerTerm();
515 for (
size_t gen = 0; gen < getGeneratorCount(); ++gen)
518 return getGeneratorCount();
522 const size_t wordCount = getWordsPerTerm();
523 for (
size_t offset = 0; offset < wordCount; ++offset) {
526 for (
size_t gen = 0; gen < _genCount; ++gen) {
527 Word word = getGenerator(gen)[offset];
528 twice |= once & word;
531 const Word onceOnly = once & ~twice;
533 for (
size_t gen = 0; ; ++gen) {
535 Word word = getGenerator(gen)[offset];
542 return getGeneratorCount();
547 const size_t wordCount = getWordsPerTerm();
550 const Word* firstGenOffset = _memory;
551 const Word* endGenOffset = _memoryEnd;
552 size_t varsLeft = getVarCount();
554 const Word* gen = firstGenOffset;
555 Word support = *ignore;
556 while (gen != endGenOffset) {
562 if (support != allOnes)
566 return support == allOnes;
567 const Word fullSupportWord = (((
Word)1) << varsLeft) - 1;
568 return support == fullSupportWord;
580 size_t wordCount = getWordsPerTerm();
581 for (
size_t i = 0; i < _genCount; ++i)
582 for (
size_t div = 0; div < _genCount; ++div)
584 Ops::divides(getGenerator(div), getGenerator(div) + wordCount,
591 ASSERT(a < getGeneratorCount());
592 ASSERT(b < getGeneratorCount());
593 Ops::swap(getGenerator(a), getGenerator(b), getVarCount());
603 const size_t varCount = getVarCount();
607 for (; it != stop; ++it, ++it2)
614 struct CmpForSortLexAscending : std::binary_function<size_t, size_t, bool> {
615 bool operator()(
size_t a,
size_t b)
const {
616 return Ops::lexLess(ideal->getGenerator(a), ideal->getGenerator(b),
617 ideal->getVarCount());
624 vector<size_t> sorted(getGeneratorCount());
625 for (
size_t gen = 0; gen < getGeneratorCount(); ++gen)
628 CmpForSortLexAscending cmp;
630 std::sort(sorted.begin(), sorted.end(), cmp);
635 for (
size_t gen = 0; gen < getGeneratorCount(); ++gen)
636 clone->insert(getGenerator(gen));
637 for (
size_t gen = 0; gen < getGeneratorCount(); ++gen)
638 Ops::assign(getGenerator(gen), clone->getGenerator(sorted[gen]),
645 Ops::assign(_memoryEnd, _memoryEnd + getWordsPerTerm(), term);
647 _memoryEnd += getWordsPerTerm();
653 const size_t varCount = getVarCount();
654 for (
iterator it = begin(); it != stop; ++it)
661 _memoryEnd += getWordsPerTerm();
666 struct ColonReminimizeTermHelper {
667 bool operator()(
const Word* term) {
671 const Word* colonEnd;
677 const size_t varCount = getVarCount();
678 const size_t wordCount = getWordsPerTerm();
682 ColonReminimizeTermHelper colonIsRelativelyPrime;
683 colonIsRelativelyPrime.colon = by;
684 colonIsRelativelyPrime.colonEnd = by + wordCount;
685 iterator middle = RsfPartition(start, stop, colonIsRelativelyPrime, varCount);
687 if (middle == start) {
691 for (
iterator it = start; it != middle; ++it)
697 iterator newMiddle = ::minimize(start, middle, getWordsPerTerm());
700 for (
iterator it = middle; it != stop; ++it) {
709 _memoryEnd = *newEnd;
710 _genCount = newEnd - start;
715 struct ColonReminimizeVarHelper {
716 bool operator()(
const Word* term) {
724 ASSERT(var < getVarCount());
725 const size_t varCount = getVarCount();
726 const size_t wordCount = getWordsPerTerm();
730 ColonReminimizeVarHelper varDivides;
731 varDivides.var = var;
732 iterator middle = RsfPartition(start, stop, varDivides, varCount);
734 if (middle == start) {
738 for (
iterator it = start; it != middle; ++it)
740 if (middle == stop) {
748 for (
iterator it = middle; it != stop;) {
766 Word* lcmEnd = lcm + getWordsPerTerm();
775 const size_t varCount = getVarCount();
776 const size_t wordCount = getWordsPerTerm();
777 const size_t genCount = getGeneratorCount();
778 if (varCount != _varCount)
780 if (wordCount != _wordsPerTerm)
782 if (_genCount != genCount)
787 if (_memoryEnd != _memory + wordCount * genCount)
789 if (_memoryEnd < _memory)
792 for (
const Word* p = _memory; p != _memoryEnd; p += wordCount)
801 void* buffer =
new char[byteCount];
812 void* buffer =
new char[byteCount];
820 istringstream in(str);
821 vector<string> lines;
824 while (getline(in, line))
826 lines.push_back(line);
828 const size_t varCount = lines.empty() ? 0 : lines.front().size();
830 for (
size_t gen = 0; gen < lines.size(); ++gen) {
831 ASSERT(lines[gen].size() == varCount);
841 delete[]
reinterpret_cast<char*
>(ideal);
void sortLexAscending()
Sorts the generators in ascending lex order.
void getLcmOfNonMultiples(Word *lcm, size_t var) const
Sets lcm to be the least common multple of those generators that var does not divide.
void print(FILE *file) const
Print a debug-suitable representation of this object to file.
size_t getMinSupportGen() const
Returns the index of a generator with minimum support.
bool isValid() const
Returns true if the internal invariants of ideal are satisfied.
RawSquareFreeIdeal RSFIdeal
size_t getNonMultiple(size_t var) const
Returns the index of the first generator that var does not divide or getGeneratorCount() if no such g...
void lcmInPlace(Word *res, const Word *resEnd, const Word *a)
size_t getExclusiveVarGenerator()
Returns the index of a generator that is the only one to be divisible by some variable.
bool lexLess(const Word *a, const Word *b, size_t varCount)
bool equals(const Word *a, const Word *b, size_t varCount)
Returns true if a equals b.
const_iterator doesn't have all it needs to be a proper STL iterator.
void getGcdOfMultiples(Word *gcd, size_t var) const
Sets gcd to be the greatest common denominator of those generators that are divisible by var...
void colonReminimize(const Word *colon)
Performs a colon and minimize.
void invert(Word *a, size_t varCount)
Make 0 exponents 1 and make 1 exponents 0.
size_t getWordOffset(size_t var)
Word * getGenerator(size_t index)
Returns the generator at index.
void getVarDividesCounts(vector< size_t > &counts) const
Sets counts[var] to the number of generators that var divides.
void removeGenerator(size_t index)
Removes the generator at index.
Represents a monomial ideal with int exponents.
size_t getBitOffset(size_t var)
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
void transpose(Word *eraseVars=0)
Equivalent to setToTransposeOf(this, eraseVars).
RSFIdeal * newRawSquareFreeIdeal(size_t varCount, size_t capacity)
Allocates object with enough memory for capacity generators in varCount variables.
void setToIdentity(Word *res, const Word *resEnd)
size_t getNotRelativelyPrime(const Word *term)
Returns the index of the first generator that is not relatively prime with term.
size_t getMaxSupportGen() const
Returns the index of a generator with maximum support.
A bit packed square free ideal placed in a pre-allocated buffer.
void setToTransposeOf(const RawSquareFreeIdeal &ideal, Word *eraseVars=0)
Resets this object to the transpose of ideal.
void colon(Word *res, const Word *resEnd, const Word *a, const Word *b)
size_t getVarCount() const
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
void setExponent(Word *a, size_t var, bool value)
bool operator==(const RawSquareFreeIdeal &ideal) const
Returns true if *this equals ideal.
size_t getGeneratorCount() const
void compact(const Word *remove)
Removes the variables that divide remove.
iterator doesn't have all it needs to be a proper STL iterator.
static Arena & getArena()
Returns an arena object that can be used for non-thread safe scratch memory after static objects have...
unsigned long Word
The native unsigned type for the CPU.
size_t getVarCount() const
void print(FILE *out, const ColumnPrinter &pr)
static RawSquareFreeIdeal * construct(void *buffer, size_t varCount=0)
This is an arena allocator.
static const size_t BitsPerWord
void * alloc(size_t size)
Returns a pointer to a buffer of size bytes.
static void countVarDividesBlockUpTo15(const Word *it, size_t genCount, const size_t wordsPerTerm, size_t *counts)
void swap(size_t a, size_t b)
bool encodeTerm(Word *encoded, const Exponent *term, const size_t varCount)
Assigns the RawSquareFreeTerm-encoded form of term to encoded and returns true if term is square free...
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
size_t getWordCount(size_t varCount)
void transpose(Matrix &trans, const Matrix &mat)
Sets trans to the transpose of mat.
size_t getGeneratorCount() const
size_t getMultiple(size_t var) const
Returns the index of the first generator that var divides or getGeneratorCount() if no such generator...
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...
void swap01Exponents()
Change 0 exponents into 1 and vice versa.
bool isMinimallyGenerated() const
Returns true if no generator divides another.
size_t getVarCount() const
bool hasFullSupport(const Word *ignore) const
Returns true if for every variable it either divides ignore or it divides some (not necessarily minim...
void freeTop(void *ptr)
Frees the buffer pointed to by ptr.
RawSquareFreeIdeal * newRawSquareFreeIdealParse(const char *str)
Allocates and returns an ideal based on str.
void colonInPlace(Word *res, const Word *resEnd, const Word *b)
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
void setToAllVarProd(Word *res, size_t varCount)
Sets all exponents of res to 1.
size_t getSizeOfSupport(const Word *a, size_t varCount)
Word * newTermParse(const char *strParam)
Allocates and returns a term based on str.
size_t getGeneratorCount() const
void getLcm(Word *lcm) const
Puts the least common multiple of the generators of the ideal into lcm.
void assign(Word *a, const Word *b, size_t varCount)
size_t insert(const Ideal &ideal)
Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all ...
void insertNonMultiples(const Word *term, const RawSquareFreeIdeal &ideal)
Insert those generators of ideal that are not multiples of term.
void deleteRawSquareFreeIdeal(RSFIdeal *ideal)
static size_t getBytesOfMemoryFor(size_t varCount, size_t generatorCount)
Returns the number of bytes of memory necessary to contain an ideal with the given parameters...
void colon(const Word *by)
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 swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
void gcdInPlace(Word *res, const Word *resEnd, const Word *a)