Frobby 0.9.5
SliceStrategyCommon.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 "SliceStrategyCommon.h"
19#include "ElementDeleter.h"
20#include "TaskEngine.h"
21
22#include "Slice.h"
23
25 _split(splitStrategy),
26 _useIndependence(true),
27 _useSimplification(true) {
28 ASSERT(splitStrategy != 0);
29}
30
32 // TODO: use ElementDeleter instead
33 while (!_sliceCache.empty()) {
34 delete _sliceCache.back();
35 _sliceCache.pop_back();
36 }
37}
38
39void SliceStrategyCommon::freeSlice(auto_ptr<Slice> slice) {
40 ASSERT(slice.get() != 0);
41 ASSERT(debugIsValidSlice(slice.get()));
42
43 slice->clearIdealAndSubtract(); // To preserve memory.
45}
46
48 _useIndependence = use;
49}
50
53}
54
57 return slice.simplify();
58 else if (_split->isLabelSplit()) {
59 // The label split code requires at least this simplification.
60 return slice.adjustMultiply();
61 }
62 return false;
63}
64
66 auto_ptr<Slice> slice;
67 if (!_sliceCache.empty()) {
68 slice.reset(_sliceCache.back());
69 _sliceCache.pop_back();
70 } else
71 slice = allocateSlice();
72
73 ASSERT(debugIsValidSlice(slice.get()));
74 return slice;
75}
76
77void SliceStrategyCommon::pivotSplit(auto_ptr<Slice> slice) {
78 ASSERT(slice.get() != 0);
79
80 _pivotTmp.reset(slice->getVarCount());
81 getPivot(_pivotTmp, *slice);
82
83 // Assert valid pivot.
84 ASSERT(_pivotTmp.getVarCount() == slice->getVarCount());
86 ASSERT(!slice->getIdeal().contains(_pivotTmp));
87 ASSERT(!slice->getSubtract().contains(_pivotTmp));
88
89 // Set slice2 to the inner slice.
90 auto_ptr<Slice> slice2 = newSlice();
91 *slice2 = *slice;
92 slice2->innerSlice(_pivotTmp);
93 simplify(*slice2);
94
95 // Set slice to the outer slice.
96 slice->outerSlice(_pivotTmp);
97 simplify(*slice);
98
99 // Process the smaller slice first to preserve memory.
100 if (slice2->getIdeal().getGeneratorCount() <
101 slice->getIdeal().getGeneratorCount()) {
102 // std::swap() may not work correctly on auto_ptr, so we have to
103 // do the swap by hand.
104 auto_ptr<Slice> tmp = slice2;
105 slice2 = slice;
106 slice = tmp;
107 }
108
109 _tasks.addTask(slice2.release());
110 _tasks.addTask(slice.release());
111}
112
114 return _useIndependence;
115}
116
118 return _useSimplification;
119}
void noThrowPushBack(Container &container, auto_ptr< Element > pointer)
virtual void setUseIndependence(bool use)
This method should only be called before calling run().
bool getUseIndependence() const
Returns true if independence splits should be performed when possible.
virtual void getPivot(Term &pivot, Slice &slice)=0
Used by pivotSplit to obtain a pivot.
virtual auto_ptr< Slice > allocateSlice()=0
Directly allocate a slice of the correct type using new.
bool getUseSimplification() const
Returns true if slices should be simplified.
const SplitStrategy * _split
vector< Slice * > _sliceCache
This is the cache maintained through newSlice and freeSlice.
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.
SliceStrategyCommon(const SplitStrategy *splitStrategy)
virtual void setUseSimplification(bool use)
This method should only be called before calling run().
virtual void freeSlice(auto_ptr< Slice > slice)
It is allowed to delete returned slices directly, but it is better to use freeSlice.
virtual bool debugIsValidSlice(Slice *slice)=0
Check that this slice is valid for use with this strategy.
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
bool adjustMultiply()
Ensure that for each var, var appears to the first power in some generator of getIdeal().
Definition: Slice.cpp:162
virtual bool simplify()
Simplifies this object such that it may become simpler without changing the content.
Definition: Slice.cpp:204
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition: SplitStrategy.h:30
virtual bool isLabelSplit() const =0
If returns true, only call getLabelSplitVariable.
void addTask(Task *task)
Add a task at the head of the list of pending tasks.
Definition: TaskEngine.cpp:35
void reset(size_t newVarCount)
Definition: Term.h:551
size_t getVarCount() const
Definition: Term.h:85
static bool isIdentity(const Exponent *a, size_t varCount)
Returns whether a is 1, i.e. whether all entries of a are 0.
Definition: Term.h:316
#define ASSERT(X)
Definition: stdinc.h:86