summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--impl/EquationSystem.hpp79
-rw-r--r--impl/MaxStrategy.hpp5
-rw-r--r--impl/Operator.hpp15
-rw-r--r--impl/Solver.hpp17
-rw-r--r--impl/Variable.hpp9
-rw-r--r--impl/VariableAssignment.hpp44
-rw-r--r--impl/main.cpp33
7 files changed, 181 insertions, 21 deletions
diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
new file mode 100644
index 0000000..065a1a2
--- /dev/null
+++ b/impl/EquationSystem.hpp
@@ -0,0 +1,79 @@
+#ifndef EQUATION_SYSTEM_HPP
+#define EQUATION_SYSTEM_HPP
+
+#include "Expression.hpp"
+
+template<typename T>
+struct EquationSystem {
+ EquationSystem ()
+ : _max_id(0) { }
+ virtual ~EquationSystem() {
+ for (int i = 0, size = _vars.size(); i < size; ++i) {
+ delete _vars[i];
+ }
+ }
+ Variable<T>* newVariable(const std::string&) {
+ _vars.push_back(new Variable<T>(_vars.size()));
+ return _vars[_vars.size()-1];
+ }
+ unsigned int varCount() const {
+ return _vars.size();
+ }
+ MaxExpression<T>* newMaxExpression(const std::vector<Expression<T>*>& args) {
+ MaxExpression<T>* expr = new MaxExpression<T>(args);
+ expr->id(_max_id++);
+ return expr;
+ }
+ unsigned int maxCount() const {
+ return _max_id;
+ }
+
+ Expression<T>*& operator[] (const Variable<T>& v) {
+ if (_expressions.size() <= v.id()) {
+ _expressions.resize(v.id()+1);
+ }
+ return _expressions[v.id()];
+ }
+ const Expression<T>*& operator[] (const Variable<T>& v) const {
+ if (_expressions.size() <= v.id()) {
+ throw "Out of range";
+ }
+ return _expressions[v.id()];
+ }
+
+ template<typename F>
+ VariableAssignment<T> foreach(F op, const VariableAssignment<T>& v) {
+ VariableAssignment<T> result(_vars.size());
+ for (unsigned int i = 0, size = _vars.size(); i < size; ++i) {
+ result[_vars[i]] = op(_expressions[i], v);
+ }
+ }
+
+ VariableAssignment<T> operator() (const VariableAssignment<T>& rho) {
+ VariableAssignment<T> result(_vars.size());
+ for (unsigned int i = 0, size = _vars.size(); i < size; ++i) {
+ result[*_vars[i]] = (*_expressions[i])(rho);
+ }
+ return result;
+ }
+
+ VariableAssignment<T> maxFixpoint() {
+ unsigned int size = _vars.size();
+ VariableAssignment<T> result(size, infinity<T>());
+ for (unsigned int i = 0; i < size; ++i) {
+ result = (*this)(result);
+ }
+ result = result.expand((*this)(result), -infinity<T>());
+ for (unsigned int i = 0; i < size-1; ++i) {
+ result = (*this)(result);
+ }
+ return result;
+ }
+ private:
+ unsigned int _max_id;
+ std::vector<Variable<T>*> _vars;
+ std::vector<Expression<T>*> _expressions;
+};
+
+
+#endif
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index a324359..7a37fb2 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -23,6 +23,9 @@ struct MaxStrategy {
}
return _assignment[x.id()];
}
+ T operator() (const EquationSystem<T>& eqns, const VariableAssignment<T>& rho) const {
+ return eqns.foreach((*this), rho);
+ }
T operator() (const Expression<T>& expr, const VariableAssignment<T>& rho) const {
const MaxExpression<T>* max = dynamic_cast<const MaxExpression<T>*>(&expr);
if (max == NULL) {
@@ -31,6 +34,8 @@ struct MaxStrategy {
return (*expr.arguments()[_assignment[max->id()]])(rho);
}
}
+ MaxStrategy<T> improve() {
+ }
private:
unsigned int _length;
unsigned int* _assignment;
diff --git a/impl/Operator.hpp b/impl/Operator.hpp
index d6b92f2..3e11443 100644
--- a/impl/Operator.hpp
+++ b/impl/Operator.hpp
@@ -34,9 +34,9 @@ struct Maximum : public Operator<T> {
}
};
template<typename T>
-struct Minimumm : public Operator<T> {
+struct Minimum : public Operator<T> {
virtual T operator() (const std::vector< Expression<T>* >& args, const VariableAssignment<T>& assignment) const {
- T value = -infinity<T>();
+ T value = infinity<T>();
for (typename std::vector< Expression<T>* >::const_iterator it = args.begin();
it != args.end();
++it) {
@@ -47,6 +47,17 @@ struct Minimumm : public Operator<T> {
}
};
+template<typename T>
+struct Constant : public Operator<T> {
+ Constant(const T& val)
+ : _value(val) { }
+ T operator() (const std::vector< Expression<T>* >& args, const VariableAssignment<T>& ass) const {
+ return _value;
+ }
+ private:
+ const T _value;
+};
+
#include "VariableAssignment.hpp"
#include "Expression.hpp"
diff --git a/impl/Solver.hpp b/impl/Solver.hpp
new file mode 100644
index 0000000..11369bc
--- /dev/null
+++ b/impl/Solver.hpp
@@ -0,0 +1,17 @@
+#ifndef SOLVER_HPP
+#define SOLVER_HPP
+
+#include "Factory.hpp"
+#include "VariableAssignment.hpp"
+
+template<typename T>
+struct Solver {
+ VariableAssignment<T> solveBF(const EquationSystem<T>& system) {
+ VariableAssignment<T> result;
+ for (unsigned int i = 0; i < _var_count; ++i) {
+ result = system(result);
+ }
+ }
+};
+
+#endif
diff --git a/impl/Variable.hpp b/impl/Variable.hpp
index 0ba13e9..2386e7a 100644
--- a/impl/Variable.hpp
+++ b/impl/Variable.hpp
@@ -5,18 +5,19 @@
template<typename T>
struct Variable : public Operator<T> {
+ Variable(unsigned int id)
+ : _id(id) { }
+ Variable(const Variable& other)
+ : _id(other._id) { }
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;
+ const unsigned int _id;
};
#endif
diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp
index e41f3d8..a2d0afd 100644
--- a/impl/VariableAssignment.hpp
+++ b/impl/VariableAssignment.hpp
@@ -6,11 +6,36 @@
template<typename T>
struct VariableAssignment {
VariableAssignment(unsigned int length)
- : _length(length), _assignment(new T[length]) { }
+ : _length(length), _assignment(new T[length]) {
+ for (unsigned int i = 0; i < _length; ++i) {
+ _assignment[i] = -infinity<T>();
+ }
+ }
+ VariableAssignment(unsigned int length, const T& initial)
+ : _length(length), _assignment(new T[length]) {
+ for (unsigned int i = 0; i < _length; ++i) {
+ _assignment[i] = initial;
+ }
+ }
+ VariableAssignment(const VariableAssignment& other)
+ : _length(other._length), _assignment(new T[other._length]) {
+ for (unsigned int i = 0; i < _length; ++i) {
+ _assignment[i] = other._assignment[i];
+ }
+ }
~VariableAssignment() {
delete[] _assignment;
}
- const T& operator[] (const Variable<T> x) const {
+ VariableAssignment& operator=(const VariableAssignment& other) {
+ delete[] _assignment;
+ _length = other._length;
+ _assignment = new T[_length];
+ for (unsigned int i = 0; i < _length; ++i) {
+ _assignment[i] = other._assignment[i];
+ }
+ return *this;
+ }
+ const T& operator[] (const Variable<T>& x) const {
if (x.id() < 0 || x.id() >= _length) {
throw "Array out of bounds";
}
@@ -22,6 +47,21 @@ struct VariableAssignment {
}
return _assignment[x.id()];
}
+
+ VariableAssignment<T> expand(const VariableAssignment<T>& other) {
+ return expand(other, infinity<T>());
+ }
+ VariableAssignment<T> expand(const VariableAssignment<T>& other, const T& value) {
+ VariableAssignment<T> expansion(_length);
+ for (unsigned int i = 0; i < _length; ++i) {
+ if (_assignment[i] == other._assignment[i]) {
+ expansion._assignment[i] = _assignment[i];
+ } else {
+ expansion._assignment[i] = value;
+ }
+ }
+ return expansion;
+ }
private:
unsigned int _length;
T* _assignment;
diff --git a/impl/main.cpp b/impl/main.cpp
index 589a1e7..6f84cdd 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -4,6 +4,7 @@
#include "Operator.hpp"
#include "Expression.hpp"
+#include "EquationSystem.hpp"
#include "MaxStrategy.hpp"
using namespace std;
@@ -19,22 +20,28 @@ struct Complete {
std::vector< Expression<float>* > empty;
int main () {
- Variable<float> x;
- x.id(0);
- Variable<float> y;
- y.id(1);
+ EquationSystem<float> fac;
+ Variable<float>* x = fac.newVariable("x");
+ Variable<float>* y = fac.newVariable("y");
VariableAssignment<float> rho(2);
- rho[x] = 12;
- rho[y] = 10;
- Expression<float> expr(&x, empty);
+ 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);
+ args.push_back(new Expression<float>(x, empty));
+ args.push_back(new Expression<float>(y, empty));
+ args.push_back(new Expression<float>(new Constant<float>(10), empty));
+ MaxExpression<float>* maxExpression = fac.newMaxExpression(args);
+ Expression<float>* minExpression = new Expression<float>(new Minimum<float>(), args);
+
+
MaxStrategy<float> strat(1);
- strat[maxExpr] = 0;
- cout << strat(maxExpr,rho) << endl;
+ strat[*maxExpression] = 0;
+ cout << strat(*maxExpression,rho) << endl;
+
+ fac[*x] = minExpression;
+ fac[*y] = minExpression;
+ cout << fac.maxFixpoint()[*x] << endl;
return 0;
}
generated by cgit v1.2.3 (git 2.46.2) at 2024-12-24 17:58:55 +0000