summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--impl/EquationSystem.hpp64
-rw-r--r--impl/Expression.cpp13
-rw-r--r--impl/Expression.h26
-rw-r--r--impl/Expression.hpp80
-rw-r--r--impl/Operator.hpp (renamed from impl/Operator.h)4
-rw-r--r--impl/main.cpp133
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;
}
generated by cgit v1.2.3 (git 2.46.2) at 2024-11-10 07:16:28 +0000