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