33 _allocator(varCount) {
37 _varCount(term.getVarCount()),
38 _allocator(term.getVarCount()) {
43 _varCount(ideal.getVarCount()),
44 _allocator(ideal.getVarCount()) {
107 for (
size_t var = 0; var <
_varCount; ++var) {
113 if (lastExponent != 0 && lastExponent == (*it)[var])
115 lastExponent = (*it)[var];
133 goto foundStrictDivisor;
146 if ((*it)[var] > 0) {
173 for (++it; it != stop; ++it)
182 for (; it != stop; ++it) {
202 for (; it != stop; ++it) {
222 for (
size_t var = 0; var <
_varCount; ++var)
223 if (least[var] == 0 || ((*it)[var] < least[var] && (*it)[var] > 0))
224 least[var] = (*it)[var];
231 for (
size_t var = 0; var <
_varCount; ++var)
242 for (
size_t var = 0; var <
_varCount; ++var) {
253 if (lastExponent == exponent)
258 if (count > maxCount) {
261 typicalExponent = exponent;
264 lastExponent = exponent;
279 for (
size_t var = 0; var < _varCount; ++var) {
280 singleDegreeSort(var);
284 while (blockBegin != stop) {
285 Exponent blockExponent = (*blockBegin)[var];
289 }
while (blockEnd != stop && (*blockEnd)[var] == blockExponent);
296 size_t span = blockEnd - blockBegin;
297 if (blockExponent == 0 || (span * (span + 1)) / 2 <= maxCount) {
298 blockBegin = blockEnd;
302 size_t nonGenericCount = 0;
303 for (; blockBegin != blockEnd; ++blockBegin) {
305 for (++it; it != blockEnd; ++it) {
306 lcm.
lcm(*blockBegin, *it);
307 if (!strictlyContains(lcm)) {
314 if (nonGenericCount > maxCount) {
315 maxCount = nonGenericCount;
317 mostNGExponent = blockExponent;
333 for (
size_t var = 0; var < _varCount; ++var) {
334 singleDegreeSort(var);
338 while (blockBegin != stop) {
339 Exponent blockExponent = (*blockBegin)[var];
343 }
while (blockEnd != stop && (*blockEnd)[var] == blockExponent);
350 size_t count = blockEnd - blockBegin;
351 if (blockExponent == 0 || count <= maxCount) {
352 blockBegin = blockEnd;
356 for (; blockBegin != blockEnd; ++blockBegin) {
358 for (++it; it != blockEnd; ++it) {
359 lcm.
lcm(*blockBegin, *it);
360 if (!strictlyContains(lcm)) {
365 typicalExponent = blockExponent;
366 blockBegin = blockEnd;
385 for (
size_t var = 0; var < _varCount; ++var) {
386 singleDegreeSort(var);
390 while (blockBegin != stop) {
391 Exponent blockExponent = (*blockBegin)[var];
395 }
while (blockEnd != stop && (*blockEnd)[var] == blockExponent);
401 if (blockExponent == 0) {
402 blockBegin = blockEnd;
406 for (; blockBegin != blockEnd; ++blockBegin) {
408 for (++it; it != blockEnd; ++it) {
409 lcm.
lcm(*blockBegin, *it);
410 if (!strictlyContains(lcm)) {
413 ngExponent = blockExponent;
433 for (; it != stop; ++it, ++it2)
443 fputs(out.str().c_str(), file);
447 out <<
"//------------ Ideal:\n";
452 out <<
"------------\\\\\n";
458 copy(exponents, exponents +
_varCount, term);
554 pair<iterator, bool> pair =
567 pair<iterator, bool> pair =
593 _terms.erase(newEnd, stop);
600 if ((*it)[var] < e) {
605 _terms.erase(newEnd, stop);
631 _terms.erase(newEnd, stop);
655 for (
size_t var = 0; var <
_varCount; ++var)
656 if ((*it)[var] == zeroExponents[var])
663 for (
size_t var = 0; var <
_varCount; ++var)
707 return new Exponent[ExponentsPerChunk];
719 }
catch (
const bad_alloc&) {
725 for (
size_t i = 0; i <
_chunks.size(); ++i)
751 if (_chunkIterator +
_varCount > _chunkEnd) {
752 if (useSingleChunking()) {
755 _chunks.push_back(term);
767 _chunks.push_back(_chunkIterator);
776 ASSERT(_chunkIterator <= _chunkEnd);
784 if (useSingleChunking()) {
785 for (
size_t i = 0; i < _chunks.size(); ++i)
792 for (
size_t i = 0; i < _chunks.size(); ++i)
803 _chunks.swap(allocator.
_chunks);
void deallocate(Exponent *chunk)
bool isSquareFree() const
vector< Exponent * > _chunks
Cont::const_iterator const_iterator
size_t getTypicalNonGenericExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is the typical non-generic degree.
bool useSingleChunking() const
static void clearStaticCache()
Ideal caches memory allocated with new internally and reuses it to avoid calling new all the time...
iterator minimize(iterator begin, iterator end) const
const int ExponentsPerChunk
bool equals(const Word *a, const Word *b, size_t varCount)
Returns true if a equals b.
void product(const Exponent *term)
bool isIncomparable(const Exponent *term) const
void print(FILE *file) const
void insertNonMultiples(const Exponent *term, const Ideal &ideal)
void getSupportCounts(Exponent *counts) const
counts[var] will be the number of generators divisible by var.
bool isSquareFree() const
Ideal(size_t varCount=0)
Initialize this object to the zero ideal in varCount variables.
void getGcdOfMultiplesOf(Exponent *gcd, const Exponent *divisor)
Sets gcd to the greatest common divisor of those generators that are divisible by divisor...
Represents a monomial ideal with int exponents.
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
A predicate that sorts terms in weakly ascending order according to degree of the specified variable...
static bool strictlyDivides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a strictly divides b.
void colon(const Exponent *by)
ExponentAllocator _allocator
bool isMinimallyGenerated() const
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
Exponent * _chunkIterator
bool isWeaklyGeneric() const
static void product(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the product of a and b.
void swap(ExponentAllocator &allocator)
void singleDegreeSort(size_t var)
size_t getVarCount() const
bool containsIdentity() const
bool colonReminimize(const Exponent *colon)
void removeStrictMultiples(const Exponent *term)
vector< Exponent * > _chunks
vector< Exponent * > _terms
void mapExponentsToZeroNoMinimize(const Term &zeroExponents)
Replaces the exponents from zeroExponents with zero and does not remove any non-minimal generators th...
size_t getSizeOfSupport() const
const int MinTermsPerChunk
const_iterator end() const
void getGcdAtExponent(Exponent *gcd, size_t var, Exponent exp)
Sets gcd to the greatest common divisor of those generators that raise the variable var to the power ...
Ideal & operator=(const Ideal &ideal)
bool disjointSupport() const
Returns true if all pairs of generators have disjoint support.
bool operator==(const Ideal &ideal) const
Rereturns true if *this equals ideal.
static bool divides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a divides b.
void insertReminimize(const Exponent *term)
A predicate that compares for equality.
bool isIrreducible() const
class ChunkPool globalChunkPool
void getGcd(Exponent *gcd) const
Sets gcd to the greatest common divisor of all generators.
static void print(FILE *file, const Exponent *e, size_t varCount)
Writes e to file in a format suitable for debug output.
void reset(size_t newVarCount)
size_t getTypicalExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is the typical non-zero exponent.
void getLeastExponents(Exponent *least) const
static bool dominates(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a dominates b, i.e. whether b divides a.
static void gcd(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the greatest common divisor of a and b.
bool isMinimallyGenerated(const_iterator begin, const_iterator end)
void getLcm(Exponent *lcm) const
Sets lcm to the least common multiple of all generators.
const_iterator getMultiple(size_t var) const
bool strictlyContains(const Exponent *term) const
void remove(const_iterator it)
const_iterator begin() const
void removeMultiples(const Exponent *term)
static void colon(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to .
bool contains(const Exponent *term) const
static bool sharesNonZeroExponent(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether there is some such that .
void insert(const Exponent *term)
size_t getMostNonGenericExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is the most non-generic degree.
void takeRadicalNoMinimize()
Replaces all generators with their support and does not remove any non-minimal generators this may pr...
ExponentAllocator(size_t varCount)
static void lcm(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the least commom multiple of a and b.
bool getNonGenericExponent(size_t &var, Exponent &exp)
Sets var and exp such that var^exp is some non-generic degree.
Term represents a product of variables which does not include a coefficient.
A predicate that sorts according to reverse lexicographic order.
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
A predicate that sorts terms according to lexicographic order.
void clearAndSetVarCount(size_t varCount)
pair< iterator, bool > colonReminimize(iterator begin, iterator end, const Exponent *colon)
size_t getGeneratorCount() const