summaryrefslogtreecommitdiff
path: root/impl
diff options
context:
space:
mode:
Diffstat (limited to 'impl')
-rw-r--r--impl/EquationSystem.hpp35
-rw-r--r--impl/IdSet.hpp10
-rw-r--r--impl/ImprovementOperator.hpp71
-rw-r--r--impl/Log.hpp2
-rw-r--r--impl/Makefile2
-rw-r--r--impl/main.cpp1
6 files changed, 85 insertions, 36 deletions
diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
index d09bef2..c7e5f4c 100644
--- a/impl/EquationSystem.hpp
+++ b/impl/EquationSystem.hpp
@@ -7,12 +7,16 @@
#include "Operator.hpp"
#include "Expression.hpp"
#include "VariableAssignment.hpp"
+#include "IdMap.hpp"
template<typename Domain>
struct MaxStrategy;
template<typename Domain>
struct EquationSystem {
+ EquationSystem()
+ : _expr_to_var(NULL) { }
+
virtual ~EquationSystem() {
for (typename std::set<Expression<Domain>*>::iterator it = _expressions.begin();
it != _expressions.end();
@@ -24,6 +28,8 @@ struct EquationSystem {
++it) {
delete *it;
}
+ if (_expr_to_var)
+ delete _expr_to_var;
}
MaxExpression<Domain>& maxExpression(const std::vector<Expression<Domain>*>& arguments) {
@@ -86,7 +92,7 @@ struct EquationSystem {
StableVariableAssignment<Domain>* assignment(const Domain& value) const {
return new StableVariableAssignment<Domain>(_variables.size(), value);
}
- VariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho) const {
+ StableVariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho) const {
StableVariableAssignment<Domain>* result = this->assignment(-infinity<Domain>());
for (unsigned int i = 0, length = _variables.size();
i < length;
@@ -97,7 +103,7 @@ struct EquationSystem {
}
return result;
}
- VariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
+ StableVariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
StableVariableAssignment<Domain>* result = this->assignment(-infinity<Domain>());
for (unsigned int i = 0, length = _variables.size();
i < length;
@@ -109,12 +115,28 @@ struct EquationSystem {
return result;
}
- Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const {
+ void indexMaxExpressions() {
+ _expr_to_var = new IdMap<MaxExpression<Domain>,Variable<Domain>*>(maxExpressionCount(), NULL);
for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) {
- if (_right_sides[i] == &expr)
- return _variables[i];
+ (*_expr_to_var)[*_right_sides[i]] = _variables[i];
+ }
+ }
+
+ Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const {
+ if (_expr_to_var) { // we've indexed:
+ auto* maxExpr = dynamic_cast<const MaxExpression<Domain>*>(&expr);
+ if (maxExpr) {
+ return (*_expr_to_var)[*maxExpr];
+ } else {
+ return NULL;
+ }
+ } else {
+ for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) {
+ if (_right_sides[i] == &expr)
+ return _variables[i];
+ }
+ return NULL;
}
- return NULL;
}
virtual bool equalAssignments(const VariableAssignment<Domain>& l, const VariableAssignment<Domain>& r) const {
@@ -141,6 +163,7 @@ struct EquationSystem {
std::set<Expression<Domain>*> _expressions;
std::vector<Variable<Domain>*> _variables;
std::map<std::string, Variable<Domain>*> _variable_names;
+ IdMap<MaxExpression<Domain>, Variable<Domain>*>* _expr_to_var;
std::vector<MaxExpression<Domain>*> _max_expressions;
std::vector<MaxExpression<Domain>*> _right_sides;
};
diff --git a/impl/IdSet.hpp b/impl/IdSet.hpp
index 99f89cc..950b1e1 100644
--- a/impl/IdSet.hpp
+++ b/impl/IdSet.hpp
@@ -39,6 +39,16 @@ class IdSet {
}
}
+ IdSet inverse() const {
+ IdSet other(_range);
+ for (unsigned int i = 0; i < _range; ++i) {
+ if (_set.find(i) == _set.end()) {
+ other._set.insert(i);
+ }
+ }
+ return other;
+ }
+
bool contains(const T& obj) const {
return _set.find(obj.id()) != _set.end();
}
diff --git a/impl/ImprovementOperator.hpp b/impl/ImprovementOperator.hpp
index 5cee78c..e6b2ded 100644
--- a/impl/ImprovementOperator.hpp
+++ b/impl/ImprovementOperator.hpp
@@ -10,7 +10,7 @@ struct ImprovementOperator {
virtual bool improve(
EquationSystem<Domain>& system,
ConcreteMaxStrategy<Domain>& strat,
- const VariableAssignment<Domain>& rho,
+ StableVariableAssignment<Domain>& rho,
IdSet<Variable<Domain> >& changedIn,
IdSet<Variable<Domain> >& changedOut
) const = 0;
@@ -21,7 +21,7 @@ struct NaiveImprovementOperator : public ImprovementOperator<Domain> {
bool improve(
EquationSystem<Domain>& system,
ConcreteMaxStrategy<Domain>& strat,
- const VariableAssignment<Domain>& rho,
+ StableVariableAssignment<Domain>& rho,
IdSet<Variable<Domain> >&,
IdSet<Variable<Domain> >&
) const {
@@ -52,12 +52,12 @@ struct RepeatedImprovementOperator : public ImprovementOperator<Domain> {
bool improve(
EquationSystem<Domain>& system,
ConcreteMaxStrategy<Domain>& strat,
- const VariableAssignment<Domain>& rho,
+ StableVariableAssignment<Domain>& rho,
IdSet<Variable<Domain> >& changedIn,
IdSet<Variable<Domain> >& changedOut
) const {
if (_subImprovement.improve(system, strat, rho, changedIn, changedOut)) {
- VariableAssignment<Domain>* rho2 = system.eval(rho, strat);
+ StableVariableAssignment<Domain>* rho2 = system.eval(rho, strat);
improve(system, strat, *rho2, changedIn, changedOut);
delete rho2;
return true;
@@ -81,7 +81,7 @@ struct SmartImprovementOperator : public ImprovementOperator<Domain> {
const EquationSystem<Domain>& system,
ConcreteMaxStrategy<Domain>& strat,
IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain>>>& influence,
- const VariableAssignment<Domain>& rho,
+ StableVariableAssignment<Domain>& rho,
IdSet<MaxExpression<Domain>>& stable,
IdSet<MaxExpression<Domain>>& changed
) : _system(system),
@@ -125,7 +125,7 @@ struct SmartImprovementOperator : public ImprovementOperator<Domain> {
struct DependencyAssignment : public VariableAssignment<Domain>{
DependencyAssignment(const DynamicMaxStrategy& strat,
- const VariableAssignment<Domain>& rho,
+ StableVariableAssignment<Domain>& rho,
const MaxExpression<Domain>& expr)
: _strat(strat),
_rho(rho),
@@ -133,11 +133,12 @@ struct SmartImprovementOperator : public ImprovementOperator<Domain> {
}
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;
- const VariableAssignment<Domain>& _rho;
+ StableVariableAssignment<Domain>& _rho;
const MaxExpression<Domain>& _expr;
};
@@ -148,7 +149,9 @@ struct SmartImprovementOperator : public ImprovementOperator<Domain> {
}
unsigned int get(const MaxExpression<Domain>& e) const {
_strat.solve(e);
- _strat._influence[e].insert(_expr);
+ if (&_expr != &e) {
+ _strat._influence[e].insert(_expr);
+ }
return _strat._values.get(e);
}
private:
@@ -158,7 +161,7 @@ struct SmartImprovementOperator : public ImprovementOperator<Domain> {
private:
const EquationSystem<Domain>& _system;
- const VariableAssignment<Domain>& _rho;
+ StableVariableAssignment<Domain>& _rho;
ConcreteMaxStrategy<Domain>& _values;
IdSet<MaxExpression<Domain>>& _stable;
IdSet<MaxExpression<Domain>>& _changed;
@@ -166,28 +169,34 @@ struct SmartImprovementOperator : public ImprovementOperator<Domain> {
};
void invalidateSubexpressions(IdSet<MaxExpression<Domain>>& set, Expression<Domain>& expr) const {
- MaxExpression<Domain>* maxExpr = static_cast<MaxExpression<Domain>*>(&expr);
+ MaxExpression<Domain>* maxExpr = dynamic_cast<MaxExpression<Domain>*>(&expr);
if (maxExpr != NULL && maxExpr->id() < _system.maxExpressionCount()) {
- invalidateAll(set, *maxExpr);
- for (auto it = maxExpr->arguments().begin(),
- end = maxExpr->arguments().end();
- it != end;
- ++it) {
- invalidateSubexpressions(set, **it);
+ if (invalidateAll(set, *maxExpr)) {
+ for (auto it = maxExpr->arguments().begin(),
+ end = maxExpr->arguments().end();
+ it != end;
+ ++it) {
+ invalidateSubexpressions(set, **it);
+ }
}
}
}
- void invalidateAll(IdSet<MaxExpression<Domain>>& set, MaxExpression<Domain>& expr) const {
+ bool invalidateAll(IdSet<MaxExpression<Domain>>& set, MaxExpression<Domain>& expr) const {
if (!set.contains(expr)) {
set.insert(expr);
for (auto it = _influence[expr].begin(),
end = _influence[expr].end();
it != end;
++it) {
- invalidateSubexpressions(set, _system.maxExpression(*it));
+ if (!set.contains(_system.maxExpression(*it))) {
+ set.insert(_system.maxExpression(*it));
+ }
+ //invalidateSubexpressions(set, _system.maxExpression(*it));
}
+ return true;
}
+ return false;
}
void markChanged(IdSet<Variable<Domain>>& set, MaxExpression<Domain>& expr, IdSet<MaxExpression<Domain>>& seen) const {
@@ -210,14 +219,16 @@ struct SmartImprovementOperator : public ImprovementOperator<Domain> {
bool improve(
EquationSystem<Domain>&,
ConcreteMaxStrategy<Domain>& stratOut,
- const VariableAssignment<Domain>& rho,
+ 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) {
- _first_run = false;
+ invalidSet.invert(); // everything is invalid on the first run
+ _first_run = false;
} else {
for (auto it = changedIn.begin(),
end = changedIn.end();
@@ -225,17 +236,19 @@ struct SmartImprovementOperator : public ImprovementOperator<Domain> {
++it) {
invalidateSubexpressions(invalidSet, *_system[_system.variable(*it)]);
}
- invalidSet.invert();
+ stableSet = invalidSet.inverse();
}
- log::debug << "stable: " << invalidSet;
- log::debug << "infl: " << _influence;
- DynamicMaxStrategy strat(_system, stratOut, _influence, rho, invalidSet, changedSet);
- auto inv = invalidSet;
- for (unsigned int i = 0, length = _system.maxExpressionCount();
- i < length;
- ++i) {
- strat.get(_system.maxExpression(i));
+ log::strategy << "stable: " << stableSet;
+ log::strategy << "infl: " << _influence;
+ DynamicMaxStrategy strat(_system, stratOut, _influence, rho, stableSet, changedSet);
+ log::strategy << "invalid: " << invalidSet;
+ for (auto it = invalidSet.begin(),
+ end = invalidSet.end();
+ it != end;
+ ++it) {
+ log::strategy << _system.maxExpression(*it);
+ strat.get(_system.maxExpression(*it));
}
IdSet<MaxExpression<Domain>> seen;
for (auto it = changedSet.begin(),
diff --git a/impl/Log.hpp b/impl/Log.hpp
index a920906..1e340c7 100644
--- a/impl/Log.hpp
+++ b/impl/Log.hpp
@@ -40,8 +40,10 @@ namespace log {
return logger;
}
+ Logger info(std::cout, "info");
Logger trace(std::cerr, "trace");
Logger strategy(std::cerr, "strategy");
+ Logger fixpoint(std::cerr, "fixpoint");
Logger debug(std::cerr, "debug");
}
diff --git a/impl/Makefile b/impl/Makefile
index 588c3ab..3192191 100644
--- a/impl/Makefile
+++ b/impl/Makefile
@@ -1,7 +1,7 @@
CC=gcc
CPP=g++
BUILD=build/
-FLAGS=-Wall -Werror -Wextra -pedantic -g -lantlr3c -pg -std=c++11
+FLAGS=-Wall -Werror -Wextra -pedantic -lantlr3c -std=c++11 -g -pg
all: main
diff --git a/impl/main.cpp b/impl/main.cpp
index 0317390..31f2937 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -155,6 +155,7 @@ int main (int argc, char* argv[]) {
}
log::debug << system;
+ system.indexMaxExpressions(); // make reverse-lookup O(1) instead of O(n)
StableVariableAssignment<ZBar> result(system.variableCount(), infinity<ZBar>());
ConcreteMaxStrategy<ZBar> strategy(system);
IdSet<Variable<ZBar>> s1(system.variableCount());
generated by cgit v1.2.3 (git 2.46.0) at 2024-09-20 03:50:33 +0000