Frobby 0.9.5
HashPolynomial.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2009 University of Aarhus
3 Contact Bjarke Hammersholt Roune for license information (www.broune.com)
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see http://www.gnu.org/licenses/.
17*/
18#include "stdinc.h"
19#include "HashPolynomial.h"
20
21#include "CoefBigTermConsumer.h"
22#include "TermTranslator.h"
23#include "TermPredicate.h"
24#include <vector>
25#include <algorithm>
26
28 _varCount(varCount) {
29}
30
32 _terms.clear();
33 _varCount = varCount;
34}
35
36void HashPolynomial::add(const mpz_class& coef, const Term& term) {
37 ASSERT(_varCount == term.getVarCount());
38
39 if (coef == 0)
40 return;
41
42 // Doing it this way incurs the penalty of looking up term twice if
43 // ref ends up zero. I don't know how to avoid two look-ups in all
44 // cases, especially when the interface of _terms is not fixed,
45 // e.g. lowerbound doesn't exist for GCC's hash_map, so we can't use
46 // that.
47 mpz_class& ref = _terms[term];
48 ref += coef;
49 if (ref == 0)
50 _terms.erase(term);
51}
52
53void HashPolynomial::add(bool plus, const Term& term) {
54 ASSERT(_varCount == term.getVarCount());
55
56 mpz_class& ref = _terms[term];
57 if (plus)
58 ++ref;
59 else
60 --ref;
61 if (ref == 0)
62 _terms.erase(term);
63}
64
65namespace {
67 class RefCompare {
68 public:
69 typedef HashMap<Term, mpz_class> TermMap;
70 bool operator()(TermMap::const_iterator a, TermMap::const_iterator b) {
71 return lexCompare(a->first, b->first) > 0;
72 }
73 };
74}
75
77(const TermTranslator& translator,
78 CoefBigTermConsumer& consumer,
79 bool inCanonicalOrder) const {
80
81 consumer.consumeRing(translator.getNames());
82 consumer.beginConsuming();
83
84 if (!inCanonicalOrder) {
85 // Output the terms in whatever order _terms is storing them.
86 TermMap::const_iterator termsEnd = _terms.end();
87 TermMap::const_iterator it = _terms.begin();
88 for (; it != termsEnd; ++it)
89 consumer.consume(it->second, it->first, translator);
90 } else {
91
92 // Fill refs with references to the terms in order to sort
93 // them. We can't sort _terms since HashMap doesn't support that,
94 // so we have to sort references into _terms instead.
95 vector<TermMap::const_iterator> refs;
96 refs.reserve(_terms.size());
97
98 TermMap::const_iterator termsEnd = _terms.end();
99 TermMap::const_iterator it = _terms.begin();
100 for (; it != termsEnd; ++it)
101 refs.push_back(it);
102
103 // Sort the references.
104 sort(refs.begin(), refs.end(), RefCompare());
105
106 // Output the terms in the sorted order specified by refs.
107
108 vector<TermMap::const_iterator>::const_iterator refsEnd = refs.end();
109 vector<TermMap::const_iterator>::const_iterator refIt = refs.begin();
110 for (; refIt != refsEnd; ++refIt)
111 consumer.consume((*refIt)->second, (*refIt)->first, translator);
112 }
113
114 consumer.doneConsuming();
115}
116
118 return _terms.size();
119}
int lexCompare(const Exponent *a, const Exponent *b, size_t varCount)
Indicates how a relates to b according to the lexicographic term order where .
virtual void beginConsuming()=0
virtual void consume(const mpz_class &coef, const Term &term)
virtual void doneConsuming()=0
virtual void consumeRing(const VarNames &names)=0
void add(const mpz_class &coef, const Term &term)
Add coef*term to the polynomial.
size_t getTermCount() const
void clearAndSetVarCount(size_t varCount)
void feedTo(const TermTranslator &translator, CoefBigTermConsumer &consumer, bool inCanonicalOrder) const
HashPolynomial(size_t varCount=0)
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
const VarNames & getNames() const
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
size_t getVarCount() const
Definition: Term.h:85
#define ASSERT(X)
Definition: stdinc.h:86