From c065ae2bd1176b17d137e0f52df6ef1d9af9e757 Mon Sep 17 00:00:00 2001
From: Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au>
Date: Fri, 26 Oct 2012 16:29:52 +1100
Subject: Try to make the correct solver into a local solver

As far as I can tell, it's worked! Hooray!
---
 impl/EquationSystem.hpp     |  2 +-
 impl/Expression.hpp         | 18 ++++-----
 impl/IdSet.hpp              |  4 ++
 impl/MaxStrategy.hpp        | 96 ++++++++++++++++++++++++---------------------
 impl/VariableAssignment.hpp | 55 ++++++++++++++++----------
 impl/main.cpp               |  7 ++--
 6 files changed, 104 insertions(+), 78 deletions(-)

(limited to 'impl')

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);
-- 
cgit v1.2.3


From e5e937b77b45dd683af97da82f8c8a1761c6d4f0 Mon Sep 17 00:00:00 2001
From: Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au>
Date: Fri, 26 Oct 2012 16:35:28 +1100
Subject: Add some tests, and stuff.

---
 impl/test/10.eqns | 9 +++++++++
 impl/test/10.soln | 9 +++++++++
 impl/test/11.eqns | 2 ++
 impl/test/11.soln | 2 ++
 impl/test/12.eqns | 2 ++
 impl/test/12.soln | 2 ++
 impl/test/13.eqns | 3 +++
 impl/test/13.soln | 3 +++
 impl/test/8.eqns  | 4 ++++
 impl/test/8.soln  | 4 ++++
 impl/test/9.eqns  | 5 +++++
 impl/test/9.soln  | 5 +++++
 12 files changed, 50 insertions(+)
 create mode 100644 impl/test/10.eqns
 create mode 100644 impl/test/10.soln
 create mode 100644 impl/test/11.eqns
 create mode 100644 impl/test/11.soln
 create mode 100644 impl/test/12.eqns
 create mode 100644 impl/test/12.soln
 create mode 100644 impl/test/13.eqns
 create mode 100644 impl/test/13.soln
 create mode 100644 impl/test/8.eqns
 create mode 100644 impl/test/8.soln
 create mode 100644 impl/test/9.eqns
 create mode 100644 impl/test/9.soln

(limited to 'impl')

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/11.eqns b/impl/test/11.eqns
new file mode 100644
index 0000000..4edc114
--- /dev/null
+++ b/impl/test/11.eqns
@@ -0,0 +1,2 @@
+x = y
+y = max(-100000, y+1)
diff --git a/impl/test/11.soln b/impl/test/11.soln
new file mode 100644
index 0000000..cdfcb1f
--- /dev/null
+++ b/impl/test/11.soln
@@ -0,0 +1,2 @@
+x = inf
+y = inf
diff --git a/impl/test/12.eqns b/impl/test/12.eqns
new file mode 100644
index 0000000..91be47b
--- /dev/null
+++ b/impl/test/12.eqns
@@ -0,0 +1,2 @@
+x = y + 1
+y = max(0, x + 1)
diff --git a/impl/test/12.soln b/impl/test/12.soln
new file mode 100644
index 0000000..cdfcb1f
--- /dev/null
+++ b/impl/test/12.soln
@@ -0,0 +1,2 @@
+x = inf
+y = inf
diff --git a/impl/test/13.eqns b/impl/test/13.eqns
new file mode 100644
index 0000000..ce399ef
--- /dev/null
+++ b/impl/test/13.eqns
@@ -0,0 +1,3 @@
+x = y + 1
+y = max(0, z)
+z = x
diff --git a/impl/test/13.soln b/impl/test/13.soln
new file mode 100644
index 0000000..ff37347
--- /dev/null
+++ b/impl/test/13.soln
@@ -0,0 +1,3 @@
+x = inf
+y = inf
+z = inf
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
-- 
cgit v1.2.3