1 files changed, 60 insertions, 65 deletions

diff --git a/impl/FixpointAlgorithm.hpp b/impl/FixpointAlgorithm.hpp
index ed97bec..b39a915 100644
--- a/impl/FixpointAlgorithm.hpp
+++ b/impl/FixpointAlgorithm.hpp
@@ -1,97 +1,92 @@
 #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 Domain>
+struct SmartFixpointAlgorithm : public FixpointAlgorithm<Domain> {
+  struct DynamicVariableAssignment : public VariableAssignment<Domain> {
+    DynamicVariableAssignment(const EquationSystem<Domain>& system)
+      : _system(system),
+        _values(system.variableCount(), infinity<Domain>()),
+        _stable(system.variableCount()),
+        _influence(system.variableCount(), IdSet<Variable<Domain> >(system.variableCount())) { }
 
-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),
-        _evaluating(NULL),
-        _influence(system.varCount(), IdSet<Variable<T> >(system.varCount())),
-        _stable(system.varCount()) {
+    const Domain& operator[](const Variable<Domain>& var) const {
+      solve(var);
+      //std::cout << _values << std::endl;
+      return _values[var];
     }
-    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()];
-      }
-    }
-    void solve(const Variable<T>& x) const {
+
+    private:
+
+    void solve(const Variable<Domain>& x) const {
       if (!_stable.contains(x)) {
         _stable.insert(x);
 
-        const Variable<T>* oldEval = _evaluating;
-        _evaluating = &x;
-        T t = _strategy(*_system[x], *this);
-        _evaluating = oldEval;
+        Domain val = _system[x]->eval(DependencyAssignment(*this, x));
 
-        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;
+
+    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 IdMap<Variable<Domain>,Domain> _values;
+    mutable IdSet<Variable<Domain> > _stable;
+    mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
   };
 
-  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);
   }
 };