Functional algorithm. Unoptimised.

7 files changed, 184 insertions, 45 deletions

diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
index 065a1a2..adc608b 100644
--- a/impl/EquationSystem.hpp
+++ b/impl/EquationSystem.hpp
@@ -2,11 +2,11 @@
 #define EQUATION_SYSTEM_HPP
 
 #include "Expression.hpp"
+template<typename T>
+struct MaxStrategy;
 
 template<typename T>
 struct EquationSystem {
-  EquationSystem ()
-    : _max_id(0) { }
   virtual ~EquationSystem() {
     for (int i = 0, size = _vars.size(); i < size; ++i) {
       delete _vars[i];
@@ -19,13 +19,26 @@ struct EquationSystem {
   unsigned int varCount() const {
     return _vars.size();
   }
+
   MaxExpression<T>* newMaxExpression(const std::vector<Expression<T>*>& args) {
     MaxExpression<T>* expr = new MaxExpression<T>(args);
-    expr->id(_max_id++);
+    expr->id(_max_expressions.size());
+    _max_expressions.push_back(expr);
     return expr;
   }
   unsigned int maxCount() const {
-    return _max_id;
+    return _max_expressions.count();
+  }
+  const MaxExpression<T>* getMax(unsigned int i) const {
+    return _max_expressions[i];
+  }
+
+  MaxStrategy<T> strategy() const {
+    return MaxStrategy<T>(_max_expressions.size());
+  }
+  
+  VariableAssignment<T> assignment() const {
+    return VariableAssignment<T>(_vars.size());
   }
 
   Expression<T>*& operator[] (const Variable<T>& v) {
@@ -42,14 +55,15 @@ struct EquationSystem {
   }
 
   template<typename F>
-  VariableAssignment<T> foreach(F op, const VariableAssignment<T>& v) {
+  VariableAssignment<T> foreach(F op, const VariableAssignment<T>& rho) const {
     VariableAssignment<T> result(_vars.size());
     for (unsigned int i = 0, size = _vars.size(); i < size; ++i) {
-      result[_vars[i]] = op(_expressions[i], v);
+      result[*_vars[i]] = op(*_expressions[i], rho);
     }
+    return result;
   }
 
-  VariableAssignment<T> operator() (const VariableAssignment<T>& rho) {
+  VariableAssignment<T> operator() (const VariableAssignment<T>& rho) const {
     VariableAssignment<T> result(_vars.size());
     for (unsigned int i = 0, size = _vars.size(); i < size; ++i) {
       result[*_vars[i]] = (*_expressions[i])(rho);
@@ -57,7 +71,7 @@ struct EquationSystem {
     return result;
   }
 
-  VariableAssignment<T> maxFixpoint() {
+  VariableAssignment<T> maxFixpoint() const {
     unsigned int size = _vars.size();
     VariableAssignment<T> result(size, infinity<T>());
     for (unsigned int i = 0; i < size; ++i) {
@@ -69,11 +83,37 @@ struct EquationSystem {
     }
     return result;
   }
+
+  VariableAssignment<T> maxFixpoint(const MaxStrategy<T>& strat) const {
+    unsigned int size = _vars.size();
+    VariableAssignment<T> result(size, infinity<T>());
+    for (unsigned int i = 0; i < size; ++i) {
+      result = strat(*this, result);
+    }
+    result = result.expand(strat(*this, result), -infinity<T>());
+    for (unsigned int i = 0; i < size-1; ++i) {
+      result = strat(*this, result);
+    }
+    return result;
+  }
+
+  VariableAssignment<T> minFixpoint() const {
+    VariableAssignment<T> rho = assignment();
+    VariableAssignment<T> lastRho = assignment();
+    MaxStrategy<T> strat = strategy();
+    do {
+      lastRho = rho;
+      strat = strat.improve(*this, rho);
+      rho = maxFixpoint(strat);
+    } while(lastRho != rho);
+    return rho;
+  }
   private:
-  unsigned int _max_id;
   std::vector<Variable<T>*> _vars;
+  std::vector<MaxExpression<T>*> _max_expressions;
   std::vector<Expression<T>*> _expressions;
 };
 
+#include "MaxStrategy.hpp"
 
 #endif
diff --git a/impl/Expression.hpp b/impl/Expression.hpp
index 46ccf23..7b157c2 100644
--- a/impl/Expression.hpp
+++ b/impl/Expression.hpp
@@ -1,6 +1,7 @@
 #ifndef EXPRESSION_HPP
 #define EXPRESSION_HPP
 
+//#include <pair>
 #include "VariableAssignment.hpp"
 #include "Operator.hpp"
 
@@ -16,13 +17,10 @@ struct Expression {
       delete *it;
     }*/
   }
-  const std::vector<Expression<T>*>& arguments() const {
-    return _arguments;
-  }
   virtual T operator() (const VariableAssignment<T>& assignment) const {
     return (*_operator)(_arguments, assignment);
   }
-  private:
+  protected:
   Operator<T>* _operator;
   std::vector< Expression<T>* > _arguments;
 };
@@ -37,6 +35,22 @@ struct MaxExpression : public Expression<T> {
   unsigned int id(unsigned int id) {
     return (_id = id);
   }
+  Expression<T>* argument(unsigned int i) const {
+    if (i >= Expression<T>::_arguments.size()) {
+      throw "Error";
+    }
+    return Expression<T>::_arguments[i];
+  }
+  std::pair<T, unsigned int> bestStrategy(const VariableAssignment<T>& rho) const {
+    std::pair<T, unsigned int> best = std::pair<T, unsigned int>(-infinity<T>(), 0);
+    for (unsigned int i = 0, size = Expression<T>::_arguments.size(); i < size; ++i) {
+      T value = (*Expression<T>::_arguments[i])(rho);
+      if (value > best.first)
+        best = std::pair<T, unsigned int>(value, i);
+    }
+    std::cout << "Best strategy: (" << best.first << ", " << best.second << ")" << std::endl;
+    return best;
+  }
   private:
   unsigned int _id;
 };
diff --git a/impl/ExpressionFactory.hpp b/impl/ExpressionFactory.hpp
new file mode 100644
index 0000000..0eb7268
--- /dev/null
+++ b/impl/ExpressionFactory.hpp
@@ -0,0 +1,12 @@
+#ifndef EXPRESSION_FACTORY_HPP
+#define EXPRESSION_FACTORY_HPP
+
+template<typename T>
+struct ExpressionFactory {
+  ExpressionFactory() : _count(0) { }
+
+  private:
+  unsigned int _count;
+};
+
+#endif
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index 7a37fb2..e52fd99 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -2,39 +2,89 @@
 #define MAX_STRATEGY_HPP
 
 #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]) { }
+    : _length(length), _assignment(new unsigned int[length]) {
+    for (unsigned int i = 0; i < length; ++i) {
+      _assignment[i] = 0;
+    }
+  }
+  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];
+    }
+  }
+
+  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];
+    }
+    return *this;
+  }
+
   virtual ~MaxStrategy() {
     delete[] _assignment;
   }
   const unsigned int& operator[] (const MaxExpression<T> x) const {
-    if (x.id() < 0 || x.id() >= _length) {
+    if (x.id() >= _length) {
       throw "Array out of bounds";
     }
     return _assignment[x.id()];
   }
   unsigned int& operator[] (const MaxExpression<T>& x) {
-    if (x.id() < 0 || x.id() >= _length) {
+    if (x.id() >= _length) {
       throw "Array out of bounds";
     }
     return _assignment[x.id()];
   }
-  T operator() (const EquationSystem<T>& eqns, const VariableAssignment<T>& rho) const {
-    return eqns.foreach((*this), rho);
+  VariableAssignment<T> operator() (const EquationSystem<T>& eqns, const VariableAssignment<T>& rho) const {
+    return eqns.foreach(*this, rho);
   }
   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 (*expr.arguments()[_assignment[max->id()]])(rho);
+      return (*max->argument(_assignment[max->id()]))(rho);
+    }
+  }
+  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);
+      std::pair<const T,unsigned int> best = expr->bestStrategy(rho);
+      if (best.first > oldValue)
+        newStrategy[*expr] = best.second;
+    }
+    std::cout << "Strat improvement: " << newStrategy[*s.getMax(0)] << std::endl;
+    return newStrategy;
+  }
+
+  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;
+      }
     }
