From e00d7e6486739221f4d5adea1583743d3e23acfd Mon Sep 17 00:00:00 2001
From: Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au>
Date: Fri, 15 Jun 2012 14:13:04 +1000
Subject: Fix up the smart fixpoint iteration - make it actually work!

---
 impl/FixpointAlgorithm.hpp | 39 +++++++++++++++++----------------------
 impl/MaxStrategy.hpp       |  2 +-
 impl/main.cpp              |  6 +++---
 3 files changed, 21 insertions(+), 26 deletions(-)

(limited to 'impl')

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;
-- 
cgit v1.2.3