Frobby  0.9.1
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 
39 void 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 
52  _useSimplification = use;
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 
65 auto_ptr<Slice> SliceStrategyCommon::newSlice() {
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 
77 void 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 }
SliceStrategyCommon::_split
const SplitStrategy * _split
Definition: SliceStrategyCommon.h:80
SliceStrategyCommon::_useIndependence
bool _useIndependence
Definition: SliceStrategyCommon.h:87
SliceStrategyCommon::setUseSimplification
virtual void setUseSimplification(bool use)
This method should only be called before calling run().
Definition: SliceStrategyCommon.cpp:51
Term::isIdentity
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
SliceStrategyCommon::_sliceCache
vector< Slice * > _sliceCache
This is the cache maintained through newSlice and freeSlice.
Definition: SliceStrategyCommon.h:95
SliceStrategyCommon.h
SliceStrategyCommon::setUseIndependence
virtual void setUseIndependence(bool use)
This method should only be called before calling run().
Definition: SliceStrategyCommon.cpp:47
stdinc.h
SliceStrategyCommon::newSlice
auto_ptr< Slice > newSlice()
Returns a slice from the cache that freeSlice adds to, or allocate a new one using allocateSlice.
Definition: SliceStrategyCommon.cpp:65
Term::reset
void reset(size_t newVarCount)
Definition: Term.h:551
SliceStrategyCommon::_tasks
TaskEngine _tasks
This keeps track of pending tasks to process.
Definition: SliceStrategyCommon.h:84
Slice::simplify
virtual bool simplify()
Simplifies this object such that it may become simpler without changing the content.
Definition: Slice.cpp:204
SliceStrategyCommon::allocateSlice
virtual auto_ptr< Slice > allocateSlice()=0
Directly allocate a slice of the correct type using new.
Term::getVarCount
size_t getVarCount() const
Definition: Term.h:85
SplitStrategy
A SplitStrategy is an implementation of a split selection strategy for the Slice Algorithm.
Definition: SplitStrategy.h:30
SliceStrategyCommon::_useSimplification
bool _useSimplification
Definition: SliceStrategyCommon.h:88
SliceStrategyCommon::~SliceStrategyCommon
virtual ~SliceStrategyCommon()
Definition: SliceStrategyCommon.cpp:31
SliceStrategyCommon::simplify
virtual bool simplify(Slice &slice)
Simplifies slice and returns true if it changed.
Definition: SliceStrategyCommon.cpp:55
SliceStrategyCommon::pivotSplit
virtual void pivotSplit(auto_ptr< Slice > slice)
Takes over ownership of slice.
Definition: SliceStrategyCommon.cpp:77
TaskEngine::addTask
void addTask(Task *task)
Add a task at the head of the list of pending tasks.
Definition: TaskEngine.cpp:35
SliceStrategyCommon::SliceStrategyCommon
SliceStrategyCommon(const SplitStrategy *splitStrategy)
Definition: SliceStrategyCommon.cpp:24
SliceStrategyCommon::getUseIndependence
bool getUseIndependence() const
Returns true if independence splits should be performed when possible.
Definition: SliceStrategyCommon.cpp:113
Slice
This class represents a slice, which is the central data structure of the Slice Algorithm.
Definition: Slice.h:77
noThrowPushBack
void noThrowPushBack(Container &container, auto_ptr< Element > pointer)
Definition: ElementDeleter.h:141
SliceStrategyCommon::debugIsValidSlice
virtual bool debugIsValidSlice(Slice *slice)=0
Check that this slice is valid for use with this strategy.
TaskEngine.h
SliceStrategyCommon::getUseSimplification
bool getUseSimplification() const
Returns true if slices should be simplified.
Definition: SliceStrategyCommon.cpp:117
SliceStrategyCommon::getPivot
virtual void getPivot(Term &pivot, Slice &slice)=0
Used by pivotSplit to obtain a pivot.
SliceStrategyCommon::_pivotTmp
Term _pivotTmp
Definition: SliceStrategyCommon.h:97
SplitStrategy::isLabelSplit
virtual bool isLabelSplit() const =0
If returns true, only call getLabelSplitVariable.
Slice::adjustMultiply
bool adjustMultiply()
Ensure that for each var, var appears to the first power in some generator of getIdeal().
Definition: Slice.cpp:162
ASSERT
#define ASSERT(X)
Definition: stdinc.h:86
SliceStrategyCommon::freeSlice
virtual void freeSlice(auto_ptr< Slice > slice)
It is allowed to delete returned slices directly, but it is better to use freeSlice.
Definition: SliceStrategyCommon.cpp:39
Slice.h
ElementDeleter.h