HashPolynomial.cpp
Go to the documentation of this file.
/* Frobby: Software for monomial ideal computations.
Copyright (C) 2009 University of Aarhus
Contact Bjarke Hammersholt Roune for license information (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 "HashPolynomial.h"
#include "CoefBigTermConsumer.h"
#include "TermTranslator.h"
#include "TermPredicate.h"
#include <vector>
#include <algorithm>
HashPolynomial::HashPolynomial(size_t varCount):
_varCount(varCount) {
}
void HashPolynomial::clearAndSetVarCount(size_t varCount) {
_terms.clear();
_varCount = varCount;
}
void HashPolynomial::add(const mpz_class& coef, const Term& term) {
ASSERT(_varCount == term.getVarCount());
if (coef == 0)
return;
// Doing it this way incurs the penalty of looking up term twice if
// ref ends up zero. I don't know how to avoid two look-ups in all
// cases, especially when the interface of _terms is not fixed,
// e.g. lowerbound doesn't exist for GCC's hash_map, so we can't use
// that.
mpz_class& ref = _terms[term];
ref += coef;
if (ref == 0)
_terms.erase(term);
}
void HashPolynomial::add(bool plus, const Term& term) {
ASSERT(_varCount == term.getVarCount());
mpz_class& ref = _terms[term];
if (plus)
++ref;
else
--ref;
if (ref == 0)
_terms.erase(term);
}
namespace {
class RefCompare {
public:
typedef HashMap<Term, mpz_class> TermMap;
bool operator()(TermMap::const_iterator a, TermMap::const_iterator b) {
return lexCompare(a->first, b->first) > 0;
}
};
}
void HashPolynomial::feedTo
(const TermTranslator& translator,
CoefBigTermConsumer& consumer,
bool inCanonicalOrder) const {
consumer.consumeRing(translator.getNames());
consumer.beginConsuming();
if (!inCanonicalOrder) {
// Output the terms in whatever order _terms is storing them.
TermMap::const_iterator termsEnd = _terms.end();
TermMap::const_iterator it = _terms.begin();
for (; it != termsEnd; ++it)
consumer.consume(it->second, it->first, translator);
} else {
// Fill refs with references to the terms in order to sort
// them. We can't sort _terms since HashMap doesn't support that,
// so we have to sort references into _terms instead.
vector<TermMap::const_iterator> refs;
refs.reserve(_terms.size());
TermMap::const_iterator termsEnd = _terms.end();
TermMap::const_iterator it = _terms.begin();
for (; it != termsEnd; ++it)
refs.push_back(it);
// Sort the references.
sort(refs.begin(), refs.end(), RefCompare());
// Output the terms in the sorted order specified by refs.
vector<TermMap::const_iterator>::const_iterator refsEnd = refs.end();
vector<TermMap::const_iterator>::const_iterator refIt = refs.begin();
for (; refIt != refsEnd; ++refIt)
consumer.consume((*refIt)->second, (*refIt)->first, translator);
}
consumer.doneConsuming();
}
size_t HashPolynomial::getTermCount() const {
return _terms.size();
}
CoefBigTermConsumer.h
HashPolynomial.h
lexCompare
int lexCompare(const Exponent *a, const Exponent *b, size_t varCount)
Indicates how a relates to b according to the lexicographic term order where .
Definition TermPredicate.cpp:50
TermPredicate.h
TermTranslator.h
CoefBigTermConsumer
Definition CoefBigTermConsumer.h:29
CoefBigTermConsumer::beginConsuming
virtual void beginConsuming()=0
CoefBigTermConsumer::consume
virtual void consume(const mpz_class &coef, const Term &term)
Definition CoefBigTermConsumer.cpp:25
CoefBigTermConsumer::doneConsuming
virtual void doneConsuming()=0
CoefBigTermConsumer::consumeRing
virtual void consumeRing(const VarNames &names)=0
HashMap
Definition HashMap.h:93
HashPolynomial::add
void add(const mpz_class &coef, const Term &term)
Add coef*term to the polynomial.
Definition HashPolynomial.cpp:36
HashPolynomial::getTermCount
size_t getTermCount() const
Definition HashPolynomial.cpp:117
HashPolynomial::_varCount
size_t _varCount
Definition HashPolynomial.h:62
HashPolynomial::clearAndSetVarCount
void clearAndSetVarCount(size_t varCount)
Definition HashPolynomial.cpp:31
HashPolynomial::_terms
TermMap _terms
Definition HashPolynomial.h:65
HashPolynomial::feedTo
void feedTo(const TermTranslator &translator, CoefBigTermConsumer &consumer, bool inCanonicalOrder) const
Definition HashPolynomial.cpp:77
HashPolynomial::HashPolynomial
HashPolynomial(size_t varCount=0)
Definition HashPolynomial.cpp:27
TermTranslator
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
Definition TermTranslator.h:41
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::getVarCount
size_t getVarCount() const
Definition Term.h:85
stdinc.h
This header file includes common definitions and is included as the first line of code in every imple...
ASSERT
#define ASSERT(X)
Definition stdinc.h:86