From 42e729d20000eb141b2907ad83630af34f4afea3 Mon Sep 17 00:00:00 2001
From: Carlo Zancanaro <carlo@carlo-laptop>
Date: Mon, 6 Aug 2012 22:58:29 +1000
Subject: New variation on the equation system solver.

Much simpler to understand. Basically have a variable assignment which
is dynamic and updates with the strategy changes. Similarly have
strategy changes easily invalidate the variable assignment.

This makes them strongly inter-dependent, but simplifies the
implementation considerably. Proving it should be easier like this, too.
---
 impl/VariableAssignment.hpp | 83 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 83 insertions(+)

(limited to 'impl/VariableAssignment.hpp')

diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp
index e0f7dc8..f41dab3 100644
--- a/impl/VariableAssignment.hpp
+++ b/impl/VariableAssignment.hpp
@@ -26,4 +26,87 @@ struct StableVariableAssignment
   }
 };
 
+#include "EquationSystem.hpp"
+
+template<typename Domain>
+struct DynamicMaxStrategy;
+
+template<typename Domain>
+struct DynamicVariableAssignment : public VariableAssignment<Domain> {
+  DynamicVariableAssignment(
+    const EquationSystem<Domain>& system,
+    const DynamicMaxStrategy<Domain>& strat
+  ) : _system(system),
+      _strategy(strat),
+      _values(system.variableCount(), infinity<Domain>()),
+      _stable(system.variableCount()),
+      _influence(system.variableCount(),
+                 IdSet<Variable<Domain>>(system.variableCount()))
+  { }
+
+  const Domain& operator[](const Variable<Domain>& var) const {
+    solve(var);
+    return _values[var];
+  }
+
+  void invalidate(const Variable<Domain>& x) const {
+    log::fixpoint << "invalidating " << x << std::endl;
+    _stable.remove(x);
+    _values[x] = infinity<Domain>();
+  }
+
+private:
+
+  void solve(const Variable<Domain>& x) const {
+      if (!_stable.contains(x)) {
+        _stable.insert(x);
+        
+        Domain val = _system[x]->eval(DependencyAssignment(*this, x),
+                                      _strategy);
+
+        if (val != _values[x]) {
+          log::fixpoint << "Updating value for " << x
+                        << " to " << val << std::endl;
+
+          auto oldInfluence = _influence[x];
+          _influence[x].clear();
+          _values[x] = val;
+
+          _strategy.invalidate(x);
+          
+          _stable.filter(oldInfluence);
+          
+          for (auto it = oldInfluence.begin();
+               it != oldInfluence.end();
+               ++it) {
+            solve(_system.variable(*it));
+          }
+        } else {
+          log::fixpoint << x << " did not change" << std::endl;
+        }
+      } else {
+        log::fixpoint << x << " is stable" << std::endl;
+      }
+    }
+
+    struct DependencyAssignment : public VariableAssignment<Domain> {
+      DependencyAssignment(const DynamicVariableAssignment& assignment, const Variable<Domain>& var)
+        : _assignment(assignment), _var(var) { }
+      const Domain& operator[](const Variable<Domain>& x) const {
+        const Domain& result = _assignment[x];
+        _assignment._influence[x].insert(_var);
+        return result;
+      }
+    private:
+      const DynamicVariableAssignment& _assignment;
+      const Variable<Domain>& _var;
+    };
+  
+  const EquationSystem<Domain>& _system;
+  const DynamicMaxStrategy<Domain>& _strategy;
+  mutable StableVariableAssignment<Domain> _values;
+  mutable IdSet<Variable<Domain> > _stable;
+  mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
+};
+
 #endif
-- 
cgit v1.2.3