Frobby 0.9.5
TermTranslator.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2007 Bjarke Hammersholt Roune (www.broune.com)
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see http://www.gnu.org/licenses/.
16*/
17#include "stdinc.h"
18#include "TermTranslator.h"
19
20#include "Term.h"
21#include "Ideal.h"
22#include "BigIdeal.h"
23#include "VarNames.h"
24#include "FrobbyStringStream.h"
25#include "ElementDeleter.h"
26
27#include <iterator>
28#include <algorithm>
29#include <sstream>
30#include <set>
31
32TermTranslator::TermTranslator(size_t varCount, size_t upToExponent):
33 _exponents(varCount),
34 _names(varCount) {
35 if (varCount > 0) {
36 _exponents[0].reserve(upToExponent + 1);
37 for (size_t i = 0; i < upToExponent; ++i)
38 _exponents[0].push_back(i);
39 _exponents[0].push_back(0);
40 for (size_t var = 1; var < varCount; ++var)
41 _exponents[var] = _exponents[0];
42 }
43}
44
46 bool sortVars) {
47 vector<BigIdeal*> bigIdeals;
48 bigIdeals.push_back(const_cast<BigIdeal*>(&bigIdeal));
49 initialize(bigIdeals, sortVars);
50
51 shrinkBigIdeal(bigIdeal, ideal);
52}
53
54TermTranslator::TermTranslator(const vector<BigIdeal*>& bigIdeals,
55 vector<Ideal*>& ideals) {
56 ASSERT(!bigIdeals.empty());
57
58 ideals.clear();
59 ElementDeleter<vector<Ideal*> > idealsDeleter(ideals);
60
61 initialize(bigIdeals, true);
62
63 for (size_t i = 0; i < bigIdeals.size(); ++i) {
64 exceptionSafePushBack(ideals, auto_ptr<Ideal>(new Ideal()));
65 shrinkBigIdeal(*(bigIdeals[i]), *(ideals.back()));
66 }
67 idealsDeleter.release();
68}
69
70// Helper function for extractExponents.
71bool mpzClassPointerLess(const mpz_class* a, const mpz_class* b) {
72 return *a < *b;
73}
74
75// Helper function for extractExponents.
76bool mpzClassPointerEqual(const mpz_class* a, const mpz_class* b) {
77 return *a == *b;
78}
79
80// Helper function for initialize.
81//
82// Assign int IDs to big integer exponents. The correspondence
83// preserves order, except that the largest ID maps to 0, which is
84// necessary to support adding pure powers. Only the exponents
85// that actually appear in generators of the ideals are translated,
86// except that 0 is guaranteed to be included and to be assigned the
87// ID 0, and that a maximal ID is added, which also maps to zero.
88//
89// extractExponents changes the exponents that it extracts.
90void extractExponents(const vector<BigIdeal*>& ideals,
91 vector<mpz_class>& exponents,
92 const string& varName) {
93 vector<mpz_class*> exponentRefs;
94
95 mpz_class zero(0);
96 exponentRefs.push_back(&zero); // 0 must be included
97
98 // Reserve sufficient capacity for the exponentRefs.
99 size_t termCount = 0;
100 for (size_t i = 0; i < ideals.size(); ++i)
101 termCount += ideals[i]->getGeneratorCount();
102 exponentRefs.reserve(termCount + 1); // + 1 because we added the 0 above.
103
104 // Collect the exponents
105 const int MaxSmall = 900;
106 bool seen[MaxSmall + 1]; // avoid adding small numbers more than once
107 fill_n(seen, MaxSmall + 1, false);
108 seen[0] = true;
109 for (size_t i = 0; i < ideals.size(); ++i) {
110 BigIdeal& ideal = *(ideals[i]);
111 size_t var = ideal.getNames().getIndex(varName);
112 if (var == VarNames::invalidIndex)
113 continue;
114
115 size_t generatorCount = ideal.getGeneratorCount();
116 for (size_t term = 0; term < generatorCount; ++term) {
117 const mpz_class& e = ideal.getExponent(term, var);
118 if (e <= MaxSmall) {
119 ASSERT(e.fits_uint_p());
120 unsigned int ui = e.get_ui();
121 if (seen[ui])
122 continue;
123 seen[ui] = true;
124 }
125 exponentRefs.push_back(&(ideal.getExponent(term, var)));
126 }
127 }
128
129 // Sort and remove duplicates.
130 std::sort(exponentRefs.begin(), exponentRefs.end(), mpzClassPointerLess);
131 exponentRefs.erase
132 (unique(exponentRefs.begin(), exponentRefs.end(), mpzClassPointerEqual),
133 exponentRefs.end());
134 exponentRefs.push_back(&zero);
135
136 exponents.clear();
137 exponents.resize(exponentRefs.size());
138 size_t size = exponentRefs.size();
139 for (size_t e = 0; e < size; ++e)
140 exponents[e] = *(exponentRefs[e]);
141}
142
144 for (size_t i = 0; i < _stringExponents.size(); ++i)
145 for (size_t j = 0; j < _stringExponents[i].size(); ++j)
146 delete[] _stringExponents[i][j];
147 _stringExponents.clear();
148
149 for (size_t i = 0; i < _stringVarExponents.size(); ++i)
150 for (size_t j = 0; j < _stringVarExponents[i].size(); ++j)
151 delete[] _stringVarExponents[i][j];
152 _stringVarExponents.clear();
153}
154
156(const string* a, const string* b) {
157 return *a < *b;
158}
159
161(const string* a, const string* b) {
162 return *a == *b;
163}
164
165void TermTranslator::initialize(const vector<BigIdeal*>& bigIdeals,
166 bool sortVars) {
167 ASSERT(!bigIdeals.empty());
168
169 if (sortVars) {
170 vector<const string*> variables;
171 for (size_t ideal = 0; ideal < bigIdeals.size(); ++ideal) {
172 const VarNames& names = bigIdeals[ideal]->getNames();
173 if (ideal != 0 && names == bigIdeals[ideal - 1]->getNames())
174 continue;
175 for (size_t var = 0; var < bigIdeals[ideal]->getVarCount(); ++var)
176 variables.push_back(&(names.getName(var)));
177 }
178 std::sort(variables.begin(), variables.end(),
180 variables.erase
181 (std::unique(variables.begin(), variables.end(),
183 variables.end());
184
185 for (vector<const string*>::const_iterator var = variables.begin();
186 var != variables.end(); ++var)
187 _names.addVar(**var);
188 } else {
189 ASSERT(bigIdeals.size() == 1);
190 _names = bigIdeals[0]->getNames();
191 }
192
193 _exponents.resize(_names.getVarCount());
194
195 for (size_t var = 0; var < _names.getVarCount(); ++var)
196 extractExponents(bigIdeals, _exponents[var], _names.getName(var));
197}
198
200 Ideal& ideal) const {
202
203 // Figure out how bigIdeal's names map onto _names.
204 vector<size_t> newVars;
205 newVars.reserve(bigIdeal.getVarCount());
206
207 if (bigIdeal.getNames() == _names) {
208 for (size_t var = 0; var < bigIdeal.getVarCount(); ++var)
209 newVars.push_back(var);
210 } else {
211 for (size_t var = 0; var < bigIdeal.getVarCount(); ++var) {
212 const string& name = bigIdeal.getNames().getName(var);
213 size_t newVar = _names.getIndex(name);
214 newVars.push_back(newVar);
215
217 }
218 }
219
220 // Insert generators after translating exponents and variables.
221 Term term(ideal.getVarCount());
222 size_t varCount = bigIdeal.getVarCount();
223 for (size_t i = 0; i < bigIdeal.getGeneratorCount(); ++i) {
224 for (size_t var = 0; var < varCount; ++var) {
225 size_t newVar = newVars[var];
226 term[newVar] = shrinkExponent(newVar, bigIdeal.getExponent(i, var));
227 }
228 ideal.insert(term);
229 }
230}
231
233 size_t varCount = ideal.getVarCount();
234
235 // Find out which variables already have pure powers.
236 vector<bool> hasPurePower(varCount);
237
238 Ideal::const_iterator stop = ideal.end();
239 for (Ideal::const_iterator term = ideal.begin(); term != stop; ++term) {
240 if (Term::getSizeOfSupport(*term, varCount) > 1)
241 continue;
242
243 size_t var = Term::getFirstNonZeroExponent(*term, varCount);
244 if (var == varCount)
245 return; // The ideal is <1> so we need add nothing.
246
247 hasPurePower[var] = true;
248 }
249
250 // Add any missing pure powers.
251 for (size_t var = 0; var < varCount; ++var) {
252 if (hasPurePower[var])
253 continue;
254
255 Term purePower(varCount);
256 purePower[var] = _exponents[var].size() - 1;
257 ideal.insert(purePower);
258 }
259}
260
265 size_t varCount = ideal.getVarCount();
266 Ideal::iterator term = ideal.begin();
267 while (term != ideal.end()) {
268 bool changed = false;
269 for (size_t var = 0; var < varCount; ++var) {
270 if ((*term)[var] == getMaxId(var)) {
271 ASSERT(getExponent(var, (*term)[var]) == 0);
272 (*term)[var] = 0;
273 changed = true;
274 }
275 }
276 ++term;
277 continue; // uhm... ?
278 if (changed && Term::isIdentity(*term, varCount)) {
279 bool last = (term + 1 == ideal.end());
280 ideal.remove(term);
281 if (last)
282 break;
283 } else
284 ++term;
285 }
286}
287
288void TermTranslator::dualize(const vector<mpz_class>& a) {
289 clearStrings();
290 for (size_t var = 0; var < _exponents.size(); ++var)
291 for (size_t exp = 0; exp < _exponents[var].size(); ++exp)
292 if (_exponents[var][exp] != 0)
293 _exponents[var][exp] = a[var] - _exponents[var][exp] + 1;
294}
295
297 clearStrings();
298 for (size_t var = 0; var < _exponents.size(); ++var)
299 for (size_t exp = 0; exp < _exponents[var].size(); ++exp)
300 _exponents[var][exp] -= 1;
301}
302
304 ASSERT(getVarCount() == names.getVarCount());
305
306 clearStrings();
307 _names = names;
308}
309
310void TermTranslator::swapVariables(size_t a, size_t b) {
311 ASSERT(a < getVarCount());
312 ASSERT(b < getVarCount());
313
314 if (a == b)
315 return;
316
318
319 if (!_stringExponents.empty())
321
322 if (!_stringVarExponents.empty())
324
325 _names.swapVariables(a, b);
326}
327
328void TermTranslator::print(ostream& out) const {
329 out << "TermTranslator(\n";
330 for (size_t var = 0; var < _exponents.size(); ++var) {
331 out << " var " << var + 1 << ':';
332 for (size_t e = 0; e < _exponents[var].size(); ++e) {
333 out << ' ' << _exponents[var][e];
334 }
335 out << '\n';
336 }
337 out << ")\n";
338}
339
341 ostringstream out;
342 print(out);
343 return out.str();
344}
345
346void TermTranslator::makeStrings(bool includeVar) const {
347 vector<vector<const char*> >& strings =
349
350 ASSERT(strings.empty());
351
352 strings.resize(_exponents.size());
353 for (unsigned int i = 0; i < _exponents.size(); ++i) {
354 strings[i].resize(_exponents[i].size());
355 for (unsigned int j = 0; j < _exponents[i].size(); ++j) {
356 char* str = 0;
357
358 if (_exponents[i][j] != 0 || !includeVar) {
360 if (!includeVar)
361 out << _exponents[i][j];
362 else {
363 out << _names.getName(i);
364 if (_exponents[i][j] != 1)
365 out << '^' << _exponents[i][j];
366 }
367
368 str = new char[out.str().size() + 1];
369 strcpy(str, out.str().c_str());
370 }
371 strings[i][j] = str;
372 }
373 }
374}
375
377 *this = translator;
378}
379
381 clearStrings();
382 _exponents = translator._exponents;
383 _names = translator._names;
384 return *this;
385}
386
388 clearStrings();
389}
390
391const mpz_class& TermTranslator::
392getExponent(size_t variable, Exponent exponent) const {
393 ASSERT(variable < _exponents.size());
394 ASSERT(exponent < _exponents[variable].size());
395
396 return _exponents[variable][exponent];
397}
398
400getVarExponentString(size_t variable, Exponent exponent) const {
401 ASSERT(variable < _exponents.size());
402 ASSERT(exponent < _exponents[variable].size());
403
404 if (_stringVarExponents.empty())
405 makeStrings(true);
406 return _stringVarExponents[variable][exponent];
407}
408
410getExponentString(size_t variable, Exponent exponent) const {
411 ASSERT(variable < _exponents.size());
412 ASSERT(exponent < _exponents[variable].size());
413
414 if (_stringExponents.empty())
415 makeStrings(false);
416 return _stringExponents[variable][exponent];
417}
418
419const mpz_class& TermTranslator::
420getExponent(size_t variable, const Term& term) const {
421 return getExponent(variable, term[variable]);
422}
423
424Exponent TermTranslator::getMaxId(size_t variable) const {
425 ASSERT(variable < _exponents.size());
426
427 return _exponents[variable].size() - 1;
428}
429
431 const mpz_class& exponent) const {
432 const vector<mpz_class>& exponents = _exponents[var];
433
434 // We subtract 1 from exponents.end() to skip past the 0 that is
435 // added there. Otherwise the range would not be sorted.
436 vector<mpz_class>::const_iterator it =
437 lower_bound(exponents.begin(), exponents.end() - 1, exponent);
438 ASSERT(*it == exponent);
439
440 return it - exponents.begin();
441}
442
444 return _names;
445}
446
448 return _names.getVarCount();
449}
450
452lessThanReverseLex(const Exponent* a, const Exponent* b) const {
453 size_t varCount = getVarCount();
454
455 for (size_t var = 0; var < varCount; ++var) {
456 const mpz_class& ae = getExponent(var, a[var]);
457 const mpz_class& be = getExponent(var, b[var]);
458
459 if (ae != be)
460 return ae > be;
461 }
462
463 return 0;
464}
465
467 const Term& b) const {
470 return operator()(a.begin(), b.begin());
471}
472
474 const Exponent* b) const {
475 ASSERT(a != 0 || _translator.getVarCount() == 0);
476 ASSERT(b != 0 || _translator.getVarCount() == 0);
477
478 return _translator.lessThanReverseLex(a, b);
479}
480
481void setToZeroOne(TermTranslator& translator) {
482 BigIdeal zeroOneIdeal(translator.getNames());
483 zeroOneIdeal.newLastTerm(); // Add term with all exponents zero.
484 zeroOneIdeal.newLastTerm(); // Add term with all exponents one.
485 for (size_t var = 0; var < translator.getVarCount(); ++var)
486 zeroOneIdeal.getLastTermExponentRef(var) = 1;
487
488 Ideal dummy;
489 translator = TermTranslator(zeroOneIdeal, dummy, false);
490}
491
492ostream& operator<<(ostream& out, const TermTranslator& translator) {
493 translator.print(out);
494 return out;
495}
void exceptionSafePushBack(Container &container, auto_ptr< Element > pointer)
void setToZeroOne(TermTranslator &translator)
bool mpzClassPointerLess(const mpz_class *a, const mpz_class *b)
ostream & operator<<(ostream &out, const TermTranslator &translator)
bool mpzClassPointerEqual(const mpz_class *a, const mpz_class *b)
void extractExponents(const vector< BigIdeal * > &ideals, vector< mpz_class > &exponents, const string &varName)
bool TermTranslatorInitializeHelper_StringPointerCompareLess(const string *a, const string *b)
bool TermTranslatorInitializeHelper_StringPointerCompareEqual(const string *a, const string *b)
void newLastTerm()
Definition: BigIdeal.cpp:104
mpz_class & getLastTermExponentRef(size_t var)
Definition: BigIdeal.h:126
size_t getVarCount() const
Definition: BigIdeal.h:148
const VarNames & getNames() const
Definition: BigIdeal.cpp:253
size_t getGeneratorCount() const
Definition: BigIdeal.h:144
const mpz_class & getExponent(size_t term, size_t var) const
Definition: BigIdeal.cpp:328
A replacement for stringstream.
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
void remove(const_iterator it)
Definition: Ideal.cpp:576
void clearAndSetVarCount(size_t varCount)
Definition: Ideal.cpp:646
Cont::const_iterator const_iterator
Definition: Ideal.h:43
void insert(const Exponent *term)
Definition: Ideal.cpp:455
const_iterator end() const
Definition: Ideal.h:49
const_iterator begin() const
Definition: Ideal.h:48
Cont::iterator iterator
Definition: Ideal.h:44
size_t getVarCount() const
Definition: Ideal.h:56
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
void swapVariables(size_t a, size_t b)
const mpz_class & getExponent(size_t variable, Exponent exponent) const
This method translates from IDs to arbitrary precision integers.
size_t getVarCount() const
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...
void renameVariables(const VarNames &names)
bool lessThanReverseLex(const Exponent *a, const Exponent *b) const
vector< vector< const char * > > _stringExponents
TermTranslator(size_t varCount, size_t upToExponent)
Constructs a translator of varCount variables that translates each number to itself,...
void makeStrings(bool includeVar) const
string toString() const
vector< vector< const char * > > _stringVarExponents
void dualize(const vector< mpz_class > &a)
Replaces var^v by var^(a[i] - v) except that var^0 is left alone.
TermTranslator & operator=(const TermTranslator &translator)
const char * getExponentString(size_t variable, Exponent exponent) const
as getExponent, except the string "e" is returned, where e is the exponent.
Exponent getMaxId(size_t variable) const
The assigned IDs are those in the range [0, getMaxId(var)].
Exponent shrinkExponent(size_t var, const mpz_class &exponent) const
void shrinkBigIdeal(const BigIdeal &bigIdeal, Ideal &ideal) const
vector< vector< mpz_class > > _exponents
void initialize(const vector< BigIdeal * > &bigIdeals, bool sortVars)
void setInfinityPowersToZero(Ideal &ideal) const
The method addPurePowersAtInfinity adds high exponents that map to zero.
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,...
void decrement()
Replaces var^v by var^(v-1).
void print(ostream &out) const
const VarNames & getNames() const
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
Exponent * begin()
Definition: Term.h:79
bool isIdentity() const
Definition: Term.h:324
size_t getVarCount() const
Definition: Term.h:85
size_t getFirstNonZeroExponent() const
Definition: Term.h:354
size_t getSizeOfSupport() const
Definition: Term.h:411
bool operator()(const Term &a, const Term &b) const
const TermTranslator & _translator
Defines the variables of a polynomial ring and facilities IO involving them.
Definition: VarNames.h:40
bool addVar(const string &name)
Adds the variable and returns true if name is not already a variable.
Definition: VarNames.cpp:44
size_t getVarCount() const
Returns the current number of variables.
Definition: VarNames.h:113
const string & getName(size_t index) const
The returned reference can become invalid next time addVar is called.
Definition: VarNames.cpp:100
void swapVariables(size_t a, size_t b)
Swaps the variables with indexes a and b.
Definition: VarNames.cpp:143
static const size_t invalidIndex
Returns a fixed variable offset that is always invalid.
Definition: VarNames.h:100
size_t getIndex(const string &name) const
Returns VarNames::invalidIndex() if name is not known.
Definition: VarNames.cpp:83
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
Definition: hashtable.h:740
unsigned int Exponent
Definition: stdinc.h:89
#define ASSERT(X)
Definition: stdinc.h:86