summaryrefslogtreecommitdiff
path: root/impl/ImprovementOperator.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'impl/ImprovementOperator.hpp')
-rw-r--r--impl/ImprovementOperator.hpp253
1 files changed, 91 insertions, 162 deletions
diff --git a/impl/ImprovementOperator.hpp b/impl/ImprovementOperator.hpp
index e70b5af..78c9ac5 100644
--- a/impl/ImprovementOperator.hpp
+++ b/impl/ImprovementOperator.hpp
@@ -68,192 +68,121 @@ struct RepeatedImprovementOperator : public ImprovementOperator<Domain> {
const ImprovementOperator<Domain>& _subImprovement;
};
-template<typename Domain>
-struct SmartImprovementOperator : public ImprovementOperator<Domain> {
- SmartImprovementOperator(const EquationSystem<Domain>& system)
- : _system(system),
- _influence(system.maxExpressionCount(), IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
- _first_run(true) {
- }
-
- struct DynamicMaxStrategy : public MaxStrategy<Domain> {
- DynamicMaxStrategy(
- const EquationSystem<Domain>& system,
- ConcreteMaxStrategy<Domain>& strat,
- IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain>>>& influence,
- StableVariableAssignment<Domain>& rho,
- IdSet<MaxExpression<Domain>>& stable,
- IdSet<MaxExpression<Domain>>& changed
- ) : _system(system),
- _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);
+#include "VariableAssignment.hpp"
- unsigned int val = x.bestStrategy(DependencyAssignment(*this, _rho, x),
- DependencyStrategy(*this, x));
+template<typename Domain>
+struct DynamicMaxStrategy : public MaxStrategy<Domain> {
+ DynamicMaxStrategy(
+ const EquationSystem<Domain>& system
+ ) : _system(system),
+ _rho(NULL),
+ _values(system),
+ _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;
+ }
- if (val != _values.get(x)) {
- auto oldInfluence = _influence[x];
- _influence[x].clear();
- _values.set(x, val);
- _changed.insert(x);
+ unsigned int get(const MaxExpression<Domain>& e) const {
+ solve(e);
+ return _values.get(e);
+ }
- _stable.filter(oldInfluence);
+ void invalidate(const Variable<Domain>& v) const {
+ log::strategy << "invalidating " << v << " - " << *_system[v] << std::endl;
+ log::strategy << "\t" << _var_influence[v] << std::endl;
+ _stable.filter(_var_influence[v]);
- for (auto it = oldInfluence.begin();
- it != oldInfluence.end();
- ++it) {
- solve(_system.maxExpression(*it));
- }
- _influence[x] = oldInfluence;
- }
- }
+ for (auto it = _var_influence[v].begin();
+ it != _var_influence[v].end();
+ ++it) {
+ solve(_system.maxExpression(*it));
}
+ }
- struct DependencyAssignment : public VariableAssignment<Domain>{
- DependencyAssignment(const DynamicMaxStrategy& strat,
- StableVariableAssignment<Domain>& rho,
- const MaxExpression<Domain>& expr)
- : _strat(strat),
- _rho(rho),
- _expr(expr) {
- }
- const Domain& operator[](const Variable<Domain>& var) const {
- _strat._influence[*_strat._system[var]].insert(_expr);
- _rho[var] =_strat._system[var]->eval(_rho, _strat);
- return _rho[var];
- }
- private:
- const DynamicMaxStrategy& _strat;
- StableVariableAssignment<Domain>& _rho;
- const MaxExpression<Domain>& _expr;
- };
+private:
+ void solve(const MaxExpression<Domain>& x) const {
+ if (!_stable.contains(x)) {
+ _stable.insert(x);
+
+ unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x),
+ DependencyStrategy(*this, x));
- 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.get(e);
- }
- private:
- const DynamicMaxStrategy& _strat;
- const MaxExpression<Domain>& _expr;
- };
+ if (val != _values.get(x)) {
+ log::strategy << "Updating strategy for " << x
+ << " to " << val << std::endl;
- private:
- const EquationSystem<Domain>& _system;
- StableVariableAssignment<Domain>& _rho;
- ConcreteMaxStrategy<Domain>& _values;
- IdSet<MaxExpression<Domain>>& _stable;
- IdSet<MaxExpression<Domain>>& _changed;
- IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain>>>& _influence;
- };
+ auto oldInfluence = _influence[x];
+ _influence[x].clear();
+ _values.set(x, val);
+
+ _rho->invalidate(*_system.varFromExpr(x));
- void invalidateSubexpressions(IdSet<MaxExpression<Domain>>& set, const Expression<Domain>* expr) const {
- const MaxExpression<Domain>* maxExpr = dynamic_cast<const MaxExpression<Domain>*>(expr);
- if (maxExpr != NULL) {
- if (!set.contains(*maxExpr)) {
- set.insert(*maxExpr);
- for (auto it = maxExpr->arguments().begin(),
- end = maxExpr->arguments().end();
- it != end;
+ _stable.filter(oldInfluence);
+
+ for (auto it = oldInfluence.begin();
+ it != oldInfluence.end();
++it) {
- invalidateSubexpressions(set, *it);
+ solve(_system.maxExpression(*it));
}
- }
+ } else {
+ log::strategy << x << " did not change" << std::endl;
+ }
+ } else {
+ log::strategy << x << " is stable" << std::endl;
}
}
- void markChanged(IdSet<Variable<Domain>>& set, MaxExpression<Domain>& expr, IdSet<MaxExpression<Domain>>& seen) const {
- if (seen.contains(expr))
- return;
- seen.insert(expr);
- auto var = _system.varFromExpr(expr);
- if (var == NULL || !set.contains(*var)) {
- if (var != NULL) {
- set.insert(*var);
- }
- for (auto it = _influence[expr].begin(),
- end = _influence[expr].end();
- it != end;
- ++it) {
- markChanged(set, _system.maxExpression(*it), seen);
- }
+ struct DependencyAssignment : public VariableAssignment<Domain>{
+ DependencyAssignment(const DynamicMaxStrategy& strat,
+ VariableAssignment<Domain>& rho,
+ const MaxExpression<Domain>& expr)
+ : _strat(strat),
+ _rho(rho),
+ _expr(expr) {
}
- }
-
- bool improve(
- EquationSystem<Domain>&,
- ConcreteMaxStrategy<Domain>& stratOut,
- StableVariableAssignment<Domain>& rho,
- IdSet<Variable<Domain> >& changedIn,
- IdSet<Variable<Domain> >& changedOut
- ) const {
- IdSet<MaxExpression<Domain>> invalidSet(_system.maxExpressionCount());
- IdSet<MaxExpression<Domain>> changedSet(_system.maxExpressionCount());
- IdSet<MaxExpression<Domain>> stableSet(_system.maxExpressionCount());
- if (_first_run) {
- invalidSet.invert(); // everything is invalid on the first run
- _first_run = false;
- } else {
- for (auto it = changedIn.begin(),
- end = changedIn.end();
- it != end;
- ++it) {
- invalidateSubexpressions(invalidSet, _system[_system.variable(*it)]);
- }
- stableSet = invalidSet.inverse();
+ 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;
+ };
- log::strategy << std::endl;
- log::strategy << "stable: " << stableSet << std::endl;
- log::strategy << "infl: " << _influence << std::endl;
- DynamicMaxStrategy strat(_system, stratOut, _influence, rho, stableSet, changedSet);
- log::strategy << "invalid: " << invalidSet << std::endl;
- log::strategy << "==================" << std::endl;
- for (auto it = invalidSet.begin(),
- end = invalidSet.end();
- it != end;
- ++it) {
- auto expr = _system.maxExpression(*it);
- unsigned int subExpression = strat.get(_system.maxExpression(*it));
- log::strategy << expr
- << " --[" << subExpression << "]-> "
- << *expr.arguments()[subExpression] << std::endl;
+ struct DependencyStrategy : public MaxStrategy<Domain> {
+ DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
+ : _strat(strat),
+ _expr(expr) {
}
- log::strategy << std::endl;
- IdSet<MaxExpression<Domain>> seen;
- for (auto it = changedSet.begin(),
- end = changedSet.end();
- it != end;
- ++it) {
- markChanged(changedOut, _system.maxExpression(*it), seen);
+ unsigned int get(const MaxExpression<Domain>& e) const {
+ _strat.solve(e);
+ if (&_expr != &e) {
+ _strat._influence[e].insert(_expr);
+ }
+ return _strat._values.get(e);
}
- return changedOut.begin() != changedOut.end(); // true iff changedOut is non-empty
- }
private:
+ const DynamicMaxStrategy& _strat;
+ const MaxExpression<Domain>& _expr;
+ };
+
+private:
const EquationSystem<Domain>& _system;
+ mutable DynamicVariableAssignment<Domain>* _rho;
+ mutable ConcreteMaxStrategy<Domain> _values;
+ mutable IdSet<MaxExpression<Domain>> _stable;
mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain>>> _influence;
- mutable bool _first_run;
+ mutable IdMap<Variable<Domain>,IdSet<MaxExpression<Domain>>> _var_influence;
};
+
#endif
generated by cgit v1.2.3 (git 2.46.0) at 2024-09-20 07:00:07 +0000