summaryrefslogtreecommitdiff
path: root/impl
diff options
context:
space:
mode:
authorCarlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au>2012-06-15 14:13:04 +1000
committerCarlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au>2012-06-15 14:13:04 +1000
commite00d7e6486739221f4d5adea1583743d3e23acfd (patch)
tree804a4762b816545b90034dc7eb8d3a372f4b497a /impl
parent3e3cc16699b2cf4d24629ba24c6d72ff912f0d96 (diff)
Fix up the smart fixpoint iteration - make it actually work!
Diffstat (limited to 'impl')
-rw-r--r--impl/FixpointAlgorithm.hpp39
-rw-r--r--impl/MaxStrategy.hpp2
-rw-r--r--impl/main.cpp6
3 files changed, 21 insertions, 26 deletions
diff --git a/impl/FixpointAlgorithm.hpp b/impl/FixpointAlgorithm.hpp
index f199476..4c84ff2 100644
--- a/impl/FixpointAlgorithm.hpp
+++ b/impl/FixpointAlgorithm.hpp
@@ -33,40 +33,23 @@ struct SmartFixpointAlgorithm : public FixpointAlgorithm<Domain> {
DynamicVariableAssignment(const EquationSystem<Domain>& system)
: _system(system),
_evaluating(NULL),
- _values(system.variableCount(), -infinity<Domain>()),
+ _values(system.variableCount(), infinity<Domain>()),
_stable(system.variableCount()),
_haveValue(system.variableCount()),
- _influence(system.variableCount(), IdSet<Variable<Domain> >(system.variableCount())),
- _id(0) { }
+ _influence(system.variableCount(), IdSet<Variable<Domain> >(system.variableCount())) { }
const Domain& operator[](const Variable<Domain>& var) const {
- _id++;
solve(var);
- for (unsigned int i = 0; i < _id; ++i) {
- std::cout << " ";
- }
- std::cout << "operator[] " << var.name() << " => " << _values[var] << std::endl;
- _id--;
- if (_evaluating) {
- _influence[var].insert(*_evaluating);
- }
return _values[var];
}
private:
+
void solve(const Variable<Domain>& x) const {
if (!_stable.contains(x)) {
_stable.insert(x);
- for (unsigned int i = 0; i < _id; ++i) {
- std::cout << " ";
- }
- std::cout << "solve(" << x.name() << ") " << &x << " " << _evaluating << std::endl;
- std::cout << _stable << std::endl;
- const Variable<Domain>* oldEval = _evaluating;
- _evaluating = &x;
- Domain val = _system[x]->eval(*this);
- _evaluating = oldEval;
+ Domain val = _system[x]->eval(DependencyAssignment(*this, x));
if (val != _values[x]) {
IdSet<Variable<Domain> > oldInfluence = _influence[x];
@@ -84,13 +67,25 @@ struct SmartFixpointAlgorithm : public FixpointAlgorithm<Domain> {
}
}
+ struct DependencyAssignment : public VariableAssignment<Domain> {
+ DependencyAssignment(const DynamicVariableAssignment& assignment, const Variable<Domain>& var)
+ : _assignment(assignment), _var(var) { }
+ const Domain& operator[](const Variable<Domain>& x) const {
+ const Domain& result = _assignment[x];
+ _assignment._influence[x].insert(_var);
+ return result;
+ }
+ private:
+ const DynamicVariableAssignment& _assignment;
+ const Variable<Domain>& _var;
+ };
+
const EquationSystem<Domain>& _system;
mutable const Variable<Domain>* _evaluating;
mutable IdMap<Variable<Domain>,Domain> _values;
mutable IdSet<Variable<Domain> > _stable;
mutable IdSet<Variable<Domain> > _haveValue;
mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
- mutable unsigned int _id;
};
virtual VariableAssignment<Domain>* maxFixpoint(const EquationSystem<Domain>& system) const {
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index 5d139fe..06f61b7 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -101,7 +101,7 @@ struct MaxStrategy : public EquationSystem<Domain> {
unsigned int bestIndex = this->get(expr);
// this relies on the fact that an expression will only be proessed after the expressions
- // it depends on (which should always be true)
+ // it depends on (which should always be true, as they form a DAG)
const std::vector<Expression<Domain>*> args = expr.arguments();
for (unsigned int j = 0, length = args.size();
j < length;
diff --git a/impl/main.cpp b/impl/main.cpp
index b03a4f2..40cae42 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -125,12 +125,12 @@ int main (int argc, char* argv[]) {
do {
if (prev) delete prev;
prev = result;
- strategy.improve(*prev);
- for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) {
+ /*for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) {
Variable<ZBar>& var = system.variable(i);
cout << var.name() << " = " << (*result)[var] << ", ";
}
- cout << endl;
+ cout << endl;*/
+ strategy.improve(*prev);
result = algorithm->maxFixpoint(strategy);
} while(!system.equalAssignments(*prev, *result));
if (prev) delete prev;