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