+    return true;
   }
-  MaxStrategy<T> improve() {
+  bool operator!= (const MaxStrategy& other) const {
+    return !(*this == other);
   }
   private:
   unsigned int _length;
diff --git a/impl/Operator.hpp b/impl/Operator.hpp
index 3e11443..71a1e68 100644
--- a/impl/Operator.hpp
+++ b/impl/Operator.hpp
@@ -58,6 +58,13 @@ struct Constant : public Operator<T> {
   const T _value;
 };
 
+template<typename T>
+struct Increment: public Operator<T> {
+  T operator() (const std::vector< Expression<T>* >& args, const VariableAssignment<T>& ass) const {
+    return (*args[0])(ass) + 1;
+  }
+};
+
 #include "VariableAssignment.hpp"
 #include "Expression.hpp"
 
diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp
index a2d0afd..c0c7148 100644
--- a/impl/VariableAssignment.hpp
+++ b/impl/VariableAssignment.hpp
@@ -36,13 +36,13 @@ struct VariableAssignment {
     return *this;
   }
   const T& operator[] (const Variable<T>& x) const {
-    if (x.id() < 0 || x.id() >= _length) {
+    if (x.id() >= _length) {
       throw "Array out of bounds";
     }
     return _assignment[x.id()];
   }
   T& operator[] (const Variable<T>& x) {
-    if (x.id() < 0 || x.id() >= _length) {
+    if (x.id() >= _length) {
       throw "Array out of bounds";
     }
     return _assignment[x.id()];
@@ -62,6 +62,20 @@ struct VariableAssignment {
     }
     return expansion;
   }
+
+  bool operator==(const VariableAssignment& other) const {
+    if (_length != other._length)
+      return false;
+    for (unsigned int i = 0; i < _length; ++i) {
+      if (_assignment[i] != other._assignment[i]) {
+        return false;
+      }
+    }
+    return true;
+  }
+  bool operator!=(const VariableAssignment& other) const {
+    return !(*this == other);
+  }
   private:
   unsigned int _length;
   T* _assignment;
diff --git a/impl/main.cpp b/impl/main.cpp
index 6f84cdd..579db25 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -18,30 +18,32 @@ struct Complete {
   T _value;
 };*/
 
+typedef std::vector<Expression<float>*> Args;
+typedef Expression<float> E;
+typedef Constant<float> C;
+typedef Minimum<float> Min;
+
 std::vector< Expression<float>* > empty;
 int main () {
-  EquationSystem<float> fac;
-  Variable<float>* x = fac.newVariable("x");
-  Variable<float>* y = fac.newVariable("y");
-  VariableAssignment<float> rho(2);
-  rho[*x] = 12;
-  rho[*y] = 10;
-  Expression<float> expr(x, empty);
-
-  std::vector<Expression<float>*> args;
-  args.push_back(new Expression<float>(x, empty));
-  args.push_back(new Expression<float>(y, empty));
-  args.push_back(new Expression<float>(new Constant<float>(10), empty));
-  MaxExpression<float>* maxExpression = fac.newMaxExpression(args);
-  Expression<float>* minExpression = new Expression<float>(new Minimum<float>(), args);
-
-
-  MaxStrategy<float> strat(1);
-  strat[*maxExpression] = 0;
-  cout << strat(*maxExpression,rho) << endl;
-
-  fac[*x] = minExpression;
-  fac[*y] = minExpression;
-  cout << fac.maxFixpoint()[*x] << endl;
+  EquationSystem<float> sys;
+  Variable<float>* x = sys.newVariable("x");
+
+  Args incArgs;
+  incArgs.push_back(new E(x, empty));
+
+  Args minArgs;
+  minArgs.push_back(new E(new Increment<float>, incArgs));
+  minArgs.push_back(new E(new C(100), empty));
+
+  Args maxArgs;
+  maxArgs.push_back(new E(new C(0), empty));
+  maxArgs.push_back(new E(new Min(), minArgs));
+
+  sys[*x] = sys.newMaxExpression(maxArgs);
+  // x = max(0, min(x+1, 100))
+
+  cout << sys.minFixpoint()[*x] << endl;
+  // -> 100, as expected
+
   return 0;
 }