Fixed up the newer strategy iteration stuff

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

6 files changed, 85 insertions, 36 deletions

diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
index d09bef2..c7e5f4c 100644
--- a/impl/EquationSystem.hpp
+++ b/impl/EquationSystem.hpp
@@ -7,12 +7,16 @@
 #include "Operator.hpp"
 #include "Expression.hpp"
 #include "VariableAssignment.hpp"
+#include "IdMap.hpp"
 
 template<typename Domain>
 struct MaxStrategy;
 
 template<typename Domain>
 struct EquationSystem {
+  EquationSystem()
+    : _expr_to_var(NULL) { }
+
   virtual ~EquationSystem() {
     for (typename std::set<Expression<Domain>*>::iterator it = _expressions.begin();
          it != _expressions.end();
@@ -24,6 +28,8 @@ struct EquationSystem {
          ++it) {
       delete *it;
     }
+    if (_expr_to_var)
+      delete _expr_to_var;
   }
 
   MaxExpression<Domain>& maxExpression(const std::vector<Expression<Domain>*>& arguments) {
@@ -86,7 +92,7 @@ struct EquationSystem {
   StableVariableAssignment<Domain>* assignment(const Domain& value) const {
     return new StableVariableAssignment<Domain>(_variables.size(), value);
   }
-  VariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho) const {
+  StableVariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho) const {
     StableVariableAssignment<Domain>* result = this->assignment(-infinity<Domain>());
     for (unsigned int i = 0, length = _variables.size();
          i < length;
@@ -97,7 +103,7 @@ struct EquationSystem {
     }
     return result;
   }
-  VariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
+  StableVariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho, const MaxStrategy<Domain>& strat) const {
     StableVariableAssignment<Domain>* result = this->assignment(-infinity<Domain>());
     for (unsigned int i = 0, length = _variables.size();
          i < length;
@@ -109,12 +115,28 @@ struct EquationSystem {
     return result;
   }
 
-  Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const {
+  void indexMaxExpressions() {
+    _expr_to_var = new IdMap<MaxExpression<Domain>,Variable<Domain>*>(maxExpressionCount(), NULL); 
     for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) {
-      if (_right_sides[i] == &expr)
-        return _variables[i];
+      (*_expr_to_var)[*_right_sides[i]] = _variables[i];
+    }
+  }
+
+  Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const {
+    if (_expr_to_var) { // we've indexed:
+      auto* maxExpr = dynamic_cast<const MaxExpression<Domain>*>(&expr);
+      if (maxExpr) {
+        return (*_expr_to_var)[*maxExpr];
+      } else {
+        return NULL;
+      }
+    } else {
+      for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) {
+        if (_right_sides[i] == &expr)
+          return _variables[i];
+      }
+      return NULL;
     }
-    return NULL;
   }
 
   virtual bool equalAssignments(const VariableAssignment<Domain>& l, const VariableAssignment<Domain>& r) const {
@@ -141,6 +163,7 @@ struct EquationSystem {
   std::set<Expression<Domain>*> _expressions;
   std::vector<Variable<Domain>*> _variables;
   std::map<std::string, Variable<Domain>*> _variable_names;
+  IdMap<MaxExpression<Domain>, Variable<Domain>*>* _expr_to_var;
   std::vector<MaxExpression<Domain>*> _max_expressions;
   std::vector<MaxExpression<Domain>*> _right_sides;
 };
diff --git a/impl/IdSet.hpp b/impl/IdSet.hpp
index 99f89cc..950b1e1 100644
--- a/impl/IdSet.hpp
+++ b/impl/IdSet.hpp
@@ -39,6 +39,16 @@ class IdSet {
     }
   }
 
+  IdSet inverse() const {
+    IdSet other(_range);
+    for (unsigned int i = 0; i < _range; ++i) {
+      if (_set.find(i) == _set.end()) {
+        other._set.insert(i);
+      }
+    }
+    return other;
+  }
+
   bool contains(const T& obj) const {
     return _set.find(obj.id()) != _set.end();
   }
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(),
diff --git a/impl/Log.hpp b/impl/Log.hpp
index a920906..1e340c7 100644
--- a/impl/Log.hpp
+++ b/impl/Log.hpp
@@ -40,8 +40,10 @@ namespace log {
     return logger;
   }
 
+  Logger info(std::cout, "info");
   Logger trace(std::cerr, "trace");
   Logger strategy(std::cerr, "strategy");
+  Logger fixpoint(std::cerr, "fixpoint");
   Logger debug(std::cerr, "debug");
 
 }
diff --git a/impl/Makefile b/impl/Makefile
index 588c3ab..3192191 100644
--- a/impl/Makefile
+++ b/impl/Makefile
@@ -1,7 +1,7 @@
 CC=gcc
 CPP=g++
 BUILD=build/
-FLAGS=-Wall -Werror -Wextra -pedantic -g -lantlr3c -pg -std=c++11
+FLAGS=-Wall -Werror -Wextra -pedantic -lantlr3c -std=c++11 -g -pg
 
 all: main
 
diff --git a/impl/main.cpp b/impl/main.cpp
index 0317390..31f2937 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -155,6 +155,7 @@ int main (int argc, char* argv[]) {
   }
 
   log::debug << system;
+  system.indexMaxExpressions(); // make reverse-lookup O(1) instead of O(n)
   StableVariableAssignment<ZBar> result(system.variableCount(), infinity<ZBar>());
   ConcreteMaxStrategy<ZBar> strategy(system);
   IdSet<Variable<ZBar>> s1(system.variableCount());