summaryrefslogtreecommitdiff
path: root/impl/MaxStrategy.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'impl/MaxStrategy.hpp')
-rw-r--r--impl/MaxStrategy.hpp126
1 files changed, 105 insertions, 21 deletions
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index 21a6420..8f40c99 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -12,42 +12,126 @@ struct MaxStrategy {
virtual unsigned int get(const MaxExpression<Domain>& e) const = 0;
};
+#include "VariableAssignment.hpp"
+
+template<typename Domain>
+struct DynamicVariableAssignment;
+
template<typename Domain>
-struct ConcreteMaxStrategy : public MaxStrategy<Domain> {
- ConcreteMaxStrategy(const EquationSystem<Domain>& system)
- : _system(system),
- _strategy(system.maxExpressionCount(), 0) {
+struct DynamicMaxStrategy : public MaxStrategy<Domain> {
+ DynamicMaxStrategy(
+ const EquationSystem<Domain>& system
+ ) : _system(system),
+ _rho(NULL),
+ _values(system.maxExpressionCount(), 0),
+ _stable(system.maxExpressionCount()),
+ _influence(system.maxExpressionCount(),
+ IdSet<MaxExpression<Domain>>(system.maxExpressionCount())),
+ _var_influence(system.variableCount(),
+ IdSet<MaxExpression<Domain>>(system.maxExpressionCount()))
+ {}
+
+ void setRho(DynamicVariableAssignment<Domain>& rho) {
+ _rho = &rho;
}
unsigned int get(const MaxExpression<Domain>& e) const {
- return _strategy[e];
+ solve(e);
+ return _values[e];
}
- unsigned int set(const MaxExpression<Domain>& e, unsigned int i) {
- _strategy[e] = i;
- return i;
+
+ void invalidate(const Variable<Domain>& v) const {
+ log::strategy << "\tInvalidating " << v << " - " << *_system[v] << std::endl;
+ _stable.filter(_var_influence[v]);
+
+ for (auto it = _var_influence[v].begin();
+ it != _var_influence[v].end();
+ ++it) {
+ solve(_system.maxExpression(*it));
+ }
}
- void print(std::ostream& cout) const {
- for (unsigned int i = 0, length = _system.maxExpressionCount();
- i < length;
- ++i) {
- auto expr = _system.maxExpression(i);
- unsigned int subExpression = get(expr);
- cout << expr
- << " --[" << subExpression << "]-> "
- << *expr.arguments()[subExpression] << std::endl;
+private:
+ void solve(const MaxExpression<Domain>& x) const {
+ if (!_stable.contains(x)) {
+ _stable.insert(x);
+ log::strategy << "\tStabilise " << x << std::endl;
+
+ unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x),
+ DependencyStrategy(*this, x));
+
+ if (val != _values[x]) {
+ log::strategy << x << " => " << *x.arguments()[val] << std::endl;
+
+ auto oldInfluence = _influence[x];
+ _influence[x].clear();
+ _values[x] = val;
+
+ _rho->invalidate(*_system.varFromExpr(x));
+
+ _stable.filter(oldInfluence);
+
+ for (auto it = oldInfluence.begin();
+ it != oldInfluence.end();
+ ++it) {
+ solve(_system.maxExpression(*it));
+ }
+ } else {
+ log::strategy << "\t" << x << " did not change" << std::endl;
+ }
+ } else {
+ log::strategy << "\t" << x << " is stable" << std::endl;
}
}
+ struct DependencyAssignment : public VariableAssignment<Domain>{
+ DependencyAssignment(const DynamicMaxStrategy& strat,
+ VariableAssignment<Domain>& rho,
+ const MaxExpression<Domain>& expr)
+ : _strat(strat),
+ _rho(rho),
+ _expr(expr) {
+ }
+ const Domain& operator[](const Variable<Domain>& var) const {
+ _strat._var_influence[var].insert(_expr);
+ return _rho[var];
+ }
+ private:
+ const DynamicMaxStrategy& _strat;
+ VariableAssignment<Domain>& _rho;
+ const MaxExpression<Domain>& _expr;
+ };
+
+ struct DependencyStrategy : public MaxStrategy<Domain> {
+ DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
+ : _strat(strat),
+ _expr(expr) {
+ }
+ unsigned int get(const MaxExpression<Domain>& e) const {
+ _strat.solve(e);
+ if (&_expr != &e) {
+ _strat._influence[e].insert(_expr);
+ }
+ return _strat._values[e];
+ }
private:
+ const DynamicMaxStrategy& _strat;
+ const MaxExpression<Domain>& _expr;
+ };
+
+private:
const EquationSystem<Domain>& _system;
- IdMap<MaxExpression<Domain>,unsigned int> _strategy;
+ mutable DynamicVariableAssignment<Domain>* _rho;
+ mutable IdMap<MaxExpression<Domain>,unsigned int> _values;
+ mutable IdSet<MaxExpression<Domain>> _stable;
+ mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain>>> _influence;
+ mutable IdMap<Variable<Domain>,IdSet<MaxExpression<Domain>>> _var_influence;
};
-template<typename Domain>
-std::ostream& operator<<(std::ostream& cout, const ConcreteMaxStrategy<Domain>& strat) {
+/*template<typename Domain>
+std::ostream& operator<<(std::ostream& cout, const MaxStrategy<Domain>& strat) {
strat.print(cout);
return cout;
-}
+}*/
#endif