Merge branch 'master' of https://bitbucket.org/czan/honours

Conflicts:
	.gitignore
	impl/MaxStrategy.hpp
	impl/VariableAssignment.hpp
	impl/systems/test.eqns
	impl/test/7.eqns

1 files changed, 65 insertions, 11 deletions

diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index 96d0492..ba7cc11 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -10,6 +10,9 @@ 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);
+  }
 };
 
 unsigned int stack_depth = 1;
@@ -39,9 +42,22 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
       _influence(system.maxExpressionCount(),
                  IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
       _var_influence(system.variableCount(),
-                     IdSet<MaxExpression<Domain> >(system.maxExpressionCount()))
+                     IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
+      _frozen(false)
   {}
 
+  void freeze() {
+    _frozen = true;
+  }
+
+  void thaw() {
+    _frozen = false;
+  }
+
+  bool is_frozen() {
+    return _frozen;
+  }
+
   void setRho(DynamicVariableAssignment<Domain>& rho) {
     _rho = &rho;
   }
@@ -71,7 +87,7 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
   }
 
 private:
-  void solve(const MaxExpression<Domain>& x) const {
+  void solve(const MaxExpression<Domain>& x) {
     if (!_stable.contains(x)) {
       _stable.insert(x);
       log::strategy << indent() << "Stabilise " << x << std::endl;
@@ -121,7 +137,7 @@ private:
   }
 
   struct DependencyAssignment : public VariableAssignment<Domain>{
-    DependencyAssignment(const DynamicMaxStrategy& strat,
+    DependencyAssignment(DynamicMaxStrategy& strat,
                          VariableAssignment<Domain>& rho,
                          const MaxExpression<Domain>& expr)
       : _strat(strat),
@@ -133,7 +149,7 @@ private:
       return _rho[var];
     }
   private:
-    const DynamicMaxStrategy& _strat;
+    DynamicMaxStrategy& _strat;
     VariableAssignment<Domain>& _rho;
     const MaxExpression<Domain>& _expr;
   };
@@ -163,7 +179,7 @@ private:
   };
 
   struct DependencyStrategy : public MaxStrategy<Domain> {
-    DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
+    DependencyStrategy(DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
       : _strat(strat),
         _expr(expr) {
     }
@@ -175,20 +191,58 @@ private:
       return _strat._values[e];
     }
   private:
-    const DynamicMaxStrategy& _strat;
+    DynamicMaxStrategy& _strat;
     const MaxExpression<Domain>& _expr;
   };
 
 private:
   mutable bool _frozen;
   const EquationSystem<Domain>& _system;
-  mutable DynamicVariableAssignment<Domain>* _rho;
-  mutable IdMap<MaxExpression<Domain>,unsigned int> _values;
-  mutable IdSet<MaxExpression<Domain> > _stable;
-  mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
-  mutable IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence;
+  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 _frozen;
 };
 
+
+template<typename T>
+IdMap<Variable<T>,T> solve_for(const EquationSystem<T>& system) {
+  IdMap<Variable<T>,T> result(system.variableCount(), infinity<T>());
+
+  DynamicMaxStrategy<T> strategy(system);
+  DynamicVariableAssignment<T> rho(system, strategy, -infinity<T>());
+  strategy.setRho(rho);
+
+  bool changed;
+  do {
+    changed = false;
+
+    // improve strategy
+    rho.freeze();
+    strategy.thaw();
+    for (unsigned int i = 0; i < system.variableCount(); ++i) {
+      strategy.get(*system[system.variable(i)]);
+    }
+
+    // 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);
+
+  return result;
+}
+
+
 /*template<typename Domain>
 std::ostream& operator<<(std::ostream& cout, const MaxStrategy<Domain>& strat) {
   strat.print(cout);