From fd6bc1887fecca5338e7d5660d56a4038c805d96 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Tue, 29 May 2012 23:34:24 +1000 Subject: Range stuff better, RecursiveFixpoint broken. --- impl/Complete.hpp | 2 +- impl/Expression.hpp | 25 +++++++++++++++++++++++-- impl/Operator.hpp | 23 ++++++++++++++--------- impl/Variable.hpp | 4 ++-- impl/main.cpp | 47 ++++++++++++++++++++++++++++++++++++----------- impl/systems/basic-range | 2 ++ 6 files changed, 78 insertions(+), 25 deletions(-) create mode 100644 impl/systems/basic-range diff --git a/impl/Complete.hpp b/impl/Complete.hpp index 1cf40af..64b850a 100644 --- a/impl/Complete.hpp +++ b/impl/Complete.hpp @@ -69,7 +69,7 @@ struct Complete { } } bool operator>(const Complete& other) const { - return !(*this < other || *this == other); + return other < *this; } bool operator==(const Complete& other) const { if (_infinity) { diff --git a/impl/Expression.hpp b/impl/Expression.hpp index d3dfcf3..3c84d30 100644 --- a/impl/Expression.hpp +++ b/impl/Expression.hpp @@ -24,6 +24,10 @@ struct Expression { virtual T operator() (const VariableAssignment& assignment) const { return (*_operator)(_arguments, assignment); } + + template + friend std::ostream& operator<<(std::ostream&, const Expression&); + protected: Operator* _operator; std::vector< Expression* > _arguments; @@ -52,16 +56,33 @@ struct MaxExpression : public Expression { std::pair best = std::pair(-infinity(), 0); for (unsigned int i = 0, size = Expression::_arguments.size(); i < size; ++i) { T value = strat(*Expression::_arguments[i], rho); - if (value > best.first) + if (best.first < value) best = std::pair(value, i); } - std::cerr << "Best strategy: (" << best.first << ", " << best.second << ")" << std::endl << std::endl; + std::cerr << "Best strategy: (" << best.first << ", " << best.second << ")" << std::endl; return best; } private: unsigned int _id; }; +template +std::ostream& operator<<(std::ostream& cout, const Expression& expr) { + if (expr._arguments.size() == 0) { + cout << expr._operator->op_name; + } else { + cout << expr._operator->op_name << "("; + for (typename std::vector*>::const_iterator it = expr._arguments.begin(); + it != expr._arguments.end(); + ++it) { + cout << (it == expr._arguments.begin() ? "" : ", "); + cout << **it; + } + cout << ")"; + } + return cout; +} + #include "Variable.hpp" #include "MaxStrategy.hpp" diff --git a/impl/Operator.hpp b/impl/Operator.hpp index 5f7cd1e..87e4eea 100644 --- a/impl/Operator.hpp +++ b/impl/Operator.hpp @@ -21,18 +21,21 @@ struct Expression; template struct Operator { + Operator(const std::string& name) : op_name(name) { } virtual ~Operator() { } virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& rho) const = 0; + const std::string op_name; }; template struct Maximum : public Operator { + Maximum() : Operator("max") { } 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); - value = (temporary > value ? temporary : value); + value = (value < temporary ? value : temporary); //if (value == infinity()) break; } return value; @@ -40,6 +43,7 @@ struct Maximum : public Operator { }; template struct Minimum : public Operator { + Minimum() : Operator("min") { } 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(); @@ -55,8 +59,8 @@ struct Minimum : public Operator { template struct Constant : public Operator { - Constant(const T& val) - : _value(val) { } + Constant(const std::string& value, const T& val) + : Operator(value), _value(val) { } T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { return _value; } @@ -66,6 +70,7 @@ struct Constant : public Operator { template struct Addition: public Operator { + Addition() : Operator("add") { } 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) { @@ -76,18 +81,17 @@ struct Addition: public Operator { }; template -struct Subtraction: public Operator { +struct Negate: public Operator { + Negate() : Operator("neg") { } 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); - } - return sum; + // assert(args.size() == 1); + return -(*args[0])(ass); } }; template struct Comma: public Operator { + Comma() : Operator("comma") { } T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { if ((*args[0])(ass) == -infinity()) { std::cout << "Comma - neg inf" << std::endl; @@ -101,6 +105,7 @@ struct Comma: public Operator { template struct Guard: public Operator { + Guard() : Operator("guard") { } T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { if ((*args[0])(ass) < (*args[1])(ass)) { return -infinity(); diff --git a/impl/Variable.hpp b/impl/Variable.hpp index a174ea8..35a3991 100644 --- a/impl/Variable.hpp +++ b/impl/Variable.hpp @@ -7,9 +7,9 @@ template struct Variable : public Operator { Variable(unsigned int id, const std::string& name) - : _id(id), _name(name) { } + : Operator(name), _id(id), _name(name) { } Variable(const Variable& other) - : _id(other._id) { } + : Operator(name), _id(other._id) { } unsigned int id() const { return _id; } diff --git a/impl/main.cpp b/impl/main.cpp index 21be64b..2006565 100644 --- a/impl/main.cpp +++ b/impl/main.cpp @@ -26,9 +26,21 @@ std::pair*, Expression*> treeToExpression(pANTLR3_BASE_TREE nod // leaf node - variable if (num == 0) { - return std::pair*, Expression*>( - system.newExpression(system.newVariable(name + "_l")), - system.newExpression(system.newVariable(name + "_u"))); + if (negative) { + vector*> firstArgs; + firstArgs.push_back(system.newExpression(system.newVariable(name + "_u"))); + vector*> secondArgs; + secondArgs.push_back(system.newExpression(system.newVariable(name + "_l"))); + return std::pair*, Expression*>( + system.newExpression(new Negate(), + firstArgs), + system.newExpression(new Negate(), + secondArgs)); + } else { + return std::pair*, Expression*>( + system.newExpression(system.newVariable(name + "_l")), + system.newExpression(system.newVariable(name + "_u"))); + } } // a range itself @@ -43,7 +55,7 @@ std::pair*, Expression*> treeToExpression(pANTLR3_BASE_TREE nod if (!(firstStream >> firstValue)) { throw "Invalid number."; } - if (negative) firstValue = -firstValue; + string firstChildName = childName; childNode = (pANTLR3_BASE_TREE) node->getChild(node, 1); childName = (char*) childNode->getText(childNode)->chars; @@ -51,11 +63,22 @@ std::pair*, Expression*> treeToExpression(pANTLR3_BASE_TREE nod if (!(secondStream >> secondValue)) { throw "Invalid number."; } - if (negative) secondValue = -secondValue; + string secondChildName = childName; + + if (negative) { + T temp = firstValue; + string tempname = firstChildName; + + firstValue = -secondValue; + firstChildName = "-" + secondChildName; + + secondValue = -temp; + secondChildName = "-" + tempname; + } return std::pair*, Expression*>( - system.newExpression(new Constant(firstValue)), - system.newExpression(new Constant(secondValue))); + system.newExpression(new Constant(firstChildName, firstValue)), + system.newExpression(new Constant(secondChildName, secondValue))); } if (name == "-") { @@ -77,8 +100,8 @@ std::pair*, Expression*> treeToExpression(pANTLR3_BASE_TREE nod if (name == "-") { //if (firstArgs.size() == 1) { // secondArgs.size() == firstArgs.size() return std::pair*, Expression*>( - secondArgs[0], - firstArgs[0]); + firstArgs[0], + secondArgs[0]); } if (name == "max") { @@ -132,15 +155,17 @@ void treeToSystem(pANTLR3_BASE_TREE node, EquationSystem& system) { std::pair*, Expression*> exprs = treeToExpression(exprNode, system); var = system.newVariable(varName + "_l"); - args.push_back(system.newExpression(new Constant(-infinity()))); + args.push_back(system.newExpression(new Constant("-inf", -infinity()))); args.push_back(exprs.first); system[*var] = system.newMaxExpression(args); + std::cout << var->op_name << " = " << *system[*var] << std::endl; args.clear(); var = system.newVariable(varName + "_u"); - args.push_back(system.newExpression(new Constant(-infinity()))); + args.push_back(system.newExpression(new Constant("-inf", -infinity()))); args.push_back(exprs.second); system[*var] = system.newMaxExpression(args); + std::cout << var->op_name << " = " << *system[*var] << std::endl; } } diff --git a/impl/systems/basic-range b/impl/systems/basic-range new file mode 100644 index 0000000..c6bf8fa --- /dev/null +++ b/impl/systems/basic-range @@ -0,0 +1,2 @@ +x = [0, 1] +y = -[0, 1] -- cgit v1.2.3