From a9de4273bf8377aeab7d3f76a6d8bc0c89b42f79 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Fri, 20 Apr 2012 01:19:54 +1000 Subject: Start on the max-strategy stuff. Also more BF. --- impl/EquationSystem.hpp | 64 +++++++++++++++++++++++ impl/Expression.cpp | 13 ----- impl/Expression.h | 26 ---------- impl/Expression.hpp | 80 +++++++++++++++++++++++++++++ impl/Operator.h | 14 ----- impl/Operator.hpp | 16 ++++++ impl/main.cpp | 133 +++++++++++++++++++++++++++++++----------------- 7 files changed, 246 insertions(+), 100 deletions(-) create mode 100644 impl/EquationSystem.hpp delete mode 100644 impl/Expression.cpp delete mode 100644 impl/Expression.h create mode 100644 impl/Expression.hpp delete mode 100644 impl/Operator.h create mode 100644 impl/Operator.hpp 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 +#include +#include "Expression.hpp" + +template +struct EquationSystem { + void add(std::string k, Expression v) { + equations.insert(std::pair >(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 solveBF(const T& init) const { + std::map solutions; + for (typename std::map >::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& assignment) { + EquationSystem result; + for (typename std::map >::const_iterator it = equations.begin(); + it != equations.end(); + ++it) { + result.add(it->first, it->second.maxStrategyEager(assignment)); + } + return result; + } + + private: + std::map eval(const std::map& assignment, bool infinity, const T& infValue) const { + std::map result; + for (typename std::map >::const_iterator it = equations.begin(); + it != equations.end(); + ++it) { + T val = it->second.eval(assignment); + if (infinity) { + typename std::map::const_iterator oldEntry = assignment.find(it->first); + result[it->first] = (oldEntry->second == val ? val : infValue); + } else { + result[it->first] = val; + } + } + return result; + } + std::map > 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 -const T -Expression :: minvalue(std::map< std::string, T> > m) { - return _operator.eval(_arguments, m); -} - -template -const T -Expression :: 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 -#include -#include -template -struct Expression; -#include "Operator.h" - -template -struct Expression { - Expression(Operator* o, std::vector< Expression > a) - : _operator(o), _arguments(a) { } - virtual const T minvalue(std::map m) const { - return _operator->eval(_arguments, m); - } - virtual const T maxvalue(std::map m) const { - return _operator->eval(_arguments, m); - } - private: - Operator* _operator; - std::vector< Expression > _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 +#include +#include +template +struct Expression; +#include "Operator.hpp" + +template +struct Maximum : public Operator { + const T eval(const std::vector >& v, const std::map& m) const { + //assert(v.size() == 1); + T value = -INFINITY; + for (typename std::vector >::const_iterator it = v.begin(); + it != v.end(); + ++it) { + const T result = it->eval(m); + value = (value < result ? result : value); + } + return value; + } +}; + +template +struct Minimum : public Operator { + const T eval(const std::vector >& v, const std::map& m) const { + //assert(v.size() == 1); + T value = INFINITY; + for (typename std::vector >::const_iterator it = v.begin(); + it != v.end(); + ++it) { + const T result = it->eval(m); + value = (value < result ? value : result); + } + return value; + } +}; + + +template +struct Expression { + Expression(Operator* o, const std::vector< Expression >& a) + : _operator(o), _arguments(a) { } + virtual const T eval(std::map m) const { + return _operator->eval(_arguments, m); + } + + virtual Expression maxStrategyEager(const std::map assignment) const { + if (dynamic_cast*>(_operator) != NULL) { + T bestVal; + const Expression* best; + for (typename std::vector >::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 > newArgs; + for (typename std::vector >::const_iterator it = _arguments.begin(); + it != _arguments.end(); + ++it) { + newArgs.push_back(it->maxStrategyEager(assignment)); + } + return Expression(_operator, newArgs); + } + + virtual ~Expression() {} + private: + Operator* _operator; + std::vector< Expression > _arguments; +}; + +#endif diff --git a/impl/Operator.h b/impl/Operator.h deleted file mode 100644 index e83d495..0000000 --- a/impl/Operator.h +++ /dev/null @@ -1,14 +0,0 @@ -#ifndef OPERATOR_H -#define OPERATOR_H - -#include -#include -#include -#include "Expression.h" - -template -struct Operator { - virtual const T eval(const std::vector< Expression >&, const std::map&) const = 0; -}; - -#endif diff --git a/impl/Operator.hpp b/impl/Operator.hpp new file mode 100644 index 0000000..f9a80f3 --- /dev/null +++ b/impl/Operator.hpp @@ -0,0 +1,16 @@ +#ifndef OPERATOR_H +#define OPERATOR_H + +#include +#include +#include +#include "Expression.hpp" + +template +struct Operator { + virtual const T eval(const std::vector< Expression >&, const std::map&) 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 #include #include -#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 { : _value(x) { } const float eval(const vector >& v, const map& m) const { //assert(v.size() == 0); - map::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 _value; }; -struct Mult : public Operator { - Mult(const float& x) +struct Plus : public Operator { + Plus(const float& x) : _value(x) { } const float eval(const vector >& v, const map& 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 { +struct Mult : public Operator { + Mult(const float& x) + : _value(x) { } const float eval(const vector >& v, const map& m) const { //assert(v.size() == 1); - float value = -INFINITY; - for (vector >::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 { - const float eval(const vector >& v, const map& m) const { - //assert(v.size() == 1); - float value = INFINITY; - for (vector >::const_iterator it = v.begin(); - it != v.end(); - ++it) { - const float result = it->maxvalue(m); - value = (value < result ? value : result); - } - return value; - } -}; +Expression constant(float x) { + return Expression(new Const(x), vector >()); +} +Expression variable(string x) { + return Expression(new Variable(x), vector >()); +} +Expression add(float a, Expression b) { + vector > args; + args.push_back(b); + return Expression(new Plus(a), args); +} +Expression Max(Expression a, Expression b) { + vector > args; + args.push_back(a); + args.push_back(b); + return Expression(new Maximum(), args); +} +Expression Min(Expression a, Expression b) { + vector > args; + args.push_back(a); + args.push_back(b); + return Expression(new Minimum(), args); +} int main () { typedef Expression E; typedef vector Args; - map 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 m; - vector > empty; - vector > args; - args.push_back(Expression(new Const(10), empty)); - cout << Expression(new Mult(3), args).minvalue(m) << endl;*/ + EquationSystem 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 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(), xArgs)); + + Args yArgs; + yArgs.push_back(E(new Variable("x"), empty)); + test.add("y", E(new Mult(10), yArgs)); + + map m = test.solveBF(-INFINITY); + cout << m["x"] << endl; + cout << m["y"] << endl; + + map assignment; + assignment["x"] = -INFINITY; + assignment["y"] = -INFINITY; + map result = test.maxStrategy(assignment).solveBF(INFINITY); + cout << result["x"] << endl; + cout << result["y"] << endl; + + + assignment["x"] = 12; + cout << E(new Maximum(), xArgs).maxStrategyEager(assignment).eval(assignment) << endl;*/ return 0; } -- cgit v1.2.3