Start on the max-strategy stuff. Also more BF.

6 files changed, 233 insertions, 87 deletions

diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
new file mode 100644
index 0000000..efd34b3
--- /dev/null
+++ b/impl/EquationSystem.hpp
@@ -0,0 +1,64 @@
+#ifndef EQUATION_SYSTEM_H
+#define EQUATION_SYSTEM_H
+
+#include <map>
+#include <string>
+#include "Expression.hpp"
+
+template<typename T>
+struct EquationSystem {
+  void add(std::string k, Expression<T> v) {
+    equations.insert(std::pair<std::string, Expression<T> >(k, v));
+  }
+  /**
+     init is the value where it STARTS, it's working the other way
+     if there's no stability then it ends with -init
+  */
+  std::map<std::string, T> solveBF(const T& init) const {
+    std::map<std::string, T> solutions;
+    for (typename std::map<std::string, Expression<T> >::const_iterator it = equations.begin();
+         it != equations.end();
+         ++it){
+      solutions[it->first] = init;
+    }
+    int num = equations.size();
+    for (int i = 0; i < num; ++i) {
+      solutions = eval(solutions, false, -init);
+    }
+    solutions = eval(solutions, true, -init);
+    for (int i = 0; i < num-1; ++i) {
+      solutions = eval(solutions, false, -init);
+    }
+    return solutions;
+  }
+
+  EquationSystem maxStrategy(const std::map<std::string, T>& assignment) {
+    EquationSystem result;
+    for (typename std::map<std::string, Expression<T> >::const_iterator it = equations.begin();
+         it != equations.end();
+         ++it) {
+      result.add(it->first, it->second.maxStrategyEager(assignment));
+    }
+    return result;
+  }
+
+  private:
+  std::map<std::string, T> eval(const std::map<std::string, T>& assignment, bool infinity, const T& infValue) const {
+    std::map<std::string, T> result;
+    for (typename std::map<std::string, Expression<T> >::const_iterator it = equations.begin();
+         it != equations.end();
+         ++it) {
+      T val = it->second.eval(assignment);
+      if (infinity) {
+        typename std::map<std::string, T>::const_iterator oldEntry = assignment.find(it->first);
+        result[it->first] = (oldEntry->second == val ? val : infValue);
+      } else {
+        result[it->first] = val;
+      }
+    }
+    return result;
+  }
+  std::map<std::string, Expression<T> > equations;
+};
+
+#endif
diff --git a/impl/Expression.cpp b/impl/Expression.cpp
deleted file mode 100644
index 61fe3ac..0000000
--- a/impl/Expression.cpp
+++ /dev/null
@@ -1,13 +0,0 @@
-#include "Expression.h"
-
-template<typename T>
-const T
-Expression<T> :: minvalue(std::map< std::string, T> > m) {
-  return _operator.eval(_arguments, m);
-}
-
-template<typename T>
-const T
-Expression<T> :: maxvalue(std::map< std::string, T> > m) {
-  return _operator.eval(_arguments, m);
-}
diff --git a/impl/Expression.h b/impl/Expression.h
deleted file mode 100644
index 38a5e65..0000000
--- a/impl/Expression.h
+++ /dev/null
@@ -1,26 +0,0 @@
-#ifndef EXPRESSION_H
-#define EXPRESSION_H
-
-#include <map>
-#include <string>
-#include <vector>
-template<typename T>
-struct Expression;
-#include "Operator.h"
-
-template<typename T>
-struct Expression {
-  Expression(Operator<T>* o, std::vector< Expression<T> > a)
-    : _operator(o), _arguments(a) { }
-  virtual const T minvalue(std::map<std::string, T> m) const {
-    return _operator->eval(_arguments, m);
-  }
-  virtual const T maxvalue(std::map<std::string, T> m) const {
-    return _operator->eval(_arguments, m);
-  }
-  private:
-  Operator<T>* _operator;
-  std::vector< Expression<T> > _arguments;
-};
-
-#endif
diff --git a/impl/Expression.hpp b/impl/Expression.hpp
new file mode 100644
index 0000000..7d2d956
--- /dev/null
+++ b/impl/Expression.hpp
@@ -0,0 +1,80 @@
+#ifndef EXPRESSION_H
+#define EXPRESSION_H
+
+#include <map>
+#include <string>
+#include <vector>
+template<typename T>
+struct Expression;
+#include "Operator.hpp"
+
+template<typename T>
+struct Maximum : public Operator<T> {
+  const T eval(const std::vector<Expression<T> >& v, const std::map<std::string, T>& m) const {
+    //assert(v.size() == 1);
+    T value = -INFINITY;
+    for (typename std::vector<Expression<T> >::const_iterator it = v.begin();
+         it != v.end();
+         ++it) {
+      const T result = it->eval(m);
+      value = (value < result ? result : value);
+    }
+    return value;
+  }
+};
+
+template<typename T>
+struct Minimum : public Operator<T> {
+  const T eval(const std::vector<Expression<T> >& v, const std::map<std::string, T>& m) const {
+    //assert(v.size() == 1);
+    T value = INFINITY;
+    for (typename std::vector<Expression<T> >::const_iterator it = v.begin();
+         it != v.end();
+         ++it) {
+      const T result = it->eval(m);
+      value = (value < result ? value : result);
+    }
+    return value;
+  }
+};
+
+
+template<typename T>
+struct Expression {
+  Expression(Operator<T>* o, const std::vector< Expression<T> >& a)
+    : _operator(o), _arguments(a) { }
+  virtual const T eval(std::map<std::string, T> m) const {
+    return _operator->eval(_arguments, m);
+  }
+
+  virtual Expression<T> maxStrategyEager(const std::map<std::string, T> assignment) const {
+    if (dynamic_cast<Maximum<T>*>(_operator) != NULL) {
+      T bestVal;
+      const Expression<T>* best;
+      for (typename std::vector<Expression<T> >::const_iterator it = _arguments.begin();
+           it != _arguments.end();
+           ++it) {
+        T nextVal = it->eval(assignment);
+        if (best == NULL || nextVal > bestVal) {
+          best = &(*it);
+          bestVal = nextVal;
+        }
+      }
+      return best->maxStrategyEager(assignment);
+    }
+    std::vector<Expression<T> > newArgs;
+    for (typename std::vector<Expression<T> >::const_iterator it = _arguments.begin();
+         it != _arguments.end();
+         ++it) {
+      newArgs.push_back(it->maxStrategyEager(assignment));
+    }
+    return Expression(_operator, newArgs);
+  }
+
+  virtual ~Expression() {}
+  private:
+  Operator<T>* _operator;
+  std::vector< Expression<T> > _arguments;
+};
+
+#endif
diff --git a/impl/Operator.h b/impl/Operator.hpp
index e83d495..f9a80f3 100644
--- a/impl/Operator.h
+++ b/impl/Operator.hpp
@@ -4,11 +4,13 @@
 #include <map>
 #include <string>
 #include <vector>
