From f09ce60d45d5524e36d07e76814b6e0cbc554288 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Mon, 28 May 2012 21:50:12 +1000 Subject: Fix issues with some things ignoring strategies. --- impl/EquationSystem.hpp | 2 +- impl/Expression.hpp | 15 ++++++++------ impl/MaxStrategy.hpp | 15 +++++++------- impl/Operator.hpp | 43 ++++++++++++++++++---------------------- impl/Variable.hpp | 4 +--- impl/main.cpp | 4 ++-- impl/systems/.long-fixpoint.swp | Bin 188416 -> 0 bytes impl/systems/long-fixpoint | 1 - 8 files changed, 39 insertions(+), 45 deletions(-) delete mode 100644 impl/systems/.long-fixpoint.swp diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp index 772ac37..13319e0 100644 --- a/impl/EquationSystem.hpp +++ b/impl/EquationSystem.hpp @@ -119,7 +119,7 @@ struct EquationSystem { VariableAssignment minFixpoint(const FixpointAlgorithm& algo) const { VariableAssignment rho = assignment(); - VariableAssignment lastRho = assignment(); + VariableAssignment lastRho(0); MaxStrategy strat = strategy(); do { lastRho = rho; diff --git a/impl/Expression.hpp b/impl/Expression.hpp index 4798e60..d3dfcf3 100644 --- a/impl/Expression.hpp +++ b/impl/Expression.hpp @@ -7,6 +7,8 @@ template struct Variable; +template +struct MaxStrategy; int ExpressionCount; @@ -22,9 +24,6 @@ struct Expression { virtual T operator() (const VariableAssignment& assignment) const { return (*_operator)(_arguments, assignment); } - virtual T operator() (const VariableAssignment& assignment, VariableSet* visited) const { - return (*_operator)(_arguments, assignment, visited); - } protected: Operator* _operator; std::vector< Expression* > _arguments; @@ -46,14 +45,17 @@ struct MaxExpression : public Expression { } return Expression::_arguments[i]; } - std::pair bestStrategy(const VariableAssignment& rho) const { + virtual T operator() (const VariableAssignment& assignment) const { + throw "error"; + } + std::pair bestStrategy(const VariableAssignment& rho, const MaxStrategy& strat) 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); + T value = strat(*Expression::_arguments[i], rho); if (value > best.first) best = std::pair(value, i); } - std::cerr << "Best strategy: (" << best.first << ", " << best.second << ")" << std::endl; + std::cerr << "Best strategy: (" << best.first << ", " << best.second << ")" << std::endl << std::endl; return best; } private: @@ -61,5 +63,6 @@ struct MaxExpression : public Expression { }; #include "Variable.hpp" +#include "MaxStrategy.hpp" #endif diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp index a1c50d8..aa49c9d 100644 --- a/impl/MaxStrategy.hpp +++ b/impl/MaxStrategy.hpp @@ -59,7 +59,7 @@ struct MaxStrategy { if (max == NULL) { return expr(rho); } else { - return (*max->argument(_assignment[max->id()]))(rho); + return (*this)(*max->argument(_assignment[max->id()]), rho); } } MaxStrategy improve(const EquationSystem& s, const VariableAssignment& rho) const { @@ -67,16 +67,15 @@ struct MaxStrategy { 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); + + // this relies on the fact that deeper MaxExpressions have a lower id + // than the MaxExpressions containing them. This means that we know that + // we have enough of a strategy to work with what we have within us + std::pair best = expr.bestStrategy(rho, newStrategy); + if (best.first > oldValue) newStrategy[expr] = best.second; } - std::cerr << "Strat improvement: "; - if (_length > 0) - std::cerr << newStrategy[*s.getMax(0)]; - else - std::cerr << "no max expressions"; - std::cerr << std::endl; return newStrategy; } diff --git a/impl/Operator.hpp b/impl/Operator.hpp index 80bc8b2..5f7cd1e 100644 --- a/impl/Operator.hpp +++ b/impl/Operator.hpp @@ -13,8 +13,6 @@ float infinity() { template struct Variable; -template -struct VariableSet : public IdSet > {}; template struct VariableAssignment; @@ -24,35 +22,32 @@ struct Expression; template struct Operator { virtual ~Operator() { } - T operator() (const std::vector< Expression* >& args, const VariableAssignment& rho) const { - return (*this)(args, rho, (VariableSet*) NULL); - } - virtual T operator() (const std::vector< Expression* >&, const VariableAssignment&, VariableSet*) const = 0; + virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& rho) const = 0; }; template struct Maximum : public Operator { - virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& assignment, VariableSet* visited) const { + virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& assignment) const { T value = -infinity(); for (typename std::vector< Expression* >::const_iterator it = args.begin(); it != args.end(); ++it) { - T temporary = (**it)(assignment, visited); - value = (temporary < value ? value : temporary); - if (value == infinity()) break; + T temporary = (**it)(assignment); + value = (temporary > value ? temporary : value); + //if (value == infinity()) break; } return value; } }; template struct Minimum : public Operator { - virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& assignment, VariableSet* visited) const { + virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& assignment) const { T value = infinity(); for (typename std::vector< Expression* >::const_iterator it = args.begin(); it != args.end(); ++it) { - T temporary = (**it)(assignment, visited); + T temporary = (**it)(assignment); value = (temporary < value ? temporary : value); - if (value == -infinity()) break; + //if (value == -infinity()) break; } return value; } @@ -62,7 +57,7 @@ template struct Constant : public Operator { Constant(const T& val) : _value(val) { } - T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass, VariableSet*) const { + T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { return _value; } private: @@ -71,10 +66,10 @@ struct Constant : public Operator { template struct Addition: public Operator { - T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass, VariableSet* visited) const { + T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { T sum = (*args[0])(ass); for (unsigned int i = 1, size = args.size(); i < size; ++i) { - sum += (*args[i])(ass, visited); + sum += (*args[i])(ass); } return sum; } @@ -82,10 +77,10 @@ struct Addition: public Operator { template struct Subtraction: public Operator { - T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass, VariableSet* visited) const { + T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { T sum = (*args[0])(ass); for (unsigned int i = 1, size = args.size(); i < size; ++i) { - sum -= (*args[i])(ass, visited); + sum -= (*args[i])(ass); } return sum; } @@ -93,24 +88,24 @@ struct Subtraction: public Operator { template struct Comma: public Operator { - T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass, VariableSet* visited) const { - if ((*args[0])(ass, visited) == -infinity()) { + T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { + if ((*args[0])(ass) == -infinity()) { std::cout << "Comma - neg inf" << std::endl; return -infinity(); } else { std::cout << "Comma - finite" << std::endl; - return (*args[1])(ass, visited); + return (*args[1])(ass); } } }; template struct Guard: public Operator { - T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass, VariableSet* visited) const { - if ((*args[0])(ass, visited) < (*args[1])(ass, visited)) { + T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { + if ((*args[0])(ass) < (*args[1])(ass)) { return -infinity(); } else { - return (*args[2])(ass, visited); + return (*args[2])(ass); } } }; diff --git a/impl/Variable.hpp b/impl/Variable.hpp index 5ebbbed..a174ea8 100644 --- a/impl/Variable.hpp +++ b/impl/Variable.hpp @@ -17,10 +17,8 @@ struct Variable : public Operator { return _name; } //T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { - virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& assignment, VariableSet* visited) const { + virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& assignment) const { //assert(args.size() == 0) - if (visited != NULL) - visited->insert(*this); return assignment[*this]; } private: diff --git a/impl/main.cpp b/impl/main.cpp index abd27ba..530556f 100644 --- a/impl/main.cpp +++ b/impl/main.cpp @@ -19,7 +19,7 @@ extern "C" { using namespace std; template -Expression* treeToExpression(pANTLR3_BASE_TREE node, EquationSystem& system, bool topLevel=true) { +Expression* treeToExpression(pANTLR3_BASE_TREE node, EquationSystem& system) { ANTLR3_UINT32 num = node->getChildCount(node); string name = (char*) node->getText(node)->chars; @@ -44,7 +44,7 @@ Expression* treeToExpression(pANTLR3_BASE_TREE node, EquationSystem& syste pANTLR3_BASE_TREE childNode; for (unsigned int i = 0; i < num; ++i) { childNode = (pANTLR3_BASE_TREE) node->getChild(node, i); - args.push_back(treeToExpression(childNode, system, false)); + args.push_back(treeToExpression(childNode, system)); } if (name == "max") { diff --git a/impl/systems/.long-fixpoint.swp b/impl/systems/.long-fixpoint.swp deleted file mode 100644 index 726d6ce..0000000 Binary files a/impl/systems/.long-fixpoint.swp and /dev/null differ diff --git a/impl/systems/long-fixpoint b/impl/systems/long-fixpoint index f56b700..5838910 100644 --- a/impl/systems/long-fixpoint +++ b/impl/systems/long-fixpoint @@ -98,7 +98,6 @@ x96 = x95 x97 = x96 x98 = x97 x99 = x98 -<<<<<<< HEAD x100 = x99 x101 = x100 x102 = x101 -- cgit v1.2.3