Intermediate (broken) commit - smarter strategy

1 files changed, 63 insertions, 84 deletions

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;