Re-write heaps of code to work better.

1 files changed, 65 insertions, 62 deletions

diff --git a/impl/FixpointAlgorithm.hpp b/impl/FixpointAlgorithm.hpp
index ed97bec..f199476 100644
--- a/impl/FixpointAlgorithm.hpp
+++ b/impl/FixpointAlgorithm.hpp
@@ -1,97 +1,100 @@
 #ifndef FIXPOINT_ALGORITHM_HPP
 #define FIXPOINT_ALGORITHM_HPP
 
+#include "IdSet.hpp"
+#include "IdMap.hpp"
 #include "VariableAssignment.hpp"
+#include "EquationSystem.hpp"
 
-template<typename T>
-struct EquationSystem;
-template<typename T>
-struct MaxStrategy;
-
-template<typename T>
+template<typename Domain>
 struct FixpointAlgorithm {
-  virtual VariableAssignment<T> maxFixpoint(const MaxStrategy<T>&, const EquationSystem<T>&) const = 0;
+  virtual ~FixpointAlgorithm() { }
+  virtual VariableAssignment<Domain>* maxFixpoint(const EquationSystem<Domain>&) const = 0;
 };
 
-#include "EquationSystem.hpp"
-#include "MaxStrategy.hpp"
-
-template<typename T>
-struct NaiveFixpoint : public FixpointAlgorithm<T> {
-  virtual VariableAssignment<T> maxFixpoint(const MaxStrategy<T>& strat, const EquationSystem<T>& system) const {
-    unsigned int size = system.varCount();
-    VariableAssignment<T> newResult(size, infinity<T>());
-    VariableAssignment<T> result(0);
+template<typename Domain>
+struct NaiveFixpointAlgorithm : public FixpointAlgorithm<Domain> {
+  virtual VariableAssignment<Domain>* maxFixpoint(const EquationSystem<Domain>& system) const {
+    VariableAssignment<Domain>* rho = NULL;
+    VariableAssignment<Domain>* result = system.assignment(infinity<Domain>());
     do {
-      result = newResult;
-      newResult = strat(system, result);
-    } while (newResult != result);
+      if (rho) delete rho;
+      rho = result;
+      result = system.eval(*rho);
+    } while (!system.equalAssignments(*rho, *result));
+    if (rho) delete rho;
     return result;
   }
 };
 
-
-template<typename T>
-struct RecursiveFixpoint : public FixpointAlgorithm<T> {
-  // this is a "VariableAssignment" which actually performs a recursive
-  // call to determine what value to return
-  struct EvaluatingVariableAssignment : public VariableAssignment<T> {
-    EvaluatingVariableAssignment(const MaxStrategy<T>& strategy, const EquationSystem<T>& system)
-      : VariableAssignment<T>(system.varCount(), infinity<T>()),
-        _strategy(strategy), _system(system),
+template<typename Domain>
+struct SmartFixpointAlgorithm : public FixpointAlgorithm<Domain> {
+  struct DynamicVariableAssignment : public VariableAssignment<Domain> {
+    DynamicVariableAssignment(const EquationSystem<Domain>& system)
+      : _system(system),
         _evaluating(NULL),
-        _influence(system.varCount(), IdSet<Variable<T> >(system.varCount())),
-        _stable(system.varCount()) {
-    }
-    virtual T& operator[] (const Variable<T>& x) const {
-      if (_evaluating == NULL) {
-        solve(x);
-        return VariableAssignment<T>::_assignment[x.id()];
-      } else {
-        solve(x);
-        _influence[x].insert(*_evaluating);
-        return VariableAssignment<T>::_assignment[x.id()];
+        _values(system.variableCount(), -infinity<Domain>()),
+        _stable(system.variableCount()),
+        _haveValue(system.variableCount()),
+        _influence(system.variableCount(), IdSet<Variable<Domain> >(system.variableCount())),
+        _id(0) { }
+
+    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];
     }
-    void solve(const Variable<T>& x) const {
+
+    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<T>* oldEval = _evaluating;
+        const Variable<Domain>* oldEval = _evaluating;
         _evaluating = &x;
-        T t = _strategy(*_system[x], *this);
+        Domain val = _system[x]->eval(*this);
         _evaluating = oldEval;
 
-        if (t != VariableAssignment<T>::_assignment[x.id()]) {
-          IdSet<Variable<T> > oldInfluence = _influence[x];
-          _influence[x].clear(); // clear out our idea of what x influences
-          VariableAssignment<T>::_assignment[x.id()] = t;
+        if (val != _values[x]) {
+          IdSet<Variable<Domain> > oldInfluence = _influence[x];
+          _influence[x].clear();
+          _values[x] = val;
 
-          _stable.filter(oldInfluence); // whatever x influences needs to be re-evaluated
+          _stable.filter(oldInfluence);
 
-          for (typename IdSet<Variable<T> >::iterator it = oldInfluence.begin();
+          for (typename IdSet<Variable<Domain> >::iterator it = oldInfluence.begin();
                it != oldInfluence.end();
                ++it) {
-            solve(*_system.getVar(*it));
+            solve(_system.variable(*it));
           }
         }
       }
     }
-    private:
-    const MaxStrategy<T>& _strategy;
-    const EquationSystem<T>& _system;
-    mutable const Variable<T>* _evaluating;
-    mutable IdMap<Variable<T>, IdSet<Variable<T> > > _influence;
-    mutable IdSet<Variable<T> > _stable;
+
+    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<T> maxFixpoint(const MaxStrategy<T>& strat, const EquationSystem<T>& system) const {
-    EvaluatingVariableAssignment assignment(strat, system);
-    VariableAssignment<T> result(system.varCount());
-    for (unsigned int i = 0; i < system.varCount(); ++i) {
-      result[*system.getVar(i)] = assignment[*system.getVar(i)];
-    }
-    return result;
+  virtual VariableAssignment<Domain>* maxFixpoint(const EquationSystem<Domain>& system) const {
+    return new DynamicVariableAssignment(system);
   }
 };