diff options
Diffstat (limited to 'src/libvpsc/constraint.cpp')
| -rw-r--r-- | src/libvpsc/constraint.cpp | 218 |
1 files changed, 0 insertions, 218 deletions
diff --git a/src/libvpsc/constraint.cpp b/src/libvpsc/constraint.cpp deleted file mode 100644 index f1b7f0571..000000000 --- a/src/libvpsc/constraint.cpp +++ /dev/null @@ -1,218 +0,0 @@ -/* - * vim: ts=4 sw=4 et tw=0 wm=0 - * - * libvpsc - A solver for the problem of Variable Placement with - * Separation Constraints. - * - * Copyright (C) 2005-2008 Monash University - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * See the file LICENSE.LGPL distributed with the library. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. - * - * Author(s): Tim Dwyer -*/ - - -#include <map> -#include <list> -#include <sstream> -#include <cassert> -#include <cfloat> -#include <cmath> - - -#include "libvpsc/constraint.h" -#include "libvpsc/variable.h" - -namespace vpsc { -Constraint::Constraint(Variable *left, Variable *right, double gap, bool equality) -: left(left), - right(right), - gap(gap), - timeStamp(0), - active(false), - equality(equality), - unsatisfiable(false), - needsScaling(true), - creator(NULL) -{ - // In hindsight I think it's probably better to build the constraint DAG - // (by creating variable in/out lists) when needed, rather than in advance - //left->out.push_back(this); - //right->in.push_back(this); -} -Constraint::~Constraint() { - // see constructor: the following is just way too slow. - // Better to create a - // new DAG on demand than maintain the lists dynamically. - //Constraints::iterator i; - //for(i=left->out.begin(); i!=left->out.end(); i++) { - //if(*i==this) break; - //} - //left->out.erase(i); - //for(i=right->in.begin(); i!=right->in.end(); i++) { - //if(*i==this) break; - //} - //right->in.erase(i); -} -std::ostream& operator <<(std::ostream &os, const Constraint &c) -{ - const char *type = c.equality ? "=" : "<="; - std::ostringstream lscale, rscale; - if (c.left->scale != 1) - { - lscale << c.left->scale << "*"; - } - if (c.right->scale != 1) - { - rscale << c.right->scale << "*"; - } - os << lscale.str() << *c.left << "+" << c.gap << type << - rscale.str() << *c.right; - if (c.left->block && c.right->block) - { - os << "(" << c.slack() << ")" << (c.active ? "-active" : "") << - "(lm=" << c.lm << ")"; - } - else - { - os << "(vars have no position)"; - } - return os; -} -#include "libvpsc/block.h" -bool CompareConstraints::operator() ( - Constraint *const &l, Constraint *const &r -) const { - double const sl = - l->left->block->timeStamp > l->timeStamp - ||l->left->block==l->right->block - ?-DBL_MAX:l->slack(); - double const sr = - r->left->block->timeStamp > r->timeStamp - ||r->left->block==r->right->block - ?-DBL_MAX:r->slack(); - if(sl==sr) { - // arbitrary choice based on id - if(l->left->id==r->left->id) { - if(l->right->id<r->right->id) return true; - return false; - } - if(l->left->id<r->left->id) return true; - return false; - } - return sl < sr; -} - - -typedef std::list<std::map<Variable *, double> > VarOffsetMapList; - -class EqualityConstraintSet -{ - public: - EqualityConstraintSet(Variables vs) - { - for (size_t i = 0; i < vs.size(); ++i) - { - std::map<Variable *, double> varSet; - varSet[vs[i]] = 0; - variableGroups.push_back(varSet); - } - } - bool isRedundant(Variable *lhs, Variable *rhs, double sep) - { - VarOffsetMapList::iterator lhsSet = setForVar(lhs); - VarOffsetMapList::iterator rhsSet = setForVar(rhs); - COLA_ASSERT(lhsSet != variableGroups.end()); - COLA_ASSERT(rhsSet != variableGroups.end()); - if (lhsSet == rhsSet) - { - // Check if this is a redundant constraint. - if (fabs(((*lhsSet)[lhs] + sep) - (*rhsSet)[rhs]) < 0.0001) - { - // If so, return true. - return true; - } - } - return false; - } - void mergeSets(Variable *lhs, Variable *rhs, double sep) - { - VarOffsetMapList::iterator lhsSet = setForVar(lhs); - VarOffsetMapList::iterator rhsSet = setForVar(rhs); - if (lhsSet == rhsSet) - { - return; - } - - double rhsOldOffset = (*rhsSet)[rhs]; - double rhsNewOffset = (*lhsSet)[lhs] + sep; - double offset = rhsNewOffset - rhsOldOffset; - - // Update offsets - for (std::map<Variable *, double>::iterator it = rhsSet->begin(); - it != rhsSet->end(); ++it) - { - it->second += offset; - } - - // Merge rhsSet into lhsSet - lhsSet->insert(rhsSet->begin(), rhsSet->end()); - variableGroups.erase(rhsSet); - } - - private: - VarOffsetMapList::iterator setForVar(Variable *var) - { - for (VarOffsetMapList::iterator it = variableGroups.begin(); - it != variableGroups.end(); ++it) - { - if (it->find(var) != it->end()) - { - return it; - } - } - return variableGroups.end(); - } - - VarOffsetMapList variableGroups; -}; - -Constraints constraintsRemovingRedundantEqualities(const Variables& vars, - const Constraints& constraints) -{ - EqualityConstraintSet equalitySets(vars); - Constraints cs = Constraints(constraints.size()); - int csSize = 0; - - for (unsigned i = 0; i < constraints.size(); ++i) - { - Constraint *c = constraints[i]; - if (c->equality) - { - if (!equalitySets.isRedundant(c->left, c->right, c->gap)) - { - // Only add non-redundant equalities - equalitySets.mergeSets(c->left, c->right, c->gap); - cs[csSize++] = c; - } - } - else - { - // Add all non-equalities - cs[csSize++] = c; - } - } - cs.resize(csSize); - return cs; -} - - -} |