summaryrefslogtreecommitdiff
path: root/impl
diff options
context:
space:
mode:
Diffstat (limited to 'impl')
-rw-r--r--impl/EquationSystem.hpp18
-rw-r--r--impl/MaxStrategy.hpp147
-rw-r--r--impl/main.cpp16
-rw-r--r--impl/systems/example.eqns6
4 files changed, 91 insertions, 96 deletions
diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
index 50a0e45..5549674 100644
--- a/impl/EquationSystem.hpp
+++ b/impl/EquationSystem.hpp
@@ -13,11 +13,13 @@ struct EquationSystem {
virtual ~EquationSystem() { }
virtual const Expression<Domain>* operator[](const Variable<Domain>&) const = 0;
virtual VariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho) const = 0;
+
virtual unsigned int variableCount() const = 0;
virtual Variable<Domain>& variable(unsigned int) const = 0;
+
virtual StableVariableAssignment<Domain>* assignment(const Domain& value) const = 0;
+ virtual Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const = 0;
virtual bool equalAssignments(const VariableAssignment<Domain>&, const VariableAssignment<Domain>&) const = 0;
-
virtual void print(std::ostream& cout) const = 0;
};
@@ -86,10 +88,10 @@ struct ConcreteEquationSystem : public EquationSystem<Domain> {
return *constant;
}
- Expression<Domain>* operator[](const Variable<Domain>& var) const {
+ MaxExpression<Domain>* operator[](const Variable<Domain>& var) const {
return _right_sides[var.id()];
}
- Expression<Domain>*& operator[](const Variable<Domain>& var) {
+ MaxExpression<Domain>*& operator[](const Variable<Domain>& var) {
return _right_sides[var.id()];
}
@@ -108,6 +110,14 @@ struct ConcreteEquationSystem : public EquationSystem<Domain> {
return result;
}
+ Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const {
+ for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) {
+ if (_right_sides[i] == &expr)
+ return _variables[i];
+ }
+ return NULL;
+ }
+
virtual bool equalAssignments(const VariableAssignment<Domain>& l, const VariableAssignment<Domain>& r) const {
for (unsigned int i = 0, length = _variables.size();
i < length;
@@ -133,7 +143,7 @@ struct ConcreteEquationSystem : public EquationSystem<Domain> {
std::vector<Variable<Domain>*> _variables;
std::map<std::string, Variable<Domain>*> _variable_names;
std::vector<MaxExpression<Domain>*> _max_expressions;
- std::vector<Expression<Domain>*> _right_sides;
+ std::vector<MaxExpression<Domain>*> _right_sides;
};
template<typename T>
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index 9fa7768..977036f 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -6,8 +6,44 @@
#include "IdSet.hpp"
template<typename Domain>
+struct MaxStrategy : public EquationSystem<Domain> {
+ MaxStrategy(const EquationSystem<Domain>& sub)
+ : _sub(sub) { }
+
+ virtual ~MaxStrategy() { }
+ virtual const Expression<Domain>* operator[](const Variable<Domain>& var) const {
+ return _sub[var];
+ }
+ virtual VariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho) const {
+ return _sub.eval(rho);
+ }
+ virtual unsigned int variableCount() const {
+ return _sub.variableCount();
+ }
+ virtual Variable<Domain>& variable(unsigned int i) const {
+ return _sub.variable(i);
+ }
+ virtual StableVariableAssignment<Domain>* assignment(const Domain& value) const {
+ return _sub.assignment(value);
+ }
+ virtual bool equalAssignments(const VariableAssignment<Domain>& r1, const VariableAssignment<Domain>& r2) const {
+ return _sub.equalAssignments(r1, r2);
+ }
+ virtual Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const {
+ return _sub.varFromExpr(expr);
+ }
+ virtual void print(std::ostream& cout) const {
+ return _sub.print(cout);
+ }
+
+ virtual unsigned int get(const MaxExpression<Domain>& e) const = 0;
+ private:
+ const EquationSystem<Domain>& _sub;
+};
+
+template<typename Domain>
struct MaxStrategyExpression : public Expression<Domain> {
- MaxStrategyExpression(const Expression<Domain>& expr, const IdMap<MaxExpression<Domain>,unsigned int>& strategy)
+ MaxStrategyExpression(const Expression<Domain>& expr, const MaxStrategy<Domain>& strategy)
: _expr(expr), _strategy(strategy) { }
virtual Domain eval(const VariableAssignment<Domain>& rho) const {
@@ -17,7 +53,7 @@ struct MaxStrategyExpression : public Expression<Domain> {
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];
+ unsigned int i = _strategy.get(*maxExpr);
return MaxStrategyExpression(*args[i], _strategy).eval(rho);
} else {
std::vector<Domain> argumentValues;
@@ -38,16 +74,19 @@ struct MaxStrategyExpression : public Expression<Domain> {
}
private:
const Expression<Domain>& _expr;
- const IdMap<MaxExpression<Domain>,unsigned int>& _strategy;
+ const MaxStrategy<Domain>& _strategy;
};
template<typename Domain>
-struct MaxStrategy : public EquationSystem<Domain> {
- MaxStrategy(const ConcreteEquationSystem<Domain>& system)
- : _system(system), _expressions(system.variableCount(), NULL), _strategy(system.maxExpressionCount(), 0) {
+struct ConcreteMaxStrategy : public MaxStrategy<Domain> {
+ ConcreteMaxStrategy(const ConcreteEquationSystem<Domain>& system)
+ : MaxStrategy<Domain>(system),
+ _system(system),
+ _expressions(system.variableCount(), NULL),
+ _strategy(system.maxExpressionCount(), 0) {
}
- ~MaxStrategy() {
+ ~ConcreteMaxStrategy() {
for (int i = 0, length = _system.variableCount();
i < length;
++i) {
@@ -59,7 +98,7 @@ struct MaxStrategy : public EquationSystem<Domain> {
const Expression<Domain>* operator[](const Variable<Domain>& v) const {
if (_expressions[v] == NULL) {
- Expression<Domain>* expression = new MaxStrategyExpression<Domain>(*_system[v], _strategy);
+ Expression<Domain>* expression = new MaxStrategyExpression<Domain>(*_system[v], *this);
_expressions[v] = expression;
return expression;
} else {
@@ -94,6 +133,14 @@ struct MaxStrategy : public EquationSystem<Domain> {
Variable<Domain>& variable(unsigned int i) const {
return _system.variable(i);
}
+
+ unsigned int maxExpressionCount() const {
+ return _system.maxExpressionCount();
+ }
+
+ MaxExpression<Domain>& maxExpression(unsigned int i) const {
+ return _system.maxExpression(i);
+ }
StableVariableAssignment<Domain>* assignment(const Domain& v) const {
return _system.assignment(v);
@@ -103,86 +150,18 @@ struct MaxStrategy : public EquationSystem<Domain> {
return _system.equalAssignments(l, r);
}
-
- struct ImprovementOperator {
- virtual ~ImprovementOperator() { }
- virtual bool improve(
- MaxStrategy<Domain>& strat,
- const VariableAssignment<Domain>& rho,
- const IdSet<Variable<Domain> >& changedIn,
- IdSet<Variable<Domain> >& changedOut
- ) const = 0;
- };
- bool improve(const ImprovementOperator& op, const VariableAssignment<Domain>& rho, const IdSet<Variable<Domain> >& changedIn, IdSet<Variable<Domain> >& changedOut) {
- return op.improve(*this, rho, changedIn, changedOut);
- }
-
- struct NaiveImprovementOperator : public ImprovementOperator {
- bool improve(
- MaxStrategy<Domain>& strat,
- const VariableAssignment<Domain>& rho,
- const IdSet<Variable<Domain> >& changedIn,
- IdSet<Variable<Domain> >& changedOut
- ) 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;
- }
- };
-
- struct RepeatedImprovementOperator : public ImprovementOperator {
- RepeatedImprovementOperator(const ImprovementOperator& op)
- : _subImprovement(op) { }
-
- bool improve(
- MaxStrategy<Domain>& strat,
- const VariableAssignment<Domain>& rho,
- const 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& _subImprovement;
- };
-
- struct DependencyImprovementOperator : public ImprovementOperator {
- };
-
void print(std::ostream& cout) const {
cout << _system << std::endl;
}
+ const ConcreteEquationSystem<Domain>& system() const {
+ return _system;
+ }
+
+ const IdMap<MaxExpression<Domain>,unsigned int>& strategy() const {
+ return _strategy;
+ }
+
private:
const ConcreteEquationSystem<Domain>& _system;
mutable IdMap<Variable<Domain>,Expression<Domain>*> _expressions;
diff --git a/impl/main.cpp b/impl/main.cpp
index b761587..26aedbe 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -6,6 +6,7 @@
#include "Operator.hpp"
#include "EquationSystem.hpp"
#include "MaxStrategy.hpp"
+#include "ImprovementOperator.hpp"
#include "FixpointAlgorithm.hpp"
extern "C" {
@@ -126,14 +127,17 @@ int main (int argc, char* argv[]) {
}
// PARSE ARGUMENTS - strat improvement
- MaxStrategy<ZBar>::ImprovementOperator* naiveImprovement = new MaxStrategy<ZBar>::NaiveImprovementOperator();
- MaxStrategy<ZBar>::ImprovementOperator* improvement = NULL;
+ ImprovementOperator<ZBar>* naiveImprovement = new NaiveImprovementOperator<ZBar>();
+ ImprovementOperator<ZBar>* improvement = NULL;
if (!strcmp(argv[3], "repeat")) {
- improvement = new MaxStrategy<ZBar>::RepeatedImprovementOperator(*naiveImprovement);
+ improvement = new RepeatedImprovementOperator<ZBar>(*naiveImprovement);
cout << "Repeated strategy improvement" << endl;
} else if (!strcmp(argv[3], "naive")) {
improvement = naiveImprovement;
cout << "Naive strategy improvement" << endl;
+ } else if (!strcmp(argv[3], "smart")) {
+ improvement = new SmartImprovementOperator<ZBar>(system);
+ cout << "Smart strategy improvement" << endl;
} else {
cout << "Unknown strategy improvement algorithm." << endl;
}
@@ -143,7 +147,7 @@ int main (int argc, char* argv[]) {
cout << system << endl;
StableVariableAssignment<ZBar> result(system.variableCount(), infinity<ZBar>());
- MaxStrategy<ZBar> strategy(system);
+ ConcreteMaxStrategy<ZBar> strategy(system);
IdSet<Variable<ZBar> > s1(system.variableCount());
IdSet<Variable<ZBar> > s2(system.variableCount());
bool changed = false;
@@ -159,7 +163,9 @@ int main (int argc, char* argv[]) {
cout << endl;
exit(0);*/
- changed = strategy.improve(*improvement, result, s1, s2);
+ s2.clear();
+ changed = improvement->improve(strategy, result, s1, s2);
+ std::cout << (changed ? "true" : "false") << std::endl;
} while(changed);
cout << endl;
diff --git a/impl/systems/example.eqns b/impl/systems/example.eqns
index 9ef3135..71ee74a 100644
--- a/impl/systems/example.eqns
+++ b/impl/systems/example.eqns
@@ -1,3 +1,3 @@
-x1 = max([0,0], min(x1-[1,1], x2))
-x2 = max([0,0], [5,5]+x1, x1)
-x3 = max([0,0], [1,1]+x3, [0,0]+x1)
+x1 = max(0, min(x1-1, x2))
+x2 = max(0, 5+x1, x1)
+x3 = max(0, 1+x3, 0+x1)
generated by cgit v1.2.3 (git 2.46.2) at 2024-12-25 17:05:43 +0000