summaryrefslogtreecommitdiff
path: root/impl
diff options
context:
space:
mode:
authorCarlo Zancanaro <carlo@carlo-laptop>2012-10-30 20:56:38 +1100
committerCarlo Zancanaro <carlo@carlo-laptop>2012-10-30 20:56:38 +1100
commit6a4786bde976e9a023c7f65a395384d214c5102c (patch)
treef3dd303f21dfa0be269a932dd05438041a290f27 /impl
parentff2030f3a19926334fbe3a043c5f88622c17c2f8 (diff)
parent95b82ea3830c3a34455323167894647e3aa773a6 (diff)
Merge branch 'master' of ssh://bitbucket.org/czan/honours
Conflicts: impl/test/run
Diffstat (limited to 'impl')
-rw-r--r--impl/Complete.hpp30
-rw-r--r--impl/EquationSystem.hpp4
-rw-r--r--impl/Expression.hpp73
-rw-r--r--impl/IdSet.hpp4
-rw-r--r--impl/Makefile2
-rw-r--r--impl/MaxStrategy.hpp162
-rw-r--r--impl/VariableAssignment.hpp95
-rw-r--r--impl/main.cpp32
-rw-r--r--impl/systems/example.eqns4
-rw-r--r--impl/test/7.eqns2
10 files changed, 227 insertions, 181 deletions
diff --git a/impl/Complete.hpp b/impl/Complete.hpp
index 336ab24..e3ec15a 100644
--- a/impl/Complete.hpp
+++ b/impl/Complete.hpp
@@ -7,38 +7,23 @@
template<typename T>
T infinity() { }
-template<typename T>
-T unknown(const T&) { }
template<typename T>
struct Complete {
Complete()
- : _value(0), _infinity(false), _unknown(false) { }
+ : _value(0), _infinity(false) { }
Complete(const T& value)
- : _value(value), _infinity(false), _unknown(false) { }
+ : _value(value), _infinity(false) { }
Complete(const T& value, const bool& infinity)
- : _value(value), _infinity(infinity), _unknown(false) {
+ : _value(value), _infinity(infinity) {
assert(value != 0 || infinity == false);
}
Complete(const Complete& other)
- : _value(other._value), _infinity(other._infinity), _unknown(other._unknown) { }
- Complete(const Complete& other, bool unknown)
- : _value(other._value), _infinity(other._infinity), _unknown(unknown) { }
-
- Complete asUnknown() const {
- return Complete(*this, true);
- }
- Complete asKnown() const {
- return Complete(*this, false);
- }
- bool isUnknown() const {
- return _unknown;
- }
+ : _value(other._value), _infinity(other._infinity) { }
Complete& operator=(const Complete& other) {
_value = other._value;
_infinity = other._infinity;
- _unknown = other._unknown;
return *this;
}
Complete& operator+=(const Complete& other) {
@@ -117,7 +102,6 @@ struct Complete {
private:
T _value;
bool _infinity;
- bool _unknown;
};
template<typename Z>
@@ -130,8 +114,6 @@ std::istream& operator>>(std::istream& cin, Complete<Z>& num) {
template<typename Z>
std::ostream& operator<<(std::ostream& cout, const Complete<Z>& num) {
- if (num._unknown)
- cout << "(unknown)";
if (num._infinity) {
cout << (num._value > 0 ? "inf" : "-inf");
} else {
@@ -144,9 +126,5 @@ template<>
Complete<int> infinity() {
return Complete<int>(1, true);
}
-template<>
-Complete<int> unknown(const Complete<int>& x) {
- return Complete<int>(x, true);
-}
#endif
diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
index a0ba8a1..3342cc7 100644
--- a/impl/EquationSystem.hpp
+++ b/impl/EquationSystem.hpp
@@ -31,7 +31,7 @@ struct EquationSystem {
delete _expr_to_var;
}
- MaxExpression<Domain>& maxExpression(const std::vector<Expression<Domain>*> arguments) {
+ MaxExpression<Domain>& maxExpression(const std::vector<Expression<Domain>*>& arguments) {
unsigned int id = _max_expressions.size();
Maximum<Domain>* max = new Maximum<Domain>();
MaxExpression<Domain>* expr = new MaxExpression<Domain>(id, *max, arguments);
@@ -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 cba9582..dcf7201 100644
--- a/impl/Expression.hpp
+++ b/impl/Expression.hpp
@@ -4,6 +4,7 @@
#include <string>
#include <vector>
#include <sstream>
+#include <set>
#include "IdMap.hpp"
#include "Operator.hpp"
@@ -31,15 +32,22 @@ struct Expression {
return NULL;
}
- virtual Domain eval(const VariableAssignment<Domain>&) const = 0;
- virtual Domain eval(const VariableAssignment<Domain>& rho,
+ virtual Domain eval(VariableAssignment<Domain>&) const = 0;
+ virtual Domain eval(VariableAssignment<Domain>& rho,
const MaxStrategy<Domain>&) const {
return eval(rho);
}
+ virtual Domain eval(VariableAssignment<Domain>& rho,
+ MaxStrategy<Domain>&) const {
+ return eval(rho);
+ }
virtual void mapTo(Variable<Domain>&, IdMap<MaxExpression<Domain>, Variable<Domain>*>&) const {
}
+ virtual void subMaxExprs(std::set<const MaxExpression<Domain>*>&) const {
+ }
+
virtual void print(std::ostream&) const = 0;
};
@@ -48,7 +56,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 +80,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 +98,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 +108,17 @@ 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, const MaxStrategy<Domain>& strat) const {
+ std::vector<Domain> argumentValues;
+ for (typename std::vector<Expression<Domain>*>::const_iterator it = _arguments.begin();
+ it != _arguments.end();
+ ++it) {
+ argumentValues.push_back((*it)->eval(rho, strat));
+ }
+ return _operator.eval(argumentValues);
+ }
+
+ 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();
@@ -130,6 +148,14 @@ struct OperatorExpression : public Expression<Domain> {
}
}
+ virtual void subMaxExprs(std::set<const MaxExpression<Domain>*>& exprs) const {
+ for (unsigned int i = 0, length = _arguments.size();
+ i < length;
+ ++i) {
+ _arguments[i]->subMaxExprs(exprs);
+ }
+ }
+
void print(std::ostream& cout) const {
cout << _operator << "(";
for (unsigned int i = 0, length = _arguments.size();
@@ -151,7 +177,7 @@ struct OperatorExpression : public Expression<Domain> {
template<typename Domain>
struct MaxExpression : public OperatorExpression<Domain> {
MaxExpression(const unsigned int& id, const Maximum<Domain>& op, const std::vector<Expression<Domain>*>& arguments)
- : OperatorExpression<Domain>(op, arguments), _id(id) {}
+ : OperatorExpression<Domain>(op, arguments), _id(id) { }
MaxExpression* toMaxExpression() {
return this;
@@ -161,29 +187,33 @@ 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, const MaxStrategy<Domain>& strat) const {
+ log::fixpoint << "const MaxExpression eval" << std::endl;
+ return this->_arguments[strat.get(*this)]->eval(rho, strat);
+ }
+
+ virtual Domain eval(VariableAssignment<Domain>& rho, MaxStrategy<Domain>& strat) const {
+ log::strategy << "const MaxExpression eval" << std::endl;
return this->_arguments[strat.get(*this)]->eval(rho, strat);
}
- unsigned int bestStrategy(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
- Domain bestValue = this->eval(rho, strat);
- unsigned int bestIndex = strat.get(*this);
+ unsigned int bestStrategy(VariableAssignment<Domain>& rho, MaxStrategy<Domain>& strat) const {
+ unsigned int bestIndex = const_cast<const MaxStrategy<Domain>&>(strat).get(*this);
+ Domain bestValue = this->_arguments[bestIndex]->eval(rho, strat);
for (unsigned int i = 0, length = this->_arguments.size();
i < length;
++i) {
const Domain value = this->_arguments[i]->eval(rho, strat);
- if (!value.isUnknown()) {
- if (bestValue < value) {
- bestValue = value;
- bestIndex = i;
- }
+ if (bestValue < value) {
+ bestIndex = i;
+ bestValue = value;
}
}
return bestIndex;
}
- virtual void mapTo(Variable<Domain>& v, IdMap<MaxExpression<Domain>, Variable<Domain>*>& m) const {
+ virtual void mapTo(Variable<Domain>& v, IdMap<MaxExpression<Domain>,Variable<Domain>*>& m) const {
m[*this] = &v;
for (unsigned int i = 0, length = this->_arguments.size();
i < length;
@@ -192,6 +222,15 @@ struct MaxExpression : public OperatorExpression<Domain> {
}
}
+ virtual void subMaxExprs(std::set<const MaxExpression<Domain>*>& exprs) const {
+ exprs.insert(this);
+ for (unsigned int i = 0, length = this->_arguments.size();
+ i < length;
+ ++i) {
+ this->_arguments[i]->subMaxExprs(exprs);
+ }
+ }
+
unsigned int id() const {
return _id;
}
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/Makefile b/impl/Makefile
index 6fc6f3b..ca0b37d 100644
--- a/impl/Makefile
+++ b/impl/Makefile
@@ -2,7 +2,7 @@ CC=gcc
CPP=g++
BUILD=build
PARSER=parser
-FLAGS=-Wall -Werror -Wextra -pedantic -lantlr3c -fno-exceptions
+FLAGS=-Wall -Werror -Wextra -pedantic -lantlr3c -fno-exceptions -lrt
NORMAL_FLAGS=$(FLAGS) -g -pg
OPTIMISED_FLAGS=$(FLAGS) -O3
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index 3ed7972..5534597 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -9,10 +9,10 @@
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);
+ return const_cast<const MaxStrategy<Domain>*>(this)->get(e);
}
+ virtual unsigned int get(const MaxExpression<Domain>& e) const = 0;
};
unsigned int stack_depth = 1;
@@ -34,46 +34,67 @@ template<typename Domain>
struct DynamicMaxStrategy : public MaxStrategy<Domain> {
DynamicMaxStrategy(
const EquationSystem<Domain>& system
- ) : _frozen(false),
- _system(system),
+ ) : _system(system),
_rho(NULL),
_values(system.maxExpressionCount(), 0),
_stable(system.maxExpressionCount()),
_influence(system.maxExpressionCount(),
IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
_var_influence(system.variableCount(),
- IdSet<MaxExpression<Domain> >(system.maxExpressionCount()))
+ IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
+ _changed(false)
{}
void setRho(DynamicVariableAssignment<Domain>& rho) {
_rho = &rho;
}
+ void hasChanged(bool c) {
+ _changed = c;
+ }
+
+ bool hasChanged() const {
+ return _changed;
+ }
+
unsigned int get(const MaxExpression<Domain>& e) const {
- // slightly hacky
- return const_cast<DynamicMaxStrategy<Domain>*>(this)->get(e);
+ log::strategy << indent() << "Look up " << e << std::endl;
+ return _values[e];
}
unsigned int get(const MaxExpression<Domain>& e) {
- if (!_frozen)
- solve(e);
+ log::strategy << indent() << "Solve for " << e << std::endl;
+ solve(e);
return _values[e];
}
void invalidate(const Variable<Domain>& v) {
- log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl;
- if (_system[v] && _stable.contains(*_system[v])) {
- _stable.remove(*_system[v]);
- _stable.filter(_var_influence[v]);
+ log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl;
+ //log::debug << indent() << " var-influence sets " << _var_influence << std::endl;
+
+ IdSet<MaxExpression<Domain> > infl = _var_influence[v];
+ for (typename IdSet<MaxExpression<Domain> >::iterator
+ it = infl.begin(),
+ end = infl.end();
+ it != end;
+ ++it) {
+ invalidate(_system.maxExpression(*it));
+ }
+ }
- IdSet<MaxExpression<Domain> > infl = _var_influence[v];
- _var_influence[v].clear();
+ void invalidate(const MaxExpression<Domain>& v) {
+ if (_stable.contains(v)) {
+ log::strategy << indent() << "Invalidating " << v << std::endl;
+ //log::debug << indent() << " influence sets " << _influence << std::endl;
+ _stable.remove(v);
+
+ IdSet<MaxExpression<Domain> > infl = _influence[v];
for (typename IdSet<MaxExpression<Domain> >::iterator
it = infl.begin(),
end = infl.end();
it != end;
++it) {
- solve(_system.maxExpression(*it));
+ invalidate(_system.maxExpression(*it));
}
}
}
@@ -84,20 +105,23 @@ 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]) {
-
log::strategy << x << " => " << *x.arguments()[val] << std::endl;
IdSet<MaxExpression<Domain> > oldInfluence = _influence[x];
- _influence[x].clear();
+ //_influence[x].clear();
_values[x] = val;
+ _changed = true;
_rho->invalidate(*_system.varFromExpr(x));
+
+ //_rho->stabilise();
_stable.filter(oldInfluence);
@@ -118,56 +142,27 @@ private:
}
}
- const DynamicMaxStrategy& freeze() const {
- _frozen = true;
- return *this;
- }
-
- const DynamicMaxStrategy& thaw() const {
- _frozen = false;
- return *this;
- }
-
struct DependencyAssignment : public VariableAssignment<Domain>{
DependencyAssignment(DynamicMaxStrategy& strat,
VariableAssignment<Domain>& rho,
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) {
+ // solve the strategy for this variable, too
+ _strat.solve(*_strat._system[var]);
_strat._var_influence[var].insert(_expr);
+ _strat._influence[*_strat._system[var]].insert(_expr);
return _rho[var];
}
private:
DynamicMaxStrategy& _strat;
VariableAssignment<Domain>& _rho;
const MaxExpression<Domain>& _expr;
- };
-
- struct InvalidatingAssignment : public VariableAssignment<Domain>{
- InvalidatingAssignment(DynamicVariableAssignment<Domain>& rho)
- : _rho(rho) {
- }
- ~InvalidatingAssignment() {
- for (typename std::set<const Variable<Domain>*>::iterator
- it = seen.begin(),
- ei = seen.end();
- it != ei;
- ++it) {
- if (!_old_stable.contains(**it))
- _rho.invalidate(**it);
- }
- }
- const Domain& operator[](const Variable<Domain>& var) const {
- seen.insert(&var);
- return _rho[var];
- }
- private:
- DynamicVariableAssignment<Domain>& _rho;
- IdSet<Variable<Domain> > _old_stable;
- mutable std::set<const Variable<Domain>*> seen;
+ IdSet<Variable<Domain> > _current;
};
struct DependencyStrategy : public MaxStrategy<Domain> {
@@ -176,10 +171,12 @@ private:
_expr(expr) {
}
unsigned int get(const MaxExpression<Domain>& e) const {
+ _strat._influence[e].insert(_expr);
+ return _strat._values[e];
+ }
+ unsigned int get(const MaxExpression<Domain>& e) {
_strat.solve(e);
- if (&_expr != &e) {
- _strat._influence[e].insert(_expr);
- }
+ _strat._influence[e].insert(_expr);
return _strat._values[e];
}
private:
@@ -187,14 +184,55 @@ private:
const MaxExpression<Domain>& _expr;
};
-private:
- mutable bool _frozen;
+private:
const EquationSystem<Domain>& _system;
DynamicVariableAssignment<Domain>* _rho;
IdMap<MaxExpression<Domain>,unsigned int> _values;
IdSet<MaxExpression<Domain> > _stable;
IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence;
+ bool _changed;
+};
+
+
+template<typename Domain>
+struct Solver {
+ Solver(const EquationSystem<Domain>& system)
+ : _system(system),
+ _strategy(system),
+ _rho(_system, _strategy, -infinity<Domain>()) {
+ _strategy.setRho(_rho);
+ }
+
+ Domain solve(Variable<Domain>& var) {
+ MaxExpression<Domain>& rhs = *_system[var];
+
+ // _rho automatically keeps up to date with changes made to the
+ // strategy, so you don't need to stabilise it
+
+ _strategy.get(rhs);
+
+
+ /*
+ do {
+ _strategy.hasChanged(false);
+
+ log::debug << "Stabilise assignment (toplevel)" << std::endl;
+ _rho.stabilise();
+
+ log::debug << "Improve strategy (toplevel)" << std::endl;
+ // improve strategy
+ _strategy.get(rhs);
+ log::debug << (_strategy.hasChanged() ? "Strategy has changed - loop again" : "Strategy has not changed - terminate") << std::endl;
+ } while (_strategy.hasChanged());
+ */
+
+ return _rho[var];
+ }
+private:
+ const EquationSystem<Domain>& _system;
+ DynamicMaxStrategy<Domain> _strategy;
+ DynamicVariableAssignment<Domain> _rho;
};
diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp
index 19403a8..2e081e6 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"
@@ -22,58 +19,44 @@ template<typename Domain>
struct DynamicVariableAssignment : public VariableAssignment<Domain> {
DynamicVariableAssignment(
const EquationSystem<Domain>& system,
- DynamicMaxStrategy<Domain>& strat
+ DynamicMaxStrategy<Domain>& strat,
+ const Domain& value=infinity<Domain>()
) : _system(system),
_strategy(strat),
- _values(system.variableCount(), unknown(infinity<Domain>())),
- _stable(system.variableCount()),
+ _values(system.variableCount(), value),
+ _unstable(system.variableCount()),
_influence(system.variableCount(),
- IdSet<Variable<Domain> >(system.variableCount())),
- _frozen(false)
+ IdSet<Variable<Domain> >(system.variableCount()))
{ }
- void freeze() {
- _frozen = true;
- }
-
- void thaw() {
- _frozen = false;
- }
-
- bool is_frozen() {
- return _frozen;
- }
-
- const Domain& operator[](const Variable<Domain>& var) const {
- // slightly hacky
- return const_cast<DynamicVariableAssignment<Domain>&>(*this)[var];
+ const Domain operator[](const Variable<Domain>& var) {
+ solve(var);
+ return _values[var];
}
- const Domain& operator[](const Variable<Domain>& var) {
- if (!_frozen)
+ /*void stabilise() {
+ if (!_unstable.empty()) {
+ Variable<Domain>& var = _system.variable(*_unstable.begin());
solve(var);
- return _values[var];
- }
+ }
+ }*/
- void invalidate(const Variable<Domain>& x, bool also_solve=true) {
- log::fixpoint << indent() << "Invalidating " << x << std::endl;
- if (_stable.contains(x)) {
- _stable.remove(x);
- _values[x] = unknown(infinity<Domain>());
+ void invalidate(const Variable<Domain>& x) {
+ if (!_unstable.contains(x)) {
+ log::fixpoint << indent() << "Invalidating " << x << std::endl;
+
+ _unstable.insert(x);
+ _values[x] = infinity<Domain>();
IdSet<Variable<Domain> > infl = _influence[x];
+ _influence[x].clear();
+
for (typename IdSet<Variable<Domain> >::iterator
- it = infl.begin(),
- ei = infl.end();
- it != ei;
- ++it) {
- invalidate(_system.variable(*it), false);
- }
-
- if (also_solve) {
- solve(x);
- if (_values[x] == infinity<Domain>())
- _values[x] = _values[x].asKnown();
+ it = infl.begin(),
+ ei = infl.end();
+ it != ei;
+ ++it) {
+ invalidate(_system.variable(*it));
}
}
}
@@ -81,25 +64,28 @@ 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);
+ // we don't want the assignment to affect the strategy, so we're
+ // going to use a const reference here
+ const DynamicMaxStrategy<Domain>& const_strat = _strategy;
+ DependencyAssignment assignment(*this, x);
+ Domain val = _system[x]->eval(assignment, const_strat);
stack_depth--;
if (val != _values[x]) {
log::fixpoint << x << " = " << val << std::endl;
+
+ _strategy.invalidate(x);
IdSet<Variable<Domain> > oldInfluence = _influence[x];
_influence[x].clear();
_values[x] = val;
- _strategy.invalidate(x);
-
- _stable.filter(oldInfluence);
+ _unstable.absorb(oldInfluence);
for (typename IdSet<Variable<Domain> >::iterator it = oldInfluence.begin();
it != oldInfluence.end();
@@ -119,8 +105,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;
}
@@ -132,9 +118,8 @@ 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;
};
#endif
diff --git a/impl/main.cpp b/impl/main.cpp
index b83894d..1fed389 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -1,5 +1,6 @@
#include "Log.hpp"
#include <iostream>
+#include <iomanip>
#include <vector>
#include <sstream>
#include "Complete.hpp"
@@ -136,44 +137,46 @@ int main (int argc, char* argv[]) {
EquationSystemParser_equation_system_return ret = parser -> equation_system(parser);
+ std::cerr << "Parse complete." << std::endl;
+
EquationSystem<ZBar> system;
treeToSystem<ZBar>(ret.tree, system);
log::debug << system << endl;
system.indexMaxExpressions(); // make reverse-lookup O(1) instead of O(n)
- DynamicMaxStrategy<ZBar> strategy(system);
- DynamicVariableAssignment<ZBar> rho(system, strategy);
- strategy.setRho(rho);
+ std::cerr << "System created and indexed." << std::endl;
+
+ Solver<ZBar> solver(system); // local *and* lazy. I love it!
timespec start, finish;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
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()) {
- rho[var];
- }
+ for (set<string>::iterator it = variables.begin(), ei = variables.end();
+ it != ei;
+ ++it) {
+ solver.solve(system.variable(*it));
}
} else {
for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) {
Variable<ZBar>& var = system.variable(i);
- rho[var];
+ solver.solve(var);
}
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &finish);
+ std::cerr << "System solved." << std::endl;
+
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() << " = " << rho[var].asKnown() << endl;
- }
+ if (variables.find(var.name()) != variables.end())
+ 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() << " = " << rho[var].asKnown() << endl;
+ cout << var.name() << " = " << solver.solve(var) << endl;
}
}
@@ -185,8 +188,7 @@ int main (int argc, char* argv[]) {
temp.tv_sec = finish.tv_sec-start.tv_sec;
temp.tv_nsec = finish.tv_nsec-start.tv_nsec;
}
- cerr << "Time taken: " << temp.tv_sec << " seconds and " << temp.tv_nsec << " nanoseconds." << endl;
-
+ cerr << "Time taken: " << temp.tv_sec << "." << setfill('0') << setw(9) << temp.tv_nsec << " seconds." << endl;
parser -> free(parser);
tokens -> free(tokens);
diff --git a/impl/systems/example.eqns b/impl/systems/example.eqns
index 71ee74a..dc59a01 100644
--- a/impl/systems/example.eqns
+++ b/impl/systems/example.eqns
@@ -1,3 +1,3 @@
-x1 = max(0, min(x1-1, x2))
+x1 = max(0, min(x1 - 1, x2))
x2 = max(0, 5+x1, x1)
-x3 = max(0, 1+x3, 0+x1)
+x3 = max(0, 1 + x3, 0 + x1)
diff --git a/impl/test/7.eqns b/impl/test/7.eqns
index 1f69268..2789f0e 100644
--- a/impl/test/7.eqns
+++ b/impl/test/7.eqns
@@ -1,5 +1,5 @@
x = 0
-y = max(x,a)
+y = max(-inf, x, a)
a = b
b = c
c = d