summaryrefslogtreecommitdiff
path: root/impl
diff options
context:
space:
mode:
Diffstat (limited to 'impl')
-rw-r--r--impl/EquationSystem.hpp77
-rw-r--r--impl/Expression.hpp119
-rw-r--r--impl/ExpressionFactory.hpp19
-rw-r--r--impl/MaxStrategy.hpp39
-rw-r--r--impl/Operator.hpp50
-rw-r--r--impl/Solver.hpp30
-rw-r--r--impl/Variable.hpp22
-rw-r--r--impl/VariableAssignment.hpp30
-rw-r--r--impl/main.cpp188
9 files changed, 188 insertions, 386 deletions
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 <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));
- }
- 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<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;
- }
-
- 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;
- 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.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 <ostream>
-#include <map>
-#include <string>
-#include <vector>
-template<typename T>
-struct Expression;
+#include "VariableAssignment.hpp"
#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();
+struct Expression {
+ Expression(Operator<T>* op, const std::vector< Expression<T>* >& args)
+ : _operator(op), _arguments(args) { }
+ virtual ~Expression() {
+ /*delete _operator;
+ for (typename std::vector< Expression<T>* >::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<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;
+ const std::vector<Expression<T>*>& arguments() const {
+ return _arguments;
}
- virtual std::string output() const {
- return "min";
+ virtual T operator() (const VariableAssignment<T>& assignment) const {
+ return (*_operator)(_arguments, assignment);
}
+ private:
+ Operator<T>* _operator;
+ std::vector< Expression<T>* > _arguments;
};
-
template<typename T>
-struct Expression {
- 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);
+struct MaxExpression : public Expression<T> {
+ MaxExpression(const std::vector< Expression<T>* >& args)
+ : Expression<T>(new Maximum<T>, args) { }
+ unsigned int id() const {
+ return _id;
}
-
- 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 = NULL;
- 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);
- }
-
- 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 + ")";
+ unsigned int id(unsigned int id) {
+ return (_id = id);
}
-
- 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
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<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/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<typename T>
+struct MaxStrategy {
+ MaxStrategy(unsigned int length)
+ : _length(length), _assignment(new unsigned int[length]) { }
+ virtual ~MaxStrategy() {
+ delete[] _assignment;
+ }
+ const unsigned int& operator[] (const MaxExpression<T> x) const {
+ if (x.id() < 0 || x.id() >= _length) {
+ throw "Array out of bounds";
+ }
+ return _assignment[x.id()];
+ }
+ unsigned int& operator[] (const MaxExpression<T>& x) {
+ if (x.id() < 0 || x.id() >= _length) {
+ throw "Array out of bounds";
+ }
+ return _assignment[x.id()];
+ }
+ T operator() (const Expression<T>& expr, const VariableAssignment<T>& rho) const {
+ const MaxExpression<T>* max = dynamic_cast<const MaxExpression<T>*>(&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<typename T>
+T infinity() { }
+
+template<>
+float infinity() {
+ return INFINITY;
+}
-#include <map>
-#include <string>
#include <vector>
-#include "Expression.hpp"
+
+template<typename T>
+struct VariableAssignment;
+template<typename T>
+struct Expression;
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;
+ virtual T operator() (const std::vector< Expression<T>* >&, const VariableAssignment<T>&) const = 0;
+};
+template<typename T>
+struct Maximum : public Operator<T> {
+ virtual T operator() (const std::vector< Expression<T>* >& args, const VariableAssignment<T>& assignment) const {
+ T value = -infinity<T>();
+ for (typename std::vector< Expression<T>* >::const_iterator it = args.begin();
+ it != args.end();
+ ++it) {
+ T temporary = (**it)(assignment);
+ value = (temporary < value ? value : temporary);
+ }
+ return value;
+ }
+};
+template<typename T>
+struct Minimumm : public Operator<T> {
+ virtual T operator() (const std::vector< Expression<T>* >& args, const VariableAssignment<T>& assignment) const {
+ T value = -infinity<T>();
+ for (typename std::vector< Expression<T>* >::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<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/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<typename T>
+struct Variable : public Operator<T> {
+ unsigned int id() const {
+ return _id;
+ }
+ unsigned int id(unsigned int id) {
+ return (_id = id);
+ }
+ T operator() (const std::vector< Expression<T>* >& args, const VariableAssignment<T>& 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<typename T>
+struct VariableAssignment {
+ VariableAssignment(unsigned int length)
+ : _length(length), _assignment(new T[length]) { }
+ ~VariableAssignment() {
+ delete[] _assignment;
+ }
+ const T& operator[] (const Variable<T> x) const {
+ if (x.id() < 0 || x.id() >= _length) {
+ throw "Array out of bounds";
+ }
+ return _assignment[x.id()];
+ }
+ T& operator[] (const Variable<T>& 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 <iostream>
#include <vector>
#include <math.h>
-#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<float> {
- Variable(const std::string& x)
- : _value(x) { }
- const float eval(const vector<Expression<float> >& v, const map<string, float>& 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<float> {
- Const(const float& x)
- : _value(x) { }
- const float eval(const vector<Expression<float> >& v, const map<string, float>& m) const {
- //assert(v.size() == 0);
- return _value;
- }
- virtual std::string output() const {
- return "const";
- }
- private:
- float _value;
-};
-
-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].eval(m);
- }
- virtual std::string output() const {
- return "+()";
- }
- private:
- float _value;
-};
-
-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);
- return _value * v[0].eval(m);
- }
- virtual std::string output() const {
- return "*()";
- }
+/*template<typename T>
+struct Complete {
+ Complete(const T& value)
+ : _value(value) { }
private:
- float _value;
-};
-
-ExpressionFactory<float> f;
-
-Expression<float> constant(float x) {
- return f.createExpression(new Const(x), vector<Expression<float> >());
-}
-Expression<float> variable(string x) {
- 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 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 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 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;
-
-}
+ bool _infinity;
+ T _value;
+};*/
+std::vector< Expression<float>* > empty;
int main () {
- tests();
- /*typedef Expression<float> E;
- typedef vector<E> Args;
- Args empty;
-
- 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;*/
+ Variable<float> x;
+ x.id(0);
+ Variable<float> y;
+ y.id(1);
+ VariableAssignment<float> rho(2);
+ rho[x] = 12;
+ rho[y] = 10;
+ Expression<float> expr(&x, empty);
+
+ std::vector<Expression<float>*> args;
+ args.push_back(new Expression<float>(&x, empty));
+ args.push_back(new Expression<float>(&y, empty));
+ MaxExpression<float> maxExpr(args);
+ maxExpr.id(0);
+ MaxStrategy<float> strat(1);
+ strat[maxExpr] = 0;
+ cout << strat(maxExpr,rho) << endl;
return 0;
}
generated by cgit v1.2.3 (git 2.46.0) at 2024-09-20 05:48:52 +0000