summaryrefslogtreecommitdiff
path: root/impl/FixpointAlgorithm.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'impl/FixpointAlgorithm.hpp')
-rw-r--r--impl/FixpointAlgorithm.hpp125
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);
}
};