summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--impl/EquationSystem.hpp2
-rw-r--r--impl/Expression.hpp18
-rw-r--r--impl/IdSet.hpp4
-rw-r--r--impl/MaxStrategy.hpp96
-rw-r--r--impl/VariableAssignment.hpp55
-rw-r--r--impl/main.cpp7
6 files changed, 104 insertions, 78 deletions
diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
index 2fd24bd..3342cc7 100644
--- a/impl/EquationSystem.hpp
+++ b/impl/EquationSystem.hpp
@@ -105,7 +105,7 @@ struct EquationSystem {
}
}
- virtual bool equalAssignments(const VariableAssignment<Domain>& l, const VariableAssignment<Domain>& r) const {
+ virtual bool equalAssignments(VariableAssignment<Domain>& l, VariableAssignment<Domain>& r) const {
for (unsigned int i = 0, length = _variables.size();
i < length;
++i) {
diff --git a/impl/Expression.hpp b/impl/Expression.hpp
index 9c4ac9f..c005fd6 100644
--- a/impl/Expression.hpp
+++ b/impl/Expression.hpp
@@ -31,9 +31,9 @@ struct Expression {
return NULL;
}
- virtual Domain eval(const VariableAssignment<Domain>&) const = 0;
- virtual Domain eval(const VariableAssignment<Domain>& rho,
- const MaxStrategy<Domain>&) const {
+ virtual Domain eval(VariableAssignment<Domain>&) const = 0;
+ virtual Domain eval(VariableAssignment<Domain>& rho,
+ MaxStrategy<Domain>&) const {
return eval(rho);
}
@@ -48,7 +48,7 @@ struct Constant : public Expression<Domain> {
Constant(const Domain& value)
: _value(value) { }
- virtual Domain eval(const VariableAssignment<Domain>&) const {
+ virtual Domain eval(VariableAssignment<Domain>&) const {
return _value;
}
@@ -72,7 +72,7 @@ struct Variable : public Expression<Domain> {
return _name;
}
- virtual Domain eval(const VariableAssignment<Domain>& rho) const {
+ virtual Domain eval(VariableAssignment<Domain>& rho) const {
return rho[*this];
}
@@ -90,7 +90,7 @@ struct OperatorExpression : public Expression<Domain> {
OperatorExpression(const Operator<Domain>& op, const std::vector<Expression<Domain>*>& arguments)
: _operator(op), _arguments(arguments) { }
- virtual Domain eval(const VariableAssignment<Domain>& rho) const {
+ virtual Domain eval(VariableAssignment<Domain>& rho) const {
std::vector<Domain> argumentValues;
for (typename std::vector<Expression<Domain>*>::const_iterator it = _arguments.begin();
it != _arguments.end();
@@ -100,7 +100,7 @@ struct OperatorExpression : public Expression<Domain> {
return _operator.eval(argumentValues);
}
- virtual Domain eval(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
+ virtual Domain eval(VariableAssignment<Domain>& rho, MaxStrategy<Domain>& strat) const {
std::vector<Domain> argumentValues;
for (typename std::vector<Expression<Domain>*>::const_iterator it = _arguments.begin();
it != _arguments.end();
@@ -161,11 +161,11 @@ struct MaxExpression : public OperatorExpression<Domain> {
return this;
}
- virtual Domain eval(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
+ virtual Domain eval(VariableAssignment<Domain>& rho, MaxStrategy<Domain>& strat) const {
return this->_arguments[strat.get(*this)]->eval(rho, strat);
}
- unsigned int bestStrategy(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
+ unsigned int bestStrategy(VariableAssignment<Domain>& rho, MaxStrategy<Domain>& strat) const {
Domain bestValue = this->eval(rho, strat);
unsigned int bestIndex = strat.get(*this);
diff --git a/impl/IdSet.hpp b/impl/IdSet.hpp
index 950b1e1..bf98502 100644
--- a/impl/IdSet.hpp
+++ b/impl/IdSet.hpp
@@ -96,6 +96,10 @@ class IdSet {
return _set.size();
}
+ bool empty() const {
+ return _set.empty();
+ }
+
private:
unsigned int _range;
std::set<unsigned int> _set;
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index f4026dd..d908c7b 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -9,10 +9,7 @@
template<typename Domain>
struct MaxStrategy {
virtual ~MaxStrategy() { }
- virtual unsigned int get(const MaxExpression<Domain>& e) const = 0;
- virtual unsigned int get(const MaxExpression<Domain>& e) {
- return const_cast<const MaxStrategy*>(this)->get(e);
- }
+ virtual unsigned int get(const MaxExpression<Domain>& e) = 0;
};
unsigned int stack_depth = 1;
@@ -61,10 +58,6 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
_rho = &rho;
}
- unsigned int get(const MaxExpression<Domain>& e) const {
- return _values[e];
- }
-
unsigned int get(const MaxExpression<Domain>& e) {
if (!_frozen)
solve(e);
@@ -93,9 +86,10 @@ private:
_stable.insert(x);
log::strategy << indent() << "Stabilise " << x << std::endl;
- stack_depth++;
- unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x),
- DependencyStrategy(*this, x));
+ stack_depth++;
+ DependencyAssignment assignment(*this, *_rho, x);
+ DependencyStrategy depStrat(*this, x);
+ unsigned int val = x.bestStrategy(assignment, depStrat);
stack_depth--;
if (val != _values[x]) {
@@ -107,6 +101,12 @@ private:
_rho->invalidate(*_system.varFromExpr(x));
+ _rho->thaw();
+ this->freeze();
+ _rho->stabilise();
+ _rho->freeze();
+ this->thaw();
+
_stable.filter(oldInfluence);
for (typename IdSet<MaxExpression<Domain> >::iterator
@@ -132,16 +132,25 @@ private:
const MaxExpression<Domain>& expr)
: _strat(strat),
_rho(rho),
- _expr(expr) {
+ _expr(expr),
+ _current(strat._system.variableCount()) {
}
- const Domain& operator[](const Variable<Domain>& var) const {
+ const Domain operator[](const Variable<Domain>& var) {
_strat._var_influence[var].insert(_expr);
- return _rho[var];
+ if (_current.contains(var)) {
+ return _rho[var];
+ } else {
+ _current.insert(var);
+ Domain val = _strat._system[var]->eval(_rho, _strat);
+ _current.remove(var);
+ return val;
+ }
}
private:
DynamicMaxStrategy& _strat;
VariableAssignment<Domain>& _rho;
const MaxExpression<Domain>& _expr;
+ IdSet<Variable<Domain> > _current;
};
struct DependencyStrategy : public MaxStrategy<Domain> {
@@ -149,7 +158,7 @@ private:
: _strat(strat),
_expr(expr) {
}
- unsigned int get(const MaxExpression<Domain>& e) const {
+ unsigned int get(const MaxExpression<Domain>& e) {
_strat.solve(e);
if (&_expr != &e) {
_strat._influence[e].insert(_expr);
@@ -172,40 +181,39 @@ private:
};
-template<typename T>
-IdMap<Variable<T>,T> solve_for(const EquationSystem<T>& system) {
- IdMap<Variable<T>,T> result(system.variableCount(), infinity<T>());
+template<typename Domain>
+struct Solver {
+ Solver(const EquationSystem<Domain>& system)
+ : _system(system),
+ _strategy(system),
+ _rho(_system, _strategy, -infinity<Domain>()) {
+ _strategy.setRho(_rho);
+ }
- DynamicMaxStrategy<T> strategy(system);
- DynamicVariableAssignment<T> rho(system, strategy, -infinity<T>());
- strategy.setRho(rho);
+ Domain solve(Variable<Domain>& var) {
+ MaxExpression<Domain>& rhs = *_system[var];
- bool changed;
- do {
- changed = false;
+ do {
+ _rho.has_changed(false);
- // improve strategy
- rho.freeze();
- strategy.thaw();
- for (unsigned int i = 0; i < system.variableCount(); ++i) {
- strategy.get(*system[system.variable(i)]);
- }
+ // improve strategy
+ _rho.freeze();
+ _strategy.thaw();
+ _strategy.get(rhs);
- // iterate fixpoint
- strategy.freeze();
- rho.thaw();
- for (unsigned int i = 0; i < system.variableCount(); ++i) {
- Variable<T>& var = system.variable(i);
- T val = rho[var];
- if (result[var] != val) {
- result[var] = val;
- changed = true;
- }
- }
- } while(changed);
+ // iterate fixpoint
+ _strategy.freeze();
+ _rho.thaw();
+ _rho.stabilise();
+ } while (_rho.has_changed());
- return result;
-}
+ return _rho[var];
+ }
+private:
+ const EquationSystem<Domain>& _system;
+ DynamicMaxStrategy<Domain> _strategy;
+ DynamicVariableAssignment<Domain> _rho;
+};
/*template<typename Domain>
diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp
index 2a63756..e074f6f 100644
--- a/impl/VariableAssignment.hpp
+++ b/impl/VariableAssignment.hpp
@@ -7,10 +7,7 @@
template<typename Domain>
struct VariableAssignment {
virtual ~VariableAssignment() { }
- virtual const Domain& operator[](const Variable<Domain>&) const = 0;
- virtual const Domain& operator[](const Variable<Domain>& x) {
- return (*const_cast<const VariableAssignment*>(this))[x];
- }
+ virtual const Domain operator[](const Variable<Domain>& x) = 0;
};
#include "EquationSystem.hpp"
@@ -27,11 +24,13 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
) : _system(system),
_strategy(strat),
_values(system.variableCount(), value),
- _stable(system.variableCount()),
+ _unstable(system.variableCount()),
_influence(system.variableCount(),
IdSet<Variable<Domain> >(system.variableCount())),
- _frozen(false)
- { }
+ _frozen(false),
+ _changed(false)
+ {
+ }
void freeze() {
_frozen = true;
@@ -41,25 +40,37 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
_frozen = false;
}
- bool is_frozen() {
+ bool is_frozen() const {
return _frozen;
}
- const Domain& operator[](const Variable<Domain>& var) const {
- return _values[var];
+ void has_changed(bool c) {
+ _changed = c;
+ }
+
+ bool has_changed() const {
+ return _changed;
}
- const Domain& operator[](const Variable<Domain>& var) {
+ const Domain operator[](const Variable<Domain>& var) {
if (!_frozen)
solve(var);
return _values[var];
}
+ void stabilise() {
+ if (!_unstable.empty()) {
+ Variable<Domain>& var = _system.variable(*_unstable.begin());
+ solve(var);
+ }
+ }
+
void invalidate(const Variable<Domain>& x) {
log::fixpoint << indent() << "Invalidating " << x << std::endl;
- if (_stable.contains(x)) {
- _stable.remove(x);
+ if (!_unstable.contains(x)) {
+ _unstable.insert(x);
_values[x] = infinity<Domain>();
+ _changed = true;
IdSet<Variable<Domain> > infl = _influence[x];
_influence[x].clear();
@@ -76,13 +87,13 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
private:
void solve(const Variable<Domain>& x) {
- if (!_stable.contains(x)) {
- _stable.insert(x);
+ if (_unstable.contains(x)) {
+ _unstable.remove(x);
log::fixpoint << indent() << "Stabilise " << x << std::endl;
stack_depth++;
- Domain val = _system[x]->eval(DependencyAssignment(*this, x),
- _strategy);
+ DependencyAssignment assignment(*this, x);
+ Domain val = _system[x]->eval(assignment, _strategy);
stack_depth--;
if (val != _values[x]) {
@@ -91,10 +102,11 @@ private:
IdSet<Variable<Domain> > oldInfluence = _influence[x];
_influence[x].clear();
_values[x] = val;
+ _changed = true;
_strategy.invalidate(x);
- _stable.filter(oldInfluence);
+ _unstable.absorb(oldInfluence);
for (typename IdSet<Variable<Domain> >::iterator it = oldInfluence.begin();
it != oldInfluence.end();
@@ -114,8 +126,8 @@ private:
struct DependencyAssignment : public VariableAssignment<Domain> {
DependencyAssignment(DynamicVariableAssignment& assignment, const Variable<Domain>& var)
: _assignment(assignment), _var(var) { }
- const Domain& operator[](const Variable<Domain>& x) const {
- const Domain& result = _assignment[x];
+ const Domain operator[](const Variable<Domain>& x) {
+ const Domain result = _assignment[x];
_assignment._influence[x].insert(_var);
return result;
}
@@ -127,9 +139,10 @@ private:
const EquationSystem<Domain>& _system;
DynamicMaxStrategy<Domain>& _strategy;
IdMap<Variable<Domain>, Domain> _values;
- IdSet<Variable<Domain> > _stable;
+ IdSet<Variable<Domain> > _unstable;
IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
bool _frozen;
+ bool _changed;
};
#endif
diff --git a/impl/main.cpp b/impl/main.cpp
index 84f17dd..94351ec 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -140,19 +140,20 @@ int main (int argc, char* argv[]) {
log::debug << system << endl;
system.indexMaxExpressions(); // make reverse-lookup O(1) instead of O(n)
- IdMap<Variable<ZBar>,ZBar> result = solve_for(system);
+ Solver<ZBar> solver(system); // local *and* lazy. I love it!
if (variables.size() > 0) {
for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) {
Variable<ZBar>& var = system.variable(i);
if (variables.find(var.name()) != variables.end())
- cout << var.name() << " = " << result[var] << endl;
+ cout << var.name() << " = " << solver.solve(var) << endl;
}
} else {
for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) {
Variable<ZBar>& var = system.variable(i);
- cout << var.name() << " = " << result[var] << endl;
+ cout << var.name() << " = " << solver.solve(var) << endl;
}
}
+
/*
DynamicMaxStrategy<ZBar> strategy(system);
DynamicVariableAssignment<ZBar> rho(system, strategy);
generated by cgit v1.2.3 (git 2.46.2) at 2024-12-25 06:55:32 +0000