Try to make some more modular Fixpoint algorithms.

1 files changed, 98 insertions, 0 deletions

diff --git a/impl/FixpointAlgorithm.hpp b/impl/FixpointAlgorithm.hpp
new file mode 100644
index 0000000..ed97bec
--- /dev/null
+++ b/impl/FixpointAlgorithm.hpp
@@ -0,0 +1,98 @@
+#ifndef FIXPOINT_ALGORITHM_HPP
+#define FIXPOINT_ALGORITHM_HPP
+
+#include "VariableAssignment.hpp"
+
+template<typename T>
+struct EquationSystem;
+template<typename T>
+struct MaxStrategy;
+
+template<typename T>
+struct FixpointAlgorithm {
+  virtual VariableAssignment<T> maxFixpoint(const MaxStrategy<T>&, const EquationSystem<T>&) 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);
+    do {
+      result = newResult;
+      newResult = strat(system, result);
+    } while (newResult != result);
+    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),
+        _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()];
+      }
+    }
+    void solve(const Variable<T>& x) const {
+      if (!_stable.contains(x)) {
+        _stable.insert(x);
+
+        const Variable<T>* oldEval = _evaluating;
+        _evaluating = &x;
+        T t = _strategy(*_system[x], *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;
+
+          _stable.filter(oldInfluence); // whatever x influences needs to be re-evaluated
+
+          for (typename IdSet<Variable<T> >::iterator it = oldInfluence.begin();
+               it != oldInfluence.end();
+               ++it) {
+            solve(*_system.getVar(*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;
+  };
+
+  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;
+  }
+};
+
+#endif