1 files changed, 117 insertions, 75 deletions

diff --git a/impl/ImprovementOperator.hpp b/impl/ImprovementOperator.hpp
index 3a9171f..5cee78c 100644
--- a/impl/ImprovementOperator.hpp
+++ b/impl/ImprovementOperator.hpp
@@ -8,6 +8,7 @@ template<typename Domain>
 struct ImprovementOperator {
   virtual ~ImprovementOperator() { }
   virtual bool improve(
+      EquationSystem<Domain>& system,
       ConcreteMaxStrategy<Domain>& strat,
       const VariableAssignment<Domain>& rho,
       IdSet<Variable<Domain> >& changedIn,
@@ -16,48 +17,29 @@ struct ImprovementOperator {
 };
 
 template<typename Domain>
-unsigned int bestStrategy(const MaxStrategy<Domain>& strat, const MaxExpression<Domain>& expr, const VariableAssignment<Domain>& rho) {
-  Domain bestValue = MaxStrategyExpression<Domain>(expr, strat).eval(rho);
-  unsigned int bestIndex = strat.get(expr);
-
-  const std::vector<Expression<Domain>*>& args = expr.arguments();
-  for (unsigned int j = 0, length = args.size();
-       j < length;
-       ++j) {
-    const Domain value = MaxStrategyExpression<Domain>(*args[j], strat).eval(rho);
-    std::cout << bestValue << " < " << value << ": ";
-    if (bestValue < value) {
-      std::cout << "change!" << std::endl;
-      bestValue = value;
-      bestIndex = j;
-    }
-    std::cout << std::endl;
-  }
-  return bestIndex;
-}
-
-template<typename Domain>
 struct NaiveImprovementOperator : public ImprovementOperator<Domain> {
   bool improve(
+      EquationSystem<Domain>& system,
       ConcreteMaxStrategy<Domain>& strat,
       const VariableAssignment<Domain>& rho,
-      IdSet<Variable<Domain> >& changedIn,
-      IdSet<Variable<Domain> >& changedOut
+      IdSet<Variable<Domain> >&,
+      IdSet<Variable<Domain> >&
   ) const {
     bool changed = false;
-    for (unsigned int i = 0, length = strat.maxExpressionCount();
+    for (unsigned int i = 0, length = system.maxExpressionCount();
          i < length;
          ++i) {
-      MaxExpression<Domain>& expr = strat.maxExpression(i);
+      MaxExpression<Domain>& expr = system.maxExpression(i);
       // this relies on the fact that an expression will only be proessed after the expressions
       // it depends on (which should always be true, as they form a DAG)
-      unsigned int index = bestStrategy(strat, expr, rho);
+      unsigned int index = expr.bestStrategy(rho, strat);
 
       if (index != strat.get(expr)) {
         changed = true;
         strat.set(expr, index);
       }
     }
+    //log::strategy << strat;
     return changed;
   }
 };
@@ -68,14 +50,15 @@ struct RepeatedImprovementOperator : public ImprovementOperator<Domain> {
     : _subImprovement(op) { }
 
   bool improve(
+      EquationSystem<Domain>& system,
       ConcreteMaxStrategy<Domain>& strat,
       const VariableAssignment<Domain>& rho,
       IdSet<Variable<Domain> >& changedIn,
       IdSet<Variable<Domain> >& changedOut
   ) const {
-    if (_subImprovement.improve(strat, rho, changedIn, changedOut)) {
-      VariableAssignment<Domain>* rho2 = strat.eval(rho);
-      improve(strat, *rho2, changedIn, changedOut);
+    if (_subImprovement.improve(system, strat, rho, changedIn, changedOut)) {
+      VariableAssignment<Domain>* rho2 = system.eval(rho, strat);
+      improve(system, strat, *rho2, changedIn, changedOut);
       delete rho2;
       return true;
     }
@@ -87,19 +70,21 @@ struct RepeatedImprovementOperator : public ImprovementOperator<Domain> {
 
 template<typename Domain>
 struct SmartImprovementOperator : public ImprovementOperator<Domain> {
-  SmartImprovementOperator(const ConcreteEquationSystem<Domain>& system)
+  SmartImprovementOperator(const EquationSystem<Domain>& system)
     : _system(system),
-      _influence(system.maxExpressionCount(), IdSet<MaxExpression<Domain> >(system.maxExpressionCount())) {
+      _influence(system.maxExpressionCount(), IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
+      _first_run(true) {
   }
 
   struct DynamicMaxStrategy : public MaxStrategy<Domain> {
     DynamicMaxStrategy(
+        const EquationSystem<Domain>& system,
         ConcreteMaxStrategy<Domain>& strat,
-        IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > >& influence,
+        IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain>>>& influence,
         const VariableAssignment<Domain>& rho,
-        IdSet<MaxExpression<Domain> >& stable,
-        IdSet<MaxExpression<Domain> >& changed
-    ) : MaxStrategy<Domain>(strat),
+        IdSet<MaxExpression<Domain>>& stable,
+        IdSet<MaxExpression<Domain>>& changed
+    ) : _system(system),
         _rho(rho),
         _values(strat),
         _stable(stable),
@@ -117,32 +102,48 @@ struct SmartImprovementOperator : public ImprovementOperator<Domain> {
       if (!_stable.contains(x)) {
         _stable.insert(x);
 
-        unsigned int val = bestStrategy(DependencyStrategy(*this, x), x, _rho);
-        //MaxStrategyExpression(x, DependencyStrategy(_values, x));
+        unsigned int val = x.bestStrategy(DependencyAssignment(*this, _rho, x),
+                                          DependencyStrategy(*this, x));
 
         if (val != _values.get(x)) {
-          IdSet<MaxExpression<Domain> > oldInfluence = _influence[x];
+          auto oldInfluence = _influence[x];
           _influence[x].clear();
           _values.set(x, val);
           _changed.insert(x);
-          std::cout << x << std::endl;
 
           _stable.filter(oldInfluence);
 
-          for (typename IdSet<MaxExpression<Domain> >::iterator it = oldInfluence.begin();
+          for (auto it = oldInfluence.begin();
                it != oldInfluence.end();
                ++it) {
-            solve(_values.maxExpression(*it));
+            solve(_system.maxExpression(*it));
           }
           _influence[x] = oldInfluence;
         }
       }
     }
 
+    struct DependencyAssignment : public VariableAssignment<Domain>{
+      DependencyAssignment(const DynamicMaxStrategy& strat,
+                           const VariableAssignment<Domain>& rho,
+                           const MaxExpression<Domain>& expr)
+        : _strat(strat),
+          _rho(rho),
+          _expr(expr) {
+      }
+      const Domain& operator[](const Variable<Domain>& var) const {
+        _strat._influence[*_strat._system[var]].insert(_expr);
+        return _rho[var];
+      }
+      private:
+      const DynamicMaxStrategy& _strat;
+      const VariableAssignment<Domain>& _rho;
+      const MaxExpression<Domain>& _expr;
+    };
+
     struct DependencyStrategy : public MaxStrategy<Domain> {
       DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
-        : MaxStrategy<Domain>(strat),
-          _strat(strat),
+        : _strat(strat),
           _expr(expr) {
       }
       unsigned int get(const MaxExpression<Domain>& e) const {
@@ -156,58 +157,99 @@ struct SmartImprovementOperator : public ImprovementOperator<Domain> {
     };
 
     private:
+    const EquationSystem<Domain>& _system;
     const VariableAssignment<Domain>& _rho;
     ConcreteMaxStrategy<Domain>& _values;
-    IdSet<MaxExpression<Domain> >& _stable;
-    IdSet<MaxExpression<Domain> >& _changed;
-    IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > >& _influence;
+    IdSet<MaxExpression<Domain>>& _stable;
+    IdSet<MaxExpression<Domain>>& _changed;
+    IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain>>>& _influence;
   };
 
-  void invalidate(IdSet<MaxExpression<Domain> >& set, MaxExpression<Domain>& expr) const {
-    for (typename IdSet<MaxExpression<Domain> >::iterator it = _influence[expr].begin(),
-                                                          end = _influence[expr].end();
-         it != end;
-         ++it) {
-      set.insert(_system.maxExpression(*it));
-      invalidate(set, expr);
+  void invalidateSubexpressions(IdSet<MaxExpression<Domain>>& set, Expression<Domain>& expr) const {
+    MaxExpression<Domain>* maxExpr = static_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);
+      }
+    }
+  }
+
+  void 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));
+      }
+    }
+  }
+
+  void markChanged(IdSet<Variable<Domain>>& set, MaxExpression<Domain>& expr, IdSet<MaxExpression<Domain>>& seen) const {
+    if (seen.contains(expr)) return;
+    seen.insert(expr);
+    auto var = _system.varFromExpr(expr);
+    if (var == NULL || !set.contains(*var)) {
+      if (var != NULL) {
+        set.insert(*var);
+      }
+      for (auto it = _influence[expr].begin(),
+                end = _influence[expr].end();
+           it != end;
+           ++it) {
+        markChanged(set, _system.maxExpression(*it), seen);
+      }
     }
   }
 
   bool improve(
+      EquationSystem<Domain>&,
       ConcreteMaxStrategy<Domain>& stratOut,
       const VariableAssignment<Domain>& rho,
       IdSet<Variable<Domain> >& changedIn,
       IdSet<Variable<Domain> >& changedOut
   ) const {
-    IdSet<MaxExpression<Domain> > invalidSet(_system.maxExpressionCount());
-    IdSet<MaxExpression<Domain> > changedSet(_system.maxExpressionCount());
-    for (typename IdSet<Variable<Domain> >::iterator it = changedIn.begin(),
-                                                     end = changedIn.end();
-         it != end;
-         ++it) {
-      invalidate(invalidSet, *_system[_system.variable(*it)]);
+    IdSet<MaxExpression<Domain>> invalidSet(_system.maxExpressionCount());
+    IdSet<MaxExpression<Domain>> changedSet(_system.maxExpressionCount());
+    if (_first_run) {
+      _first_run = false;
+    } else {
+      for (auto it = changedIn.begin(),
+                end = changedIn.end();
+           it != end;
+           ++it) {
+        invalidateSubexpressions(invalidSet, *_system[_system.variable(*it)]);
+      }
+      invalidSet.invert();
     }
-    invalidSet.invert();
 
-    std::cout << std::endl;
-    DynamicMaxStrategy strat(stratOut, _influence, rho, invalidSet, changedSet);
-    std::cout << std::endl;
-    for (typename IdSet<MaxExpression<Domain> >::iterator it = changedSet.begin(),
-                                                          end = changedSet.end();
+    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));
+    }
+    IdSet<MaxExpression<Domain>> seen;
+    for (auto it = changedSet.begin(),
+              end = changedSet.end();
          it != end;
          ++it) {
-      Variable<Domain>* var = strat.varFromExpr(_system.maxExpression(*it));
-      if (var) {
-        changedOut.insert(*var);
-      }
+      markChanged(changedOut, _system.maxExpression(*it), seen);
     }
-    std::cout << changedSet << std::endl;
-    std::cout << changedOut << std::endl;
-    return changedOut.size() != 0;
+    return changedOut.begin() != changedOut.end(); // true iff changedOut is non-empty
   }
   private:
-  const ConcreteEquationSystem<Domain>& _system;
-  mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
+  const EquationSystem<Domain>& _system;
+  mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain>>> _influence;
+  mutable bool _first_run;
 };
 
 #endif