Intermediate (broken) commit - smarter strategy

4 files changed, 91 insertions, 96 deletions

diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
index 50a0e45..5549674 100644
--- a/impl/EquationSystem.hpp
+++ b/impl/EquationSystem.hpp
@@ -13,11 +13,13 @@ struct EquationSystem {
   virtual ~EquationSystem() { }
   virtual const Expression<Domain>* operator[](const Variable<Domain>&) const = 0;
   virtual VariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho) const = 0;
+
   virtual unsigned int variableCount() const = 0;
   virtual Variable<Domain>& variable(unsigned int) const = 0;
+
   virtual StableVariableAssignment<Domain>* assignment(const Domain& value) const = 0;
+  virtual Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const = 0;
   virtual bool equalAssignments(const VariableAssignment<Domain>&, const VariableAssignment<Domain>&) const = 0;
-
   virtual void print(std::ostream& cout) const = 0;
 };
 
@@ -86,10 +88,10 @@ struct ConcreteEquationSystem : public EquationSystem<Domain> {
     return *constant;
   }
 
-  Expression<Domain>* operator[](const Variable<Domain>& var) const {
+  MaxExpression<Domain>* operator[](const Variable<Domain>& var) const {
     return _right_sides[var.id()];
   }
-  Expression<Domain>*& operator[](const Variable<Domain>& var) {
+  MaxExpression<Domain>*& operator[](const Variable<Domain>& var) {
     return _right_sides[var.id()];
   }
 
@@ -108,6 +110,14 @@ struct ConcreteEquationSystem : public EquationSystem<Domain> {
     return result;
   }
 
+  Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const {
+    for (unsigned int i = 0, length = _right_sides.size(); i < length; ++i) {
+      if (_right_sides[i] == &expr)
+        return _variables[i];
+    }
+    return NULL;
+  }
+
   virtual bool equalAssignments(const VariableAssignment<Domain>& l, const VariableAssignment<Domain>& r) const {
     for (unsigned int i = 0, length = _variables.size();
          i < length;
@@ -133,7 +143,7 @@ struct ConcreteEquationSystem : public EquationSystem<Domain> {
   std::vector<Variable<Domain>*> _variables;
   std::map<std::string, Variable<Domain>*> _variable_names;
   std::vector<MaxExpression<Domain>*> _max_expressions;
-  std::vector<Expression<Domain>*> _right_sides;
+  std::vector<MaxExpression<Domain>*> _right_sides;
 };
 
 template<typename T>
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index 9fa7768..977036f 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -6,8 +6,44 @@
 #include "IdSet.hpp"
 
 template<typename Domain>
+struct MaxStrategy : public EquationSystem<Domain> {
+  MaxStrategy(const EquationSystem<Domain>& sub)
+    : _sub(sub) { }
+
+  virtual ~MaxStrategy() { }
+  virtual const Expression<Domain>* operator[](const Variable<Domain>& var) const {
+    return _sub[var];
+  }
+  virtual VariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho) const {
+    return _sub.eval(rho);
+  }
+  virtual unsigned int variableCount() const {
+    return _sub.variableCount();
+  }
+  virtual Variable<Domain>& variable(unsigned int i) const {
+    return _sub.variable(i);
+  }
+  virtual StableVariableAssignment<Domain>* assignment(const Domain& value) const {
+    return _sub.assignment(value);
+  }
+  virtual bool equalAssignments(const VariableAssignment<Domain>& r1, const VariableAssignment<Domain>& r2) const {
+    return _sub.equalAssignments(r1, r2);
+  }
+  virtual Variable<Domain>* varFromExpr(const Expression<Domain>& expr) const {
+    return _sub.varFromExpr(expr);
+  }
+  virtual void print(std::ostream& cout) const {
+    return _sub.print(cout);
+  }
+
+  virtual unsigned int get(const MaxExpression<Domain>& e) const = 0;
+  private:
+  const EquationSystem<Domain>& _sub;
+};
+
+template<typename Domain>
 struct MaxStrategyExpression : public Expression<Domain> {
-  MaxStrategyExpression(const Expression<Domain>& expr, const IdMap<MaxExpression<Domain>,unsigned int>& strategy)
+  MaxStrategyExpression(const Expression<Domain>& expr, const MaxStrategy<Domain>& strategy)
     : _expr(expr), _strategy(strategy) { }
 
   virtual Domain eval(const VariableAssignment<Domain>& rho) const {
@@ -17,7 +53,7 @@ struct MaxStrategyExpression : public Expression<Domain> {
       const MaxExpression<Domain>* maxExpr = dynamic_cast<const MaxExpression<Domain>*>(opExpr);
       const std::vector<Expression<Domain>*> args = opExpr->arguments();
       if (maxExpr) {
-        unsigned int i = _strategy[*maxExpr];
+        unsigned int i = _strategy.get(*maxExpr);
         return MaxStrategyExpression(*args[i], _strategy).eval(rho);
       } else {
         std::vector<Domain> argumentValues;
@@ -38,16 +74,19 @@ struct MaxStrategyExpression : public Expression<Domain> {
   }
   private:
   const Expression<Domain>& _expr;
-  const IdMap<MaxExpression<Domain>,unsigned int>& _strategy;
+  const MaxStrategy<Domain>& _strategy;
 };
 
 template<typename Domain>
-struct MaxStrategy : public EquationSystem<Domain> {
-  MaxStrategy(const ConcreteEquationSystem<Domain>& system)
-    : _system(system), _expressions(system.variableCount(), NULL), _strategy(system.maxExpressionCount(), 0) {
+struct ConcreteMaxStrategy : public MaxStrategy<Domain> {
+  ConcreteMaxStrategy(const ConcreteEquationSystem<Domain>& system)
+    : MaxStrategy<Domain>(system),
+      _system(system),
+      _expressions(system.variableCount(), NULL),
+      _strategy(system.maxExpressionCount(), 0) {
   }
 
-  ~MaxStrategy() {
+  ~ConcreteMaxStrategy() {
     for (int i = 0, length = _system.variableCount();
          i < length;
          ++i) {
@@ -59,7 +98,7 @@ struct MaxStrategy : public EquationSystem<Domain> {
 
   const Expression<Domain>* operator[](const Variable<Domain>& v) const {
     if (_expressions[v] == NULL) {
-      Expression<Domain>* expression = new MaxStrategyExpression<Domain>(*_system[v], _strategy);
+      Expression<Domain>* expression = new MaxStrategyExpression<Domain>(*_system[v], *this);
       _expressions[v] = expression;
       return expression;
     } else {
@@ -94,6 +133,14 @@ struct MaxStrategy : public EquationSystem<Domain> {
   Variable<Domain>& variable(unsigned int i) const {
     return _system.variable(i);
   }
+  
+  unsigned int maxExpressionCount() const {
+    return _system.maxExpressionCount();
+  }
+
+  MaxExpression<Domain>& maxExpression(unsigned int i) const {
+    return _system.maxExpression(i);
+  }
 
   StableVariableAssignment<Domain>* assignment(const Domain& v) const {
     return _system.assignment(v);
@@ -103,86 +150,18 @@ struct MaxStrategy : public EquationSystem<Domain> {
     return _system.equalAssignments(l, r);
   }
 
-
-  struct ImprovementOperator {
-    virtual ~ImprovementOperator() { }
-    virtual bool improve(
-        MaxStrategy<Domain>& strat,
-        const VariableAssignment<Domain>& rho,
-        const IdSet<Variable<Domain> >& changedIn,
-        IdSet<Variable<Domain> >& changedOut
-    ) const  = 0;
-  };
-  bool improve(const ImprovementOperator& op, const VariableAssignment<Domain>& rho, const IdSet<Variable<Domain> >& changedIn, IdSet<Variable<Domain> >& changedOut) {
-    return op.improve(*this, rho, changedIn, changedOut);
-  }
-
-  struct NaiveImprovementOperator : public ImprovementOperator {
-    bool improve(
-        MaxStrategy<Domain>& strat,
-        const VariableAssignment<Domain>& rho,
-        const IdSet<Variable<Domain> >& changedIn,
-        IdSet<Variable<Domain> >& changedOut
-    ) const {
-      bool changed = false;
-      for (unsigned int i = 0, length = strat._system.maxExpressionCount();
-           i < length;
-           ++i) {
-        MaxExpression<Domain>& expr = strat._system.maxExpression(i);
-        Domain bestValue = MaxStrategyExpression<Domain>(expr, strat._strategy).eval(rho);
-        unsigned int lastIndex= strat.get(expr);
-        unsigned int bestIndex = strat.get(expr);
-
-        // 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)
-        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._strategy).eval(rho);
-          if (bestValue < value) {
-            bestValue = value;
-            bestIndex = j;
-          }
-        }
-        if (bestIndex != lastIndex) {
-          changed = true;
-          strat.set(expr, bestIndex);
-        }
-      }
-      return changed;
-    }
-  };
-    
-  struct RepeatedImprovementOperator : public ImprovementOperator {
-    RepeatedImprovementOperator(const ImprovementOperator& op)
-      : _subImprovement(op) { }
-
-    bool improve(
-        MaxStrategy<Domain>& strat,
-        const VariableAssignment<Domain>& rho,
-        const 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);
-        delete rho2;
-        return true;
-      }
-      return false;
-    }
-    private:
-    const ImprovementOperator& _subImprovement;
-  };
-
-  struct DependencyImprovementOperator : public ImprovementOperator {
-  };
-
   void print(std::ostream& cout) const {
     cout << _system << std::endl;
   }
 
+  const ConcreteEquationSystem<Domain>& system() const {
+    return _system;
+  }
+
+  const IdMap<MaxExpression<Domain>,unsigned int>& strategy() const {
+    return _strategy;
+  }
+
   private:
   const ConcreteEquationSystem<Domain>& _system;
   mutable IdMap<Variable<Domain>,Expression<Domain>*> _expressions;
diff --git a/impl/main.cpp b/impl/main.cpp
index b761587..26aedbe 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -6,6 +6,7 @@
 #include "Operator.hpp"
 #include "EquationSystem.hpp"
 #include "MaxStrategy.hpp"
+#include "ImprovementOperator.hpp"
 #include "FixpointAlgorithm.hpp"
 
 extern "C" {
@@ -126,14 +127,17 @@ int main (int argc, char* argv[]) {
   }
 
   // PARSE ARGUMENTS - strat improvement
-  MaxStrategy<ZBar>::ImprovementOperator* naiveImprovement = new MaxStrategy<ZBar>::NaiveImprovementOperator();
-  MaxStrategy<ZBar>::ImprovementOperator* improvement = NULL;
+  ImprovementOperator<ZBar>* naiveImprovement = new NaiveImprovementOperator<ZBar>();
+  ImprovementOperator<ZBar>* improvement = NULL;
   if (!strcmp(argv[3], "repeat")) {
-    improvement = new MaxStrategy<ZBar>::RepeatedImprovementOperator(*naiveImprovement);
+    improvement = new RepeatedImprovementOperator<ZBar>(*naiveImprovement);
     cout << "Repeated strategy improvement" << endl;
   } else if (!strcmp(argv[3], "naive")) {
     improvement = naiveImprovement;
     cout << "Naive strategy improvement" << endl;
+  } else if (!strcmp(argv[3], "smart")) {
+    improvement = new SmartImprovementOperator<ZBar>(system);
+    cout << "Smart strategy improvement" << endl;
   } else {
     cout << "Unknown strategy improvement algorithm." << endl;
   }
@@ -143,7 +147,7 @@ int main (int argc, char* argv[]) {
 
   cout << system << endl;
   StableVariableAssignment<ZBar> result(system.variableCount(), infinity<ZBar>());
-  MaxStrategy<ZBar> strategy(system);
+  ConcreteMaxStrategy<ZBar> strategy(system);
   IdSet<Variable<ZBar> > s1(system.variableCount());
   IdSet<Variable<ZBar> > s2(system.variableCount());
   bool changed = false;
@@ -159,7 +163,9 @@ int main (int argc, char* argv[]) {
     cout << endl;
     exit(0);*/
 
-    changed = strategy.improve(*improvement, result, s1, s2);
+    s2.clear();
+    changed = improvement->improve(strategy, result, s1, s2);
+    std::cout << (changed ? "true" : "false") << std::endl;
   } while(changed);
 
   cout << endl;
diff --git a/impl/systems/example.eqns b/impl/systems/example.eqns
index 9ef3135..71ee74a 100644
--- a/impl/systems/example.eqns
+++ b/impl/systems/example.eqns
@@ -1,3 +1,3 @@
-x1 = max([0,0], min(x1-[1,1], x2))
-x2 = max([0,0], [5,5]+x1, x1)
-x3 = max([0,0], [1,1]+x3, [0,0]+x1)
+x1 = max(0, min(x1-1, x2))
+x2 = max(0, 5+x1, x1)
+x3 = max(0, 1+x3, 0+x1)