Fixed up the newer strategy iteration stuff

Trivial 100000 var case in 15s on my Uni machine.

1 files changed, 42 insertions, 29 deletions

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(),