From 2c22cee1f8fa87c527449a8bdc668ea311fdaf64 Mon Sep 17 00:00:00 2001
From: Carlo Zancanaro <carlo@carlo-laptop>
Date: Fri, 27 Apr 2012 13:33:58 +1000
Subject: Bit more work. maxFixpoint should be working now.

---
 impl/EquationSystem.hpp     | 79 +++++++++++++++++++++++++++++++++++++++++++++
 impl/MaxStrategy.hpp        |  5 +++
 impl/Operator.hpp           | 15 +++++++--
 impl/Solver.hpp             | 17 ++++++++++
 impl/Variable.hpp           |  9 +++---
 impl/VariableAssignment.hpp | 44 +++++++++++++++++++++++--
 impl/main.cpp               | 33 +++++++++++--------
 7 files changed, 181 insertions(+), 21 deletions(-)
 create mode 100644 impl/EquationSystem.hpp
 create mode 100644 impl/Solver.hpp

diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
new file mode 100644
index 0000000..065a1a2
--- /dev/null
+++ b/impl/EquationSystem.hpp
@@ -0,0 +1,79 @@
+#ifndef EQUATION_SYSTEM_HPP
+#define EQUATION_SYSTEM_HPP
+
+#include "Expression.hpp"
+
+template<typename T>
+struct EquationSystem {
+  EquationSystem ()
+    : _max_id(0) { }
+  virtual ~EquationSystem() {
+    for (int i = 0, size = _vars.size(); i < size; ++i) {
+      delete _vars[i];
+    }
+  }
+  Variable<T>* newVariable(const std::string&) {
+    _vars.push_back(new Variable<T>(_vars.size()));
+    return _vars[_vars.size()-1];
+  }
+  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++);
+    return expr;
+  }
+  unsigned int maxCount() const {
+    return _max_id;
+  }
+
+  Expression<T>*& operator[] (const Variable<T>& v) {
+    if (_expressions.size() <= v.id()) {
+      _expressions.resize(v.id()+1);
+    }
+    return _expressions[v.id()];
+  }
+  const Expression<T>*& operator[] (const Variable<T>& v) const {
+    if (_expressions.size() <= v.id()) {
+      throw "Out of range";
+    }
+    return _expressions[v.id()];
+  }
+
+  template<typename F>
+  VariableAssignment<T> foreach(F op, const VariableAssignment<T>& v) {
+    VariableAssignment<T> result(_vars.size());
+    for (unsigned int i = 0, size = _vars.size(); i < size; ++i) {
+      result[_vars[i]] = op(_expressions[i], v);
+    }
+  }
+
+  VariableAssignment<T> operator() (const VariableAssignment<T>& rho) {
+    VariableAssignment<T> result(_vars.size());
+    for (unsigned int i = 0, size = _vars.size(); i < size; ++i) {
+      result[*_vars[i]] = (*_expressions[i])(rho);
+    }
+    return result;
+  }
+
+  VariableAssignment<T> maxFixpoint() {
+    unsigned int size = _vars.size();
+    VariableAssignment<T> result(size, infinity<T>());
+    for (unsigned int i = 0; i < size; ++i) {
+      result = (*this)(result);
+    }
+    result = result.expand((*this)(result), -infinity<T>());
+    for (unsigned int i = 0; i < size-1; ++i) {
+      result = (*this)(result);
+    }
+    return result;
+  }
+  private:
+  unsigned int _max_id;
+  std::vector<Variable<T>*> _vars;
+  std::vector<Expression<T>*> _expressions;
+};
+
+
+#endif
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index a324359..7a37fb2 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -23,6 +23,9 @@ struct MaxStrategy {
     }
     return _assignment[x.id()];
   }
+  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) {
@@ -31,6 +34,8 @@ struct MaxStrategy {
       return (*expr.arguments()[_assignment[max->id()]])(rho);
     }
   }
+  MaxStrategy<T> improve() {
+  }
   private:
   unsigned int _length;
   unsigned int* _assignment;
diff --git a/impl/Operator.hpp b/impl/Operator.hpp
index d6b92f2..3e11443 100644
--- a/impl/Operator.hpp
+++ b/impl/Operator.hpp
@@ -34,9 +34,9 @@ struct Maximum : public Operator<T> {
   }
 };
 template<typename T>
