From 5f3cb0bf02ed32976370cf6c7f656d000b4d7694 Mon Sep 17 00:00:00 2001
From: Carlo Zancanaro <carlo@pc-4w14-0.cs.usyd.edu.au>
Date: Fri, 15 Jun 2012 11:26:32 +1000
Subject: Re-write heaps of code to work better.

---
 impl/MaxStrategy.hpp | 175 ++++++++++++++++++++++++++++++---------------------
 1 file changed, 102 insertions(+), 73 deletions(-)

(limited to 'impl/MaxStrategy.hpp')

diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index aa49c9d..5d139fe 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -1,100 +1,129 @@
-#ifndef MAX_STRATEGY_HPP
-#define MAX_STRATEGY_HPP
+#ifndef MAX_EXPRESSION_HPP
+#define MAX_EXPRESSION_HPP
 
-#include <iostream>
 #include "Expression.hpp"
 #include "EquationSystem.hpp"
-#include "VariableAssignment.hpp"
-
-template<typename T>
-struct MaxStrategy {
-  MaxStrategy()
-    : _length(0), _assignment(NULL) { }
-  MaxStrategy(unsigned int length)
-    : _length(length), _assignment(new unsigned int[length]) {
-    for (unsigned int i = 0; i < length; ++i) {
-      _assignment[i] = 0;
+
+template<typename Domain>
+struct MaxStrategyExpression : public Expression<Domain> {
+  MaxStrategyExpression(const Expression<Domain>& expr, const IdMap<MaxExpression<Domain>,unsigned int>& strategy)
+    : _expr(expr), _strategy(strategy) { }
+
+  virtual Domain eval(const VariableAssignment<Domain>& rho) const {
+    // relies on implementation details - BAD BAD BAD, maybe
+    const OperatorExpression<Domain>* opExpr = dynamic_cast<const OperatorExpression<Domain>*>(&_expr);
+    if (opExpr) {
+      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];
+        return MaxStrategyExpression(*args[i], _strategy).eval(rho);
+      } else {
+        std::vector<Domain> argumentValues;
+        for (typename std::vector<Expression<Domain>*>::const_iterator it = args.begin();
+             it != args.end();
+             ++it) {
+          argumentValues.push_back(MaxStrategyExpression(**it, _strategy).eval(rho));
+        }
+        return opExpr->op().eval(argumentValues);
+      }
+    } else {
+      return _expr.eval(rho);
     }
   }
-  MaxStrategy(const MaxStrategy& other)
-    : _length(other._length), _assignment(new unsigned int[other._length]) {
-    for (unsigned int i = 0; i < other._length; ++i) {
-      _assignment[i] = other._assignment[i];
-    }
+
+  void print(std::ostream& cout) const {
+    cout << _expr;
   }
+  private:
+  const Expression<Domain>& _expr;
+  const IdMap<MaxExpression<Domain>,unsigned int>& _strategy;
+};
 
-  virtual ~MaxStrategy() {
-    delete[] _assignment;
+template<typename Domain>
+struct MaxStrategy : public EquationSystem<Domain> {
+  MaxStrategy(const ConcreteEquationSystem<Domain>& system)
+    : _system(system), _expressions(system.variableCount(), NULL), _strategy(system.maxExpressionCount(), 0) {
   }
 
-  MaxStrategy<T>& operator=(const MaxStrategy& other) {
-    if (_length != other._length) {
-      _length = other._length;
-      delete[] _assignment;
-      _assignment = new unsigned int[_length];
-    }
-    for (unsigned int i = 0; i < _length; ++i) {
-      _assignment[i] = other._assignment[i];
+  const Expression<Domain>* operator[](const Variable<Domain>& v) const {
+    if (_expressions[v] == NULL) {
+      Expression<Domain>* expression = new MaxStrategyExpression<Domain>(*_system[v], _strategy);
+      _expressions[v] = expression;
+      return expression;
+    } else {
+      return _expressions[v];
     }
-    return *this;
   }
 
-  const unsigned int& operator[] (const MaxExpression<T> x) const {
-    if (x.id() >= _length) {
-      throw "Array out of bounds";
-    }
-    return _assignment[x.id()];
+  unsigned int get(const MaxExpression<Domain>& e) const {
+    return _strategy[e];
+  }
+  unsigned int set(const MaxExpression<Domain>& e, unsigned int i) {
+    _strategy[e] = i;
+    return i;
   }
-  unsigned int& operator[] (const MaxExpression<T>& x) {
-    if (x.id() >= _length) {
-      throw "Array out of bounds";
+
+  VariableAssignment<Domain>* eval(const VariableAssignment<Domain>& rho) const {
+    StableVariableAssignment<Domain>* result = this->assignment(-infinity<Domain>());
+    for (unsigned int i = 0, length = _system.variableCount();
+         i < length;
+         ++i) {
+      const Variable<Domain>& var = _system.variable(i);
+      const Expression<Domain>& expr = * (*this)[var];
+      (*result)[var] = expr.eval(rho);
     }
-    return _assignment[x.id()];
+    return result;
   }
-  VariableAssignment<T> operator() (const EquationSystem<T>& eqns, const VariableAssignment<T>& rho) const {
-    return eqns.foreach(*this, rho);
+
+  unsigned int variableCount() const {
+    return _system.variableCount();
   }
-  T operator() (const Expression<T>& expr, const VariableAssignment<T>& rho) const {
-    const MaxExpression<T>* max = dynamic_cast<const MaxExpression<T>*>(&expr);
-    if (max == NULL) {
-      return expr(rho);
-    } else {
-      return (*this)(*max->argument(_assignment[max->id()]), rho);
-    }
+
+  Variable<Domain>& variable(unsigned int i) const {
+    return _system.variable(i);
   }
-  MaxStrategy<T> improve(const EquationSystem<T>& s, const VariableAssignment<T>& rho) const {
-    MaxStrategy<T> newStrategy(*this);
-    for (unsigned int i = 0; i < _length; ++i) {
-      const MaxExpression<T>& expr = *s.getMax(i);
-      const T oldValue = (*this)(expr, rho);
-
-      // this relies on the fact that deeper MaxExpressions have a lower id
-      // than the MaxExpressions containing them. This means that we know that
-      // we have enough of a strategy to work with what we have within us
-      std::pair<const T,unsigned int> best = expr.bestStrategy(rho, newStrategy);
-
-      if (best.first > oldValue)
-        newStrategy[expr] = best.second;
-    }
-    return newStrategy;
+
+  StableVariableAssignment<Domain>* assignment(const Domain& v) const {
+    return _system.assignment(v);
+  }
+
+  bool equalAssignments(const VariableAssignment<Domain>& l, const VariableAssignment<Domain>& r) const {
+    return _system.equalAssignments(l, r);
   }
 
-  bool operator== (const MaxStrategy& other) const {
-    if (_length != other._length)
-      return false;
-    for (unsigned int i = 0; i < _length; ++i) {
-      if (_assignment[i] != other._assignment[i]) {
-        return false;
+  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)
+      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;
+        }
       }
+      this->set(expr, bestIndex);
     }
-    return true;
   }
-  bool operator!= (const MaxStrategy& other) const {
-    return !(*this == other);
+
+  void print(std::ostream& cout) const {
+    cout << _system << std::endl;
   }
+
   private:
-  unsigned int _length;
-  unsigned int* _assignment;
+  const ConcreteEquationSystem<Domain>& _system;
+  mutable IdMap<Variable<Domain>,Expression<Domain>*> _expressions;
+  IdMap<MaxExpression<Domain>,unsigned int> _strategy;
 };
 
 #endif
-- 
cgit v1.2.3