diff options
Diffstat (limited to 'impl')
| -rw-r--r-- | impl/ImprovementOperator.hpp | 213 |
1 files changed, 213 insertions, 0 deletions
diff --git a/impl/ImprovementOperator.hpp b/impl/ImprovementOperator.hpp new file mode 100644 index 0000000..3a9171f --- /dev/null +++ b/impl/ImprovementOperator.hpp @@ -0,0 +1,213 @@ +#ifndef IMPROVEMENT_OPERATOR_HPP +#define IMPROVEMENT_OPERATOR_HPP + +#include "IdSet.hpp" +#include "MaxStrategy.hpp" + +template<typename Domain> +struct ImprovementOperator { + virtual ~ImprovementOperator() { } + virtual bool improve( + ConcreteMaxStrategy<Domain>& strat, + const VariableAssignment<Domain>& rho, + IdSet<Variable<Domain> >& changedIn, + IdSet<Variable<Domain> >& changedOut + ) const = 0; +}; + +template<typename Domain> +unsigned int bestStrategy(const MaxStrategy<Domain>& strat, const MaxExpression<Domain>& expr, const VariableAssignment<Domain>& rho) { + Domain bestValue = MaxStrategyExpression<Domain>(expr, strat).eval(rho); + unsigned int bestIndex = strat.get(expr); + + const std::vector<Expression<Domain>*>& args = expr.arguments(); + for (unsigned int j = 0, length = args.size(); + j < length; + ++j) { + const Domain value = MaxStrategyExpression<Domain>(*args[j], strat).eval(rho); + std::cout << bestValue << " < " << value << ": "; + if (bestValue < value) { + std::cout << "change!" << std::endl; + bestValue = value; + bestIndex = j; + } + std::cout << std::endl; + } + return bestIndex; +} + +template<typename Domain> +struct NaiveImprovementOperator : public ImprovementOperator<Domain> { + bool improve( + ConcreteMaxStrategy<Domain>& strat, + const VariableAssignment<Domain>& rho, + IdSet<Variable<Domain> >& changedIn, + IdSet<Variable<Domain> >& changedOut + ) const { + bool changed = false; + for (unsigned int i = 0, length = strat.maxExpressionCount(); + i < length; + ++i) { + MaxExpression<Domain>& expr = strat.maxExpression(i); + // this relies on the fact that an expression will only be proessed after the expressions + // it depends on (which should always be true, as they form a DAG) + unsigned int index = bestStrategy(strat, expr, rho); + + if (index != strat.get(expr)) { + changed = true; + strat.set(expr, index); + } + } + return changed; + } +}; + +template<typename Domain> +struct RepeatedImprovementOperator : public ImprovementOperator<Domain> { + RepeatedImprovementOperator(const ImprovementOperator<Domain>& op) + : _subImprovement(op) { } + + bool improve( + ConcreteMaxStrategy<Domain>& strat, + const VariableAssignment<Domain>& rho, + IdSet<Variable<Domain> >& changedIn, + IdSet<Variable<Domain> >& changedOut + ) const { + if (_subImprovement.improve(strat, rho, changedIn, changedOut)) { + VariableAssignment<Domain>* rho2 = strat.eval(rho); + improve(strat, *rho2, changedIn, changedOut); + delete rho2; + return true; + } + return false; + } + private: + const ImprovementOperator<Domain>& _subImprovement; +}; + +template<typename Domain> +struct SmartImprovementOperator : public ImprovementOperator<Domain> { + SmartImprovementOperator(const ConcreteEquationSystem<Domain>& system) + : _system(system), + _influence(system.maxExpressionCount(), IdSet<MaxExpression<Domain> >(system.maxExpressionCount())) { + } + + struct DynamicMaxStrategy : public MaxStrategy<Domain> { + DynamicMaxStrategy( + ConcreteMaxStrategy<Domain>& strat, + IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > >& influence, + const VariableAssignment<Domain>& rho, + IdSet<MaxExpression<Domain> >& stable, + IdSet<MaxExpression<Domain> >& changed + ) : MaxStrategy<Domain>(strat), + _rho(rho), + _values(strat), + _stable(stable), + _changed(changed), + _influence(influence) { + } + + unsigned int get(const MaxExpression<Domain>& e) const { + solve(e); + return _values.get(e); + } + + private: + void solve(const MaxExpression<Domain>& x) const { + if (!_stable.contains(x)) { + _stable.insert(x); + + unsigned int val = bestStrategy(DependencyStrategy(*this, x), x, _rho); + //MaxStrategyExpression(x, DependencyStrategy(_values, x)); + + if (val != _values.get(x)) { + IdSet<MaxExpression<Domain> > oldInfluence = _influence[x]; + _influence[x].clear(); + _values.set(x, val); + _changed.insert(x); + std::cout << x << std::endl; + + _stable.filter(oldInfluence); + + for (typename IdSet<MaxExpression<Domain> >::iterator it = oldInfluence.begin(); + it != oldInfluence.end(); + ++it) { + solve(_values.maxExpression(*it)); + } + _influence[x] = oldInfluence; + } + } + } + + struct DependencyStrategy : public MaxStrategy<Domain> { + DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr) + : MaxStrategy<Domain>(strat), + _strat(strat), + _expr(expr) { + } + unsigned int get(const MaxExpression<Domain>& e) const { + _strat.solve(e); + _strat._influence[e].insert(_expr); + return _strat._values.get(e); + } + private: + const DynamicMaxStrategy& _strat; + const MaxExpression<Domain>& _expr; + }; + + private: + const VariableAssignment<Domain>& _rho; + ConcreteMaxStrategy<Domain>& _values; + IdSet<MaxExpression<Domain> >& _stable; + IdSet<MaxExpression<Domain> >& _changed; + IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > >& _influence; + }; + + void invalidate(IdSet<MaxExpression<Domain> >& set, MaxExpression<Domain>& expr) const { + for (typename IdSet<MaxExpression<Domain> >::iterator it = _influence[expr].begin(), + end = _influence[expr].end(); + it != end; + ++it) { + set.insert(_system.maxExpression(*it)); + invalidate(set, expr); + } + } + + bool improve( + ConcreteMaxStrategy<Domain>& stratOut, + const VariableAssignment<Domain>& rho, + IdSet<Variable<Domain> >& changedIn, + IdSet<Variable<Domain> >& changedOut + ) const { + IdSet<MaxExpression<Domain> > invalidSet(_system.maxExpressionCount()); + IdSet<MaxExpression<Domain> > changedSet(_system.maxExpressionCount()); + for (typename IdSet<Variable<Domain> >::iterator it = changedIn.begin(), + end = changedIn.end(); + it != end; + ++it) { + invalidate(invalidSet, *_system[_system.variable(*it)]); + } + invalidSet.invert(); + + std::cout << std::endl; + DynamicMaxStrategy strat(stratOut, _influence, rho, invalidSet, changedSet); + std::cout << std::endl; + for (typename IdSet<MaxExpression<Domain> >::iterator it = changedSet.begin(), + end = changedSet.end(); + it != end; + ++it) { + Variable<Domain>* var = strat.varFromExpr(_system.maxExpression(*it)); + if (var) { + changedOut.insert(*var); + } + } + std::cout << changedSet << std::endl; + std::cout << changedOut << std::endl; + return changedOut.size() != 0; + } + private: + const ConcreteEquationSystem<Domain>& _system; + mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence; +}; + +#endif |