From 76a4f0fcf3a9bf54ef910cdb2c0bebea37182391 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Thu, 26 Apr 2012 22:32:35 +1000 Subject: A new attempt. Better strategies implementation. Still lacking: - Factories (to set the ids) - Solver - Systems of equations --- impl/EquationSystem.hpp | 77 ------------------ impl/Expression.hpp | 119 ++++++---------------------- impl/ExpressionFactory.hpp | 19 ----- impl/MaxStrategy.hpp | 39 +++++++++ impl/Operator.hpp | 50 ++++++++++-- impl/Solver.hpp | 30 ------- impl/Variable.hpp | 22 ++++++ impl/VariableAssignment.hpp | 30 +++++++ impl/main.cpp | 188 +++++++------------------------------------- 9 files changed, 188 insertions(+), 386 deletions(-) delete mode 100644 impl/EquationSystem.hpp delete mode 100644 impl/ExpressionFactory.hpp create mode 100644 impl/MaxStrategy.hpp delete mode 100644 impl/Solver.hpp create mode 100644 impl/Variable.hpp create mode 100644 impl/VariableAssignment.hpp (limited to 'impl') diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp deleted file mode 100644 index 3232620..0000000 --- a/impl/EquationSystem.hpp +++ /dev/null @@ -1,77 +0,0 @@ -#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)); - } - unsigned int count() const { - return equations.size(); - } - /** - 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; - } - - std::string output() const { - std::string output = ""; - for (typename std::map >::const_iterator it = equations.begin(); - it != equations.end(); - ++it) { - output += it->first + " = " + it->second.output() + "\n"; - } - return output; - } - - 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.hpp b/impl/Expression.hpp index 97dda10..46ccf23 100644 --- a/impl/Expression.hpp +++ b/impl/Expression.hpp @@ -1,111 +1,44 @@ -#ifndef EXPRESSION_H -#define EXPRESSION_H +#ifndef EXPRESSION_HPP +#define EXPRESSION_HPP -#include -#include -#include -#include -template -struct Expression; +#include "VariableAssignment.hpp" #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(); +struct Expression { + Expression(Operator* op, const std::vector< Expression* >& args) + : _operator(op), _arguments(args) { } + virtual ~Expression() { + /*delete _operator; + for (typename std::vector< Expression* >::iterator it = _arguments.begin(); + it != _arguments.end(); ++it) { - const T result = it->eval(m); - value = (value < result ? result : value); - } - return value; + delete *it; + }*/ } - virtual std::string output() const { - return "max"; - } -}; - -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; + const std::vector*>& arguments() const { + return _arguments; } - virtual std::string output() const { - return "min"; + virtual T operator() (const VariableAssignment& assignment) const { + return (*_operator)(_arguments, assignment); } + private: + Operator* _operator; + std::vector< Expression* > _arguments; }; - template -struct Expression { - Expression(unsigned int id, Operator* o, const std::vector< Expression >& a) - : _id(id), _operator(o), _arguments(a) { } - virtual const T eval(std::map m) const { - return _operator->eval(_arguments, m); +struct MaxExpression : public Expression { + MaxExpression(const std::vector< Expression* >& args) + : Expression(new Maximum, args) { } + unsigned int id() const { + return _id; } - - virtual Expression maxStrategyEager(const std::map assignment) const { - if (dynamic_cast*>(_operator) != NULL) { - T bestVal; - const Expression* best = NULL; - 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); - } - - std::string output() const { - std::string result = _operator->output() + "("; - for (typename std::vector >::const_iterator it = _arguments.begin(); - it != _arguments.end(); - ++it) { - if (it != _arguments.begin()) { - result += ", "; - } - result += it->output(); - } - return result + ")"; + unsigned int id(unsigned int id) { + return (_id = id); } - - virtual ~Expression() {} private: unsigned int _id; - Operator* _operator; - std::vector< Expression > _arguments; - - template - friend std::ostream& operator<<(std::ostream&, const Expression&); }; -template -std::ostream& operator<<(std::ostream& cout, const Expression& e) { - cout << e._operator->output() << "(" - << ")"; - return cout; -} - #endif diff --git a/impl/ExpressionFactory.hpp b/impl/ExpressionFactory.hpp deleted file mode 100644 index 605dd9e..0000000 --- a/impl/ExpressionFactory.hpp +++ /dev/null @@ -1,19 +0,0 @@ -#ifndef EXPRESSION_FACTORY_HPP -#define EXPRESSION_FACTORY_HPP - -#include "Expression.hpp" - -template -struct ExpressionFactory { - ExpressionFactory() : id(0) { } - Expression createExpression(Operator* op, std::vector< Expression > args) { - return Expression(id++, op, args); - } - unsigned int count() const { - return id; - } - private: - unsigned int id; -}; - -#endif diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp new file mode 100644 index 0000000..a324359 --- /dev/null +++ b/impl/MaxStrategy.hpp @@ -0,0 +1,39 @@ +#ifndef MAX_STRATEGY_HPP +#define MAX_STRATEGY_HPP + +#include "Expression.hpp" +#include "VariableAssignment.hpp" + +template +struct MaxStrategy { + MaxStrategy(unsigned int length) + : _length(length), _assignment(new unsigned int[length]) { } + virtual ~MaxStrategy() { + delete[] _assignment; + } + const unsigned int& operator[] (const MaxExpression x) const { + if (x.id() < 0 || x.id() >= _length) { + throw "Array out of bounds"; + } + return _assignment[x.id()]; + } + unsigned int& operator[] (const MaxExpression& x) { + if (x.id() < 0 || x.id() >= _length) { + throw "Array out of bounds"; + } + return _assignment[x.id()]; + } + T operator() (const Expression& expr, const VariableAssignment& rho) const { + const MaxExpression* max = dynamic_cast*>(&expr); + if (max == NULL) { + return expr(rho); + } else { + return (*expr.arguments()[_assignment[max->id()]])(rho); + } + } + private: + unsigned int _length; + unsigned int* _assignment; +}; + +#endif diff --git a/impl/Operator.hpp b/impl/Operator.hpp index 9f17cbf..d6b92f2 100644 --- a/impl/Operator.hpp +++ b/impl/Operator.hpp @@ -1,17 +1,53 @@ -#ifndef OPERATOR_H -#define OPERATOR_H +#ifndef OPERATOR_HPP +#define OPERATOR_HPP + +template +T infinity() { } + +template<> +float infinity() { + return INFINITY; +} -#include -#include #include -#include "Expression.hpp" + +template +struct VariableAssignment; +template +struct Expression; template struct Operator { - virtual const T eval(const std::vector< Expression >&, const std::map&) const = 0; - virtual std::string output() const = 0; + virtual T operator() (const std::vector< Expression* >&, const VariableAssignment&) const = 0; +}; +template +struct Maximum : public Operator { + virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& assignment) const { + T value = -infinity(); + for (typename std::vector< Expression* >::const_iterator it = args.begin(); + it != args.end(); + ++it) { + T temporary = (**it)(assignment); + value = (temporary < value ? value : temporary); + } + return value; + } +}; +template +struct Minimumm : public Operator { + virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& assignment) const { + T value = -infinity(); + for (typename std::vector< Expression* >::const_iterator it = args.begin(); + it != args.end(); + ++it) { + T temporary = (**it)(assignment); + value = (temporary > value ? value : temporary); + } + return value; + } }; +#include "VariableAssignment.hpp" #include "Expression.hpp" #endif diff --git a/impl/Solver.hpp b/impl/Solver.hpp deleted file mode 100644 index 53751ca..0000000 --- a/impl/Solver.hpp +++ /dev/null @@ -1,30 +0,0 @@ -#ifndef SOLVER_HPP -#define SOLVER_HPP - -template -struct MaxStrategy { - MaxStrategy(unsigned int count) - : size(count){ - - } - Expression takeTo(const Expression& from, const Expression& to) { - } - Expression operator() (const Expression& expression) const { - } - private: - unsigned int count; - Expression* mappings; -}; - -template -struct Solver { - Solver(ExpressionFactory factory, EquationSystem system) - : numExpressions(factory.count()), numVariables(system.count()) { - } - private: - unsigned int numExpressions; - unsigned int numVariables; - MaxStrategy _strategy; -}; - -#endif diff --git a/impl/Variable.hpp b/impl/Variable.hpp new file mode 100644 index 0000000..0ba13e9 --- /dev/null +++ b/impl/Variable.hpp @@ -0,0 +1,22 @@ +#ifndef VARIABLE_HPP +#define VARIABLE_HPP + +#include "Operator.hpp" + +template +struct Variable : public Operator { + unsigned int id() const { + return _id; + } + unsigned int id(unsigned int id) { + return (_id = id); + } + T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { + //assert(args.size() == 0) + return ass[*this]; + } + private: + unsigned int _id; +}; + +#endif diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp new file mode 100644 index 0000000..e41f3d8 --- /dev/null +++ b/impl/VariableAssignment.hpp @@ -0,0 +1,30 @@ +#ifndef VARIABLE_ASSIGNMENT_HPP +#define VARIABLE_ASSIGNMENT_HPP + +#include "Variable.hpp" + +template +struct VariableAssignment { + VariableAssignment(unsigned int length) + : _length(length), _assignment(new T[length]) { } + ~VariableAssignment() { + delete[] _assignment; + } + const T& operator[] (const Variable x) const { + if (x.id() < 0 || x.id() >= _length) { + throw "Array out of bounds"; + } + return _assignment[x.id()]; + } + T& operator[] (const Variable& x) { + if (x.id() < 0 || x.id() >= _length) { + throw "Array out of bounds"; + } + return _assignment[x.id()]; + } + private: + unsigned int _length; + T* _assignment; +}; + +#endif diff --git a/impl/main.cpp b/impl/main.cpp index 5b73068..589a1e7 100644 --- a/impl/main.cpp +++ b/impl/main.cpp @@ -1,172 +1,40 @@ #include #include #include -#include "Expression.hpp" + #include "Operator.hpp" -#include "EquationSystem.hpp" -#include "ExpressionFactory.hpp" +#include "Expression.hpp" +#include "MaxStrategy.hpp" using namespace std; -struct Variable : public Operator { - Variable(const std::string& x) - : _value(x) { } - const float eval(const vector >& v, const map& m) const { - //assert(v.size() == 0); - return m.find(_value)->second; - } - virtual std::string output() const { - return "var"; - } - private: - std::string _value; -}; - -struct Const : public Operator { - Const(const float& x) - : _value(x) { } - const float eval(const vector >& v, const map& m) const { - //assert(v.size() == 0); - return _value; - } - virtual std::string output() const { - return "const"; - } - private: - float _value; -}; - -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].eval(m); - } - virtual std::string output() const { - return "+()"; - } - private: - float _value; -}; - -struct Mult : public Operator { - Mult(const float& x) - : _value(x) { } - const float eval(const vector >& v, const map& m) const { - //assert(v.size() == 1); - return _value * v[0].eval(m); - } - virtual std::string output() const { - return "*()"; - } +/*template +struct Complete { + Complete(const T& value) + : _value(value) { } private: - float _value; -}; - -ExpressionFactory f; - -Expression constant(float x) { - return f.createExpression(new Const(x), vector >()); -} -Expression variable(string x) { - return f.createExpression(new Variable(x), vector >()); -} -Expression add(float a, Expression b) { - vector > args; - args.push_back(b); - return f.createExpression(new Plus(a), args); -} -Expression Max(Expression a, Expression b) { - vector > args; - args.push_back(a); - args.push_back(b); - return f.createExpression(new Maximum(), args); -} -Expression Min(Expression a, Expression b) { - vector > args; - args.push_back(a); - args.push_back(b); - return f.createExpression(new Minimum(), args); -} - - -void tests() { - map assignment; - assignment["x"] = -INFINITY; - - EquationSystem test; - test.add("x", Max(constant(0), - Min(add(1, variable("x")), - constant(100)))); - - test = test.maxStrategy(assignment); - cout << test.output(); - assignment = test.solveBF(-INFINITY); - cout << assignment["x"] << endl; - - test = test.maxStrategy(assignment); - cout << test.output(); - assignment = test.solveBF(-INFINITY); - cout << assignment["x"] << endl; - -} + bool _infinity; + T _value; +};*/ +std::vector< Expression* > empty; int main () { - tests(); - /*typedef Expression E; - typedef vector Args; - Args empty; - - 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;*/ + Variable x; + x.id(0); + Variable y; + y.id(1); + VariableAssignment rho(2); + rho[x] = 12; + rho[y] = 10; + Expression expr(&x, empty); + + std::vector*> args; + args.push_back(new Expression(&x, empty)); + args.push_back(new Expression(&y, empty)); + MaxExpression maxExpr(args); + maxExpr.id(0); + MaxStrategy strat(1); + strat[maxExpr] = 0; + cout << strat(maxExpr,rho) << endl; return 0; } -- cgit v1.2.3