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);
void sortLexAscending()
Sorts the generators in ascending lex order.
RawSquareFreeIdeal RSFIdeal
size_t getMaxSupportGen() const
Returns the index of a generator with maximum support.
void lcmInPlace(Word *res, const Word *resEnd, const Word *a)
void getVarDividesCounts(vector< size_t > &counts) const
Sets counts[var] to the number of generators that var divides.
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.
size_t getMinSupportGen() const
Returns the index of a generator with minimum support.
void colonReminimize(const Word *colon)
Performs a colon and minimize.
bool hasFullSupport(const Word *ignore) const
Returns true if for every variable it either divides ignore or it divides some (not necessarily minim...
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 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.
size_t getGeneratorCount() const
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.
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)
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
void setExponent(Word *a, size_t var, bool value)
size_t getGeneratorCount() const
size_t getVarCount() 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.
void getLcmOfNonMultiples(Word *lcm, size_t var) const
Sets lcm to be the least common multple of those generators that var does not divide.
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.
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 getWordsPerTerm() const
size_t getWordCount(size_t varCount)
void print(FILE *file) const
Print a debug-suitable representation of this object to file.
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.
void freeTop(void *ptr)
Frees the buffer pointed to by ptr.
bool operator==(const RawSquareFreeIdeal &ideal) const
Returns true if *this equals ideal.
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 getNonMultiple(size_t var) const
Returns the index of the first generator that var does not divide or getGeneratorCount() if no such g...
bool isMinimallyGenerated() const
Returns true if no generator divides another.
void assign(Word *a, const Word *b, size_t varCount)
void getLcm(Word *lcm) const
Puts the least common multiple of the generators of the ideal into lcm.
size_t getVarCount() const
bool isValid() const
Returns true if the internal invariants of ideal are satisfied.
size_t insert(const Ideal &ideal)
Inserts the generators of ideal from index 0 onward until reaching a non-squarefree generator or all ...
size_t getVarCount() const
size_t getMultiple(size_t var) const
Returns the index of the first generator that var divides or getGeneratorCount() if no such generator...
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 getGcdOfMultiples(Word *gcd, size_t var) const
Sets gcd to be the greatest common denominator of those generators that are divisible by var...
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)
size_t getGeneratorCount() const