summaryrefslogtreecommitdiff
path: root/impl
diff options
context:
space:
mode:
authorCarlo Zancanaro <carlo@carlo-laptop>2012-04-26 16:15:17 +1000
committerCarlo Zancanaro <carlo@carlo-laptop>2012-04-26 16:15:17 +1000
commit63a10756032fa5c677787fba209706b8bf1e4bef (patch)
tree705ee15011d9aaeec3b921c3f808427c8aa00589 /impl
parenta9de4273bf8377aeab7d3f76a6d8bc0c89b42f79 (diff)
A bunch of modifications working to a good solver.
Diffstat (limited to 'impl')
-rw-r--r--impl/EquationSystem.hpp13
-rw-r--r--impl/Expression.hpp37
-rw-r--r--impl/ExpressionFactory.hpp19
-rw-r--r--impl/Makefile3
-rw-r--r--impl/Operator.hpp1
-rw-r--r--impl/Solver.hpp30
-rw-r--r--impl/main.cpp52
7 files changed, 144 insertions, 11 deletions
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<T> v) {
equations.insert(std::pair<std::string, Expression<T> >(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<std::string, Expression<T> >::const_iterator it = equations.begin();
+ it != equations.end();
+ ++it) {
+ output += it->first + " = " + it->second.output() + "\n";
+ }
+ return output;
+ }
+
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;
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 <ostream>
#include <map>
#include <string>
#include <vector>
@@ -21,6 +22,9 @@ struct Maximum : public Operator<T> {
}
return value;
}
+ virtual std::string output() const {
+ return "max";
+ }
};
template<typename T>
@@ -36,13 +40,16 @@ struct Minimum : public Operator<T> {
}
return value;
}
+ virtual std::string output() const {
+ return "min";
+ }
};
template<typename T>
struct Expression {
- Expression(Operator<T>* o, const std::vector< Expression<T> >& a)
- : _operator(o), _arguments(a) { }
+ Expression(unsigned int id, Operator<T>* o, const std::vector< Expression<T> >& a)
+ : _id(id), _operator(o), _arguments(a) { }
virtual const T eval(std::map<std::string, T> m) const {
return _operator->eval(_arguments, m);
}
@@ -50,7 +57,7 @@ struct Expression {
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;
+ const Expression<T>* best = NULL;
for (typename std::vector<Expression<T> >::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<Expression<T> >::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<T>* _operator;
std::vector< Expression<T> > _arguments;
+
+ template<typename E>
+ friend std::ostream& operator<<(std::ostream&, const Expression<E>&);
};
+template<typename T>
+std::ostream& operator<<(std::ostream& cout, const Expression<T>& 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<typename T>
+struct ExpressionFactory {
+ ExpressionFactory() : id(0) { }
+ Expression<T> createExpression(Operator<T>* op, std::vector< Expression<T> > args) {
+ return Expression<T>(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<typename T>
struct Operator {
virtual const T eval(const std::vector< Expression<T> >&, const std::map<std::string, T>&) 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<typename T>
+struct MaxStrategy {
+ MaxStrategy(unsigned int count)
+ : size(count){
+
+ }
+ Expression<T> takeTo(const Expression<T>& from, const Expression<T>& to) {
+ }
+ Expression<T> operator() (const Expression<T>& expression) const {
+ }
+ private:
+ unsigned int count;
+ Expression<T>* mappings;
+};
+
+template<typename T>
+struct Solver {
+ Solver(ExpressionFactory<T> factory, EquationSystem<T> 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<float> {
//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<float> {
//assert(v.size() == 0);
return _value;
}
+ virtual std::string output() const {
+ return "const";
+ }
private:
float _value;
};
@@ -36,6 +43,9 @@ struct Plus : public Operator<float> {
//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<float> {
//assert(v.size() == 1);
return _value * v[0].eval(m);
}
+ virtual std::string output() const {
+ return "*()";
+ }
private:
float _value;
};
+ExpressionFactory<float> f;
+
Expression<float> constant(float x) {
- return Expression<float>(new Const(x), vector<Expression<float> >());
+ return f.createExpression(new Const(x), vector<Expression<float> >());
}
Expression<float> variable(string x) {
- return Expression<float>(new Variable(x), vector<Expression<float> >());
+ return f.createExpression(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);
+ return f.createExpression(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);
+ return f.createExpression(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);
+ return f.createExpression(new Minimum<float>(), args);
+}
+
+
+void tests() {
+ map<string,float> assignment;
+ assignment["x"] = -INFINITY;
+
+ EquationSystem<float> 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<float> E;
+ tests();
+ /*typedef Expression<float> E;
typedef vector<E> 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;