summaryrefslogtreecommitdiff
path: root/impl/MaxStrategy.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'impl/MaxStrategy.hpp')
-rw-r--r--impl/MaxStrategy.hpp218
1 files changed, 145 insertions, 73 deletions
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index aa49c9d..2be9f4c 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -1,100 +1,172 @@
-#ifndef MAX_STRATEGY_HPP
-#define MAX_STRATEGY_HPP
+#ifndef MAX_EXPRESSION_HPP
+#define MAX_EXPRESSION_HPP
-#include <iostream>
#include "Expression.hpp"
#include "EquationSystem.hpp"
-#include "VariableAssignment.hpp"
-
-template<typename T>
-struct MaxStrategy {
- MaxStrategy()
- : _length(0), _assignment(NULL) { }
- MaxStrategy(unsigned int length)
- : _length(length), _assignment(new unsigned int[length]) {
- for (unsigned int i = 0; i < length; ++i) {
- _assignment[i] = 0;
+
+template<typename Domain>
+struct MaxStrategyExpression : public Expression<Domain> {
+ MaxStrategyExpression(const Expression<Domain>& expr, const IdMap<MaxExpression<Domain>,unsigned int>& strategy)
+ : _expr(expr), _strategy(strategy) { }
+
+ virtual Domain eval(const VariableAssignment<Domain>& rho) const {
+ // relies on implementation details - BAD BAD BAD, maybe
+ const OperatorExpression<Domain>* opExpr = dynamic_cast<const OperatorExpression<Domain>*>(&_expr);
+ if (opExpr) {
+ const MaxExpression<Domain>* maxExpr = dynamic_cast<const MaxExpression<Domain>*>(opExpr);
+ const std::vector<Expression<Domain>*> args = opExpr->arguments();
+ if (maxExpr) {
+ unsigned int i = _strategy[*maxExpr];
+ return MaxStrategyExpression(*args[i], _strategy).eval(rho);
+ } else {
+ std::vector<Domain> argumentValues;
+ for (typename std::vector<Expression<Domain>*>::const_iterator it = args.begin();
+ it != args.end();
+ ++it) {
+ argumentValues.push_back(MaxStrategyExpression(**it, _strategy).eval(rho));
+ }
+ return opExpr->op().eval(argumentValues);
+ }
+ } else {
+ return _expr.eval(rho);
}
}
- MaxStrategy(const MaxStrategy& other)
- : _length(other._length), _assignment(new unsigned int[other._length]) {
- for (unsigned int i = 0; i < other._length; ++i) {
- _assignment[i] = other._assignment[i];
- }
+
+ void print(std::ostream& cout) const {
+ cout << _expr;
}
+ private:
+ const Expression<Domain>& _expr;
+ const IdMap<MaxExpression<Domain>,unsigned int>& _strategy;
+};
- virtual ~MaxStrategy() {
- delete[] _assignment;
+template<typename Domain>
+struct MaxStrategy : public EquationSystem<Domain> {
+ MaxStrategy(const ConcreteEquationSystem<Domain>& system)
+ : _system(system), _expressions(system.variableCount(), NULL), _strategy(system.maxExpressionCount(), 0) {
}
- MaxStrategy<T>& operator=(const MaxStrategy& other) {
- if (_length != other._length) {
- _length = other._length;
- delete[] _assignment;
- _assignment = new unsigned int[_length];
- }
- for (unsigned int i = 0; i < _length; ++i) {
- _assignment[i] = other._assignment[i];
+ ~MaxStrategy() {
+ for (int i = 0, length = _system.variableCount();
+ i < length;
+ ++i) {
+ Expression<Domain>* expr = _expressions[_system.variable(i)];
+ if (expr)
+ delete expr;
}
- return *this;
}
- const unsigned int& operator[] (const MaxExpression<T> x) const {
- if (x.id() >= _length) {
- throw "Array out of bounds";
+ const Expression<Domain>* operator[](const Variable<Domain>& v) const {
+ if (_expressions[v] == NULL) {
+ Expression<Domain>* expression = new MaxStrategyExpression<Domain>(*_system[v], _strategy);
+ _expressions[v] = expression;
+ return expression;
+ } else {
+ return _expressions[v];
}
- return _assignment[x.id()];
}
- unsigned int& operator[] (const MaxExpression<T>& x) {
- if (x.id() >= _length) {
- throw "Array out of bounds";
- }
- return _assignment[x.id()];
+
+ unsigned int get(const MaxExpression<Domain>& e) const {
+ return _strategy[e];
}
- VariableAssignment<T> operator() (const EquationSystem<T>& eqns, const VariableAssignment<T>& rho) const {
- return eqns.foreach(*this, rho);
+ unsigned int set(const MaxExpression<Domain>& e, unsigned int i) {
+ _strategy[e] = i;
+ return i;
}
- T operator() (const Expression<T>& expr, const VariableAssignment<T>& rho) const {
- const MaxExpression<T>* max = dynamic_cast<const MaxExpression<T>*>(&expr);
- if (max == NULL) {
- return expr(rho);
- } else {
- return (*this)(*max->argument(_assignment[max->id()]), rho);
+
+ VariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho) const {
+ StableVariableAssignment<Domain>* result = this->assignment(-infinity<Domain>());
+ for (unsigned int i = 0, length = _system.variableCount();
+ i < length;
+ ++i) {
+ const Variable<Domain>& var = _system.variable(i);
+ const Expression<Domain>& expr = * (*this)[var];
+ (*result)[var] = expr.eval(rho);
}
+ return result;
}
- MaxStrategy<T> improve(const EquationSystem<T>& s, const VariableAssignment<T>& rho) const {
- MaxStrategy<T> newStrategy(*this);
- for (unsigned int i = 0; i < _length; ++i) {
- const MaxExpression<T>& expr = *s.getMax(i);
- const T oldValue = (*this)(expr, rho);
-
- // this relies on the fact that deeper MaxExpressions have a lower id
- // than the MaxExpressions containing them. This means that we know that
- // we have enough of a strategy to work with what we have within us
- std::pair<const T,unsigned int> best = expr.bestStrategy(rho, newStrategy);
-
- if (best.first > oldValue)
- newStrategy[expr] = best.second;
- }
- return newStrategy;
+
+ unsigned int variableCount() const {
+ return _system.variableCount();
}
- bool operator== (const MaxStrategy& other) const {
- if (_length != other._length)
- return false;
- for (unsigned int i = 0; i < _length; ++i) {
- if (_assignment[i] != other._assignment[i]) {
- return false;
+ Variable<Domain>& variable(unsigned int i) const {
+ return _system.variable(i);
+ }
+
+ StableVariableAssignment<Domain>* assignment(const Domain& v) const {
+ return _system.assignment(v);
+ }
+
+ bool equalAssignments(const VariableAssignment<Domain>& l, const VariableAssignment<Domain>& r) const {
+ return _system.equalAssignments(l, r);
+ }
+
+
+ struct ImprovementOperator {
+ virtual ~ImprovementOperator() { }
+ virtual bool improve(MaxStrategy<Domain>&, const VariableAssignment<Domain>&) const = 0;
+ };
+ bool improve(const ImprovementOperator& op, const VariableAssignment<Domain>& rho) {
+ return op.improve(*this, rho);
+ }
+
+ struct NaiveImprovementOperator : public ImprovementOperator {
+ bool improve(MaxStrategy<Domain>& strat, const VariableAssignment<Domain>& rho) const {
+ bool changed = false;
+ for (unsigned int i = 0, length = strat._system.maxExpressionCount();
+ i < length;
+ ++i) {
+ MaxExpression<Domain>& expr = strat._system.maxExpression(i);
+ Domain bestValue = MaxStrategyExpression<Domain>(expr, strat._strategy).eval(rho);
+ unsigned int lastIndex= strat.get(expr);
+ unsigned int bestIndex = strat.get(expr);
+
+ // 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)
+ 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._strategy).eval(rho);
+ if (bestValue < value) {
+ bestValue = value;
+ bestIndex = j;
+ }
+ }
+ if (bestIndex != lastIndex) {
+ changed = true;
+ strat.set(expr, bestIndex);
+ }
}
+ return changed;
}
- return true;
- }
- bool operator!= (const MaxStrategy& other) const {
- return !(*this == other);
+ };
+
+ struct RepeatedImprovementOperator : public ImprovementOperator {
+ RepeatedImprovementOperator(const ImprovementOperator& op)
+ : _subImprovement(op) { }
+ bool improve(MaxStrategy<Domain>& strat, const VariableAssignment<Domain>& rho) const {
+ if (_subImprovement.improve(strat, rho)) {
+ VariableAssignment<Domain>* rho2 = strat.eval(rho);
+ improve(strat, *rho2);
+ delete rho2;
+ return true;
+ }
+ return false;
+ }
+ private:
+ const ImprovementOperator& _subImprovement;
+ };
+
+ void print(std::ostream& cout) const {
+ cout << _system << std::endl;
}
+
private:
- unsigned int _length;
- unsigned int* _assignment;
+ const ConcreteEquationSystem<Domain>& _system;
+ mutable IdMap<Variable<Domain>,Expression<Domain>*> _expressions;
+ IdMap<MaxExpression<Domain>,unsigned int> _strategy;
};
#endif
generated by cgit v1.2.3 (git 2.46.2) at 2024-11-10 06:39:18 +0000