From 63a10756032fa5c677787fba209706b8bf1e4bef Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Thu, 26 Apr 2012 16:15:17 +1000 Subject: A bunch of modifications working to a good solver. --- impl/EquationSystem.hpp | 13 ++++++++++++ impl/Expression.hpp | 37 ++++++++++++++++++++++++++++++--- impl/ExpressionFactory.hpp | 19 +++++++++++++++++ impl/Makefile | 3 ++- impl/Operator.hpp | 1 + impl/Solver.hpp | 30 ++++++++++++++++++++++++++ impl/main.cpp | 52 +++++++++++++++++++++++++++++++++++++++------- 7 files changed, 144 insertions(+), 11 deletions(-) create mode 100644 impl/ExpressionFactory.hpp create mode 100644 impl/Solver.hpp (limited to 'impl') diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp index efd34b3..3232620 100644 --- a/impl/EquationSystem.hpp +++ b/impl/EquationSystem.hpp @@ -10,6 +10,9 @@ 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 @@ -42,6 +45,16 @@ struct EquationSystem { 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; diff --git a/impl/Expression.hpp b/impl/Expression.hpp index 7d2d956..97dda10 100644 --- a/impl/Expression.hpp +++ b/impl/Expression.hpp @@ -1,6 +1,7 @@ #ifndef EXPRESSION_H #define EXPRESSION_H +#include #include #include #include @@ -21,6 +22,9 @@ struct Maximum : public Operator { } return value; } + virtual std::string output() const { + return "max"; + } }; template @@ -36,13 +40,16 @@ struct Minimum : public Operator { } return value; } + virtual std::string output() const { + return "min"; + } }; template struct Expression { - Expression(Operator* o, const std::vector< Expression >& a) - : _operator(o), _arguments(a) { } + 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); } @@ -50,7 +57,7 @@ struct Expression { virtual Expression maxStrategyEager(const std::map assignment) const { if (dynamic_cast*>(_operator) != NULL) { T bestVal; - const Expression* best; + const Expression* best = NULL; for (typename std::vector >::const_iterator it = _arguments.begin(); it != _arguments.end(); ++it) { @@ -71,10 +78,34 @@ struct Expression { 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 + ")"; + } + 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 new file mode 100644 index 0000000..605dd9e --- /dev/null +++ b/impl/ExpressionFactory.hpp @@ -0,0 +1,19 @@ +#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/Makefile b/impl/Makefile index 1d2eb4b..05e4a83 100644 --- a/impl/Makefile +++ b/impl/Makefile @@ -1,8 +1,9 @@ CC=g++ BUILD=build/ +FLAGS=-Wall -Werror -g all: build-dir - $(CC) main.cpp -Wall -Werror -o $(BUILD)/main + $(CC) main.cpp $(FLAGS) -o $(BUILD)/main build-dir: mkdir -p $(BUILD) diff --git a/impl/Operator.hpp b/impl/Operator.hpp index f9a80f3..9f17cbf 100644 --- a/impl/Operator.hpp +++ b/impl/Operator.hpp @@ -9,6 +9,7 @@ template struct Operator { virtual const T eval(const std::vector< Expression >&, const std::map&) const = 0; + virtual std::string output() const = 0; }; #include "Expression.hpp" diff --git a/impl/Solver.hpp b/impl/Solver.hpp new file mode 100644 index 0000000..53751ca --- /dev/null +++ b/impl/Solver.hpp @@ -0,0 +1,30 @@ +#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/main.cpp b/impl/main.cpp index c048c5b..5b73068 100644 --- a/impl/main.cpp +++ b/impl/main.cpp @@ -4,6 +4,7 @@ #include "Expression.hpp" #include "Operator.hpp" #include "EquationSystem.hpp" +#include "ExpressionFactory.hpp" using namespace std; @@ -14,6 +15,9 @@ struct Variable : public Operator { //assert(v.size() == 0); return m.find(_value)->second; } + virtual std::string output() const { + return "var"; + } private: std::string _value; }; @@ -25,6 +29,9 @@ struct Const : public Operator { //assert(v.size() == 0); return _value; } + virtual std::string output() const { + return "const"; + } private: float _value; }; @@ -36,6 +43,9 @@ struct Plus : public Operator { //assert(v.size() == 1); return _value + v[0].eval(m); } + virtual std::string output() const { + return "+()"; + } private: float _value; }; @@ -47,36 +57,64 @@ struct Mult : public Operator { //assert(v.size() == 1); return _value * v[0].eval(m); } + virtual std::string output() const { + return "*()"; + } private: float _value; }; +ExpressionFactory f; + Expression constant(float x) { - return Expression(new Const(x), vector >()); + return f.createExpression(new Const(x), vector >()); } Expression variable(string x) { - return Expression(new Variable(x), vector >()); + return f.createExpression(new Variable(x), vector >()); } Expression add(float a, Expression b) { vector > args; args.push_back(b); - return Expression(new Plus(a), args); + return f.createExpression(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); + return f.createExpression(new Maximum(), args); } Expression Min(Expression a, Expression b) { vector > args; args.push_back(a); args.push_back(b); - return Expression(new Minimum(), args); + 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; + } int main () { - typedef Expression E; + tests(); + /*typedef Expression E; typedef vector Args; Args empty; @@ -104,7 +142,7 @@ int main () { m = test.maxStrategy(m).solveBF(-INFINITY); cout << m["x1"] << endl; cout << m["x2"] << endl; - cout << m["x3"] << endl; + cout << m["x3"] << endl;*/ /*Args xArgs; -- cgit v1.2.3