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 #ifndef TERM_TRANSLATOR_GUARD 18 #define TERM_TRANSLATOR_GUARD 19 20 #include "VarNames.h" 21 22 #include <vector> 23 #include <ostream> 24 25 class BigIdeal; 26 class Ideal; 27 class Term; 28 29 /** TermTranslator handles translation between terms whose exponents 30 are infinite precision integers and terms whose exponents are 32 31 bit integers. 32 33 This is done by assigning the big integers IDs that are 32 bit 34 integers such that the assignment of IDs preserves order of 35 exponents for each variable. 36 37 The translation is done at the level of whole ideals. 38 39 The big integer 0 is always assigned the ID 0. 40 */ 41 class TermTranslator { 42 public: 43 /** Constructs a translator of varCount variables that translates each 44 number to itself, up to and not including upToExponent. 45 */ 46 TermTranslator(size_t varCount, size_t upToExponent); 47 48 /** Translates bigIdeal into ideal, and construct a translator to 49 translate back. sortVars indicates whether or not the order of the 50 variable names should be sorted. 51 */ 52 TermTranslator(const BigIdeal& bigIdeal, Ideal& ideal, bool sortVars = true); 53 54 /** Translates bigIdeals into ideals, while constructing a 55 translator to translate back. The variable names will be sorted, 56 and the ideals will be embedded in a ring with the union of all 57 variables present in bigIdeals. 58 */ 59 TermTranslator(const vector<BigIdeal*>& bigIdeals, vector<Ideal*>& ideals); 60 61 TermTranslator(const TermTranslator& translator); 62 ~TermTranslator(); 63 64 TermTranslator& operator=(const TermTranslator& translator); 65 66 /** This method translates from IDs to arbitrary precision integers. 67 */ 68 const mpz_class& getExponent(size_t variable, Exponent exponent) const; 69 70 /** This method translates from IDs to arbitrary precision integers. 71 */ 72 const mpz_class& getExponent(size_t variable, const Term& term) const; 73 74 /** As getExponent, except the string "var^e" is returned or null if 75 the exponent is zero, where var is the variable and e is the 76 exponent. 77 */ 78 const char* getVarExponentString(size_t variable, Exponent exponent) const; 79 80 /** as getExponent, except the string "e" is returned, where e is the 81 exponent. 82 */ 83 const char* getExponentString(size_t variable, Exponent exponent) const; 84 85 /** The assigned IDs are those in the range [0, getMaxId(var)]. As a 86 special case, getMaxId(var) maps to the same exponent as 0 87 does. */ 88 Exponent getMaxId(size_t variable) const; 89 90 /** Adds a generator of the form v^e, e > 0, for any variable v where 91 generator of that form is not already present. e is chosen to be 92 larger than any exponent (i.e. ID) already present, and it maps 93 to 0. Note that this does NOT preserve order - the highest ID 94 always maps to 0. The reason for this is that this is what is 95 needed for computing irreducible decompositions. 96 */ 97 void addPurePowersAtInfinity(Ideal& ideal) const; 98 99 /** The method addPurePowersAtInfinity adds high exponents that map to 100 zero. This method replaces those high powers with the power 101 zero. 102 */ 103 void setInfinityPowersToZero(Ideal& ideal) const; 104 105 const VarNames& getNames() const; 106 size_t getVarCount() const; 107 108 /** Replaces var^v by var^(a[i] - v) except that var^0 is left 109 alone. 110 */ 111 void dualize(const vector<mpz_class>& a); 112 113 /** Replaces var^v by var^(v-1). */ 114 void decrement(); 115 116 void renameVariables(const VarNames& names); 117 void swapVariables(size_t a, size_t b); 118 119 bool lessThanReverseLex(const Exponent* a, const Exponent* b) const; 120 121 void print(ostream& out) const; 122 string toString() const; 123 124 private: 125 void makeStrings(bool includeVar) const; 126 void clearStrings(); 127 128 void initialize(const vector<BigIdeal*>& bigIdeals, bool sortVars); 129 void shrinkBigIdeal(const BigIdeal& bigIdeal, Ideal& ideal) const; 130 Exponent shrinkExponent(size_t var, const mpz_class& exponent) const; 131 132 vector<vector<mpz_class> > _exponents; 133 mutable vector<vector<const char*> > _stringExponents; 134 mutable vector<vector<const char*> > _stringVarExponents; 135 VarNames _names; 136 }; 137 138 /** A predicate that sorts according to reverse lexicographic order 139 on the translated values of a term. 140 */ 141 class TranslatedReverseLexComparator { 142 public: TranslatedReverseLexComparator(const TermTranslator & translator)143 TranslatedReverseLexComparator(const TermTranslator& translator): 144 _translator(translator) { 145 } 146 147 bool operator()(const Term& a, const Term& b) const; 148 bool operator()(const Exponent* a, const Exponent* b) const; 149 150 private: 151 const TermTranslator& _translator; 152 }; 153 154 void setToZeroOne(TermTranslator& translator); 155 156 ostream& operator<<(ostream& out, const TermTranslator& translator); 157 158 #endif 159