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
35
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)
53
55 for (size_t var = 0; var < varCount; ++var)
56 sliceMultiply[var] = 1;
57
59 (new MsmSlice(*this, ideal, *_initialSubtract, sliceMultiply, _consumer));
61
62 _initialSubtract.reset();
63 _tasks.addTask(slice.release());
66}
67
69 ASSERT(slice.get() != 0);
70
71 if (slice->baseCase(getUseSimplification())) {
73 return true;
74 }
75
78 else if (_split->isLabelSplit())
80 else {
83 }
84
85 return false;
86}
87
90 ASSERT(dynamic_cast<MsmSlice*>(slice.get()) != 0);
91 return auto_ptr<MsmSlice>(static_cast<MsmSlice*>(slice.release()));
92}
93
97
99 ASSERT(slice != 0);
100 ASSERT(dynamic_cast<MsmSlice*>(slice) != 0);
101 return true;
102}
103
105 ASSERT(sliceParam.get() != 0);
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();
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
150
151 if (label != stop) {
152 term = *label;
153 term[var] -= 1;
154
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) {
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
191
193 return _leftProjection;
194 }
195
197 return _rightProjection;
198 }
199
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
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
260 ASSERT(sliceParam.get() != 0);
263 (static_cast<MsmSlice*>(sliceParam.release()));
264
265 // Construct split object
267 autoSplit->reset(slice->getConsumer(), _indep);
269 _tasks.addTask(split); // Runs when we are done with all of this split.
270
271 // Construct left slice.
273 leftSlice->setToProjOf(*slice, split->getLeftProjection(), split);
274 _tasks.addTask(leftSlice.release());
275
276 // Construct right slice.
278 rightSlice->setToProjOf(*slice, split->getRightProjection(),
279 split->getRightConsumer());
280 _tasks.addTask(rightSlice.release());
281
282 // Deal with slice.
284}
285
292
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
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
bool analyze(const Slice &slice)
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()
virtual bool debugIsValidSlice(Slice *slice)
Check that this slice is valid for use with this strategy.
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.
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.
MsmStrategy(TermConsumer *consumer, const SplitStrategy *splitStrategy)
virtual auto_ptr< Slice > allocateSlice()
Directly allocate a slice of the correct type using new.
auto_ptr< Ideal > _initialSubtract
Definition MsmStrategy.h:65
void inverseProject(Term &to, const Exponent *from) const
size_t getRangeVarCount() const
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.
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.
void runTasks()
Runs all pending tasks.
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,...
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
#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.