-#include "Expression.h"
+#include "Expression.hpp"
 
 template<typename T>
 struct Operator {
   virtual const T eval(const std::vector< Expression<T> >&, const std::map<std::string, T>&) const = 0;
 };
 
+#include "Expression.hpp"
+
 #endif
diff --git a/impl/main.cpp b/impl/main.cpp
index dc6cf45..c048c5b 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -1,8 +1,9 @@
 #include <iostream>
 #include <vector>
 #include <math.h>
-#include "Expression.h"
-#include "Operator.h"
+#include "Expression.hpp"
+#include "Operator.hpp"
+#include "EquationSystem.hpp"
 
 using namespace std;
 
@@ -11,8 +12,7 @@ struct Variable : public Operator<float> {
     : _value(x) { }
   const float eval(const vector<Expression<float> >& v, const map<string, float>& m) const {
     //assert(v.size() == 0);
-    map<string, float>::const_iterator it = m.find(_value);
-    return (it == m.end() ? -INFINITY : it->second);
+    return m.find(_value)->second;
   }
   private:
   std::string _value;
@@ -29,67 +29,106 @@ struct Const : public Operator<float> {
   float _value;
 };
 
-struct Mult : public Operator<float> {
-  Mult(const float& x)
+struct Plus : public Operator<float> {
+  Plus(const float& x)
     : _value(x) { }
   const float eval(const vector<Expression<float> >& v, const map<string, float>& m) const {
     //assert(v.size() == 1);
-    return _value * v[0].minvalue(m);
+    return _value + v[0].eval(m);
   }
   private:
   float _value;
 };
 
-struct Maximum : public Operator<float> {
+struct Mult : public Operator<float> {
+  Mult(const float& x)
+    : _value(x) { }
   const float eval(const vector<Expression<float> >& v, const map<string, float>& m) const {
     //assert(v.size() == 1);
-    float value = -INFINITY;
-    for (vector<Expression<float> >::const_iterator it = v.begin();
-         it != v.end();
-         ++it) {
-      const float result = it->maxvalue(m);
-      value = (value < result ? result : value);
-    }
-    return value;
+    return _value * v[0].eval(m);
   }
+  private:
+  float _value;
 };
 
-struct Minimum : public Operator<float> {
-  const float eval(const vector<Expression<float> >& v, const map<string, float>& m) const {
-    //assert(v.size() == 1);
-    float value = INFINITY;
-    for (vector<Expression<float> >::const_iterator it = v.begin();
-         it != v.end();
-         ++it) {
-      const float result = it->maxvalue(m);
-      value = (value < result ? value : result);
-    }
-    return value;
-  }
-};
+Expression<float> constant(float x) {
+  return Expression<float>(new Const(x), vector<Expression<float> >());
+}
+Expression<float> variable(string x) {
+  return Expression<float>(new Variable(x), vector<Expression<float> >());
+}
+Expression<float> add(float a, Expression<float> b) {
+  vector<Expression<float> > args;
+  args.push_back(b);
+  return Expression<float>(new Plus(a), args);
+}
+Expression<float> Max(Expression<float> a, Expression<float> b) {
+  vector<Expression<float> > args;
+  args.push_back(a);
+  args.push_back(b);
+  return Expression<float>(new Maximum<float>(), args);
+}
+Expression<float> Min(Expression<float> a, Expression<float> b) {
+  vector<Expression<float> > args;
+  args.push_back(a);
+  args.push_back(b);
+  return Expression<float>(new Minimum<float>(), args);
+}
 
 int main () {
   typedef Expression<float> E;
   typedef vector<E> Args;
-  map<string, float> m;
-  //m["x"] = -10;
   Args empty;
-  {
-    Args a;
-    {
-      Args b;
-      b.push_back(E(new Const(10), empty));
-      b.push_back(E(new Const(20), empty));
-      b.push_back(E(new Variable("x"), empty));
-      a.push_back(E(new Minimum(), b));
-      cout << E(new Minimum(), b).minvalue(m) << endl;
-    }
-  }
 
-  /*map<string, float> m;
-  vector<Expression<float> > empty;
-  vector<Expression<float> > args;
-  args.push_back(Expression<float>(new Const(10), empty));
-  cout << Expression<float>(new Mult(3), args).minvalue(m) << endl;*/
+  EquationSystem<float> test;
+
+  // problem:
+  // x = max(y, 10)
+  // y = 10 * x
+
+  test.add("x1", Max(constant(0),
+                     Min(add(-1, variable("x1")),
+                         variable("x2"))));
+  test.add("x2", Max(constant(0),
+                     Max(add(5, variable("x1")),
+                         variable("x1"))));
+  test.add("x3", Max(constant(0),
+                     Max(add(1, variable("x3")),
+                         add(0, variable("x1")))));
+
+  map<string, float> m = test.solveBF(-INFINITY);
+  cout << m["x1"] << endl;
+  cout << m["x2"] << endl;
+  cout << m["x3"] << endl;
+
+  m = test.maxStrategy(m).solveBF(-INFINITY);
+  cout << m["x1"] << endl;
+  cout << m["x2"] << endl;
+  cout << m["x3"] << endl;
+
+
+  /*Args xArgs;
+  xArgs.push_back(E(new Variable("x"), empty));
+  xArgs.push_back(E(new Const(10), empty));
+  test.add("x", E(new Maximum<float>(), xArgs));
+
+  Args yArgs;
+  yArgs.push_back(E(new Variable("x"), empty));
+  test.add("y", E(new Mult(10), yArgs));
+
+  map<string, float> m = test.solveBF(-INFINITY);
+  cout << m["x"] << endl;
+  cout << m["y"] << endl;
+
+  map<string,float> assignment;
+  assignment["x"] = -INFINITY;
+  assignment["y"] = -INFINITY;
+  map<string, float> result = test.maxStrategy(assignment).solveBF(INFINITY);
+  cout << result["x"] << endl;
+  cout << result["y"] << endl;
+
+
+  assignment["x"] = 12;
+  cout << E(new Maximum<float>(), xArgs).maxStrategyEager(assignment).eval(assignment) << endl;*/
   return 0;
 }