From b8045f2fa861959cdd87bd88dc2c6be98c115ec8 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Thu, 5 Jul 2012 17:19:10 +1000 Subject: Forgot a file! Whoops! --- impl/ImprovementOperator.hpp | 213 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 213 insertions(+) create mode 100644 impl/ImprovementOperator.hpp (limited to 'impl') 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 +struct ImprovementOperator { + virtual ~ImprovementOperator() { } + virtual bool improve( + ConcreteMaxStrategy& strat, + const VariableAssignment& rho, + IdSet >& changedIn, + IdSet >& changedOut + ) const = 0; +}; + +template +unsigned int bestStrategy(const MaxStrategy& strat, const MaxExpression& expr, const VariableAssignment& rho) { + Domain bestValue = MaxStrategyExpression(expr, strat).eval(rho); + unsigned int bestIndex = strat.get(expr); + + const std::vector*>& args = expr.arguments(); + for (unsigned int j = 0, length = args.size(); + j < length; + ++j) { + const Domain value = MaxStrategyExpression(*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 +struct NaiveImprovementOperator : public ImprovementOperator { + bool improve( + ConcreteMaxStrategy& strat, + const VariableAssignment& rho, + IdSet >& changedIn, + IdSet >& changedOut + ) const { + bool changed = false; + for (unsigned int i = 0, length = strat.maxExpressionCount(); + i < length; + ++i) { + MaxExpression& 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 +struct RepeatedImprovementOperator : public ImprovementOperator { + RepeatedImprovementOperator(const ImprovementOperator& op) + : _subImprovement(op) { } + + bool improve( + ConcreteMaxStrategy& strat, + const VariableAssignment& rho, + IdSet >& changedIn, + IdSet >& changedOut + ) const { + if (_subImprovement.improve(strat, rho, changedIn, changedOut)) { + VariableAssignment* rho2 = strat.eval(rho); + improve(strat, *rho2, changedIn, changedOut); + delete rho2; + return true; + } + return false; + } + private: + const ImprovementOperator& _subImprovement; +}; + +template +struct SmartImprovementOperator : public ImprovementOperator { + SmartImprovementOperator(const ConcreteEquationSystem& system) + : _system(system), + _influence(system.maxExpressionCount(), IdSet >(system.maxExpressionCount())) { + } + + struct DynamicMaxStrategy : public MaxStrategy { + DynamicMaxStrategy( + ConcreteMaxStrategy& strat, + IdMap,IdSet > >& influence, + const VariableAssignment& rho, + IdSet >& stable, + IdSet >& changed + ) : MaxStrategy(strat), + _rho(rho), + _values(strat), + _stable(stable), + _changed(changed), + _influence(influence) { + } + + unsigned int get(const MaxExpression& e) const { + solve(e); + return _values.get(e); + } + + private: + void solve(const MaxExpression& 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 > oldInfluence = _influence[x]; + _influence[x].clear(); + _values.set(x, val); + _changed.insert(x); + std::cout << x << std::endl; + + _stable.filter(oldInfluence); + + for (typename IdSet >::iterator it = oldInfluence.begin(); + it != oldInfluence.end(); + ++it) { + solve(_values.maxExpression(*it)); + } + _influence[x] = oldInfluence; + } + } + } + + struct DependencyStrategy : public MaxStrategy { + DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression& expr) + : MaxStrategy(strat), + _strat(strat), + _expr(expr) { + } + unsigned int get(const MaxExpression& e) const { + _strat.solve(e); + _strat._influence[e].insert(_expr); + return _strat._values.get(e); + } + private: + const DynamicMaxStrategy& _strat; + const MaxExpression& _expr; + }; + + private: + const VariableAssignment& _rho; + ConcreteMaxStrategy& _values; + IdSet >& _stable; + IdSet >& _changed; + IdMap,IdSet > >& _influence; + }; + + void invalidate(IdSet >& set, MaxExpression& expr) const { + for (typename IdSet >::iterator it = _influence[expr].begin(), + end = _influence[expr].end(); + it != end; + ++it) { + set.insert(_system.maxExpression(*it)); + invalidate(set, expr); + } + } + + bool improve( + ConcreteMaxStrategy& stratOut, + const VariableAssignment& rho, + IdSet >& changedIn, + IdSet >& changedOut + ) const { + IdSet > invalidSet(_system.maxExpressionCount()); + IdSet > changedSet(_system.maxExpressionCount()); + for (typename IdSet >::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 >::iterator it = changedSet.begin(), + end = changedSet.end(); + it != end; + ++it) { + Variable* 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& _system; + mutable IdMap,IdSet > > _influence; +}; + +#endif -- cgit v1.2.3