-struct Minimumm : public Operator<T> {
+struct Minimum : public Operator<T> {
   virtual T operator() (const std::vector< Expression<T>* >& args, const VariableAssignment<T>& assignment) const {
-    T value = -infinity<T>();
+    T value = infinity<T>();
     for (typename std::vector< Expression<T>* >::const_iterator it = args.begin();
          it != args.end();
          ++it) {
@@ -47,6 +47,17 @@ struct Minimumm : public Operator<T> {
   }
 };
 
+template<typename T>
+struct Constant : public Operator<T> {
+  Constant(const T& val)
+    : _value(val) { }
+  T operator() (const std::vector< Expression<T>* >& args, const VariableAssignment<T>& ass) const {
+    return _value;
+  }
+  private:
+  const T _value;
+};
+
 #include "VariableAssignment.hpp"
 #include "Expression.hpp"
 
diff --git a/impl/Solver.hpp b/impl/Solver.hpp
new file mode 100644
index 0000000..11369bc
--- /dev/null
+++ b/impl/Solver.hpp
@@ -0,0 +1,17 @@
+#ifndef SOLVER_HPP
+#define SOLVER_HPP
+
+#include "Factory.hpp"
+#include "VariableAssignment.hpp"
+
+template<typename T>
+struct Solver {
+  VariableAssignment<T> solveBF(const EquationSystem<T>& system) {
+    VariableAssignment<T> result;
+    for (unsigned int i = 0; i < _var_count; ++i) {
+      result = system(result);
+    }
+  }
+};
+
+#endif
diff --git a/impl/Variable.hpp b/impl/Variable.hpp
index 0ba13e9..2386e7a 100644
--- a/impl/Variable.hpp
+++ b/impl/Variable.hpp
@@ -5,18 +5,19 @@
 
 template<typename T>
 struct Variable : public Operator<T> {
+  Variable(unsigned int id)
+    : _id(id) { }
+  Variable(const Variable& other)
+    : _id(other._id) { }
   unsigned int id() const {
     return _id;
   }
-  unsigned int id(unsigned int id) {
-    return (_id = id);
-  }
   T operator() (const std::vector< Expression<T>* >& args, const VariableAssignment<T>& ass) const {
     //assert(args.size() == 0)
     return ass[*this];
   }
   private:
-  unsigned int _id;
+  const unsigned int _id;
 };
 
 #endif
diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp
index e41f3d8..a2d0afd 100644
--- a/impl/VariableAssignment.hpp
+++ b/impl/VariableAssignment.hpp
@@ -6,11 +6,36 @@
 template<typename T>
 struct VariableAssignment {
   VariableAssignment(unsigned int length)
-    : _length(length), _assignment(new T[length]) { }
+    : _length(length), _assignment(new T[length]) {
+    for (unsigned int i = 0; i < _length; ++i) {
+      _assignment[i] = -infinity<T>();
+    }
+  }
+  VariableAssignment(unsigned int length, const T& initial)
+    : _length(length), _assignment(new T[length]) {
+    for (unsigned int i = 0; i < _length; ++i) {
+      _assignment[i] = initial;
+    }
+  }
+  VariableAssignment(const VariableAssignment& other)
+    : _length(other._length), _assignment(new T[other._length]) {
+    for (unsigned int i = 0; i < _length; ++i) {
+      _assignment[i] = other._assignment[i];
+    }
+  }
   ~VariableAssignment() {
     delete[] _assignment;
   }
-  const T& operator[] (const Variable<T> x) const {
+  VariableAssignment& operator=(const VariableAssignment& other) {
+    delete[] _assignment;
+    _length = other._length;
+    _assignment = new T[_length];
+    for (unsigned int i = 0; i < _length; ++i) {
+      _assignment[i] = other._assignment[i];
+    }
+    return *this;
+  }
+  const T& operator[] (const Variable<T>& x) const {
     if (x.id() < 0 || x.id() >= _length) {
       throw "Array out of bounds";
     }
@@ -22,6 +47,21 @@ struct VariableAssignment {
     }
     return _assignment[x.id()];
   }
+
+  VariableAssignment<T> expand(const VariableAssignment<T>& other) {
+    return expand(other, infinity<T>());
+  }
+  VariableAssignment<T> expand(const VariableAssignment<T>& other, const T& value) {
+    VariableAssignment<T> expansion(_length);
+    for (unsigned int i = 0; i < _length; ++i) {
+      if (_assignment[i] == other._assignment[i]) {
+        expansion._assignment[i] = _assignment[i];
+      } else {
+        expansion._assignment[i] = value;
+      }
+    }
+    return expansion;
+  }
   private:
   unsigned int _length;
   T* _assignment;
diff --git a/impl/main.cpp b/impl/main.cpp
index 589a1e7..6f84cdd 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -4,6 +4,7 @@
 
 #include "Operator.hpp"
 #include "Expression.hpp"
+#include "EquationSystem.hpp"
 #include "MaxStrategy.hpp"
 
 using namespace std;
@@ -19,22 +20,28 @@ struct Complete {
 
 std::vector< Expression<float>* > empty;
 int main () {
-  Variable<float> x;
-  x.id(0);
-  Variable<float> y;
-  y.id(1);
+  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);
+  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));
-  MaxExpression<float> maxExpr(args);
-  maxExpr.id(0);
+  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[maxExpr] = 0;
-  cout << strat(maxExpr,rho) << endl;
+  strat[*maxExpression] = 0;
+  cout << strat(*maxExpression,rho) << endl;
+
+  fac[*x] = minExpression;
+  fac[*y] = minExpression;
+  cout << fac.maxFixpoint()[*x] << endl;
   return 0;
 }
-- 
cgit v1.2.3