Frobby 0.9.5
IdealOrderer.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2010 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 "IdealOrderer.h"
20
21#include "Ideal.h"
22#include "TermPredicate.h"
23#include "IdealOrderer.h"
24#include "NameFactory.h"
25#include "TermExtra.h"
26#include "ElementDeleter.h"
27
28#include <algorithm>
29#include <iterator>
30#include <map>
31
34
35namespace {
36 template<class Pred>
37 class IdealSorter : public IdealOrderer {
38 public:
39 static const char* staticGetName() {
40 return Pred::staticGetName();
41 }
42
43 private:
44 virtual void doOrder(Ideal& ideal) const {
45 Pred pred;
46 pred.setVarCount(ideal.getVarCount());
47 stable_sort(ideal.begin(), ideal.end(), pred);
48 }
49 };
50
51 class RandomOrderer : public IdealOrderer {
52 public:
53 static const char* staticGetName() {return "random";}
54 private:
55 void doOrder(Ideal& ideal) const {
56 random_shuffle(ideal.begin(), ideal.end());
57 }
58 };
59
60 class TotalDegreeComparator : public TermPredicate {
61 public:
62 static const char* staticGetName() {return "tdeg";}
63 private:
64 virtual bool doPredicate(const Exponent* a,
65 const Exponent* b) const {
66 totalDegree(_degA, a, getVarCount());
67 totalDegree(_degB, b, getVarCount());
68 return _degA < _degB;
69 }
70 mutable mpz_class _degA; // member to avoid repeated allocation
71 mutable mpz_class _degB;
72 };
73
74 class MedianComparator : public TermPredicate {
75 public:
76 static const char* staticGetName() {return "median";}
77 private:
78 virtual bool doPredicate(const Exponent* a,
79 const Exponent* b) const {
80 return median(a, getVarCount()) < median(b, getVarCount());
81 }
82 };
83
84 class MedianPositiveComparator : public TermPredicate {
85 public:
86 static const char* staticGetName() {return "posMedian";}
87 private:
88 virtual bool doPredicate(const Exponent* a,
89 const Exponent* b) const {
90 return medianPositive(a, getVarCount()) <
92 }
93 };
94
95 class MinimumPositiveComparator : public TermPredicate {
96 public:
97 static const char* staticGetName() {return "minPos";}
98 private:
99 virtual bool doPredicate(const Exponent* a,
100 const Exponent* b) const {
101 return minimumPositive(a, getVarCount()) <
103 }
104 };
105
106 class MaximumComparator : public TermPredicate {
107 public:
108 static const char* staticGetName() {return "max";}
109 private:
110 virtual bool doPredicate(const Exponent* a,
111 const Exponent* b) const {
112 return maximum(a, getVarCount()) < maximum(b, getVarCount());
113 }
114 };
115
116 class SupportComparator : public TermPredicate {
117 public:
118 static const char* staticGetName() {return "support";}
119 private:
120 virtual bool doPredicate(const Exponent* a,
121 const Exponent* b) const {
124 }
125 };
126
127 class StrongGenericityOrderer : public IdealOrderer {
128 public:
129 static const char* staticGetName() {return "strongGenericity";}
130
131 protected:
132 void orderGenericity(Ideal& ideal, bool strong) const {
133 // Using a map here is the prettier of several ugly
134 // alternaties. Only trade more ugly for efficiency if this
135 // method turns up as a significant consumer of time in a
136 // profiler.
137 UnGenMap degeneracy;
138
139 // Make degeneracy[gen] be the number of other generators that
140 // shares a positive exponent with gen.
141 Term tmp(ideal.getVarCount());
142 for (cit a = ideal.begin(); a != ideal.end(); ++a) {
143 for (cit b = a + 1; b != ideal.end(); ++b) {
144 if (Term::sharesNonZeroExponent(*a, *b, ideal.getVarCount())) {
145 if (!strong) {
146 tmp.lcm(*a, *b);
147 if (ideal.strictlyContains(tmp))
148 continue;
149 }
150 ++degeneracy[*a];
151 ++degeneracy[*b];
152 }
153 }
154 }
155
156 Pred pred(degeneracy);
157 stable_sort(ideal.begin(), ideal.end(), pred);
158 }
159
160 private:
161 typedef Ideal::const_iterator cit;
162 typedef map<const Exponent*, size_t> UnGenMap;
163
164 virtual void doOrder(Ideal& ideal) const {
165 orderGenericity(ideal, true);
166 }
167
168 class Pred {
169 public:
170 Pred(UnGenMap& degeneracy): _degeneracy(degeneracy) {}
171
172 bool operator()(const Exponent* a, const Exponent* b) const {
173 return _degeneracy[a] < _degeneracy[b];
174 }
175
176 private:
177 UnGenMap& _degeneracy;
178 };
179 };
180
181 class NullOrderer : public IdealOrderer {
182 public:
183 static const char* staticGetName() {return "null";}
184 private:
185 virtual void doOrder(Ideal& ideal) const {}
186 };
187
189 class WeakGenericityOrderer : public StrongGenericityOrderer {
190 public:
191 static const char* staticGetName() {return "weakGenericity";}
192 private:
193 virtual void doOrder(Ideal& ideal) const {
194 orderGenericity(ideal, false);
195 }
196 };
197
200 class ReverseOrderer : public IdealOrderer {
201 public:
202 ReverseOrderer(auto_ptr<IdealOrderer> orderer): _orderer(orderer) {}
203
204 private:
205 virtual void doOrder(Ideal& ideal) const {
206 // Could probably be done more efficiently by trying to interact
207 // with the orderer, but that would be so much more trouble. The
208 // first reverse is necessary to ensure the ordering is stable.
209 reverse(ideal.begin(), ideal.end());
210 _orderer->order(ideal);
211 reverse(ideal.begin(), ideal.end());
212 }
213 auto_ptr<IdealOrderer> _orderer;
214 };
215
216 class CompositeOrderer : public IdealOrderer {
217 public:
218 CompositeOrderer(): _orderersDeleter(_orderers) {}
219
221 exceptionSafePushBack(_orderers, orderer);
222 }
223
224 private:
225 typedef vector<IdealOrderer*> Container;
226 typedef Container::const_reverse_iterator rev_cit;
227
228 virtual void doOrder(Ideal& ideal) const {
229 // This works because orderes that define a non-total order
230 // (i.e. those that can be interestingly refined) use a stable
231 // sorting algorithm.
232 rev_cit rbegin(_orderers.end());
233 rev_cit rend(_orderers.begin());
234 for (rev_cit it = rbegin; it != rend; ++it)
235 (*it)->order(ideal);
236 }
237
238 Container _orderers;
239 ElementDeleter<Container> _orderersDeleter;
240 };
241
244 OrdererFactory factory("ordering of terms");
245
258
259 return factory;
260 }
261
263 if (prefix.substr(0, 3) == "rev") {
265 createWithPrefix(getOrdererFactory(), prefix.substr(3));
266 return auto_ptr<IdealOrderer>(new ReverseOrderer(orderer));
267 } else
268 return createWithPrefix(getOrdererFactory(), prefix);
269 }
270}
271
273 if (prefix.find('_') == string::npos)
274 return createNonCompositeOrderer(prefix);
275
276 auto_ptr<CompositeOrderer> composite(new CompositeOrderer());
277 size_t pos = 0;
278 while (true) {
279 size_t nextUnderscore = prefix.find('_', pos);
280 string subPrefix = prefix.substr(pos, nextUnderscore - pos);
281 composite->refineOrderingWith(createNonCompositeOrderer(subPrefix));
282
283 if (nextUnderscore == string::npos)
284 break;
285 pos = nextUnderscore + 1;
286 }
287 return auto_ptr<IdealOrderer>(composite.release());
288}
void exceptionSafePushBack(Container &container, auto_ptr< Element > pointer)
auto_ptr< IdealOrderer > createIdealOrderer(const string &prefix)
auto_ptr< AbstractProduct > createWithPrefix(const NameFactory< AbstractProduct > &factory, const string &prefix)
Creates the unique product that has the indicated prefix, or create the actual product that has name ...
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
Exponent median(const Exponent *a, size_t varCount)
Returns the lower median exponent of a.
Definition TermExtra.cpp:25
Exponent medianPositive(const Exponent *a, size_t varCount)
Returns the lower median of the positive exponents of a.
Definition TermExtra.cpp:35
void totalDegree(mpz_class &res, const Exponent *a, size_t varCount)
Puts the sum of the entries of a into res.
Definition TermExtra.cpp:49
Exponent minimumPositive(const Exponent *a, size_t varCount)
Returns the smallest positive exponent of a.
Definition TermExtra.cpp:55
Exponent maximum(const Exponent *a, size_t varCount)
Returns the largest exponent of a.
Definition TermExtra.cpp:68
virtual ~IdealOrderer()
virtual void doOrder(Ideal &ideal) const =0
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
Cont::const_iterator const_iterator
Definition Ideal.h:43
bool strictlyContains(const Exponent *term) const
Definition Ideal.cpp:73
const_iterator end() const
Definition Ideal.h:49
const_iterator begin() const
Definition Ideal.h:48
size_t getVarCount() const
Definition Ideal.h:56
A NameFactory takes a name and then creates an instance of a class that has been previously registere...
Definition NameFactory.h:33
size_t getVarCount() const
virtual bool doPredicate(const Exponent *a, const Exponent *b) const =0
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
size_t getSizeOfSupport() const
Definition Term.h:411
static bool sharesNonZeroExponent(const Exponent *a, const Exponent *b, size_t varCount)
Returns whether there is some such that .
Definition Term.h:416
unsigned int Exponent
Definition stdinc.h:89