From e00c1e3f71bb1840e10a85af53469a81c73c7ef1 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Mon, 30 Apr 2012 21:17:07 +1000 Subject: Functional algorithm. Unoptimised. --- impl/EquationSystem.hpp | 58 +++++++++++++++++++++++++++++++++------- impl/Expression.hpp | 22 +++++++++++++--- impl/ExpressionFactory.hpp | 12 +++++++++ impl/MaxStrategy.hpp | 64 ++++++++++++++++++++++++++++++++++++++++----- impl/Operator.hpp | 7 +++++ impl/VariableAssignment.hpp | 18 +++++++++++-- impl/main.cpp | 48 ++++++++++++++++++---------------- 7 files changed, 184 insertions(+), 45 deletions(-) create mode 100644 impl/ExpressionFactory.hpp 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 +struct MaxStrategy; template 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* newMaxExpression(const std::vector*>& args) { MaxExpression* expr = new MaxExpression(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* getMax(unsigned int i) const { + return _max_expressions[i]; + } + + MaxStrategy strategy() const { + return MaxStrategy(_max_expressions.size()); + } + + VariableAssignment assignment() const { + return VariableAssignment(_vars.size()); } Expression*& operator[] (const Variable& v) { @@ -42,14 +55,15 @@ struct EquationSystem { } template - VariableAssignment foreach(F op, const VariableAssignment& v) { + VariableAssignment foreach(F op, const VariableAssignment& rho) const { VariableAssignment 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 operator() (const VariableAssignment& rho) { + VariableAssignment operator() (const VariableAssignment& rho) const { VariableAssignment 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 maxFixpoint() { + VariableAssignment maxFixpoint() const { unsigned int size = _vars.size(); VariableAssignment result(size, infinity()); for (unsigned int i = 0; i < size; ++i) { @@ -69,11 +83,37 @@ struct EquationSystem { } return result; } + + VariableAssignment maxFixpoint(const MaxStrategy& strat) const { + unsigned int size = _vars.size(); + VariableAssignment result(size, infinity()); + for (unsigned int i = 0; i < size; ++i) { + result = strat(*this, result); + } + result = result.expand(strat(*this, result), -infinity()); + for (unsigned int i = 0; i < size-1; ++i) { + result = strat(*this, result); + } + return result; + } + + VariableAssignment minFixpoint() const { + VariableAssignment rho = assignment(); + VariableAssignment lastRho = assignment(); + MaxStrategy 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*> _vars; + std::vector*> _max_expressions; std::vector*> _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 #include "VariableAssignment.hpp" #include "Operator.hpp" @@ -16,13 +17,10 @@ struct Expression { delete *it; }*/ } - const std::vector*>& arguments() const { - return _arguments; - } virtual T operator() (const VariableAssignment& assignment) const { return (*_operator)(_arguments, assignment); } - private: + protected: Operator* _operator; std::vector< Expression* > _arguments; }; @@ -37,6 +35,22 @@ struct MaxExpression : public Expression { unsigned int id(unsigned int id) { return (_id = id); } + Expression* argument(unsigned int i) const { + if (i >= Expression::_arguments.size()) { + throw "Error"; + } + return Expression::_arguments[i]; + } + std::pair bestStrategy(const VariableAssignment& rho) const { + std::pair best = std::pair(-infinity(), 0); + for (unsigned int i = 0, size = Expression::_arguments.size(); i < size; ++i) { + T value = (*Expression::_arguments[i])(rho); + if (value > best.first) + best = std::pair(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 +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 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& 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 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& 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& eqns, const VariableAssignment& rho) const { - return eqns.foreach((*this), rho); + VariableAssignment operator() (const EquationSystem& eqns, const VariableAssignment& rho) const { + return eqns.foreach(*this, rho); } T operator() (const Expression& expr, const VariableAssignment& rho) const { const MaxExpression* max = dynamic_cast*>(&expr); if (max == NULL) { return expr(rho); } else { - return (*expr.arguments()[_assignment[max->id()]])(rho); + return (*max->argument(_assignment[max->id()]))(rho); + } + } + MaxStrategy improve(const EquationSystem& s, const VariableAssignment& rho) const { + MaxStrategy newStrategy(*this); + for (unsigned int i = 0; i < _length; ++i) { + const MaxExpression* expr = s.getMax(i); + const T oldValue = (*this)(*expr, rho); + std::pair 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 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 { const T _value; }; +template +struct Increment: public Operator { + T operator() (const std::vector< Expression* >& args, const VariableAssignment& 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& 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& 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*> Args; +typedef Expression E; +typedef Constant C; +typedef Minimum Min; + std::vector< Expression* > empty; int main () { - EquationSystem fac; - Variable* x = fac.newVariable("x"); - Variable* y = fac.newVariable("y"); - VariableAssignment rho(2); - rho[*x] = 12; - rho[*y] = 10; - Expression expr(x, empty); - - std::vector*> args; - args.push_back(new Expression(x, empty)); - args.push_back(new Expression(y, empty)); - args.push_back(new Expression(new Constant(10), empty)); - MaxExpression* maxExpression = fac.newMaxExpression(args); - Expression* minExpression = new Expression(new Minimum(), args); - - - MaxStrategy strat(1); - strat[*maxExpression] = 0; - cout << strat(*maxExpression,rho) << endl; - - fac[*x] = minExpression; - fac[*y] = minExpression; - cout << fac.maxFixpoint()[*x] << endl; + EquationSystem sys; + Variable* x = sys.newVariable("x"); + + Args incArgs; + incArgs.push_back(new E(x, empty)); + + Args minArgs; + minArgs.push_back(new E(new Increment, 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; } -- cgit v1.2.3