Frobby 0.9.5
MsmStrategy.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 "MsmStrategy.h"
19
20#include "MsmSlice.h"
21#include "Term.h"
22#include "Ideal.h"
23#include "TermTranslator.h"
24#include <vector>
25#include "Projection.h"
26#include "TermGrader.h"
27
29 const SplitStrategy* splitStrategy):
30 SliceStrategyCommon(splitStrategy),
31 _consumer(consumer),
32 _initialSubtract(0) {
33 ASSERT(consumer != 0);
34}
35
37 const SplitStrategy* splitStrategy,
38 const Ideal& initialSubtract):
39 SliceStrategyCommon(splitStrategy),
40 _consumer(consumer),
41 _initialSubtract(new Ideal(initialSubtract)) {
42 ASSERT(consumer != 0);
43}
44
45void MsmStrategy::run(const Ideal& ideal) {
46 ASSERT(_initialSubtract.get() == 0 ||
47 _initialSubtract->getVarCount() == ideal.getVarCount());
48
50 size_t varCount = ideal.getVarCount();
51 if (_initialSubtract.get() == 0)
52 _initialSubtract = auto_ptr<Ideal>(new Ideal(varCount));
53
54 Term sliceMultiply(varCount);
55 for (size_t var = 0; var < varCount; ++var)
56 sliceMultiply[var] = 1;
57
58 auto_ptr<Slice> slice
59 (new MsmSlice(*this, ideal, *_initialSubtract, sliceMultiply, _consumer));
60 simplify(*slice);
61
62 _initialSubtract.reset();
63 _tasks.addTask(slice.release());
66}
67
68bool MsmStrategy::processSlice(TaskEngine& tasks, auto_ptr<Slice> slice) {
69 ASSERT(slice.get() != 0);
70
71 if (slice->baseCase(getUseSimplification())) {
72 freeSlice(slice);
73 return true;
74 }
75
76 if (getUseIndependence() && _indep.analyze(*slice))
77 independenceSplit(slice);
78 else if (_split->isLabelSplit())
79 labelSplit(slice);
80 else {
82 pivotSplit(auto_ptr<Slice>(slice));
83 }
84
85 return false;
86}
87
88auto_ptr<MsmSlice> MsmStrategy::newMsmSlice() {
89 auto_ptr<Slice> slice(newSlice());
90 ASSERT(dynamic_cast<MsmSlice*>(slice.get()) != 0);
91 return auto_ptr<MsmSlice>(static_cast<MsmSlice*>(slice.release()));
92}
93
94auto_ptr<Slice> MsmStrategy::allocateSlice() {
95 return auto_ptr<Slice>(new MsmSlice(*this));
96}
97
99 ASSERT(slice != 0);
100 ASSERT(dynamic_cast<MsmSlice*>(slice) != 0);
101 return true;
102}
103
104void MsmStrategy::labelSplit(auto_ptr<Slice> sliceParam) {
105 ASSERT(sliceParam.get() != 0);
106 ASSERT(debugIsValidSlice(sliceParam.get()));
107 auto_ptr<MsmSlice> slice
108 (static_cast<MsmSlice*>(sliceParam.release()));
109
110 ASSERT(!slice->adjustMultiply());
111 ASSERT(!slice->normalize());
112 ASSERT(_split != 0);
113 size_t var = _split->getLabelSplitVariable(*slice);
114
115 Term term(slice->getVarCount());
116
117 const Term& lcm = slice->getLcm();
118
119 Ideal::const_iterator stop = slice->getIdeal().end();
120 Ideal::const_iterator label = stop;
121 bool hasTwoLabels = false;
122 for (Ideal::const_iterator it = slice->getIdeal().begin();
123 it != stop; ++it) {
124 if ((*it)[var] == 1) {
125 term = *it;
126 term[var] -= 1;
127
128 bool couldBeLabel = !slice->getSubtract().contains(term);
129 if (couldBeLabel) {
130 for (size_t v = 0; v < slice->getVarCount(); ++v) {
131 if (term[v] == lcm[v]) {
132 couldBeLabel = false;
133 break;
134 }
135 }
136 }
137
138 if (couldBeLabel) {
139 if (label == stop)
140 label = it;
141 else {
142 hasTwoLabels = true;
143 break;
144 }
145 }
146 }
147 }
148
149 auto_ptr<Slice> hasLabelSlice;
150
151 if (label != stop) {
152 term = *label;
153 term[var] -= 1;
154
155 hasLabelSlice = newSlice();
156 *hasLabelSlice = *slice;
157 hasLabelSlice->innerSlice(term);
158
159 if (hasTwoLabels)
160 slice->outerSlice(term);
161 }
162
163 if (!hasTwoLabels) {
164 term.setToIdentity();
165 term[var] = 1;
166 slice->innerSlice(term);
167 }
168
169 if (hasLabelSlice.get() != 0) {
170 simplify(*hasLabelSlice);
171 _tasks.addTask(hasLabelSlice.release());
172 }
173
174 simplify(*slice);
175 _tasks.addTask(slice.release());
176}
177
178class MsmIndependenceSplit : public TermConsumer, public Task {
179public:
181 return this;
182 }
183
185 return this;
186 }
187
189 return &_rightConsumer;
190 }
191
193 return _leftProjection;
194 }
195
197 return _rightProjection;
198 }
199
200 void reset(TermConsumer* consumer,
201 IndependenceSplitter& splitter) {
202 _consumer = consumer;
203 _tmpTerm.reset(splitter.getVarCount());
204
207
210 }
211
212private:
213 virtual void run(TaskEngine& engine) {
214 dispose();
215 }
216
217 virtual void dispose() {
218 delete this;
219 }
220
221 virtual void beginConsuming() {
222 }
223
224 virtual void doneConsuming() {
225 }
226
227 virtual void consume(const Term& term) {
231 it != stop; ++it) {
234 }
235 }
236
237 struct RightConsumer : public TermConsumer {
238 virtual void beginConsuming() {
239 }
240
241 virtual void doneConsuming() {
242 }
243
244 virtual void consume(const Term& term) {
245 _decom.insert(term);
246 }
247
250
252
255
257};
258
259void MsmStrategy::independenceSplit(auto_ptr<Slice> sliceParam) {
260 ASSERT(sliceParam.get() != 0);
261 ASSERT(debugIsValidSlice(sliceParam.get()));
262 auto_ptr<MsmSlice> slice
263 (static_cast<MsmSlice*>(sliceParam.release()));
264
265 // Construct split object
266 auto_ptr<MsmIndependenceSplit> autoSplit(new MsmIndependenceSplit());
267 autoSplit->reset(slice->getConsumer(), _indep);
268 MsmIndependenceSplit* split = autoSplit.release();
269 _tasks.addTask(split); // Runs when we are done with all of this split.
270
271 // Construct left slice.
272 auto_ptr<MsmSlice> leftSlice(new MsmSlice(*this));
273 leftSlice->setToProjOf(*slice, split->getLeftProjection(), split);
274 _tasks.addTask(leftSlice.release());
275
276 // Construct right slice.
277 auto_ptr<MsmSlice> rightSlice(new MsmSlice(*this));
278 rightSlice->setToProjOf(*slice, split->getRightProjection(),
279 split->getRightConsumer());
280 _tasks.addTask(rightSlice.release());
281
282 // Deal with slice.
283 freeSlice(auto_ptr<Slice>(slice));
284}
285
286void MsmStrategy::getPivot(Term& pivot, Slice& slice) {
287 ASSERT(_split != 0);
289
290 _split->getPivot(pivot, slice);
291}
292
293void MsmStrategy::getPivot(Term& pivot, Slice& slice, const TermGrader& grader) {
294 ASSERT(_split != 0);
296
297 _split->getPivot(pivot, slice, grader);
298}
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
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
size_t getVarCount() const
Definition: Ideal.h:56
void getRestProjection(Projection &projection) const
void getBigProjection(Projection &projection) const
bool analyze(const Slice &slice)
Projection _leftProjection
MsmIndependenceSplit::RightConsumer _rightConsumer
virtual void dispose()
Called when the task is no longer used but run has not and will not be called.
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.
Projection _rightProjection
TermConsumer * _consumer
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
virtual void run(TaskEngine &engine)
Does whatever work this task represents.
const Projection & getRightProjection()
TermConsumer * getLeftConsumer()
void reset(TermConsumer *consumer, IndependenceSplitter &splitter)
const Projection & getLeftProjection()
TermConsumer * getRightConsumer()
virtual void consume(const Term &term)
Consume a term.
Invariant: either the slice is a trivial base case, or removeDoubleLcm returns false.
Definition: MsmSlice.h:33
auto_ptr< MsmSlice > newMsmSlice()
Definition: MsmStrategy.cpp:88
virtual bool debugIsValidSlice(Slice *slice)
Check that this slice is valid for use with this strategy.
Definition: MsmStrategy.cpp:98
void independenceSplit(auto_ptr< Slice > slice)
IndependenceSplitter _indep
Definition: MsmStrategy.h:62
TermConsumer * _consumer
Definition: MsmStrategy.h:63
virtual bool processSlice(TaskEngine &tasks, auto_ptr< Slice > slice)
Process the parameter slice.
Definition: MsmStrategy.cpp:68
virtual void getPivot(Term &pivot, Slice &slice)
Used by pivotSplit to obtain a pivot.
void labelSplit(auto_ptr< Slice > slice)
virtual void run(const Ideal &ideal)
Run the Slice algorithm.
Definition: MsmStrategy.cpp:45
MsmStrategy(TermConsumer *consumer, const SplitStrategy *splitStrategy)
Definition: MsmStrategy.cpp:28
virtual auto_ptr< Slice > allocateSlice()
Directly allocate a slice of the correct type using new.
Definition: MsmStrategy.cpp:94
auto_ptr< Ideal > _initialSubtract
Definition: MsmStrategy.h:65
void inverseProject(Term &to, const Exponent *from) const
Definition: Projection.cpp:78
size_t getRangeVarCount() const
Definition: Projection.cpp:24
This class adds code to the SliceStrategy base class that is useful for derived classes.
bool getUseIndependence() const
Returns true if independence splits should be performed when possible.
bool getUseSimplification() const
Returns true if slices should be simplified.
const SplitStrategy * _split
virtual bool simplify(Slice &slice)
Simplifies slice and returns true if it changed.
virtual void pivotSplit(auto_ptr< Slice > slice)
Takes over ownership of slice.
auto_ptr< Slice > newSlice()
Returns a slice from the cache that freeSlice adds to, or allocate a new one using allocateSlice.
virtual void freeSlice(auto_ptr< Slice > slice)
It is allowed to delete returned slices directly, but it is better to use freeSlice.
TaskEngine _tasks
This keeps track of pending tasks to process.
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition: Slice.h:77
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition: SplitStrategy.h:30
virtual size_t getLabelSplitVariable(const Slice &slice) const =0
Returns the variable to perform a label split on.
virtual bool isPivotSplit() const =0
If returns true, only call getPivot.
virtual bool isLabelSplit() const =0
If returns true, only call getLabelSplitVariable.
virtual void getPivot(Term &pivot, Slice &slice) const =0
Sets pivot to the pivot of a pivot split on slice.
TaskEngine handles a list of tasks that are to be carried out.
Definition: TaskEngine.h:40
void addTask(Task *task)
Add a task at the head of the list of pending tasks.
Definition: TaskEngine.cpp:35
void runTasks()
Runs all pending tasks.
Definition: TaskEngine.cpp:61
A Task object represents a unit of work that is performed when the method run() is called.
Definition: Task.h:27
This class is used to transfer terms one at a time from one part of the program to another,...
Definition: TermConsumer.h:36
virtual void beginConsuming()=0
Tell the consumer to begin consuming an ideal.
virtual void doneConsuming()=0
Must be called once after each time beginConsuming has been called.
virtual void consume(const Term &term)=0
Consume a term.
A TermGrader assigns a value, the degree, to each monomial.
Definition: TermGrader.h:27
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
void reset(size_t newVarCount)
Definition: Term.h:551
static void setToIdentity(Exponent *res, size_t varCount)
Set res equal to , i.e. set each entry of res equal to 0.
Definition: Term.h:304
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
#define ASSERT(X)
Definition: stdinc.h:86
virtual void doneConsuming()
Must be called once after each time beginConsuming has been called.
virtual void consume(const Term &term)
Consume a term.
virtual void beginConsuming()
Tell the consumer to begin consuming an ideal.