summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore11
-rw-r--r--impl/Complete.hpp30
-rw-r--r--impl/EquationSystem.hpp2
-rw-r--r--impl/Expression.hpp10
-rw-r--r--impl/MaxStrategy.hpp73
-rw-r--r--impl/VariableAssignment.hpp30
-rw-r--r--impl/main.cpp7
-rw-r--r--impl/test/10.eqns9
-rw-r--r--impl/test/10.soln9
-rw-r--r--impl/test/7.eqns2
-rw-r--r--impl/test/8.eqns4
-rw-r--r--impl/test/8.soln4
-rw-r--r--impl/test/9.eqns5
-rw-r--r--impl/test/9.soln5
14 files changed, 156 insertions, 45 deletions
diff --git a/.gitignore b/.gitignore
index 93c639b..0173d7a 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,14 @@
/impl/build/*
/impl/parser/*
+*.log
+*.dvi
+*.ps
+*.aux
+*.blg
+*.bbl
+*.toc
+*.lof
+*.lot
+*.out
+*~
gmon.out
diff --git a/impl/Complete.hpp b/impl/Complete.hpp
index e3ec15a..336ab24 100644
--- a/impl/Complete.hpp
+++ b/impl/Complete.hpp
@@ -7,23 +7,38 @@
template<typename T>
T infinity() { }
+template<typename T>
+T unknown(const T&) { }
template<typename T>
struct Complete {
Complete()
- : _value(0), _infinity(false) { }
+ : _value(0), _infinity(false), _unknown(false) { }
Complete(const T& value)
- : _value(value), _infinity(false) { }
+ : _value(value), _infinity(false), _unknown(false) { }
Complete(const T& value, const bool& infinity)
- : _value(value), _infinity(infinity) {
+ : _value(value), _infinity(infinity), _unknown(false) {
assert(value != 0 || infinity == false);
}
Complete(const Complete& other)
- : _value(other._value), _infinity(other._infinity) { }
+ : _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;
+ }
Complete& operator=(const Complete& other) {
_value = other._value;
_infinity = other._infinity;
+ _unknown = other._unknown;
return *this;
}
Complete& operator+=(const Complete& other) {
@@ -102,6 +117,7 @@ struct Complete {
private:
T _value;
bool _infinity;
+ bool _unknown;
};
template<typename Z>
@@ -114,6 +130,8 @@ 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 {
@@ -126,5 +144,9 @@ 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 2fd24bd..a0ba8a1 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);
diff --git a/impl/Expression.hpp b/impl/Expression.hpp
index 9c4ac9f..cba9582 100644
--- a/impl/Expression.hpp
+++ b/impl/Expression.hpp
@@ -151,7 +151,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;
@@ -173,9 +173,11 @@ struct MaxExpression : public OperatorExpression<Domain> {
i < length;
++i) {
const Domain value = this->_arguments[i]->eval(rho, strat);
- if (bestValue < value) {
- bestValue = value;
- bestIndex = i;
+ if (!value.isUnknown()) {
+ if (bestValue < value) {
+ bestValue = value;
+ bestIndex = i;
+ }
}
}
return bestIndex;
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index f4026dd..ba7cc11 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -34,7 +34,8 @@ template<typename Domain>
struct DynamicMaxStrategy : public MaxStrategy<Domain> {
DynamicMaxStrategy(
const EquationSystem<Domain>& system
- ) : _system(system),
+ ) : _frozen(false),
+ _system(system),
_rho(NULL),
_values(system.maxExpressionCount(), 0),
_stable(system.maxExpressionCount()),
@@ -62,28 +63,26 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
}
unsigned int get(const MaxExpression<Domain>& e) const {
- return _values[e];
- }
-
- unsigned int get(const MaxExpression<Domain>& e) {
if (!_frozen)
solve(e);
return _values[e];
}
- void invalidate(const Variable<Domain>& v) {
- log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl;
- _stable.filter(_var_influence[v]);
-
- IdSet<MaxExpression<Domain> > infl = _var_influence[v];
- _var_influence[v].clear();
-
- for (typename IdSet<MaxExpression<Domain> >::iterator
- it = infl.begin(),
- end = infl.end();
- it != end;
- ++it) {
- solve(_system.maxExpression(*it));
+ void invalidate(const Variable<Domain>& v) const {
+ 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]);
+
+ IdSet<MaxExpression<Domain> > infl = _var_influence[v];
+ _var_influence[v].clear();
+ for (typename IdSet<MaxExpression<Domain> >::iterator
+ it = infl.begin(),
+ end = infl.end();
+ it != end;
+ ++it) {
+ solve(_system.maxExpression(*it));
+ }
}
}
@@ -99,6 +98,7 @@ private:
stack_depth--;
if (val != _values[x]) {
+
log::strategy << x << " => " << *x.arguments()[val] << std::endl;
IdSet<MaxExpression<Domain> > oldInfluence = _influence[x];
@@ -126,6 +126,16 @@ 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,
@@ -144,6 +154,30 @@ private:
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;
+ };
+
struct DependencyStrategy : public MaxStrategy<Domain> {
DependencyStrategy(DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
: _strat(strat),
@@ -161,7 +195,8 @@ private:
const MaxExpression<Domain>& _expr;
};
-private:
+private:
+ mutable bool _frozen;
const EquationSystem<Domain>& _system;
DynamicVariableAssignment<Domain>* _rho;
IdMap<MaxExpression<Domain>,unsigned int> _values;
diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp
index 2a63756..cfce925 100644
--- a/impl/VariableAssignment.hpp
+++ b/impl/VariableAssignment.hpp
@@ -26,7 +26,7 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
const Domain& value=infinity<Domain>()
) : _system(system),
_strategy(strat),
- _values(system.variableCount(), value),
+ _values(system.variableCount(), unknown(infinity<Domain>())),
_stable(system.variableCount()),
_influence(system.variableCount(),
IdSet<Variable<Domain> >(system.variableCount())),
@@ -59,17 +59,20 @@ struct DynamicVariableAssignment : public VariableAssignment<Domain> {
log::fixpoint << indent() << "Invalidating " << x << std::endl;
if (_stable.contains(x)) {
_stable.remove(x);
- _values[x] = infinity<Domain>();
-
+ _values[x] = unknown(infinity<Domain>());
+
+ solve(x);
+ /*
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));
+ it = infl.begin(),
+ ei = infl.end();
+ it != ei;
+ ++it) {
+ invalidate(_system.variable(*it));
}
+ */
}
}
@@ -125,11 +128,12 @@ private:
};
const EquationSystem<Domain>& _system;
- DynamicMaxStrategy<Domain>& _strategy;
- IdMap<Variable<Domain>, Domain> _values;
- IdSet<Variable<Domain> > _stable;
- IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
- bool _frozen;
+ const DynamicMaxStrategy<Domain>& _strategy;
+ mutable IdMap<Variable<Domain>, Domain> _values;
+public:
+ mutable IdSet<Variable<Domain> > _stable;
+private:
+ mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
};
#endif
diff --git a/impl/main.cpp b/impl/main.cpp
index 84f17dd..02faca5 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -161,13 +161,14 @@ int main (int argc, char* argv[]) {
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] << endl;
+ if (variables.find(var.name()) != variables.end()) {
+ cout << var.name() << " = " << rho[var].asKnown() << endl;
+ }
}
} else {
for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) {
Variable<ZBar>& var = system.variable(i);
- cout << var.name() << " = " << rho[var] << endl;
+ cout << var.name() << " = " << rho[var].asKnown() << endl;
}
}
*/
diff --git a/impl/test/10.eqns b/impl/test/10.eqns
new file mode 100644
index 0000000..39598f4
--- /dev/null
+++ b/impl/test/10.eqns
@@ -0,0 +1,9 @@
+x = 0
+w = max(x,y,z,u,w)
+y = w
+z = w
+u = a
+a = b
+b = c
+c = d
+d = w
diff --git a/impl/test/10.soln b/impl/test/10.soln
new file mode 100644
index 0000000..20a47ca
--- /dev/null
+++ b/impl/test/10.soln
@@ -0,0 +1,9 @@
+x = 0
+w = 0
+y = 0
+z = 0
+u = 0
+a = 0
+b = 0
+c = 0
+d = 0
diff --git a/impl/test/7.eqns b/impl/test/7.eqns
index 2789f0e..1f69268 100644
--- a/impl/test/7.eqns
+++ b/impl/test/7.eqns
@@ -1,5 +1,5 @@
x = 0
-y = max(-inf, x, a)
+y = max(x,a)
a = b
b = c
c = d
diff --git a/impl/test/8.eqns b/impl/test/8.eqns
new file mode 100644
index 0000000..c9e9c4e
--- /dev/null
+++ b/impl/test/8.eqns
@@ -0,0 +1,4 @@
+x = 0
+w = max(x,y,z)
+y = w
+z = w
diff --git a/impl/test/8.soln b/impl/test/8.soln
new file mode 100644
index 0000000..1945057
--- /dev/null
+++ b/impl/test/8.soln
@@ -0,0 +1,4 @@
+x = 0
+w = 0
+y = 0
+z = 0
diff --git a/impl/test/9.eqns b/impl/test/9.eqns
new file mode 100644
index 0000000..b85e118
--- /dev/null
+++ b/impl/test/9.eqns
@@ -0,0 +1,5 @@
+x = 0
+w = max(x,y,z,u)
+y = w
+z = w
+u = w
diff --git a/impl/test/9.soln b/impl/test/9.soln
new file mode 100644
index 0000000..616c5e5
--- /dev/null
+++ b/impl/test/9.soln
@@ -0,0 +1,5 @@
+x = 0
+w = 0
+y = 0
+z = 0
+u = 0
generated by cgit v1.2.3 (git 2.46.2) at 2024-12-25 06:46:23 +0000