From ab5f8ff5869021958f4ae8b838c3d707a2e85eaa Mon Sep 17 00:00:00 2001 From: Marc Jeanmougin Date: Sun, 29 Apr 2018 16:25:32 +0200 Subject: Put adaptagrams into its own folder --- src/libcola/compound_constraints.cpp | 1671 ---------------------------------- 1 file changed, 1671 deletions(-) delete mode 100644 src/libcola/compound_constraints.cpp (limited to 'src/libcola/compound_constraints.cpp') diff --git a/src/libcola/compound_constraints.cpp b/src/libcola/compound_constraints.cpp deleted file mode 100644 index e4552e606..000000000 --- a/src/libcola/compound_constraints.cpp +++ /dev/null @@ -1,1671 +0,0 @@ -/* - * vim: ts=4 sw=4 et tw=0 wm=0 - * - * libcola - A library providing force-directed network layout using the - * stress-majorization method subject to separation constraints. - * - * Copyright (C) 2006-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 - * Michael Wybrow -*/ - -#include -#include -#include - -#include -#include -#include - -#include "libcola/cola.h" -#include "libcola/compound_constraints.h" -#include "libcola/exceptions.h" - -using std::vector; -using vpsc::XDIM; -using vpsc::YDIM; - -namespace cola { - -void SubConstraintInfo::updateVarIDsWithMapping( - const VariableIDMap& idMap, bool forward) -{ - varIndex = idMap.mappingForVariable(varIndex, forward); -} - -//----------------------------------------------------------------------------- -// BoundaryConstraint code -//----------------------------------------------------------------------------- - -class Offset : public SubConstraintInfo -{ - public: - Offset(unsigned ind, double offset) : - SubConstraintInfo(ind), - distOffset(offset) - { - } - double distOffset; -}; - - -BoundaryConstraint::BoundaryConstraint(const vpsc::Dim dim) - : CompoundConstraint(dim), - position(0), - variable(NULL) -{ -} - - -void BoundaryConstraint::updatePosition(const vpsc::Dim dim) -{ - if (dim == _primaryDim) - { - position = variable->finalPosition; - } -} - - -void BoundaryConstraint::addShape(const unsigned int index, - const double offset) -{ - _subConstraintInfo.push_back(new Offset(index, offset)); -} - - -void BoundaryConstraint::printCreationCode(FILE *fp) const -{ - fprintf(fp, " BoundaryConstraint *boundary%llu = " - "new BoundaryConstraint(vpsc::%cDIM);\n", - (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y'); - for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - Offset *info = static_cast (*o); - fprintf(fp, " boundary%llu->addShape(%u, %g);\n", - (unsigned long long) this, info->varIndex, info->distOffset); - } - fprintf(fp, " ccs.push_back(boundary%llu);\n\n", - (unsigned long long) this); -} - - -std::string BoundaryConstraint::toString(void) const -{ - std::ostringstream stream; - stream << "BoundaryConstraint("; - stream << "dim: " << ((_primaryDim == 0) ? 'X' : 'Y'); - stream << "): {"; - bool first = true; - for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - Offset *info = static_cast (*o); - if (!first) - { - stream << ", "; - } - stream << "(" << "rect: " << info->varIndex << ", offset: " << info->distOffset << ")"; - first = false; - } - stream << "}"; - return stream.str(); -} - - -void BoundaryConstraint::generateVariables(const vpsc::Dim dim, - vpsc::Variables& vars) -{ - if (dim == _primaryDim) - { - // Just one variable is generated, associated with the position - // of the boundary. This variable can float freely. - variable = new vpsc::Variable(vars.size(), position, freeWeight); - vars.push_back(variable); - } -} - - -void BoundaryConstraint::generateSeparationConstraints(const vpsc::Dim dim, - vpsc::Variables& vars, vpsc::Constraints& cs, - vpsc::Rectangles& bbs) -{ - COLA_UNUSED(bbs); - if (dim == _primaryDim) - { - COLA_ASSERT(variable != NULL); - for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - Offset *info = static_cast (*o); - assertValidVariableIndex(vars, info->varIndex); - vpsc::Constraint *constraint = NULL; - if (info->distOffset < 0) - { - // Constrain the objects with negative offsets to be - // to the left of the boundary. - constraint = new vpsc::Constraint(vars[info->varIndex], - variable, -info->distOffset); - } - else - { - // Constrain the objects with positive offsets to be - // to the right of the boundary. - constraint = new vpsc::Constraint(variable, - vars[info->varIndex], info->distOffset); - } - constraint->creator = this; - cs.push_back(constraint); - } - } -} - - -SubConstraintAlternatives -BoundaryConstraint::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) -{ - SubConstraintAlternatives alternatives; - - Offset *info = static_cast - (_subConstraintInfo[_currSubConstraintIndex]); - - assertValidVariableIndex(vs[_primaryDim], info->varIndex); - if (info->distOffset < 0) - { - // Constrain the objects with negative offsets to be - // to the left of the boundary. - vpsc::Constraint constraint = vpsc::Constraint( - vs[_primaryDim][info->varIndex], variable, -info->distOffset); - alternatives.push_back(SubConstraint(_primaryDim, constraint)); - } - else - { - // Constrain the objects with positive offsets to be - // to the right of the boundary. - vpsc::Constraint constraint = vpsc::Constraint( - variable, vs[_primaryDim][info->varIndex], info->distOffset); - alternatives.push_back(SubConstraint(_primaryDim, constraint)); - } - - //fprintf(stderr, "===== BOUNDARYLINE ALTERNATIVES -======\n"); - return alternatives; -} - - - -//----------------------------------------------------------------------------- -// AlignmentConstraint code -//----------------------------------------------------------------------------- - -AlignmentConstraint::AlignmentConstraint(const vpsc::Dim dim, double position) - : CompoundConstraint(dim), - indicator(NULL), - variable(NULL), - _position(position), - _isFixed(false) -{ -} - - -void AlignmentConstraint::addShape(const unsigned int index, - const double offset) -{ - _subConstraintInfo.push_back(new Offset(index, offset)); -} - - -void AlignmentConstraint::updatePosition(const vpsc::Dim dim) -{ - if (dim == _primaryDim) - { - _position = variable->finalPosition; - } -} - - -void AlignmentConstraint::fixPos(double pos) -{ - _position = pos; - _isFixed = true; -} - - -void AlignmentConstraint::unfixPos() -{ - _isFixed = false; -} - - -double AlignmentConstraint::position(void) const -{ - return _position; -} - -bool AlignmentConstraint::isFixed(void) const -{ - return _isFixed; -} - -void AlignmentConstraint::generateVariables(const vpsc::Dim dim, - vpsc::Variables& vars) -{ - if (dim == _primaryDim) - { - // Variable representing the position of a guideline. - variable = new vpsc::Variable(vars.size(), _position, freeWeight); - if (_isFixed) - { - variable->fixedDesiredPosition = true; - variable->weight = 100000; - } - vars.push_back(variable); - } -} - - -void AlignmentConstraint::generateSeparationConstraints(const vpsc::Dim dim, - vpsc::Variables& vars, vpsc::Constraints& cs, - vpsc::Rectangles& bbs) -{ - COLA_UNUSED(bbs); - if (dim == _primaryDim) - { - COLA_ASSERT(variable != NULL); - // Constrain each object to be offset from the guideline by - // some exact amount. - for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - Offset *info = static_cast (*o); - assertValidVariableIndex(vars, info->varIndex); - vpsc::Constraint *constraint = new vpsc::Constraint( - variable, vars[info->varIndex], info->distOffset, true); - constraint->creator = this; - cs.push_back(constraint); - } - } -} - -void AlignmentConstraint::updateShapeOffsetsForDifferentCentres( - const std::vector& offsets, bool forward) -{ - for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - Offset *info = static_cast (*o); - if (offsets[info->varIndex] == 0) - { - continue; - } - - if (forward) - { - info->distOffset -= offsets[info->varIndex]; - } - else - { - info->distOffset += offsets[info->varIndex]; - } - } -} - -void AlignmentConstraint::printCreationCode(FILE *fp) const -{ - fprintf(fp, " AlignmentConstraint *alignment%llu = " - "new AlignmentConstraint(vpsc::%cDIM, %g);\n", - (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y', - _position); - if (_isFixed) - { - fprintf(fp, " alignment%llu->fixPos(%g);\n", - (unsigned long long) this, _position); - } - for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - Offset *info = static_cast (*o); - fprintf(fp, " alignment%llu->addShape(%u, %g);\n", - (unsigned long long) this, info->varIndex, info->distOffset); - } - fprintf(fp, " ccs.push_back(alignment%llu);\n\n", - (unsigned long long) this); -} - - -std::string AlignmentConstraint::toString(void) const -{ - std::ostringstream stream; - stream << "AlignmentConstraint("; - stream << "dim: " << ((_primaryDim == 0) ? 'X' : 'Y'); - stream << ", pos: " << _position; - if (_isFixed) - { - stream << ", fixed: true"; - } -#if 0 - // TODO: buggy. Not the right value. - if (variable) - { - stream << ", varInd: " << variable->id; - } -#endif - stream << "): {"; - bool first = true; - for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - Offset *info = static_cast (*o); - if (!first) - { - stream << ", "; - } - stream << "(" << "rect: " << info->varIndex << ", offset: " << info->distOffset << ")"; - first = false; - } - stream << "}"; - return stream.str(); -} - - -SubConstraintAlternatives -AlignmentConstraint::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) -{ - SubConstraintAlternatives alternatives; - - Offset *info = static_cast - (_subConstraintInfo[_currSubConstraintIndex]); - - assertValidVariableIndex(vs[_primaryDim], info->varIndex); - vpsc::Constraint constraint(variable, vs[_primaryDim][info->varIndex], - info->distOffset, true); - alternatives.push_back(SubConstraint(_primaryDim, constraint)); - - //fprintf(stderr, "===== ALIGN ALTERNATIVES -======\n"); - return alternatives; -} - - -//----------------------------------------------------------------------------- -// SeparationConstraint code -//----------------------------------------------------------------------------- - - -class VarIndexPair : public SubConstraintInfo -{ - public: - VarIndexPair(unsigned ind1, unsigned ind2) - : SubConstraintInfo(ind1), - lConstraint(NULL), - rConstraint(NULL), - varIndex2(ind2) - { - } - VarIndexPair(AlignmentConstraint *l, AlignmentConstraint *r) - : SubConstraintInfo(0), - lConstraint(l), - rConstraint(r), - varIndex2(0) - { - } - unsigned indexL(void) const - { - return (lConstraint) ? - (unsigned) lConstraint->variable->id : varIndex; - } - unsigned indexR(void) const - { - return (rConstraint) ? - (unsigned) rConstraint->variable->id : varIndex2; - } - void updateVarIDsWithMapping(const VariableIDMap& idMap, bool forward) - { - varIndex = idMap.mappingForVariable(varIndex, forward); - varIndex2 = idMap.mappingForVariable(varIndex2, forward); - } - - AlignmentConstraint *lConstraint; - AlignmentConstraint *rConstraint; - unsigned varIndex2; -}; - - -SeparationConstraint::SeparationConstraint(const vpsc::Dim dim, - unsigned l, unsigned r, double g, bool equality) - : CompoundConstraint(dim), - gap(g), - equality(equality), - vpscConstraint(NULL) -{ - _subConstraintInfo.push_back(new VarIndexPair(l, r)); -} - - -SeparationConstraint::SeparationConstraint(const vpsc::Dim dim, - AlignmentConstraint *l, AlignmentConstraint *r, double g, - bool equality) - : CompoundConstraint(dim), - gap(g), - equality(equality) -{ - COLA_ASSERT(l); - COLA_ASSERT(r); - - _subConstraintInfo.push_back(new VarIndexPair(l, r)); -} - - -void SeparationConstraint::printCreationCode(FILE *fp) const -{ - assert(_subConstraintInfo.size() == 1); - VarIndexPair *varIndexPair = (VarIndexPair *) _subConstraintInfo.front(); - if (varIndexPair->lConstraint && varIndexPair->rConstraint) - { - fprintf(fp, " SeparationConstraint *separation%llu = " - "new SeparationConstraint(vpsc::%cDIM, alignment%llu, " - "alignment%llu, %g, %s);\n", - (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y', - (unsigned long long) varIndexPair->lConstraint, - (unsigned long long) varIndexPair->rConstraint, gap, - (equality) ? "true" : "false"); - } - else - { - fprintf(fp, " SeparationConstraint *separation%llu = " - "new SeparationConstraint(vpsc::%cDIM, %u, %u, %g, %s);\n", - (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y', - varIndexPair->indexL(), varIndexPair->indexR(), gap, - (equality) ? "true" : "false"); - } - fprintf(fp, " ccs.push_back(separation%llu);\n\n", - (unsigned long long) this); -} - - -std::string SeparationConstraint::toString(void) const -{ - std::ostringstream stream; - stream << "SeparationConstraint("; - stream << "dim: " << ((_primaryDim == 0) ? 'X' : 'Y'); - stream << ", sep: " << gap; - stream << ", equality: " << ((equality) ? "true" : "false"); - stream << "): {"; - VarIndexPair *varIndexPair = (VarIndexPair *) _subConstraintInfo.front(); - if (varIndexPair->lConstraint && varIndexPair->rConstraint) - { - stream << "(alignment: " << varIndexPair->indexL() << "), "; - stream << "(alignment: " << varIndexPair->indexR() << "), "; - } - else - { - stream << "(rect: " << varIndexPair->indexL() << "), "; - stream << "(rect: " << varIndexPair->indexR() << "), "; - } - stream << "}"; - return stream.str(); -} - - -void SeparationConstraint::generateVariables(const vpsc::Dim dim, - vpsc::Variables& vars) -{ - COLA_UNUSED(dim); - COLA_UNUSED(vars); - - // No additional variables are required! -} - - -SubConstraintAlternatives -SeparationConstraint::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) -{ - SubConstraintAlternatives alternatives; - - VarIndexPair *info = static_cast - (_subConstraintInfo[_currSubConstraintIndex]); - - assertValidVariableIndex(vs[_primaryDim], info->indexL()); - assertValidVariableIndex(vs[_primaryDim], info->indexR()); - vpsc::Constraint constraint(vs[_primaryDim][info->indexL()], - vs[_primaryDim][info->indexR()], gap, equality); - alternatives.push_back(SubConstraint(_primaryDim, constraint)); - - //fprintf(stderr, "===== SEPARATION ALTERNATIVES -======\n"); - return alternatives; -} - - -void SeparationConstraint::generateSeparationConstraints(const vpsc::Dim dim, - vpsc::Variables& vs, vpsc::Constraints& cs, - vpsc::Rectangles& bbs) -{ - COLA_UNUSED(bbs); - if (dim == _primaryDim) - { - VarIndexPair *info = - static_cast (_subConstraintInfo.front()); - - unsigned left = info->indexL(); - unsigned right = info->indexR(); - assertValidVariableIndex(vs, left); - assertValidVariableIndex(vs, right); - vpscConstraint = - new vpsc::Constraint(vs[left], vs[right], gap, equality); - vpscConstraint->creator = this; - cs.push_back(vpscConstraint); - } -} - - -unsigned SeparationConstraint::left(void) const -{ - VarIndexPair *info = - static_cast (_subConstraintInfo.front()); - - return info->indexL(); -} - - -unsigned SeparationConstraint::right(void) const -{ - VarIndexPair *info = - static_cast (_subConstraintInfo.front()); - - return info->indexR(); -} - - -void SeparationConstraint::setSeparation(double gap) -{ - this->gap = gap; - if (vpscConstraint != NULL) - { - vpscConstraint->gap = gap; - } -} - - -//----------------------------------------------------------------------------- -// OrthogonalEdgeConstraint code -//----------------------------------------------------------------------------- - -OrthogonalEdgeConstraint::OrthogonalEdgeConstraint(const vpsc::Dim dim, - unsigned l, unsigned r) - : CompoundConstraint(dim), - left(l), - right(r), - vpscConstraint(NULL) -{ -} - - -void OrthogonalEdgeConstraint::generateVariables(const vpsc::Dim dim, - vpsc::Variables& vars) -{ - COLA_UNUSED(dim); - COLA_UNUSED(vars); - - // No additional variables are required! -} - - -void OrthogonalEdgeConstraint::printCreationCode(FILE *fp) const -{ - fprintf(fp, " /* OrthogonalEdgeConstraint *orthogonal%llu = NULL; */\n\n", - (unsigned long long) this); -} - - -std::string OrthogonalEdgeConstraint::toString(void) const -{ - std::ostringstream stream; - stream << "OrthogonalEdgeConstraint()"; - return stream.str(); -} - - - -SubConstraintAlternatives -OrthogonalEdgeConstraint::getCurrSubConstraintAlternatives( - vpsc::Variables vs[]) -{ - COLA_UNUSED(vs); - - // XXX: What to do here? - _currSubConstraintIndex = _subConstraintInfo.size(); - return SubConstraintAlternatives(); -} - - -void OrthogonalEdgeConstraint::generateSeparationConstraints( - const vpsc::Dim dim, vpsc::Variables& vs, vpsc::Constraints& cs, - vpsc::Rectangles& bbs) -{ - COLA_UNUSED(bbs); - if (dim == _primaryDim) - { - assertValidVariableIndex(vs, left); - assertValidVariableIndex(vs, right); - vpscConstraint = new vpsc::Constraint(vs[left], vs[right], 0, true); - vpscConstraint->creator = this; - cs.push_back(vpscConstraint); - } -} - - -void OrthogonalEdgeConstraint::generateTopologyConstraints(const vpsc::Dim k, - const vpsc::Rectangles& rs, vector const & vars, - vector & cs) -{ - assertValidVariableIndex(vars, left); - assertValidVariableIndex(vars, right); - double lBound, rBound, pos; - if (k == vpsc::HORIZONTAL) - { - lBound = rs[left]->getCentreY(); - rBound = rs[right]->getCentreY(); - pos = rs[left]->getCentreX(); - } - else - { - lBound = rs[left]->getCentreX(); - rBound = rs[right]->getCentreX(); - pos = rs[left]->getCentreY(); - } - double minBound = std::min(lBound, rBound); - double maxBound = std::max(lBound, rBound); - for (unsigned i = 0; i < rs.size(); ++i) - { - if (i==left || i==right) continue; - vpsc::Rectangle *r = rs[i]; - if (r->allowOverlap()) continue; - double l, rMin, rMax, rCentre; - rectBounds(k, r, rMin, rMax, rCentre, l); - if ( ((rMin >= minBound) && (rMin <= maxBound)) || - ((rMax >= minBound) && (rMax <= maxBound))) - { - double g = l / 2; - if (rCentre < pos) - { - cs.push_back(new vpsc::Constraint(vars[i], vars[left], g)); - } - else - { - cs.push_back(new vpsc::Constraint(vars[left], vars[i], g)); - } - } - } -} - - -void OrthogonalEdgeConstraint::rectBounds(const vpsc::Dim k, - vpsc::Rectangle const *r, double& cmin, double& cmax, - double& centre, double & l) const -{ - if (k == vpsc::HORIZONTAL) - { - cmin = r->getMinY(); - cmax = r->getMaxY(); - centre = r->getCentreX(); - l = r->width(); - } - else - { - cmin = r->getMinX(); - cmax = r->getMaxX(); - centre = r->getCentreY(); - l = r->height(); - } -} - - -//----------------------------------------------------------------------------- -// MultiSeparationConstraint code -//----------------------------------------------------------------------------- - -class AlignmentPair : public SubConstraintInfo -{ - public: - AlignmentPair(AlignmentConstraint *ac1, AlignmentConstraint *ac2) - : SubConstraintInfo(0), - alignment1(ac1), - alignment2(ac2) - { - } - AlignmentConstraint *alignment1; - AlignmentConstraint *alignment2; -}; - - -MultiSeparationConstraint::MultiSeparationConstraint(const vpsc::Dim dim, - double minSep, bool equality) - : CompoundConstraint(dim), - indicator(NULL), - sep(minSep), - equality(equality) -{ -} - - -void MultiSeparationConstraint::addAlignmentPair(AlignmentConstraint *ac1, - AlignmentConstraint *ac2) -{ - _subConstraintInfo.push_back(new AlignmentPair(ac1, ac2)); -} - - -void MultiSeparationConstraint::printCreationCode(FILE *fp) const -{ - fprintf(fp, " MultiSeparationConstraint *multiSep%llu = " - "new MultiSeparationConstraint(vpsc::%cDIM, %g, %s);\n", - (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y', sep, - (equality) ? "true" : "false"); - for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - AlignmentPair *pair = static_cast (*o); - fprintf(fp, " multiSep%llu->addAlignmentPair(" - "alignment%llu, alignment%llu);\n", - (unsigned long long) this, - (unsigned long long) pair->alignment1, - (unsigned long long) pair->alignment2); - } - fprintf(fp, " ccs.push_back(multiSep%llu);\n\n", - (unsigned long long) this); -} - - -std::string MultiSeparationConstraint::toString(void) const -{ - std::ostringstream stream; - stream << "MultiSeparationConstraint("; - stream << "dim: " << ((_primaryDim == 0) ? 'X' : 'Y'); - stream << ", sep: " << sep; - stream << ", equality: " << ((equality) ? "true" : "false"); - stream << "): {"; - bool first = true; - for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - if (!first) - { - stream << ", "; - } - AlignmentPair *pair = static_cast (*o); - stream << "(alignment: " << pair->alignment1->variable->id - << ", alignment: " << pair->alignment2->variable->id << ")"; - first = false; - } - stream << "}"; - return stream.str(); -} - - -void MultiSeparationConstraint::generateVariables(const vpsc::Dim dim, - vpsc::Variables& vars) -{ - COLA_UNUSED(dim); - COLA_UNUSED(vars); - - // No additional variables are required! -} - - -SubConstraintAlternatives -MultiSeparationConstraint::getCurrSubConstraintAlternatives( - vpsc::Variables vs[]) -{ - COLA_UNUSED(vs); - - SubConstraintAlternatives alternatives; - - AlignmentPair *info = static_cast - (_subConstraintInfo[_currSubConstraintIndex]); - - AlignmentConstraint *c1 = info->alignment1; - AlignmentConstraint *c2 = info->alignment2; - if (!c1->variable || !c2->variable) - { - throw InvalidConstraint(this); - } - vpsc::Constraint constraint(c1->variable, c2->variable, sep, equality); - alternatives.push_back(SubConstraint(_primaryDim, constraint)); - - //fprintf(stderr, "===== MULTI SEPARATION ALTERNATIVES -======\n"); - return alternatives; -} - - -void MultiSeparationConstraint::setSeparation(double sep) -{ - this->sep = sep; -} - - -void MultiSeparationConstraint::generateSeparationConstraints( - const vpsc::Dim dim, vpsc::Variables& vs, vpsc::Constraints& gcs, - vpsc::Rectangles& bbs) -{ - COLA_UNUSED(vs); - COLA_UNUSED(bbs); - - if (dim == _primaryDim) - { - for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - AlignmentPair *info = static_cast (*o); - AlignmentConstraint *c1 = info->alignment1; - AlignmentConstraint *c2 = info->alignment2; - if (!c1->variable || !c2->variable) - { - throw InvalidConstraint(this); - } - vpsc::Constraint *c = new vpsc::Constraint( - c1->variable, c2->variable, sep, equality); - c->creator = this; - gcs.push_back(c); - cs.push_back(c); - } - } -} - - -//----------------------------------------------------------------------------- -// DistributionConstraint code -//----------------------------------------------------------------------------- - -DistributionConstraint::DistributionConstraint(const vpsc::Dim dim) - : CompoundConstraint(dim), - indicator(NULL) -{ -} - - -void DistributionConstraint::addAlignmentPair(AlignmentConstraint *ac1, - AlignmentConstraint *ac2) -{ - _subConstraintInfo.push_back(new AlignmentPair(ac1, ac2)); -} - - -void DistributionConstraint::generateVariables(const vpsc::Dim dim, - vpsc::Variables& vars) -{ - COLA_UNUSED(dim); - COLA_UNUSED(vars); - - // No additional variables are required! -} - - -void DistributionConstraint::setSeparation(double sep) -{ - this->sep = sep; -} - - -void DistributionConstraint::printCreationCode(FILE *fp) const -{ - fprintf(fp, " DistributionConstraint *distribution%llu = " - "new DistributionConstraint(vpsc::%cDIM);\n", - (unsigned long long) this, (_primaryDim == 0) ? 'X' : 'Y'); - fprintf(fp, " distribution%llu->setSeparation(%g);\n", - (unsigned long long) this, sep); - for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - AlignmentPair *pair = static_cast (*o); - fprintf(fp, " distribution%llu->addAlignmentPair(" - "alignment%llu, alignment%llu);\n", - (unsigned long long) this, - (unsigned long long) pair->alignment1, - (unsigned long long) pair->alignment2); - } - fprintf(fp, " ccs.push_back(distribution%llu);\n\n", - (unsigned long long) this); -} - - -std::string DistributionConstraint::toString(void) const -{ - std::ostringstream stream; - stream << "DistributionConstraint("; - stream << "dim: " << ((_primaryDim == 0) ? 'X' : 'Y'); - stream << ", sep: " << sep; - stream << "): {"; - bool first = true; - for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - if (!first) - { - stream << ", "; - } - AlignmentPair *pair = static_cast (*o); - stream << "(alignment: " << pair->alignment1->variable->id - << ", alignment: " << pair->alignment2->variable->id << ")"; - first = false; - } - stream << "}"; - return stream.str(); -} - - -SubConstraintAlternatives -DistributionConstraint::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) -{ - COLA_UNUSED(vs); - - SubConstraintAlternatives alternatives; - - AlignmentPair *info = static_cast - (_subConstraintInfo[_currSubConstraintIndex]); - AlignmentConstraint *c1 = info->alignment1; - AlignmentConstraint *c2 = info->alignment2; - if (!c1->variable || !c2->variable) - { - throw InvalidConstraint(this); - } - vpsc::Constraint constraint(c1->variable, c2->variable, sep, true); - alternatives.push_back(SubConstraint(_primaryDim, constraint)); - - //fprintf(stderr, "===== DISTRIBUTION ALTERNATIVES -======\n"); - return alternatives; -} - - -void DistributionConstraint::generateSeparationConstraints( - const vpsc::Dim dim, vpsc::Variables& vars, vpsc::Constraints& gcs, - vpsc::Rectangles& bbs) -{ - COLA_UNUSED(vars); - COLA_UNUSED(bbs); - - if (dim == _primaryDim) - { - cs.clear(); - for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - AlignmentPair *info = static_cast (*o); - AlignmentConstraint *c1 = info->alignment1; - AlignmentConstraint *c2 = info->alignment2; - if (!c1->variable || !c2->variable) - { - throw InvalidConstraint(this); - } - vpsc::Constraint *c=new vpsc::Constraint( - c1->variable, c2->variable, sep, true); - c->creator = this; - gcs.push_back(c); - cs.push_back(c); -#if 0 - // The following was an experiment to allow variable distributions - // solved by optimisation rather than satisfying constraints - if(isVariable) { - // set second derivatives of: - // (u + g - v)^2 = g^2 + 2gu + u^2 - 2gv - 2uv + v^2 - (*Q)[make_pair(c1->variable->id,c1->variable->id)]+=w; - (*Q)[make_pair(c2->variable->id,c2->variable->id)]+=w; - (*Q)[make_pair(variable->id,variable->id)]+=w; - (*Q)[make_pair(c1->variable->id,c2->variable->id)]-=w; - (*Q)[make_pair(c2->variable->id,c1->variable->id)]-=w; - (*Q)[make_pair(c1->variable->id,variable->id)]+=w; - (*Q)[make_pair(variable->id,c1->variable->id)]+=w; - (*Q)[make_pair(c2->variable->id,variable->id)]-=w; - (*Q)[make_pair(variable->id,c2->variable->id)]-=w; - } -#endif - } - } -} - - -//----------------------------------------------------------------------------- -// FixedRelativeConstraint code -//----------------------------------------------------------------------------- - -class RelativeOffset : public SubConstraintInfo -{ - public: - RelativeOffset(unsigned indL, unsigned indR, vpsc::Dim dim, - double offset) - : SubConstraintInfo(indL), - varIndex2(indR), - dim(dim), - distOffset(offset) - { - } - void updateVarIDsWithMapping(const VariableIDMap& idMap, bool forward) - { - varIndex = idMap.mappingForVariable(varIndex, forward); - varIndex2 = idMap.mappingForVariable(varIndex2, forward); - } - - unsigned varIndex2; - vpsc::Dim dim; - double distOffset; -}; - - -FixedRelativeConstraint::FixedRelativeConstraint(const vpsc::Rectangles& rs, - std::vector shapeIds, const bool fixedPosition) - : CompoundConstraint(vpsc::XDIM), - m_fixed_position(fixedPosition), - m_shape_vars(shapeIds) -{ - _combineSubConstraints = true; - - // Make sure that m_shape_vars doesn't contain duplicates. - std::sort(m_shape_vars.begin(), m_shape_vars.end()); - std::vector::iterator last = - std::unique(m_shape_vars.begin(), m_shape_vars.end()); - m_shape_vars.erase(last, m_shape_vars.end()); - - unsigned firstId = UINT_MAX; - COLA_ASSERT(m_shape_vars.size() >= 2); - for (std::vector::iterator it = m_shape_vars.begin(); - it != m_shape_vars.end(); ++it) - { - COLA_ASSERT(*it < rs.size()); - - if (it == m_shape_vars.begin()) - { - firstId = *it; - } - else - { - unsigned thisId = *it; - _subConstraintInfo.push_back( - new RelativeOffset(firstId, thisId, vpsc::XDIM, - rs[thisId]->getCentreX() - rs[firstId]->getCentreX())); - _subConstraintInfo.push_back( - new RelativeOffset(firstId, thisId, vpsc::YDIM, - rs[thisId]->getCentreY() - rs[firstId]->getCentreY())); - } - } -} - -void FixedRelativeConstraint::updateVarIDsWithMapping( - const VariableIDMap& idMap, bool forward) -{ - CompoundConstraint::updateVarIDsWithMapping(idMap, forward); - - // We need to map variables in m_shape_vars too, - // since this is used in generateVariables(). - for (size_t i = 0; i < m_shape_vars.size(); ++i) - { - m_shape_vars[i] = idMap.mappingForVariable(m_shape_vars[i], forward); - } -} - - - -void FixedRelativeConstraint::generateVariables(const vpsc::Dim dim, - vpsc::Variables& vars) -{ - COLA_UNUSED(dim); - COLA_UNUSED(vars); - - // No additional variables are required! - - // Fix shape positions if required. - if (m_fixed_position) - { - for (std::vector::iterator it = m_shape_vars.begin(); - it != m_shape_vars.end(); ++it) - { - vars[*it]->fixedDesiredPosition = true; - vars[*it]->weight = 100000; - } - } -} - - -void FixedRelativeConstraint::printCreationCode(FILE *fp) const -{ - fprintf(fp, " std::vector fixedRelativeSet%llu;\n", - (unsigned long long) this); - for (std::vector::const_iterator it = m_shape_vars.begin(); - it != m_shape_vars.end(); ++it) - { - fprintf(fp, " fixedRelativeSet%llu.push_back(%u);\n", - (unsigned long long) this, *it); - } - fprintf(fp, " FixedRelativeConstraint *fixedRelative%llu = " - "new FixedRelativeConstraint(rs, fixedRelativeSet%llu, %s);\n", - (unsigned long long) this, (unsigned long long) this, - (m_fixed_position) ? "true" : "false"); - fprintf(fp, " ccs.push_back(fixedRelative%llu);\n\n", - (unsigned long long) this); -} - - -std::string FixedRelativeConstraint::toString(void) const -{ - std::ostringstream stream; - stream << "FixedRelativeConstraint("; - stream << "fixedPos: " << ((m_fixed_position) ? "true" : "false"); - stream << "): {"; - bool first = true; - for (std::vector::const_iterator it = m_shape_vars.begin(); - it != m_shape_vars.end(); ++it) - { - if (!first) - { - stream << ", "; - } - stream << "(rect: " << *it << ")"; - first = false; - } - stream << "}"; - return stream.str(); -} - - -SubConstraintAlternatives -FixedRelativeConstraint::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) -{ - COLA_UNUSED(vs); - - SubConstraintAlternatives alternatives; - - RelativeOffset *offset = static_cast - (_subConstraintInfo[_currSubConstraintIndex]); - - vpsc::Dim dim = offset->dim; - vpsc::Constraint constraint(vs[dim][offset->varIndex], - vs[dim][offset->varIndex2], offset->distOffset, true); - alternatives.push_back(SubConstraint(dim, constraint)); - - //fprintf(stderr, "===== FixedRelativeConstraint ALTERNATIVES -======\n"); - return alternatives; -} - - -void FixedRelativeConstraint::generateSeparationConstraints( - const vpsc::Dim dim, vpsc::Variables& vars, vpsc::Constraints& ccs, - vpsc::Rectangles& bbs) -{ - COLA_UNUSED(vars); - COLA_UNUSED(bbs); - - for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - RelativeOffset *offset = static_cast (*o); - if (dim != offset->dim) - { - continue; - } - - assertValidVariableIndex(vars, offset->varIndex); - assertValidVariableIndex(vars, offset->varIndex2); - vpsc::Constraint *c = - new vpsc::Constraint(vars[offset->varIndex], - vars[offset->varIndex2], offset->distOffset, true); - c->creator = this; - ccs.push_back(c); - } -} - - -//----------------------------------------------------------------------------- -// PageBoundaryConstraint code -//----------------------------------------------------------------------------- - -class PageBoundaryShapeOffsets : public SubConstraintInfo -{ - public: - PageBoundaryShapeOffsets(unsigned ind, double xOffset, double yOffset) : - SubConstraintInfo(ind) - { - halfDim[0] = xOffset; - halfDim[1] = yOffset; - } - double halfDim[2]; // half width and height values; -}; - - -PageBoundaryConstraints::PageBoundaryConstraints(double xLow, double xHigh, - double yLow, double yHigh, double weight) - : CompoundConstraint(vpsc::HORIZONTAL) -{ - COLA_ASSERT(xLow < xHigh); - COLA_ASSERT(yLow < yHigh); - - leftMargin[vpsc::XDIM] = xLow; - rightMargin[vpsc::XDIM] = xHigh; - leftMargin[vpsc::YDIM] = yLow; - rightMargin[vpsc::YDIM] = yHigh; - - for (unsigned i = 0; i < 2; ++i) - { - actualLeftMargin[i] = leftMargin[i]; - actualRightMargin[i] = rightMargin[i]; - leftWeight[i] = weight; - rightWeight[i] = weight; - vl[i] = NULL; - vr[i] = NULL; - } -} - - -void PageBoundaryConstraints::addShape(unsigned id, double halfW, double halfH) -{ - _subConstraintInfo.push_back(new PageBoundaryShapeOffsets(id, halfW, halfH)); -} - - -void PageBoundaryConstraints::printCreationCode(FILE *fp) const -{ - fprintf(fp, " PageBoundaryConstraints *pageBoundary%llu = " - "new PageBoundaryConstraints(%g, %g, %g, %g, %g);\n", - (unsigned long long) this, leftMargin[vpsc::XDIM], - rightMargin[vpsc::XDIM], leftMargin[vpsc::YDIM], - rightMargin[vpsc::YDIM], leftWeight[0]); - for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - PageBoundaryShapeOffsets *offsets = - static_cast (*o); - fprintf(fp, " pageBoundary%llu->addShape(%u, %g, %g);\n", - (unsigned long long) this, offsets->varIndex, - offsets->halfDim[XDIM], offsets->halfDim[YDIM]); - } - fprintf(fp, " ccs.push_back(pageBoundary%llu);\n\n", - (unsigned long long) this); -} - - -std::string PageBoundaryConstraints::toString(void) const -{ - std::ostringstream stream; - stream << "PageBoundaryConstraints("; - stream << "xLow: " << leftMargin[vpsc::XDIM]; - stream << ", xHigh: " << rightMargin[vpsc::XDIM]; - stream << ", yLow: " << leftMargin[vpsc::YDIM]; - stream << ", yHigh: " << rightMargin[vpsc::YDIM]; - stream << ", weight: " << leftWeight[0]; - stream << "): {"; - bool first = true; - for (SubConstraintInfoList::const_iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - if (!first) - { - stream << ", "; - } - PageBoundaryShapeOffsets *offsets = - static_cast (*o); - stream << "(rect: " << offsets->varIndex; - stream << ", halfWidth: " << offsets->halfDim[XDIM]; - stream << ", halfHeight: " << offsets->halfDim[YDIM]; - stream <<")"; - first = false; - } - stream << "}"; - return stream.str(); -} - -SubConstraintAlternatives -PageBoundaryConstraints::getCurrSubConstraintAlternatives(vpsc::Variables vs[]) -{ - COLA_UNUSED(vs); - - // Page boundary constraints do not need to be evaluated at the - // time of makeFeasible, so we return an empty list here. - _currSubConstraintIndex = _subConstraintInfo.size(); - return SubConstraintAlternatives(); -} - - -void PageBoundaryConstraints::updatePosition(const vpsc::Dim dim) -{ - if (vl[dim]) - { - actualLeftMargin[dim] = vl[dim]->finalPosition; - } - - if (vr[dim]) - { - actualRightMargin[dim] = vr[dim]->finalPosition; - } -} - - -double PageBoundaryConstraints::getActualLeftMargin(const vpsc::Dim dim) -{ - return actualLeftMargin[dim]; -} - - -double PageBoundaryConstraints::getActualRightMargin(const vpsc::Dim dim) -{ - return actualRightMargin[dim]; -} - - -void PageBoundaryConstraints::generateVariables(const vpsc::Dim dim, - vpsc::Variables& vars) -{ - // create 2 dummy vars, based on the dimension we are in - if (leftWeight[dim]) - { - vars.push_back(vl[dim] = new vpsc::Variable(vars.size(), - leftMargin[dim], leftWeight[dim])); - vl[dim]->fixedDesiredPosition = true; - } - - if (rightWeight[dim]) - { - vars.push_back(vr[dim] = new vpsc::Variable(vars.size(), - rightMargin[dim], rightWeight[dim])); - vr[dim]->fixedDesiredPosition = true; - } -} - - -void PageBoundaryConstraints::generateSeparationConstraints( - const vpsc::Dim dim, vpsc::Variables& vs, vpsc::Constraints& cs, - vpsc::Rectangles& bbs) -{ - COLA_UNUSED(bbs); - // For each of the "real" variables, create a constraint that puts - // that var between our two new dummy vars, depending on the dimension. - for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - PageBoundaryShapeOffsets *info = - static_cast (*o); - assertValidVariableIndex(vs, info->varIndex); - if (vl[dim]) - { - vpsc::Constraint *constraint = new vpsc::Constraint(vl[dim], - vs[info->varIndex], info->halfDim[dim]); - constraint->creator = this; - cs.push_back(constraint); - } - - if (vr[dim]) - { - vpsc::Constraint *constraint = new vpsc::Constraint( - vs[info->varIndex], vr[dim], info->halfDim[dim]); - constraint->creator = this; - cs.push_back(constraint); - } - } -} - - -//----------------------------------------------------------------------------- -// Support code -//----------------------------------------------------------------------------- - - -struct GenerateVariables -{ - GenerateVariables(const vpsc::Dim dim, vpsc::Variables& vars) - : dim(dim), - vars(vars) - { - } - void operator() (CompoundConstraint *c) - { - c->generateVariables(dim, vars); - } - - const vpsc::Dim dim; - vpsc::Variables& vars; -}; - - -struct GenerateSeparationConstraints -{ - GenerateSeparationConstraints(const vpsc::Dim dim, vpsc::Variables& vars, - vpsc::Constraints& cs, vpsc::Rectangles& bbs) - : dim(dim), - vars(vars), - cs(cs), - bbs(bbs) - { - } - void operator() (CompoundConstraint *c) - { - c->generateSeparationConstraints(dim, vars, cs, bbs); - } - const vpsc::Dim dim; - vpsc::Variables& vars; - vpsc::Constraints& cs; - vpsc::Rectangles& bbs; -}; - - -void generateVariablesAndConstraints(CompoundConstraints& ccs, - const vpsc::Dim dim, vpsc::Variables& vars, vpsc::Constraints& cs, - vpsc::Rectangles& bbs) -{ - for_each(ccs.begin(), ccs.end(), - GenerateVariables(dim, vars)); - for_each(ccs.begin(), ccs.end(), - GenerateSeparationConstraints(dim, vars, cs, bbs)); -} - - -void generateVariables(CompoundConstraints& ccs, const vpsc::Dim dim, - vpsc::Variables& vars) -{ - for_each(ccs.begin(), ccs.end(), - GenerateVariables(dim, vars)); -} - - -CompoundConstraint::CompoundConstraint(vpsc::Dim primaryDim, - unsigned int priority) : - _primaryDim(primaryDim), - _secondaryDim((vpsc::Dim) ((primaryDim + 1) % 2)), - _priority(priority), - _combineSubConstraints(false), - _currSubConstraintIndex(0) -{ -} - - -CompoundConstraint::~CompoundConstraint() -{ - // Free memory from the subConstraintInfo list. - for_each(_subConstraintInfo.begin(), _subConstraintInfo.end(), delete_object()); - _subConstraintInfo.clear(); -} - - -vpsc::Dim CompoundConstraint::dimension(void) const -{ - return _primaryDim; -} - - -unsigned int CompoundConstraint::priority(void) const -{ - return _priority; -} - - -void CompoundConstraint::printCreationCode(FILE *fp) const -{ - COLA_UNUSED(fp); - - // Do nothing. Subclasses can implement this. -} - -void CompoundConstraint::updateVarIDsWithMapping(const VariableIDMap& idMap, - bool forward) -{ - for (SubConstraintInfoList::iterator o = _subConstraintInfo.begin(); - o != _subConstraintInfo.end(); ++o) - { - (*o)->updateVarIDsWithMapping(idMap, forward); - } -} - - -std::list CompoundConstraint::subConstraintObjIndexes(void) const -{ - std::list idList; - for (size_t i = 0; i < _subConstraintInfo.size(); ++i) - { - idList.push_back(_subConstraintInfo[i]->varIndex); - } - return idList; -} - - -bool CompoundConstraint::subConstraintsRemaining(void) const -{ - return _currSubConstraintIndex < _subConstraintInfo.size(); -} - - -void CompoundConstraint::markAllSubConstraintsAsInactive(void) -{ - for (size_t i = 0; i < _subConstraintInfo.size(); ++i) - { - _subConstraintInfo[i]->satisfied = false; - } - _currSubConstraintIndex = 0; -} - - -void CompoundConstraint::markCurrSubConstraintAsActive(const bool satisfiable) -{ - _subConstraintInfo[_currSubConstraintIndex]->satisfied = satisfiable; - - _currSubConstraintIndex++; -} - - -void CompoundConstraint::assertValidVariableIndex(const vpsc::Variables& vars, - const unsigned index) -{ - if (index >= vars.size()) - { - throw InvalidVariableIndexException(this, index); - } -} - - -bool CompoundConstraint::shouldCombineSubConstraints(void) const -{ - return _combineSubConstraints; -} - - -UnsatisfiableConstraintInfo::UnsatisfiableConstraintInfo( - const vpsc::Constraint *c) - : leftVarIndex(c->left->id), - rightVarIndex(c->right->id), - separation(c->gap), - equality(c->equality), - cc((CompoundConstraint *)c->creator) -{ -} - -// Variable mapping. - -VariableIDMap::VariableIDMap() -{ -} - -VariableIDMap::~VariableIDMap() -{ -} - -typedef std::pair IDPair; -typedef std::list IDPairList; - -bool VariableIDMap::addMappingForVariable(const unsigned from, - const unsigned to) -{ - bool found = false; - for (IDPairList::iterator it = m_mapping.begin(); it != m_mapping.end(); - ++it) - { - IDPair& ids = *it; - - if (ids.first == from) - { - found = true; - break; - } - } - - if (!found) - { - m_mapping.push_back(std::make_pair(from, to)); - return true; - } - //fprintf(stderr, "VariableIDMap: mapping already exists for var %u\n", from); - return false; -} - -void VariableIDMap::printCreationCode(FILE *fp) const -{ - fprintf(fp, " cola::VariableIDMap idMap;\n"); - for (IDPairList::const_iterator it = m_mapping.begin(); - it != m_mapping.end(); ++it) - { - fprintf(fp, " idMap.addMappingForVariable(%u, %u);\n", - it->first, it->second); - } - fprintf(fp, " \n"); -} - -unsigned VariableIDMap::mappingForVariable(const unsigned var, - bool forward) const -{ - for (IDPairList::const_iterator it = m_mapping.begin(); - it != m_mapping.end(); ++it) - { - const IDPair& ids = *it; - - if (forward) - { - if (ids.first == var) - { - return ids.second; - } - } - else // (!forward) - { - if (ids.second == var) - { - return ids.first; - } - } - } - - //fprintf(stderr, "Warning: mapping not found for var %u\n", var); - - // Just return original variable index. - return var; -} - -void VariableIDMap::clear(void) -{ - m_mapping.clear(); -} - - -} // namespace cola - -- cgit v1.2.3