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
HashPolynomial(size_t varCount)27 HashPolynomial::HashPolynomial(size_t varCount):
28 _varCount(varCount) {
29 }
30
clearAndSetVarCount(size_t varCount)31 void HashPolynomial::clearAndSetVarCount(size_t varCount) {
32 _terms.clear();
33 _varCount = varCount;
34 }
35
add(const mpz_class & coef,const Term & term)36 void 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
add(bool plus,const Term & term)53 void 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
65 namespace {
66 /** Helper class for feedTo. */
67 class RefCompare {
68 public:
69 typedef HashMap<Term, mpz_class> TermMap;
operator ()(TermMap::const_iterator a,TermMap::const_iterator b)70 bool operator()(TermMap::const_iterator a, TermMap::const_iterator b) {
71 return lexCompare(a->first, b->first) > 0;
72 }
73 };
74 }
75
feedTo(const TermTranslator & translator,CoefBigTermConsumer & consumer,bool inCanonicalOrder) const76 void HashPolynomial::feedTo
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
getTermCount() const117 size_t HashPolynomial::getTermCount() const {
118 return _terms.size();
119 }
120