Term.h
Go to the documentation of this file.
/* Frobby: Software for monomial ideal computations.
Copyright (C) 2007 Bjarke Hammersholt Roune (www.broune.com)
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see http://www.gnu.org/licenses/.
*/
#ifndef TERM_GUARD
#define TERM_GUARD
#include <ostream>
class Term {
public:
Term(): _exponents(0), _varCount(0) {}
Term(const Term& term) {initialize(term._exponents, term._varCount);}
Term(const Exponent* exponents, size_t varCount) {
initialize(exponents, varCount);
}
Term(size_t varCount):
_varCount(varCount) {
if (varCount > 0) {
_exponents = allocate(varCount);
setToIdentity();
} else
_exponents = 0;
}
Term(const string& str);
~Term() {deallocate(_exponents, _varCount);}
operator Exponent*() {return _exponents;}
operator const Exponent*() const {return _exponents;}
Exponent* begin() {return _exponents;}
const Exponent* begin() const {return _exponents;}
Exponent* end() {return _exponents + _varCount;}
const Exponent* end() const {return _exponents + _varCount;}
size_t getVarCount() const {return _varCount;}
// We need all these versions to make everything work out on
// different platforms.
Exponent operator[](int offset) const {
ASSERT(0 <= offset);
ASSERT((unsigned int)offset < _varCount);
return _exponents[offset];
}
Exponent operator[](unsigned int offset) const {
ASSERT(offset < _varCount);
return _exponents[offset];
}
Exponent operator[](unsigned long offset) const {
ASSERT(offset < _varCount);
return _exponents[offset];
}
Exponent operator[](unsigned long long offset) const {
ASSERT(offset < _varCount);
return _exponents[offset];
}
Exponent& operator[](int offset) {
ASSERT(0 <= offset);
ASSERT((unsigned int)offset < _varCount);
return _exponents[offset];
}
Exponent& operator[](unsigned int offset) {
ASSERT(offset < _varCount);
return _exponents[offset];
}
Exponent& operator[](unsigned long offset) {
ASSERT(offset < _varCount);
return _exponents[offset];
}
Exponent& operator[](unsigned long long offset) {
ASSERT(offset < _varCount);
return _exponents[offset];
}
bool operator==(const Term& term) const {
ASSERT(_varCount == term._varCount);
return (*this) == term._exponents;
}
bool operator==(const Exponent* term) const;
bool operator!=(const Term& term) const {return !(*this == term);}
bool operator!=(const Exponent* term) const {return !(*this == term);}
Term& operator=(const Term& term) {
if (_varCount != term._varCount) {
Exponent* newBuffer = allocate(term._varCount);
deallocate(_exponents, _varCount);
_exponents = newBuffer;
_varCount = term._varCount;
}
ASSERT(_varCount == term._varCount);
return (*this) = term._exponents;
}
Term& operator=(const Exponent* exponents) {
IF_DEBUG(if (_varCount > 0)) // avoid copy asserting on null pointer
copy(exponents, exponents + _varCount, _exponents);
return *this;
}
inline static bool divides(const Exponent* a, const Exponent* b, size_t varCount) {
ASSERT(a != 0 || varCount == 0);
ASSERT(b != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var)
if (a[var] > b[var])
return false;
return true;
}
bool divides(const Term& term) const {
ASSERT(_varCount == term._varCount);
return divides(_exponents, term._exponents, _varCount);
}
bool divides(const Exponent* term) const {
return divides(_exponents, term, _varCount);
}
inline static bool dominates(const Exponent* a, const Exponent* b,
size_t varCount) {
ASSERT(a != 0 || varCount == 0);
ASSERT(b != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var)
if (a[var] < b[var])
return false;
return true;
}
bool dominates(const Term& term) const {
ASSERT(_varCount == term._varCount);
return dominates(_exponents, term._exponents, _varCount);
}
bool dominates(const Exponent* term) const {
return dominates(_exponents, term, _varCount);
}
inline static bool strictlyDivides(const Exponent* a, const Exponent* b,
size_t varCount) {
ASSERT(a != 0 || varCount == 0);
ASSERT(b != 0 || varCount == 0);
bool bIsIdentity = true;
for (size_t var = 0; var < varCount; ++var) {
if (a[var] >= b[var] && a[var] != 0)
return false;
if (b[var] != 0)
bIsIdentity = false;
}
return !bIsIdentity;
}
bool strictlyDivides(const Term& term) const {
ASSERT(_varCount == term._varCount);
return strictlyDivides(_exponents, term._exponents, _varCount);
}
bool strictlyDivides(const Exponent* term) const {
return strictlyDivides(_exponents, term, _varCount);
}
inline static void lcm(Exponent* res,
const Exponent* a, const Exponent* b,
size_t varCount) {
ASSERT(res != 0 || varCount == 0);
ASSERT(a != 0 || varCount == 0);
ASSERT(b != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var) {
if (a[var] > b[var])
res[var] = a[var];
else
res[var] = b[var];
}
}
void lcm(const Term& a, const Term& b, int position) {
ASSERT(_varCount == a._varCount);
ASSERT(_varCount == b._varCount);
lcm(_exponents + position,
a._exponents + position,
b._exponents + position,
_varCount - position);
}
void lcm(const Term& a, const Term& b) {
ASSERT(_varCount == a._varCount);
ASSERT(_varCount == b._varCount);
lcm(_exponents, a._exponents, b._exponents, _varCount);
}
void lcm(const Exponent* a, const Exponent* b) {
lcm(_exponents, a, b, _varCount);
}
inline static void gcd(Exponent* res,
const Exponent* a, const Exponent* b,
size_t varCount) {
ASSERT(res != 0 || varCount == 0);
ASSERT(a != 0 || varCount == 0);
ASSERT(b != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var) {
if (a[var] < b[var])
res[var] = a[var];
else
res[var] = b[var];
}
}
void gcd(const Term& a, const Term& b) {
ASSERT(_varCount == a._varCount);
ASSERT(_varCount == b._varCount);
gcd(a._exponents, b._exponents);
}
void gcd(const Exponent* a, const Exponent* b) {
gcd(_exponents, a, b, _varCount);
}
inline static void product(Exponent* res,
const Exponent* a, const Exponent* b,
size_t varCount) {
ASSERT(res != 0 || varCount == 0);
ASSERT(a != 0 || varCount == 0);
ASSERT(b != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var)
res[var] = a[var] + b[var];
}
void product(const Term& a, const Term& b) {
ASSERT(_varCount == a._varCount);
ASSERT(_varCount == b._varCount);
product(_exponents, a._exponents, b._exponents, _varCount);
}
void product(const Exponent* a, const Exponent* b) {
product(_exponents, a, b, _varCount);
}
inline static void setToIdentity(Exponent* res, size_t varCount) {
ASSERT(res != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var)
res[var] = 0;
}
void setToIdentity() {
setToIdentity(_exponents, _varCount);
}
inline static bool isIdentity(const Exponent* a, size_t varCount) {
ASSERT(a != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var)
if (a[var] != 0)
return false;
return true;
}
bool isIdentity() const {
return isIdentity(_exponents, _varCount);
}
inline static bool isSquareFree(const Exponent* a, size_t varCount) {
ASSERT(a != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var)
if (a[var] >= 2)
return false;
return true;
}
bool isSquareFree() const {
return isSquareFree(_exponents, _varCount);
}
inline static size_t getFirstNonZeroExponent(const Exponent* a, size_t varCount) {
ASSERT(a != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var)
if (a[var] != 0)
return var;
return varCount;
}
size_t getFirstNonZeroExponent() const {
return getFirstNonZeroExponent(_exponents, _varCount);
}
inline static size_t getMiddleNonZeroExponent(const Exponent* a, size_t varCount) {
ASSERT(a != 0 || varCount == 0);
size_t nonZeroOffset = getSizeOfSupport(a, varCount) / 2;
for (size_t var = 0; var < varCount; ++var) {
if (a[var] != 0) {
if (nonZeroOffset == 0)
return var;
--nonZeroOffset;
}
}
ASSERT(isIdentity(a, varCount));
return varCount;
}
size_t getMiddleNonZeroExponent() const {
return getMiddleNonZeroExponent(_exponents, _varCount);
}
inline static size_t getFirstMaxExponent(const Exponent* a, size_t varCount) {
ASSERT(a != 0 || varCount == 0);
size_t max = 0;
for (size_t var = 1; var < varCount; ++var)
if (a[max] < a[var])
max = var;
return max;
}
size_t getFirstMaxExponent() const {
return getFirstMaxExponent(_exponents, _varCount);
}
size_t getMaxExponent() const {
ASSERT(_varCount > 0);
return _exponents[getFirstMaxExponent()];
}
inline static size_t getSizeOfSupport(const Exponent* a, size_t varCount) {
ASSERT(a != 0 || varCount == 0);
size_t size = 0;
for (size_t var = 0; var < varCount; ++var)
if (a[var] != 0)
++size;
return size;
}
size_t getSizeOfSupport() const {
return getSizeOfSupport(_exponents, _varCount);
}
static bool sharesNonZeroExponent(const Exponent* a, const Exponent* b,
size_t varCount) {
for (size_t var = 0; var < varCount; ++var)
if (a[var] != 0 && a[var] == b[var])
return true;
return false;
}
inline static size_t getHashCode(const Exponent* a, size_t varCount) {
size_t hashCode = varCount;
for (size_t var = 0; var < varCount; ++var)
hashCode = 31 * hashCode + a[var];
return hashCode;
}
size_t getHashCode() const {
return getHashCode(_exponents, _varCount);
}
bool sharesNonZeroExponent(const Exponent* a) const {
return sharesNonZeroExponent(_exponents, a, _varCount);
}
bool sharesNonZeroExponent(const Term& a) const {
return sharesNonZeroExponent(a._exponents);
}
inline static bool hasSameSupport(const Exponent* a, const Exponent* b,
size_t varCount) {
ASSERT(a != 0 || varCount == 0);
ASSERT(b != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var) {
if (a[var] == 0) {
if (b[var] != 0)
return false;
} else {
ASSERT(a[var] != 0);
if (b[var] == 0)
return false;
}
}
return true;
}
bool hasSameSupport(const Term& a) const {
ASSERT(_varCount == a._varCount);
return hasSameSupport(a._exponents);
}
bool hasSameSupport(const Exponent* a) const {
return hasSameSupport(_exponents, a, _varCount);
}
inline static void colon(Exponent* res,
const Exponent* a, const Exponent* b,
size_t varCount) {
ASSERT(res != 0 || varCount == 0);
ASSERT(a != 0 || varCount == 0);
ASSERT(b != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var) {
if (a[var] > b[var])
res[var] = a[var] - b[var];
else
res[var] = 0;
}
}
void colon(const Term& a, const Term& b) {
ASSERT(_varCount == a._varCount);
ASSERT(_varCount == b._varCount);
colon(a._exponents, b._exponents);
}
void colon(const Exponent* a, const Exponent* b) {
colon(_exponents, a, b, _varCount);
}
inline static void encodedDual(Exponent* res,
const Exponent* dualOf, const Exponent* point,
size_t varCount) {
ASSERT(res != 0 || varCount == 0);
ASSERT(dualOf != 0 || varCount == 0);
ASSERT(point != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var) {
ASSERT(dualOf[var] <= point[var]);
if (dualOf[var] != 0)
res[var] = point[var] - dualOf[var] + 1;
else
res[var] = 0;
}
}
void encodedDual(const Term& dualOf, const Term& point) {
ASSERT(_varCount == dualOf._varCount);
ASSERT(_varCount == point._varCount);
encodedDual(dualOf._exponents, point._exponents);
}
void encodedDual(const Exponent* dualOf, const Exponent* point) {
encodedDual(_exponents, dualOf, point, _varCount);
}
inline static void decrement(Exponent* a, size_t varCount) {
ASSERT(a != 0 || varCount == 0);
for (size_t var = 0; var < varCount; ++var)
if (a[var] > 0)
a[var] -= 1;
}
void decrement() {
decrement(_exponents, _varCount);
}
void swap(Term& term) {
std::swap(_varCount, term._varCount);
Exponent* tmp = _exponents;
_exponents = term._exponents;
term._exponents = tmp;
}
void reset(size_t newVarCount) {
if (newVarCount != _varCount) {
Exponent* newBuffer = allocate(newVarCount);
deallocate(_exponents, _varCount);
_varCount = newVarCount;
_exponents = newBuffer;
}
setToIdentity();
}
void clear() {
deallocate(_exponents, _varCount);
_exponents = 0;
_varCount = 0;
}
static void print(FILE* file, const Exponent* e, size_t varCount);
static void print(ostream& out, const Exponent* e, size_t varCount);
void print(FILE* file) const {
print(file, _exponents, _varCount);
}
void print(ostream& out) const {
print(out, _exponents, _varCount);
}
private:
static Exponent* allocate(size_t size);
static void deallocate(Exponent* p, size_t size);
void initialize(const Exponent* exponents, size_t varCount) {
if (varCount > 0) {
ASSERT(exponents != 0);
_exponents = allocate(varCount);
copy(exponents, exponents + varCount, _exponents);
} else
_exponents = 0;
_varCount = varCount;
}
Exponent* _exponents;
size_t _varCount;
};
inline void swap(Term& a, Term& b) { a.swap(b); }
inline ostream& operator<<(ostream& out, const Term& term) {
term.print(out);
return out;
}
#endif
swap
void swap(Term &a, Term &b)
Definition Term.h:601
operator<<
ostream & operator<<(ostream &out, const Term &term)
Definition Term.h:604
Term
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
Term::lcm
void lcm(const Exponent *a, const Exponent *b)
Definition Term.h:250
Term::divides
bool divides(const Term &term) const
Definition Term.h:161
Term::product
void product(const Term &a, const Term &b)
Set this object equal to the product of a and b.
Definition Term.h:291
Term::getHashCode
static size_t getHashCode(const Exponent *a, size_t varCount)
Definition Term.h:424
Term::operator[]
Exponent & operator[](int offset)
Definition Term.h:107
Term::dominates
bool dominates(const Term &term) const
Definition Term.h:182
Term::operator[]
Exponent & operator[](unsigned long offset)
Definition Term.h:116
Term::getMiddleNonZeroExponent
size_t getMiddleNonZeroExponent() const
Definition Term.h:376
Term::reset
void reset(size_t newVarCount)
Definition Term.h:551
Term::decrement
static void decrement(Exponent *a, size_t varCount)
Decrements each positive entry of a by one.
Definition Term.h:532
Term::strictlyDivides
bool strictlyDivides(const Exponent *term) const
Definition Term.h:216
Term::_varCount
size_t _varCount
Definition Term.h:598
Term::divides
bool divides(const Exponent *term) const
Definition Term.h:166
Term::hasSameSupport
static bool hasSameSupport(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether for every variable .
Definition Term.h:446
Term::operator=
Term & operator=(const Term &term)
Definition Term.h:133
Term::operator[]
Exponent operator[](unsigned int offset) const
Definition Term.h:94
Term::getSizeOfSupport
static size_t getSizeOfSupport(const Exponent *a, size_t varCount)
Returns the number of variables such that divides .
Definition Term.h:402
Term::begin
Exponent * begin()
Definition Term.h:79
Term::operator==
bool operator==(const Term &term) const
Definition Term.h:125
Term::allocate
static Exponent * allocate(size_t size)
Definition Term.cpp:86
Term::operator[]
Exponent & operator[](unsigned long long offset)
Definition Term.h:120
Term::end
Exponent * end()
Definition Term.h:82
Term::encodedDual
static void encodedDual(Exponent *res, const Exponent *dualOf, const Exponent *point, size_t varCount)
The parameter dualOf is interpreted to encode an irreducible ideal, and the dual of that reflected in...
Definition Term.h:505
Term::operator[]
Exponent & operator[](unsigned int offset)
Definition Term.h:112
Term::isIdentity
bool isIdentity() const
Definition Term.h:324
Term::product
static void product(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to the product of a and b.
Definition Term.h:280
Term::print
void print(ostream &out) const
Definition Term.h:578
Term::deallocate
static void deallocate(Exponent *p, size_t size)
Definition Term.cpp:98
Term::getHashCode
size_t getHashCode() const
Definition Term.h:431
Term::product
void product(const Exponent *a, const Exponent *b)
Definition Term.h:297
Term::Term
Term()
Definition Term.h:51
Term::dominates
static bool dominates(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a dominates b, i.e. whether b divides a.
Definition Term.h:172
Term::strictlyDivides
static bool strictlyDivides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a strictly divides b.
Definition Term.h:196
Term::operator[]
Exponent operator[](unsigned long offset) const
Definition Term.h:98
Term::colon
void colon(const Exponent *a, const Exponent *b)
Definition Term.h:496
Term::setToIdentity
void setToIdentity()
Definition Term.h:310
Term::isSquareFree
bool isSquareFree() const
Definition Term.h:339
Term::begin
const Exponent * begin() const
Definition Term.h:80
Term::sharesNonZeroExponent
bool sharesNonZeroExponent(const Term &a) const
Definition Term.h:439
Term::end
const Exponent * end() const
Definition Term.h:83
Term::gcd
void gcd(const Term &a, const Term &b)
Definition Term.h:269
Term::getVarCount
size_t getVarCount() const
Definition Term.h:85
Term::print
static void print(FILE *file, const Exponent *e, size_t varCount)
Writes e to file in a format suitable for debug output.
Definition Term.cpp:110
Term::encodedDual
void encodedDual(const Term &dualOf, const Term &point)
Definition Term.h:521
Term::strictlyDivides
bool strictlyDivides(const Term &term) const
Definition Term.h:211
Term::dominates
bool dominates(const Exponent *term) const
Definition Term.h:187
Term::colon
static void colon(Exponent *res, const Exponent *a, const Exponent *b, size_t varCount)
Sets res equal to .
Definition Term.h:476
Term::swap
void swap(Term &term)
Definition Term.h:543
Term::getMiddleNonZeroExponent
static size_t getMiddleNonZeroExponent(const Exponent *a, size_t varCount)
Returns a median element of the set of var's such that a[var] is non-zero.
Definition Term.h:361
Term::lcm
void lcm(const Term &a, const Term &b, int position)
Definition Term.h:235
Term::getFirstNonZeroExponent
static size_t getFirstNonZeroExponent(const Exponent *a, size_t varCount)
Returns least var such that a[var] is non-zero.
Definition Term.h:346
Term::hasSameSupport
bool hasSameSupport(const Exponent *a) const
Definition Term.h:468
Term::isIdentity
static bool isIdentity(const Exponent *a, size_t varCount)
Returns whether a is 1, i.e. whether all entries of a are 0.
Definition Term.h:316
Term::hasSameSupport
bool hasSameSupport(const Term &a) const
Definition Term.h:463
Term::gcd
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.
Definition Term.h:255
Term::Term
Term(const Exponent *exponents, size_t varCount)
Definition Term.h:53
Term::operator[]
Exponent operator[](int offset) const
Definition Term.h:89
Term::clear
void clear()
Definition Term.h:562
Term::getFirstMaxExponent
size_t getFirstMaxExponent() const
Definition Term.h:390
Term::initialize
void initialize(const Exponent *exponents, size_t varCount)
Definition Term.h:587
Term::sharesNonZeroExponent
bool sharesNonZeroExponent(const Exponent *a) const
Definition Term.h:435
Term::getFirstNonZeroExponent
size_t getFirstNonZeroExponent() const
Definition Term.h:354
Term::print
void print(FILE *file) const
Definition Term.h:574
Term::getSizeOfSupport
size_t getSizeOfSupport() const
Definition Term.h:411
Term::divides
static bool divides(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether a divides b.
Definition Term.h:152
Term::Term
Term(const Term &term)
Definition Term.h:52
Term::colon
void colon(const Term &a, const Term &b)
Definition Term.h:490
Term::decrement
void decrement()
Definition Term.h:539
Term::isSquareFree
static bool isSquareFree(const Exponent *a, size_t varCount)
Returns whether a is square free, i.e. for each where .
Definition Term.h:331
Term::operator!=
bool operator!=(const Term &term) const
Definition Term.h:130
Term::operator[]
Exponent operator[](unsigned long long offset) const
Definition Term.h:102
Term::lcm
void lcm(const Term &a, const Term &b)
Definition Term.h:244
Term::operator!=
bool operator!=(const Exponent *term) const
Definition Term.h:131
Term::Term
Term(size_t varCount)
This object is initialized to the identity, i.e. the exponent vector is the zero vector.
Definition Term.h:60
Term::getFirstMaxExponent
static size_t getFirstMaxExponent(const Exponent *a, size_t varCount)
Returns a var such that a[var] >= a[i] for all i.
Definition Term.h:381
Term::getMaxExponent
size_t getMaxExponent() const
Definition Term.h:394
Term::gcd
void gcd(const Exponent *a, const Exponent *b)
Definition Term.h:275
Term::operator=
Term & operator=(const Exponent *exponents)
Definition Term.h:145
Term::_exponents
Exponent * _exponents
Definition Term.h:597
Term::sharesNonZeroExponent
static bool sharesNonZeroExponent(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether there is some such that .
Definition Term.h:416
Term::encodedDual
void encodedDual(const Exponent *dualOf, const Exponent *point)
Definition Term.h:527
Term::~Term
~Term()
Definition Term.h:74
Term::lcm
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.
Definition Term.h:221
Term::setToIdentity
static void setToIdentity(Exponent *res, size_t varCount)
Set res equal to , i.e. set each entry of res equal to 0.
Definition Term.h:304
Exponent
unsigned int Exponent
Definition stdinc.h:89
IF_DEBUG
#define IF_DEBUG(X)
Definition stdinc.h:85
ASSERT
#define ASSERT(X)
Definition stdinc.h:86