diff options
Diffstat (limited to 'impl/MaxStrategy.hpp')
| -rw-r--r-- | impl/MaxStrategy.hpp | 162 |
1 files changed, 100 insertions, 62 deletions
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp index 3ed7972..5534597 100644 --- a/impl/MaxStrategy.hpp +++ b/impl/MaxStrategy.hpp @@ -9,10 +9,10 @@ template<typename Domain> struct MaxStrategy { virtual ~MaxStrategy() { } - virtual unsigned int get(const MaxExpression<Domain>& e) const = 0; virtual unsigned int get(const MaxExpression<Domain>& e) { - return const_cast<const MaxStrategy*>(this)->get(e); + return const_cast<const MaxStrategy<Domain>*>(this)->get(e); } + virtual unsigned int get(const MaxExpression<Domain>& e) const = 0; }; unsigned int stack_depth = 1; @@ -34,46 +34,67 @@ template<typename Domain> struct DynamicMaxStrategy : public MaxStrategy<Domain> { DynamicMaxStrategy( const EquationSystem<Domain>& system - ) : _frozen(false), - _system(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())) + IdSet<MaxExpression<Domain> >(system.maxExpressionCount())), + _changed(false) {} void setRho(DynamicVariableAssignment<Domain>& rho) { _rho = ρ } + void hasChanged(bool c) { + _changed = c; + } + + bool hasChanged() const { + return _changed; + } + unsigned int get(const MaxExpression<Domain>& e) const { - // slightly hacky - return const_cast<DynamicMaxStrategy<Domain>*>(this)->get(e); + log::strategy << indent() << "Look up " << e << std::endl; + return _values[e]; } unsigned int get(const MaxExpression<Domain>& e) { - if (!_frozen) - solve(e); + log::strategy << indent() << "Solve for " << e << std::endl; + solve(e); return _values[e]; } void invalidate(const Variable<Domain>& v) { - log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; - if (_system[v] && _stable.contains(*_system[v])) { - _stable.remove(*_system[v]); - _stable.filter(_var_influence[v]); + log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; + //log::debug << indent() << " var-influence sets " << _var_influence << std::endl; + + IdSet<MaxExpression<Domain> > infl = _var_influence[v]; + for (typename IdSet<MaxExpression<Domain> >::iterator + it = infl.begin(), + end = infl.end(); + it != end; + ++it) { + invalidate(_system.maxExpression(*it)); + } + } - IdSet<MaxExpression<Domain> > infl = _var_influence[v]; - _var_influence[v].clear(); + void invalidate(const MaxExpression<Domain>& v) { + if (_stable.contains(v)) { + log::strategy << indent() << "Invalidating " << v << std::endl; + //log::debug << indent() << " influence sets " << _influence << std::endl; + _stable.remove(v); + + IdSet<MaxExpression<Domain> > infl = _influence[v]; for (typename IdSet<MaxExpression<Domain> >::iterator it = infl.begin(), end = infl.end(); it != end; ++it) { - solve(_system.maxExpression(*it)); + invalidate(_system.maxExpression(*it)); } } } @@ -84,20 +105,23 @@ 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]) { - log::strategy << x << " => " << *x.arguments()[val] << std::endl; IdSet<MaxExpression<Domain> > oldInfluence = _influence[x]; - _influence[x].clear(); + //_influence[x].clear(); _values[x] = val; + _changed = true; _rho->invalidate(*_system.varFromExpr(x)); + + //_rho->stabilise(); _stable.filter(oldInfluence); @@ -118,56 +142,27 @@ private: } } - const DynamicMaxStrategy& freeze() const { - _frozen = true; - return *this; - } - - const DynamicMaxStrategy& thaw() const { - _frozen = false; - return *this; - } - struct DependencyAssignment : public VariableAssignment<Domain>{ DependencyAssignment(DynamicMaxStrategy& strat, VariableAssignment<Domain>& rho, const MaxExpression<Domain>& expr) : _strat(strat), _rho(rho), - _expr(expr) { + _expr(expr), + _current(strat._system.variableCount()) { } - const Domain& operator[](const Variable<Domain>& var) const { + const Domain operator[](const Variable<Domain>& var) { + // solve the strategy for this variable, too + _strat.solve(*_strat._system[var]); _strat._var_influence[var].insert(_expr); + _strat._influence[*_strat._system[var]].insert(_expr); return _rho[var]; } private: DynamicMaxStrategy& _strat; VariableAssignment<Domain>& _rho; const MaxExpression<Domain>& _expr; - }; - - struct InvalidatingAssignment : public VariableAssignment<Domain>{ - InvalidatingAssignment(DynamicVariableAssignment<Domain>& rho) - : _rho(rho) { - } - ~InvalidatingAssignment() { - for (typename std::set<const Variable<Domain>*>::iterator - it = seen.begin(), - ei = seen.end(); - it != ei; - ++it) { - if (!_old_stable.contains(**it)) - _rho.invalidate(**it); - } - } - const Domain& operator[](const Variable<Domain>& var) const { - seen.insert(&var); - return _rho[var]; - } - private: - DynamicVariableAssignment<Domain>& _rho; - IdSet<Variable<Domain> > _old_stable; - mutable std::set<const Variable<Domain>*> seen; + IdSet<Variable<Domain> > _current; }; struct DependencyStrategy : public MaxStrategy<Domain> { @@ -176,10 +171,12 @@ private: _expr(expr) { } unsigned int get(const MaxExpression<Domain>& e) const { + _strat._influence[e].insert(_expr); + return _strat._values[e]; + } + unsigned int get(const MaxExpression<Domain>& e) { _strat.solve(e); - if (&_expr != &e) { - _strat._influence[e].insert(_expr); - } + _strat._influence[e].insert(_expr); return _strat._values[e]; } private: @@ -187,14 +184,55 @@ private: const MaxExpression<Domain>& _expr; }; -private: - mutable bool _frozen; +private: const EquationSystem<Domain>& _system; DynamicVariableAssignment<Domain>* _rho; IdMap<MaxExpression<Domain>,unsigned int> _values; IdSet<MaxExpression<Domain> > _stable; IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence; IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence; + bool _changed; +}; + + +template<typename Domain> +struct Solver { + Solver(const EquationSystem<Domain>& system) + : _system(system), + _strategy(system), + _rho(_system, _strategy, -infinity<Domain>()) { + _strategy.setRho(_rho); + } + + Domain solve(Variable<Domain>& var) { + MaxExpression<Domain>& rhs = *_system[var]; + + // _rho automatically keeps up to date with changes made to the + // strategy, so you don't need to stabilise it + + _strategy.get(rhs); + + + /* + do { + _strategy.hasChanged(false); + + log::debug << "Stabilise assignment (toplevel)" << std::endl; + _rho.stabilise(); + + log::debug << "Improve strategy (toplevel)" << std::endl; + // improve strategy + _strategy.get(rhs); + log::debug << (_strategy.hasChanged() ? "Strategy has changed - loop again" : "Strategy has not changed - terminate") << std::endl; + } while (_strategy.hasChanged()); + */ + + return _rho[var]; + } +private: + const EquationSystem<Domain>& _system; + DynamicMaxStrategy<Domain> _strategy; + DynamicVariableAssignment<Domain> _rho; }; |