diff options
Diffstat (limited to 'impl')
-rw-r--r-- | impl/EquationSystem.hpp | 58 | ||||
-rw-r--r-- | impl/Expression.hpp | 22 | ||||
-rw-r--r-- | impl/ExpressionFactory.hpp | 12 | ||||
-rw-r--r-- | impl/MaxStrategy.hpp | 64 | ||||
-rw-r--r-- | impl/Operator.hpp | 7 | ||||
-rw-r--r-- | impl/VariableAssignment.hpp | 18 | ||||
-rw-r--r-- | impl/main.cpp | 48 |
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; } |