Frobby  0.9.0
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"
25 #include "IndependenceSplitter.h"
27 #include "ElementDeleter.h"
28 
30  const SplitStrategy* splitStrategy):
31  SliceStrategyCommon(splitStrategy),
32  _consumerCache(),
33  _consumerCacheDeleter(_consumerCache),
34  _consumer(consumer) {
35 }
36 
37 void 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());
62  _tasks.runTasks();
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 {
79  ASSERT(_split->isPivotSplit());
80  pivotSplit(auto_ptr<Slice>(slice));
81  }
82 
83  return false;
84 }
85 
86 auto_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 
92 auto_ptr<Slice> HilbertStrategy::allocateSlice() {
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 
102 void HilbertStrategy::getPivot(Term& term, Slice& slice) {
103  ASSERT(term.getVarCount() == slice.getVarCount());
104 
105  _split->getPivot(term, slice);
106 }
107 
108 void 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();
116  noThrowPushBack(_consumerCache, consumer);
117 }
118 
119 void 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 
147 auto_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)
auto_ptr< Slice > newSlice()
Returns a slice from the cache that freeSlice adds to, or allocate a new one using allocateSlice...
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition: SplitStrategy.h:30
void product(const Exponent *term)
Definition: Ideal.cpp:525
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition: Slice.h:77
void freeConsumer(auto_ptr< HilbertIndependenceConsumer > consumer)
virtual void run(const Ideal &ideal)
Run the Slice algorithm.
virtual bool debugIsValidSlice(Slice *slice)
Check that this slice is valid for use with this strategy.
#define ASSERT(X)
Definition: stdinc.h:85
auto_ptr< HilbertSlice > newHilbertSlice()
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
const SplitStrategy * _split
size_t getVarCount() const
Definition: Term.h:85
TaskEngine _tasks
This keeps track of pending tasks to process.
virtual void freeSlice(auto_ptr< Slice > slice)
It is allowed to delete returned slices directly, but it is better to use freeSlice.
size_t getVarCount() const
Definition: Ideal.h:56
void independenceSplit(auto_ptr< Slice > slice)
IndependenceSplitter _indepSplitter
void runTasks()
Runs all pending tasks.
Definition: TaskEngine.cpp:61
HilbertStrategy(CoefTermConsumer *consumer, const SplitStrategy *splitStrategy)
virtual bool processSlice(TaskEngine &tasks, auto_ptr< Slice > slice)
Process the parameter slice.
void deleteElements()
TaskEngine handles a list of tasks that are to be carried out.
Definition: TaskEngine.h:40
auto_ptr< HilbertIndependenceConsumer > newConsumer()
CoefTermConsumer * _consumer
virtual void getPivot(Term &term, Slice &slice)
Used by pivotSplit to obtain a pivot.
size_t getVarCount() const
Returns the number of variables in the ambient ring.
Definition: Slice.h:96
virtual auto_ptr< Slice > allocateSlice()
Directly allocate a slice of the correct type using new.
This class adds code to the SliceStrategy base class that is useful for derived classes.
const Projection & getRightProjection() const
void addTask(Task *task)
Add a task at the head of the list of pending tasks.
Definition: TaskEngine.cpp:35
virtual void getPivot(Term &pivot, Slice &slice) const =0
Sets pivot to the pivot of a pivot split on slice.
virtual bool simplify(Slice &slice)
Simplifies slice and returns true if it changed.
bool contains(const Exponent *term) const
Definition: Ideal.cpp:57
vector< HilbertIndependenceConsumer * > _consumerCache
virtual void consume(const Polynomial &poly)
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
const Projection & getLeftProjection() const
size_t getGeneratorCount() const
Definition: Ideal.h:57
ElementDeleter< vector< HilbertIndependenceConsumer * > > _consumerCacheDeleter