TermTranslator.cpp
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/.
*/
#include "stdinc.h"
#include "TermTranslator.h"
#include "Term.h"
#include "Ideal.h"
#include "BigIdeal.h"
#include "VarNames.h"
#include "FrobbyStringStream.h"
#include "ElementDeleter.h"
#include <iterator>
#include <algorithm>
#include <sstream>
#include <set>
TermTranslator::TermTranslator(size_t varCount, size_t upToExponent):
_exponents(varCount),
_names(varCount) {
if (varCount > 0) {
_exponents[0].reserve(upToExponent + 1);
for (size_t i = 0; i < upToExponent; ++i)
_exponents[0].push_back(i);
_exponents[0].push_back(0);
for (size_t var = 1; var < varCount; ++var)
_exponents[var] = _exponents[0];
}
}
TermTranslator::TermTranslator(const BigIdeal& bigIdeal, Ideal& ideal,
bool sortVars) {
vector<BigIdeal*> bigIdeals;
bigIdeals.push_back(const_cast<BigIdeal*>(&bigIdeal));
initialize(bigIdeals, sortVars);
shrinkBigIdeal(bigIdeal, ideal);
}
TermTranslator::TermTranslator(const vector<BigIdeal*>& bigIdeals,
vector<Ideal*>& ideals) {
ASSERT(!bigIdeals.empty());
ideals.clear();
ElementDeleter<vector<Ideal*> > idealsDeleter(ideals);
initialize(bigIdeals, true);
for (size_t i = 0; i < bigIdeals.size(); ++i) {
exceptionSafePushBack(ideals, unique_ptr<Ideal>(new Ideal()));
shrinkBigIdeal(*(bigIdeals[i]), *(ideals.back()));
}
idealsDeleter.release();
}
// Helper function for extractExponents.
bool mpzClassPointerLess(const mpz_class* a, const mpz_class* b) {
return *a < *b;
}
// Helper function for extractExponents.
bool mpzClassPointerEqual(const mpz_class* a, const mpz_class* b) {
return *a == *b;
}
// Helper function for initialize.
//
// Assign int IDs to big integer exponents. The correspondence
// preserves order, except that the largest ID maps to 0, which is
// necessary to support adding pure powers. Only the exponents
// that actually appear in generators of the ideals are translated,
// except that 0 is guaranteed to be included and to be assigned the
// ID 0, and that a maximal ID is added, which also maps to zero.
//
// extractExponents changes the exponents that it extracts.
void extractExponents(const vector<BigIdeal*>& ideals,
vector<mpz_class>& exponents,
const string& varName) {
vector<mpz_class*> exponentRefs;
mpz_class zero(0);
exponentRefs.push_back(&zero); // 0 must be included
// Reserve sufficient capacity for the exponentRefs.
size_t termCount = 0;
for (size_t i = 0; i < ideals.size(); ++i)
termCount += ideals[i]->getGeneratorCount();
exponentRefs.reserve(termCount + 1); // + 1 because we added the 0 above.
// Collect the exponents
const int MaxSmall = 900;
bool seen[MaxSmall + 1]; // avoid adding small numbers more than once
fill_n(seen, MaxSmall + 1, false);
seen[0] = true;
for (size_t i = 0; i < ideals.size(); ++i) {
BigIdeal& ideal = *(ideals[i]);
size_t var = ideal.getNames().getIndex(varName);
if (var == VarNames::invalidIndex)
continue;
size_t generatorCount = ideal.getGeneratorCount();
for (size_t term = 0; term < generatorCount; ++term) {
const mpz_class& e = ideal.getExponent(term, var);
if (e <= MaxSmall) {
ASSERT(e.fits_uint_p());
unsigned int ui = e.get_ui();
if (seen[ui])
continue;
seen[ui] = true;
}
exponentRefs.push_back(&(ideal.getExponent(term, var)));
}
}
// Sort and remove duplicates.
std::sort(exponentRefs.begin(), exponentRefs.end(), mpzClassPointerLess);
exponentRefs.erase
(unique(exponentRefs.begin(), exponentRefs.end(), mpzClassPointerEqual),
exponentRefs.end());
exponentRefs.push_back(&zero);
exponents.clear();
exponents.resize(exponentRefs.size());
size_t size = exponentRefs.size();
for (size_t e = 0; e < size; ++e)
exponents[e] = *(exponentRefs[e]);
}
void TermTranslator::clearStrings() {
for (size_t i = 0; i < _stringExponents.size(); ++i)
for (size_t j = 0; j < _stringExponents[i].size(); ++j)
delete[] _stringExponents[i][j];
_stringExponents.clear();
for (size_t i = 0; i < _stringVarExponents.size(); ++i)
for (size_t j = 0; j < _stringVarExponents[i].size(); ++j)
delete[] _stringVarExponents[i][j];
_stringVarExponents.clear();
}
bool TermTranslatorInitializeHelper_StringPointerCompareLess
(const string* a, const string* b) {
return *a < *b;
}
bool TermTranslatorInitializeHelper_StringPointerCompareEqual
(const string* a, const string* b) {
return *a == *b;
}
void TermTranslator::initialize(const vector<BigIdeal*>& bigIdeals,
bool sortVars) {
ASSERT(!bigIdeals.empty());
if (sortVars) {
vector<const string*> variables;
for (size_t ideal = 0; ideal < bigIdeals.size(); ++ideal) {
const VarNames& names = bigIdeals[ideal]->getNames();
if (ideal != 0 && names == bigIdeals[ideal - 1]->getNames())
continue;
for (size_t var = 0; var < bigIdeals[ideal]->getVarCount(); ++var)
variables.push_back(&(names.getName(var)));
}
std::sort(variables.begin(), variables.end(),
TermTranslatorInitializeHelper_StringPointerCompareLess);
variables.erase
(std::unique(variables.begin(), variables.end(),
TermTranslatorInitializeHelper_StringPointerCompareEqual),
variables.end());
for (vector<const string*>::const_iterator var = variables.begin();
var != variables.end(); ++var)
_names.addVar(**var);
} else {
ASSERT(bigIdeals.size() == 1);
_names = bigIdeals[0]->getNames();
}
_exponents.resize(_names.getVarCount());
for (size_t var = 0; var < _names.getVarCount(); ++var)
extractExponents(bigIdeals, _exponents[var], _names.getName(var));
}
void TermTranslator::shrinkBigIdeal(const BigIdeal& bigIdeal,
Ideal& ideal) const {
ideal.clearAndSetVarCount(_names.getVarCount());
// Figure out how bigIdeal's names map onto _names.
vector<size_t> newVars;
newVars.reserve(bigIdeal.getVarCount());
if (bigIdeal.getNames() == _names) {
for (size_t var = 0; var < bigIdeal.getVarCount(); ++var)
newVars.push_back(var);
} else {
for (size_t var = 0; var < bigIdeal.getVarCount(); ++var) {
const string& name = bigIdeal.getNames().getName(var);
size_t newVar = _names.getIndex(name);
newVars.push_back(newVar);
ASSERT(newVar != VarNames::invalidIndex);
}
}
// Insert generators after translating exponents and variables.
Term term(ideal.getVarCount());
size_t varCount = bigIdeal.getVarCount();
for (size_t i = 0; i < bigIdeal.getGeneratorCount(); ++i) {
for (size_t var = 0; var < varCount; ++var) {
size_t newVar = newVars[var];
term[newVar] = shrinkExponent(newVar, bigIdeal.getExponent(i, var));
}
ideal.insert(term);
}
}
void TermTranslator::addPurePowersAtInfinity(Ideal& ideal) const {
size_t varCount = ideal.getVarCount();
// Find out which variables already have pure powers.
vector<bool> hasPurePower(varCount);
Ideal::const_iterator stop = ideal.end();
for (Ideal::const_iterator term = ideal.begin(); term != stop; ++term) {
if (Term::getSizeOfSupport(*term, varCount) > 1)
continue;
size_t var = Term::getFirstNonZeroExponent(*term, varCount);
if (var == varCount)
return; // The ideal is <1> so we need add nothing.
hasPurePower[var] = true;
}
// Add any missing pure powers.
for (size_t var = 0; var < varCount; ++var) {
if (hasPurePower[var])
continue;
Term purePower(varCount);
purePower[var] = _exponents[var].size() - 1;
ideal.insert(purePower);
}
}
void TermTranslator::setInfinityPowersToZero(Ideal& ideal) const {
size_t varCount = ideal.getVarCount();
Ideal::iterator term = ideal.begin();
while (term != ideal.end()) {
bool changed = false;
for (size_t var = 0; var < varCount; ++var) {
if ((*term)[var] == getMaxId(var)) {
ASSERT(getExponent(var, (*term)[var]) == 0);
(*term)[var] = 0;
changed = true;
}
}
++term;
continue; // uhm... ?
if (changed && Term::isIdentity(*term, varCount)) {
bool last = (term + 1 == ideal.end());
ideal.remove(term);
if (last)
break;
} else
++term;
}
}
void TermTranslator::dualize(const vector<mpz_class>& a) {
clearStrings();
for (size_t var = 0; var < _exponents.size(); ++var)
for (size_t exp = 0; exp < _exponents[var].size(); ++exp)
if (_exponents[var][exp] != 0)
_exponents[var][exp] = a[var] - _exponents[var][exp] + 1;
}
void TermTranslator::decrement() {
clearStrings();
for (size_t var = 0; var < _exponents.size(); ++var)
for (size_t exp = 0; exp < _exponents[var].size(); ++exp)
_exponents[var][exp] -= 1;
}
void TermTranslator::renameVariables(const VarNames& names) {
ASSERT(getVarCount() == names.getVarCount());
clearStrings();
_names = names;
}
void TermTranslator::swapVariables(size_t a, size_t b) {
ASSERT(a < getVarCount());
ASSERT(b < getVarCount());
if (a == b)
return;
std::swap(_exponents[a], _exponents[b]);
if (!_stringExponents.empty())
std::swap(_stringExponents[a], _stringExponents[b]);
if (!_stringVarExponents.empty())
std::swap(_stringVarExponents[a], _stringVarExponents[b]);
_names.swapVariables(a, b);
}
void TermTranslator::print(ostream& out) const {
out << "TermTranslator(\n";
for (size_t var = 0; var < _exponents.size(); ++var) {
out << " var " << var + 1 << ':';
for (size_t e = 0; e < _exponents[var].size(); ++e) {
out << ' ' << _exponents[var][e];
}
out << '\n';
}
out << ")\n";
}
string TermTranslator::toString() const {
ostringstream out;
print(out);
return out.str();
}
void TermTranslator::makeStrings(bool includeVar) const {
vector<vector<const char*> >& strings =
includeVar ? _stringVarExponents : _stringExponents;
ASSERT(strings.empty());
strings.resize(_exponents.size());
for (unsigned int i = 0; i < _exponents.size(); ++i) {
strings[i].resize(_exponents[i].size());
for (unsigned int j = 0; j < _exponents[i].size(); ++j) {
char* str = 0;
if (_exponents[i][j] != 0 || !includeVar) {
FrobbyStringStream out;
if (!includeVar)
out << _exponents[i][j];
else {
out << _names.getName(i);
if (_exponents[i][j] != 1)
out << '^' << _exponents[i][j];
}
str = new char[out.str().size() + 1];
strcpy(str, out.str().c_str());
}
strings[i][j] = str;
}
}
}
TermTranslator::TermTranslator(const TermTranslator& translator) {
*this = translator;
}
TermTranslator& TermTranslator::operator=(const TermTranslator& translator) {
clearStrings();
_exponents = translator._exponents;
_names = translator._names;
return *this;
}
TermTranslator::~TermTranslator() {
clearStrings();
}
const mpz_class& TermTranslator::
getExponent(size_t variable, Exponent exponent) const {
ASSERT(variable < _exponents.size());
ASSERT(exponent < _exponents[variable].size());
return _exponents[variable][exponent];
}
const char* TermTranslator::
getVarExponentString(size_t variable, Exponent exponent) const {
ASSERT(variable < _exponents.size());
ASSERT(exponent < _exponents[variable].size());
if (_stringVarExponents.empty())
makeStrings(true);
return _stringVarExponents[variable][exponent];
}
const char* TermTranslator::
getExponentString(size_t variable, Exponent exponent) const {
ASSERT(variable < _exponents.size());
ASSERT(exponent < _exponents[variable].size());
if (_stringExponents.empty())
makeStrings(false);
return _stringExponents[variable][exponent];
}
const mpz_class& TermTranslator::
getExponent(size_t variable, const Term& term) const {
return getExponent(variable, term[variable]);
}
Exponent TermTranslator::getMaxId(size_t variable) const {
ASSERT(variable < _exponents.size());
return _exponents[variable].size() - 1;
}
Exponent TermTranslator::shrinkExponent(size_t var,
const mpz_class& exponent) const {
const vector<mpz_class>& exponents = _exponents[var];
// We subtract 1 from exponents.end() to skip past the 0 that is
// added there. Otherwise the range would not be sorted.
vector<mpz_class>::const_iterator it =
lower_bound(exponents.begin(), exponents.end() - 1, exponent);
ASSERT(*it == exponent);
return it - exponents.begin();
}
const VarNames& TermTranslator::getNames() const {
return _names;
}
size_t TermTranslator::getVarCount() const {
return _names.getVarCount();
}
bool TermTranslator::
lessThanReverseLex(const Exponent* a, const Exponent* b) const {
size_t varCount = getVarCount();
for (size_t var = 0; var < varCount; ++var) {
const mpz_class& ae = getExponent(var, a[var]);
const mpz_class& be = getExponent(var, b[var]);
if (ae != be)
return ae > be;
}
return 0;
}
bool TranslatedReverseLexComparator::operator()(const Term& a,
const Term& b) const {
ASSERT(a.getVarCount() == _translator.getVarCount());
ASSERT(b.getVarCount() == _translator.getVarCount());
return operator()(a.begin(), b.begin());
}
bool TranslatedReverseLexComparator::operator()(const Exponent* a,
const Exponent* b) const {
ASSERT(a != 0 || _translator.getVarCount() == 0);
ASSERT(b != 0 || _translator.getVarCount() == 0);
return _translator.lessThanReverseLex(a, b);
}
void setToZeroOne(TermTranslator& translator) {
BigIdeal zeroOneIdeal(translator.getNames());
zeroOneIdeal.newLastTerm(); // Add term with all exponents zero.
zeroOneIdeal.newLastTerm(); // Add term with all exponents one.
for (size_t var = 0; var < translator.getVarCount(); ++var)
zeroOneIdeal.getLastTermExponentRef(var) = 1;
Ideal dummy;
translator = TermTranslator(zeroOneIdeal, dummy, false);
}
ostream& operator<<(ostream& out, const TermTranslator& translator) {
translator.print(out);
return out;
}
BigIdeal.h
ElementDeleter.h
exceptionSafePushBack
void exceptionSafePushBack(Container &container, unique_ptr< Element > pointer)
Definition ElementDeleter.h:129
FrobbyStringStream.h
Ideal.h
setToZeroOne
void setToZeroOne(TermTranslator &translator)
Definition TermTranslator.cpp:481
mpzClassPointerLess
bool mpzClassPointerLess(const mpz_class *a, const mpz_class *b)
Definition TermTranslator.cpp:71
operator<<
ostream & operator<<(ostream &out, const TermTranslator &translator)
Definition TermTranslator.cpp:492
mpzClassPointerEqual
bool mpzClassPointerEqual(const mpz_class *a, const mpz_class *b)
Definition TermTranslator.cpp:76
extractExponents
void extractExponents(const vector< BigIdeal * > &ideals, vector< mpz_class > &exponents, const string &varName)
Definition TermTranslator.cpp:90
TermTranslatorInitializeHelper_StringPointerCompareLess
bool TermTranslatorInitializeHelper_StringPointerCompareLess(const string *a, const string *b)
Definition TermTranslator.cpp:156
TermTranslatorInitializeHelper_StringPointerCompareEqual
bool TermTranslatorInitializeHelper_StringPointerCompareEqual(const string *a, const string *b)
Definition TermTranslator.cpp:161
TermTranslator.h
Term.h
VarNames.h
BigIdeal
Definition BigIdeal.h:27
BigIdeal::newLastTerm
void newLastTerm()
Definition BigIdeal.cpp:104
BigIdeal::getLastTermExponentRef
mpz_class & getLastTermExponentRef(size_t var)
Definition BigIdeal.h:126
BigIdeal::getVarCount
size_t getVarCount() const
Definition BigIdeal.h:148
BigIdeal::getNames
const VarNames & getNames() const
Definition BigIdeal.cpp:253
BigIdeal::getGeneratorCount
size_t getGeneratorCount() const
Definition BigIdeal.h:144
BigIdeal::getExponent
const mpz_class & getExponent(size_t term, size_t var) const
Definition BigIdeal.cpp:328
ElementDeleter
Definition ElementDeleter.h:50
ElementDeleter::release
void release()
Definition ElementDeleter.h:65
FrobbyStringStream
A replacement for stringstream.
Definition FrobbyStringStream.h:26
FrobbyStringStream::str
string & str()
Definition FrobbyStringStream.cpp:74
Ideal
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Ideal::remove
void remove(const_iterator it)
Definition Ideal.cpp:576
Ideal::clearAndSetVarCount
void clearAndSetVarCount(size_t varCount)
Definition Ideal.cpp:646
Ideal::const_iterator
Cont::const_iterator const_iterator
Definition Ideal.h:43
Ideal::insert
void insert(const Exponent *term)
Definition Ideal.cpp:455
Ideal::end
const_iterator end() const
Definition Ideal.h:49
Ideal::begin
const_iterator begin() const
Definition Ideal.h:48
Ideal::iterator
Cont::iterator iterator
Definition Ideal.h:44
Ideal::getVarCount
size_t getVarCount() const
Definition Ideal.h:56
TermTranslator
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
Definition TermTranslator.h:41
TermTranslator::swapVariables
void swapVariables(size_t a, size_t b)
Definition TermTranslator.cpp:310
TermTranslator::getExponent
const mpz_class & getExponent(size_t variable, Exponent exponent) const
This method translates from IDs to arbitrary precision integers.
Definition TermTranslator.cpp:392
TermTranslator::getVarCount
size_t getVarCount() const
Definition TermTranslator.cpp:447
TermTranslator::addPurePowersAtInfinity
void addPurePowersAtInfinity(Ideal &ideal) const
Adds a generator of the form v^e, e > 0, for any variable v where generator of that form is not alrea...
Definition TermTranslator.cpp:232
TermTranslator::renameVariables
void renameVariables(const VarNames &names)
Definition TermTranslator.cpp:303
TermTranslator::lessThanReverseLex
bool lessThanReverseLex(const Exponent *a, const Exponent *b) const
Definition TermTranslator.cpp:452
TermTranslator::_stringExponents
vector< vector< const char * > > _stringExponents
Definition TermTranslator.h:133
TermTranslator::TermTranslator
TermTranslator(size_t varCount, size_t upToExponent)
Constructs a translator of varCount variables that translates each number to itself,...
Definition TermTranslator.cpp:32
TermTranslator::makeStrings
void makeStrings(bool includeVar) const
Definition TermTranslator.cpp:346
TermTranslator::toString
string toString() const
Definition TermTranslator.cpp:340
TermTranslator::_stringVarExponents
vector< vector< const char * > > _stringVarExponents
Definition TermTranslator.h:134
TermTranslator::dualize
void dualize(const vector< mpz_class > &a)
Replaces var^v by var^(a[i] - v) except that var^0 is left alone.
Definition TermTranslator.cpp:288
TermTranslator::operator=
TermTranslator & operator=(const TermTranslator &translator)
Definition TermTranslator.cpp:380
TermTranslator::getExponentString
const char * getExponentString(size_t variable, Exponent exponent) const
as getExponent, except the string "e" is returned, where e is the exponent.
Definition TermTranslator.cpp:410
TermTranslator::clearStrings
void clearStrings()
Definition TermTranslator.cpp:143
TermTranslator::getMaxId
Exponent getMaxId(size_t variable) const
The assigned IDs are those in the range [0, getMaxId(var)].
Definition TermTranslator.cpp:424
TermTranslator::shrinkExponent
Exponent shrinkExponent(size_t var, const mpz_class &exponent) const
Definition TermTranslator.cpp:430
TermTranslator::shrinkBigIdeal
void shrinkBigIdeal(const BigIdeal &bigIdeal, Ideal &ideal) const
Definition TermTranslator.cpp:199
TermTranslator::_exponents
vector< vector< mpz_class > > _exponents
Definition TermTranslator.h:132
TermTranslator::initialize
void initialize(const vector< BigIdeal * > &bigIdeals, bool sortVars)
Definition TermTranslator.cpp:165
TermTranslator::~TermTranslator
~TermTranslator()
Definition TermTranslator.cpp:387
TermTranslator::setInfinityPowersToZero
void setInfinityPowersToZero(Ideal &ideal) const
The method addPurePowersAtInfinity adds high exponents that map to zero.
Definition TermTranslator.cpp:264
TermTranslator::getVarExponentString
const char * getVarExponentString(size_t variable, Exponent exponent) const
As getExponent, except the string "var^e" is returned or null if the exponent is zero,...
Definition TermTranslator.cpp:400
TermTranslator::decrement
void decrement()
Replaces var^v by var^(v-1).
Definition TermTranslator.cpp:296
TermTranslator::print
void print(ostream &out) const
Definition TermTranslator.cpp:328
TermTranslator::_names
VarNames _names
Definition TermTranslator.h:135
TermTranslator::getNames
const VarNames & getNames() const
Definition TermTranslator.cpp:443
Term
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
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::getVarCount
size_t getVarCount() const
Definition Term.h:85
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::getFirstNonZeroExponent
size_t getFirstNonZeroExponent() const
Definition Term.h:354
TranslatedReverseLexComparator::operator()
bool operator()(const Term &a, const Term &b) const
Definition TermTranslator.cpp:466
TranslatedReverseLexComparator::_translator
const TermTranslator & _translator
Definition TermTranslator.h:151
VarNames
Defines the variables of a polynomial ring and facilities IO involving them.
Definition VarNames.h:40
VarNames::getVarCount
size_t getVarCount() const
Returns the current number of variables.
Definition VarNames.h:113
VarNames::getName
const string & getName(size_t index) const
The returned reference can become invalid next time addVar is called.
Definition VarNames.cpp:100
VarNames::invalidIndex
static const size_t invalidIndex
Returns a fixed variable offset that is always invalid.
Definition VarNames.h:100
VarNames::getIndex
size_t getIndex(const string &name) const
Returns VarNames::invalidIndex() if name is not known.
Definition VarNames.cpp:83
stdinc.h
This header file includes common definitions and is included as the first line of code in every imple...
Exponent
unsigned int Exponent
Definition stdinc.h:89
ASSERT
#define ASSERT(X)
Definition stdinc.h:86