Go to the documentation of this file.
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) {
154 for (
size_t var = 0; var < idealVarCount; ++var) {
159 for (
size_t gen = 0; gen < idealGenCount; ++gen) {
173 void* buffer = arena.
alloc(bytes);
182 fputs(out.str().c_str(), file);
187 out <<
"//------------ Ideal (Square Free):\n";
189 for (
size_t var = 0; var < varCount; ++var)
193 out <<
"------------\\\\\n";
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;
295 for (
iterator oldIt = oldBegin; oldIt != oldStop; ++oldIt, ++newIt)
296 Ops::assign(*newIt, (*newIt) + newWordCount, *oldIt);
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;
374 size_t* divCountsBasePtr = &(divCounts.front());
375 size_t* divCountsEnd = divCountsBasePtr +
BitsPerWord * wordCount;
376 memset(divCountsBasePtr, 0,
sizeof(
size_t) * varCount);
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;
425 for (++it; it != stop; ++it) {
427 if (maxSupp < supp) {
432 return maxSuppIt -
begin();
445 for (++it; it != stop; ++it) {
447 if (minSupp > supp) {
452 return minSuppIt -
begin();
470 const Word*
const gcdEnd =
gcd + wordCount;
471 const Word* divEnd = div + wordCount;
523 for (
size_t offset = 0; offset < wordCount; ++offset) {
526 for (
size_t gen = 0; gen <
_genCount; ++gen) {
528 twice |= once & word;
531 const Word onceOnly = once & ~twice;
533 for (
size_t gen = 0; ; ++gen) {
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;
582 for (
size_t div = 0; div <
_genCount; ++div)
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());
628 CmpForSortLexAscending cmp;
630 std::sort(sorted.begin(), sorted.end(), cmp);
666 struct ColonReminimizeTermHelper {
667 bool operator()(
const Word* term) {
671 const Word* colonEnd;
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)
700 for (
iterator it = middle; it != stop; ++it) {
715 struct ColonReminimizeVarHelper {
716 bool operator()(
const Word* term) {
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;) {
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);
static void countVarDividesBlockUpTo15(const Word *it, size_t genCount, const size_t wordsPerTerm, size_t *counts)
size_t getGeneratorCount() const
const_iterator doesn't have all it needs to be a proper STL iterator.
void insertNonMultiples(const Word *term, const RawSquareFreeIdeal &ideal)
Insert those generators of ideal that are not multiples of term.
size_t insert(const Ideal &ideal)
Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all ...
void invert(Word *a, size_t varCount)
Make 0 exponents 1 and make 1 exponents 0.
bool isValid() const
Returns true if the internal invariants of ideal are satisfied.
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...
size_t getVarCount() const
size_t getWordCount(size_t varCount)
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.
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.
void setToAllVarProd(Word *res, size_t varCount)
Sets all exponents of res to 1.
This is an arena allocator.
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
size_t getExclusiveVarGenerator()
Returns the index of a generator that is the only one to be divisible by some variable.
void assign(Word *a, const Word *b, size_t varCount)
void getLcmOfNonMultiples(Word *lcm, size_t var) const
Sets lcm to be the least common multple of those generators that var does not divide.
bool isMinimallyGenerated() const
Returns true if no generator divides another.
static const size_t BitsPerWord
iterator doesn't have all it needs to be a proper STL iterator.
void setToTransposeOf(const RawSquareFreeIdeal &ideal, Word *eraseVars=0)
Resets this object to the transpose of ideal.
static RawSquareFreeIdeal * construct(void *buffer, size_t varCount=0)
void colonInPlace(Word *res, const Word *resEnd, const Word *b)
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
void compact(const Word *remove)
Removes the variables that divide remove.
void colon(Word *res, const Word *resEnd, const Word *a, const Word *b)
void gcdInPlace(Word *res, const Word *resEnd, const Word *a)
void * alloc(size_t size)
Returns a pointer to a buffer of size bytes.
size_t getGeneratorCount() const
static Arena & getArena()
Returns an arena object that can be used for non-thread safe scratch memory after static objects have...
void setExponent(Word *a, size_t var, bool value)
void setToIdentity(Word *res, const Word *resEnd)
RawSquareFreeIdeal RSFIdeal
bool hasFullSupport(const Word *ignore) const
Returns true if for every variable it either divides ignore or it divides some (not necessarily minim...
void lcmInPlace(Word *res, const Word *resEnd, const Word *a)
void freeTop(void *ptr)
Frees the buffer pointed to by ptr.
void removeGenerator(size_t index)
Removes the generator at index.
void colonReminimize(const Word *colon)
Performs a colon and minimize.
void swap01Exponents()
Change 0 exponents into 1 and vice versa.
size_t getVarCount() const
A bit packed square free ideal placed in a pre-allocated buffer.
RSFIdeal * newRawSquareFreeIdeal(size_t varCount, size_t capacity)
Allocates object with enough memory for capacity generators in varCount variables.
bool operator==(const RawSquareFreeIdeal &ideal) const
Returns true if *this equals ideal.
size_t getMultiple(size_t var) const
Returns the index of the first generator that var divides or getGeneratorCount() if no such generator...
Word * getGenerator(size_t index)
Returns the generator at index.
unsigned long Word
The native unsigned type for the CPU.
void getVarDividesCounts(vector< size_t > &counts) const
Sets counts[var] to the number of generators that var divides.
size_t getMinSupportGen() const
Returns the index of a generator with minimum support.
void sortLexAscending()
Sorts the generators in ascending lex order.
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
void colon(const Word *by)
void swap(size_t a, size_t b)
Word * newTermParse(const char *strParam)
Allocates and returns a term based on str.
Represents a monomial ideal with int exponents.
void deleteRawSquareFreeIdeal(RSFIdeal *ideal)
size_t getSizeOfSupport(const Word *a, size_t varCount)
size_t getWordOffset(size_t var)
void print(FILE *file) const
Print a debug-suitable representation of this object to file.
size_t getNotRelativelyPrime(const Word *term)
Returns the index of the first generator that is not relatively prime with term.
void transpose(Word *eraseVars=0)
Equivalent to setToTransposeOf(this, eraseVars).
size_t getWordsPerTerm() const
size_t getBitOffset(size_t var)
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.
size_t getGeneratorCount() const
RawSquareFreeIdeal * newRawSquareFreeIdealParse(const char *str)
Allocates and returns an ideal based on str.
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 getGcdOfMultiples(Word *gcd, size_t var) const
Sets gcd to be the greatest common denominator of those generators that are divisible by var.
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().
size_t getVarCount() const
void getLcm(Word *lcm) const
Puts the least common multiple of the generators of the ideal into lcm.
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
size_t getMaxSupportGen() const
Returns the index of a generator with maximum support.