summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--impl/EquationSystem.hpp58
-rw-r--r--impl/Expression.hpp22
-rw-r--r--impl/ExpressionFactory.hpp12
-rw-r--r--impl/MaxStrategy.hpp64
-rw-r--r--impl/Operator.hpp7
-rw-r--r--impl/VariableAssignment.hpp18
-rw-r--r--impl/main.cpp48
7 files changed, 184 insertions, 45 deletions
diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp
index 065a1a2..adc608b 100644
--- a/impl/EquationSystem.hpp
+++ b/impl/EquationSystem.hpp
@@ -2,11 +2,11 @@
#define EQUATION_SYSTEM_HPP
#include "Expression.hpp"
+template<typename T>
+struct MaxStrategy;
template<typename T>
struct EquationSystem {
- EquationSystem ()
- : _max_id(0) { }
virtual ~EquationSystem() {
for (int i = 0, size = _vars.size(); i < size; ++i) {
delete _vars[i];
@@ -19,13 +19,26 @@ struct EquationSystem {
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++);
+ expr->id(_max_expressions.size());
+ _max_expressions.push_back(expr);
return expr;
}
unsigned int maxCount() const {
- return _max_id;
+ return _max_expressions.count();
+ }
+ const MaxExpression<T>* getMax(unsigned int i) const {
+ return _max_expressions[i];
+ }
+
+ MaxStrategy<T> strategy() const {
+ return MaxStrategy<T>(_max_expressions.size());
+ }
+
+ VariableAssignment<T> assignment() const {
+ return VariableAssignment<T>(_vars.size());
}
Expression<T>*& operator[] (const Variable<T>& v) {
@@ -42,14 +55,15 @@ struct EquationSystem {
}
template<typename F>
- VariableAssignment<T> foreach(F op, const VariableAssignment<T>& v) {
+ VariableAssignment<T> foreach(F op, const VariableAssignment<T>& rho) const {
VariableAssignment<T> result(_vars.size());
for (unsigned int i = 0, size = _vars.size(); i < size; ++i) {
- result[_vars[i]] = op(_expressions[i], v);
+ result[*_vars[i]] = op(*_expressions[i], rho);
}
+ return result;
}
- VariableAssignment<T> operator() (const VariableAssignment<T>& rho) {
+ VariableAssignment<T> operator() (const VariableAssignment<T>& rho) const {
VariableAssignment<T> result(_vars.size());
for (unsigned int i = 0, size = _vars.size(); i < size; ++i) {
result[*_vars[i]] = (*_expressions[i])(rho);
@@ -57,7 +71,7 @@ struct EquationSystem {
return result;
}
- VariableAssignment<T> maxFixpoint() {
+ VariableAssignment<T> maxFixpoint() const {
unsigned int size = _vars.size();
VariableAssignment<T> result(size, infinity<T>());
for (unsigned int i = 0; i < size; ++i) {
@@ -69,11 +83,37 @@ struct EquationSystem {
}
return result;
}
+
+ VariableAssignment<T> maxFixpoint(const MaxStrategy<T>& strat) const {
+ unsigned int size = _vars.size();
+ VariableAssignment<T> result(size, infinity<T>());
+ for (unsigned int i = 0; i < size; ++i) {
+ result = strat(*this, result);
+ }
+ result = result.expand(strat(*this, result), -infinity<T>());
+ for (unsigned int i = 0; i < size-1; ++i) {
+ result = strat(*this, result);
+ }
+ return result;
+ }
+
+ VariableAssignment<T> minFixpoint() const {
+ VariableAssignment<T> rho = assignment();
+ VariableAssignment<T> lastRho = assignment();
+ MaxStrategy<T> strat = strategy();
+ do {
+ lastRho = rho;
+ strat = strat.improve(*this, rho);
+ rho = maxFixpoint(strat);
+ } while(lastRho != rho);
+ return rho;
+ }
private:
- unsigned int _max_id;
std::vector<Variable<T>*> _vars;
+ std::vector<MaxExpression<T>*> _max_expressions;
std::vector<Expression<T>*> _expressions;
};
+#include "MaxStrategy.hpp"
#endif
diff --git a/impl/Expression.hpp b/impl/Expression.hpp
index 46ccf23..7b157c2 100644
--- a/impl/Expression.hpp
+++ b/impl/Expression.hpp
@@ -1,6 +1,7 @@
#ifndef EXPRESSION_HPP
#define EXPRESSION_HPP
+//#include <pair>
#include "VariableAssignment.hpp"
#include "Operator.hpp"
@@ -16,13 +17,10 @@ struct Expression {
delete *it;
}*/
}
- const std::vector<Expression<T>*>& arguments() const {
- return _arguments;
- }
virtual T operator() (const VariableAssignment<T>& assignment) const {
return (*_operator)(_arguments, assignment);
}
- private:
+ protected:
Operator<T>* _operator;
std::vector< Expression<T>* > _arguments;
};
@@ -37,6 +35,22 @@ struct MaxExpression : public Expression<T> {
unsigned int id(unsigned int id) {
return (_id = id);
}
+ Expression<T>* argument(unsigned int i) const {
+ if (i >= Expression<T>::_arguments.size()) {
+ throw "Error";
+ }
+ return Expression<T>::_arguments[i];
+ }
+ std::pair<T, unsigned int> bestStrategy(const VariableAssignment<T>& rho) const {
+ std::pair<T, unsigned int> best = std::pair<T, unsigned int>(-infinity<T>(), 0);
+ for (unsigned int i = 0, size = Expression<T>::_arguments.size(); i < size; ++i) {
+ T value = (*Expression<T>::_arguments[i])(rho);
+ if (value > best.first)
+ best = std::pair<T, unsigned int>(value, i);
+ }
+ std::cout << "Best strategy: (" << best.first << ", " << best.second << ")" << std::endl;
+ return best;
+ }
private:
unsigned int _id;
};
diff --git a/impl/ExpressionFactory.hpp b/impl/ExpressionFactory.hpp
new file mode 100644
index 0000000..0eb7268
--- /dev/null
+++ b/impl/ExpressionFactory.hpp
@@ -0,0 +1,12 @@
+#ifndef EXPRESSION_FACTORY_HPP
+#define EXPRESSION_FACTORY_HPP
+
+template<typename T>
+struct ExpressionFactory {
+ ExpressionFactory() : _count(0) { }
+
+ private:
+ unsigned int _count;
+};
+
+#endif
diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp
index 7a37fb2..e52fd99 100644
--- a/impl/MaxStrategy.hpp
+++ b/impl/MaxStrategy.hpp
@@ -2,39 +2,89 @@
#define MAX_STRATEGY_HPP
#include "Expression.hpp"
+#include "EquationSystem.hpp"
#include "VariableAssignment.hpp"
template<typename T>
struct MaxStrategy {
+ MaxStrategy()
+ : _length(0), _assignment(NULL) { }
MaxStrategy(unsigned int length)
- : _length(length), _assignment(new unsigned int[length]) { }
+ : _length(length), _assignment(new unsigned int[length]) {
+ for (unsigned int i = 0; i < length; ++i) {
+ _assignment[i] = 0;
+ }
+ }
+ MaxStrategy(const MaxStrategy& other)
+ : _length(other._length), _assignment(new unsigned int[other._length]) {
+ for (unsigned int i = 0; i < other._length; ++i) {
+ _assignment[i] = other._assignment[i];
+ }
+ }
+
+ MaxStrategy<T>& operator=(const MaxStrategy& other) {
+ if (_length != other._length) {
+ _length = other._length;
+ delete[] _assignment;
+ _assignment = new unsigned int[_length];
+ }
+ for (unsigned int i = 0; i < _length; ++i) {
+ _assignment[i] = other._assignment[i];
+ }
+ return *this;
+ }
+
virtual ~MaxStrategy() {
delete[] _assignment;
}
const unsigned int& operator[] (const MaxExpression<T> x) const {
- if (x.id() < 0 || x.id() >= _length) {
+ if (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) {
+ if (x.id() >= _length) {
throw "Array out of bounds";
}
return _assignment[x.id()];
}
- T operator() (const EquationSystem<T>& eqns, const VariableAssignment<T>& rho) const {
- return eqns.foreach((*this), rho);
+ VariableAssignment<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) {
return expr(rho);
} else {
- return (*expr.arguments()[_assignment[max->id()]])(rho);
+ return (*max->argument(_assignment[max->id()]))(rho);
+ }
+ }
+ MaxStrategy<T> improve(const EquationSystem<T>& s, const VariableAssignment<T>& rho) const {
+ MaxStrategy<T> newStrategy(*this);
+ for (unsigned int i = 0; i < _length; ++i) {
+ const MaxExpression<T>* expr = s.getMax(i);
+ const T oldValue = (*this)(*expr, rho);
+ std::pair<const T,unsigned int> best = expr->bestStrategy(rho);
+ if (best.first > oldValue)
+ newStrategy[*expr] = best.second;
+ }
+ std::cout << "Strat improvement: " << newStrategy[*s.getMax(0)] << std::endl;
+ return newStrategy;
+ }
+
+ bool operator== (const MaxStrategy& other) const {
+ if (_length != other._length)
+ return false;
+ for (unsigned int i = 0; i < _length; ++i) {
+ if (_assignment[i] != other._assignment[i]) {
+ return false;
+ }
}
+ return true;
}
- MaxStrategy<T> improve() {
+ bool operator!= (const MaxStrategy& other) const {
+ return !(*this == other);
}
private:
unsigned int _length;
diff --git a/impl/Operator.hpp b/impl/Operator.hpp
index 3e11443..71a1e68 100644
--- a/impl/Operator.hpp
+++ b/impl/Operator.hpp
@@ -58,6 +58,13 @@ struct Constant : public Operator<T> {
const T _value;
};
+template<typename T>
+struct Increment: public Operator<T> {
+ T operator() (const std::vector< Expression<T>* >& args, const VariableAssignment<T>& ass) const {
+ return (*args[0])(ass) + 1;
+ }
+};
+
#include "VariableAssignment.hpp"
#include "Expression.hpp"
diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp
index a2d0afd..c0c7148 100644
--- a/impl/VariableAssignment.hpp
+++ b/impl/VariableAssignment.hpp
@@ -36,13 +36,13 @@ struct VariableAssignment {
return *this;
}
const T& operator[] (const Variable<T>& x) const {
- if (x.id() < 0 || x.id() >= _length) {
+ if (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) {
+ if (x.id() >= _length) {
throw "Array out of bounds";
}
return _assignment[x.id()];
@@ -62,6 +62,20 @@ struct VariableAssignment {
}
return expansion;
}
+
+ bool operator==(const VariableAssignment& other) const {
+ if (_length != other._length)
+ return false;
+ for (unsigned int i = 0; i < _length; ++i) {
+ if (_assignment[i] != other._assignment[i]) {
+ return false;
+ }
+ }
+ return true;
+ }
+ bool operator!=(const VariableAssignment& other) const {
+ return !(*this == other);
+ }
private:
unsigned int _length;
T* _assignment;
diff --git a/impl/main.cpp b/impl/main.cpp
index 6f84cdd..579db25 100644
--- a/impl/main.cpp
+++ b/impl/main.cpp
@@ -18,30 +18,32 @@ struct Complete {
T _value;
};*/
+typedef std::vector<Expression<float>*> Args;
+typedef Expression<float> E;
+typedef Constant<float> C;
+typedef Minimum<float> Min;
+
std::vector< Expression<float>* > empty;
int main () {
- 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);
-
- std::vector<Expression<float>*> args;
- 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[*maxExpression] = 0;
- cout << strat(*maxExpression,rho) << endl;
-
- fac[*x] = minExpression;
- fac[*y] = minExpression;
- cout << fac.maxFixpoint()[*x] << endl;
+ EquationSystem<float> sys;
+ Variable<float>* x = sys.newVariable("x");
+
+ Args incArgs;
+ incArgs.push_back(new E(x, empty));
+
+ Args minArgs;
+ minArgs.push_back(new E(new Increment<float>, incArgs));
+ minArgs.push_back(new E(new C(100), empty));
+
+ Args maxArgs;
+ maxArgs.push_back(new E(new C(0), empty));
+ maxArgs.push_back(new E(new Min(), minArgs));
+
+ sys[*x] = sys.newMaxExpression(maxArgs);
+ // x = max(0, min(x+1, 100))
+
+ cout << sys.minFixpoint()[*x] << endl;
+ // -> 100, as expected
+
return 0;
}
generated by cgit v1.2.3 (git 2.46.2) at 2024-12-25 06:24:11 +0000