Frobby 0.9.5
HilbertStrategy.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 "HilbertStrategy.h"
19
20#include "Term.h"
21#include "HilbertSlice.h"
22#include "Ideal.h"
23#include "CoefTermConsumer.h"
24#include "Projection.h"
27#include "ElementDeleter.h"
28
30 const SplitStrategy* splitStrategy):
31 SliceStrategyCommon(splitStrategy),
32 _consumerCache(),
33 _consumerCacheDeleter(_consumerCache),
34 _consumer(consumer) {
35}
36
37void HilbertStrategy::run(const Ideal& ideal) {
38 ASSERT(_consumer != 0);
39
40 size_t varCount = ideal.getVarCount();
41 Ideal sliceIdeal(varCount);
42
43 if (!ideal.contains(Term(varCount))) {
44 _consumer->consume(1, Term(varCount));
45
46 if (ideal.getGeneratorCount() > 0) {
47 Term allOnes(varCount);
48 for (size_t var = 0; var < varCount; ++var)
49 allOnes[var] = 1;
50
51 sliceIdeal = ideal;
52 sliceIdeal.product(allOnes);
53 }
54 }
55
56 auto_ptr<Slice> slice
57 (new HilbertSlice(*this, sliceIdeal, Ideal(varCount),
58 Term(varCount), _consumer));
59
60 simplify(*slice);
61 _tasks.addTask(slice.release());
64}
65
67(TaskEngine& tasks, auto_ptr<Slice> slice) {
68 ASSERT(slice.get() != 0);
69 ASSERT(debugIsValidSlice(slice.get()));
70
71 if (slice->baseCase(getUseSimplification())) {
72 freeSlice(slice);
73 return true;
74 }
75
76 if (getUseIndependence() && _indepSplitter.analyze(*slice)) {
77 independenceSplit(slice);
78 } else {
80 pivotSplit(auto_ptr<Slice>(slice));
81 }
82
83 return false;
84}
85
86auto_ptr<HilbertSlice> HilbertStrategy::newHilbertSlice() {
87 auto_ptr<Slice> slice(newSlice());
88 ASSERT(debugIsValidSlice(slice.get()));
89 return auto_ptr<HilbertSlice>(static_cast<HilbertSlice*>(slice.release()));
90}
91
93 return auto_ptr<Slice>(new HilbertSlice(*this));
94}
95
97 ASSERT(slice != 0);
98 ASSERT(dynamic_cast<HilbertSlice*>(slice) != 0);
99 return true;
100}
101
103 ASSERT(term.getVarCount() == slice.getVarCount());
104
105 _split->getPivot(term, slice);
106}
107
108void HilbertStrategy::freeConsumer(auto_ptr<HilbertIndependenceConsumer>
109 consumer) {
110 ASSERT(consumer.get() != 0);
111 ASSERT(std::find(_consumerCache.begin(),
112 _consumerCache.end(), consumer.get()) ==
113 _consumerCache.end());
114
115 consumer->clear();
117}
118
119void HilbertStrategy::independenceSplit(auto_ptr<Slice> sliceParam) {
120 ASSERT(sliceParam.get() != 0);
121 ASSERT(debugIsValidSlice(sliceParam.get()));
122 auto_ptr<HilbertSlice> slice
123 (static_cast<HilbertSlice*>(sliceParam.release()));
124
125 // Construct split object.
126 auto_ptr<HilbertIndependenceConsumer> autoSplit = newConsumer();
127 autoSplit->reset(slice->getConsumer(), _indepSplitter, slice->getVarCount());
128 HilbertIndependenceConsumer* split = autoSplit.release();
129 _tasks.addTask(split); // Runs when we are done with all of this split.
130
131 // Construct left slice.
132 auto_ptr<HilbertSlice> leftSlice(newHilbertSlice());
133 leftSlice->setToProjOf(*slice, split->getLeftProjection(),
134 split->getLeftConsumer());
135 _tasks.addTask(leftSlice.release());
136
137 // Construct right slice.
138 auto_ptr<HilbertSlice> rightSlice(newHilbertSlice());
139 rightSlice->setToProjOf(*slice, split->getRightProjection(),
140 split->getRightConsumer());
141 _tasks.addTask(rightSlice.release());
142
143 // Deal with slice.
144 freeSlice(auto_ptr<Slice>(slice));
145}
146
147auto_ptr<HilbertIndependenceConsumer> HilbertStrategy::newConsumer() {
148 if (_consumerCache.empty())
149 return auto_ptr<HilbertIndependenceConsumer>
150 (new HilbertIndependenceConsumer(this));
151
152 auto_ptr<HilbertIndependenceConsumer> consumer(_consumerCache.back());
153 _consumerCache.pop_back();
154 return consumer;
155}
void noThrowPushBack(Container &container, auto_ptr< Element > pointer)
virtual void consume(const Polynomial &poly)
void deleteElements()
const Projection & getRightProjection() const
const Projection & getLeftProjection() const
void freeConsumer(auto_ptr< HilbertIndependenceConsumer > consumer)
virtual auto_ptr< Slice > allocateSlice()
Directly allocate a slice of the correct type using new.
virtual void getPivot(Term &term, Slice &slice)
Used by pivotSplit to obtain a pivot.
ElementDeleter< vector< HilbertIndependenceConsumer * > > _consumerCacheDeleter
HilbertStrategy(CoefTermConsumer *consumer, const SplitStrategy *splitStrategy)
virtual bool debugIsValidSlice(Slice *slice)
Check that this slice is valid for use with this strategy.
IndependenceSplitter _indepSplitter
auto_ptr< HilbertSlice > newHilbertSlice()
vector< HilbertIndependenceConsumer * > _consumerCache
CoefTermConsumer * _consumer
virtual void run(const Ideal &ideal)
Run the Slice algorithm.
virtual bool processSlice(TaskEngine &tasks, auto_ptr< Slice > slice)
Process the parameter slice.
void independenceSplit(auto_ptr< Slice > slice)
auto_ptr< HilbertIndependenceConsumer > newConsumer()
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
void product(const Exponent *term)
Definition: Ideal.cpp:525
size_t getGeneratorCount() const
Definition: Ideal.h:57
bool contains(const Exponent *term) const
Definition: Ideal.cpp:57
size_t getVarCount() const
Definition: Ideal.h:56
bool analyze(const Slice &slice)
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
size_t getVarCount() const
Returns the number of variables in the ambient ring.
Definition: Slice.h:96
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition: SplitStrategy.h:30
virtual bool isPivotSplit() const =0
If returns true, only call getPivot.
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
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
size_t getVarCount() const
Definition: Term.h:85
#define ASSERT(X)
Definition: stdinc.h:86