From c065ae2bd1176b17d137e0f52df6ef1d9af9e757 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Fri, 26 Oct 2012 16:29:52 +1100 Subject: Try to make the correct solver into a local solver As far as I can tell, it's worked! Hooray! --- impl/EquationSystem.hpp | 2 +- impl/Expression.hpp | 18 ++++----- impl/IdSet.hpp | 4 ++ impl/MaxStrategy.hpp | 96 ++++++++++++++++++++++++--------------------- impl/VariableAssignment.hpp | 55 ++++++++++++++++---------- impl/main.cpp | 7 ++-- 6 files changed, 104 insertions(+), 78 deletions(-) (limited to 'impl') diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp index 2fd24bd..3342cc7 100644 --- a/impl/EquationSystem.hpp +++ b/impl/EquationSystem.hpp @@ -105,7 +105,7 @@ struct EquationSystem { } } - virtual bool equalAssignments(const VariableAssignment& l, const VariableAssignment& r) const { + virtual bool equalAssignments(VariableAssignment& l, VariableAssignment& r) const { for (unsigned int i = 0, length = _variables.size(); i < length; ++i) { diff --git a/impl/Expression.hpp b/impl/Expression.hpp index 9c4ac9f..c005fd6 100644 --- a/impl/Expression.hpp +++ b/impl/Expression.hpp @@ -31,9 +31,9 @@ struct Expression { return NULL; } - virtual Domain eval(const VariableAssignment&) const = 0; - virtual Domain eval(const VariableAssignment& rho, - const MaxStrategy&) const { + virtual Domain eval(VariableAssignment&) const = 0; + virtual Domain eval(VariableAssignment& rho, + MaxStrategy&) const { return eval(rho); } @@ -48,7 +48,7 @@ struct Constant : public Expression { Constant(const Domain& value) : _value(value) { } - virtual Domain eval(const VariableAssignment&) const { + virtual Domain eval(VariableAssignment&) const { return _value; } @@ -72,7 +72,7 @@ struct Variable : public Expression { return _name; } - virtual Domain eval(const VariableAssignment& rho) const { + virtual Domain eval(VariableAssignment& rho) const { return rho[*this]; } @@ -90,7 +90,7 @@ struct OperatorExpression : public Expression { OperatorExpression(const Operator& op, const std::vector*>& arguments) : _operator(op), _arguments(arguments) { } - virtual Domain eval(const VariableAssignment& rho) const { + virtual Domain eval(VariableAssignment& rho) const { std::vector argumentValues; for (typename std::vector*>::const_iterator it = _arguments.begin(); it != _arguments.end(); @@ -100,7 +100,7 @@ struct OperatorExpression : public Expression { return _operator.eval(argumentValues); } - virtual Domain eval(const VariableAssignment& rho, const MaxStrategy& strat) const { + virtual Domain eval(VariableAssignment& rho, MaxStrategy& strat) const { std::vector argumentValues; for (typename std::vector*>::const_iterator it = _arguments.begin(); it != _arguments.end(); @@ -161,11 +161,11 @@ struct MaxExpression : public OperatorExpression { return this; } - virtual Domain eval(const VariableAssignment& rho, const MaxStrategy& strat) const { + virtual Domain eval(VariableAssignment& rho, MaxStrategy& strat) const { return this->_arguments[strat.get(*this)]->eval(rho, strat); } - unsigned int bestStrategy(const VariableAssignment& rho, const MaxStrategy& strat) const { + unsigned int bestStrategy(VariableAssignment& rho, MaxStrategy& strat) const { Domain bestValue = this->eval(rho, strat); unsigned int bestIndex = strat.get(*this); diff --git a/impl/IdSet.hpp b/impl/IdSet.hpp index 950b1e1..bf98502 100644 --- a/impl/IdSet.hpp +++ b/impl/IdSet.hpp @@ -96,6 +96,10 @@ class IdSet { return _set.size(); } + bool empty() const { + return _set.empty(); + } + private: unsigned int _range; std::set _set; diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp index f4026dd..d908c7b 100644 --- a/impl/MaxStrategy.hpp +++ b/impl/MaxStrategy.hpp @@ -9,10 +9,7 @@ template struct MaxStrategy { virtual ~MaxStrategy() { } - virtual unsigned int get(const MaxExpression& e) const = 0; - virtual unsigned int get(const MaxExpression& e) { - return const_cast(this)->get(e); - } + virtual unsigned int get(const MaxExpression& e) = 0; }; unsigned int stack_depth = 1; @@ -61,10 +58,6 @@ struct DynamicMaxStrategy : public MaxStrategy { _rho = ρ } - unsigned int get(const MaxExpression& e) const { - return _values[e]; - } - unsigned int get(const MaxExpression& e) { if (!_frozen) solve(e); @@ -93,9 +86,10 @@ private: _stable.insert(x); log::strategy << indent() << "Stabilise " << x << std::endl; - stack_depth++; - unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x), - DependencyStrategy(*this, x)); + stack_depth++; + DependencyAssignment assignment(*this, *_rho, x); + DependencyStrategy depStrat(*this, x); + unsigned int val = x.bestStrategy(assignment, depStrat); stack_depth--; if (val != _values[x]) { @@ -107,6 +101,12 @@ private: _rho->invalidate(*_system.varFromExpr(x)); + _rho->thaw(); + this->freeze(); + _rho->stabilise(); + _rho->freeze(); + this->thaw(); + _stable.filter(oldInfluence); for (typename IdSet >::iterator @@ -132,16 +132,25 @@ private: const MaxExpression& expr) : _strat(strat), _rho(rho), - _expr(expr) { + _expr(expr), + _current(strat._system.variableCount()) { } - const Domain& operator[](const Variable& var) const { + const Domain operator[](const Variable& var) { _strat._var_influence[var].insert(_expr); - return _rho[var]; + if (_current.contains(var)) { + return _rho[var]; + } else { + _current.insert(var); + Domain val = _strat._system[var]->eval(_rho, _strat); + _current.remove(var); + return val; + } } private: DynamicMaxStrategy& _strat; VariableAssignment& _rho; const MaxExpression& _expr; + IdSet > _current; }; struct DependencyStrategy : public MaxStrategy { @@ -149,7 +158,7 @@ private: : _strat(strat), _expr(expr) { } - unsigned int get(const MaxExpression& e) const { + unsigned int get(const MaxExpression& e) { _strat.solve(e); if (&_expr != &e) { _strat._influence[e].insert(_expr); @@ -172,40 +181,39 @@ private: }; -template -IdMap,T> solve_for(const EquationSystem& system) { - IdMap,T> result(system.variableCount(), infinity()); +template +struct Solver { + Solver(const EquationSystem& system) + : _system(system), + _strategy(system), + _rho(_system, _strategy, -infinity()) { + _strategy.setRho(_rho); + } - DynamicMaxStrategy strategy(system); - DynamicVariableAssignment rho(system, strategy, -infinity()); - strategy.setRho(rho); + Domain solve(Variable& var) { + MaxExpression& rhs = *_system[var]; - bool changed; - do { - changed = false; + do { + _rho.has_changed(false); - // improve strategy - rho.freeze(); - strategy.thaw(); - for (unsigned int i = 0; i < system.variableCount(); ++i) { - strategy.get(*system[system.variable(i)]); - } + // improve strategy + _rho.freeze(); + _strategy.thaw(); + _strategy.get(rhs); - // iterate fixpoint - strategy.freeze(); - rho.thaw(); - for (unsigned int i = 0; i < system.variableCount(); ++i) { - Variable& var = system.variable(i); - T val = rho[var]; - if (result[var] != val) { - result[var] = val; - changed = true; - } - } - } while(changed); + // iterate fixpoint + _strategy.freeze(); + _rho.thaw(); + _rho.stabilise(); + } while (_rho.has_changed()); - return result; -} + return _rho[var]; + } +private: + const EquationSystem& _system; + DynamicMaxStrategy _strategy; + DynamicVariableAssignment _rho; +}; /*template diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp index 2a63756..e074f6f 100644 --- a/impl/VariableAssignment.hpp +++ b/impl/VariableAssignment.hpp @@ -7,10 +7,7 @@ template struct VariableAssignment { virtual ~VariableAssignment() { } - virtual const Domain& operator[](const Variable&) const = 0; - virtual const Domain& operator[](const Variable& x) { - return (*const_cast(this))[x]; - } + virtual const Domain operator[](const Variable& x) = 0; }; #include "EquationSystem.hpp" @@ -27,11 +24,13 @@ struct DynamicVariableAssignment : public VariableAssignment { ) : _system(system), _strategy(strat), _values(system.variableCount(), value), - _stable(system.variableCount()), + _unstable(system.variableCount()), _influence(system.variableCount(), IdSet >(system.variableCount())), - _frozen(false) - { } + _frozen(false), + _changed(false) + { + } void freeze() { _frozen = true; @@ -41,25 +40,37 @@ struct DynamicVariableAssignment : public VariableAssignment { _frozen = false; } - bool is_frozen() { + bool is_frozen() const { return _frozen; } - const Domain& operator[](const Variable& var) const { - return _values[var]; + void has_changed(bool c) { + _changed = c; + } + + bool has_changed() const { + return _changed; } - const Domain& operator[](const Variable& var) { + const Domain operator[](const Variable& var) { if (!_frozen) solve(var); return _values[var]; } + void stabilise() { + if (!_unstable.empty()) { + Variable& var = _system.variable(*_unstable.begin()); + solve(var); + } + } + void invalidate(const Variable& x) { log::fixpoint << indent() << "Invalidating " << x << std::endl; - if (_stable.contains(x)) { - _stable.remove(x); + if (!_unstable.contains(x)) { + _unstable.insert(x); _values[x] = infinity(); + _changed = true; IdSet > infl = _influence[x]; _influence[x].clear(); @@ -76,13 +87,13 @@ struct DynamicVariableAssignment : public VariableAssignment { private: void solve(const Variable& x) { - if (!_stable.contains(x)) { - _stable.insert(x); + if (_unstable.contains(x)) { + _unstable.remove(x); log::fixpoint << indent() << "Stabilise " << x << std::endl; stack_depth++; - Domain val = _system[x]->eval(DependencyAssignment(*this, x), - _strategy); + DependencyAssignment assignment(*this, x); + Domain val = _system[x]->eval(assignment, _strategy); stack_depth--; if (val != _values[x]) { @@ -91,10 +102,11 @@ private: IdSet > oldInfluence = _influence[x]; _influence[x].clear(); _values[x] = val; + _changed = true; _strategy.invalidate(x); - _stable.filter(oldInfluence); + _unstable.absorb(oldInfluence); for (typename IdSet >::iterator it = oldInfluence.begin(); it != oldInfluence.end(); @@ -114,8 +126,8 @@ private: struct DependencyAssignment : public VariableAssignment { DependencyAssignment(DynamicVariableAssignment& assignment, const Variable& var) : _assignment(assignment), _var(var) { } - const Domain& operator[](const Variable& x) const { - const Domain& result = _assignment[x]; + const Domain operator[](const Variable& x) { + const Domain result = _assignment[x]; _assignment._influence[x].insert(_var); return result; } @@ -127,9 +139,10 @@ private: const EquationSystem& _system; DynamicMaxStrategy& _strategy; IdMap, Domain> _values; - IdSet > _stable; + IdSet > _unstable; IdMap,IdSet > > _influence; bool _frozen; + bool _changed; }; #endif diff --git a/impl/main.cpp b/impl/main.cpp index 84f17dd..94351ec 100644 --- a/impl/main.cpp +++ b/impl/main.cpp @@ -140,19 +140,20 @@ int main (int argc, char* argv[]) { log::debug << system << endl; system.indexMaxExpressions(); // make reverse-lookup O(1) instead of O(n) - IdMap,ZBar> result = solve_for(system); + Solver solver(system); // local *and* lazy. I love it! if (variables.size() > 0) { for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) { Variable& var = system.variable(i); if (variables.find(var.name()) != variables.end()) - cout << var.name() << " = " << result[var] << endl; + cout << var.name() << " = " << solver.solve(var) << endl; } } else { for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) { Variable& var = system.variable(i); - cout << var.name() << " = " << result[var] << endl; + cout << var.name() << " = " << solver.solve(var) << endl; } } + /* DynamicMaxStrategy strategy(system); DynamicVariableAssignment rho(system, strategy); -- cgit v1.2.3