From a61d8b829afab13593e254fc69e260b6346939dc Mon Sep 17 00:00:00 2001
From: Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au>
Date: Fri, 15 Jun 2012 15:48:16 +1000
Subject: Parameterise fixpoint and strategy improvement (command-line
 arguments specify which to use)

Also:
 - Fix up Complete<T> to work comparing `inf` to 1 (stupid bug)
 - Clean up the systems/ folder a bit
 - Change the printed output to differentiate variables and constants
   (!v/!c, respectively)
 - Perform a slight optimisation to the strategy-iteration process
---
 impl/MaxStrategy.hpp | 83 +++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 63 insertions(+), 20 deletions(-)

(limited to 'impl/MaxStrategy.hpp')

diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index 06f61b7..2be9f4c 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -46,6 +46,16 @@ struct MaxStrategy : public EquationSystem<Domain> {
     : _system(system), _expressions(system.variableCount(), NULL), _strategy(system.maxExpressionCount(), 0) {
   }
 
+  ~MaxStrategy() {
+    for (int i = 0, length = _system.variableCount();
+         i < length;
+         ++i) {
+      Expression<Domain>* expr = _expressions[_system.variable(i)];
+      if (expr)
+        delete expr;
+    }
+  }
+
   const Expression<Domain>* operator[](const Variable<Domain>& v) const {
     if (_expressions[v] == NULL) {
       Expression<Domain>* expression = new MaxStrategyExpression<Domain>(*_system[v], _strategy);
@@ -92,29 +102,62 @@ struct MaxStrategy : public EquationSystem<Domain> {
     return _system.equalAssignments(l, r);
   }
 
-  void improve(const VariableAssignment<Domain>& rho) {
-    for (unsigned int i = 0, length = _system.maxExpressionCount();
-         i < length;
-         ++i) {
-      MaxExpression<Domain>& expr = _system.maxExpression(i);
-      Domain bestValue = MaxStrategyExpression<Domain>(expr, _strategy).eval(rho);
-      unsigned int bestIndex = this->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], _strategy).eval(rho);
-        if (bestValue < value) {
-          bestValue = value;
-          bestIndex = j;
+
+  struct ImprovementOperator {
+    virtual ~ImprovementOperator() { }
+    virtual bool improve(MaxStrategy<Domain>&, const VariableAssignment<Domain>&) const = 0;
+  };
+  bool improve(const ImprovementOperator& op, const VariableAssignment<Domain>& rho) {
+    return op.improve(*this, rho);
+  }
+
+  struct NaiveImprovementOperator : public ImprovementOperator {
+    bool improve(MaxStrategy<Domain>& strat, const VariableAssignment<Domain>& rho) 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);
         }
       }
-      this->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 {
+      if (_subImprovement.improve(strat, rho)) {
+        VariableAssignment<Domain>* rho2 = strat.eval(rho);
+        improve(strat, *rho2);
+        delete rho2;
+        return true;
+      }
+      return false;
+    }
+    private:
+    const ImprovementOperator& _subImprovement;
+  };
 
   void print(std::ostream& cout) const {
     cout << _system << std::endl;
-- 
cgit v1.2.3